首页 理论教育 大学应用数学:单纯形法的基本思想

大学应用数学:单纯形法的基本思想

更新时间:2025-01-17 工作计划 版权反馈
【摘要】:,bm)T,基、基变量与非基变量.矩阵A中任意一个m阶的非奇异子阵B称为线性规划问题(7.2)的一个基,不妨设那么Pj对应的变量xj(j=1,2,…,xn称为非基变量.基本解、基本可行解与可行基.对于基B=(p1,p2,…,pm),在AX=b中,令非基变量全为零,可唯一地确定出一个解X=(x1,x2,…

1.几个基本概念

设有线性规划问题minS=cX

其中c=(c1,c2,…,cn),X=(x1,x2,…,xnT,b=(b1,b2,…,bmT

(1)基、基变量与非基变量.矩阵A中任意一个m阶的非奇异子阵B称为线性规划问题(7.2)的一个基,不妨设

那么Pj对应的变量xj(j=1,2,…,m)称为基变量,而其余的变量xm+1,xm+2,…,xn称为非基变量.

(2)基本解、基本可行解与可行基.对于基B=(p1,p2,…,pm),在AX=b中,令非基变量全为零,可唯一地确定出一个解

X=(x1,x2,…,xm,0,…,0)T

称为线性规划问题(7.2)的一个基本解.

如果基本解X又满足非负限制,即X≥0,则X被称为基本可行解,基本可行解对应的基称为可行基.

2.解法举例

例7.4 求解线性规划问题.

解 首先引进松弛变量x3≥0,x4≥0,x5≥0,将原线性规划问题转化为标准形式:

因为约束方程的系数矩阵为

显然子阵是非奇异的,从而是线性规划问题的一个基.于是变量x3,x4,x5成为对应于此基的基变量,变量x1,x2就是非基变量.

令x1=x2=0,由方程组(7.3)得到问题的一个基本解X(0)=(0.0,8,7,3)T.(www.xing528.com)

由于基本解X(0)满足非负限制条件,所以X(0)是一个基本可行解,相应的基B成为可行基,目标函数值=-2×0-3×0=0.显然这个解不是最优解.

为寻求更优解,考察目标函数=-2x1-3x2,由于非基变量x1,x2的系数都是负数,x1,x2中只要有一个取正值,的值就会减小,又因x2的系数的绝对值比x1的大些,改变x2的值对值的影响较大,所以考虑把非基变量x2换成基变量(称x2为入基变量).但是基变量只能有3个,必须从x3,x4,x5中换走一个作为非基变量(称为离基变量).至于换走哪一个,这需让入基变量x2保证所有的变量满足非负限制.为此,考虑让入基变量x2取正值,x1仍为非基变量取零.将方程组(7.3)等价变形为

显然只有选择,才能使x3≥0,x4≥0,x5≥0同时成立.而当x2=3时,原基变量x5=3-3=0.因此确定x5为离基变量,得新基B1=(p2,p3,p4)和新基变量x2,x3,x4及非基变量x1,x5,此时对方程组(7.3)作初等变换,使新基变量x2,x3,x4的系数全变为1,得方程组的等价变形为:

将式(7.6)代入目标函数=-2x1-3x2中,得目标函数新的表达式为~S1=-9-2x1+3x5,于是得到线性规划问题(7.3)的一个等价形式,即

令x1=x5=0,得一基本可行解X(1)=(0,3,5,1,0)T,相应的目标函数值=-9-2×0+3×0=-9.显然这个解也不是最优解.因为目标函数中x1的系数为负值,如果x1不取零而取正值,则目标函数值还可以减少.于是重复上述方法,将非基变量x1换作入基变量.为找出离基变量,在方程组(7.5)中令非基变量x5=0,得

此时x2=3>0,为保证其他变量非负,令,有.显然只有选择x1=,才能使x3≥0,x4≥0.而当x1=1时,有x4=1-1=0.因此选择x4为离基变量,得新基B2=(p1,p2,p3)和新基变量x1,x2,x3及非基变量x4,x5.将方程组(7.5)作等价变形,化为

将方程组(7.9)代入目标函数=-9-2x1+3x5中,得新目标函数=-11+2x4-x5及原线性规划问题(7.3)的又一等价形式,即

令x4=x5=0,得又一基本可行解X(2)=(1,3,3,0,0)T.

相应的目标函数值=-11+2×0-0=-11.它还不是最优解.因为目标函数值中非基变量x5的系数是负的,所以当x5取正值时,目标函数的值还有减小的可能.于是重复上述方法,将非基变量x5与基变量x3互换,得新基B3=(p1,p2,p5),新基变量x1,x2,x5,非基变量x3,x4及等价的方程组

将其代入目标函数中,得相应的新目标函数及相应的与(7.3)等价的线性规划问题:

令x3=x4=0,又得一基本可行解X(3)(3,2,0,0,1)T,相应的目标函数值由于此时的目标函数,非基变量的系数均为正数,所以当它们之中任一个取正值时,都不能使目标函数S~3的值减少,因此X(3)=(3,2,0,0,1)T就是线性规划(7.12)使目标函数值最小的最优解.与它对应的基B3称为最优基.从而原线性规划问题(7.3)的最优解X=(x1,x2)=(3,2),相应的最优值max S=2×3+3×2=12.

通过此例可以发现,线性规划问题的单纯形法求解,就是不断重复换基,使基本可行解从其可行域的一个顶点转换到另一个顶点,使相应的目标函数值一次比一次更好,从而最终取得最优解.这就是单纯形法的基本思想.

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