下载掌阅APP，畅读海量书库
立即打开
用矩阵来描述单纯形法的计算过程，有助于加深我们对单纯形法的理解。
对于线性规划问题：
加入松弛变量Xs＝（X n＋1 ，X n＋2 ，…，X n＋m ） T 以后，得到标准型：
这里 I 是 m × m 单位矩阵。
设 B 是一个可行基，也称基矩阵。将系数矩阵（ A ， I ）分为（ B ， N ）两块，这里 N 是非基变量的系数矩阵。
对应于
B
的变量
X
B
1
，
X
B
2
，…，
X
BM
是基变量，用向量
X
B
表示。其他为非基变量，用向量
X
N
表示，则
。
同时将 C 也分为两块（ C B ， C N ）。 C B 是目标函数中基变量 X B 的系数行向量； C N 是目标函数中非基变量 X N 的系数行向量。于是约束条件可以转化为：
这时可以将原问题改写为：
将约束条件进行等价转换后得到：
将上式代入目标函数得到：
令非基变量
X
N
＝
0
，可以得到一个基可行解
。
对应目标函数值为 z （1） ＝ C B B －1 b 。
从以上分析可以看出：
（1）非基变量的系数 C N － C B B －1 N 就是单纯形法中的检验数。
（2）用矩阵描述时， θ 规则的表达式是：
这里（ B －1 b ） i 是向量（ B －1 b ）中第 i 个元素，（ B －1 P j ） i 是向量（ B －1 P j ）中第 i 个元素。这里 θ 的表达式的形式与之前有所不同，但是其含义完全相同。
为了方便于在单纯形表中找到 B －1 所在位置，将 z ＝ C B X B ＋ C N X N 改写为－ z ＋ C B X B ＋ C N′ X N′ ＋0 X s ＝0，约束条件 BX B ＋ NX N ＝ b 也改写为 BX B ＋ N′X N′ ＋ IX s ＝ b 。
X s 是当前的基本变量， X N′ 为其他的非基本变量，当确定 X B 为新的基变量时，经过基变换，可以得到：
上述两式用矩阵关系式表示为：
这些分块的系数矩阵可以用表格形式表示（见表2.10）。
表2.10
在分块的系数矩阵中，（0，1） T 这一列不参加运算，所以表格中不填这些数字。表2.10即为迭代后的计算表，各部分数字都可以用矩阵的运算求得。此外可见在初始单位矩阵的位置，在各个运算表中就是 B －1 的所在位置。
由于单纯形法的迭代过程中基矩阵的逆矩阵 B －1 求出后，单纯形表上的其他行和列的数字也随之可以确定。按这一分析对单纯形法进行改进，计算步骤为：
（1）根据给出的线性规划问题，在加入松弛变量或人工变量后，得到初始基变量。求初始基矩阵 B 的逆矩阵 B －1 。
求出初始解：
然后计算单纯形乘子 Y ＝ C B B －1 。
（2）计算非基变量 X N 的检验数 σ N ， σ N ＝ C N － C B B －1 N 。若 σ N ≤0，已经得到最优解，可以停止计算；若不是，转下一步。
（3）根据max（ σ j ｜ σ j ＞0）＝ σ k 所对应的非基变量 X k 为换入变量计算 B －1 P k ，若 B －1 P k ≤0，那么问题无解，停止计算；否则进入下一步。
（4）根据 θ 规则，求出：
它对应的基变量 X l 为换出变量。是可以给出一组新的基变量以及新的基矩阵 B 1 。
（5）计算新的基矩阵
B
1
的逆矩阵
，求出
和
。重复（2）～（5）。
单纯形法的迭代过程中，上一步迭代的基
B
与下一步迭代的基
B
1
之间只差了一个变量。如何只根据
B
－1
和换入变量
X
k
的系数列向量
P
k
来计算出
，而不是直接求出
，其计算过程为：
①把 m × m 单位矩阵 I m 表示为 I m ＝（ e 1 ， e 2 ，…， e m ）。 e i 表示第 i 个位置的元素是1，其他元素均为0的单位列向量。
②设
X
k
为换入变量，
X
l
为换出变量，则有
。
其中：
例2.7 用改进单纯形法求解。
解：初始基
B
0
＝（
P
3
，
P
4
，
P
5
）是单位阵，基变量
。相应地，
（0，0，0），
，
。计算非基变量检验数
（2，3），由此可以确定
x
2
为换入变量，计算：
对应的换出变量为 x 5 。
于是得到新的基
B
1
＝（
P
3
，
P
4
，
P
2
），
，
（2，0）。
下面进行基转换，
，
：
非基变量检验数：
所以下一步换入变量为 x 1 ，计算：
换出变量为第一基本变量
x
3
。于是得到新的基
B
2
＝（
P
1
，
P
4
，
P
2
），
，
，
第二步迭代计算：
所以，
。
非基变量检验数：
x 5 为换入变量，再确定换出变量：
所以对应的换出变量为 x 4 。再重复之前的步骤，最后得到最优解：
X ＊ ＝（4，2，0，0，4） T
2.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？
2.2 将下列线性规划问题化为标准形式。
2.3 用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步得到的基可行解对应与图解法可行域中的哪个点。
2.4 对下列线性规划问题，找出所有基本解，判断哪些是基可行解，并用图解法说明。
2.5 求解下列线性规划问题。
微信扫码，
加入【本书话题交流群】
与同读本书的读者，讨论本书相关话题，交流阅读心得
整数规划（Integer Programming）
整数线性规划（Integer Linear Programming）
混合整数规划（Mixed Integer Programming）
0－1规划（Zero－one Integer Programming）
分支定界法（Branch and Bound Method）
割平面法（Cutting Plane Algorithm）
线性规划问题的解都假设为具有连续型数值，但是在许多实际问题中，决策变量仅仅在取整数值时才有意义，比如变量表示的是工人的数量、机器的台数、货物的箱数、装货的车皮数等。为了满足整数解的要求，比较自然的简便方法似乎就是把用线性规划方法所求得的分数解进行“四舍五入”或“取整”处理。虽然这样做有时也可以取得与整数最优解相近的可行整数解，但是有时这样处理得到的解可能不是整数最优解，甚至不是原问题的可行解，因而发展出分支定界法和割平面法等整数规划问题的专用解法。
在一个线性规划问题中，如果它的所有决策变量都要求取整数时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混合整数规划，二者统称为整数规划。整数规划的一个特殊情形是0－1规划，它的决策变量取值仅限于0或1两个逻辑值。
例3.1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如表3.1所示。两种货物各装运多少箱，可使获得利润最大？
表3.1
解：设甲、乙两种货物装运箱数分别为 x 1 和 x 2 ，显然， x 1 和 x 2 都需取整数，于是可建立整数规划模型如下：
若暂且不考虑 x 1 和 x 2 取整数这一条件，则规划就变为下列线性规划：
去掉整数限定后的规划问题称为原整数规划的伴随规划或松弛规划。求解例3.1的伴随规划： x 1 ＝4.8， x 2 ＝0， z′ ＝96。
但此解不满足整数要求，因此它不是原规划的最优解，一个直观的想法是对伴随规划的解进行四舍五入处理，得到 x 1 ＝5， x 2 ＝0，但它不是原规划的可行解。
若伴随规划的可行域是有界的，则原整数规划的可行域应是伴随规划可行域中有限个格点（整数点）的集合。因此，另一个直接的思路是能否用“穷举法”来求解整数规划。将伴随规划中所有整数点的目标函数值都计算出来，然后逐一比较找出最优解。这种方法对变量所能取的整数值个数较少时，勉强可以应用，如本例 x 1 可取0，1，2，3，4共5个数值，而 x 2 只能取0，1，2共三个数值，因此其组合最多为15个（其中还包含不可行的点）。但对大型问题，这种组合数的个数可能大得惊人，如在指派问题中，有 n 项任务指派 n 个人去完成，不同的指派方案共有 n ！种。当 n ＝20时，这个数超过2 1013 。显然穷举法并不是求解整数规划的有效方法。自20世纪60年代以来，已发展了一些常用的解整数规划的算法，如各种类型的割平面法、分支定界法、解0－1规划的隐枚举法、分解方法、群论方法、动态规划方法等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果。
割平面法是从松弛问题的一个非整数的最优解出发，序贯地每次添加一个新的线性不等式（其对应线性方程所代表的超平面即称为割平面），求解新的松弛问题。每次增添的新的不等式要满足两个条件：①前一个不等式的最优解不满足这个不等式，即松弛问题的可行解集合被割去了一块。② S 中的“点”都满足这个不等式，即保证整数可行解不被割去。