解线性规划问题时可能出现的几种结果精选文档.ppt

《解线性规划问题时可能出现的几种结果精选文档.ppt》由会员分享，可在线阅读，更多相关《解线性规划问题时可能出现的几种结果精选文档.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、解线性规划问题时可能出现的几种结果本讲稿第一页，共四十一页首先，给出一个线性规划问题的模型：首先，给出一个线性规划问题的模型：目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0下面，我们采用最直观、简单的图解法求解：下面，我们采用最直观、简单的图解法求解：理论性问题研究理论性问题研究本讲稿第二页，共四十一页u图解法图解法 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16

2、 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12本讲稿第三页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84

3、x1=164 x2=12可行域u图解法图解法本讲稿第四页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=126 6=2=2x x1 1+3+3x x2 20 0=2=2x x1 1+3+3x x2 2u图解法图解法本讲稿第五页，共四十一页

4、目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12最优解：（4，2）x1+2x2=8 4x1=16A(4，2)u图解法图解法本讲稿第六页，共四十一页上述线性规划问题的模型的最优解出现在可行域的一个顶点处，此时线性规划问题有唯一最优解。zzzzzzzzz

5、总结理论性问题研究理论性问题研究本讲稿第七页，共四十一页1、若将上面题目中的目标函数改为：、若将上面题目中的目标函数改为：Max Max Z Z=2=2x x1 1+4+4x x2 22 2 2 2、将约束条件、将约束条件 x x1 1+2+2x x2 2 8 8 改为：改为：改为：改为：2 2 x x1 1+3+3x x2 2 1212此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化理论性问题研究理论性问题研究本讲稿第八页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x

6、1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0理论性问题研究理论性问题研究第一种情况：第一种情况：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+4+4x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0改变目标函数改变目标函数改变目标函数改变目标函数此时线性规

7、划问题模型为：同样采用图解法，请看下面图形：本讲稿第九页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+4+4x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12沿着箭头的方向画平行线最后，平行线与直线：x1+2x2=8无穷多最优解AB第一种情况：第一种情况：0 0=2=2x x1 1+4+4

8、x x2 2本讲稿第十页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0理论性问题研究理论性问题研究第二种情况：第二种情况：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 2 2x x1 1+3+3x x2 2 12 12 4 4x x1 1 16 16 4 4x x2

9、 2 12 12 x x1 1、x x2 2 0 0 0 0改变约束条件改变约束条件改变约束条件改变约束条件此时线性规划问题模型为：同样采用图解法，请看下面图形：本讲稿第十一页，共四十一页第二种情况：第二种情况：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 2 2 x x1 1+3+3x x2 2 12 12 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 09 8 7 6 5 4 3 2 1 0|123456789x12x1+3x2=124x1=164

10、 x2=12x x2 20 0=2=2x x1 1+3+3x x2 2最后，平行线与直线：2x1+3x2=12无穷多最优解AB本讲稿第十二页，共四十一页事实上，阴影部分构成一个凸多边事实上，阴影部分构成一个凸多边形，其中形，其中A和和B分别是两个极点，分别是两个极点，A和和B就是典型的两个最优解，而连就是典型的两个最优解，而连接两点之间的线段上的每一个坐标接两点之间的线段上的每一个坐标值，都是原问题的一个最优解。值，都是原问题的一个最优解。理论性问题研究理论性问题研究本讲稿第十三页，共四十一页思考思考当我们把原约束条件变为：当我们把原约束条件变为：4 4x x1 1 16 16 则最优解又将发

11、生何改变则最优解又将发生何改变则最优解又将发生何改变则最优解又将发生何改变 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 4 4x x1 1 16 16 x x1 1、x x2 2 0 0 0 0理论性问题研究理论性问题研究本讲稿第十四页，共四十一页x x2 29 8 7 6 5 4 3 2 1 0|123456789x1 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 4 4x x1 1 16 16 x x1 1、x x2

12、2 0 0 0 0|123456789x14x1=16可行域为图中阴影处向上延伸，看图可知：可行域无界。为求最优解做作等值线：Z Z=2=2x x1 1+3+3x x2 2，当Z值由小变大时，等值线平行向上移动，无论Z值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。u图解法图解法本讲稿第十五页，共四十一页当我们在原线性规划模型中增加一个约束条件：x x1+1+x x2 2 9 9思考：这时最优解又将作何改变思考：这时最优解又将作何改变思考：这时最优

13、解又将作何改变思考：这时最优解又将作何改变举一反三线性规划模型：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1+x x2 2 9 9 x x1 1、x x2 2 0 0 0 0理论性问题研究理论性问题研究本讲稿第十六页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2

