线性规划问题图解法.pptx

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

1、1什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。第1页/共18页2.图解法举例 实施图解法，以求出最优最优生产计划（最优解最优解）,给出最优值。最优值。例例3-1第2页/共18页 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。标系就

2、可以进行图解了。标系就可以进行图解了。标系就可以进行图解了。第一步：第一步：建立平面直角坐标系 标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品A的产量，用x2轴表示产品B的产量。第二步：第二步：对约束条件加以图解。第三步：第三步：画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。第四步：第四步：最优解带入目标函数，得出最优值。第3页/共18页 约束条件的图解:每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的先画出该半平面的边界边界，然后确定是哪个半平面确定是哪个半平面。?以第一个约束条件:为例,说明图解过程。怎麽画边界怎麽画边界 怎麽确定怎麽确定

3、半平面半平面第4页/共18页代表一个半平面其边界:x1+2 x2=8x1+2 x2=8及x1，x2 0 AOB点A、B连线AB 经济含义？A0B1203x24123x18567Q4B BA A第5页/共18页点A(8,0)：连接AB：设备全部占用所生产、数量对应的点的集合。全部的设备都用来生产产品而不生产产品,那么产品的最大可能产量为8台,计算过程为：x1+20 8 x1 80 B：设备没有全部占用所生产、数量对应的点的集合。1203x2412 3x185 6 7Q4B BA A第6页/共18页 约束条件及约束条件及非负条件非负条件x x1 1,x,x2 2 0 0代表的公共部分图中阴影区，就

4、是满足代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一行域。在这个区域中的每一个点都对应着一个可行的生产方案。个可行的生产方案。另另两两个个约约束束条条件件的的边界直线边界直线CDCD、EF:EF:4x4x1 11616，4 4 x x2 2 12128567x1A A3x2B BC CD DE E4123102F F第7页/共18页 令 Z=2x1+3x2=c,其中c c为为任任选选的的一一个个常常数数，在图 中画出直线 2x1+3x2=c,即对应着一个可行的生产结果，即使两种产品的总利润达到

5、c。这样的直线有无数条，且相互平行，称这样的直线为目目标标函函数数等等值值线线。只只要要画两条目标函数等值线等值线，如令 c0和c=6，可看出目目 标函数值变化的方向标函数值变化的方向,即虚线 l1和l2,箭头为产 品的总利润递增的方向。最优点最优点8567x1A A3x2B BC CD DE E4123102F F第8页/共18页对应坐标x1=4,x2=2 是最佳的产品组合,4,2T就是线性规划模型的最优解最优解使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数最优最优值值。沿着箭头沿着箭头方向平移平移目标函数等值线，达到可可行域中的最远点行域中的最远点E E,E点就是最优点

6、最优点;最优点最优点8567x1A A3x2B BC CD DE E4123102F F第9页/共18页 尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用用解解联联立立方方程程的的方方法法求求出出最最优优解解的的精精确值。确值。比如C点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:x1+2x2=8 直线CD:4x1=16第10页/共18页最优点最优点8567x1A A3x2B BC CD DE E4123102F F第11页/共18页结果有唯一最优解有唯一最优解可行域是一个非空有界区域

7、可行域是一个非空有界区域 用图解法求解线性规划的各种可能的结果可行域有几种可能?解有几种可能?讨论第12页/共18页唯一最优解唯一最优解 例例3-3 3-3 将例将例3-13-1中目标要求改为极中目标要求改为极小化，目标函数和约束条件均不变，则可小化，目标函数和约束条件均不变，则可行域与例行域与例3-13-1相同，目标函数等值线也完相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得头相反的方向平移目标函数等值线，求得的结果是有的结果是有唯一最优解唯一最优解x x1 1=4,x=4,x2 2=2,=2,对对应着图中

8、的坐标原点。应着图中的坐标原点。第13页/共18页 无穷多个最优解无穷多个最优解cc1 1,c,c2 2 8567x13x24123102B BA A第14页/共18页 沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合。结果表明，该线性规划有无无穷穷多多个个最最优优解解线段AB上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=14。第15页/共18页无界解无界解2406x212543x1第16页/共18页 如图中可行域是一个无界区域，如阴影区所示。虚线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。这种情况通常称为无无无无“有有有有限限限限最最最最优解优解优解优解”或或“最优解无界最优解无界最优解无界最优解无界”。如果一个实际问题抽象成像例1-4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大。此时应重新检查和修改模型，否则就没有实际意义。注意，对对于于无无界界可可行行域域的的情情况况，也也可可能能有有唯唯一一最最优解或无穷多个最优解优解或无穷多个最优解。第17页/共18页感谢您的观看！第18页/共18页