王大虎:第四节 改进的单纯形方法

2018年4月18日

王大虎

一、改进单纯形法的特点

利用单纯形表求解线性规划时,每一次迭代都需要把整个单纯形表计算一遍,但事实上我们关心以下一些数据.

(1)基础可行解xB=B-1b,其相应的目标函数值z=cBB-1b;

(2)非基变量检验数λN=cBB-1N-cN,及其换入变量xk和换出变量xι.

设max{λj|λj>0}=λk,j为非基变量下标,则由检验数λk确定了换入基变量xk,同时也确定了主元列元素B-1Pk,再由主元列元素B-1Pk,得

i为基变量下标

确定被换出的基变量xι.由此可得到一组新的基变量以及新的可行基B1.

对任一个基础可行解x,只要知道了B-1,上述的关键数据都可以从线性规划问题的初始数据直接计算出来.因此,如何计算基础可行解x对应的可行基B的逆阵B-1,即成为改进单纯形法的关键.

为改进单纯形法,可以导出从可行基B变换到B1时B-1到的变换公式.当初始可行基为单位矩阵E时,变换公式将更具有优越性,因为这样可以避免矩阵求逆的麻烦.

下面推导从B-1到的变换公式,假设当前基

B=(P1,P2,…,Pl-1,,Pl+1,…Pm),

在基变换中用非基变量xk取代基变量xl,可得新基

B1=(P1,P2,…,Pl-1,,Pl+1,…Pm)

前后两个基相比仅相差一列,且

 

其中ei表示第i个元素为1,其他元素均为零的单位列向量,B-1Pk为主元列元素.

 

所以,由可以推出:

王大虎

二、改进单纯形法的步骤

①根据给出的线性规划问题的标准形,确定初始基变量和初始可行基B.求初始可行基B的逆阵B-1,得初始基础可行解

xB=B-1b,xN=0;

②计算单纯形乘子π=cBB-1,得目标函数当前值z=cBB-1b=πb;

③计算非基变量检验数λN=cBB-1N-cN=πN-cN.若λN≤0,则当前解已是最优解,停止计算;否则转下一步;

④根据max{λj|λj>0}=λk,确定非基变量xk为换入变量,计算B-1Pk.若B-1Pk≤0,则问题没有有限最优解;停止计算,否则转下一步;

⑤根据确定基变量xl为换出变量;

⑥用Pk替代Pl得新基B1,由变换公式计算新基的逆矩阵,求出新的基础可行解.其中Elk为变换矩阵,其构造方法是:从一个单位矩阵出发,把换出变量xl在基B中的对应列的单位向量,替换成换入变量xk对应的系数列向量B-1Pk,并作如下变形:主元素a′lk(应在主对角线上)取倒数,其他元素除以主元素a′lk并取相反数.

重复步骤②~⑥,直至求得最优解.

用改进的单纯形法求解线性规划问题的流程图为

 

例1 试用改进单纯形法求解线性规划问题

maxz=3×1+2×2

 

解 化为标准形

minz′=-3×1-2×2

 

其中

①观察法确定x3,x4为基变量,x1,x2为非基变量,

 

②计算单纯形乘子当前目标函数值

③非基变量检验数

王大虎

④选择换入变量

max{λj|λj>0}={3,2}=3,

故x1为换入变量.

计算

⑤确定换出变量

 

确定x4为换出变量,主元素=2.

用P1代替P4得新可行基为基变量,x2,x4为非基变量,

 

重复以上步骤,进入第次二循环:

(2-1)

(2-2)

(2-3)

(2-4)选择x2换入变量,计算

 

(2-5)确定换出变量

王大虎

选择x3换出变量,

(2-6)用P2代替P3得新可行基为新的基变量,x3,x4为新的非基变量,

 

进入第三次循环.

(3-1)

(3-2)

 

(3-3)

这里非基变量对应的检验数全部非正,故当前解x2=x*=(20,20,0,0)T即为最优解,相应的目标函数最优值maxz=-minz′=100.

【练习4】

1.求下面线性规划问题的初始基础可行解.

(1)maxz=3×1+6×2

 

(2)maxz=6×1+4×2

 

2.用本节给出的方法求解下列线性规划问题的最优解.

(1)maxz=5×1+2×2+3×3-x4+x5

 

(2)maxz=2×1+3×2

 

3.用单纯形法求解下列线性规划问题.

(1)maxz=3×1+5×2

 

(2)maxz=2×1-x2+x3

 

(3)minz=x1-x2+x3

 

4.用单纯形法求解下列线性规划问题,并指出解的情况.

(1)maxz=-x1-x2+4×3

 

(2)maxz=6×1+2×2+10×3+8×4

 

(3)minz=-x1-2×2

 

5.用大M法求解下列线性规划问题

(1)minz=40×1+36×2

 

(2)minz=-3×1+x2+x3

(3)maxz=-x1+2×2

 

(4)minz=3×1+2×2+x3

 

6.用两阶段法求解下列线性规划问题

(1)minz=5×1+21×3

 

(2)maxz=x1+5×2+3×3

 

(3)minz=2×1+4×2

王大虎

 

(4)maxz=3×1-x2-x3

 

没有评论

评论已关闭。