min f x1 3x2 x3 s.t. x2 2 x3 x4 4 x1 2 x2 x3 x4 x5 4 3x1 3x3 x4 4 x j 0, j 1, ,5
解：只需引入两个人工变量 x6 和 x7 ，相应的辅 助线性规划问题（ALP）如下：
min cT x MeT x s.t. Ax x b x 0,xα 0
（2 ）
其中 A 是 m n 矩阵， b 0, M 0 很大， e 是分量全为 1 的 m 维列向量。
0 ，用单纯形法求解（2） 显然， （2）有初始可行解 ， b
其结果必为下列几种情形之一：
两阶段法的第二阶段。 综上所述，对不具有明显可行基的（ LP ） ，可 先用单纯形法求解辅助性性规划问题（ALP） ，解 的结果或者说明（LP）无可行解，或者找到（LP） 的一个基本可行解， 然后再从这个基本可行解开始 应用单纯形法求解（LP） ，此即两阶段法的第二阶 段。将目标函数 g 用非基变量表示如下：
1/3
-7/2
-1
0
-4/3
21/6
0
0
1/3
7
f
-3/2 -7/2
x1
x2 0 1
x3 1 0
x4 -1/8 1/4
x5 -1/8 -3/4
x6 1/8 -1/4
x7 1/8 3/4 3/8 1/4 0
x3
x2 g
1/4 1/2
0
1/4 x1
0
0 x2 -1/2 2
-1/2
0
0 x3 1 0
0
0
一： 情形 1： x 0 ，这时（LP）无可行解。因为
ˆ 如果（LP）有可行解 x 的可行解，在此点， （ALP）的目标函数值
优值。
ˆ x x x ，则 0 是（ALP）
ˆ eT 0 0 eT x ，而 eT x 是（ALP）的最 g 0T x
其中
1 Ers

b1s brs
1
br 1, s brs 1 brs

b11, s brs bms brs
1