14、 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1+x x2 2 9 9 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12x x1 1+x x2 2=9=9由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。u图解法图解法本讲稿第十七页，共四十一页理论性问题研究理论性问题研究zzzzzzzzz总结总结线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果无穷多最优解无界解无可行解唯一最优解注意：在应用

15、上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。本讲稿第十八页，共四十一页在应用上，当线性在应用上，当线性规划问题出现无界规划问题出现无界解和无可行解两种解和无可行解两种情形时，说明线性情形时，说明线性规划问题的模型有规划问题的模型有问题。问题。理论性问题研究理论性问题研究本讲稿第十九页，共四十一页原线性规划模型目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x

16、 x2 2 0 0 0 0 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 4 4x x1 1 16 16 x x1 1、x x2 2 0 0 0 0无界解时的线性规划模型无界解时的线性规划模型 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1+x x2 2 9 9 x x1 1、x x2 2 0 0 0 0无可

17、行解的线性规划模型无可行解的线性规划模型理论性问题研究理论性问题研究对比对比本讲稿第二十页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12最优解：（4，2）x1+2x2=8 4x1=16A(4，2)、唯一最优解、唯一最优解本讲稿第二十一

18、页，共四十一页x x2 29 8 7 6 5 4 3 2 1 0|123456789x1 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 4 4x x1 1 16 16 x x1 1、x x2 2 0 0 0 0|123456789x14x1=16可行域为图中阴影处向上延伸，看图可知：可行域无界。为求最优解做作等值线：Z Z=2=2x x1 1+3+3x x2 2，当Z值由小变大时，等值线平行向上移动，无论Z值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无

19、法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。、无界解、无界解本讲稿第二十二页，共四十一页 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1+x x2 2 9 9 x x1 1、x x2 2 0 0 0 0 x x2 29 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2=84x1=164 x2=12x x1 1+x x2 2=

20、9=9由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。、无可行解、无可行解本讲稿第二十三页，共四十一页实践性实践性问题研究问题研究通过对比分析，我们得出：通过对比分析，我们得出：a、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，增加恰当的约束条件，使出现有界的可行域，即可解决问题；增加恰当的约束条件，使出现有界的可行域，即可解决问题；b、出现无可行解，是因为线性规划模型中的约束条件相互冲、出现无可行解，是因为线性规划模型中的约束条件相互冲突，突，需要修改模型后再进行求解。需要修

21、改模型后再进行求解。结论本讲稿第二十四页，共四十一页实践性问题研究假设在上题(P245.14)中该公司的4位营销总监月薪分别是2.5,2.1,1.8,1.6万元，若该公司还想将业务范围扩大到西北和西南，现在公司想在6个区中筹建销售分公司，考虑到甲业务最熟悉，他最多可以负责三个区的建设，乙的业务也比较熟练，他最多可以负责两个区的分公司的建设。为了避免多头领导，每个地区只派一个营销总监进行筹建工作。表7-21是各位营销总监在不同地区建分公司预计所用时间(单位：月)。问：如何指派各位营销总监区建设各区的分公司才能使总工资成本最低？建立数学模型并进行数值求解以及Excel软件求解。课本246页 习题

22、第15题所用筹建时间1华中2华南3华北4东北5西北6西南月薪(万元)1甲343.56482.52乙3.5438672.13丙45.556491.84丁567557.51.6地区地区人员人员本讲稿第二十五页，共四十一页实践性问题研究实践性问题研究建立数学模型，进行数值求解建立数学模型，进行数值求解 解解：若若用用aij表表示示营营销销总总监监i在在地地区区j筹筹建建分分公公司司所所用用的的时时间间，用用yi表表示示营营销销总总监监i的月薪。的月薪。引入引入0-1变量变量xij，令令Xij=1 ，营销总监营销总监i被指派被指派到地区到地区j筹建分公司筹建分公司0 ，营销总监营销总监i没被指派没被指

23、派到地区到地区j筹建分公司筹建分公司便可得到如下的便可得到如下的0-1整数规划模型整数规划模型s.t本讲稿第二十六页，共四十一页1华中2华南3华北4东北5西北6西南71甲343.564801甲343.564801甲343.564802乙3.5438670解：解：由题意，甲最多可以负责三个区的建设，乙最多可以负责两个区的分公司的建设，丙、丁分别可以负责一个区的分公司的建设。因此将4人看作7人，在虚设1个地区，化为平衡指派问题。实践性问题研究实践性问题研究地区地区人员人员2乙3.54386703丙45.5564904丁567557.50本讲稿第二十七页，共四十一页利用匈牙利法解：按第一步的（1）和

