即: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 于是对偶问题的对偶是原问题。-对称性 互为对偶