单纯形法

目录

第一章 单纯形法的提出??????????????????????? 1.1 单纯形法提出背景??????????????????????? 第二章 单纯形法的一般原理????????????????????? 2.1 单纯形法的基本思路?????????????????????? 2.2 确定初始基本可行解?????????????????????? 2.3 最优性检验?????????????????????????? 2.4 基变换???????????????????????????? 2.5 解的判别定理????????????????????????? 2.6 单纯形法求解线性规划问题的程序框图?????????????? 第三章 表格单纯形法????????????????????????

3.1单纯型表求解????????????????????????? 3.2 用单纯形法求解线性规划问题的举例??????????????? 第四章 人工变量及其处理方法????????????????????

4.1大M法 ???????????????????????????? 4.2两阶段法 ??????????????????????????? 4.3无最优解和无穷多最优解 ???????????????????? 4.4退化与循环 ?????????????????????????? 第五章 单纯形法的矩阵表示????????????????????? 总结 ???????????????????????????????? 参考文献 ??????????????????????????????

1

第一章 单纯形法的提出

1.1 单纯形法的提出背景

单纯形法是1947年由George Bernard Dantzing(1914-2005)创建的，单纯形

法的创建标志着线性规划问题的诞生。线性规划问题是研究在线性约束条件下，求线性函数的极值问题。然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。

线性规划是数学规划的一个重要分支，也是最早形成的一个分支，线性规划的理论与算法均非常成熟，在实际问题和生产生活中的应用非常广泛；线性规划问题的诞生标志着一个新的应用数学分支——数学规划时代的到来。过去的60年中，数学规划已经成为一门成熟的学科。其理论与方法被应用到经济、金融、军事等各个领域。数学规划领域内，其他重要分支的很多问题是在线性规划理论与算法的基础上建立起来的，同时也是利用线性规划的理论来解决和处理的。由此可见，线性规划问题在整个数学规划和应用数学领域中占有重要地位。因此，研究单纯形法的产生与发展对于认识整个数学规划的发展有重大意义。

线性规划问题是在一定约束条件下求目标函数的最优(最大或最小)值。求解线性规划问题有图解法，单纯形法，椭球法及投影尺度法。其中以单纯性法最常用，应用范围也更广泛。

通过对线性规划问题的基本学习，我们已经知道，若LP问题有最优解，必可

在某个极点上达到，即某个基本可行解上取得最优解。因此很容易想到枚举法，即把LP问题所有的最优解都找出来，然后逐个进行比较，找出最优解。这种方法看

mm似可行，但事实上往往行不通，因为可行解的个数≤Cn个，而Cn随着ｍ，ｎ的增

大迅速增大，使枚举法变得不可行。 换一种思路：

先设法找到一个初始基可行解，判断它是否是最优解，如果是则停止计算；否则，则找一个比上一个“更好”的基可行解，而不比上一个“更好”的基可行解不去计算。这种逐步改善的求解方法需要解决以下三个问题： （1）：如何判别当前的基可行解是否达到最优；

（2）：若当前基可行解不是最优解，如何去寻找下一个改进的基可行解； （3）：如何得到一个初始的基可行解。

单纯形法（Simplex Method）解决了上述的三个问题。单纯形法是1947年由 G.B.Dantzig提出，是解 LP 问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。

单纯形法是求解优化设计线性规划问题行之有效的方法，在线性规划问题的求解上得到了广泛的应用。单纯形法是利用单纯形表通过转轴运算最终获得最优解和目标函数的极值，但一般要列数个单纯形表和进行数次转轴运算，且要计算单纯形表中的所有元素，其计算量较大和较繁琐。因此，人们在对单纯形法进行了较深入的研究基础上，推出了修正单纯形法或称改进单纯形法。

2

第二章 单纯形法的一般原理

2.1 单纯形法的基本思路

第一步：构造一个初始基本可行解；

对已经标准化的线性规划模型，设法在约束矩阵Am?n中构造出一个m阶单位阵初始可行基，相应的就有一个初始可行解。 以一个例子来说明单纯形法的基本思路， 例 数学模型为：

maxz?5x1?2x2

?30x1?20x2?160,?5x?x?15,?12? x?4, 1???x1,x2?0.化为标准形式：

maxz?5x1?2x2?0x3?0x4?0x5 (1-1)

?30x1?20x2?x3?160,?5x?x?x?15,?124? x1?x5?4, （1-2）

