如何写出非规范的原问题相应的对偶问题，1.目标函数MINMAX≤2.约束条件≥3.约束条件=+?≤0或 无约束变量4.?例：P52例2，写出下面规划的对偶规划minz = 7x +4x2 -3x[- 4x +2x2 -6x, ≤24-3x -6x2 -4x ≥155x2 +3x, = 30≤0,x无约束，,≥0122024-10-27
2024-10-27 12 如何写出非规范的原问题相应的对偶问题： 1. 目标函数MIN MAX 2. 约束条件 3. 约束条件 = ? 4. 变量 ? 0 或 无约束 0 或 无约束 例：P52 例2，写出下面规划的对偶规划 0, 0 5 3 30 3 6 4 15 4 2 6 24 min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 无约束
解：原问题的对偶问题：min z= 7x, +4x2 -3x3- 4x +2x2 -6x, ≤24y1- 3xi -6x2 - 4x, ≥15y2J35x2 +3xg =30≤0,x无约束，≥0maxw =-24yi +15y2 +30y则对偶问题是[- 4y1 +3y2≤-7xi-2y1-6y2 +5y, = 4X2X36y1-4y2 +3x, ≤-3[J,≥0,x,无约束132024-10-27
2024-10-27 13 解：原问题的对偶问题： 3 2 1 y y y 则对偶问题是 1 2 3无约束 1 2 3 1 2 3 1 2 1 2 3 , 0, 6 4 3 3 2 6 5 4 4 3 7 max 24 15 30 y y x y y x y y y y y w y y y 3 2 1 x x x 0, 0 5 3 30 3 6 4 15 4 2 6 24 min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 无约束
小结：对偶问题与原问题的关系：目标函数：MIN目标函数：MAX对变量：m个变量约束条件：m个约束原≤≥0偶间(2)间(≤ 0)题题=无约束变量：n个变量约束条件：n个约束≥≥0(≤)(≤0)无约束约束条件右端项目标函数系数目标函数系数约束条件右端项142024-10-27
2024-10-27 14 小结：对偶问题与原问题的关系： 原 问 题 对 偶 问 题 目标函数：MAX 约束条件：m个约束 变量 ： n个变量 目标函数：MIN ( ) 无约束 ( 0) 0 约束条件：n个约束 变量 ： m个变量 无约束 ( 0) 0 ( ) 约束条件右端项 目标函数系数 目标函数系数 约束条件右端项
83对偶问题的基本性质就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质：1.弱对偶性如果Xj，Yi，i=1,,m，j=l,,n分别是原问题和对偶问题的可行解，则恒有CX,<Yb证明："X,是原问题的可行解，.. AX<b又：Y,是对偶问题的可行解，.Y,AX≤Y,b（可行解必须Y≥0）Y,A≥C,Y,AX,≥CX,CX≤Y,AX,≤Y,b.. CX<Yb152024-10-27
2024-10-27 15 §3 对偶问题的基本性质 就上节所讨论的一般的线性规划问题及其对偶问题，有如下的性质： 1. 弱对偶性 如果 分别是原问 题和对偶问题的可行解，则恒有 证明：∵Xj是原问题的可行解， ∴ AXj≤b 又 ∵Yi是对偶问题的可行解， ∴ YiAXj≤Yib（∵可行解必须 Yi≥0） YiA≥C, YiAXj≥CXj CXj≤YiAXj≤Yib ∴ CXj≤Yib CX j Yib X j , Y i , i 1,, m, j 1,, n
如果 ，Y,i=l,...,m,j=l,.,n分2.最优性别是原问题和对偶问题的可行解，且有 CX，=Yb,则x,，Y，i=1,,m，j=1,,n分别是原问题和对偶问题的最优解。证明设Xj,Yi，i=l,,m，j=l,,n分别是原问题和对偶问题的最优解，则由弱对偶性，CX,≤CX",≤Y"b≤Yb又： cX,=Yb,.. CX, =CX", =Y"b=Yb：文，是原问题的最优解。Y，是对偶问题的最优解。162024-10-27
2024-10-27 16 2. 最优性 如果 分 别是原问题和对偶问题的可行解，且有 则 分别是原问题和对偶问题的最优解。 , ˆX j Yi , i 1, , m, j 1, , n ˆ CX j Ybi ˆ ˆ , ˆX j 证明 设 分别是原问题和 对偶问题的最优解，则由弱对偶性， 又∵ ∴ ∴ 是原问题的最优解。 是对偶问题的最优解。 , * X j CX CX Y b Y bi j i j ˆ ˆ * * Yi , i 1, , m , j 1, , n ˆ Y i , i 1, , m, j 1, , n * CX j Ybi ˆ ˆ CX j CX j Y ib Yib ˆ ˆ * * X j ˆ Yiˆ