24、（2）先让系数矩阵减去每行的最小元素，然后再减去每列的最小元素。343.56480343.56480343.564803.54386703.543867045.556490567557.50000.51010000.51010000.510100.50032000.500320011.521020224010.50本讲稿第二十八页，共四十一页然后进行试指派，以寻求最优解然后进行试指派，以寻求最优解从只有一个从只有一个0元素的列元素的列(行行)开始，给这个开始，给这个0元素加圈，记作元素加圈，记作 。这表示对这行所代表的。这表示对这行所代表的人只有一种任务可指派。然后划去人只有一种任务可指派。然

25、后划去 所在行的其他所在行的其他0元素，记作元素，记作 ，,这表示这行所代表这表示这行所代表的人已指派任务，不必再考虑其他任务了。的人已指派任务，不必再考虑其他任务了。000.51010000.51010000.510100.50032000.500320011.521020224010.50本讲稿第二十九页，共四十一页仍没有划圈的仍没有划圈的0元素，且同行的元素，且同行的0元素至少有两个（表示对这人可以从两项任务中元素至少有两个（表示对这人可以从两项任务中指派其一），从剩有指派其一），从剩有0元素最少的行开始，比较这行各元素最少的行开始，比较这行各0元素所在列中元素所在列中0元素的数目，元素

26、的数目，对对0元素少的那列的这个元素少的那列的这个0元素加圈（表示选择性多的应该先满足选择性少的），然元素加圈（表示选择性多的应该先满足选择性少的），然后划掉同行同列的其他后划掉同行同列的其他0元素。元素。000.51010000.51010000.510100.50032000.500320011.521020224010.50本讲稿第三十页，共四十一页反复进行上一步反复进行上一步000.5110000.5110000.51100.50032000.500320011.521222410.5实践性问题研究实践性问题研究本讲稿第三十一页，共四十一页继续反复进行继续反复进行000.5110000

27、.5110000.51100.5320.50320011.521222410.5实践性问题研究实践性问题研究本讲稿第三十二页，共四十一页000.51010000.5110000.51100.5320.53211.521222410.5实践性问题研究实践性问题研究本讲稿第三十三页，共四十一页0.51100.511000.51100.5320.53211.521222410.5实践性问题研究实践性问题研究本讲稿第三十四页，共四十一页0.5110.5110.51100.5320.53211.521222410.5实践性问题研究实践性问题研究本讲稿第三十五页，共四十一页此时，此时，k=n=7,所以最优

28、解为所以最优解为:100000001000000000001(xij)=0010000000001000001000001000实践性问题研究实践性问题研究本讲稿第三十六页，共四十一页营销总监人员甲负责的地区是华中和华南地区，总共时间营销总监人员甲负责的地区是华中和华南地区，总共时间为为7个月；人员乙负责的地区是华北和西南地区，总共时个月；人员乙负责的地区是华北和西南地区，总共时间为间为10个月；人员丙负责的地区是西北地区，总共时间为个月；人员丙负责的地区是西北地区，总共时间为4个个月；人员丁负责的地区是东北地区，总共时间为月；人员丁负责的地区是东北地区，总共时间为5个月。个月。所需所需总工资

29、成本最低为：总工资成本最低为：Z=72.5+10 2.1+4 1.8+5 1.6=53.7（万元）（万元）100000001000000000001(xij)=0010000000001000001000001000本讲稿第三十七页，共四十一页实践性问题研究实践性问题研究用用Excel软件求解软件求解 在在Excel中建立该问题的数学模型中建立该问题的数学模型H11=SUM(B11:G11)H11=SUM(B11:G11)，H12=SUM(B12:G12)H12=SUM(B12:G12)，H13=SUM(B13:G13)H13=SUM(B13:G13)，H14=SUM(B14:G14)H14=

30、SUM(B14:G14)B15=SUM(B11:B14)B15=SUM(B11:B14)，C15=SUM(C11:C14)C15=SUM(C11:C14)，G15=SUM(G11:G14)G15=SUM(G11:G14)K11=SUMPRODUCT(B3:G3,B11:G11)K11=SUMPRODUCT(B3:G3,B11:G11)，K14=SUMPRODUCT(B6:G6,B14:G14)K14=SUMPRODUCT(B6:G6,B14:G14)B19=SUMPRODUCT(H3:H6,K11:K14)B19=SUMPRODUCT(H3:H6,K11:K14)本讲稿第三十八页，共四十一页实践性问题研究实践性问题研究在在“工具工具”菜单中找到菜单中找到“规划求解规划求解”，单击，单击“规划求解规划求解”。在在“规划求解参数规划求解参数”对话框中，如下图进行设置。对话框中，如下图进行设置。本讲稿第三十九页，共四十一页在在“规划求解参数规划求解参数”对话框中，点击求解。对话框中，点击求解。得到下图所示的最优解得到下图所示的最优解用用Excel的规划求解可知总工资成的规划求解可知总工资成本最低为本最低为53.7万元。万元。本讲稿第四十页，共四十一页本讲稿第四十一页，共四十一页