第二章线性规划问题的图解法精选PPT.ppt

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

1、第二章 线性规划问题的图解法第1页，本讲稿共18页1什麽是图解法？什麽是图解法？线线性性规规划划的的图图解解法法就就是是用用几几何何作作图图的的方方法分析并求出其最优解的过程。法分析并求出其最优解的过程。求求求求解解解解的的的的思思思思路路路路是是是是：先先先先将将将将约约约约束束束束条条条条件件件件加加加加以以以以图图图图解解解解，求求求求得得得得满满满满足足足足约约约约束束束束条条条条件件件件和和和和非非非非负负负负条条条条件件件件的的的的解解解解的的的的集集集集合合合合（即即即即可可可可行行行行域域域域），然然然然后后后后结结结结合合合合目目目目标标标标函函函函数数数数的的的的要要要要求

2、求求求从从从从可行域中找出最优解。可行域中找出最优解。可行域中找出最优解。可行域中找出最优解。第2页，本讲稿共18页2.2.图解法举例图解法举例 实施图解法，以求出实施图解法，以求出最优最优最优最优生产计划生产计划（最优解最优解）,给出给出最优值。最优值。例例2-1第3页，本讲稿共18页 由于线性规划模型中只有两个决策由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就变量，因此只需建立平面直角坐标系就可以进行图解了。可以进行图解了。第一步：第一步：第一步：第一步：建立平面直角坐标系建立平面直角坐标系 标标出出坐坐标标原原点点,坐坐标标轴轴的的指指向向和和单单位位长长度度。用用x1

3、轴轴表表示示产产品品A的的产产量量，用用x2轴轴表表示示产产品品B的产量。的产量。第二步：第二步：第二步：第二步：对约束条件加以图解。对约束条件加以图解。第三步：第三步：第三步：第三步：画出目标函数等值线，结合目标函数的要求画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。求出最优解：最优生产方案。第四步：第四步：第四步：第四步：最优解带入目标函数，得出最优值。最优解带入目标函数，得出最优值。第4页，本讲稿共18页 约束条件的图解约束条件的图解:每一个约束不等式在平面直角坐标系中都每一个约束不等式在平面直角坐标系中都代表一个半平面，只要代表一个半平面，只要先画出该半平面的边界先画

4、出该半平面的边界先画出该半平面的边界先画出该半平面的边界，然后然后确定是哪个半平面确定是哪个半平面确定是哪个半平面确定是哪个半平面。?以第一个约束条件以第一个约束条件:为例为例,说明图解过程。说明图解过程。怎麽画边界怎麽画边界怎麽画边界怎麽画边界 怎麽确定怎麽确定怎麽确定怎麽确定 半平面半平面半平面半平面第5页，本讲稿共18页代表一个半平面代表一个半平面其边界其边界:x1+2 x2=8x1+2 x2=8及及x1，x2 0 AOB点点A、B连线连线连线连线AB AB 经济含义经济含义？A0B1203x24123x18567Q4B BA A第6页，本讲稿共18页点点A(8,0)A(8,0)：连接连

5、接ABAB：设设备备全全部部占占用用所所生生产产、数数量量对对应应的的点点的的集集合。合。全全部部的的设设备备都都用用来来生生产产产产品品而而不不生生产产产产品品,那那么么产产品品的的最最大大可可能能产产量量为为8台台,计计算算过过程程为：为：x1+20 8 x1 80 B0 B：设设备备没没有有全全部部占占用用所所生生产产、数数量量对对应应的的点点的集合。的集合。1203x2412 3x185 6 7Q4B BA A第7页，本讲稿共18页 约束条件及约束条件及约束条件及约束条件及非负条件非负条件非负条件非负条件x x1 1,x,x2 2 0 0代表的公共部分图中阴影区，就是满足所有约束条代表

6、的公共部分图中阴影区，就是满足所有约束条代表的公共部分图中阴影区，就是满足所有约束条代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的件和非负条件的点的集合，即可行域。在这个区域中的件和非负条件的点的集合，即可行域。在这个区域中的件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。每一个点都对应着一个可行的生产方案。每一个点都对应着一个可行的生产方案。每一个点都对应着一个可行的生产方案。另另另另两两两两个个个个约约约约束束束束条条条条件件件件的的的的边界直线边界直线边界直线边界直线CDCD、EF:EF:4x 4x1 11

7、616，4 x4 x2 2 12 128567x1A A3x2B BC CD DE E4123102F F第8页，本讲稿共18页 令令 Z=2x1+3x2=c,其其中中c c为为为为任任任任选选选选的的的的一一一一个个个个常常常常数数数数，在在图图 中中画画出出直直线线 2x1+3x2=c,即即对对应应着着一一个个可可行行的的生生产产结结果果，即即使使两两种种产产品品的的总总利利润润达到达到c。这这样样的的直直线线有有无无数数条条，且且相相互互平平行行，称称这这样样的的直直线线为为目目目目标标标标函函函函数数数数等等等等值值值值线线线线。只只只只要要要要画画两两条条目目标标函数函数等值线等值线

8、等值线等值线，如令，如令 c0和和c=6，可看出，可看出目目目目 标函数值变化的方向标函数值变化的方向标函数值变化的方向标函数值变化的方向,即虚线即虚线 l1和和l2,箭头为产箭头为产 品的总利润递增的方向。品的总利润递增的方向。最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F第9页，本讲稿共18页对应坐标对应坐标x1=4,x2=2 是最佳的产品组合是最佳的产品组合,4,2T就是线性规划模型的就是线性规划模型的最优解最优解最优解最优解使产品的总利润达到最大值使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数就是目标函数最优值最优值最优

9、值最优值。沿着箭头沿着箭头沿着箭头沿着箭头方向方向平移平移平移平移目标函数等值线，达到目标函数等值线，达到可行域中可行域中可行域中可行域中的最远点的最远点的最远点的最远点E E,E点就是点就是最优点最优点最优点最优点;最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F第10页，本讲稿共18页 尽尽管管最最优优点点的的对对应应坐坐标标可可以以直直接接从从图图中中给给出出，但但是是在在大大多多数数情情况况下下，对对实实际际问问题题精精确确地地看看出出一一个个解解答答是是比比较较困困难难的的。所所以以，通通常常总总是是用用用用解解解解联联联联立立立立方方方方

10、程程程程的方法求出最优解的精确值。的方法求出最优解的精确值。的方法求出最优解的精确值。的方法求出最优解的精确值。比比如如C点点对对应应的的坐坐标标值值我我们们可可以以通通过过求求解解下下面面的的联立方程，即求直线联立方程，即求直线AB和和CD的交点来求得。的交点来求得。直线直线AB:x1+2x2=8 直线直线CD:4x1=16第11页，本讲稿共18页最优点最优点最优点最优点8567x1A A3x2B BC CD DE E4123102F F第12页，本讲稿共18页结果有唯一最优解有唯一最优解可行域是一个非空有界区域可行域是一个非空有界区域 用图解法求解线性规划的各种可能的结果用图解法求解线性规

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

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

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

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