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

1、,课本97页 习题 第1题,求解线性规划问题时可能出现哪几种结果？哪些结果反映建模时有错误？ 如何改正这些错误？,首先，给出一个线性规划问题的模型：,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,下面，我们采用最直观、简单的图解法求解：,理论性问题研究,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 = 12,目标

2、函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 =8,4x1 = 16,4 x2 =12,可行域,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 = 12,6 = 2x1 + 3x2,0 = 2x1 + 3x2,目标函数 Max

3、 Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 = 12,最优解：（4，2）,x1+ 2x2=8 4x1 =16,A(4，2),理论性问题研究,1、若将上面题目中的目标函数改为： Max Z =2x1 + 4x2 2、将约束条件 x1 + 2x2 8 改为： 2 x1 +3x212 此时线性规划问题的最优解将有何变化,理论性问题研究,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2

4、8 4x1 16 4x2 12 x1、 x2 0,理论性问题研究,第一种情况：,目标函数 Max Z = 2x1 + 4x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,目标函数 Max Z = 2x1 + 4x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 = 12,沿着 箭头的 方向画 平行线,最后，平行线 与直线： x1 + 2x2= 8,无穷多最优解,A,B,第一种情况：,0 = 2x1 +

5、 4x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,理论性问题研究,第二种情况：,目标函数 Max Z = 2x1 + 3x2 约束条件 2x1 + 3x2 12 4x1 16 4x2 12 x1、 x2 0,第二种情况：,目标函数 Max Z = 2x1 + 3x2 约束条件 2 x1 + 3x2 12 4x1 16 4x2 12 x1、 x2 0,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,2x1 + 3x2 = 12,4x1 = 16,4 x2 =12,x2,0 = 2x1 + 3

6、x2,最后，平行线 与直线： 2x1 + 3x2= 12,无穷多最优解,A,B,事实上，阴影部分构成一个凸多边形，其中A和B分别是两个极点， A和B就是典型的两个最优解，而连接两点之间的线段上的每一个坐标值，都是原问题的一个最优解。,理论性问题研究,思考 当我们把原约束条件变为： 4x1 16 则最优解又将发生何改变,目标函数 Max Z = 2x1 + 3x2 约束条件 4x1 16 x1、 x2 0,理论性问题研究,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,目标函数 Max Z = 2x1 + 3x2 约束条件 4x1 16 x1、 x2 0,| 1234

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

8、 12 x1 + x2 9 x1、 x2 0,理论性问题研究,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1 + x2 9 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 =12,x1 + x2 =9,由图知：此时可行域为空集，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。,理论性问题研究,注意：在应用上，当线性规划问题出现无界解和无可行解两种情形时，说明线性规划问题的模型有问题。,在应用上，当线性规划问题出现

9、无界解和无可行解两种情形时，说明线性规划问题的模型有问题。,那么，如何改正这些错误呢,？,理论性问题研究,原线性规划模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,目标函数 Max Z = 2x1 + 3x2 约束条件 4x1 16 x1、 x2 0,无界解时的线性规划模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1 + x2 9 x1、 x2 0,无可行解的线性规划模型,错误的模型：,理论性问题研究,目标函数 Max Z = 2x1 + 3x2

10、 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 = 12,最优解：（4，2）,x1+ 2x2=8 4x1 =16,A(4，2),、唯一最优解,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,目标函数 Max Z = 2x1 + 3x2 约束条件 4x1 16 x1、 x2 0,| 123456789,x1,4x1 = 16,可行域为图中阴影处向上延伸，看图可知：可行域无界。为求最优解做作等值线： Z = 2

11、x1 + 3x2 ，当Z值由小变大时，等值线平行向上移动，无论Z值增大多少，等值线上总有一段位于可行域内，事实上，可行域是个无界凸多边形，因此，等值线无论怎样移动，都无法遇到两个约束条件相交汇的顶点。因此，目标函数无上界，此时问题无有限最优解，即只能是无界解。,、无界解,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1 + x2 9 x1、 x2 0,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x1 + 2x2 = 8,4x1 = 16,4 x2 =12,x1 + x2 =9,由图知：此时可行域为空集

12、，即没有满足所有约束条件的点存在。所以，问题无可行解，更不存在最优解。,、无可行解,理论问题研究完毕， 接下来请看：,实践性 问题研究,通过对比分析，我们得出： a、出现无界解，是由于线性规划模型中缺乏必要的约束条件，因此，增加恰当的约束条件，使出现有界的可行域，即可解决问题； b、出现无可行解，是因为线性规划模型中的约束条件相互冲突， 需要修改模型后再进行求解。,假设在上题(P245.14)中该公司的4位营销总监月薪分别是2.5,2.1,1.8,1.6万元，若该公司还想将业务范围扩大到西北和西南，现在公司想在6个区中筹建销售分公司，考虑到甲业务最熟悉，他最多可以负责三个区的建设，乙的业务也比

