解线性规划问题时可能出现的几种结果

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,课本,97,页 习题 第,1,题,理论研究问题,求解线性规划问题时可能出现哪几种结果？哪些结果反映建模时有错误？,如何改正这些错误？,首先，给出一个线性规划问题的模型：,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,下面，我们采用最直观、简单的图解法求解：,理论性问题研究,图解法,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,可行域,图解法,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,6,=2,x,1,+3,x,2,0,=2,x,1,+3,x,2,图解法,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,最优解：（,4,，,2,）,x,1,+2,x,2,=8,4,x,1,=16,A(4,，,2),图解法,上述线性规划问题的模型的最优解出现在可行域的一个顶点处，此时线性规划问题有唯一最优解。,zzzzzzzzz,总结,理论性问题研究,1,、若将上面题目中的目标函数改为：,Max,Z,=2,x,1,+4,x,2,2,、将约束条件,x,1,+2,x,2,8,改为：,2,x,1,+3,x,2,12,此时线性规划问题的最优解将有何变化,理论性问题研究,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,理论性问题研究,第一种情况：,目标函数,Max,Z,=2,x,1,+4,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,改变目标函数,此时线性规划问题模型为：,同样采用图解法，请看下面图形：,目标函数,Max,Z,=2,x,1,+4,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,沿着,箭头的,方向画,平行线,最后，平行线,与直线：,x,1,+2,x,2,=8,无穷多最优解,A,B,第一种情况：,0,=2,x,1,+4,x,2,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,理论性问题研究,第二种情况：,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,2,x,1,+3,x,2,12,4,x,1,16,4,x,2,12,x,1,、,x,2,0,改变约束条件,此时线性规划问题模型为：,同样采用图解法，请看下面图形：,第二种情况：,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,2,x,1,+3,x,2,12,4,x,1,16,4,x,2,12,x,1,、,x,2,0,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,2x,1,+3,x,2,=,12,4,x,1,=,16,4,x,2,=,12,x,2,0,=2,x,1,+3,x,2,最后，平行线,与直线：,2,x,1,+3,x,2,=12,无穷多最优解,A,B,事实上，阴影部分构成一个凸多边形，其中,A,和,B,分别是两个极点，,A,和,B,就是典型的两个最优解，而连接两点之间的线段上的每一个坐标值，都是原问题的一个最优解。,理论性问题研究,思考,当我们把原约束条件变为：,4,x,1,16,则最优解又将发生何改变,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,4,x,1,16,x,1,、,x,2,0,理论性问题研究,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,4,x,1,16,x,1,、,x,2,0,|,123456789,x,1,4,x,1,=,16,可行域为图中阴影处向上延伸，看图可知：可行域无界。为求最优解做作等值线：,Z,=2,x,1,+3,x,2,，当,Z,值由小变大时，等值线平行向上移动，无论,Z,值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。,图解法,当我们在原线性规划模型中增加一个约束条件：,x,1+,x,2,9,思考：这时最优解又将作何改变,举一反三,线性规划模型：,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,+,x,2,9,x,1,、,x,2,0,理论性问题研究,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,+,x,2,9,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=12,x,1,+,x,2,=9,由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。,图解法,理论性问题研究,zzzzzzzzz,总结,线性规划问题求解的,几种可能结果,无穷多最优解,无界解,无可行解,唯一最优解,注意：在应用上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。,在应用上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。,那么，如何改正这些错误呢,理论性问题研究,原线性规划模型,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,4,x,1,16,x,1,、,x,2,0,无界解时的线性规划模型,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,+,x,2,9,x,1,、,x,2,0,无可行解的线性规划模型,错误的模型：,理论性问题研究,对比,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=,12,最优解：（,4,，,2,）,x,1,+2,x,2,=8,4,x,1,=16,A(4,，,2),、唯一最优解,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,4,x,1,16,x,1,、,x,2,0,|,123456789,x,1,4,x,1,=,16,可行域为图中阴影处向上延伸，看图可知：可行域无界。为求最优解做作等值线：,Z,=2,x,1,+3,x,2,，当,Z,值由小变大时，等值线平行向上移动，无论,Z,值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。,、无界解,目标函数,Max,Z,=2,x,1,+3,x,2,约束条件,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,+,x,2,9,x,1,、,x,2,0,x,2,9,8,7,6,5,4,3,2,1,0,|,123456789,x,1,x,1,+2,x,2,=,8,4,x,1,=,16,4,x,2,=12,x,1,+,x,2,=9,由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。,、无可行解,理论问题研究完毕，,接下来请看：,实践性,问题研究,通过对比分析，我们得出：,a,、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，增加恰当的约束条件，使出现有界的可行域，即可解决问题；,b,、出现无可行解，是因为线性规划模型中的约束条件相互冲突，需要修改模型后再进行求解。,结论,实践性问题研究,假设在上题,(P245.14),中该公司的,4,位营销总监月薪分别是,2.5,2.1,1.8,1.6,万元，若该公司还想将业务范围扩大到西北和西南，现在公司想在,6,个区中筹建销售分公司，考虑到甲业务最熟悉，他最多可以负责三个区的建设，乙的业务也比较熟练，他最多可以负责两个区的分公司的建设。为了避免多头领导，每个地区只派一个营销总监进行筹建工作。表,7-21,是各位营销总监在不同地区建分公司预计所用时间,(,单位：月,),。问：如何指派各位营销总监区建设各区的分公司才能使总工资成本最低？建立数学模型并进行数值求解以及,Excel,软件求解。,课本,246,页 习题 第,15,题,所用筹建,时间,1,华中,2,华南,3,华北,4,东北,5,西北,6,西南,月薪,(,万元,),1,甲,3,4,3.5,6,4,8,2.5,2,乙,3.5,4,3,8,6,7,2.1,3,丙,4,5.5,5,6,4,9,1.8,4,丁,5,6,7,5,5,7.5,1.6,地区,人员,实践性问题研究,建立数学模型，进行数值求解,解：,若用,a,ij,表示营销总监,i,在地区,j,筹建分公司所用的时间，用,y,i,表示营销总监,i,的月薪。,引入,0-1,变量,x,ij,，,令,X,ij=,1,，,营销总监,i,被指派,到地区,j,筹建分公司,0,，,营销总监,i,没被指派,到地区,j,筹建分公司,便可得到如下的,0-1,整数规划模型,s.t,1,华中,2,华南,3,华北,4,东北,5,西北,6,西南,7,1,甲,3,4,3.5,6,4,8,0,1,甲,3,4,3.5,6,4,8,0,1,甲,3,4,3.5,6,4,8,0,2,乙,3.5,4,3,8,6,7,0,解：,由题意，甲最多可以负责三个区的建设，乙最多可以负责两个区的分公司的建设，丙、丁分别可以负责一个区的分公司的建设。因此将,4,人看作,7,人,，在,虚设,1,个地区,，化为平衡指派问题。,实践性问题研究,地区,人员,2,乙,3.5,4,3,8,6,7,0,3,丙,4,5.5,5,6