王大虎

王大虎:计算检验向量

王大虎

并计算目标函数值

用前面介绍的单纯形法求解,计算得到第一阶段问题(线性规划问题Ⅱ)的单纯形表如表4-18.

表4-18

 

由表4-18知,线性规划问题Ⅱ的所有检验数λN=cBN-cN≤0,且w=0.这时线性规划问题Ⅰ已得一个初始基础可行解线性规划问题Ⅱ的最优值为minw=0.

通过第一阶段的若干次旋转变换,线性规划问题Ⅰ的约束方程组已变换成包含一个单位矩阵的约束方程组,该约束方程组可作为第二阶段初始约束方程组.即由线性规划问题Ⅰ的约束方程组

已变换成包含单位矩阵的第二阶段的约束方程组

第一阶段表4-18的最后一个最优表说明,找到了原问题的一个基础可行解.将它作为初始基础可行解,去求线性规划问题Ⅰ的最优解:将目标函数还原成线性规划问题Ⅰ的目标函数minz′=x1-2×2,可继续利用单纯形表求解(如表4-19).此时,c=(1,-2,0,0,0),可行基基变量为x1,x2,x5,非基变量x3,x4的系数列向量构成的矩阵

计算检验向量计算目标函数值

用前面介绍的单纯形法求解,计算得到线性规划问题Ⅰ的单纯形表如表4-19.

表4-19

由表4-19的最后四行给出的最优单纯形表可得原线性规划问题的最优解x*=(0,3)T,最优目标函数值z=-z′=6.

例4 用两阶段法求解本节例2线性规划问题.

解 第一阶段问题为

minw=x5

 

用单纯形法计算得表4-20.

表4-20

王大虎

从表4-20的最后三行给出的最优单纯形表中,所有检验数λj≤0,得到第一阶段的最优解x*=(2,0,0,0,2)T,最优目标值w=2≠0,且人工变量x5仍在基变量中,从而原问题无可行解.

通过大M法或两阶段法求初始的基础可行解时,如果在大M法的最优单纯形表的基变量中仍含有人工变量(如本节例2),或者两阶段法的第一阶段辅助线性规划在最优单纯形表中目标函数的极小值大于零(如本节例4),那么该线性规划就不存在可行解.

人工变量的值不能取零,说明了原线性规划的数学模型中,约束条件出现了相互矛盾的约束方程.此时线性规划问题的可行域为空集.

三、线性规划问题的进一步讨论

定义当线性规划问题的基础可行解中有一个或多个基变量取零值时,称此基础可行解为退化的基础可行解.

产生的原因 在单纯形法计算中用最小比值原则确定换出变量时,有时存在两个或两个以上相同的最小比值,那么在下次迭代中就会出现一个甚至多个基变量等于零.

王大虎
王大虎

遇到的问题 当某个基变量取值为零,且下次迭代以该基变量作为换出变量时,目标函数并不能因此得到任何改变(由旋转变换性质可知,任何一个换入变量只能仍取零值,其他基变量的取值保持不变).通过基变换前后,两个退化的基础可行解的向量形式完全相同.从几何角度来讲,这两个退化的基础可行解对应于线性规划可行域的同一个顶点.

解决的办法 用最小比值原则计算时,如果存在两个及两个以上相同的最小比值,一般选取下标最大的基变量为换出变量,按此方法进行迭代一定能避免循环现象的产生.

例5 求解线性规划问题

maxz=3×1-80×2+2×3-24×4

王大虎

解 引入松弛变量x5,x6,x7为化标准形

minz′=-3×1+80×2-2×3+24×4

 

用单纯形法计算如表4-21.

表4-21

 

表4-21中的检验数λ1=3>0是正检验数中最大的,所以对应的非基变量x1是进基变量.但在用最小比值原则确定换出变量时,比值相等,这时应选取下标最大的基变量为换出变量,故选下标为6的基变量x6为离基变量,换基迭代如表4-22.

表4-22

王大虎

由表4-22最后四行给出的最优单纯形表中知:原问题的最优解为x*=(1,0,1,0)T,目标函数值maxz=-minz′=5.

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注