第二章线性规划的对偶理论(Dual Linear Programming, DLP)原问题与对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划2025/4/5
2025/4/5 2 第二章 线性规划的对偶理论 ( Dual Linear Programming, DLP) ◼ 原问题与对偶问题 ◼ 对偶问题的基本性质 ◼ 影子价格 ◼ 对偶单纯形法 ◼ 灵敏度分析 ◼ 参数线性规划
81对偶问题的提出线性规划单纯形法的矩阵描述设有线性规划问题的标准形式max z = CX[AX =bA=(B,NI)将系数矩阵表示成：s.tX≥0初始解非基变量基变量BNI初始单纯形表Clbaj0→ON基可行解基变量非基变量初等行变换后CBN'b'B-110a_→On'-yi..-ym初始表中是I的位置，经变换后成为B-12025/4/53
2025/4/5 3 §1 对偶问题的提出 一、 线性规划单纯形法的矩阵描述 设有线性规划问题的标准形式 = = 0 . max X AX b st z CX 将系数矩阵表示成： A = (B,N I) 初始单纯形表 初始解 非基变量 基变量 0 b B N I j → N 基可行解 基变量 非基变量 0 初等行变换后 b −1 B N I j → N m − y .,−y 1, CI CB 初始表中是I 的位置，经变换后成为 −1 B
其中 Y=(yi,y2.. ym)-Y=0-C,B-1Y=C,B-1记则（αn"=C-C,B-"N=C-YNb'= B-'b;N'=B-'N,或 P'=B-"P例：书P36例10，验证上述公式。上述公式对于灵敏度分析很有帮助。2025/4/5
2025/4/5 4 其中 ( , ,., ) 1 2 m Y = y y y 1 0 − −Y = −CB B 记 −1 Y = CB B 则 N = CN −CB B N = CN −YN − 1 例：书 P36 例10，验证上述公式。 N B N Pj B Pj 1 1 , − − ; = 或 = 1 b B b − = 上述公式对于灵敏度分析很有帮助
对偶问题的提出二设有原问题例 甲方生产计划问题：乙方租借设备：1II能力22设备A12甲方以何种价格将设备A、B、设备B4016C租借给乙方比较合理？请为设备C0515其定价。利润23I，Ⅱ各生产多少,可获最大利润?解：假设A、B、C的单位租金分别为 Ji,2,Y3思路：就甲方而言，租金收入应不低于将设备用于自已生产时的利润。2025/4/5
2025/4/5 5 例 甲方生产计划问题： Ⅰ Ⅱ 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 Ⅰ，Ⅱ各生产多少, 可获最大利润? 二、 对偶问题的提出 设有原问题 乙方租借设备： 甲方以何种价格将设备A、B、 C租借给乙方比较合理？请为 其定价。 解： 假设A、B、C的单位租金 分别为 y1 , y2 , y3 。 思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润
所以：生产产品I的资源用于出租时，租金收入应满足：2y +4y, ≥2类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：2y +5y, ≥3总的租金收入：12yi+16y2+15y3而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：min W =12y +16y2 +15y3≥22yi +4y2s.t2y1+5y,≥3Ji,y2, y, > 02025/4/5
2025/4/5 6 而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好， 这样双方才可能达成协议。 于是得到下述的线性规划模型： 所以：生产产品Ⅰ的资源用于出租时，租金收入应满足： 2y1 + 4y2 2 类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足： 2y1 + 5y3 3 总的租金收入： 12 1 16 2 15 3 y + y + y min 12 1 16 2 15 3 W = y + y + y s.t 2y1 + 4y2 2 , , 0 2 5 3 1 2 3 1 3 + y y y y y