第一章运筹学附录

《第一章运筹学附录》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.6.2单纯形原理的矩阵描述设标准的线性规划问题为minz=CTXs.t.AX=b(1.1)X³0并设A=[a1，a2，…，an]其中aj(j=1，2，…，n)是A矩阵的第j个列向量。B=[aB1，aB2，…，aBm]是A的一个基。这样，矩阵A可以分块记为A=[B，N]，相应地，向量X和C可以记为并设R为非基变量的下标集合。利用以上的记号，(1.1)中的等式约束AX=b可以写成BXB+NXN=b即XB=B-1b-B-1NXN(1.2)这就是在约束条件中，基变量用非基变量表出的形式。对于一个确定的基B，目标函数z可以写成将(1.2)式代入以上目

2、标函数表达式，得到目标函数z用非基变量表出的形式(1.3)(1.2)和(1.3)式表示，非基变量的任何一组确定的值，基变量和目标函数都有一组确定的值与之对应。特别，当XN=0时，相应的解就是对应于基B的基础解。如果B是一个可行基，则有单纯形算法包括以下步骤：1、取得一个初始可行基B、相应的基础可行解以及当前的目标函数值z=CBTXB=CBTB-1b2、在当前的非基变量中，选取一个xk（kÎR），使xk的值由当前的值0开始增加，并要求在xk增加时目标函数严格减少。其余非基变量的值均保持零值不变。如果任何一个非基变量的值由0增加时，目标函数都不能减

3、少，则当前的基已经是最优基。3、当xk的值由0开始增加时，由(1.2)可知，当前各基变量的值也要随之变化。有以下两种情况将会发生：（1）当xk的值增加时，某些基变量的值随之减小，则必定有一个基变量xBr的值在xk的增加过程中首先降为0。这时，这个基变量xBr成为非基变量，而非基变量xk成为一个新的基变量，相应地，xk在矩阵A中相应（不在基B中）的列向量ak将取代基变量xBr在基B中的列向量aBr，从而实现由原来的可行基B到一个新的可行基B’的变换。在这一过程中，称变量xk为进基变量，xBr为离基变量，由可行基B到B’的变换称为基变换。由xk的选

4、取可知，新的基B’对应的目标函数值必定小于原可行基B对应的目标函数值。（2）当xk增加时，由(1.2)确定的所有基变量的值都随之增加，则不会有任何基变量离基，这时xk值的增加没有任何限制。注意到进基变量xk的选取，xk的增加使目标函数减少，在这种情况下，可以判定可行域是无界的，且目标函数无界。4、对于新的可行基，重复步骤2和3，就一定可以获得最优基或确定目标函数无界。下面我们来详细说明如何实现以上步骤。步骤1、获得初始基础可行解的一般化的方法将在下一节中叙述。在这里，我们假定已经获得了一个初始的可行基B，基B对应的基础解为当前的目标函数值为步骤

5、2、确定进基的非基变量xk由(1.1)可知，当前目标函数值用非基变量表出的形式是令则如果对于所有非基变量jÎR，都有检验数zj-cj£0，则任何非基变量xj的值由0开始增加都不会使z减少，因此当前基B已是最优基，相应的基础可行解就是最优解，最优解的目标函数值为zj-cj称为非基变量xj的检验数，检验数是当目标函数用非基变量表出时非基变量的系数。如果有kÎR，使检验数zk-ck>0，则非基变量xk的增加将会使目标函数值减少。为了使目标函数值下降得快一些，一般选取检验数zk-ck满足(1.4)的非基变量xk为进基变量。由于除xk以外的非基变量的值均

6、保持为0不变，这时目标函数可以表示为(1.5)步骤3、确定基变量中离基的变量xBr在(1.2)中，令则(1.2)可以表示为当进基变量xk的值由0增加到某一正值，其余非基变量均保持为0时，上式成为即(1.6)在(1.6)中，有以下几种情形：（1）如果向量Yk中所有的分量yik£0，则xk的增加将不会使任何xBi(i=1，2，...，m)减少，这时xk可无限增加，同时所有的基变量仍保持非负。同时由于xk在目标函数中的系数（即检验数）zk-ck>0，由(1.5)可知当xk增加时目标函数将无限减少，即目标函数无界。（2）如果向量Yk中至少有一个分量yi

7、k>0，则xk由0开始增加将会使相应的基变量xBi的值由当前的值bi开始减少。当xk增加到相应的基变量xBr=0，而其余的基变量xBi³0（i=1，2，...，m，i¹r），这时基变量xBr离基，它在基B中相应的列向量aBr将换出基矩阵，进基变量xk在A矩阵中相应的列向量ak将取代基矩阵B中aBr的位置，得到新的可行基B’=[aB1，aB2，…，aBr-1，ak，aBr+1，…，aBm]新的基B’相应的基变量的值为(1.7)B’相应的非基变量的值为XN=0B’对应的目标函数值为(1.8)步骤4、由新的基B’重新确定非基变量集合R’，并重新计算(

8、1.4)以判定B’是否为最优基。若不是，计算(1.4)~(1.8)以实现进一步的基变换。例1.14用单纯形法求解例1.9的线性规划问题maxz=x1+