1
定理证明见陈开周老师课本 P151-153。
料的费用最小？ 解：设 x j 为每单位饲料中第 j 种配料的含量 （ j 1, , n ） ，则营养问题的数学模型为
min c j x j
j 1 n
s.t. aij x j bi i 1,
j 1
n
,m
x j 0, j 1,
,n
（1）
现在从另一角度提出如下问题：某饲料公司欲 把这 m 种营养成分分别制成 m 种营养丸出售。 公司面临的问题是，在上述条件的限制下，如 何确定各种营养丸的单位价格，才能使公司获 利最大？ 设第 i 种营养丸的单价为 yi (i 1,
一．两阶段法 算法的第一阶段：用单纯形法消去人工变量（如 可能的话） ，即把人工变量换成非基变量，求出 （LP）的一个基本可行解。 对 上 述 （ LP ） ，引入 m 个人工变量
xni 0 ( i 1, , m ) 后，
用单纯形法求解如下的辅助问题（ALP）
min g eT x s.t. Ax x b x 0, x 0
§7 线性规划的对偶理论 一． 引例 例（营养问题）某饲养场所用的饲料由 n 种配料 混合而成，要求这种饲料必须含有 m 种营养成分， 且每单位饲料中第 i 种营养成分的含量不能低于 bi 。 已知第 i 种营养成分在每单位第 j 种配料中的含 量为 aij ，第 j 种配料的单位价格为 c j ，问在保证 营养要求的条件下，应采用何种配方才能使饲
二. 对偶问题的表达 1.对称形式的对偶 定义 7.1：设有线性规划问题
min s.t. cT x Ax b x0
（3）
其中
x1 c1 b1 x c b x c b n n m
a11 a21 A am1
表 1 第一阶段初始单纯形表
表 2 第一阶段迭代一次后的单纯形表
第一阶段迭代两次后的最优单纯形表
表 4 第一阶段最优单纯形表去人工变量后的单纯形表
表 5 第二阶段初始单纯形表及最优单纯形表
此时， 表中所有检验数均非正， 所以原线性规划问题的最
* T * 优解和最优值分别为 x (0, 4 / 3, 4 / 3,0,0) , f 8 / 3.
x2 -1 1 0 0 x2 -1/6 4/3
x3 6 2 8 -21 x3 1 0
x4 -1 0 -1 0 x4 -1/6 1/3
Hale Waihona Puke x5 0 -1 -1 0 x5 0 -1
x6 1 0 0 0 x6 1/6 -1/3
x7 0 1 0 0 x7 0 1
1/3 1/3
2
1 3
g
f
0
x7
g
2/3
4/3
0
0
情形 1：达到问题（2）的最优解，且 x =0。此时 得到的 x 即为（1）的最优解；
T e 情形 2：达到问题（2）的最优解，且 x 0 ，此
时线性规划问题（1）无可行解； 情形 3：问题（2）不存在有限最优值，在单纯
1 max 0, B Pk 0, x 0 ，这时， i 形表中， k
其中 e 为分量全为 1 的 m 维列向量，
x ( xn1 , , xn m )T 是人工变量构成的 m 维列
x 0 向量。显然， x b 为（ALP）的一个基本
可行解。
设（ALP）是非退化的，求解（ALP）得到的
x 最优基本可行解是 x ，此时必有下列情形之
考虑标准形式的线性规划问题：
min ( LP) s.t.
cT x Ax b x0
不妨设 b 0 ，但并不要求 A 为行满秩矩阵。 对于一般标准型的线性规划问题， 约束方程组的系 数矩阵中不包含单位矩阵。本节通过引进人工变量， 产生一个单位矩阵，构造新的目标函数，得到新的问 题，进而得到原问题的基本可行解。
min g x6 x7 s.t. x1 x2 6 x3 x4 x6 2 x1 x2 2 x3 x5 x7 1 x j 0, j 1, ,7
,5
解：增加人工变量 x6 , x7 的辅助线性规划问题
x1 x6 x7 1 1 2 -5 x1 x3 1/6 2/3
0
-1
-1
f
-21/8 -21/8 x4 -1/4 1/2
-11/4
21/8 21/8
63/8
x5 1/4 -2/3
-9/4
x3
0 1
0
1/4 1/2 31/4
x1
f
* T 原 问 题 的 最 优 解 x (1/ 2,0,1/ 4,0,0) , 最 优 解
f * 31/ 4 。
例 2 求解线性规划问题
二．大 M 法 基本思想：在约束中增加人工变量 x ，同时
T Me x ，其中 M 是很 修改目标函数，加上罚项
大的正数，这样，在极小化目标函数的过程 中，由于大 M 的存在，将迫使人工变量离基. 考虑线性规划问题（LP）
min f cT x s.t. Ax b x0
（1）
引进人工变量 x ，研究下列问题
ˆ 1 进而完成单纯形法 逆 B 1 来获得新基的逆 B
的其他运算。在整个计算过程中，始终 持现行基的逆。
ˆ 1 ？ 怎样由 B 1 获得 B
保
定理6.1 设在单纯形法某次迭代中可 行基为 B ，以 brs 为主元作旋转变换后，则
ˆ 1 为 下一次新基的逆 B
ˆ 1 E B 1 B rs
为以后的运算方便，也可将 f c1 x1
cn xn 0 写
入上述问题的约束之中。于是可得（ALP）的一 个单纯形表。
两阶段法的初始单纯形表
例 1 求解
min z 5 x1 21x3 s.t. x1 x2 6 x3 x4 2 x1 x2 2 x3 x5 1 x j 0, j 1,
问题（1）无界； 情形 4：问题（2）不存在有限最优值，在单纯形
1 max 0, B Pk 0, 有些人工变量不 i 表中， k
T e 等于零,即 x 0 ,此时（1）无可行解.
例 3 用大 M 法求解
min f x1 x2 3x3 s.t. x1 2 x2 x3 11 2x1 x2 4 x3 3 x1 2 x3 1 x1 ,x2 ,x3 0
min g x6 x7 s.t. x2 2 x3 x4 x6 4 x1 2 x2 x3 x4 x5 4 3x1 3x3 x4 x7 4 x j 0, j 1, ,7
取初始可行基 B ( P6 , P5 , P7 ) ，相应的单纯形表如 表 1。
g xni (bi aij x j ) bi
i 1 i 1 j 1 i 1 j 1 m m n m n m
a x
i 1 ij
j
于是辅助问题可写成如下形式：
min g bi aij x j
i 1 j 1 i 1
m
n
m
s.t. Ax x b x 0, x 0
。
由于M是很大的正数，因此所有的判别数都非 正，且人工变量都取零值，原来问题的最优解 x ( x1 , x2 , x3 )T (9,1, 4)T 目标函数的最优值为
f 2