第七章单纯形法 §7.1单纯形法的基本思想 、引例求解线性规划问题 max s=4x+ 5x 2x1+x2-8 x1+2x2<7 3x2<9 x>0,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 + = −