研究生 必须课 工程数学 2-2-第二章 线性规划-单纯形方法

则选取对应的 由于 σ m+k 因此当
x m+k 为换 入变量， > 0 且为最大，
x m+1 x m+2 可使 目标函数值 Z = CB B b+(σ m+1, σ m+1, L , σ n ) M 最大限度的增加 。 xn
-1
x m+k 由零增至正值，
Dantzig的单纯形法 把寻 优的目标集 中在所有基本可行解（即可行域 顶点） 中。 其基本 思路是从 一个初始的基本可行解 出发， 寻找 一 条达 到最优基本可 行解的最佳途径 。 单纯形法的一般步骤如下： （ 1）寻找一个初始的基本可行解 ; （ 2）检查现行的基本可行解是否最优可行解 ; （ 3） 如果 不是 最优可行解，如何 改 善现行的基本可行解 ——进行基变 换，得 到下一个基本可行解。
x m+ 1 M -1 Z= C B B b+ ( σ m+ 1 , L , σ m + k , L , σ n ) λ = C B B -1 b+ σ m+ k λ M x n
因为 σ m+k > 0, 故当λ→ +∞时， Z→ +∞。
-1 -1 -1 -1
> 0，
max Z=CX, AX=b, X ≥ 0 的可行基，则 XB XB -1 -1 A X = b ⇒ (B N ) =B b = b ⇒ ( I ,B N ) X N X N
假设Ｂ是 线性规划
−1 令非基变量 X N =0，则基变量 X B =B b。
X Z = C X = (C B C N ) B XN = C B X B + C N X N = C B (B -1 b-B -1 N X N )+ C N X N
体现 了极 值的 思想
-1 其中 σ N =C N -C B B N=(σ m+1 , σ m+1 , L , σ n ) 称为非基变量Ｘ N的检验向量，
X A X = (B N ) B = B X B + N X XN
N
=b
用 可行基 Ｂ的逆阵Ｂ -1左乘等式两端，再通过移项可推得 ：
X B =B -1 b-B -1 NX N
若令所有非基变量
X N =0
, 则 基变量
X B = B -1 b
由此可得初始的基本可行解
B −1 b X= 0
可得 基本可行解 X=
−1
B−1 b 。 0
Ø 用逆阵 B 左乘约束方程 组的两端， 等价于对方程组施以一 系列的初 等 “行变换 ”。变换 的结果是将系数矩阵Ａ中的可行基 Ｂ变换成单 位矩阵 I， 把非基变量系数列向量构成 的矩阵Ｎ变 换成 成 B b。
−1
B −1 N ，把向量b变 换
则线性规划问题有无穷多最优解。
2
换入变量和 换出变量的 确定 ： l l换入 变量的确定 — 最 大增加原则 假设检验 向量 σ N =C N -C B B -1 N=(σ m+1 , σ m+2 , L σ n ) ， 若其中有 两个以上的 检验数为正 ，那么为了 使目标函数 值增加得快些， 通常 要用 “最大增加原 则 ”，即 选取最大正 检验数所对应的非基变量为换入变 量， 即若 换出变量的 确定 — 最小比值原 则 如果确定 x m+k为换入变量，方程
x m+ 1 x m +2 Z = C B B -1 b+ ( σ m+ 1, σ m + 1, L , σ n ) M xn
如果现 行的基本可行解Ｘ不是 最优解，即在检验向量 σ N =C N -C B B -1 N 中 存 在 正 的 检 验数， 则 需 在原基本可行解Ｘ的基 础 上寻找一 个新 的基本可行解，并使目标函数值有 所改善。具体做法是： Ø 先 从检 验 数为正 的非基变量中 确 定一个 换 入 变量， 使它从 非基变量变 成基 变量 （将它的值从零增至正 值）。
1
AX=b → BX B +NX N =b → X B =B -1 b -B -1 N X N → X N =0, X B =B -1 b
l 问题： Ø 要判断 m个系数列向量是否恰好构成一个基并不是 一件容易的 事。 基由系数矩阵Ａ中 m个线性 无关的系数列向量构成 。 但是要判断 m个 系数列向量 是否线性无关并非易事 。 Ø 即使 系数矩阵Ａ中找到了一个可行基 B，也不能保证该基恰好是可行基。 因为 不能保证基变量Ｘ B=Ｂ -1b≥ 0。 为了设法得 到一个 m阶单位矩阵I作为初始可行基Ｂ，可 在性规 划标准化过程中 作如下处理： Ø 若在化标准形式前， m个约束方程都是 “≤ ”的形式， 那么在化标准 形时只需在 一个约束不等式左端都加上一个松弛变 量 xn+i (i=12…m)。 Ø 若在 化标准形式前，约束方程中有 “≥ ”不等式， 那么在化标准形 时除了在方程式左端减去剩余变量 使不等式变 成等式以外，还必须在左端再加上一个非负新变量，称为 人工变量． Ø 若在 化标准形式前，约束方程中有等式 方程，那么 可以直接在 等式左端添加人工变量。
B−1b -1 Ø 为了 求得基本可行解 X= ，必须求可行基 Ｂ的逆阵Ｂ 。 0
但是 求逆阵Ｂ -1也是一 件麻烦的事 。 l 结 论： 在 线性规划 标准 化 过 程中 设 法 得 到一个 m阶 单 位 矩阵 I作 为初始可行 基Ｂ ，
要 判定 Z = C B B -1 b 是否已经达到最大值，只需将
其中 C B =(c1 ,c 2 , L c m ), C N =(c m+1 ,c m+2 ,L c n ) 分别表示 基变量和 非基变量所对应的系数子 向量。
x m+ 1 = C B B -1 b+ (C N -C B B -1 N )X N x = C B B -1 b+ σ N X N = C B B -1 b+ ( σ m +1, σ m+ 1, L , σ n ) m +2 M ——线性问题的典式(或规范式) xn
-1 由于行初等 变换后的方程组 (I,B N )
与原 约束方程组 AX=b或 ( B , N )
'
X X
B N
= b 同解
XB -1 =B b XN
例1
maxZ=5x 1 + 2x 2 + 3x 3 − x 4 + x 5
C = ( 5 ,2 ,3 , − 1 ,1 )
p p p
单纯形法的一般原理
考虑到如下线性规划问题
max
Z=CX
AX=b X ≥ 0
其中 Ａ 一个 m× n矩阵，且秩为 m， b总可以被调整为一个 m维非负列向量， Ｃ为 n维行向量，Ｘ为 n维列向量。 根据线性规划基本定理： 如果可行域Ｄ ={ Ｘ∈Ｒ n / ＡＸ =ｂ，Ｘ≥ 0}非空有界， 则 Ｄ上 的最优目标函数值Ｚ =ＣＸ一定可以 在Ｄ的一个 顶点上达到。 这 个重要的定理启发了丹齐格 (G. B Dantzig)的单纯形法， 即将寻优的目标 集中 在 D的各个顶点上。
(B -1 b) i min -1 , (B Pm+k )i
(B -1 b)l (B -1 Pm+k )i >0,1 ≤ i ≤ m = -1 (B Pm+k ) l
则选取对应的基变量 x l 为换出变量。
n 用 初等变换求改进了的基本可行解
定理 3：无 (有界 )最优解 判别定理 B −1 b 若 X= 是一个基本可行解，有一个 检验数σ m+k 0 但 是 B -1Pm+k ≤ 0 ，则该线性规划问题 无 (有界 )最优解。 证： 令 x m+k = λ , ( λ > 0) ，则得新的可行解 将上式代入 X B = B b-B P m+k x m +k = B b -B Pm +k λ
(１ )确定初始的基本可行解。
1 A= 3
2 4
2 1
1 0
0 8 b= 1 7
1 B = (P4 P5 )= 0
( I ,B
单位 向量即可。
-1
N , B -1 b )
0 ，基变量 x 4 ,x 5 ，非基变量 x 1 ,x 2 , x 3 。 1 x1 x 1 0 1 2 2 C B =(-1,1) 8 X B = 4 ,X N = ,N= 3 4 1 , C =(5,2,3) ,b= 7 x 2 ,B= 0 1 N x5 x 3
-1 若某 个基本可行解所对应的 检验向量σ N =C N -C B B N ≤ 0 ，
则这个基本可行解就是最优。
进基
定理 2：无穷多最优解 判别定理 一个基本可行解， 所对应的检 验向量 B −1 b 是 若 X= 0
Ø 再从 原 来 的基变量中 确 定一个 换出变量， 使它从 基变量变 成 非基变量 （将 它的 值从正值减至零）。 离基
n判断现行的基本可行解是否最优
假 如 已求得 一个基本可行解 B b X= 0
−1
X B = B - 1 b -B - 1 N X
N
代入目标函 数，使目标函数用非基变量表示， 即：
将这 一基本可行解代入目标函数，可求 得相应的目标函数值
B −1b -1 Z=CX=(C B C N ) =C B B b 0
n
确定初始的基本可行解