第一章 线性规划与单纯形法(5)

XB列中填入基变量，这里是x1,x2,?,xm；

CB列中填入基变量的价值系数，这里是c1,c2,?,cm，它们和基变量相对应； b列中填入约束方程组右端的常数；

最后一行称为检验数行，对应各非基变量xj的检验数，当基矩阵为单位阵时，可以用式(1.13)来计算非基变量检验数?j?cj?CBPj。另外，利用这个公式对基变量也做同样的计算时，发现对于所有基变量结果都是0，因此为了表述的一致性，在基变量的检验数行上都填入0。

表1.4称为单纯形表，每迭代一步构造一个新的单纯形表，每一个单纯形表对应于一个新的基可行解。

例1.9 试列出下面线性规划问题的初始单纯形表。

maxz?2x1?5x2?x1?4?x?3 ?2s.t.??x1?2x2?8??x1?0,x2?0解：首先，将问题标准化得

maxz?2x1?5x2?x1?x2?s..t??x1?2x2??x1,x2,x3,?x3?x4,x5?x4?0x5?4?3 ?8其次，确定初始基，为了简化计算，一般取单位阵为初始基，这里x3,x4,x5所对应的系数矩阵为单位阵，故取定x3,x4,x5为初始基向量，x1,x2为非基变量。

最后，根据表1.4的单纯形表格式，可得到该线性规划问题的初始单纯形表，如表1.5所示。

表1.5 cj? CB 0 0 0 2 5 0 0 0 XB b 4 3 8 x1 1 0 1 2 x2 0 1 2 5 x3 1 0 0 0 x4 0 1 0 0 x5 0 0 1 0 x3 x4 x5 ?j 表1.5中，最后一行的检验数只需计算非基变量x1,x2的检验数?1,?2。基变量所对应的检验数都填入0。由于基变量的价值系数CB都为0，由(1.13)式?i?ci?CBPi，可得基变量x1,x2的检验数?1,?2等于其价值系数c1,c2。

由初始单纯形表1.5可得一个初始基本可行解X(0)?(0,0,4,3,8)T。

- 25 -

2．单纯形法的计算步骤

单纯形法是利用单纯形表求线性规划最优解的方法。其主要步骤如下：

（1）求初始基本可行解 将线性规划问题标准化，建立初始单纯形表，求初始基本可行解。如例1.9所示。

（2）最优检验 若所有检验数?j?0，已求出最优解，终止求解。否则转入步骤3。如表1.5中，初始基本可行解X不是最优解。

（3）换基迭代 这个过程比较复杂，又可分以下三个步骤：

a.确定入基变量 若?k?max{?j|?j?0}，则选xk为入基变量。在表1.5中，大于0的检验数有?1?2,?2?5，按照取大的原则，选x2为入基变量；

b.确定出基变量 求最小比值?l?min{bi/aik|aik?0}，第l行的比值最小，选第l行所对应的基变量为出基变量,称为?法则。其中alk称为主元素。在表1.5中，选x2为入基变量，k?2，按照最小比值原则有??min{3/1,8/2}?3，选x4为出基变量。a22?1为主元素。

c.初等变换 求得另一个更好的基本可行解，用矩阵的初等行变换将主元素alk化为1，同时将其所在列的其它元素（包括检验数行）化为0，更换基变量及其价值系数得到新的单纯形表以及对应的新的基本可行解。转入步骤（2）。表1.6是由表1.5得到的单纯形表。

表1.6 (0)所对应的两个非基变量x1,x2的检验数都大于0，所以X(0)cj? CB 0 5 0 2 5 0 0 0 XB b 4 3 2 x1 1 0 1 2 (1)x2 0 1 0 0 x3 1 0 0 0 x4 0 1 -2 -5 x5 0 0 1 0 x3 x2 x5 ?j 表1.6所对应的基本可行解为X因为?1?2?0，所以不是最优解，?(0,3,4,0,2)T，

仍需求新的基本可行解，确定x1为入基变量，x5为出基变量，a13为主元素，用方框框起来以示区别，进行初等变换得表1.7.

表1.7 cj? CB 0 5 2 2 5 0 0 0 XB b 2 3 2 x1 0 0 1 0 (2)x2 0 1 0 0 x3 1 0 0 0 x4 2 1 -2 -1 x5 -1 0 1 -2 x3 x2 x1 ?j 表1.7所对应的基本可行解为X(2)因为所有检验数非正，所以X为?(2,3,2,0,0)T，

*最优解。最优目标函数值z?2?2?5?3?19。

- 26 -

例1.9所求的线性规划问题和例1.8一致，请大家比较不同求解方法的异同点。 说明：（1）如果单纯形表中的基变量取值皆为正数，称这个基可行解为非退化解。若LP的所有基可形解都是非退化的，则LP经过有限次迭代可达到最优。

（2）如果单纯形表中的基变量取值有的为零时，称这个解为LP的退化解，此时称LP是退化的。理论上认为这种线性规划在迭代过程中可能产生循环，从而得不到最优解。为避免循环，常采用1976年R.G.Bland提出Bland法则。

Bland法则：

a. 单纯形表中有若干个检验数?j?0时，取下标号小的非基变量入基； b. 用?法则选取出基变量时，若比值相同，则选取下标号下的基变量出基。 例1.10 用Bland法则求解下列线性规划问题

minz??2x1?x2?x3?2x4?x5?x3?x5?20?2x1?x?x?2x5?10 ?12??x4?3x5?30?3x1??x1,x2,?,x5?0解：先将线性规划化为标准型，令z???z，得

