线性规划的单纯形解法简介

线性规划的单纯形解法简介

使用单纯形法求解线性规划时，首先要化问题为标准形式 所谓标准形式是指下列形式：

maxz=

∑c

j=1

n

j

xj

⎧n

⎪∑aijxj=bi(i=1, ,m)s⋅t⋅⎨j=1

⎪x≥0(j=1,2, ,n)⎩j

当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为minz=∑cjxj时，可令Z′=-Z，而将其写成为

j=1n

minz'=-∑cjxj

j=1

n

求得最终解时，再求逆变换Z=-Z′即可。

②当s·t·中存在ai1x1+ai2x2+ +ainxn≤bi形式的约束条件时，可引进变量

⎧xn+1=bi-(ai1x1+ai2x2+ +ainxn)

⎨

⎩xn+1≥0

便写原条件成为

⎧ai1x1+ai2x2+ +ainxn+xn+1=bi

⎨

x≥0⎩n+1

其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束，经济上的含义则指明，拥有bi个单位的第i种资源将有多余量xn+1个单位未被充分利用。

同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量

⎧xn+1=(ai1x1+ai2x2+ +ainxn)-bi

⎨

x≥0⎩n+1

使原条件写成

⎧ai1x1+ +ainxn-xn+1=bi

⎨

⎩xn+1≥0

其中的xn+1的经济含义则表明，第i种资源的拥有量bi尚有不足的部分量xn+1个单位。

当然，当xn+1=0时，则bi个单位恰好够用，既不必考虑资源积压浪费也不必增加资源的使用量。仅当xn+1>0时才有前述考虑。因此，松驰变量的取值情况将说明资源的利用情况，是一个值得人们关注的变量。

在将线性规划模型化为标准形后，便可使用单纯形法求解。所谓单纯形法，是指1947年美国数学家乔治·丹捷格发明的一种求解线性规划模型的一般性方法。限于本书范围，这里只介绍解法基本思想和具体操作，不做理论探讨。为方便，不妨就下岗工人老吴的生产计划模型讨论。该模型的标准形式为

maxz=500x1+350x2+o⨯(x3+x4+x5)

⎧2x1+x2+x3=300,

⎪4x+3x+x=600,⎪124

s⋅t⋅⎨

6x+4x+x=810,25⎪1

⎪xj≥0(j=1,2,3,4,5)⎩

首先，该模型是由一个目标函数与一组约束条件的方程组加非负性变量要求形成的。我们的任务是在满足所有约束条件的变量组

，它能使目标函数达到最x (x1,x2, ,xn)T中选取这样一组（或多组）

大。因此，求解可按两步走：第一走，求出所有的变量组X=（x1,x2,„,xn）T。这样的变量组，我们称之为可行解。第二步，所有可行解中选取使目标函数达最大的，称为最优解。

第一步：求解约束条件组 由于此时的约束条件组已是含有五个变量三个方程的方程组，外加xj≥0,；因而只须求解方程组，同时考虑xj≥0即可完成。

先来求解方程组。根据线性代数知识，该方程组将有无穷多组解，这是因为方程组有两个自由变量。我们这里只求使自由变量取值为零的解。比如令x1、x2为自由变量并令其取值为零，则立刻得到一组解。

x(0)=(0,0,300,600,810)T

且它还是可行解，称这样求得的可行解为基本可行解。当然也可以令

x2、x5为自由变量，求得另一组解为

x(1)T=(135,0,30,60,0)T

它自然也是基本可行解。

我们不加证明地指出：线性规划问题若存在最优解，则最优解或最优解之一必可在基本可行解中达到。而基本可行解是通过求解约束方程组时，令所选定的自由变量为零（称为非基本变量），对剩下的变量（称为基本变量）求解所获得的解，并且这个解的所有分量必须均非负。当然，对基本变量形成的方程组须能够求出唯一解，使用线性代数的术语，即该方程组的系数阵与增广矩阵同秩。

显然，这种基本可行解并不唯一（但最多有Cnm个，其中m和n分

别是方程个数和变量个数）。那么，哪一个是最优解呢？

第二步：解的最优性判定

要检验一个解是否最优，只要代之于目标函数中，看其是否使目标函数达最优即可。这里先代入x0=(0,0,300,600,810)T，可知目标值Z（0）=0，但仅此无法判定其最优性。为此，将这个解所对应的约束组写出：

⎧x3=300-2x1-x2

⎪

⎨x4=600-4x1-3x2 （1） ⎪x=810-6x-4x

12⎩5

