运筹学课件 单纯形法的迭代原理

由于任意系数列向量均可由基向量组线性表示，则非基向 量中的 Pj 用基向量组线性表示为：
Pj a ijPi
i 1
2017/5/5
m

Pj a ijPi 0,
i 1
m
( j m 1,...,n )
12
设有 0，则
( Pj aij Pi ) 0
i 1
只要取
(0) (0) x x min i aij 0 l 为
正，于是非零分量的个数
m
，并可证得
P P2 ... Pl 1 Pl 1 ... Pm , Pj 1
线性无关，所以 X (1) 是新的基可行解。
2017/5/5
a12 a22
a1n a2 n
am 2 amn
1 0 0 0 1 0 0 0 1
9
由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组 基，就可以求出一个基可行解：
X 0,,0, b1,, bm
令：X X (1) (1 ) X ( 2 )
0 1
则AX A(X (1) (1 ) X ( 2 ) ) AX (1) AX ( 2 ) AX ( 2 ) b
X C C 为凸集
引理：线性规划问题的可行解X＝(x1,x2,……xn)为基可行解的充要条件是 X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇 异的）。
11
由构造初始可行基的方法知前m 个基向量恰好是一个单位
阵，所以约束方程组的增广矩阵为
P1 P2 ... Pm Pm1 ... Pj ... Pn b
1 0 ... 0 0 ... 0 1 ... 0 ... ... ... 0 ... 1 a1,m 1 ... ... a1, j ... ... a2,m 1 ... a2, j am,m 1 ... am , j ... a1,n b1 ... a2,n b2 ... ... ... ... am,n bm

单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4

3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1

–P1 , P2 , … , Pm 称为基向量
–与基向量对应的变量称为基变量，记为
XB = ( x1 , x2 , … , xm )T，其余的变量称非基变量，记 为 XN = ( xm+1 , xm+2 , … , xn ) T ，
故有 X = (XB ,XN )T
● 线性规划的基矩阵、基向量、基变量、非基变量
基、可行基、最优基
可行解、基解和基本可行解举例
标准型：
max f ( x) 6 x1 4 x2
2 x1 x2 10
s.t.

x1 x2 8 x2 7
x1 , x2 0
max f (x) 6x1 4x2
2x1 x2 x3 10
x1, x2 , x3 , x3, x4 , x5, x6 0
一、关于标准型解的若干基本概念
线性规划问题标准型的矩阵形式：
Max Z = CX
（a）
s.t. AX=b
（ b）
X 0
（c）
a11 a12 …. a1n
C (c1, c2 , , cn );
X (x1, x2 , , xn )T
做为一个基 （可行基）
基变量 : x3 x4 x5 非基变量: x1 x2
可见，单位矩阵 作为初始可行基， 基变量在目标中 的系数为0
非基 变量
基变量
图中的点 解
x1, x2 x3 =10 x4 =8 x5 =7 O 基可行解
x1, x3 x2 =10 x4 =-2 x1, x4 x2 =8 x3 =2 x1, x5 x2 =7 x3 =3
x5 =-3 x5 =-1 x4 =1
F

总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为0。因为行旳初等变换不能把0变成1。 ③主元素不能为负数。因为用行旳初等变换把负数变成1会 把常数列中相应旳常数变成负数。
16
三、其他解旳情况 1、无穷多种解 例2 解LP问题：
min Z x1 2 x2 x3 0 x4 0 x5
xx51
1 2c 5 3c
其中c是满足非负性旳任意常数。
21
再由
x1,
x5
旳非负性，知：
x1 x2
1 2c c
0 0
x5 5 3c 0
解出 0 c 5 3
最优解为：
(2c 1, c,0,0,5 3c)T （其中0 c 5 ）
3
最优值为：max S 1.
22
2、无最优解旳两种情况：
相应地，将 X 0代入目的函数得 Z ( X 0 ) 0
从数学角度看，若让非基变量 x1, x2 取值从零增长，
6
min Z 2x1 x2 0x3 0x4 0x5
相应旳目旳函数值Z也将随之降低。所以有可能找到一种 新旳基本可行解，使其目旳函数值有所改善。即进行基变
换，换一种与它相邻旳基。再注意到 x1 前旳系数－2比 x2
x3
6 x1 x1
2x2 x2
x4 x5
xi 0
i 1,,5
15 24 5
目前可行基{ x3, x4 , x5 }所相应旳基本可行解
X 0 (0,0,15,24,5)T
(相应可行域旳 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0
意味着该厂不安排生产，所以没有利润。
2