maxz??2x1?x2?x3?2x4?x5

?x3?x5?20?2x1?x?x?2x5?10 ?12??x4?3x5?30?3x1??x1,x2,?,x5?0注意到约束方程组系数矩阵中x3,x2,x4对应的列向量恰好构成三阶单位方阵，可以作为初始基，由式(1.13)非基变量x1,x5的检验数用分别为

?1?c1?CBp1?2?(1?1?2)?213??7

T?5?c5?CBp5?1?(1?1?2)?123??8

基变量x3,x2,x4检验数都为0，得初始单纯形表如表1.8所示。

表1.8 Tcj? CB 1 -1 -2 2 -1 1 -2 1 XB b 20 10 30 x1 2 1 3 7 (1)x2 0 1 0 0 x3 1 0 0 0 x4 0 0 1 0 x5 1 2 3 8 x3 x2 x4 ?j 表1.8所对应的基本可行解为X?(0,10,20,30,0)T，因为?1?7?0,?5?8?0，

所以不是最优解，仍需求新的基本可行解，根据Bland法则选取x1为入基变量，??min{20/2,10/1,30/3}?10，由Bland法则取定x2为出基变量，换基迭代得表1.9。

(2)(2)T表1.9所对应的基本可行解为X?(10,0,0,0,0)，因为所有检验数非正，所以X*为最优解。最优目标函数值z??20。

- 27 -

表1.9 cj? CB 1 2 -2 2 -1 1 -2 1 XB b 0 10 0 x1 0 1 0 x2 -2 1 -3 x3 1 0 0 x4 0 0 1 x5 -3 2 -3 x3 x1 x4 0 -7 0 0 -6 例1.10中换基迭代中采用了Bland法则来避免循环现象的出现。其实到目前为止在实际问题的线性规划模型中还未曾出现过循环现象。因此在退化现象出现时，实际上可以随意决定哪一个变量作为出基变量，不必考虑理论上有可能出现循环的后果。

例1.11 求解下列线性规划问题：

?j maxz?2x1?4x2??x1?2x2?4?x?2x?10 ?2s..t?1?x1?x2?2??x1,x2?0解：化为标准型后用单纯形法计算，得初始单纯形表如表1.10所示。

表1.10 cj? CB 0 0 0 2 4 0 0 0 XB b 4 10 2 x1 -1 1 1 x2 2 2 -1 x3 1 0 0 x4 0 1 0 x5 0 0 1 x3 x4 x5 2 4 0 0 0 ?j 表1.10中，?1?2,?2?4，max{?1,?2}??2，选定x2为入基变量，由?法则，

??min{4/2,10/2}?2，选定x1为出基变量，a12为主元素。换基迭代得表1.11。

表1.11 cj? CB 4 0 0 2 4 0 0 0 XB b 2 6 4 7/2 3 5/2 x1 -1/2 2 1/2 4 0 1 0 0 (1)x2 1 0 0 0 1 0 0 0 x3 1/2 -1 1/2 -2 1/4 -1/2 3/4 0 x4 0 1 0 0 1/4 1/2 -1/4 -2 x5 0 0 1 0 0 0 1 0 x2 x4 x5 ?j 4 2 0 x2 x1 x5 ?j 经过两次初等变换迭代得基本可行解X- 28 -

?(3,7/2,0,0,5/2)T，所有检验数都小于等

于0，故为最优解。最优目标函数值z?20。其中非基变量x3的检验数?3?0，x3若增加，目标函数值不变，即当x3进基时目标函数值仍为最优值20。以x3为入基变量，继续迭代，如表1.12所示，得到另一个基本可行解X(2)?(14/3,8/3,0,0)T仍为最优解，目标函数值z?20。X(1),X(2)是线性规划问题的两个最优基本可行解，它们连线上的所有点（凸组合）都是问题的最优解，从而原问题有无穷多最优解。

表1.12 **cj? CB 4 2 0 2 4 0 0 0 XB b 8/3 14/3 10/3 x1 0 1 0 0 x2 1 0 0 0 x3 0 0 1 0 x4 1/3 1/3 -1/3 -2 x5 -1/3 2/3 4/3 0 x2 x1 x3 ?j 定理1.5 无穷多最优解判定定理

当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多最优解。

例1.12 求解下列线性规划问题：

maxz??2x1?3x2?4x1?2x2?2 ?s..t?2x1?3x2?4?x,x?0?12解：化为标准型后用单纯形法计算，如表1.13所示

表1.13 cj? CB 0 0 -2 3 0 0 XB b 2 4 x1 4 2 -2 x2 -2 -3 3 x3 1 0 0 x4 0 1 0 x3 x4 ?j ?2?3，x2为入基变量，但a12?0,a22?0，没有符合条件的最小比值，说明当非基

变量x1保持为0时，只要x2?0就能保证x3,x4非负，即x2可以无限增大，此时目标函数值也无限增大且满足约束条件，从而问题具有无界解。用图解法也可看出问题有无界解，

定理1.6 无界解判定定理

在单纯形表中，若某个检验数?k?0且在A中xk的系数均为负，则线性规划问题具有无界解。

3．大M法

前面讨论的线性规划问题，其标准型中系数矩阵中都有单位子阵，作为初始基，很容易就可以得到初始基本可行解。但在实际问题中，有些规划问题的标准型中不含单位子阵，此

- 29 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法(5)在线全文阅读。