???x1,x2,x3,x4,x5?0.约束条件(1-2)式的系数矩阵为：

?30 A?(p,p,p,p,p)?512345???1从(1-2)式可看到x3,x4,x5的系数构成的列向量

20100?1010?

?0001??p3?(1,0,0)T,p4?(0,1,0)T,p5?(0,0,1)T

p3,p4,p5是线性无关的，这些向量构成一个基B,对应于B的变量x3,x4,x5为基变量，x1,x2为非基变量。将基变量用非基变量表示，则（1-2）可表示为：

3

?x3?160?30x1?20x2? ? x4?15?5x1?x2 (1-3)

? x?4?x ?5将（1-3）式带入目标函数式（1-1），得到目标函数的非基变量表示式：

若令非基变量x1z?0?5x1?2x2 (1-4)

?x2?0，代入（1-3）式中，即可得到一个基本可行解x(0) ：

(0) x?(0,0,160,15,4)

第二步：判断当前基本可行解是不是最优解；

在目标函数的规范式中，若至少有一个非基变量前的系数为正数，则当前解就

不是最优解；若所有的非基变量前的系数均为非负数，则当前解就是最优解（特指最大化问题）。将目标函数的规范式中非基变量前的系数称为检验数，故对最大化问题，当所有的检验数≤0时，当前解即为最优解。 在例题中得到一个基本可行解x x(0)(0):

?(0,0,160,15,4)

这个基本可行解显然不是最优解，故进行第三步。

第三步：若当前解不是最优解，则要进行行基变换迭代到下一个基本可行解。 首先从当前解的基变量中选一个作为进基变量。选择的原则一般是：目标函数的规范式中，最大检验数所属的非基变量作为进基变量。

再从当前解的基变量中选择一个作为出基变量。选择的方法是：在用非基变量表示的规范式中，处理进基变量外，让其余变量取值为0，在按最小比值准则确定出基变量。这样就得到一组新的基变量与非基变量，即已从上一个基本可行解迭代到下一个基本可行解。然后求出关于新基矩阵的线性规划问题的规范式，在新的规范式中可求出新基本可行解的取值及目标函数的取值。

再回到第二步判断当前新基本可行解是否达到最优。若已到达最优，停止迭代，当前基本可行解即为最优解；若没有达到最优，在进行第三步做新的基变换，再次迭代，如此往复，直到求出最优解或者判断无（有界）最优解停止。

在本例中，第一次迭代，x1作为进基变量，x4为出基变量，得到新的基本可行解为x(1)?(3,0,70,0,1)，其对应的规范式：

?x3?70?14x2?6x4 ?x?3?1/5x?1/5x (1-5)

?124?x?1?1/5x? 1/5x4 ?52 4

z?15?x2?x4 (1-6)

(1)由（1-6）可知，基本可行解x对应的目标函数值为z?15；

而目标函数的非基变量前的系数仍有正的，故此可行解不是最优的，在进行下一次迭代，x2为进基变量，x3为出基变量，得到新的基金本可行解：

x其对应的规范式：

(2)?(2,5,0,0,2)

?x2?5?1/14x3?3/7x4 ??x1?2?1/70x3?2/7x4 (1-7) ?x?2?1/70x? 1/5x4 ?53 z?20?1/14x3?4/7x4 (1-8)

(2)由（1-8）可知，基本可行解x 即得本题最优解为x(2)对应的目标函数值为20;并且目标函数中非基变

量前的系数（检验数）均为负数，故此可行解为最优解。

?(2,5,0,0,2)， 最大值z?20,

2.2 确定初始基本可行解

为了确定初始基可行解，要首先找出初始可行基，其方法如下： (1)直接观察 (2)加松弛变量 (3)加非负的人工变量 一、直接观察 从线性规划问题

nmax z??cixi (1-9) i?1?Px i?1ii的系数构成的列向量

n?b (1-10)

xi?0 i?1,2,3,?,npi(i?1,2,...,n)中，通过观察，可找出一个初始可行基

?1??0B?(P1,P2,?,Pn)?????0? 5

0?0??1?0??????0?1??

二、加松弛变量

对所有约束条件为“≤”形式的不等式，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对

x1及

