第二章线性规划问题的图解法精选文档.ppt
第二章 线性规划问题的图解法本讲稿第一页，共十八页1什麽是图解法？什麽是图解法？线线性性规规划划的的图图解解法法就就是是用用几几何何作作图图的的方方法分析并求出其最优解的过程。法分析并求出其最优解的过程。求求解解的的思思路路是是：先先将将约约束束条条件件加加以以图图解解，求求得得满满足足约约束束条条件件和和非非负负条条件件的的解解的的集集合合（即即可可行行域域），然然后后结结合合目目标标函函数数的的要求从可行域中找出最优解。要求从可行域中找出最优解。本讲稿第二页，共十八页2.图解法举例图解法举例 实施图解法，以求出实施图解法，以求出最优最优生产计划生产计划（最优解最优解）,给出给出最优值。最优值。例例2-1本讲稿第三页，共十八页 由于线性规划模型中只有两个决策由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就变量，因此只需建立平面直角坐标系就可以进行图解了。可以进行图解了。第一步：第一步：建立平面直角坐标系建立平面直角坐标系 标标出出坐坐标标原原点点,坐坐标标轴轴的的指指向向和和单单位位长长度度。用用x1轴轴表表示示产产品品A的的产产量量，用用x2轴轴表表示产品示产品B的产量。的产量。第二步：第二步：第二步：第二步：对约束条件加以图解。对约束条件加以图解。第三步：第三步：第三步：第三步：画出目标函数等值线，结合目标函数的要画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。求求出最优解：最优生产方案。第四步：第四步：最优解带入目标函数，得出最优值。最优解带入目标函数，得出最优值。本讲稿第四页，共十八页 约束条件的图解约束条件的图解:每一个约束不等式在平面直角坐标系中都代表每一个约束不等式在平面直角坐标系中都代表一个半平面，只要一个半平面，只要先画出该半平面的边界先画出该半平面的边界先画出该半平面的边界先画出该半平面的边界，然后，然后确确定是哪个半平面定是哪个半平面。?以第一个约束条件以第一个约束条件:为例为例,说明图解过程。说明图解过程。怎麽画边界怎麽画边界 怎麽确定怎麽确定 半平面半平面本讲稿第五页，共十八页代表一个半平面代表一个半平面其边界其边界: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：设设备备没没有有全全部部占占用用所所生生产产、数数量量对对应应的的点点的的集合。集合。1203x2412 3x185 6 7Q4B BA A本讲稿第七页，共十八页 约束条件及约束条件及约束条件及约束条件及非负条件非负条件非负条件非负条件x x1,x,x2 0 0代表的公共部分图中阴影区，就是满足所有约代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。区域中的每一个点都对应着一个可行的生产方案。另另两两个个约约束束条条件件的的边界直线边界直线CD、EF:4x116，4 x2 128567x1A A3x2B BC CD DE E4123102F F本讲稿第八页，共十八页 令令 Z=2x1+3x2=c,其其中中c为为任任选选的的一一个个常常数数，在在图图 中中画画出出直直线线 2x1+3x2=c,即即对对应应着着一一个个可可行行的的生生产产结结果果，即即使使两两种种产产品品的的总总利利润润达到达到c。这这样样的的直直线线有有无无数数条条，且且相相互互平平行行，称称这这样样的的直直线线为为目目标标函函数数等等值值线线。只只要要画画两两条条目目标标函数函数等值线等值线，如令，如令 c0和和c=6，可看出，可看出目目 标函数值变化的方向标函数值变化的方向,即虚线即虚线 l1和和l2,箭头为产箭头为产 品的总利润递增的方向。品的总利润递增的方向。最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F本讲稿第九页，共十八页对应坐标对应坐标x1=4,x2=2 是最佳的产品组合是最佳的产品组合,4,2T就是线性规划模型的就是线性规划模型的最优解最优解使产品的总利润达到最大值使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数就是目标函数最优值最优值。沿着箭头沿着箭头沿着箭头沿着箭头方向方向平移平移目标函数等值线，达到目标函数等值线，达到可行域中可行域中的最远点的最远点E E,E点就是点就是最优点最优点最优点最优点;最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F本讲稿第十页，共十八页 尽尽管管最最优优点点的的对对应应坐坐标标可可以以直直接接从从图图中中给给出出，但但是是在在大大多多数数情情况况下下，对对实实际际问问题题精精确确地地看看出出一一个个解解答答是是比比较较困困难难的的。所所以以，通通常常总总是是用解联立方程的方法求出最优解的精确值。用解联立方程的方法求出最优解的精确值。用解联立方程的方法求出最优解的精确值。用解联立方程的方法求出最优解的精确值。比比如如C点点对对应应的的坐坐标标值值我我们们可可以以通通过过求求解解下下面的联立方程，即求直线面的联立方程，即求直线AB和和CD的交点来求得。的交点来求得。直线直线AB:x1+2x2=8 直线直线CD:4x1=16本讲稿第十一页，共十八页最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F本讲稿第十二页，共十八页结果有唯一最优解有唯一最优解可行域是一个非空有界区域可行域是一个非空有界区域 用图解法求解线性规划的各种可能的结果用图解法求解线性规划的各种可能的结果可行域有几种可能可行域有几种可能?解有几种可能解有几种可能?讨论讨论本讲稿第十三页，共十八页唯一最优解唯一最优解 例例例例2-3 将例将例将例将例2-12-1中目标要求改为极小化，目标中目标要求改为极小化，目标中目标要求改为极小化，目标中目标要求改为极小化，目标函数和约束条件均不变，则可行域与例函数和约束条件均不变，则可行域与例函数和约束条件均不变，则可行域与例函数和约束条件均不变，则可行域与例1-1相同，相同，目标函数等值线也完全相同，只是在求最优解目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是有值线，求得的结果是有唯一最优解唯一最优解x x1 1=4,x2 2=2,对应着图对应着图对应着图对应着图2-6中的坐标原点。中的坐标原点。中的坐标原点。中的坐标原点。本讲稿第十四页，共十八页 无穷多个最优解无穷多个最优解c1,c28567x13x24123102B BA A本讲稿第十五页，共十八页 沿沿着着箭箭头头的的方方向向平平移移目目标标函函数数等等值值线线，发发现现平平移移的的最最终终结结果果是是目目标标函函数数等等值值线线将将与与可可行域的一条边界线段行域的一条边界线段AB重合。重合。结结果果表表明明，该该线线性性规规划划有有无无穷穷多多个个最最优优解解线线段段AB上上的的所所有有点点都都是是最最优优点点，它它们都使目标函数取得相同的最大值们都使目标函数取得相同的最大值Zmax=14。本讲稿第十六页，共十八页无界解无界解2406x212543x1本讲稿第十七页，共十八页 如如图图中中可可行行域域是是一一个个无无界界区区域域，如如阴阴影影区区所所示示。虚虚线线为为目目表表函函数数等等值值线线，沿沿着着箭箭头头指指的的方方向向平平移移可可以以使使目目标标函函数数值值无无限限制制地地增增大大，但但是是找找不不到到最最优优解解。这这种种情情况况通通常常称称为为无无“有有限限最最优优解解”或或或或“最最优优解解无界无界”。如如果果一一个个实实际际问问题题抽抽象象成成像像例例1-4这这样样的的线线性性规规划划模模型型，比比如如是是一一个个生生产产计计划划问问题题，其其经经济济含含义义就就是是某某些些资资源源是是无无限限的的，产产品品的的产产量量可可以以无无限限大大。此此时时应应重重新新检检查查和和修修改改模模型型，否则就没有实际意义。否则就没有实际意义。注注意意，对对对对于于于于无无无无界界界界可可可可行行行行域域域域的的的的情情情情况况况况，也也也也可可可可能能能能有有有有唯唯唯唯一一一一最最最最优优优优解解解解或或或或无无无无穷多个最优解穷多个最优解穷多个最优解穷多个最优解。本讲稿第十八页，共十八页
