《运筹学》课程教学课件（讲稿）第2章 线性规划的对偶理论（Dual Linear Programming, DLP）

第二章线性规划的对偶理论(Dual Linear Programming,DLP)，原问题与对偶问题对偶问题的基本性质对偶单纯形法灵敏度分析2024-10-27

2024-10-27 2 第二章 线性规划的对偶理论 ( Dual Linear Programming, DLP) n 原问题与对偶问题 n 对偶问题的基本性质 n 对偶单纯形法 n 灵敏度分析

s1 对偶问题的提出设有原问题例甲方生产计划问题：乙方租借设备：11[能力12设备A212甲方以何种价格将设备A、B、设备B0416C租借给乙方比较合理？请为0515设备C其定价。利润23I，Ⅱ各生产多少，可获最大利润？解：假设A、B、C的单位租金分别为 123°思路：就甲方而言，租金收入应不低于将设备用于自已生产时的利润。2024-10-273

2024-10-27 3 例 甲方生产计划问题： Ⅰ Ⅱ 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 Ⅰ，Ⅱ各生产多少, 可获最大利润? 设有原问题 乙方租借设备： 甲方以何种价格将设备A、B、 C租借给乙方比较合理？ 请为 其定价。 解： 假设A、B、C的单位租金 分别为 。 思路： 就甲方而言， 租金收入应不低于将设备用于自己生产时的利润。 §1 对偶问题的提出 1 2 3 y , y , y

所以：生产产品的资源用于出租时，租金收入应满足：2yi+4y2 ≥2类似的，生产产品ⅡI的资源用于出租时，租金收入应满足：2y+5y, ≥3总的租金收入：12yi+16y2+15y3而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好这样双方才可能达成协议。于是得到下述的线性规划模型：minW =12y +16y2 +15y3≥2s.t?yi +4y+5y, ≥32yl(Vi, y2, y3 > 02024-10-27

2024-10-27 4 而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好， 这样双方才可能达成协议。 于是得到下述 的线性规划模型： 所以：生产产品Ⅰ的资源用于出租时，租金收入应满足： 2y1  4y2  2 类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足： 2y1  5y3  3 总的租金收入： 12 1 16 2 15 3 y  y  y m 12 1 16 2 15 3 inW  y  y  y s.t 2y1  4y2  2 , , 0 2 5 3 1 2 3 1 3    y y y y y

原问题对偶问题Z=2xi+3x2maxminW =12y +16y2 +15y32 x + 2 x2 ≤12≥2(2y1+4y2s.t4 x1≤ 162yi+5y, ≥35x2 ≤ 15(J1,y2 >0X1, X2 ≥ 0(12)用矩阵将上述原问题对偶问题写出ys)16minW = Yb= (y)y2XmaxZ =CX =(2,3(15)X252(12)0≥(23)= CYA = (y)4y2y3)16=bAX -50(15)0Y≥0X≥02024-10-27

2024-10-27 5           , 0 5 15 4 16 2 2 12 1 2 2 1 1 2 x x x x x x m 2 1 3 2 ax Z  x  x m 12 1 16 2 15 3 inW  y  y  y s.t 2y1  4y2  2 , 0 2 5 3 1 2 1 3    y y y y  原问题 对偶问题 用矩阵将上述原问题对偶问题写出 0 15 16 12 0 5 4 0 2 2 max (2,3) 2 1 2 1                              X b x x AX x x Z CX       0 2 3 0 5 4 0 2 5 15 16 12 min 1 2 3 1 2 3                   Y YA y y y C W Yb y y y

即:max Z = CXminW = Yb对原偶AX≤bYA ≥C问问X≥0Y≥0题题2024-10-27

2024-10-27 6 即： 原 问 题 0 max    X AX b Z CX 0 min    Y YA C 对 W Yb 偶 问 题