aij(i?1,2,...,m,j?1,2,...,n)进行编号，则可得下列方程组(x1,x2,...,xm

为松弛变量）：

?x1? a1,m?1xm?1???a1,nxn?b1??x2? a2,m?1xm?1???a2,nxn?b2 ??? ? ? ? ? ? ? ? ?xm? am,m?1xm?1???am,nxn?bm (1-11)

???xj ?0,j?1,2,?,n 于是，（1-11）中含有一个m×m阶单位矩阵，初始可行基B即可取该单位矩阵

?1??0B?(P,P,?,P)?12n????0?将（1-11）中的每个等式移项得

01?0????0??0????1??

?x1?b1?( a1,m?1xm?1???a1,nxn)??x2?b2?( a2,m?1xm?1???a2,nxn) ?? ? ? ? ? ? ? ? ? ?xm ?bm ?( am,m?1xm?1???am,nxn) (1-12)

???xj ?0,j?1,2,?,n 令xm?1???xn?0，由(1-12)式可得

xi?bi (i?1,2,...,m)

又因bi?0，所以得到一个初始基可行解

x?(x1,x2,...,xm,0,...,0)T ?(b1,b2,...,bm,0,...,0) 6

T n?m个0

三、加非负的人工变量

对所有约束条件为“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法:

-即对等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量； -对于不等式约束，再加上一个非负的人工变量

这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。

2.3 最优性检验

根据最优性准则判断当前解是否为最优解：

经过若干次迭代后的当前解，其基变量用非基变量表示的规范式的一般形式为:

'x?b?a? iijxj,i?1,2,3,?,m. (1-14)

j?m?1'in将（1-14）代入目标函数中可得目标函数用非基变量表示的规范式为：

z ? ?cixi ??cjxji?1mj?m?1nmn

??ci(b??axj)??cjxji?1mj?m?1nj?m?1'i'ijn (1-15)

??cb???caxj??cjxj i?1mi?1j?m?1nj?m?1' ??cb??(cj??ciaij)xji?1j?m?1i?1mm'ii'iim'iijnm记z0??cb,z??ca,j?m?1,?,n，

'iij'iiji?1i?1则有 z?z0??(cj?zj)xj (1-16)

j?m?1m'?cj??ciaij?cj?zj

i?1n再记 ?j得

z?z0???jxj. (1-17)

j?m?1n定理1 设（1-14）式及（1-17）式是最大化线性规划问题关于当前解的基本可行解x的两个规范式。若关于非基变量的所有检验数?j前基本可行解x就是最优解。将?j**?0(j?jN)成立，则当

?0(j?jN)称为最大化问题的最有性准则。

7

2.4 基变换

若初始基可行解x解。具体做法是：

从原可行解基中换一个列向量(当然要保证线性无关)，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。 一、换入变量的确定

由(1-18)式可知，当某些?i(0)不是最优解及不能判别无界时，需要找一个新的基可行

?0时，若xi增大，则目标函数值还可以增大。

这时需要将某个非基变量xi换到基变量中去(称为换入变量)。 若有两个以上的?i?0，为了使目标函数值增加得快，从直观上看应选

j?i?0中的较大者，即由max(?j?0)??k 知,应选择xk为换入变量。

二、换出变量的确定 设p1,p2,...,pm是一组线性无关的向量组，它们对应的基可行解是x(0)，将它

?m代入约束方程组(1-10)得到

i?1xi(0)pi?b (1-18)

其他的向量

pm?1,pm?2,...,pm?t,...,pn都可以用p1,p2,...,pm线性表示。若

确定非基变量xm?t为换入变量，必然可以找到一组不全为0的数?i,m?t (i=1,2,?,m)使得

mmPm?t???i,m?tPi 或 Pm?t???i,m?tPi?0 (1-19)

i?1i?1在(1-19)式两边同乘一个正数θ，然后将它加到(1-18)式上，得到

i?1m?xm(0)im???b 或 P??P??P??im?ti,m?ti???i?1(1-20)

i?1?(xi(0)???i,m?t)Pi??Pm?t?b 当θ取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m个）。就应使(xi(0)???i,m?t),i?1,2,?,m.中的某一个为零，并保证其

8

余分量为非负。即取θ为：

??min(ixi(0)?i,m?t|?i,m?t?0) ?xl(0)?l,m?t

这时的xl为换出变量。按最小比值确定θ值，这种方法称为最小比值规则。

将

xl(0)?l,m?tx(1)带入到X中，便可得到新的可行解。新的可行解为：

(0)(0)?(0)xi(0)?xx(0)il????1,m?t,?,0,xm???m,m?t,?,0,,?,0? ?xl????l,m?t?l,m?tl,m?t??由此得到由x(0)转换到x(1)的各分量的转换公式：

?(0)xi(0)??i,m?t i?m?t?xi??l,m?t?lxi??(0) ?xl i?m?t ??l,m?t?这里xi(0)是原基可行解x(0)的分量；xi是新可行解x(1)的各分量;

(1)?i,m?t是换入向量pm?t对应原来一组基向量的坐标。

该新可行解x(1)也是基可行解。下面我们来证明这个新可行解x(1)的m个非零分量对应的列向量是线性无关的。事实上，因为x(0))的第l个分量对应于x(1)的相应分量是零，即xl则（