13、较熟练，他最多可以负责两个区的分公司的建设。为了避免多头领导，每个地区只派一个营销总监进行筹建工作。表7-21是各位营销总监在不同地区建分公司预计所用时间(单位：月)。问：如何指派各位营销总监区建设各区的分公司才能使总工资成本最低？建立数学模型并进行数值求解以及Excel软件求解。,课本246页 习题 第15题,地区,人员,实践性问题研究,解：若用aij表示营销总监i在地区j筹建分公司所用的时间，用yi表示营销总监i的月薪。 引入0-1变量xij，令,便可得到如下的0-1整数规划模型,s.t,解：由题意，甲最多可以负责三个区的建设，乙最多可以负责两个区的分公司的建设，丙、丁分别可以负责一个区的

14、分公司的建设。因此将4人看作7人，在虚设1个地区，化为平衡指派问题。,实践性问题研究,地区,人员,利用匈牙利法解：按第一步的（1）和（2）先让系数矩阵减去每行的最小元素，然后再减去每列的最小元素。,3 4 3.5 6 4 8 0 3 4 3.5 6 4 8 0 3 4 3.5 6 4 8 0 3.5 4 3 8 6 7 0 3.5 4 3 8 6 7 0 4 5.5 5 6 4 9 0 5 6 7 5 5 7.5 0,0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0.5 0 0 3 2 0 0 0.5 0 0 3 2 0 0 1 1.5 2 1

15、 0 2 0 2 2 4 0 1 0.5 0,然后进行试指派，以寻求最优解从只有一个0元素的列(行)开始，给这个0元素加圈，记作 。这表示对这行所代表的人只有一种任务可指派。然后划去 所在行的其他0元素，记作 ，,这表示这行所代表的人已指派任务，不必再考虑其他任务了。,0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0.5 0 0 3 2 0 0 0.5 0 0 3 2 0 0 1 1.5 2 1 0 2 0 2 2 4 0 1 0.5 0,仍没有划圈的0元素，且同行的0元素至少有两个（表示对这人可以从两项任务中指派其一），从剩有0元素最少的行开

16、始，比较这行各0元素所在列中0元素的数目，对0元素少的那列的这个0元素加圈（表示选择性多的应该先满足选择性少的），然后划掉同行同列的其他0元素。,0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0 0 0.5 1 0 1 0 0.5 0 0 3 2 0 0 0.5 0 0 3 2 0 0 1 1.5 2 1 0 2 0 2 2 4 0 1 0.5 0,反复进行上一步,0 0 0.5 1 1 0 0 0 0.5 1 1 0 0 0 0.5 1 1 0 0.5 0 0 3 2 0 0 0.5 0 0 3 2 0 0 1 1.5 2 1 2 2 2 4 1 0.5,实践性问题研究,继

17、续反复进行,0 0 0.5 1 1 0 0 0 0.5 1 1 0 0 0 0.5 1 1 0 0.5 3 2 0.5 0 3 2 0 0 1 1.5 2 1 2 2 2 4 1 0.5,实践性问题研究,0 0 0.5 1 0 1 0 0 0 0.5 1 1 0 0 0 0.5 1 1 0 0.5 3 2 0.5 3 2 1 1.5 2 1 2 2 2 4 1 0.5,实践性问题研究,0.5 1 1 0 0.5 1 1 0 0 0.5 1 1 0 0.5 3 2 0.5 3 2 1 1.5 2 1 2 2 2 4 1 0.5,实践性问题研究,0.5 1 1 0.5 1 1 0.5 1 1 0

18、0.5 3 2 0.5 3 2 1 1.5 2 1 2 2 2 4 1 0.5,实践性问题研究,此时，k=n=7,所以最优解为:,1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 (xij)= 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0,实践性问题研究,营销总监人员甲负责的地区是华中和华南地区，总共时间为7个月；人员乙负责的地区是华北和西南地区，总共时间为10个月；人员丙负责的地区是西北地区，总共时间为4个月；人员丁负责的地区是东北地区，总共时间为5个月。 所需总工资成本最低为： Z=72.5+10 2.1+4 1.8+5 1.6=53.7（万元）,1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 (xij)= 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0,实践性问题研究,在Excel中建立该问题的数学模型,H11=SUM(B11:G11)，H12=SUM(B12:G12)，H13=SUM(B13