运筹学 (单纯形法原理)

n
m
xn i bi aij x j
j 1
n
（i 1, 2,L , m）
Z 0 cn i bi
i 1 m
cni bi c j x j cni aij x j
i 1 j 1 i 1 j 1
m
n
m
n
z j cn i aij
i 1
求解步骤
（1）化为标准型 max z 2 x1 3 x2
12 2 x1 2 x2 x3 4 x x4 16 1 5 x2 x5 15 x j 0 j 1, 2, L ， 5 （2）找一个初始基本可行解X（0）
2 2 1 0 0 A 4 0 0 1 0 0 5 0 0 1
2x1 +2x2 + x3 = 12 4x1 + x4 = 16 5x2 + x5 = 15
x3 = 12 –2x1 – 2x2 x4= 16 – 4x1 x5 = 15 – 5x2
将x1 = 0， x2 = θ代入上面约束方程，为了让θ取尽可能大的值，同时 又要考虑到x3 、 x4 、 x5必须满足非负约束，从而θ的值应满足：
移项后得到： x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5
将上式代入目标函数，得目标函数用非基变量x1 、 x5表示的表达式
z =9+2x1 – 3/5x5 由于非基变量x1的系数是正数，如果把非基变量转换为基变量，则 会使目标函数的值增加。可见X （1）不是最优解。 （6）第二次迭代 和第一次迭代同样的道理，应选取非基变量x1使它成为基变量，而且 让它取尽可能大的值，同时， x5仍作为非基变量取值为零。从原来的基 变量x2 、 x3 、 x4中选出一个作为非基变量。 x1的取值也按同样的方法确 定： 将x1 = θ ， x5 = 0代入：
（4）第一次迭代。 每一次迭代，得到一个新的基本可行解。因此，哪些变量作为 基变量，哪些非基变量，就要发生变化。 由于目标函数中x2的系数大于x1的系数，因此，可以选择x2使它 作为基变量，而且让它取尽可能大的值，同时， x1仍作为非基变量 取值为零。从原来的基变量x3 、 x4 、 x5中选出一个作为非基变量。 x2的取值不能任意地增加，它要受到约束方程的限制：
b1 M M M 0 .1L bi M M M 0 0L 1 bm
表格单纯形法
max Z c1 x1 c2 x2 cn xn cn1 xn1 cnm xnm
标准型：
a11 x1 a12 x 2 a1n x n x n 1 b1 a x a x a x x b 21 1 22 2 2n n n2 2 s.t. a x a x a x x m2 2 mn n n m bm m1 1 x1 , x 2 , , x n , x n 1 , , x n m 0
m
cni bi (c j cni aij ) x j
i 1 j 1 i 1
m
n
m
j cj zj
n j 1
Z Z 0 (c j z j ) x j Z 0 j x j
j 1
n
4.判断最优；
最优性判别定理：若
X0 (0, 0, L , 0, b 1, b 2 ,L , b m)
5.没有有限最优解的判断；
无最优解判别定理：若
,L , bm ) X (0) (0,0,L ,0, b1, b2 是对应于B的基本可行解， 非基变量x k的检验数k >0 , 且对于i=1,2,……,m 均有aik ≤0, 则原问题没有有限最优解。
该证明留作课后练习
6.改进目标
若k >0，则选xk进基; 用最小比值法确定xk的最大值θ， 使基变量xl取0值，其它基变量非负；
单纯形法一般步骤
1.初始基本可行解的确定（观察法）；
n
a11 x1 a12 x2 L a1n xn xn 1 b1 j 1 a x a x L a x x b n 21 1 22 2 2n n n2 2 x j p j b s . t . M M M s.t. j 1 a x a x L a x x b x 0 j 1, 2, L , n mn n nm m j m1 1 m 2 2 x 1 , x2 , L , xn m 0
max Z c j x j
max Z c j x j
j 1
n
nm
j n 1
0x
j
基
1 0 B ( pn 1 , pn 2 , L , pn m ) M 0
0 L 1 L M 0 L
0 0 M 1
基本可行解
X (0,0,L ,0, b1, b2 ,L , bm )
alj alk aik alj alk
aij aij
L a1 k L a1 n a12 a11 M M M M ai1 L ain ai2 L aik M M M M a a L a L a mk mn m1 m 2
1 0L 0
x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5
x3 = 6 – 2 θ ≥0 x4 = 16 – 4 θ ≥0 x2 = 3 ≥0
即：
x1 = θ =min{6/2，16 /4 ，~}=3 相应地有：
x3 = 6 – 2 × 3 =0 x4 = 16 – 4 × 3=4 x2 = 3
单纯形法的计算步骤
如何改善？
• 单纯形法的思路
如何判断没有有限最优解？
找出一个初始可行解
是否最优 循 环 否
是
最优解 结束
转移到另一个基本可行解 （找出更大的目标函数值） 核心是：变量迭代
线性规划问题的代数运算形式
例：用单纯形法的代数运算形式求解下列线性规划问题
max z 2 x1 3 x2 2 x1 2 x2 12 4 x 16 1 5 x2 15 x1 0、x2 0
1 P3 0 0 0 P4 1 0
0 P5 0 1
B0 P3
P4
1 0 0 P5 0 1 0 0 0 1
B0为一个可行基， x3 、 x4 、 x5为关于可行基B0的基变量， x1 、 x2 为关于可行基B0的非基变量，为求初始基本可行解，令非基变 量x1 = x2 =0。从而有x3 =12， x4 =16， x5 =15，于是得到初始基本 可行解：
xni bi aij x j
j 1
n
（i 1, 2,L , m）
3.代入目标消去基变量，得到非基变量xj的检验数 j
Z c j x j cni xni
j 1 i 1
n Z c j x j cni b a x i ij j j 1 i 1 j 1 n m
总 结
通过ຫໍສະໝຸດ Baidu上例题的分析，可以归纳出单纯形法的步骤：
（1）建立实际问题的线性规划数学模型；
（2）把一般的线性规划问题化为标准型；
（3）确定初始基本可行解；
（4）检验所得到的基本可行解是否为最优解； （5）迭代，求得新的基本可行解。 单纯形法的三个关键部分： （1）初始基本可行解的确定； （2）最优性检验； （3）如何进行迭代: 确定入基变量,出基变量
xk 0 xni bi aik
i 1, 2,L , m
bi bl min aik 0 aik alk
即xl出基，换基过程 若θ不存在, 则Z→∞，没有有限最优解。
7.主元变换（枢变换或旋转变换）
xk进基， xl出基，解出新的基变量
alj
x1
+ 1/2 x3 – 1/5x5 = 3 – 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3
移项后得到： x1 = 3 – 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 – 4/5x5 x2 = 3 –1/5 x5 将上式代入目标函数，得目标函数用非基变量x3 、 x5表示的表达式 z =15 – x3 – 1/5x5 这时,目标函数中非基变量的系数都不大于零，可见目标函数的值不 可能再继续增大,目标函数已经取得最大值15 ，故为X （2）最优解。
2.从约束中解出基变量；
max Z c j x j
j 1 n nm
j n 1
0x
j
a11 x1 a12 x2 L a1n xn xn 1 b1 a x a x L a x x b 21 1 22 2 2n n n2 2 s.t. M M M a x a x L a x x b mn n nm m m1 1 m 2 2 x 1 , x2 , L , xn m 0
复习 由图解法得到的启示：
1.求解线性规划问题时，解的情况有：唯一解；无穷多最优 解；无界解；无可行解。 2.若线性规划问题的可行域存在，则可行域是一个凸集。 3.若线性规划问题的最优解存在，则最优解或最优解之一 （有无穷多最优解）一定是可行域的凸集的某个顶点。 4.解题思路是，先找出凸集的任一顶点，计算在顶点处的目标 函数值。比较周围相邻顶点的目标函数值是否比这个值大， 如果为否，则该顶点就是最优解的点或最优解的点之一，否 则转到比这个点的目标函数值更大的另一顶点，重复上述过 程，一直到找出使目标函数值达到最大的顶点为止。
是对应于B的基本可行解， j是用非基变量表示目标函数的表达 式 中非基变量xj的检验数，若对于一 切非基变量的角指数j 均有j ≤0 则当前基本可行解为最优解。 对于任意可行解X，Z Z 0 j x j Z 0
j 1 n
对于基本可行解X0， 无穷多最优解的判定?
Z Z0
若对于一 切非基变量的角指数j均有j ≤0, 并且存在一个j =0, 则线性规划问题有无穷多最优解
X （1） =（0，3，6，16，0） T
其对应的目标函数值：
z1=2×0+3×3=9 （5）检验X （1） 是否为最优解 将约束方程组改为用非基变量x1 、 x5来表示基变量x2、 x3 、 x4的表达 式。可用高斯消去法得到： 2x1 4x1 + x3 x2 – 2 /5x5 = 6 + x4 = 16 + 1 /5 x5 = 3
可见，从原来的基变量x2 、 x3 、 x4中选出x3作为非基变量，得第二次 迭代后的基本可行解：
X （2） =（3，3，0，4，0） T
其对应的目标函数值：
z1=2×3+3×3=15
（7）检验X （2） 是否为最优解
将约束方程组改为用非基变量x3 、 x5来表示基变量x1、 x2 、 x4的表达 式。可用高斯消去法得到：
X （0） =（0，0，12，16，15） T
其对应的目标函数值 z0=2×0+3×0=0 （3）检验X（0）是否为最优解。由目标函数的表达式： z =2x1 +3x2 可知，非基变量x1 和 x2 的系数为正，如果把非基变量x1 或x2转换
为基变量，则会使目标函数的值增加。可见 X（0）不是最优解
x3 = 12 – 2 θ ≥0 x4 = 16 ≥0 x5 = 15 – 5 θ ≥0 x2 = θ =min{12/2，~，15 /5}=3 相应地有： x3 = 12 – 2 × 3=6 x4 = 16 x5 = 15 – 5 × 3=0
即：
可见，从原来的基变量x3 、 x4 、 x5中选出x5作为非基变量，得第一次 迭代后的基本可行解：