(0)???l,m?t?0 .其中xl(0),?均不为零，根据最小比值规xl中的m个非零分量对应的个列向量是

?l,m?t?0），

pj(j?1,2,...,m,j?l)和pm?t。 若这组向量不是线性无关，则一定可以找

到不全为零的数?j，使得

Pm?t成立。又因为

9

??ajPj, j?l (1-21)

j?1m Pm?t将(1-22)式减(1-21)式得到

???j,m?tPj (1-21)

j?1m j?1j?l?(?j,m?t?aj)Pj??l,m?tPl?0m

由于上式中至少有?i,m?t?0，所以上式表明p1,p2,...,pm是线性相关的，这

xl中的m个非零分量对应的个列向量是

与假设相矛盾。由此可得，

pj(j?1,2,...,m,j?l)和pm?t是线性无关的，即经过基变换得到的解是基

可行解。此外，由式（1-17）可导出经过基变换得到的新解的目标函数值为：

z1(1)?z0??m?txm?t?z0??m?t??z0

因此，该新基可行解X(1)也是一个改进了的基本可行解。

做题时我们会发现每次选用迭代的可行基矩阵都是单位矩阵，我们不妨设

''''Tpm?(a,a,?,a)?t1,m?t2,m?tm,m?t'则，pm?t?1??0??0???1,m?t???0??1??0???m2,m?t? '??????????i,m?tpi? ?1,m?t ??2,m?t ????n,m?t ?????????????i?1?????????001???????m,m?t?即

'pm?t的表出系数为

所有的

?i,m?t?ai',m?t, i ?1,2,?,m.'pm?t的分量。同时，当可行基为单位矩阵时，当前基本可行解的基变量取值为：

xi(0)?bi' i?1,2,...,m

即当前基变量的取值为约束方程右端项的值。故最小比值准则式子为：

'?xi(0)??bi'?b'l?????min?|??0?min|a?0?i,m?ti,m?t??a'i??i?a'l,m?t?i,m?t??i,m?t?

这不仅简化了计算，而且还提供了以表格形式连续完成用单纯形法求解线性规划问

题各个步骤的可能性。

10

2.5解的判别定理

对于线性规划问题除了有唯一解还有可能出现无穷多最优解、无界解和无可行解等四种情况，因此，需要建立解的判别准则。

(0)'''Tx?(b,b,?,b,0,?,0)定理2 若为对应于基B的一个基可行解，且对12m于一切

j?m?1,...n,,有?j?0，则X(0)为最优解。若对于一切

(0)

j?m?1,...,n，有?j?0,则该线性规划问题有X

为唯一最优解，若有某个

?j?0, j?m?1,...,n，则该线性规划问题有无穷多解，且均为最优解。

