此文档仅供收集于网络,如有侵权请联系网站删除
基 S X1 X2 S 1 0 -5 X3 0 0 2 X1
0
1
1/2
第二次迭代:调入x2,调出x3 基 S X1 X2 S 1 0 0 X2 0 0 1 X1 0
1
0
?Zmax
x1?150x45002?100?4、本章作业
见本章练习题
3、本章典型例题分析
例:写出下列线性规划问题的对偶问题
maxZ?3x1?x2?4x3?6x1?3x2?5x3?25S?t???3x 1?4x2?5x3?20??xj?0(j?1,2,3)
解:其对偶问题为:
只供学习与交流
X3 0 1 0
X3 5/2 1/2 -1/4
X4 10 -1 1/2
X4 -1/2 3/4
解 4000 200 200
解 4500 100 150
15/2 此文档仅供收集于网络,如有侵权请联系网站删除
minW?25y1?20y2?6y1?3y2?3?3y?4y?1 ?12S?t???5y1?5y2?4??y1,y2?04、本章作业
见本章练习题
二、写出下列线性规划问题的对偶问题:
(1) maxZ?2x1?x2?3x3?x4
s.t. 2x1?x2?3x3??4
x1?x3?x4?1x1?x2?x3?x4?5
x1,x3?0,x2,x4无约束(2) minZ?2x1?2x2?4x3
s.t. 3x1?x2?7x3?3
x1?4x2?6x3?5x2?0,x3?02x1?3x2?5x3?2
管理运筹学复习
一、 考虑下列线性规划(20分) MaxZ=2X1+3X2 2X1+ 2X2+X3=12 X1+2X2 +X4=8
4X1 +X5=16 4X2 +X6=12 Xj≥0(j=1,2,…6) 其最优单纯形表如下: 基变量 X1 X2 X3 X3 0 0 0 1 只供学习与交流
X4 -1 X5 -1/4 X6 0 此文档仅供收集于网络,如有侵权请联系网站删除
X1 4 1 0 0 0 1/4 0 X6 4 0 0 0 -2 1/2 1 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 1)当C2=5时,求新的最优解 2)当b3=4时,求新的最优解
3)当增加一个约束条件2X1+X2≤12,问最优解是否发生变化,如果发生变化求新解?
解当C2=5时 σ4=-5/2
σ5=1/8>0所以最优解发生变化 基变量 X1 X2 X3 X4 X5 X6 0 X3 0 0 0 1 -1 -1/4 0 2 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 5 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -5/2 1/8 0 0 X3 2 0 0 1 -2 0 1/2 2 X1 2 1 0 0 1 0 -1/2 0 X5 8 0 0 0 -4 1 2 5 X2 3 0 1 0 0 0 1/4 σj 0 0 0 -2 0 -1/4 最优解为X1=2,X2=3,Z=19 2)当b3=4时 基变量 X1 X2 X3 X4 X5 X6 0 X3 3 0 0 1 -1 -1/4 0 2 X1 1 1 0 0 0 1/4 0 0 X6 -3 0 0 0 -2 1/2 1 3 X2 5/2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 0 X3 9/2 0 0 1 0 -1/2 1 2 X1 1 1 0 0 0 1/4 0 0 X4 3/2 0 0 0 1 -1/4 -1/2 3 X2 7/4 0 1 0 0 0 1/4 σj 0 0 0 0 -1/2 -3/4 此时最优解为X1=1,X2=7/4,Z=29/4 3)增加一个约束条件
只供学习与交流
此文档仅供收集于网络,如有侵权请联系网站删除
基变量 X1 X2 X3 X3 0 0 0 1 X1 4 1 0 0 X6 4 0 0 0 X2 2 0 1 0 X7 12 2 1 0 σj 0 0 0 X3 0 0 0 1 X1 4 1 0 0 X6 4 0 0 0 X2 2 0 1 0 X7 2 0 0 0 σj 0 0 0 由于X7=2大于0,所以最优解不变
X4 -1 0 -2 1/2 0 -3/2 -1 0 -2 1/2 -1/2 -3/2 X5 -1/4 1/4 1/2 -1/8 0 -1/8 -1/4 1/4 1/2 -1/8 -3/8 -1/8 X6 0 0 1 0 0 0 0 0 1 0 0 0 X7 0 0 0 0 1 0 0 0 0 0 1 0 只供学习与交流