§2原问题与对偶问题 (1)对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负；目标函数求极小值时，所有约束条件为≥号，变量非 负. P: maxZ =CX D minw=b'Y AX≤b ATY≥CI X≥0 Y≥0 (2)非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题。 2014-12-15 6
2014-12-15 6 §2 原问题与对偶问题 （1）对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负；目标函数求极小值时，所有约束条件为≥号，变量非 负. X 0 AX b maxZ CX P： Y 0 A Y C : min T T D W b Y T (2) 非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题
§2原问题与对偶问题 [例1】写出线性规划问题的对偶问题 min0=12y+16y2+15y3 2y+42+03≥2 s.t2y+0y2+5y3≥3 y1,y2,y3≥0 解：首先将原问题变形为对称形式 对偶问题 maxo=-12y1-16y2-15y3 minz=-2x-3x2 -21-4y2 ≤-2 -2x1-2x2≥-12 s.t.-2y -4x1 ≥-16 -5y3≤-3 S.t. -5x2≥-15 y1,y2,y3≥0 2014-12-15 x1,x2≥0
2014-12-15 7 §2 原问题与对偶问题 , , 0 2 0 5 3 2 4 0 2 . . min 12 16 15 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y st y y y [例1] 写出线性规划问题的对偶问题 解：首先将原问题变形为对称形式 , , 0 2 5 3 2 4y 2 . . max 12 16 15 1 2 3 1 3 1 2 1 2 3 ' y y y y y y st y y y 对偶问题 , 0 5 15 4 16 2 2 12 . . min ' 2 3 1 2 2 1 1 2 1 2 x x x x x x st z x x
§2原问题与对偶问题 [例2]写出下述线性规划的对偶问题 minz=7x+4x2-3x3 -4x1+2x2-6x3≤24 -3x1-6x2-7x3≥15 s.t. 5x2+3x3=30 x≤0，x2无约束，x3≥0 解：(1)令×1'=-X1,X2=2'-X2”, 等式约束化为：5X2+3X3≥30和5X2+3X3≤30，有 minz=-7x+4x2'-4x2"-3x3 -4x,'-2x2'+2x2"+6x3≥-24 3x1'-6x2'+6x2”-7x3≥15 5x2'-5x2"+3x3≥30 -5x2'+5x2"-3x3≥-30 2014-12-15 x',x2',x2",x3≥0 8
2014-12-15 8 §2 原问题与对偶问题 0, , 0 5 3 30 3 6 7 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 st z x x x 无约束 [例2] 写出下述线性规划的对偶问题 解：（1）令x1′= - x1，x2 = x2 ′- x2 ″ ， 等式约束化为: 5X2+3X3≥30 和 5X2 +3X3≤30，有 ', ', '', 0 5 ' 5 '' 3 30 5 '-5 '' 3 30 3 ' 6 ' 6 '' 7 15 4 ' 2 ' 2 '' 6 24 . . min 7 ' 4 ' 4 '' 3 1 2 2 3 2 2 3 2 2 3 1 2 2 3 1 2 2 3 1 2 2 3 x x x x x x x x x x x x x x x x x x st z x x x x
§2原问题与对偶问题 (2)令上式四个约束条件对应的对偶变量分别为y1,y2,Y3,y4,则其 对偶问题为： maxo=-24y+15y2+30y3-30y4 -4y+3y2≤-7 -2y-6y2+5y3-5y4≤4 s.t2y1+6y2-5y3+5y4≤-4 6y-7y2+3y3-3y4≤-3 y2:34≥0 (3)令y1'=-y1,y⅓'=y3-y4,中间两个约束条件合成等式约束，有 maxo-24y'+15y2+30y3 minz=7x+4x2-3x3 -4y'-3y2≥7 4x1+2x2-6x3≤24 2y’6y2+5y3'=4 s.t. 3x-6x2-7x3≥15 - 6y1'-7y2+3y3'≤-3 S.t. 5x2+3x3=30 y'≤0，y2≥0，y3'无约束 x1≤0，x2无约束，x3≥0 2014-12-15
2014-12-15 9 §2 原问题与对偶问题 0 6 7 3 3 3 2 6 5 5 4 2 6 5 5 4 4 3y 7 . . max 24 15 30 30 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 1 2 3 4 y y y y y y y y y y y y y y y y y st y y y y ， ， ， （2）令上式四个约束条件对应的对偶变量分别为y1，y2，y3，y4，则其 对偶问题为： （3）令y1′= - y1，y3 ′= y3 – y4 ，中间两个约束条件合成等式约束，有 ' 0， 0， '无约束 6 ' 7 3 ' 3 2 ' 6 5 ' 4 4 ' 3y 7 . . max 24 ' 15 30 ' 1 2 3 1 2 3 1 2 3 1 2 1 2 3 y y y y y y y y y y s t y y y 0, , 0 5 3 30 3 6 7 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 st z x x x 无约束
§2原问题与对偶问题 也可直接按教材表22中的对应关系写出非对称形式的对偶问题。 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数max 目标函数min m个 约束条件 m个 ≤ ≥0 銮 ≥ ≤0 = 无约束 n个 n个 塞 ≥0 ≥ ≤0 ≤ 约束条件 无约束 =
2014-12-15 10 §2 原问题与对偶问题 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数 max 目标函数 min 约 束 条 件 m个 m个 变 量 ≤ ≥0 ≥ ≤0 = 无约束 变 量 n个 n个 约 束 条 件 ≥0 ≥ ≤0 ≤ 无约束 = 也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题