运筹学基础线性规划.ppt

运筹学基础线性规划
第一页，课件共39页
另例：
0
0
0
-3
-4
12
-1
0
2
3
16
0
-1
4
2
x1 　x2 　x3 x4 b
问题：无标准的初始可行基，如何利用单纯形法求解
化为标准形
不是标准的初始可行基
第二页，课件共39页
三、人工变量问题
用单纯形法解题时，需要有一个单位矩阵作为初始基。
当约束条件都是“≤”时，加入松弛变量就形成了初始基。
但如果存在“≥”或“＝”型的约束，就没有现成的单位矩阵。
采用人造基的办法：人为构造单位矩阵
处理方法有两种：
大M 法
两阶段法
第三页，课件共39页
（一）大M法
maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1 , x2 , x3 ≥0
.
没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。
maxZ= 3x1 - x2 -2 x3 -M x4 -M x5
3x1 + 2 x2 -3 x3 + x4 =6
x1 - 2 x2 + x3 + x5 =4
x1 , x2 , x3 , x4 , x5 ≥0
人工变量最终必须等于0才能保持原问题性质不变。
为保证人工变量为0，在目标函数中令其系数为-M。
M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
第四页，课件共39页
大M法求解
按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下：
例如 maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1 , x2 , x3 ≥0
.
maxZ= 3x1 - x2 -2 x3 -M x4 -M x5
3x1 + 2 x2 -3 x3 + x4 =6
x1 - 2 x2 + x3 + x5 =4
x1 , x2 , x3 , x4 , x5 ≥0
第五页，课件共39页
初始单纯形表为：
0
-M
-2
-1
3
4
1
1
-2
1
6
0
-3
2
3
-M
0
1
～
10M
0
-2-2M
-1
3+4M
4
1
1
-2
1
6
0
-3
2
3
0
0
1
3+3M -1+2M -2-3M 0 -M 6M
所以，此时求解不是最优解，需要换基。
x1 　 x2 　 x3 x4 x5 b
10M
0
-2-2M
-1
3+4M
4
1
1
-2
1
6
0
-3
2
3
0
0
1
3+4M -1 -2-2M 0 0 10M
～
第六页，课件共39页
10M
0
-2-2M
-1
3+4M
4
1
1
-2
1
6
0
-3
2
3
0
0
1
～
-6+2M
0
1+2M
-3-8M/3
0
2
1
2
-8/3
0
2
0
-1
2/3
1
-1-4M/3
-1/3
1/3