代入目标函数可得

Z(0)=500x1+350x2+0

可见，非基本变量x1和x2的价值系数均大于零。因此，若令x1和x2改换成基本变量（取值大于零），必可使目标值增加，比如令x2增加一个单位，则目标值便从零变成350。换句话说，目前解x(0)非最优解。不仅如此，令x2增加一个单位，不如令x1增加一个单位，因为此时的目标值增幅更大为500。如果一次只允许一个非基本变量增幅，则应选择其价值系数最大者首先变成基本变量。为此，我们令x1增加一个单位而成为基本变量，x2仍为零，则由约束条件组（1）便可获得新解为

x=(1,0,298,596,804)T

对应的目标值为Z=500。这个解尽管使目标值改进了，但它却不是我们要找的基本可行解。因为基本可行解应至少有两个零分量（自由变量是两个）。也就是说，在我们让x1变成基本变量的同时，应有一个

原基本变量变成非基本变量而取值为零。注意到非负性要求便知应有

⎧300600810⎫810

x1=min⎨,,=135 ⎬=

46⎭6⎩2

于是x5=0，而得新基本可行解为

x(1)=(135,0,30,60,0)T

这个x（1）恰好是前面用解方程组的方法得到的那个解，对应的目标值一下子从零变到了67500。这是个很漂亮的结果。只所以如此，无非以下几个原因导至：（1）我们是在基本可行解中寻求最优解；

（2）在决定哪个变量从非基本变量转化为基本变量（通常称之为进基变量，反之，称为出基变量）时，应按最大化原则进行。即在非基本变量的正价值系数中选取最大者对应的变量进基。 （3）在决定出基变量时，应按最小比值规则进行。即若

⎧b⎫b

xk=min⎨i|aik>0⎬=l

⎩aik⎭alk

则应令xl出基。其中bi是目前解的基变量取值，aik是进基变量xk所在列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik≤0，则对应的xi不会因xk的增加减值而成为出基变量）。

循此基本程序，便可以以最快的速度使线性规划问题得到最优解。这个程序稍加完善便是所谓单纯形解法基本程序。为使学员熟悉这个程序，我们再来检验一下新解x(1)是否最优。

x(1)中基本变量为x1，x3和x4，如同（1）式一样，我们把它们写

成如下形式：

x1=135-

2

x2 3

x3=30+

11

x2+x5 （2） 3312

x4=60-x2+x5

33

这形式是在约束方程组中令x2和x5为自由变量，关于x1,x3和x4求解的结果。它是用非基本变量表达基本变量的最简洁形式，由于基本变量的系数列向量均为单位列向量，故这一步骤通常称作“化单位”。

将（2）式代入原目标函数可得

Z(1)=67500+

50

x2 3

可见，非基本变量x2的系数大于零，因此，令x2进基势必使目标函数增值，即X（1）仍非最优解。

我们注意到，不同解的非基本变量的系数都不相同，它们随着解的改变而改变。但是，非基本变量的系数的符号却可以决定解的最优性：当且仅当所有非基本变量的系数都非正时，目前解为最优解。事实上，若x2的系数为负，则令x2进基目标值不仅不增值反而要减值；若x2的系数为零，则令x2进基与否均不改变目标值。

称这个随解而变动的基本变量xj 的系数为xj 的检验数，记作σ

j

，便有

最优性判定定理：设目前解为X，若∀σj≤0(xj为非基本变量)，

则X为最优解；若∃σl>0(xl为非基本变量)，则X非最优解。

单纯形解法基本程序： （1）将线性规划化为标准形。

（2）用最快的方法确定一个初始基本可行解X（0）。当s·t均为“≤”形式时，以松驰变量做初始基本变量最快。

（3）求X（0）中非基本变量xj的检验数σj。若∀σj≤0，则停止运算，X（0）=X*（表示最优解），否则转下一步。

{σj>0}确定xk进基； （4）①由σk=max

j

②由xk=mini

bib

|aik>0}=l确定xl出基，其中alk称为主元素； aikalk

③利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。

（5）返回（3），直至求得最优解为止。

现利用上述程序重新求解上例。为了方便明了，采用一种称为单纯形表的形式求解。为此，将问题的标准形式进一步表述为：求x1,„,x2和Z,，使满足方程组

=300,⎧2x1+x2+x3

⎪4x+3x+x=600,⎪124

⎨

6x+4x+x=810,25⎪1⎪⎩-500x1-350x2+z=0

且要求诸xj非负，Z的值达最大。然后，将上述方程组写成如下表格形式：

