第二章2[1]21 线性规划问题的图解法.ppt

《第二章2[1]21 线性规划问题的图解法.ppt》由会员分享，可在线阅读，更多相关《第二章2[1]21 线性规划问题的图解法.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、一、线性规划的图解法线性规划的图解法 解的几何表示解的几何表示 1什麽是图解法？什麽是图解法？线线性性规规划划的的图图解解法法就就是是用用几几何何作作图图的方法分析并求出其最优解的过程。的方法分析并求出其最优解的过程。求求解解的的思思路路是是：先先将将约约束束条条件件加加以以图图解解，求求得得满满足足约约束束条条件件和和非非负负条条件件的的解解的的集集合合（即即可可行行域域），然然后后结结合合目目标标函数的要求从可行域中找出最优解。函数的要求从可行域中找出最优解。2.图解法举例图解法举例 实施图解法，以求出实施图解法，以求出最优最优生产计生产计划划（最优解最优解）,给出给出最优值。最优值。

2、例例2-1 由于线性规划模型中只有两个决策由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就变量，因此只需建立平面直角坐标系就可以进行图解了。可以进行图解了。第一步：第一步：第一步：第一步：建立平面直角坐标系建立平面直角坐标系 标标出出坐坐标标原原点点,坐坐标标轴轴的的指指向向和和单单位位长长度度。用用x1轴轴表表示示产产品品A的的产产量量，用用x2轴表示产品轴表示产品B的产量。的产量。第二步：第二步：第二步：第二步：对约束条件加以图解。对约束条件加以图解。第三步：第三步：第三步：第三步：画出目标函数等值线，结合目标函数画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方

3、案。的要求求出最优解：最优生产方案。第四步：第四步：第四步：第四步：最优解带入目标函数，得出最优值。最优解带入目标函数，得出最优值。约束条件的图解约束条件的图解:每一个约束不等式在平面直角坐标系中每一个约束不等式在平面直角坐标系中都代表一个半平面，只要都代表一个半平面，只要先画出该半平面的先画出该半平面的先画出该半平面的先画出该半平面的边界边界边界边界，然后，然后确定是哪个半平面确定是哪个半平面确定是哪个半平面确定是哪个半平面。?以第一个约束条件以第一个约束条件:为例为例,说明图解过程。说明图解过程。怎麽画边界怎麽画边界怎麽画边界怎麽画边界 怎麽确定怎麽确定怎麽确定怎麽确定 半平面半平面半平面

4、半平面代表一个半平面代表一个半平面其边界其边界:x1+2 x2=8x1+2 x2=8及及x1，x2 0 AOB点点A、B连线连线AB 经济含义经济含义？A0B1203x24123x18567Q4B BA A点点A(8,0)：连接连接AB：设设备备全全部部占占用用所所生生产产、数数量量对对应应的的点点的集合。的集合。全全部部的的设设备备都都用用来来生生产产产产品品而而不不生生产产产产品品,那那么么产产品品的的最最大大可可能能产产量量为为8台台,计算过程为：计算过程为：x1+20 8 x1 80 B：设设备备没没有有全全部部占占用用所所生生产产、数数量量对对应应的点的集合的点的集合。1203x24

5、12 3x185 6 7Q4B BA A 约束条件及约束条件及约束条件及约束条件及非负条件非负条件非负条件非负条件x x1 1,x,x2 2 0 0代表的公共部分图中阴影区，就是满足所代表的公共部分图中阴影区，就是满足所代表的公共部分图中阴影区，就是满足所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。有约束条件和非负条件的点的集合，即可行域。有约束条件和非负条件的点的集合，即可行域。有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的在这个区域中的每一个点都对应着一个可行的在这个区域中的每一个点都对应着一个可行的在这个区域中的每一个

6、点都对应着一个可行的生产方案。生产方案。生产方案。生产方案。另另另另两两两两个个个个约约约约束束束束条条条条件件件件的的的的边界直线边界直线边界直线边界直线CDCD、EF:EF:4x 4x1 11616，4 x4 x2 2 12 128567x1A A3x2B BC CD DE E4123102F F 令令 Z=2x1+3x2=c,其其中中c c为为为为任任任任选选选选的的的的一一一一个个个个常常常常数数数数，在在图图 中中画画出出直直线线 2x1+3x2=c,即即对对应应着着一一个个可可行行的的生生产产结结果果，即即使使两两种种产产品品的的总总利利润润达到达到c。这这样样的的直直线线有有无无

7、数数条条，且且相相互互平平行行，称称这这样样的的直直线线为为目目标标函函数数等等值值线线。只只只只要要要要画画两两条条目目标函数标函数等值线等值线等值线等值线，如令，如令 c0和和c=6，可看出，可看出目目目目 标函数值变化的方向标函数值变化的方向标函数值变化的方向标函数值变化的方向,即虚线即虚线 l1和和l2,箭头为产箭头为产 品的总利润递增的方向。品的总利润递增的方向。最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F对应坐标对应坐标x1=4,x2=2 是最佳的产品组合是最佳的产品组合,4,2T就是线性规划模型的就是线性规划模型的最优解最优解最优解

