2.化标准型 (1)目标函数: 原问题目标函数: min c x→max-crx (2)约束条件 (i)原问题条件:a1x1+a12x2+…+amxn≤b an11+n2x2+…+ a.r+x n+I xn;≥0 xn+:称为松弛变量 n (i)原问题条件:an1x1+a12x2+…+ aux≥b aix+aix2+ .+ainrn-xu+i=b xn+称为剩余变量 ≥0 i)原问题:x:无非负约束,则令 ≥0
2. 化标准型 (1)目标函数： c x T 原问题目标函数: min c x T max − (2)约束条件：ai x ai x ain xn bi (i) 原问题条件： 1 1 + 2 2 ++ + + + + = + + 0 1 1 2 2 n i i i in n n i i x a x a x a x x b xn+i 称为松弛变量。 ai x ai x ai n xn bi (ii) 原问题条件： 1 1 + 2 2 ++ + + + − = + + 0 1 1 2 2 n i i i in n n i i x a x a x a x x b xn+i 称为剩余变量。 原问题： 无非负约束，则令 。 = − , 0 ( ) i i i i i i u v x u v iii x
例1将下述线性规划模型化为标准型。 min 2x-3x+x+3x 4 2x1-x,+3x3+xA≥3 3x1+2x2+2x4=7 st x1+4x2-3x3-x4≤6 x1,x3,x4≥0,x2无约束 解:令x2=u2-V2,则 max-2x1+3u2-3v,-x3 3 3x 2x1-l2+v2+3x3+x4-x5=3 3x1+2l2-2v2+2x4=7 st x1+4 1 2 4v,-3x3-x4+ 6 1’34,15x7,2,V2≥0
例1 将下述线性规划模型化为标准型。 1 2 3 4 min 2x − 3x + x + 3x − + − − + + = − + + 1 3 4 2无约束 1 2 3 4 1 2 4 1 2 3 4 , , 0, 4 3 6 3 2 2 7 2 3 3 . . x x x x x x x x x x x x x x x s t 解：令x2 = u2 − v2 ,则 1 2 2 3 4 max − 2x + 3u − 3v − x − 3x − + − − − + = + − + = − + + + − = , , , , , , 0 4 4 3 6 3 2 2 2 7 2 3 3 . . 1 3 4 5 7 2 2 1 2 2 3 4 7 1 2 2 4 1 2 2 3 4 5 x x x x x u v x u v x x x x u v x x u v x x x s t
图解法 例2求解线性规划maxx=4x1+3x2 x1+2x,≤4 st 2x1+x2≤5 解:(1)画出可行解的范围 (2)利用等值线平移的方法求极值点。2 以z为参数,则方程4x1+3x2=z 表示一族等值平行线。 A B 极大值点为顶点B 1 +2x 2 4 2
三.图解法 例2 求解线性规划 + + = + , 0 2 5 2 4 . . max 4 3 1 2 1 2 1 2 1 2 x x x x x x s t z x x 解：(1)画出可行解的范围。 1 x 2 x o A B C (2) 利用等值线平移的方法求极值点。 表示一族等值平行线。 以z为参数，则方程 x + x = z 4 1 3 2 x1 + 2x2 = 4 2x1 + x2 = 5 极大值点为顶点B
例3将例2中的目标函数改为z=x1+2x2 解:分析同例2。 等值线:x1+2x2=zo B ∴极大值点为线段AB上的 C 任一点。 2r +xy=5
例3 将 例2中的目标函数改为z = x1 + 2x2。 1 x 2 x o A B C x1 + 2x2 = 4 2x1 + x2 = 5 解：分析同例2。 等值线：x1 + 2x2 = z。 任一点。 极大值点为线段AB上的
例4求解线性规划maxz=4x1+3x2 x1+x,≥2 st x≤2 x2≥0 152 解:分析同例2 2 2 2 等值线:4x1+3x2=z ∴不存在最大值。 B x1+x2=2
1 x 2 x o A B C 2 x1 − x2 = 2 x1 + x2 = 解：分析同例2。 等值线：4x1 + 3x2 = z。 例4 求解线性规划 − + = + , 0 2 2 . . max 4 3 1 2 1 2 1 2 1 2 x x x x x x s t z x x 不存在最大值