运筹学基础线性规划.ppt

运筹学基础线性规划
第1页，本讲稿共39页
另例：
0
0
0
-3
-4
12
-1
0
2
3
16
0
-1
4
2
x1 　x2 　x3 x4 b
问题-M-1/2
0
-5/3
0
1
1/2
1
-4/3
0
3
1/2
0
-2/3
1
-M-5/6
-1/6
1/6
～
x2=0, x4=0, x5=0, x1=3, x3=1 ,σj<0，此时求解最优
即X0=(3,0,1,0,0)T时，-Z=-7，最优解 maxZ=7
第7页，本讲稿共39页
试用大M法求解如下线性规划问题的最优解。
划为标准型，并按大M法引入人工变量x4 , x5 的辅助问题如下：
松驰变量
剩余变量
人工变量
惩罚项
第8页，本讲稿共39页
解：
0
-M
0
-1
-1
3
1
1
0
1
0
-2
3
0
0
2
1
-4
11
0
1
1
-2
1
0
0
-1
0
-M
0
1
0
～
4M
0
0
-1+3M
-1+M
3-6M
1
1
0
1
0
-2
3
0
0
2
1
-4
11
0
1
1
-2
1
-M
0
-1
0
0
0
1
0
x1 　 x2 　　x3　 x4　 x5 　 x6 x7 b
x1 　 x2 　　x3　 x4　 x5 　 x6 x7 b
第9页，本讲稿共39页
M+1
-3M+1
0
0
-1+M
1
1
1
0
1
0
-2
1
-2
0
0
1
0
10
-1
1
0
-2
3
-M
0
-1
0
0
0
1
0
2
-M-1
0
0
0
1
1
1
0
1
0
-2
1
-2
0
0
1
0
12
-5
1
0
0
3
-1
0
-1
-2
1-M
0
1
2
-2
-M+23
-1/3
0
0
0
9
-7/3
2/3
1
0
0
1
-2
0
0
1
0
4
-5/3
1/3
0
0
1
-1/3
-4/3
-1
-2/3
1/3-M
4/3
1
2/3
～
～
令x4=0,x5,=0,x6=0,x7,=0, 得x1=4,x2=1,x3=9即X0=(4,1,9,0,0,0,0)T
此时-Z’=-2为最大,则 最优解 minZ=-2
～
第10页，本讲稿共39页
（二）两阶段法
这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。
第一阶段是先求以人工变量等于0为目标的线性规划问题
第二阶段利用已求出的初始基可行解来求原问题最优解。
第11页，本讲稿共39页
试用两阶段法求解如下线性规划问题
解：先划约束条件为标准型
第12页，本讲稿共39页
初等变换
0
-1
0
0
0
0
-W
1
1
0
1
0
-2
0
3
0
0
2
1
-4
0
11
0
1
1
-2
1
0
0
0
-1
0
-1
0
1
0
～
4
0
0
3
1
-6
-W
1
1
0
1
0
-2
0
3
0
0
2
1
-4
0
11
0
1
1
-2
1
0
-1
0
-1
0
0
0
1
0
-Z ’ 　 x1 　 x2 　　x3　 x4 x5 　 x6 x7 b
第13页，本讲稿共39页
～
～
0
-1
0
0
0
0
-W
1
1
0
1
0
-2
0
1
-2
0
0
1
0
0
12
-5
1
0
0
3
0
0
0
-1
-2
-1
0
1
2
1