线性规划问题的求解方法.ppt

线性规划问题的求解方法
第1页，本讲稿共28页
一、利用MATLAB软件中的linprog命令求解


格式为：x=linprog(f,A,b)
[x,fval]=linprog(d
用bland法则求解特殊线性规划问题
dan0-improve
用改进的单纯形法求解线性规划问题
danm
用大M法求解线性规划问题
dan2
用两阶段法求解线性规划问题
第14页，本讲稿共28页
特殊的线性规划问题要求输入的数据（第一张单纯形表，典式）
3
1
0
1
0
0
4
4
0
1
0
1
0
3
5
1
2
0
0
1
8
0
-2
-5
0
0
0
0
基变量下标
增广系数矩阵
目标函数的系数的相反数
标准线性规划问题要求输入的数据:去掉上表最左边的一列
第15页，本讲稿共28页
用分支定界法求解整数规划问题 [书P120 T1（1）]
解：原问题记为A，将该问题进行松弛，得到问题B：
第16页，本讲稿共28页
松弛问题B的最优解： （， ）
问题B的最优解不是整数解，对该问题关于x1进行分支：
B1的最优解为: (2,4/3)
最优值为12
B2的可行解域为空集
第17页，本讲稿共28页
对问题B1关于x2进行分支：
B11的最优解为: (2,1)
最优值为11
B12的最优解为: (1,2)
最优值为10
该整数线性规划问题的最优解就是（2，1），最优值是11
第18页，本讲稿共28页
用分支定界法求解整数规划问题 [书P120 T1（3）]
解：原问题记为A，将该问题进行松弛，得到问题B：
第19页，本讲稿共28页
松弛问题B的最优解： （， 0） 最优值96
问题B的最优解不是整数解，对该问题关于x1进行分支：
B1的最优解为: (4，1)
最优值为90
B2的可行解域为空集
该整数线性规划问题的最优解就是（4，1），最优值是90
第20页，本讲稿共28页
用割平面法求解整数线性规划问题 [P120 T2（1）]
解：原问题记为A，将其松弛得到问题B：
第21页，本讲稿共28页
用对偶单纯形法求得最优解为（，），，最后一张单纯形表为
x1
x2
x3
x4
x5
b
x3
0
0
1

-

x2
0
1
0
-


x1
1
0
0

-

S
0
0
0


-
第22页，本讲稿共28页
x1
x2
x3
x4
x5
x6
b
x3
0
0
1

-
0

x2
0
1
0
-

0

x1
1
0
0

-
0

x6
0
0
0
-
-
1
-
S
0
0
0


0
-
用对偶单纯形法求得最优解为（，），，最优解不是整数解。
最后一张单纯形表为：
将新约束条件加入到原规划中，得到新的规划问题：
第23页，本讲稿共28页
1
2
3
4
5
6
b
3
0
0
1
2/3
0
-11/6
17/3
2
0
1
0
-1/3
0
1/6
2/3
1
1
0
0
1/3
0
-2/3
7/3
5
0
0
0
1/3
1
-5/3
4/3
0
0
0
0
1/3
0
11/6
-38/3
根据第四行得到新约束条件：
将新约束条件加入到规划中，得到新的规划问题：
第24页，本讲稿共28页
1
2
3
4
5
6
7
b
3
0
0
1
2/3
0
-11/6
0
17/3
2
0
1
0
-1/3
0
1/6
0
2/3
1
1
0
0
1/3
0
-2/3
0
7/3
5
0
0
0
1/3
1
-5/3
0
4/3
7
0
0
0
-1
0
-1
1
-1
0
0
0
0
1/3
0
11/6
0
-38/3
用对偶单纯形法求解得到：
第25页，本讲稿共28页
1
2
3
4
5
6
7
b
3
0