8、最优解使产品的总利润达到最大值使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数就是目标函数最优值最优值最优值最优值。沿着箭头沿着箭头沿着箭头沿着箭头方向方向平移平移平移平移目标函数等值线，达到目标函数等值线，达到可可可可行域中的最远点行域中的最远点行域中的最远点行域中的最远点E E,E点就是点就是最优点最优点最优点最优点;最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F 尽尽管管最最优优点点的的对对应应坐坐标标可可以以直直接接从从图图中中给给出出，但但是是在在大大多多数数情情况况下下，对对实实际际问问题题精精确确地地看看出出一一个个

9、解解答答是是比比较较困困难难的的。所所以以，通通常常总总是是用用用用解解解解联联联联立立立立方方方方程程程程的的的的方方方方法法法法求求求求出出出出最最最最优优优优解解解解的的的的精精精精确值。确值。确值。确值。比比如如C点点对对应应的的坐坐标标值值我我们们可可以以通通过过求求解解下下面面的的联联立立方方程程，即即求求直直线线AB和和CD的的交交点来求得。点来求得。直线直线AB:x1+2x2=8 直线直线CD:4x1=16最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F结果有唯一最优解有唯一最优解可行域是一个非空有界区域可行域是一个非空有界区域 用图

10、解法求解线性规划的各种可能的结果用图解法求解线性规划的各种可能的结果可行域有几种可能可行域有几种可能?解有几种可能解有几种可能?讨论讨论唯一最优解唯一最优解 例例例例2-3 2-3 将例将例将例将例2-12-1中目标要求改为极小化，中目标要求改为极小化，中目标要求改为极小化，中目标要求改为极小化，目标函数和约束条件均不变，则可行域与目标函数和约束条件均不变，则可行域与目标函数和约束条件均不变，则可行域与目标函数和约束条件均不变，则可行域与例例例例1-11-1相同，目标函数等值线也完全相同，相同，目标函数等值线也完全相同，相同，目标函数等值线也完全相同，相同，目标函数等值线也完全相同，只是在求最

11、优解时，应沿着与箭头相反的只是在求最优解时，应沿着与箭头相反的只是在求最优解时，应沿着与箭头相反的只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是方向平移目标函数等值线，求得的结果是方向平移目标函数等值线，求得的结果是方向平移目标函数等值线，求得的结果是有有有有唯一最优解唯一最优解x x1 1=4,x=4,x2 2=2,=2,对应着图对应着图对应着图对应着图2-62-6中中中中的坐标原点。的坐标原点。的坐标原点。的坐标原点。无穷多个最优解无穷多个最优解cc1 1,c,c2 2 8567x13x24123102B BA A 沿沿着着箭箭头头的的方方向向平平移移目目标标函函

12、数数等等值值线线，发发现现平平移移的的最最终终结结果果是是目目标标函函数数等等值值线线将将与可行域的一条边界线段与可行域的一条边界线段AB重合。重合。结结果果表表明明，该该线线性性规规划划有有无无穷穷多多个个最最优优解解线线段段AB上上的的所所有有点点都都是是最最优优点点，它它们们都都使使目目标标函函数数取取得得相相同同的的最最大大值值Zmax=14。无界解无界解2406x212543x1 如如图图中中可可行行域域是是一一个个无无界界区区域域，如如阴阴影影区区所所示示。虚虚线线为为目目表表函函数数等等值值线线，沿沿着着箭箭头头指指的的方方向向平平移移可可以以使使目目标标函函数数值值无无限限制制

13、地地增增大大，但但是是找找不不到到最最优优解解。这这种种情情况况通通常常称称为为无无无无“有有有有限限限限最最最最优优优优解解解解”或或或或“最最最最优优优优解无界解无界解无界解无界”。如如果果一一个个实实际际问问题题抽抽象象成成像像例例1-4这这样样的的线线性性规规划划模模型型，比比如如是是一一个个生生产产计计划划问问题题，其其经经济济含含义义就就是是某某些些资资源源是是无无限限的的，产产品品的的产产量量可可以以无无限限大大。此此时时应应重重新检查和修改模型，否则就没有实际意义。新检查和修改模型，否则就没有实际意义。注注意意，对对对对于于于于无无无无界界界界可可可可行行行行域域域域的的的的情情情情况况况况，也也也也可可可可能能能能有有有有唯唯唯唯一一一一最最最最优解或无穷多个最优解优解或无穷多个最优解优解或无穷多个最优解优解或无穷多个最优解。