第2章单纯形法的几种特殊情况解读

单纯形法的几种特殊情况单纯形法是一种线性规划的解法方法，用于寻找最优解。

在实际应用中，存在一些特殊情况，需要对单纯形法进行一些调整或者使用其他方法来解决。

下面将介绍几种特殊情况：1.无解情况（不可行解）：在一些情况下，约束条件可能是冲突的，导致不存在可行解。

例如，所有约束条件加在一起可能无法满足，或者一些约束条件是矛盾的，比如两个约束条件同时要求一些变量分别为正和负。

在这种情况下，单纯形法无法找到最优解，因为没有可行解。

解决方法：可以使用其他的线性规划求解方法，或者对约束条件进行调整，使其变为可行的。

例如，可以通过增加松弛变量或引入人工变量来处理不等式约束条件，在目标函数中增加人工变量的惩罚项，逐步通过单纯形法逼近可行解。

2.多个最优解：在一些情况下，线性规划问题可能存在多个最优解。

这种情况下，目标函数的值相同，但对应的解并不相同。

单纯形法只能找到一个最优解，无法得知是否存在其他最优解。

解决方法：需要使用其他算法或方法来找到额外的最优解。

例如，可以通过改变目标函数的系数或增加一些额外的约束条件，以影响单纯形法的方向，从而找到其他的最优解。

3.无界问题：在一些情况下，线性规划问题可能是无界的，即目标函数可以无限大地增加或无限小地减小。

这种情况下，单纯形法将无法找到有限的最优解。

解决方法：可以通过增加约束条件或调整目标函数的系数，使得问题变为有界的。

另外，也可以使用其他线性规划求解方法来处理无界问题。

4.退化情况：在单纯形法中，可能存在一些情况下的解陷入循环，无法继续优化。

这种情况下，称为退化。

解决方法：可以使用退化处理技术，例如人工变量法、卡工法、两阶段法等，来克服退化问题，并继续求解最优解。

5.基变量的选择：在单纯形法中，需要选择初始基变量，以便进行迭代求解。

但是，对于一些问题，选择合适的初始基变量可能非常困难，并且可能会影响最终的最优解。

解决方法：可以使用启发式的方法，例如字典法，以确定合适的初始基变量。

转(2)
从环节(2)-(5)旳每一种循环，称为一次单纯形迭代.
24
单纯形表计算环节举例 给定线性规划问题
例1 Max z = 50x1 + 30x2 4x1+3x2 ≤ 120
s.t 2x1+ x2 ≤ 50 x1，x2 ≥ 0
Max z = 50x1 + 30x2
4x1+ 3x2 + x3
= 120
数
0 CN CB B1 N
16
单纯形表
相应于基B旳单纯形表: (2.15)-(2.17)旳表格形式
cj
c1
… cm
cm+1
…
cn
CB XB b
x1
… xm
xm+1
…
xn
I
c1 x1 b’1
1
…0
a’1,m+1
…
a’1n
1
c2 x2 b’2
0
…0
a’2,m+1
…
a’2n
2
…
…
…
…
cm xm b’m
5
B2 = ( P3 P4 P2 )
z= 0 + 40 x1 + 50 x2 ④ x3 + 2x2 = 30 - x1 ①
x4 + 2x2 = 60 – 3x1 ② 2x2 = 24 - x5 ③
Max z = 40 x1 +50 x2
x1 +2x2 +x3
=30
3x1 +2x2 +x4 =60
2x2
由最小θ比值法求：
θ= min
b’i
a'i,m+k

T
1 0 为基矩阵 B = (α3 α4 ) = 0 1
为基变量， 则 x 3 , x 4 为基变量，x 1 , x 2 为非基变量
令非基变量 x1 = x2 = 0 ，则可以得到一基本 可行解为： 可行解为：
X 0 = (0 , 0 , 100 , 120 )
T
下面的计算都是以它为初始点逐次施行转 初始基本可行解 换，故将其称为初始基本可行解。 故将其称为初始基本可行解。
1 1 x 2 + x 3 − x 4 = 20 2 4 1 3 x1 − x 3 + x 4 = 20 4 8
3 z = 180 + x 2 − x 4 2 20 − 1 x + 1 x − 3 x = 180 + 3 4 4 2 4 2 1 5 = 200 − x 3 − x 4 2 4
3 z = 180 + x 2 − x 4 2
的系数仍为正 非基变量 x2 的系数仍为正数，由最大检 验数规则， 进基变量。 验数规则，则确定 x2 为进基变量。再按 最小比值规则， 离基变量。 最小比值规则，确定 x3 为离基变量。 主方程中所含的基变量就是离基变量 离基变量。 主方程中所含的基变量就是离基变量。
100 120
加工时间 （小时） 小时）
单位利润 百元） （百元）
解：该问题的LP模型为 该问题的LP模型为 LP
max z = 6 x1 + 4 x2 2 x1 + 3 x2 ≤ 100 s.t. 4 x1 + 2 x2 ≤ 120 x , x ≥ 0 1 2
将该问题的LP模型化为标准形 将该问题的LP模型化为标准形 LP
分析

此时基变量为： x3 , x2 , x1
非基变量为：x4 , x5 得到另一基本可行解为：
X 2 4,6,4,0,0
T
z1 42
迭代结果
2 1 x3 x4 x5 4 3 3 1 x4 6 x2 2 2 1 x4 x5 4 x1 3 3
最小比值规则
当确定进基变量后，以进基变量的系数列向量 中的正数为分母，以相应的方程右端常数为分子求 最小比值，所得到的最小比值的分母就是主元。主 元所在的方程中的基变量就是离基变量。即：
bi bl min ik 0 aik alk
令新的非基变量 x3 x4 0 ,得到新的 基本可行解: T
12 36 12 x2 m in , 2 4 2
2是主元，其所在方程为主方程，且
x4 为离基变量。
此时基变量为： x3 , x2 , x5
非基变量为： x1 , x4 得到另一基本可行解为：
X1 0,6,8,0,12
T
z1 30
迭代结果
8 x1 x3 1 6 x2 x4 2 3 x 2 x x 12 1 4 5
单纯形法的3种形式——
方程组形式（代数形式） 表格形式 矩阵形式
单纯形法的基本思路——
基于LP问题的标准形，先设法找到某个基本 可行解（称为初始基本可行解）； 开始实施从这个基本可行解向另一个基本可 行解的转换，要求这种转换不仅容易实现， 而且能改善（至少保持）目标函数值； 继续寻找更优的基本可行解，进一步改进目 标函数值。当某一个基本可行解不能再改善 时，该解就是最优解。（或者是出现无可行 解、无最优解、无穷多最优解的情况）