练习1答案 maxz=5x,+2x x,+x0<2 min f=2v+5y2 S.2x1+3x2≤5 y1+2y25 x1x≥0 s t +3y2≥2 1,y2≥0
16 练习1答案 1 2 1 2 1 2 1 2 min 2 5 2 5 . . 3 2 , 0 f y y y y s t y y y y = + + + 1 2 1 2 1 2 1 2 max 5 2 2 . . 2 3 5 , 0 z x x x x s t x x x x = + + +
定义设原线性规划问题为则称下列线性规划问题 Max Z=c1x1+C2x2+…+Cnx MmW=by1+b2y2+…+bnym a1x1+a12x2+…+a1nxn≤b a1y+a21y2+…+am1ym≥C1 a ≤b2 +an2x2+…+ ax≤b, VI y2+…+amym≥Cn 为其对偶问题,其中y(i=1,2,,m称为 上述对偶问题称为 原问题简记为(P),对偶问题简记为()
17 ( ) = + + + + + + + + + = + + + x j n a x a x a x b a x a x a x b a x a x a x b st Max Z c x c x c x j m m m n n m n n n n n n 0 1,2, , . 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 定义 设原线性规划问题为 则称下列线性规划问题 ( ) = + + + + + + + + + = + + + y i m a y a y a y c a y a y a y c a y a y a y c st Min W b y b y b y i n n m n m n m m m m m m 0 1,2, , . 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 1 1 2 2 为其对偶问题，其中yi (i=1,2,…,m) 称为对偶变量。 上述对偶问题称为对称型对偶问题。 原问题简记为(P)，对偶问题简记为(D)
例3:求线性规划间MaxZ=5x1+6x2 题的对偶规划 3x1-2x2≤7 ≥0 解:由原问题的结构可知为对称型对偶问题 MiW=7y1+92 3y1+4y2>5 st 2y1+y2≥6 1,y2≥0
18 + − = + , 0 4 9 3 2 7 . 5 6 1 2 1 2 1 2 1 2 x x x x x x st 例3：求线性规划问 Max Z x x 题的对偶规划 解：由原问题的结构可知为对称型对偶问题 − + + = + , 0 2 6 3 4 5 . 7 9 1 2 1 2 1 2 1 2 y y y y y y st Min W y y
例4:求线性规划问MxZ=5x1-6x2 题的对偶规划 3x,-2x,≤7 t〈4x,+x,≥9 0 解:由原问题的结构可知不是对称型对偶问题, 可先化为对称型,再求其对偶规划。 Max Z=5x,-6 Min W=7y-9y2 3x1-2x2≤7 3V1-4y,≥ 4 ≥0 y2≥0
19 + − = − , 0 4 9 3 2 7 . 5 6 1 2 1 2 1 2 1 2 x x x x x x st 例4：求线性规划问 Max Z x x 题的对偶规划 解：由原问题的结构可知不是对称型对偶问题， 可先化为对称型，再求其对偶规划。 − − − − = − , 0 2 6 3 4 5 . 7 9 1 2 1 2 1 2 1 2 y y y y y y st Min W y y − − − − = − , 0 4 9 3 2 7 . 5 6 1 2 1 2 1 2 1 2 x x x x x x st Max Z x x
例5:求线性规划问MxZ=5x1+6x2 题的对偶规划 3x,-2x,=7 t4x,+x,≤9 0 解:由原问题的结构可知不是对称型对偶问题, 可先化为对称型,再求其对偶规划。 Z=5x1+6x2 Max Z=5x, +6x 3x1-2x2≤7 3x1-2x2≤7 3x1-2x2≥7 st 3x1+2x2≤-7 4x1+x2≤9 4x1+x2≤9 x12x2≥0
20 + − = = + , 0 4 9 3 2 7 . 5 6 1 2 1 2 1 2 1 2 x x x x x x st 例5：求线性规划问 Max Z x x 题的对偶规划 解：由原问题的结构可知不是对称型对偶问题， 可先化为对称型，再求其对偶规划。 + − − = + , 0 4 9 3 2 7 3 2 7 . 5 6 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st Max Z x x + − + − − = + , 0 4 9 3 2 7 3 2 7 . 5 6 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st Max Z x x