(0)'''Tx?(b,b,?,b,0,?,0)定理3 若为一基可行解，有一个?m?k?0，12m并且对i?1,2,...,m,有ai,m?k?0,那么该线性规划问题具有无界解(或称无

最优解)。

证: 构造一个新的解 x(1)，它的分量为

xi(1)?bi'??ai',m?k(??0)(1)xm?k?? xj因ai,m?k'(1)?0;j?m?1,...,n. j?m?k

?0，所以对任意的??0都是可行解，把x(1)代入目标函数内得到

z?z0???m?k

因?m?k?0，故当λ

→+∞，则z→+∞，故该问题目标函数无界。

对于其他的情形：

当要求目标函数极小化时，一种情况是将其化为标准型。如果不化为标准型，只需在上述定理1，2中把?j?0改为?j?0。

11

2.6 单纯形法求解线性规划问题的程序框图 否 用最优性准则检验当前解是否为最优解 σk=max{σj|σj>0} 是 建立初始单纯形表 求B0，x(0),z0 打印x*，z* 选择进基变量xk，进基向量pk ?k?max{?j|? j?0} 停 止 该问题是否为无最优解问 题 是 打印本问题为无最优解 T所有aik?0,(?k?0,pk?(a1k,a2k,?amk)) 否 选择离基变量xl及离基向量 bi'bl''?0?min{'|aik?0}?' aikalk 以aik为主元素，用高斯消元法进行一次迭 '代，过渡到新的可行基B1，求出x（1），z1 12 第三章 表格单纯形法

3.1单纯型表求解

前面我们提到了，若初始可行基及在做基变换时得到的当前可行基，都化成单位矩阵，则可以表格形式用单纯形法来求解线性规划问题。将这种表格称为单纯形表，其功能与增广矩阵类似。

考虑线性规划问题：

maxz?c1x1?c2x2???cnxn?x1?a1,m?1xm?1???a1nxn?b1,?x?a22,m?1xm?1???a2nxn?b2 ????????????????x?amm,m?1xm?1???amnxn?bm?xj?0,j?1,2,...,n.?? 将目标函数改写为

?z?c1x1?c2x2???cnxn?0

为了便于迭代运算，可将上述方程组写成增广矩阵形式

?z x1 x2 ? xm xm?1 ? xn 右端?0?0?????0??110?0c101?0c2???00?1?cma1,m?1a2,m?1?am,m?1cm?1???a1na2n??amncnb1?b2?????bm?0??

采用行初等变换将c1,c2,?,cm变换为零，使其对应的系数矩阵为单位矩阵,

则

?z x1 x2 ? xm xm?1 ? xn b?0?0?????0?1??10?00?01?0??0?1a1,m?1a2,m?1?am,m?1mi?1???a1na2n?amnmi?100?0cm?1??ciai,m?1?cn??ciain 13

??? ???m??cibi???i?1b1b2?bm说明：最后一行为变检验数?j，其中基变量检验数为0，z则该线性规划问题所对应的单纯形表如下表所示 cj c1 ... cm ??cibi

i?1mcm?1 ... cn cB XB c1 c2 x1 x2 b b1 b2 x1 ............... xm xm?1 ...xn ? 10...0 00... a1,m?1 ...a2,m?1 ...a1n ?1 a2n ?2 ... ... ... ... ...... ... cm xm bm 10

am,m?1...amn ?m ?z ?z值 0 ... ?m?1 ... ?n ?bi?bi注：1. ??min?|aij?0??ii?aij?aik2. ?j?cj??ciaij

i?1m3. max??j|?j?0???k

下面我们来介绍利用单纯性表解线性规划问题的步骤如下

(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。 (2) 计算各非基变量xj的检验数，若所有检验数

?j?cj??ciaij?0,j?1,2,...,n

i?1m则已得到最优解，可停止计算。否则转入下一步。 (3)在?j?0,j?m?1,...,n中，若有某个?k对应xk的系数列向量pk?0，

?0)??k，确定xk为换入变量，按?规则计算

则此问题是无界，停止计算。否则，转入下一步。 (4) 根据max(?jbibl??min(|aik?0)?

aikaik5) 以alk为主元素进行迭代，把xk所对应的列向量

14

pk?(a1k,a2k,...,alk,...,amk)T变换为(0,0,...,1,...,0)T

将xB列中的xl换为xk，得到新的单纯形表。重复(2)～(5)，直到终止。

3.2 用单纯形法求解线性规划问题的举例

例2 线性规划问题的标准形式为：

maxz?3x1?5x2?0x3?0x4?0x5?x1?x3?4?2x?x?1224 s.t???3x1?2x2?x5?18??xi?0,(i?1,2,...,5)用单纯形表解决该问题如下所示：

cj cB 0 0 0 0 5 0 -z 0 5 3 -z x3 x2 x1 XB x3 x4 x5 x3 x2 x5 b 4 12 18 4 6 6 -30 2 6 2 -36 3 x1 1 0 3 1 0 [3] 3 0 0 1 0 5 x2 0 [2] 2 0 1 0 0 0 1 0 0 0 x3 1 0 0 1 0 0 0 1 0 0 0 0 x4 0 1 0 0 0.5 -0.5 -2 1/6 0.5 -1/6 -2 0 x5 0 0 1 0 0 1 0 -1/3 0 1/3 -1 θ - 6 9 4 2

由表格可知，检验数行的元素?j前解为最优解，即为x?0均成立，所以由最优解的判别方法可知，当

?(2,6,2,0,0)T，目标函数值z?36.

通过本题，我们可知用单纯形表解决线性规划问题非常简便快捷，而且非常容

易得出最优解，这也是单纯形表在解决现行规划问题中重要性的表现。

15

第四章 人工变量及其处理方法

在用单纯形表解决线性规划问题时，为了使初始可行基成为一个单位矩阵，在有约束条件中需要加入人工变量，但加入人工变量后的数学模型与原模型一般不等价。因此我们需要引入新的方法解决这一问题。 考虑线性规划：

maxZ??cjxj

j?1nn???xjpj?b s.t? （4-1） j?1??xj?0,j?1,2,...,n式中b?0，pj?(a1j,a2j,...,amj)T.则在每一个约束方程左边加上一个人工变量

xn?i(i?1,2,...,m)，可得到：

?a11x1?a12x2???a1nxn?xn?1?b1?ax?ax???ax?x2112222nnn?2?b2? ? （4-2） ????????????????ax?ax???ax?xm22mnnn?m?bm?m11?x1,x2,...,xn,xn?1,...,xn?m?0?(4-2)式含有一个m阶单位矩阵，以xn?1,...,xn?m为基变量，得到一个初始基本可行解：x(0)?(0,...,0,b1,...,bm)T可以从x(0)出发进行迭代。

但是以（4-2）式为约束方程的线性规划模型与原规划问题一般不是等价的 。

只有当最优解中，人工变量都取零值时，才可以认为两个问题的最优解是相当的。 关于这一点有以下结论：

（1） 以（4-2）式为约束方程组的线性规划问题的最优解中人工变量都处在非基

变量位置（即取零值），原问题（4-1）式有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。 （2） 若问题（4-2）式的最优解中包含非零的人工变量，则原问题（4-1）无可行

解。 （3） 若问题（4-2）式的最优解的基变量中包含人工变量，但该人工变量取值为

零，这时刻将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解 对于以上结论这里不作更多的理论上的证明。如何将基变量中的人工变量赶出去，下面我们主要介绍两种方法：大M法和两阶段法。

16

4.1大Ｍ法

将当以（4-2）式作为约束方程组时，若将目标函数修改为

maxZ??cjxj?Mxn?1?Mxn?2?Mxn?m （4-3）

j?1n其中M是个很大的正数，因为是对目标规划实现最大化。因此人工变量必须从基变量中迅速出去，否则目标函数不可能实现最大化。 例 考虑线性规划问题：

maxZ?3x1?x2?x3；

?x1?2x2?x3?11??4x?x?2x?3?123 s.t? (4-4)

??2x1?x3?1??x1,x2,x3?0.用大M法求解步骤如下：

解：添加人工变量将上述问题转化为：

maxZ?3x1?x2?x3?0?x4?0?x5?Mx6?Mx7；

x1?2x2?x3?x?11???4x?x?2x?x?x?3?12356 s.t??2x1?x3?x7?1??xj?0,j?1,2,...,7.?式中M是一个很大的正数,令B(0)?(p4,p6,p7)作初试可行基，作单纯形表如下 cj 3 -1 -1 0 0 -M -M cB 0 -M -M xB x4 x6 x7 b 11 3 1 4M x1 1 -4 -2 x2 -2 1 0 x3 1 2 [1] x4 1 0 0 0 x5 0 -1 0 -M x6 0 1 0 0 x7 0 0 1 0 ? 11 3/2 1 ?z 3-6M M-1 3M-1 17

0 -M -1 0 -1 -1 3 -1 -1 x4 x6 x3 10 1 1 1+M 12 1 1 2 4 1 1 -2 3 0 -2 1 [3] 0 -2 1 1 0 0 0 -2 [1] 0 M-1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 -1 0 -M -2 -1 0 -1 0 1 0 0 2 1 0 1-M 2/3 1 4/3 -1 -2 1 1-3M -5 -2 1 -M-1 -5/3 -2 -7/3 \\ 1 \\ 4 \\ \\ ?z x4 x2 x3 ?z x1 x2 x3 1/3 -2/3 0 -1 2/3 -4/3 ?z -1/3 -1/3 1/3-M -2/3-M 从上表中可以看出人工变量全部出基，且检验数全部小于0，故

x*?(4,1,9,0,0,0,0)T是原问题的最优解，最优值为z*?2

显然，若对于最小化问题，若用大M法，则对最小化目标函数中应加上惩罚项，才能在最小化过程中迫使人工变量xa从基变量中换Mxa（xa为一个人工变量）出去，则有如下一般形式：

maxZ??cjxj?Mxn?1?Mxn?2?Mxn?m

j?1n式中xn?i(i

?1,2,...,m)均为人工变量。

下面我们来介绍处理人工变量的另一种方法：两阶段法

18

4.2两阶段法

当线性规划问题（4-1）式添加人工变量后，得到以（4-2)式为约束方程的线性规划，然后将问题拆成两个线性规划。第一阶段求解第一个线性规划：

minw??xn?i；

i?1m?a11x1?a12x2???a1nxn?xn?1?b1?ax?ax???ax?x2112222nnn?2?b2? s.t??????????????? (4-5)

??ax?ax???ax?xm11m22mnnn?m?bm??x1,x2,...,xn,xn?1,...,xn?m?0?第一个线性规划的目标函数是对所有人工变量之和求最小值。

（1） 若求得的最优解中，所有人工变量都处在费基变量的位置，即

xn?i?0(i?1,2,...m,)及w*?0，则从第一阶段的最优解中去掉人工

变量之后，即为原问题的一个基本可行解。作为原问题的一个初始基本可

行解，再求解原问题，从而进入第二阶段。

（2） 假若求得第一阶段的最优解中，至少有一个人工变量不为零值，则说明添

加人工变量之前的原问题无可行解，不再需要进入第二阶段计算。 因此两阶段法的第一阶段求解，有两个目的：一，判断原问题有无可行解；二，若有可行解，泽尔可求得原问题的一个初始基本可行解，再对原问题进行第二阶段的计算。

下面用两阶段法求解(4-4).建立第一阶段的线性规划问题：

minw?x6?x7；

?x1?2x2?x3?x4?11??4x?x?2x?x?x?3?12356 s.t??2x1?x3?x7?1??xj?0,j?1,2,...,7?式中有B

19

(0)?(p4,p6,p7)?I3，可作为初始基本可行解。建立初始单纯

形表如下所示，并由此开始进行出基入基运算：

0 0 0 0 0 1 1 cj xB x4 x6 x7 cB 0 1 1 0 1 0 0 1 0 b 11 3 1 -4 10 1 1 -1 12 1 1 0 x1 1 -4 -2 6 3 0 -2 0 3 0 -2 0 x2 -2 1 0 -1 -2 [1] 0 -1 0 1 0 0 x3 1 2 [1] -3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 x5 0 -1 0 1 0 -1 0 1 -2 -1 0 0 x6 0 1 0 0 0 1 0 0 2 1 0 1 x7 0 0 1 0 -1 -2 1 3 -5 -2 1 1 ? 11 3/2 1 \\ 1 \\ ?z x4 x6 x3 ?z x4 x2 x3 ?z 通过二次基迭代之后，?j此第一阶段的最优解已得到：x?0，且人工变量x6,x7已从基变量中换出。因

(0)?(0,1,1,12,0,0,0)T为最优解。将最优表中

(0)关于人工变量列划去，即可作为第二阶段的单纯形表。x第二阶段的初始基本可行解。

建立第二阶段的数学模型：

maxz?(0,1,1,12,0)T为

?3x1?x2?x3?0?x4?0?x5；

20

?x1?2x2?x3?x4?11??4x?x?2x?x??3?1235 s.t??2x1?x3?1???xj?0,j?1,2,...,5相应地建立初始单纯形表，这时初始单纯形表中的主体只要将第一阶段中相应的列

换入即可。而目标函数行中数值须重新计算，如下：

cj xB x4 x2 x3 3 -1 -1 0 0 cB 0 -1 -1 3 -1 -1 b 12 1 1 2 4 1 9 -2 x1 [3] 0 -2 1 1 0 0 0 x2 0 1 0 0 0 1 0 0 x3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1/3 0 2/3 -1/3 x5 -2 -1 0 -1 -2/3 -1 -4/3 -1/3 ? 4 \\ \\ ?z x1 x2 x3 ?z 通过一次迭代已得到最优解（?j*T*?0）。最优解x?(4,1,9,0,0)，z?2.

4.3无最优解和无穷多最优解

无最优解与无可行解是两个不同的概念。

无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；

无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优

值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为无限最优解，或无界解。

无最优解判别定理：

在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零

21

的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。

无穷多最优解判别原理：

若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。

4.4 退化与循环

如果在一个基本可行解的基变量中至少有一个分量为零，则称此基本可行解是退化的基本可行解。

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

退化可能出现以下情况：

① 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。

② 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。事实上，已经有人给出了循环的例子.

第五章 单纯形法的矩阵表示

用矩阵描述单纯形法过程的迭代公式，不仅书写简单，而且为修正单纯形法和对偶理论（对偶单纯形法）的介绍提供方便。 线性模型的标准形式为：

maxz?cx

?Ax?b, s.t?

x?0.?假定上述线性规划问题的可行域非空；所有的基本可行解不退化。 若有一个初始可行基B,B为m×m型矩阵，且r(B)?m.即B中含有A中

的m个线性无关的列向量。不失一般性，假定是由A中的前m个列向量组成的，故A有分块矩阵表示形式: A?(B,N)

另外记

x?(xB,xN)T,xB?(x1,x2,...,xm)T,xN?(xm?1,xm?2,...,xn)T

c?(cB,cN)T,cB?(c1,c2,...,cm)T,cN?(cm?1,cm?2,...,cn)T 22

代入上式中可得

?xB?maxz?[cB,cN]??x?N??xB?s.t [B,N]??b? ?xN? xB,xN?0有时也将上式改写成以下形式：

maxz?cBxB?cNxN s.t BxB?NxN?b

xB,xN?0maxz?cBxB?cNxN s.t xB?B?1b?B?1NxN

xB,xN?0 又因为

xB?B-1b-?B-1pjxj.

j?JN所以

z?cBB?1b?(cN?cBB?1N)xN

?cBB?1b??(cj-cBB-1pj)xj.j?JN

因此线性规划问题可表述为如下正则形式：

max z?cBB?1b??(cj-cBB-1pj)xjj?JN?x?B?1b?B?1NxN?B?-1-1s.t ?Bb-Bpjxj??

j?J???xB,xN?0.N

单纯形法中各项准则的矩阵表示为： （1）最优性检验准则

23

非基变量xj的检验数?j 为：?j又令 ?则 ??cj?cBB?1pj,j?JN

?（?m?1,?m?2,?,?n) ,

?cN?cBB?1N ?cN?cBB?1N?0

称σ为检验向量。因此最优性准则用矩阵描述的形式为：

?（2）进基变量选择准则

若?k?maxcj?cBB?1pj,j?JN，则非基变量xk作为进基变量。

j（3）离基变量选择准则

当确定了进基变量为xk后，由式xB?B-1b-?B-1pjxj?B-1b-B-1pkxk

j?JN记B?1b?b',B?1pk?yk,b'及yk均是m维列向量。故由最小比值准则：

?(B?1b)i??1??min??1|(Bpk)i?0??(Bpk)i??(b')i? ?min?|(yk)i?0??(yk)i?(B?1b)lbl' ???1ykl(Bpk)l(B?1b)lbl'令进基变量xk??1，则进基变量为?(Bpk)lykl

pk

,离基变量为p1 ,即第l个基变

量离基，这里的下标l不是变量的自然下标，而是在当前解的基变量中所排序的下标。

下面用矩阵描述单纯形表。 将LP问题写成以下的方程形式：

?0z?BxB?NxN?b,???z?cBxB?cNxN?0, ?x,x?0.?BN表格表示如下：

24

z xB xN 右端项

0 ?1 B cB N cN b 0 将上表中的第二行的（?cBB?1）倍加到第三行上去，再在第二行的等式两端左乘B-1，得到下表

z xB IB xN 右端项

0 ?1 B?1N cN?cBB?1N B?1b ?cBB?1b 0 至此，关于单纯性法的介绍就到这了。事实上，还有改进的单纯形法，限于篇幅，这里不再详细阐述。

总结

通过对单纯形法的认识了解与应用，让我对单纯形法的认识更加深刻，明白了单纯形法在线性规划问题中的重要作用。单纯形法有效地提升了数学规划的应用，很多重大理论诞生之初遭到人们的质疑和反对，但是单纯形法不一样，一诞生就得到人们的青睐，这是因为，单纯形算法的计算简洁明了，计算结果精确有效，它求出的是最优解，超乎很多人的期望和想象力，因此被各个领域频频应用来提高工作效率，节约能量和减少损失，使利润最大化。

参考文献：

[1] 何坚勇 最优化方法 -北京：清华大学出版社，2007.1 [2] 敖特根 单纯形法的产生与发展探析 2011.10 [3] 刘辉 修正单纯形法与单纯形法对比分析 2005.12 [4] 吕林霞 线性规划模型的单纯形法初始可行基选择研究

25

本文来源：https://www.bwwdw.com/article/c0d6.html