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

一、利用MATLAB软件中的linprog命令求解


格式为：x=linprog(f,A,b)
[x,fval]=linprog(f,A,b)
格式为：x=linprog(f,A,b,Ae
0
0
4
4
0
1
0
1
0
3
5
1
2
0
0
1
8
0
-2
-5
0
0
0
0
基变量下标
增广系数矩阵
目标函数的系数的相反数
标准线性规划问题要求输入的数据:去掉上表最左边的一列
用分支定界法求解整数规划问题 [书P120 T1（1）]
解：原问题记为A，将该问题进行松弛，得到问题B：
松弛问题B的最优解： （， ）
问题B的最优解不是整数解，对该问题关于x1进行分支：
B1的最优解为: (2,4/3)
最优值为12
B2的可行解域为空集
对问题B1关于x2进行分支：
B11的最优解为: (2,1)
最优值为11
B12的最优解为: (1,2)
最优值为10
该整数线性规划问题的最优解就是（2，1），最优值是11
用分支定界法求解整数规划问题 [书P120 T1（3）]
解：原问题记为A，将该问题进行松弛，得到问题B：
松弛问题B的最优解： （， 0） 最优值96
问题B的最优解不是整数解，对该问题关于x1进行分支：
B1的最优解为: (4，1)
最优值为90
B2的可行解域为空集
该整数线性规划问题的最优解就是（4，1），最优值是90
用割平面法求解整数线性规划问题 [P120 T2（1）]
解：原问题记为A，将其松弛得到问题B：
用对偶单纯形法求得最优解为（，），，最后一张单纯形表为
x1
x2
x3
x4
x5
b
x3
0
0
1

-

x2
0
1
0
-


x1
1
0
0

-

S
0
0
0


-
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
-
用对偶单纯形法求得最优解为（，），，最优解不是整数解。
最后一张单纯形表为：
将新约束条件加入到原规划中，得到新的规划问题：
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
根据第四行得到新约束条件：
将新约束条件加入到规划中，得到新的规划问题：
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
用对偶单纯形法求解得到：
1
2
3
4
5
6
7
b
3
0
0
1
0
0
-5/2
2/3
5
2
0
1
0
0
0
1/2
-1/3
1
1
1
0
0
0
0
-1
1/3
2
5
0
0
0
0
1
-2
1/3
1
4
0
0
0
1
0
1
-1
1
0
0
0
0
0
0
3/2
1/3
-13
最优解为（2，1），最优值为13. 最优解为整数解，故整数规划问题的最优解就是（2，1），最优值为13
运输问题的初始调运方案的编制
:xiqikek