《运筹学》课程教学课件（讲稿）第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 偶 问 题

即:max Z = CXminW =b'y对原偶AX≤bA'Y≥CT间间X≥0题Y≥0题2024-10-27

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

8 2 原问题与对偶问题对于一般的线性规划问题maxz = Cxi +Cx2 +...+cnxn≤b→yiaiiX +ai2X2 +...+ainxna2ix +a22X2 +...+a2nn ≤b2→y2am1Xi +am2X2 +...+ammXn≤bm→ymXi,X2,"",Xn ≥02024-10-27

2024-10-27 8                     , , , 0 1 2 1 1 2 2 21 1 22 2 2 2 2 11 1 12 2 1 1 1 n m m mn n m m n n n n x x x a x a x a x b y a x a x a x b y a x a x a x b y      n n z  c x  c x  c x m 1 1 2 2 ax §2 原问题与对偶问题 对于一般的线性规划问题

类似于前面的资源定价问题，每一个约束条件对应一个“对偶变量”，它就相当于给各资源的单位定价。于是我们有如下的对偶规划：minW =byi +b,y2 +...+bmymauyi+a2iy2+...+amym≥Ci→xi→×2a12J+a22y2+...+am2ym≥C2ainJi+a2ny2+...+amnym≥Cn→xn[J1, Y2,", ym ≥02024-10-27

2024-10-27 9 类似于前面的资源定价问题，每一个约束条件对应一个“ 对偶变量” ，它就 相当于给各资源的单位定价。于是我们有如下的对偶规划：                     , , , 0 1 2 1 1 2 2 12 1 22 2 2 2 2 11 1 21 2 1 1 1 m n n mn m n n m m m m y y y a y a y a y c x a y a y a y c x a y a y a y c x      m m W  b y  b y  b y m 1 1 2 2 in

对偶问题与原问题的关系：目标函数：MIN目标函数：MAXminW = Yb对max Z = CX原偶问约束条件：m个约束约束条件：n个约束河题AX≤bYA ≥C题变量：n个变量变量：m个变量X≥0Y≥0这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题102024-10-27

2024-10-27 10 对偶问题与原问题的关系： 原 问 题 对 偶 问 题 目标函数：MAX 约束条件：m个约束 变量 ： n个变量 目标函数：MIN AX  b X  0 约束条件：n个约束 变量 ： m个变量 max Z  CX minW  Yb YA  C Y  0 这是规范形式 的原问题，由此写出其对偶问题如右方所示，那么，当原 问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规 范的原问题，再写出对偶问题

解先将该问题化为规范形式例写出下述规划的对偶问题max(-W)=-12yi -16y2 -15yminW =12y +16y2 +15y3≤-2-2y1-4y2s.t≥22y +4y2s.t-2y1-5y, ≤-32y1+5y, ≥3Ji,y2 >0Ji,y2 >0互为对偶于是对偶问题即为：也即为：min(-Z)=-2x, -3x2maxZ = 2x1 +3x22x, + 2 x2 ≤12- 2x -2x, ≥ -124 x1≤ 16- 4x1≥-165x2 ≤15-5x2 ≥ -15Xi,X2 ≥ 0Xi,X2 ≥ 0于是对偶问题的对偶是原问题。-对称性2024-10-2711

2024-10-27 11 例 写出下述规划的对偶问题 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 于是对偶问题即为： 12 1 16 2 15 3 max(W)   y  y  y s.t -2y1 -4y2 -2 , 0 2 5 3 1 2 1 3      y y y y          , 0 - 5 -15 - 4 -16 - 2 - 2 -12 1 2 2 1 1 2 x x x x x x 1 2 min ( Z )  2 x  3 x 解 先将该问题化为规范形式 也即为：           , 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 于是对偶问题的对偶是原问题。-对称性 互为对偶