最优化方法--之单纯形法.ppt

文档介绍：最优化方法 Optimization第五讲
第三章 单纯形法
主要内容 (分2讲)
单纯形法
两阶段法
退化情形
处理方法: Bland法则
修正单纯形法
线性规划的最优性条件
单纯形法 0 -1/2 -1/2
13/2
5/2
1/2
-3/2
x1
x2
x5
1 0 -5 2 0
0 1 -3 1 0
0 0 2 -1 1
0 0 1 -1 0
4
1
1
-1
１
２
x1 x2 x3 x4 x5
x4
x5
1 1 3 1 0
1 4 -1 0 1
-2 -1 1 0 0
6
4
0
x3
x1
0 -1 1 1/3 -1/3
1 3 0 1/3 2/3
0 6 0 1/3 5/3
2/3
14/3
26/3
x4
x1
0 -3 3 1 -1
1 4 -1 0 1
0 7 -1 0 2
2
4
8
１
３
单纯形法的进一步探讨
无界解
O
z→-∞
结论：若zj-cj>0,对应的系数列向量≤0，则该LP存在无界解。
x1 x2 x3 x4
-3 1 0 1
-2 0 1 1
11 0 0 -3
12
6
4
x3
x2
-2
-3
1 -1 1 0
-3 1 0 1
x3
x4
2
4
2 3 0 0
0
1
无限多个解
x
1
x
2
l
2
l
1
O
A
B
C
x1 x2 x3 x4
2 7 1 0
7 2 0 1
4 14 0 0
x3
x4
21
21
0
0 1 7/45 -2/45
1 0 -2/45 7/45
0 0 -2 0
x2
x1
7/3
7/3
-42
2/7 1 1/7 0
45/7 0 -2/7 1
0 0 -2 0
x2
x4
3
15
-42
7
45/7
结论：若某个非基变量的检验数为零，则该LP存在多个最优解。
课外练****br/>第六讲 单纯形法之完善
两阶段法
xa的每个重量称为人工变量.
两阶段法
第1阶段:用单纯形法把人工变量变为非基变量，
求出原问题的一个基可行解。
方法：求解下列模型
基
变
量
第2阶段: 从得到的基本可行解动身,
用单纯形法求(L)的最优解.
x1 x2 x3 x4 x5 x6 x7
1 1 -1 0 0 1 0
-1 1 0 -1 0 0 1
0 2 -1