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

解线性规划问题时可能出现的几种结果第1页，此课件共41页哦首先，给出一个线性规划问题的模型：首先，给出一个线性规划问题的模型：目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0下面，我们采用最直观、简单的图解法求解：下面，我们采用最直观、简单的图解法求解：理论性问题研究理论性问题研究第2页，此课件共41页哦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=12第3页，此课件共41页哦 目标函数目标函数目标函数目标函数 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可行域u图解法图解法第4页，此课件共41页哦 目标函数目标函数目标函数目标函数 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图解法图解法第5页，此课件共41页哦 目标函数目标函数目标函数目标函数 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图解法图解法第6页，此课件共41页哦上述线性规划问题的模型的最优解出现在可行域的一个顶点处，此时线性规划问题有唯一最优解。zzzzzzzzz总结理论性问题研究理论性问题研究第7页，此课件共41页哦1、若将上面题目中的目标函数改为：、若将上面题目中的目标函数改为：Max Max Z Z=2=2x x1 1+4+4x x2 22 2、将约束条件、将约束条件 x x1 1+2+2x x2 2 8 8 改为：改为：改为：改为：2 2 x x1 1+3+3x x2 2 1212此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化此时线性规划问题的最优解将有何变化理论性问题研究理论性问题研究第8页，此课件共41页哦 目标函数目标函数目标函数目标函数 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+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改变目标函数改变目标函数改变目标函数改变目标函数此时线性规划问题模型为：同样采用图解法，请看下面图形：第9页，此课件共41页哦 目标函数目标函数目标函数目标函数 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+4x x2 2第10页，此课件共41页哦 目标函数目标函数目标函数目标函数 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 2 12 12 x x1 1、x x2 2 0 0 0 0改变约束条件改变约束条件改变约束条件改变约束条件此时线性规划问题模型为：同样采用图解法，请看下面图形：第11页，此课件共41页哦第二种情况：第二种情况：目标函数目标函数目标函数目标函数 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 x2=12x x2 20 0=2=2x x1 1+3+3x x2 2最后，平行线与直线：2x1+3x2=12无穷多最优解AB第12页，此课件共41页哦事实上，阴影部分构成一个凸多边形，事实上，阴影部分构成一个凸多边形，其中其中A和和B分别是两个极点，分别是两个极点，A和和B就是典型的两个最优解，而连接两就是典型的两个最优解，而连接两点之间的线段上的每一个坐标值，都点之间的线段上的每一个坐标值，都是原问题的一个最优解。是原问题的一个最优解。理论性问题研究理论性问题研究第13页，此课件共41页哦思考思考当我们把原约束条件变为：当我们把原约束条件变为：4 4x x1 1 16 16 则最优解又将发生何改变则最优解又将发生何改变则最优解又将发生何改变则最优解又将发生何改变 目标函数目标函数目标函数目标函数 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理论性问题研究理论性问题研究第14页，此课件共41页哦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值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。u图解法图解法第15页，此课件共41页哦当我们在原线性规划模型中增加一个约束条件：x x1+1+x x2 2 9 9思考：这时最优解又将作何改变思考：这时最优解又将作何改变思考：这时最优解又将作何改变思考：这时最优解又将作何改变举一反三线性规划模型：目标函数目标函数目标函数目标函数 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理论性问题研究理论性问题研究第16页，此课件共41页哦 目标函数目标函数目标函数目标函数 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=9=9由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。u图解法图解法第17页，此课件共41页哦理论性问题研究理论性问题研究zzzzzzzzz总结总结线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果无穷多最优解无界解无可行解唯一最优解注意：在应用上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。第18页，此课件共41页哦在应用上，当线性在应用上，当线性规划问题出现无界规划问题出现无界解和无可行解两种解和无可行解两种情形时，说明线性情形时，说明线性规划问题的模型有规划问题的模型有问题。问题。理论性问题研究理论性问题研究第19页，此课件共41页哦原线性规划模型目标函数目标函数目标函数目标函数 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 约束条件约束条件约束条件约束条件 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无可行解的线性规划模型无可行解的线性规划模型理论性问题研究理论性问题研究对比对比第20页，此课件共41页哦 目标函数目标函数目标函数目标函数 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)、唯一最优解、唯一最优解第21页，此课件共41页哦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值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。、无界解、无界解第22页，此课件共41页哦 目标函数目标函数目标函数目标函数 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=9=9由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。、无可行解、无可行解第23页，此课件共41页哦实践性实践性问题研究问题研究通过对比分析，我们得出：通过对比分析，我们得出：a、出现无界解，是由于线性规划模型中缺乏必要的约束条件，、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，增加恰当的约束条件，使出现有界的可行域，即可解决问因此，增加恰当的约束条件，使出现有界的可行域，即可解决问题；题；b、出现无可行解，是因为线性规划模型中的约束条件相互冲、出现无可行解，是因为线性规划模型中的约束条件相互冲突，突，需要修改模型后再进行求解。需要修改模型后再进行求解。结论第24页，此课件共41页哦实践性问题研究假设在上题(P245.14)中该公司的4位营销总监月薪分别是2.5,2.1,1.8,1.6万元，若该公司还想将业务范围扩大到西北和西南，现在公司想在6个区中筹建销售分公司，考虑到甲业务最熟悉，他最多可以负责三个区的建设，乙的业务也比较熟练，他最多可以负责两个区的分公司的建设。为了避免多头领导，每个地区只派一个营销总监进行筹建工作。表7-21是各位营销总监在不同地区建分公司预计所用时间(单位：月)。问：如何指派各位营销总监区建设各区的分公司才能使总工资成本最低？建立数学模型并进行数值求解以及Excel软件求解。课本246页 习题 第15题所用筹建时间1华中2华南3华北4东北5西北6西南月薪(万元)1甲343.56482.52乙3.5438672.13丙45.556491.84丁567557.51.6地区地区人员人员第25页，此课件共41页哦实践性问题研究实践性问题研究建立数学模型，进行数值求解建立数学模型，进行数值求解 解解：若若用用aij表表示示营营销销总总监监i在在地地区区j筹筹建建分分公公司司所所用用的的时时间间，用用yi表表示示营营销销总总监监i的月薪。的月薪。引入引入0-1变量变量xij，令令Xij=1 ，营销总监营销总监i被指派被指派到地区到地区j筹建分公司筹建分公司0 ，营销总监营销总监i没被指派没被指派到地区到地区j筹建分公司筹建分公司便可得到如下的便可得到如下的0-1整数规划模型整数规划模型s.t第26页，此课件共41页哦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第27页，此课件共41页哦利用匈牙利法解：按第一步的（1）和（2）先让系数矩阵减去每行的最小元素，然后再减去每列的最小元素。343.56480343.56480343.564803.54386703.543867045.556490567557.50000.51010000.51010000.510100.50032000.500320011.521020224010.50第28页，此课件共41页哦然后进行试指派，以寻求最优解然后进行试指派，以寻求最优解从只有一个从只有一个0元素的列元素的列(行行)开始，给这个开始，给这个0元素加圈，记作元素加圈，记作 。这表示对这行所代表。这表示对这行所代表的人只有一种任务可指派。然后划去的人只有一种任务可指派。然后划去 所在行的其他所在行的其他0元素，记作元素，记作 ，,这表示这这表示这行所代表的人已指派任务，不必再考虑其他任务了。行所代表的人已指派任务，不必再考虑其他任务了。000.51010000.51010000.510100.50032000.500320011.521020224010.50第29页，此课件共41页哦仍没有划圈的仍没有划圈的0元素，且同行的元素，且同行的0元素至少有两个（表示对这人可以从两项任务中指元素至少有两个（表示对这人可以从两项任务中指派其一），从剩有派其一），从剩有0元素最少的行开始，比较这行各元素最少的行开始，比较这行各0元素所在列中元素所在列中0元素的数目，元素的数目，对对0元素少的那列的这个元素少的那列的这个0元素加圈（表示选择性多的应该先满足选择性少的），元素加圈（表示选择性多的应该先满足选择性少的），然后划掉同行同列的其他然后划掉同行同列的其他0元素。元素。000.51010000.51010000.510100.50032000.500320011.521020224010.50第30页，此课件共41页哦反复进行上一步反复进行上一步000.5110000.5110000.51100.50032000.500320011.521222410.5实践性问题研究实践性问题研究第31页，此课件共41页哦继续反复进行继续反复进行000.5110000.5110000.51100.5320.50320011.521222410.5实践性问题研究实践性问题研究第32页，此课件共41页哦000.51010000.5110000.51100.5320.53211.521222410.5实践性问题研究实践性问题研究第33页，此课件共41页哦0.51100.511000.51100.5320.53211.521222410.5实践性问题研究实践性问题研究第34页，此课件共41页哦0.5110.5110.51100.5320.53211.521222410.5实践性问题研究实践性问题研究第35页，此课件共41页哦此时，此时，k=n=7,所以最优解为所以最优解为:100000001000000000001(xij)=0010000000001000001000001000实践性问题研究实践性问题研究第36页，此课件共41页哦营销总监人员甲负责的地区是华中和华南地区，总共时间营销总监人员甲负责的地区是华中和华南地区，总共时间为为7个月；人员乙负责的地区是华北和西南地区，总共时间为个月；人员乙负责的地区是华北和西南地区，总共时间为10个月；人员丙负责的地区是西北地区，总共时间为个月；人员丙负责的地区是西北地区，总共时间为4个月；个月；人员丁负责的地区是东北地区，总共时间为人员丁负责的地区是东北地区，总共时间为5个月。个月。所需总工所需总工资成本最低为：资成本最低为：Z=72.5+10 2.1+4 1.8+5 1.6=53.7（万元）（万元）100000001000000000001(xij)=0010000000001000001000001000第37页，此课件共41页哦实践性问题研究实践性问题研究用用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=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)第38页，此课件共41页哦实践性问题研究实践性问题研究在在“工具工具”菜单中找到菜单中找到“规划求解规划求解”，单击，单击“规划求解规划求解”。在在“规划求解参数规划求解参数”对话框中，如下图进行设置。对话框中，如下图进行设置。第39页，此课件共41页哦在在“规划求解参数规划求解参数”对话框中，点击求解。得对话框中，点击求解。得到下图所示的最优解到下图所示的最优解用用Excel的规划求解可知总工资成的规划求解可知总工资成本最低为本最低为53.7万元。万元。第40页，此课件共41页哦第41页，此课件共41页哦