§ 单纯形方法
第二章线性规划
§ 线性规划的数学模型
§ 线性规划问题的图解法
§ 线性规划问题的标准形
§ 两阶段法
§ 运输问题的解法
§ 对偶单纯形法
§ 两阶段法
否
初始顶点
转移到新顶点
(目标值下降)
是否最优?
停止迭代
是
初始基本可行解
新的基本可行解
单纯形法的迭代思想:
复习
何时使用两阶段法:
标准形
是典式
初始基本可行解
用单纯形法求解
不是典式
两阶段法
初始基本可行解
例:
标准形
注意:
例:
用两阶段法求解
用单纯形法求解
还有很多标准形不是典式
以为基变量的典式
两阶段法的思想:
两阶段法:
第一阶段:
第二阶段:
求解辅助(LP),得到原(LP)的一个初始基本可行解。
再用单纯形法去求原的最优解。
辅助(LP)与原(LP)解的关系:
例11
辅助(LP):
第一阶段:
求解辅助(LP),得到原(LP)的一个初始基本可行解。
原(LP):
人工变量
2)若,则原(LP)无可行解。
1)若,则可得到原(LP)的一个初始基本可行解。
例11
辅助(LP):
原(LP):
人工变量
反证法:
则有:
辅助(LP)的可行解。
所以原(LP)无可行解。
矛盾。
若原(LP)有可行解
2)若,则原(LP)无可行解。
1 2 3 1 0
4 5 -6 0 1
6
6
单纯形表一
检验数
5 7 -3 0 0
1
辅助(LP):
1
0 0 0 1 1
12
1 2 3 1 0
4 5 -6 0 1
6
6
单纯形表一
检验数
5 7 -3 0 0
1
辅助(LP):
12
运筹学基础 来自淘豆网m.daumloan.com转载请标明出处.
