管 理 运 筹 学 1
第五章 单 纯 形 法
§ 1 单纯形法的基本思路和原理
§ 2 单纯形法的表格形式
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法
§ 4 几种特殊情况管 理 运 筹 学 2
§ 1 单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解 。 直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止 。
通过第二章例 1的求解来介绍单纯形法,
目标函数,max 50x1+100x2
约束条件,x1+x2+s1=300，
2x1+x2+s2=400，
x2+s3=250.
xj≥ 0 （ j=1,2）,sj≥ 0 （ j=1,2,3）
管 理 运 筹 学 3
它的系数矩阵,
其中 pj为系数矩阵 A第 j列的向量 。 A的秩为 3,A的秩 m小于此方程组的变量的个数 n,为了找到一个初始基本可行解,先介绍以下几个线性规划的基本概念 。
基,已知 A是约束条件的 m× n系数矩阵,其秩为 m。 若 B是 A中 m× m阶非奇异子矩阵 （ 即可逆矩阵 ）,则称 B是线性规划问题中的一个基 。
基向量,基 B中的一列即称为一个基向量 。 基 B中共有 m个基向量 。
非基向量,在 A中除了基 B之外的一列则称之为基 B的非基向量 。
基变量,与基向量 pi相应的变量 xi叫基变量,基变量有 m个 。
§ 1 单纯形法的基本思路和原理
10010
01012
00111
),,,,( 54321 pppppA
管 理 运 筹 学 4
非基变量,与非基向量 pj相应的变量 xj叫非基变量,非基变量有 n－ m个 。
由线性代数的知识知道,如果我们在约束方程组系数矩阵中找到一个基,令这个基的非基变量为零,再求解这个 m元线性方程组就可得到唯一的解了,这个解我们称之为线性规划的基本解 。
在此例中我们不妨找到了 为 A的一个基,令这个基的非基变量 x１,s2为零 。 这时约束方程就变为基变量的约束方程,
101
001
011
3B
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 5
x2+s1=300，
x2=400，
x2+s3=250.
x1=0,x2=400,s1=－ 100,s2=0,s3=－ 150
由于在这个基本解中 s1=－ 100,s3=－ 150,不满足该线性规划 s1≥ 0，
s3≥ 0的约束条件,显然不是此线性规划的可行解,一个基本解可以是可行解,也可以是非可行解,它们之间的主要区别在于其所有变量的解是否满足非负的条件 。 我们把满足非负条件的一个基本解叫做基本可行解,并把这样的基叫做可行基 。
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 6
一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求 bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，
那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个 bj或等于零。
010
001
100
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 7
在本例题中我们就找到了一个基是单位矩阵 。
在第一次找可行基时,所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成,称之为初始可行基,其相应的基本可行解叫初始基本可行解 。 如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基,我们将构造初始可行基,具体做法在以后详细讲述 。
100
010
001
2B
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 8
二,最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解 。
1,最优性检验的依据 ——检验数 σ j
一般来说目标函数中既包括基变量,又包括非基变量 。 现在我们要求只用非基变量来表示目标函数,这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量,然后用非基变量的表示式代替目标函数中基变量,这样目标函数中只含有非基变量了,或者说目标函数中基变量的系数都为零了 。 此时目标函数中所有变量的系数即为各变量的检验数,把变量 xi的检验数记为 σ i。 显然所有基变量的检验数必为零 。 在本例题中目标函数为 50x1+100x2。 由于初始可行解中 x1,x2为非基变量,所以此目标函数已经用非基变量表示了,不需要再代换出基变量了 。 这样我们可知
σ 1=50,σ 2=100,σ 3=0,σ 4=0,σ 5=0。
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 9
§ 1 单纯形法的基本思路和原理
2.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，
如果所有检验数 ≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式由于所有的 xj的取值范围为大于等于零，当所有的 都小于等于零时，可知 是一个小于等于零的数，要使 z
的值最大，显然 只有为零。我们把这些 xj取为非基变量 (即令这些 xj的值为零 )，所求得的基本可行解就使目标函数值最大为 z0。
**对于求目标函数最小值的情况，只需把 ≤0改为 ≥0
j?
0 jj
jJ
z z x?
j?
jj
jJ
x?
jj
jJ
x?
j? j?
管 理 运 筹 学 10
§ 1 单纯形法的基本思路和原理三,基变换通过检验,我们知道这个初始基本可行解不是最优解 。 下面介绍如何进行基变换找到一个新的可行基,具体的做法是从可行基中换一个列向量,得到一个新的可行基,使得求解得到的新的基本可行解,其目标函数值更优 。
为了换基就要确定换入变量与换出变量 。
1.
从最优解判别定理知道,当某个 σ j＞ 0时,非基变量 xj变为基变量不取零值可以使目标函数值增大,故我们要选基检验数大于 0的非基变量换到基变量中去 （ 称之为入基变量 ） 。 若有两个以上的 σ j＞ 0,则为了使目标函数增加得更大些,一般选其中的 σ j最大者的非基变量为入基变量,在本例题中 σ 2=100是检验数中最大的正数,故选 x2为入基变量 。
管 理 运 筹 学 11
§ 1 单纯形法的基本思路和原理
2.
在确定了 x2为入基变量之后,我们要在原来的 3个基变量 s1,s2,s3中确定一个出基变量,也就是确定哪一个基变量变成非基变量呢？
如果把 s3作为出基变量,则新的基变量为 x2,s1,s2,因为非基变量 x1=s3=0，
x2 +s1=300，
x2+s2=400，
x2=250，
求出基本解,x1=0,x2=250,s1=50,s2=150,s3=0。
条件,是基本可行解,故 s3可以确定为出基变量 。
能否在求出基本解以前来确定出基变量呢？
以下就来看在找出了初始基本可行解和确定了入基变量之后,怎么样的基变量可以确定为出基变量呢？ 或者说出基变量要具有什么条件呢？
管 理 运 筹 学 12
§ 1 单纯形法的基本思路和原理我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值,把其中最小比值所在的约束方程中的原基变量确定为出基变量 。 这样在下一步迭代的矩阵变换中可以确保新得到的 bj值都大于等于零 。
在本例题中约束方程为在第二步中已经知道 x2为入基变量,我们把各约束方程中 x2的为正的系数除对应的常量,得
1 2 1
1 2 2
23
3 0 0,
2 4 0 0,
250.
x x s
x x s
xs
312
1 2 2 2 3 2
3 0 0 4 0 0 2 5 03 0 0,4 0 0,2 5 0,
1 1 1
bbb
a a a
管 理 运 筹 学 13
§ 1 单纯形法的基本思路和原理其中 的值最小，所以可以知道在原基变量中系数向量为的基变量 s3为出基变量，这样可知 x2,s1,s2为基变量,x1,s3为非基变量。
令非基变量为零，得
x2+s1=300,
x2+s2=400,
x2=250.
求解得到新的基本可行解 x1=0,x2=250,s1=50,s2=150.
这时目标函数值为
50x1+100x2=50× 0+100× 250=25000。
显然比初始基本可行解 x1=0,x2=0,s1=300,s3=250时的目标函数值为 0要好得多。
下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。
3
32
b
a3 0,0,1
Te?
管 理 运 筹 学 14
§ 2 单纯形法的表格形式在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的表达式。
可行基为 m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前 m
列是单位矩阵）：
以下用 表示基变量，用表示非基变量。
j?
1 1 2 2
1 1,1 1 1,1
2 2,1 1 2,2
,1 1,
m a x,
,
,
,
0,1,2,,
nn
m m n n
m m n n
m m m m m n n m
j
z c x c x c x
x a x a x b
x a x a x b
x a x a x b
x j n
1,2,,ix i m1,2,,jx j m m n
管 理 运 筹 学 15
§ 2 单纯形法的表格形式把第 i个约束方程移项，就可以用非基变量来表示基变量 xi，
把以上的表达式带入目标函数，就有其中：
,1 1,2 2,
1
,1,2,,
i i i m m i m m i n n
n
i i j j
jm
x b a x a x a x
b a x i m
1 1 2 2
11
00
11
mn
n n i i j j
i j m
nn
j j j j j
j m j m
z c x c x c x c x c x
z c z x z x?
0
1
,;m i i j j j
i
z c b c z?
1
2
1 1 2 2 1 2
1
12
,,,
,,,
j
m
j
j i ij j j m m j m
i
mj
mj
a
a
z c a c a c a c a c c c
a
c c c p
管 理 运 筹 学 16
§ 2 单纯形法的表格形式上面假设 x1,x2,…x m是基变量，即第 i行约束方程的基变量正好是 xi，而经过迭代后，基将发生变化，计算 zj的式子也会发生变化。如果迭代后的第 i行约束方程中的基变量为 xBi，与 xBi相应的目标函数系数为 cBi，系数列向量为 则其中,(cB)是由第 1列第 m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。
单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、
迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，
而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例 1。
max 50x1+100x2+0·s1+0·s2+0·s3.
x1+x2+s1=300
2x1+x2+s2=400
x2+s3=250
x1,x2,s1,s2,s3≥0,把上面的数据填入如下的单纯形表格
1,2,,jp j n
1,,,j B B m j B jz c c p c p
管 理 运 筹 学 17
§ 2 单纯形法的表格形式
按照线性规划模型在表中填入相对应的值，如上表所示；
在上表中有一个 m*m的单位矩阵，对应的基变量为 s1,s2,s3；
在 zj行中填入第 j列与 cB列中对应的元素相乘相加所得的值，如
z2=0*1+0*1+0*1=0，所在 zi行中的第 2位数填入 0；
在 行中填入 cj-zj所得的值，如 ；
z表示把初始基本可行解代入目标函数求得的目标函数值，即 b列 *cB列；
初始基本可行解为 s1=300,s2=400,s3=250,x1=0,x2=0;
由于 250/1最小，因此确定 s3为出基变量；
由于,因此确定 x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是 a32=1，在表中画圈以示区别。
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
Bi/ai250 100 0 0 0
0
s1
s2
s3
0
0
0
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
300
400
250
300/1
400/1
250/1
zj 0 0 0 0 0
50 100 0 0 0
z=0
j j jcz 1 5 0 0 5 0
21 0
管 理 运 筹 学 18
§ 2 单纯形法的表格形式
以下进行第一次迭代，其变量为 x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得 x2的系数向量 p2变换成单位向量，由于主元在 p2的第 3 分量上，所以这个单位向量是也就是主元素变成 1。这样我们又得到的第 1次迭代的单纯表如下所示。
在上表中第 3个基变量 s1已被 x2代替，故基变量列中的第 3个基变量应变为 x2。由于第 0次迭代表中的主元 a32已经为 1，因此第 3行不变。为了使第 1行的 a12为 0，只需把第 3行 *(-1)加到第 1行即可。同样可以求得第 2行。
求得第 1次迭代的基本可行解为 s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.
3 0,0,1 Te?
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
bi/aij50 100 0 0 0
1
s1
s2
x2
0
0
100
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
50
150
250
50/1
150/2
—
zj 0 100 0 0 100
50 0 0 0 -100
25000
管 理 运 筹 学 19
§ 2 单纯形法的表格形式
从上表可以看出，第一次迭代的,因此不是最优解。设 x1
为入基变量，从此值可知 b1/a11=50为最小正数，因此,s1为出基变量，
a11为主元，继续迭代如下表所示。
从上表中可知第二次迭代得到的基本可行解为 x1=50,x2=250,s1=0,s2=50,
s3=0,这时 z=27500。
由于检验数都 <0，因此所求得的基本可行解为最优解,z=27500为最优目标函数值。
实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。
1 50 0
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
bi/aij50 100 0 0 0
2
x1
s2
x2
50
0
100
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
50
50
250
zj 50 100 50 0 50
0 0 -50 0 -50
27500
管 理 运 筹 学 20
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法一、大 M法
以第二章的例 2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。
目标函数：
约束条件：
加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：
12m i n 2 3,f x x
12
1
12
12
3 5 0,
1 2 5,
2 6 0 0,
,0,
xx
x
xx
xx
1 2 1
12
1 2 3
1 2 1 2 3
3 5 0,
1 2 5,
2 6 0 0,
,,,,0,
x x s
xs
x x s
x x s s s
管 理 运 筹 学 21
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法至于目标函数,在标准型中并不一定要求求最大值或最小值,但是为了使单纯形表解法有一个统一的解法,我们把所有求目标函数最小值的问题化成求目标函数最大值的问题 。 具体做法只要把目标函数乘以 （ － 1） 。
要注意到人工变量是与松弛,剩余变量不同的 。 松弛变量,剩余变量它们可以取零值,也可以取正值,而人工变量只能取零值 。 一旦人工变量取正值,那么有人工变量的约束方程和原始的约束方程就不等价了,这样所求得的解就不是原线性规划的解了 。 为了竭尽全力地要求人工变量为零,
我们规定人工变量在目标函数中的系数为－ M,这里 M为任意大的数 。 这样只要人工变量 M＞ 0,所求的目标函数最大值就是一个任意小的数 。 这样为了使目标函数实现最大就必须把人工变量从基变量中换出 。 如果一直到最后,人工变量仍不能从基变量中换出,也就是说人工变量仍不为零,则该问题无可行解 。
管 理 运 筹 学 22
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法目标函数,max z=－ 2x1－ 3x2－ Ma1－ Ma2.
约束条件,x1+x2－ s1+a1=350，
x1－ s2+a2=125，
2x1+x2+s3=600，
x1,x2,s1,s2,s3,a1,a2≥ 0.
像这样,为了构造初始可行基得到初始可行解,把人工变量,强行,
地加到原来的约束方程中去,又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－ M,这个方法叫做 大 M法,
M叫做 罚因子 。
管 理 运 筹 学 23
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法下面我们就用大 M法来求解此题,
迭代次数基变量
cB x1 x2 s1 s2 s3 a1 a2 b 比值
-2 -3 0 0 0 -M -M
0 a1
a2
a3
-M
-M
0
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
350
125
600
350/1
125/1
600/2
zj -2M -M M M 0 -M -M
-2+2M -3+M -M -M 0 0 0
-475M
1 a1
x2
s3
-M
-2
0
0 1 -1 0 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
225
125
350
225
-----
350/2
zj -2 -M M -M+2 0 -M -M-2
0 -3+M -M M-2 0 0 2-2M
-225M-
250
2 a1
x1
s2
-M
-2
0
0 1/2 -1 0 -1/2 1 0
1 1/2 0 0 1/2 0 0
0 1/2 0 1 1/2 0 -1
50
300
175
50/1/2
300/1/2
175/1/2
zj -2 -1/2M-1 M 0 1/2M-1 -M 0
0 1/2M-2 -M 0 - 1/2M+1 0 -M
-50M-
600
j j jcz
j j jcz
j j jcz
管 理 运 筹 学 24
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法从上表中可知检验数都小于零。已求得最优解为：
x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最优值为
f=-z=-(-800)=800。
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 a1 a2 b
比值-2 -3 0 0 0 -M -M
3
x2
x1
s2
-3
-2
0
0 1 -2 0 -1 2 0
1 0 1 0 1 -1 0
0 0 1 1 1 -1 -1
100
250
125
zj -2 -3 4 0 1 -4 0
0 0 -4 0 -1 -M+4 -M
-800
管 理 运 筹 学 25
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。
第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：
目标函数：
约束条件：
12m a x ;z a a
1 2 1 1
1 2 2
1 2 3
1 2 1 2 3 1 2
3 5 0,
1 2 5,
2 6 0 0,
,,,,,,0,
x x s a
x s a
x x s
x x s s s a a
管 理 运 筹 学 26
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法注意,此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。
第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，
把此可行解作为初始可行解进行计算。
管 理 运 筹 学 27
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量
cB x1 x2 s1 s2 s3 a1 a2 b 比值
0 0 0 0 0 -1 -1
0 a1
a2
s3
-1
-1
0
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
350
125
600
350/1
125/1
600/2
zj -2 -1 1 1 0 -1 -1
2 1 -1 -1 0 0 0
-470
1 a1
x1
s3
-1
0
0
0 1 -1 1 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
225
125
350
zj 0 -1 1 -1 0 -1 1
0 1 -1 1 0 0 -2
225
2 x2
x1
s3
0
0
0
0 1 -1 1 0 1 0
1 0 0 -1 0 0 1
0 0 1 1 1 -1 -1
225
125
125
zj 0 0 0 0 0 0 0
0 0 0 0 0 -1 -1
0
管 理 运 筹 学 28
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量
cB x1 x2 s1 s2 s3 b 比值
-2 -3 0 0 0
0 x2
x1
s3
-3
-2
0
0 1 -1 1 0
1 0 0 -1 0
0 0 1 1 1
225
125
125
225/1
125/2
zj -2 -3 3 -1 0
0 0 -3 1 0
-925
1 x2
x1
s2
-3
-2
0
0 1 -2 0 -1
1 0 1 0 1
0 0 1 1 1
100
250
125
zj -2 -3 4 0 1
0 0 -4 0 -1
-800
从表中可知其基本可行解 x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为 z=-(-800)=800。
管 理 运 筹 学 29
§ 4 几种特殊情况
.0,
,40
,30
,150103
3020m a x
21
21
1
21
21
xx
xx
x
xx
xxz
约束条件目标函数一、无可行解例 1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到,1 2 1
1 2 1
12
1 2 3 1
1 2 1 2 3 1
m a x 2 0 3 0
3 1 0 1 5 0,
3 0,
4 0,
,,,,,0,
z x x M a
x x s
xs
x x s a
x x s s s a
目 标 函 数约 束 条 件填入单纯形表计算得：
管 理 运 筹 学 30
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 s3 a1 b 比值
20 30 0 0 0 -M
0
s1
s2
a1
0
0
-M
3 10 1 0 0 0
1 0 0 1 0 0
1 1 0 0 -1 1
150
30
40
150/10
—
40/1
zj
cj-zj
-M -M 0 0 M -M
20+M 30+M 0 0 -M 0
-40M
1
x2
s2
a1
30
0
-M
3/10 1 1/10 0 0 0
1 0 0 1 0 0
7/10 0 -1/10 0 -1 1
15
30
25
15/(3/10)
30/1
25/(7/10)
zj
cj-zj
9-7/10M 30 3+M/10 0 M -M
11+7/10M 0 -3-M/10 0 -M 0
450-25M
2
x2
x1
a1
30
20
-M
0 1 1/10 -3/10 0 0
1 0 0 1 0 0
0 0 -1/10 -7/10 -1 1
6
30
4
zj
cj-zj
20 30 3+M/10 11+7M/10 M -M
0 0 -3-M/10 -11-7M/10 -M 0
780-4M
管 理 运 筹 学 31
§ 4 几种特殊情况从第二次迭代的检验数都小于零来看，可知第 2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为 780-4M。我们把最优解
x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得 x1+x2-0+4=40,即有：
x1+x2=36≤40.
并不满足原来的约束条件 3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。
像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。
二、无界解在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。
例 2、用单纯形表求解下面线性规划问题。
12
12
12
12
m a x
1,
3 2 6,
,0.
z x x
xx
xx
xx
目 标 函 数约 束 条 件管 理 运 筹 学 32
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 b 比值1 1 0 0
0
s1
s2
0
0
1 -1 1 0
-3 2 0 1
1
6
1
—
zj
cj-zj
0 0 0 0
1 1 0 0
0
1
x1
s2
1
0
1 -1 1 0
0 -1 3 1
1
9
zj
cj-zj
1 -1 1 0
0 2 -1 0
1
填入单纯形表计算得：
解：在上述问题的约束条件中加入松驰变量，得标准型如下：
12
1 2 1
1 2 2
1 2 1 2
m a x
1,
3 2 6,
,,,0,
z x x
x x s
x x s
x x s s
目 标 函 数约 束 条 件管 理 运 筹 学 33
§ 4 几种特殊情况
12a
从单纯形表中，从第一次迭代的检验数等于 2，可知所得的基本可行解
x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第 2次迭代，那么就选 x2为入基变量，但是在选择出基变量时遇到了问题,=-1,=-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从 1次迭代的单纯形表中，得到约束方程：
22a
22a
移项可得：
1 2 1
2 1 2
1,
3 9,
x x s
x s s
1 2 1
2 2 1
21
1
2
1
2
12
1,
3 9,
,0,
1,
,
0,
9.
1 2 1,
x x s
s x s
x M s
xM
xM
s
sM
z x x M M M
不 妨 设 可 得 一 组 解,
显 然 这 是 线 性 规 划 的 可 行 解,此 时 目 标 函 数管 理 运 筹 学 34
§ 4 几种特殊情况
ij?
由于 M可以是任意大的正数，可知此目标函数值无界。
上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：
在某次迭代的单纯形表中，如果存在着一个大于零的检验数,并且该列的系数向量的每个元素 aij(i=1,2,…,m) 都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。
三、无穷多最优解例 3、用单纯形法表求解下面的线性规划问题。
12
12
12
2
12
m a x 50 50
300,
2 400,
250,
,0.
z x x
xx
xx
x
xx
目 标 函 数约 束 条 件管 理 运 筹 学 35
§ 4 几种特殊情况解：此题我们用图解法已求了解，现在用单纯形表来求解。
1 2 3
12
1 2 1
1 2 2
23
1 2 1 2 3
,,
m a x 5 0 5 0
3 0 0,
2 4 0 0,
2 5 0,
,,,,0,
s s s
z x x
x x s
x x s
xs
x x s s s
加 入 松 弛 变 量,我 们 得 到 标 准 形,
目 标 函 数约 束 条 件填入单纯形表计算得：
管 理 运 筹 学 36
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 s3 b 比值
50 50 0 0 0
0
s1
s2
s3
0
0
0
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
300
400
250
300/1
400/1
250/1
zj
cj-zj
0 0 0 0 0
50 50 0 0 0
0
1
s1
s2
x2
0
0
50
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
50
150
250
50/1
150/2
—
zj
cj-zj
0 50 0 0 50
50 0 0 0 0
12500
2
x1
s2
x2
50
0
50
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
50
50
250
—
50/1
250/1
zj
cj-zj
50 50 50 0 0
0 0 -50 0 0
15000
管 理 运 筹 学 37
§ 4 几种特殊情况
1 2 4,,
这样我们求得了最优解为 x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为 15000。这个最优解是否是惟一的呢？由于在第 2次迭代的检验数中除了基变量的检验数 等于零外，非基变量 s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第 3次迭代。可求得另一个基本可行解，如下表所示：
迭代次数基变量
CB x1 x2 s1 s2 s3 b
50 50 0 0 0
3
x1
s3
x2
50
0
50
1 0 -1 1 0
0 0 -2 1 1
0 1 2 -1 0
100
50
200
zj
cj-zj
50 50 50 0 0
0 0 -50 0 0
15000
管 理 运 筹 学 38
§ 4 几种特殊情况从检验数可知此基本可行解 x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，
从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量 Z1,Z2表示上述两个最优解即 Z1 =（ 50,250,0,50,0）,Z2
=（ 100,200,0,0,50），则此线段上的任一点，即可表示为 αZ1+（ 1-
α） Z2，其中 0≤α≤1。如图 5-1所示：
100 200 300
100
200
300
250 Z1
Z2
图 5-1
管 理 运 筹 学 39
§ 4 几种特殊情况
s?
在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数为零，为什么我们把这个非基变量 xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？
不妨设出基变量为 xk，则原最优单纯形表可表示如下：
1 1 1
1 1 1,
,
1 1 1,
,
1 1 2 2
1
0
0
1
0
0
00
0,0
ks
ks
s
k k k s
k k k s
k k k s
m m m s
j j j
m
s s s m m s s s i is
i
xx
cc
x c a
x c a
x c a
x c a
x c a
cz
c a c a c a c c c a
从 此 表 可 知 即 有,也 就 是 。
管 理 运 筹 学 40
§ 4 几种特殊情况通过迭代，我们得到了新的单纯形表，其中 xs为基变量了，而 xk为非基变量了。我们可得到下表。
1
11
1
11
1
11
1
1
11
0
11
0
11
1
1
0
0
0
ks
ks
s
ks
km
k i is i is s
i i kk s k s
ks
m
kk
ks
i is k k s s
ik s k s
ss
ks
ks
kk
ks
ms
mm
ks
j k s
j j j k
xx
cc
a
xc
a
z c a c a c
aa
a
xc
a c a c a c
aa
xc
a
c
a
xc
a
a
xc
a
z z c
c z c z
在 此 表 中把
1
11
.
0.
m
s i is
i
k s k k s s k
k s k s
j k j k
ca
z c c a c c
aa
c z c z
,代 入 上 式 得,
即 又 可 得 到,
管 理 运 筹 学 41
§ 4 几种特殊情况又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。
这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。
四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。
例 4.用单纯形表，求解下列线性规划问题。
解：加上松驰变量 s1,s2,s3化为标准形式后，
填入单纯形表计算得：
13
12
13
1 2 3
1 2 3
3
m a x 2
2
2,
2 4,
3,
,,0,
z x x
xx
xx
x x x
x x x
目 标 函 数约 束 条 件管 理 运 筹 学 42
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 x3 s1 s2 s3 b 比值
2 0 3/2 0 0 0
0
s1
s2
s3
0
0
0
1 -1 0 1 0 0
2 0 1 0 1 0
1 1 1 0 0 1
2
4
3
2/1
4/2
3/1
zj
cj-zj
0 0 0 0 0 0
2 0 3/2 0 0 0
0
1
x1
s2
s3
2
0
0
1 -1 0 1 0 0
0 2 1 -2 1 0
0 2 1 -1 0 1
2
0
1
—
0/2
1/2
zj
cj-zj
2 -2 0 0 0 0
0 2 3/2 -2 0 0
4
2
x1
x2
s3
2
0
0
1 0 1/2 0 1/2 0
0 1 1/2 - 1 1/2 0
0 0 0 1 -1 1
2
0
1
2/(1/2)
0/(1/2)
—
zj
cj-zj
2 0 1 0 1 0
0 0 1/2 0 -1 0
4
管 理 运 筹 学 43
§ 4 几种特殊情况在以上的计算中可以看出在 0次迭代中，由于比值 b1/a11=b2/a21=2为最小比值，导致在第 1次迭代中出现了退化，基变量 s2=0。又由于在第 1次迭代出现了退化，基变量 s2=0，又导致第 2次迭代所取得的目标函数值并没有得到改善，仍然与第 1次迭代的一样都等于 4。像这样继续迭代而得不到目标函数的改善，
当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：
管 理 运 筹 学 44
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 x3 s1 s2 s3 b 比值
2 0 3/2 0 0 0
3
x1
x3
s3
2
3/2
0
1 -1 0 1 0 0
0 2 1 - 2 1 0
0 0 0 1 -1 1
2
0
1
2/1
—
1/1
zj
cj-zj
2 1 3/2 -1 3/2 0
0 -1 0 1 -3/2 0
4
4
x1
x3
s1
2
3/2
0
1 -1 0 0 1 -1
0 2 1 0 -1 2
0 0 0 1 -1 1
2
2
1
zj
cj-zj
2 1 3/2 0 1/2 1
0 -1 0 0 -1/2 -1
5
管 理 运 筹 学 45
§ 4 几种特殊情况得到了最优解 x1=1,x2=0,x3=2,s1=1,s2=0,s3=0,其最优值为 5。
但有时候当出现退化时,即使存在最优解,而迭代过程总是重复解的某一部分迭代过程,出现了计算过程的循环,目标函数值总是不变,永远达不到最优解 。
下面一个是由 E.Beale给出的循环的例子。
例 5
目标函数 min f =－ （ 3/4） x4+20x5－ （ 1／ 2） x6+6x7.
约束条件,x1+（ 1／ 4） x4－ 8x5－ x6+9x7=0，
x2+（ 1／ 2） x4－ 12x5－ （ 1／ 2） x6+3x7=0，
x3+x6=1，
x1,x2,x3,x4,x5,x6,x7≥ 0.
管 理 运 筹 学 46
§ 4 几种特殊情况这个例题的确存在最优解，但用一般单纯形表法，经过 6
次迭代后得到的单纯形表与第 0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。
首先我们把松弛变量（剩余变量）、人工变量都用 xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，
人工变量的下标号列在松弛变量（剩余变量）之后，在计算
（ 1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。
（ 2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。
这样就一定能避免出现循环。
第五章 单 纯 形 法
§ 1 单纯形法的基本思路和原理
§ 2 单纯形法的表格形式
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法
§ 4 几种特殊情况管 理 运 筹 学 2
§ 1 单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解 。 直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止 。
通过第二章例 1的求解来介绍单纯形法,
目标函数,max 50x1+100x2
约束条件,x1+x2+s1=300，
2x1+x2+s2=400，
x2+s3=250.
xj≥ 0 （ j=1,2）,sj≥ 0 （ j=1,2,3）
管 理 运 筹 学 3
它的系数矩阵,
其中 pj为系数矩阵 A第 j列的向量 。 A的秩为 3,A的秩 m小于此方程组的变量的个数 n,为了找到一个初始基本可行解,先介绍以下几个线性规划的基本概念 。
基,已知 A是约束条件的 m× n系数矩阵,其秩为 m。 若 B是 A中 m× m阶非奇异子矩阵 （ 即可逆矩阵 ）,则称 B是线性规划问题中的一个基 。
基向量,基 B中的一列即称为一个基向量 。 基 B中共有 m个基向量 。
非基向量,在 A中除了基 B之外的一列则称之为基 B的非基向量 。
基变量,与基向量 pi相应的变量 xi叫基变量,基变量有 m个 。
§ 1 单纯形法的基本思路和原理
10010
01012
00111
),,,,( 54321 pppppA
管 理 运 筹 学 4
非基变量,与非基向量 pj相应的变量 xj叫非基变量,非基变量有 n－ m个 。
由线性代数的知识知道,如果我们在约束方程组系数矩阵中找到一个基,令这个基的非基变量为零,再求解这个 m元线性方程组就可得到唯一的解了,这个解我们称之为线性规划的基本解 。
在此例中我们不妨找到了 为 A的一个基,令这个基的非基变量 x１,s2为零 。 这时约束方程就变为基变量的约束方程,
101
001
011
3B
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 5
x2+s1=300，
x2=400，
x2+s3=250.
x1=0,x2=400,s1=－ 100,s2=0,s3=－ 150
由于在这个基本解中 s1=－ 100,s3=－ 150,不满足该线性规划 s1≥ 0，
s3≥ 0的约束条件,显然不是此线性规划的可行解,一个基本解可以是可行解,也可以是非可行解,它们之间的主要区别在于其所有变量的解是否满足非负的条件 。 我们把满足非负条件的一个基本解叫做基本可行解,并把这样的基叫做可行基 。
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 6
一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求 bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，
那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个 bj或等于零。
010
001
100
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 7
在本例题中我们就找到了一个基是单位矩阵 。
在第一次找可行基时,所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成,称之为初始可行基,其相应的基本可行解叫初始基本可行解 。 如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基,我们将构造初始可行基,具体做法在以后详细讲述 。
100
010
001
2B
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 8
二,最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解 。
1,最优性检验的依据 ——检验数 σ j
一般来说目标函数中既包括基变量,又包括非基变量 。 现在我们要求只用非基变量来表示目标函数,这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量,然后用非基变量的表示式代替目标函数中基变量,这样目标函数中只含有非基变量了,或者说目标函数中基变量的系数都为零了 。 此时目标函数中所有变量的系数即为各变量的检验数,把变量 xi的检验数记为 σ i。 显然所有基变量的检验数必为零 。 在本例题中目标函数为 50x1+100x2。 由于初始可行解中 x1,x2为非基变量,所以此目标函数已经用非基变量表示了,不需要再代换出基变量了 。 这样我们可知
σ 1=50,σ 2=100,σ 3=0,σ 4=0,σ 5=0。
§ 1 单纯形法的基本思路和原理管 理 运 筹 学 9
§ 1 单纯形法的基本思路和原理
2.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，
如果所有检验数 ≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式由于所有的 xj的取值范围为大于等于零，当所有的 都小于等于零时，可知 是一个小于等于零的数，要使 z
的值最大，显然 只有为零。我们把这些 xj取为非基变量 (即令这些 xj的值为零 )，所求得的基本可行解就使目标函数值最大为 z0。
**对于求目标函数最小值的情况，只需把 ≤0改为 ≥0
j?
0 jj
jJ
z z x?
j?
jj
jJ
x?
jj
jJ
x?
j? j?
管 理 运 筹 学 10
§ 1 单纯形法的基本思路和原理三,基变换通过检验,我们知道这个初始基本可行解不是最优解 。 下面介绍如何进行基变换找到一个新的可行基,具体的做法是从可行基中换一个列向量,得到一个新的可行基,使得求解得到的新的基本可行解,其目标函数值更优 。
为了换基就要确定换入变量与换出变量 。
1.
从最优解判别定理知道,当某个 σ j＞ 0时,非基变量 xj变为基变量不取零值可以使目标函数值增大,故我们要选基检验数大于 0的非基变量换到基变量中去 （ 称之为入基变量 ） 。 若有两个以上的 σ j＞ 0,则为了使目标函数增加得更大些,一般选其中的 σ j最大者的非基变量为入基变量,在本例题中 σ 2=100是检验数中最大的正数,故选 x2为入基变量 。
管 理 运 筹 学 11
§ 1 单纯形法的基本思路和原理
2.
在确定了 x2为入基变量之后,我们要在原来的 3个基变量 s1,s2,s3中确定一个出基变量,也就是确定哪一个基变量变成非基变量呢？
如果把 s3作为出基变量,则新的基变量为 x2,s1,s2,因为非基变量 x1=s3=0，
x2 +s1=300，
x2+s2=400，
x2=250，
求出基本解,x1=0,x2=250,s1=50,s2=150,s3=0。
条件,是基本可行解,故 s3可以确定为出基变量 。
能否在求出基本解以前来确定出基变量呢？
以下就来看在找出了初始基本可行解和确定了入基变量之后,怎么样的基变量可以确定为出基变量呢？ 或者说出基变量要具有什么条件呢？
管 理 运 筹 学 12
§ 1 单纯形法的基本思路和原理我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值,把其中最小比值所在的约束方程中的原基变量确定为出基变量 。 这样在下一步迭代的矩阵变换中可以确保新得到的 bj值都大于等于零 。
在本例题中约束方程为在第二步中已经知道 x2为入基变量,我们把各约束方程中 x2的为正的系数除对应的常量,得
1 2 1
1 2 2
23
3 0 0,
2 4 0 0,
250.
x x s
x x s
xs
312
1 2 2 2 3 2
3 0 0 4 0 0 2 5 03 0 0,4 0 0,2 5 0,
1 1 1
bbb
a a a
管 理 运 筹 学 13
§ 1 单纯形法的基本思路和原理其中 的值最小，所以可以知道在原基变量中系数向量为的基变量 s3为出基变量，这样可知 x2,s1,s2为基变量,x1,s3为非基变量。
令非基变量为零，得
x2+s1=300,
x2+s2=400,
x2=250.
求解得到新的基本可行解 x1=0,x2=250,s1=50,s2=150.
这时目标函数值为
50x1+100x2=50× 0+100× 250=25000。
显然比初始基本可行解 x1=0,x2=0,s1=300,s3=250时的目标函数值为 0要好得多。
下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。
3
32
b
a3 0,0,1
Te?
管 理 运 筹 学 14
§ 2 单纯形法的表格形式在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的表达式。
可行基为 m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前 m
列是单位矩阵）：
以下用 表示基变量，用表示非基变量。
j?
1 1 2 2
1 1,1 1 1,1
2 2,1 1 2,2
,1 1,
m a x,
,
,
,
0,1,2,,
nn
m m n n
m m n n
m m m m m n n m
j
z c x c x c x
x a x a x b
x a x a x b
x a x a x b
x j n
1,2,,ix i m1,2,,jx j m m n
管 理 运 筹 学 15
§ 2 单纯形法的表格形式把第 i个约束方程移项，就可以用非基变量来表示基变量 xi，
把以上的表达式带入目标函数，就有其中：
,1 1,2 2,
1
,1,2,,
i i i m m i m m i n n
n
i i j j
jm
x b a x a x a x
b a x i m
1 1 2 2
11
00
11
mn
n n i i j j
i j m
nn
j j j j j
j m j m
z c x c x c x c x c x
z c z x z x?
0
1
,;m i i j j j
i
z c b c z?
1
2
1 1 2 2 1 2
1
12
,,,
,,,
j
m
j
j i ij j j m m j m
i
mj
mj
a
a
z c a c a c a c a c c c
a
c c c p
管 理 运 筹 学 16
§ 2 单纯形法的表格形式上面假设 x1,x2,…x m是基变量，即第 i行约束方程的基变量正好是 xi，而经过迭代后，基将发生变化，计算 zj的式子也会发生变化。如果迭代后的第 i行约束方程中的基变量为 xBi，与 xBi相应的目标函数系数为 cBi，系数列向量为 则其中,(cB)是由第 1列第 m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。
单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、
迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，
而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例 1。
max 50x1+100x2+0·s1+0·s2+0·s3.
x1+x2+s1=300
2x1+x2+s2=400
x2+s3=250
x1,x2,s1,s2,s3≥0,把上面的数据填入如下的单纯形表格
1,2,,jp j n
1,,,j B B m j B jz c c p c p
管 理 运 筹 学 17
§ 2 单纯形法的表格形式
按照线性规划模型在表中填入相对应的值，如上表所示；
在上表中有一个 m*m的单位矩阵，对应的基变量为 s1,s2,s3；
在 zj行中填入第 j列与 cB列中对应的元素相乘相加所得的值，如
z2=0*1+0*1+0*1=0，所在 zi行中的第 2位数填入 0；
在 行中填入 cj-zj所得的值，如 ；
z表示把初始基本可行解代入目标函数求得的目标函数值，即 b列 *cB列；
初始基本可行解为 s1=300,s2=400,s3=250,x1=0,x2=0;
由于 250/1最小，因此确定 s3为出基变量；
由于,因此确定 x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是 a32=1，在表中画圈以示区别。
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
Bi/ai250 100 0 0 0
0
s1
s2
s3
0
0
0
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
300
400
250
300/1
400/1
250/1
zj 0 0 0 0 0
50 100 0 0 0
z=0
j j jcz 1 5 0 0 5 0
21 0
管 理 运 筹 学 18
§ 2 单纯形法的表格形式
以下进行第一次迭代，其变量为 x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得 x2的系数向量 p2变换成单位向量，由于主元在 p2的第 3 分量上，所以这个单位向量是也就是主元素变成 1。这样我们又得到的第 1次迭代的单纯表如下所示。
在上表中第 3个基变量 s1已被 x2代替，故基变量列中的第 3个基变量应变为 x2。由于第 0次迭代表中的主元 a32已经为 1，因此第 3行不变。为了使第 1行的 a12为 0，只需把第 3行 *(-1)加到第 1行即可。同样可以求得第 2行。
求得第 1次迭代的基本可行解为 s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.
3 0,0,1 Te?
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
bi/aij50 100 0 0 0
1
s1
s2
x2
0
0
100
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
50
150
250
50/1
150/2
—
zj 0 100 0 0 100
50 0 0 0 -100
25000
管 理 运 筹 学 19
§ 2 单纯形法的表格形式
从上表可以看出，第一次迭代的,因此不是最优解。设 x1
为入基变量，从此值可知 b1/a11=50为最小正数，因此,s1为出基变量，
a11为主元，继续迭代如下表所示。
从上表中可知第二次迭代得到的基本可行解为 x1=50,x2=250,s1=0,s2=50,
s3=0,这时 z=27500。
由于检验数都 <0，因此所求得的基本可行解为最优解,z=27500为最优目标函数值。
实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。
1 50 0
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 b 比值
bi/aij50 100 0 0 0
2
x1
s2
x2
50
0
100
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
50
50
250
zj 50 100 50 0 50
0 0 -50 0 -50
27500
管 理 运 筹 学 20
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法一、大 M法
以第二章的例 2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。
目标函数：
约束条件：
加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：
12m i n 2 3,f x x
12
1
12
12
3 5 0,
1 2 5,
2 6 0 0,
,0,
xx
x
xx
xx
1 2 1
12
1 2 3
1 2 1 2 3
3 5 0,
1 2 5,
2 6 0 0,
,,,,0,
x x s
xs
x x s
x x s s s
管 理 运 筹 学 21
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法至于目标函数,在标准型中并不一定要求求最大值或最小值,但是为了使单纯形表解法有一个统一的解法,我们把所有求目标函数最小值的问题化成求目标函数最大值的问题 。 具体做法只要把目标函数乘以 （ － 1） 。
要注意到人工变量是与松弛,剩余变量不同的 。 松弛变量,剩余变量它们可以取零值,也可以取正值,而人工变量只能取零值 。 一旦人工变量取正值,那么有人工变量的约束方程和原始的约束方程就不等价了,这样所求得的解就不是原线性规划的解了 。 为了竭尽全力地要求人工变量为零,
我们规定人工变量在目标函数中的系数为－ M,这里 M为任意大的数 。 这样只要人工变量 M＞ 0,所求的目标函数最大值就是一个任意小的数 。 这样为了使目标函数实现最大就必须把人工变量从基变量中换出 。 如果一直到最后,人工变量仍不能从基变量中换出,也就是说人工变量仍不为零,则该问题无可行解 。
管 理 运 筹 学 22
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法目标函数,max z=－ 2x1－ 3x2－ Ma1－ Ma2.
约束条件,x1+x2－ s1+a1=350，
x1－ s2+a2=125，
2x1+x2+s3=600，
x1,x2,s1,s2,s3,a1,a2≥ 0.
像这样,为了构造初始可行基得到初始可行解,把人工变量,强行,
地加到原来的约束方程中去,又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－ M,这个方法叫做 大 M法,
M叫做 罚因子 。
管 理 运 筹 学 23
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法下面我们就用大 M法来求解此题,
迭代次数基变量
cB x1 x2 s1 s2 s3 a1 a2 b 比值
-2 -3 0 0 0 -M -M
0 a1
a2
a3
-M
-M
0
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
350
125
600
350/1
125/1
600/2
zj -2M -M M M 0 -M -M
-2+2M -3+M -M -M 0 0 0
-475M
1 a1
x2
s3
-M
-2
0
0 1 -1 0 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
225
125
350
225
-----
350/2
zj -2 -M M -M+2 0 -M -M-2
0 -3+M -M M-2 0 0 2-2M
-225M-
250
2 a1
x1
s2
-M
-2
0
0 1/2 -1 0 -1/2 1 0
1 1/2 0 0 1/2 0 0
0 1/2 0 1 1/2 0 -1
50
300
175
50/1/2
300/1/2
175/1/2
zj -2 -1/2M-1 M 0 1/2M-1 -M 0
0 1/2M-2 -M 0 - 1/2M+1 0 -M
-50M-
600
j j jcz
j j jcz
j j jcz
管 理 运 筹 学 24
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法从上表中可知检验数都小于零。已求得最优解为：
x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最优值为
f=-z=-(-800)=800。
j j jcz
迭代次数基变量 cB
x1 x2 s1 s2 s3 a1 a2 b
比值-2 -3 0 0 0 -M -M
3
x2
x1
s2
-3
-2
0
0 1 -2 0 -1 2 0
1 0 1 0 1 -1 0
0 0 1 1 1 -1 -1
100
250
125
zj -2 -3 4 0 1 -4 0
0 0 -4 0 -1 -M+4 -M
-800
管 理 运 筹 学 25
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。
第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：
目标函数：
约束条件：
12m a x ;z a a
1 2 1 1
1 2 2
1 2 3
1 2 1 2 3 1 2
3 5 0,
1 2 5,
2 6 0 0,
,,,,,,0,
x x s a
x s a
x x s
x x s s s a a
管 理 运 筹 学 26
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法注意,此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。
第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，
把此可行解作为初始可行解进行计算。
管 理 运 筹 学 27
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量
cB x1 x2 s1 s2 s3 a1 a2 b 比值
0 0 0 0 0 -1 -1
0 a1
a2
s3
-1
-1
0
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
350
125
600
350/1
125/1
600/2
zj -2 -1 1 1 0 -1 -1
2 1 -1 -1 0 0 0
-470
1 a1
x1
s3
-1
0
0
0 1 -1 1 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
225
125
350
zj 0 -1 1 -1 0 -1 1
0 1 -1 1 0 0 -2
225
2 x2
x1
s3
0
0
0
0 1 -1 1 0 1 0
1 0 0 -1 0 0 1
0 0 1 1 1 -1 -1
225
125
125
zj 0 0 0 0 0 0 0
0 0 0 0 0 -1 -1
0
管 理 运 筹 学 28
§ 3 求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量
cB x1 x2 s1 s2 s3 b 比值
-2 -3 0 0 0
0 x2
x1
s3
-3
-2
0
0 1 -1 1 0
1 0 0 -1 0
0 0 1 1 1
225
125
125
225/1
125/2
zj -2 -3 3 -1 0
0 0 -3 1 0
-925
1 x2
x1
s2
-3
-2
0
0 1 -2 0 -1
1 0 1 0 1
0 0 1 1 1
100
250
125
zj -2 -3 4 0 1
0 0 -4 0 -1
-800
从表中可知其基本可行解 x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为 z=-(-800)=800。
管 理 运 筹 学 29
§ 4 几种特殊情况
.0,
,40
,30
,150103
3020m a x
21
21
1
21
21
xx
xx
x
xx
xxz
约束条件目标函数一、无可行解例 1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到,1 2 1
1 2 1
12
1 2 3 1
1 2 1 2 3 1
m a x 2 0 3 0
3 1 0 1 5 0,
3 0,
4 0,
,,,,,0,
z x x M a
x x s
xs
x x s a
x x s s s a
目 标 函 数约 束 条 件填入单纯形表计算得：
管 理 运 筹 学 30
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 s3 a1 b 比值
20 30 0 0 0 -M
0
s1
s2
a1
0
0
-M
3 10 1 0 0 0
1 0 0 1 0 0
1 1 0 0 -1 1
150
30
40
150/10
—
40/1
zj
cj-zj
-M -M 0 0 M -M
20+M 30+M 0 0 -M 0
-40M
1
x2
s2
a1
30
0
-M
3/10 1 1/10 0 0 0
1 0 0 1 0 0
7/10 0 -1/10 0 -1 1
15
30
25
15/(3/10)
30/1
25/(7/10)
zj
cj-zj
9-7/10M 30 3+M/10 0 M -M
11+7/10M 0 -3-M/10 0 -M 0
450-25M
2
x2
x1
a1
30
20
-M
0 1 1/10 -3/10 0 0
1 0 0 1 0 0
0 0 -1/10 -7/10 -1 1
6
30
4
zj
cj-zj
20 30 3+M/10 11+7M/10 M -M
0 0 -3-M/10 -11-7M/10 -M 0
780-4M
管 理 运 筹 学 31
§ 4 几种特殊情况从第二次迭代的检验数都小于零来看，可知第 2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为 780-4M。我们把最优解
x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得 x1+x2-0+4=40,即有：
x1+x2=36≤40.
并不满足原来的约束条件 3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。
像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。
二、无界解在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。
例 2、用单纯形表求解下面线性规划问题。
12
12
12
12
m a x
1,
3 2 6,
,0.
z x x
xx
xx
xx
目 标 函 数约 束 条 件管 理 运 筹 学 32
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 b 比值1 1 0 0
0
s1
s2
0
0
1 -1 1 0
-3 2 0 1
1
6
1
—
zj
cj-zj
0 0 0 0
1 1 0 0
0
1
x1
s2
1
0
1 -1 1 0
0 -1 3 1
1
9
zj
cj-zj
1 -1 1 0
0 2 -1 0
1
填入单纯形表计算得：
解：在上述问题的约束条件中加入松驰变量，得标准型如下：
12
1 2 1
1 2 2
1 2 1 2
m a x
1,
3 2 6,
,,,0,
z x x
x x s
x x s
x x s s
目 标 函 数约 束 条 件管 理 运 筹 学 33
§ 4 几种特殊情况
12a
从单纯形表中，从第一次迭代的检验数等于 2，可知所得的基本可行解
x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第 2次迭代，那么就选 x2为入基变量，但是在选择出基变量时遇到了问题,=-1,=-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从 1次迭代的单纯形表中，得到约束方程：
22a
22a
移项可得：
1 2 1
2 1 2
1,
3 9,
x x s
x s s
1 2 1
2 2 1
21
1
2
1
2
12
1,
3 9,
,0,
1,
,
0,
9.
1 2 1,
x x s
s x s
x M s
xM
xM
s
sM
z x x M M M
不 妨 设 可 得 一 组 解,
显 然 这 是 线 性 规 划 的 可 行 解,此 时 目 标 函 数管 理 运 筹 学 34
§ 4 几种特殊情况
ij?
由于 M可以是任意大的正数，可知此目标函数值无界。
上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：
在某次迭代的单纯形表中，如果存在着一个大于零的检验数,并且该列的系数向量的每个元素 aij(i=1,2,…,m) 都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。
三、无穷多最优解例 3、用单纯形法表求解下面的线性规划问题。
12
12
12
2
12
m a x 50 50
300,
2 400,
250,
,0.
z x x
xx
xx
x
xx
目 标 函 数约 束 条 件管 理 运 筹 学 35
§ 4 几种特殊情况解：此题我们用图解法已求了解，现在用单纯形表来求解。
1 2 3
12
1 2 1
1 2 2
23
1 2 1 2 3
,,
m a x 5 0 5 0
3 0 0,
2 4 0 0,
2 5 0,
,,,,0,
s s s
z x x
x x s
x x s
xs
x x s s s
加 入 松 弛 变 量,我 们 得 到 标 准 形,
目 标 函 数约 束 条 件填入单纯形表计算得：
管 理 运 筹 学 36
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 s1 s2 s3 b 比值
50 50 0 0 0
0
s1
s2
s3
0
0
0
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
300
400
250
300/1
400/1
250/1
zj
cj-zj
0 0 0 0 0
50 50 0 0 0
0
1
s1
s2
x2
0
0
50
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
50
150
250
50/1
150/2
—
zj
cj-zj
0 50 0 0 50
50 0 0 0 0
12500
2
x1
s2
x2
50
0
50
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
50
50
250
—
50/1
250/1
zj
cj-zj
50 50 50 0 0
0 0 -50 0 0
15000
管 理 运 筹 学 37
§ 4 几种特殊情况
1 2 4,,
这样我们求得了最优解为 x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为 15000。这个最优解是否是惟一的呢？由于在第 2次迭代的检验数中除了基变量的检验数 等于零外，非基变量 s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第 3次迭代。可求得另一个基本可行解，如下表所示：
迭代次数基变量
CB x1 x2 s1 s2 s3 b
50 50 0 0 0
3
x1
s3
x2
50
0
50
1 0 -1 1 0
0 0 -2 1 1
0 1 2 -1 0
100
50
200
zj
cj-zj
50 50 50 0 0
0 0 -50 0 0
15000
管 理 运 筹 学 38
§ 4 几种特殊情况从检验数可知此基本可行解 x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，
从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量 Z1,Z2表示上述两个最优解即 Z1 =（ 50,250,0,50,0）,Z2
=（ 100,200,0,0,50），则此线段上的任一点，即可表示为 αZ1+（ 1-
α） Z2，其中 0≤α≤1。如图 5-1所示：
100 200 300
100
200
300
250 Z1
Z2
图 5-1
管 理 运 筹 学 39
§ 4 几种特殊情况
s?
在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数为零，为什么我们把这个非基变量 xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？
不妨设出基变量为 xk，则原最优单纯形表可表示如下：
1 1 1
1 1 1,
,
1 1 1,
,
1 1 2 2
1
0
0
1
0
0
00
0,0
ks
ks
s
k k k s
k k k s
k k k s
m m m s
j j j
m
s s s m m s s s i is
i
xx
cc
x c a
x c a
x c a
x c a
x c a
cz
c a c a c a c c c a
从 此 表 可 知 即 有,也 就 是 。
管 理 运 筹 学 40
§ 4 几种特殊情况通过迭代，我们得到了新的单纯形表，其中 xs为基变量了，而 xk为非基变量了。我们可得到下表。
1
11
1
11
1
11
1
1
11
0
11
0
11
1
1
0
0
0
ks
ks
s
ks
km
k i is i is s
i i kk s k s
ks
m
kk
ks
i is k k s s
ik s k s
ss
ks
ks
kk
ks
ms
mm
ks
j k s
j j j k
xx
cc
a
xc
a
z c a c a c
aa
a
xc
a c a c a c
aa
xc
a
c
a
xc
a
a
xc
a
z z c
c z c z
在 此 表 中把
1
11
.
0.
m
s i is
i
k s k k s s k
k s k s
j k j k
ca
z c c a c c
aa
c z c z
,代 入 上 式 得,
即 又 可 得 到,
管 理 运 筹 学 41
§ 4 几种特殊情况又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。
这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。
四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。
例 4.用单纯形表，求解下列线性规划问题。
解：加上松驰变量 s1,s2,s3化为标准形式后，
填入单纯形表计算得：
13
12
13
1 2 3
1 2 3
3
m a x 2
2
2,
2 4,
3,
,,0,
z x x
xx
xx
x x x
x x x
目 标 函 数约 束 条 件管 理 运 筹 学 42
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 x3 s1 s2 s3 b 比值
2 0 3/2 0 0 0
0
s1
s2
s3
0
0
0
1 -1 0 1 0 0
2 0 1 0 1 0
1 1 1 0 0 1
2
4
3
2/1
4/2
3/1
zj
cj-zj
0 0 0 0 0 0
2 0 3/2 0 0 0
0
1
x1
s2
s3
2
0
0
1 -1 0 1 0 0
0 2 1 -2 1 0
0 2 1 -1 0 1
2
0
1
—
0/2
1/2
zj
cj-zj
2 -2 0 0 0 0
0 2 3/2 -2 0 0
4
2
x1
x2
s3
2
0
0
1 0 1/2 0 1/2 0
0 1 1/2 - 1 1/2 0
0 0 0 1 -1 1
2
0
1
2/(1/2)
0/(1/2)
—
zj
cj-zj
2 0 1 0 1 0
0 0 1/2 0 -1 0
4
管 理 运 筹 学 43
§ 4 几种特殊情况在以上的计算中可以看出在 0次迭代中，由于比值 b1/a11=b2/a21=2为最小比值，导致在第 1次迭代中出现了退化，基变量 s2=0。又由于在第 1次迭代出现了退化，基变量 s2=0，又导致第 2次迭代所取得的目标函数值并没有得到改善，仍然与第 1次迭代的一样都等于 4。像这样继续迭代而得不到目标函数的改善，
当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：
管 理 运 筹 学 44
§ 4 几种特殊情况迭代次数基变量
CB x1 x2 x3 s1 s2 s3 b 比值
2 0 3/2 0 0 0
3
x1
x3
s3
2
3/2
0
1 -1 0 1 0 0
0 2 1 - 2 1 0
0 0 0 1 -1 1
2
0
1
2/1
—
1/1
zj
cj-zj
2 1 3/2 -1 3/2 0
0 -1 0 1 -3/2 0
4
4
x1
x3
s1
2
3/2
0
1 -1 0 0 1 -1
0 2 1 0 -1 2
0 0 0 1 -1 1
2
2
1
zj
cj-zj
2 1 3/2 0 1/2 1
0 -1 0 0 -1/2 -1
5
管 理 运 筹 学 45
§ 4 几种特殊情况得到了最优解 x1=1,x2=0,x3=2,s1=1,s2=0,s3=0,其最优值为 5。
但有时候当出现退化时,即使存在最优解,而迭代过程总是重复解的某一部分迭代过程,出现了计算过程的循环,目标函数值总是不变,永远达不到最优解 。
下面一个是由 E.Beale给出的循环的例子。
例 5
目标函数 min f =－ （ 3/4） x4+20x5－ （ 1／ 2） x6+6x7.
约束条件,x1+（ 1／ 4） x4－ 8x5－ x6+9x7=0，
x2+（ 1／ 2） x4－ 12x5－ （ 1／ 2） x6+3x7=0，
x3+x6=1，
x1,x2,x3,x4,x5,x6,x7≥ 0.
管 理 运 筹 学 46
§ 4 几种特殊情况这个例题的确存在最优解，但用一般单纯形表法，经过 6
次迭代后得到的单纯形表与第 0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。
首先我们把松弛变量（剩余变量）、人工变量都用 xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，
人工变量的下标号列在松弛变量（剩余变量）之后，在计算
（ 1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。
（ 2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。
这样就一定能避免出现循环。