我们把这个表称作初始单纯形表，其特点是，从第三列起将约束

方程组连同目标函数Z一起按各变量位置写出，它把目标函数作为一个特殊的约束，实际上是各变量的检验数所在行。最左边两列则表明了目前解的基本变量及其相应的价值系数，最右边一列则给出了目前解的基本变量取值，右下角的数0给出这一解的目标值=（0，0，0）（300，600，810）T=0

由于σ1=500, σ2=350,均为正数，故目前解非最优，按步骤（三）开始寻找另一个更好的解。令x1进基，然后以b列与x1所在列各正分量作比，求其最小值，得

x1=min{

[1**********]0

,,= 2466

故x5出基而主元素为6。为明确，将主元素加上括号便清楚地看到主元素所在列对应的x1进基，所在行对应的变量x5 出基。

以x1替代x5，并将6化为1（该行各元素除以6），然后利用这个1将同列的其它元素化为0（相当于解方程组中的同解变换：第三行乘-4加到第二行上，乘以-2加到第一行上，乘-500加到第四行上）便可得另一表：

由这一表易见，目前解X（1）=（135，0，30，60，0）T，目标值为67500（元）。由于σ2=

50

>0，故3

X（1）仍非最优解。令x2进基进行第

二次迭代便可得到下表

此时的所有检验数均为非正，故这一表给出的解应为最优解X*=（15，180，90，0，0）T，而目标值由-Z=-70500知Z*=70500（元）。于是吴师付的最优生产方案为：生产A、B两种产品依次为15和180个单位，最大利润为7.05（万元）。

这里还有一个问题：x3=90，x4=x5=0说明了什么问题？按前述松驰变量的经济解释就是：第一种原料尚有90单位未被利用，第二、三种原料已被充分利用。这就是说，当初配置原料时，第一种原料估计量多了，按最佳配置只需210个单位便足够了。

看来，线性规划不仅可提供最优生产方案，还可以有效说明资源利用情况。事实上，线性规划按单纯形法求解后，可向决策人提供很多有用的经济信息。

（2） 优化后分析简介

在最终单纯形表的检验数行中，松驰变量检验数的相反数称为该松驰变量所代表的资源的影子价值。本例中三个松驰变量x3，x4和x5

的检验数依次为0，-50，-50，故三种资源的影子价值依次为0，50和50。

影子价值的经济解释如下：设第i种资源bi的影子价值为-σi>0，那么，增加第i种资源一个单位的使用量，会使目标值增加-σi个单位。如b2若增加一个单位的使用量（从600扩大到601），则目标值从70500增加到70550。这个结果可进行一般性理论证明，亦可令b2=600变为601重新求解而知。如果从优化后分析角度说明，因需要线性规划的对偶理论等繁琐的讨论，限于篇幅不再探讨，但这里给出三个基本分析公式，要探讨其原因，可参看运筹学教材中有关章节。三个公式如下：

-1b*=B*-1b;Pj*=B*-1Pjσ*j=Cj-CBB*Pj

其中带“*”号的部分表示最终表上的数据，B*-1是最终表上基矩阵的逆，其余部分均为初始表上的对应数据。例如本例中

b*=(90，180，15)T，对应初始表数据为b=(300,600,810)T，而

B*-1

⎛112⎫

⎪= 034⎪ 046⎪⎝⎭

-1

-1⎫⎛11

⎪= 03-2⎪ 0-23/2⎪⎝⎭

注意，B*-1恰好位于松驰变量对应的位置。于是可计算而知B*-1b恰好为b*。而当b变为（300，601，801）T时，b*变成了（91，183，13）

T

，对应目标值为70550。同理可试求最终表中其它数据。

由上述三个公式的应用过程可见，当原始数据（初始表中数据）

发生改变时，应用这三个公式便把变化一步反映到最终表上了，即最优解发生改变情况便立即得知了。这样便免去了因数据变化而重新求

解的麻烦，这就是所谓优化后分析方法的基本依据。

值得特别指出的是，原始数据改变是有一定范围限制的。比如b2增加带来好处，便无限制地扩大使用量，这是不可能的。事实上，

当b2增加到一定程度时，人们便会发现由公式算得的b*变成具有负分

量的解了，作为最优解这就是不允许的。当然，若实际问题需要b增加到使b*出现负分量，就是引进一些方法以应对，如使用对偶单纯形法、交替单纯形法等。同样，当 *

j出现大于零情形，最优性也被破坏，

好在，此时可继续使用单纯形计算下去。这里不再赘述。