第七章单纯形法 §7.1单纯形法的基本思想 、引例求解线性规划问题 max s=4x+ 5x 2x1+x2-8 x1+2x20,x20 解为了便于对照先将其图解如下:
第七章 单纯形法 §7.1 单纯形法的基本思想 一、引例 求解线性规划问题 max S = 4x1+ 5x2 2x1+ x2≤8 x1+ 2x2≤7 3x2≤9 x1≥0, x2≥0 解 为了便于对照.先将其图解如下: s t
能2 下面用消去法求解: 引入松驰变量x3=0, Bp 3‰=9 x4≥0x≥0.并令S=一S C 将线性规划问题化为标准形式1 min s=-4xr-5x O123 5、6、为 2x1+x2+x2=8 x1+2x+x4=7 (7.1) S·t 3x2+x5 ≥0(=1,2,3,4,5)
下面用消去法求解: 引入松弛变量x3≥0, x4≥0,x5≥0.并令S´ = – S. 将线性规划问题化为标准形式 min S´ = – 4x1 – 5x2 2x1+ x2+ x3 = 8 x1+ 2x2+ x4 = 7 (7.1) 3x2+ x5 = 9 xj≥0 ( j =1, 2, 3, 4, 5 ) s t
8-2x 将(71)的约束方程组改写为x=7-x-2x2(72) 9-3x 令x1=x2=0.则得(7)的一个可行解X=00.8,79)T 相应的目标函数值S0=-4×0-5×0=0 (1)与图解法比较,可知:X0对应极点O (2)由目标函数S=-4x1-5x2可看出,x1x2若取正值, 目标函数值可减少让x1=0,x2取正,且尽量大,但应保 持其余变量为非负,即
将(7.1)的约束方程组改写为 ( 7.2 ) 令 x1= x2= 0 .则得(7.1)的一个可行解X(0)=(0,0,8,7,9)T 相应的目标函数值 S´ 0= – 4×0 – 5×0=0. (1) 与图解法比较,可知: X(0) 对应极点O. (2) 由目标函数 S´ = – 4x1 – 5x2可看出, x1 ,x2若取正值， 目标函数值可减少. 让 x1=0, x2取正, 且尽量大，但应保 持其余变量为非负,即 = − = − − = − − 5 2 4 1 2 3 1 2 9 3 7 2 8 2 x x x x x x x x
8-x>0 s·tx4=7-2x20 xs=9-3x2>0 取 87919 时,有x、=9-3x,=0 于是,把x2与x的地位互换即应在约束条件中用xx来 表示x2x32x将(71)的约束变形为 5-2x1+-x x1+-x (7.4) 3 3 5
x3 = 8－x2≥0 x4 = 7－2x2≥0 (7.3) x5 = 9－3x2≥0 于是,把x2与x5的地位互换,即应在约束条件中用x1 ,x5来 表示x2 , x3 , x4 . 将(7.1)的约束变形为 (7.4) 9 3 0. 3 9 3 9 , 2 7 , 1 8 2 min 5 = − 2 = = 取x = 时，有x x s t = − = − + = − + 2 5 4 1 5 3 1 5 3 1 3 3 2 1 3 1 5 2 x x x x x x x x
此时目标函数为:S=-15-4x+5x 于是,我们得到(71)的一个等价形式,即 minS′=-15-4x,+-x x x X x 4 x (7.5) 5 ≥0(j=1,2…5) 令x1=0,x5=0,即得(1)的又一可行解X=0,35,10 相应的目标函数值:S1=-15-4×Dx 0=-15
此时目标函数为: 于是, 我们得到(7.1)的一个等价形式,即 (7.5) 令x1=0, x5=0,即得(7.1)的又一可行解X(1)= (0,3,5,1,0)T 相应的目标函数值: 1 5 3 5 S = −15 − 4x + x = + = + − = + − = = − − + 0 ( 1,2, ,5) 3 3 1 1 3 2 5 3 1 2 3 5 min 15 4 2 5 1 4 5 1 3 5 1 5 x j x x x x x x x x S x x j s t 0 15. 3 5 S1 = −15 − 4 0 + = −
(1)与图解法比较可知:XD对应极点A (2)由目标函数S=-15-4x1+x可看出,若x不 取零而取正数,目标函数还可减少 在(74)中,令x5=0,x取正值,并尽可能大,同时使得 3=5-2x1=0 4=1-x1>0 →x1=mmn 时,x4=0 (7.6)
(1) 与图解法比较可知:X(1) 对应极点A (2) 由目标函数 可看出, 若x1不 取零而取正数,目标函数还可减少. 在(7.4)中,令 x5= 0, x1取正值,并尽可能大, 同时使得 x3 = 5－2x1≥0 x4 = 1－x1≥0 x2 = 3 (7.6) 1 5 3 5 S = −15 − 4x + x , , 0. 1 1 1 1 2 5 min 1 4 = = = x 时 x
所以互换x1与x4即用x,x来表示x2x12x2即: x3=3+2x4-x 2 x1=1-x4+x (7.7) 此时目标函数S=-19+4x4-x5
所以互换 x1与x4 , 即用x4 , x5来表示x3 , x1 , x2 .即: x3 = 3 + 2x4 – x5 x1 = 1 – x4 + x5 (7.7) x2 = 3 – x5 此时目标函数 S´ = – 19 + 4x4 – x5 3 1 3 2
于是又得(7.1)的一个等价形式 min S=-19+ 4x4-x 2x,+ (78) ,+x s·t +-x=3 x1≥0(j=1,2,…,5) 令x4=0,x=0.即得又一可行解X2)=(1330.0) 相应的目标函数值为S2=-19+4×0-0=-19
于是又得(7.1) 的一个等价形式: min = – 19 + 4x4 – x5 （7.8） 令x4 = 0, x5 = 0. 即得又一可行解 X(2) = (1,3,3,0,0)T , 相应的目标函数值为 2 = – 19+4×0 – 0 = – 19. S S = + = + − = − + = 0 ( 1,2, ,5) 3 3 1 1 3 2 2 3 2 5 1 4 5 3 4 5 x j x x x x x x x x j s t
(1)与图解法比较可知:Y2)对应于极点B (2)由目标函数S=-19+4x4-X5可知:让x取正, S"还可减少 在()中令x4=0,让x取正并尽量大,同时使得 3-x x1=1+x5 →x=mmn 时有x3=0 x2=3--x
(1) 与图解法比较可知: X(2) 对应于极点 B (2) 由目标函数 S´ = – 19 + 4x4 – x5 可知: 让x5 取正, S´还可减少. 在(7.7)中,令x4 = 0,让 x5取正并尽量大,同 时使 得 0 1 3 3 , 1 3 min 3 1 3 3 2 1 3 3 3 1 5 2 5 1 5 3 5 = = = = − = + = − x x x x x x x x 时有
故互换x与x用x3,x来表示x,x1,x2,即 x=3-x,+2. (7.9) 3 2+-x 此时目标函数S=-22+x3+2x4
故互换x5 与 x3 . 用x3 , x4来表示x5 , x1 , x2 . 即 (7.9) 此时目标函数 S´ = – 22 + x3 + 2x4 = + − = − + = − + 2 3 4 1 3 4 5 3 4 3 2 3 1 2 3 1 3 2 3 3 2 x x x x x x x x x