线性规划问题的图解法.ppt_第1页
线性规划问题的图解法.ppt_第2页
线性规划问题的图解法.ppt_第3页
线性规划问题的图解法.ppt_第4页
线性规划问题的图解法.ppt_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

一、 线性规划的图解法,解的几何表示,1什麽是图解法? 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是:先将约束条件加以图解,求得满足约束条件和非负条件的解的集合(即可行域),然后结合目标函数的要求从可行域中找出最优解。,2. 图解法举例,实施图解法,以求出最优生产计划(最优解), 给出最优值。,例3-1,由于线性规划模型中只有两个决策变量,因此只需建立平面直角坐标系就可以进行图解了。,第一步:建立平面直角坐标系 标出坐标原点, 坐标轴的指向和单位长度。用x1轴表示产品A的产量,用x2轴表示产品B的产量。 第二步:对约束条件加以图解。 第三步:画出目标函数等值线,结合目标函数的要求求出最优解:最优生产方案。 第四步:最优解带入目标函数,得出最优值。,约束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面,只要先画出该半平面的边界,然后确定是哪个半平面。,以第一个约束条件: 为例, 说明图解过程。,代表一个半平面 其边界: x1+2 x2 =8,点A、B 连线AB 经济含义 ? A0B,点A(8,0):,连接AB:,设备全部占用所生产、数量对应的点的集合。,全部的设备都用来生产产品而不生产产品,那么产品的最大可能产量为8台,计算过程为: x1+208 x18,0 B:,设备没有全部占用所生产、数量对应的点的集合。,约束条件及 非负条件x1,x2 0 代表的公共部分图中阴影区,就是满足所有约束条件和非负条件的点的集合,即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。,另两个约束条件的边界直线CD、EF: 4x116,4 x2 12,令 Z=2x1+3x2=c, 其中c为任选的一个常数,在图 中画出直线 2x1+3x2=c, 即对应着一个可行的生产结果,即使两种产品的总利润达到c。 这样的直线有无数条,且相互平行,称这样的直线为目标函数等值线。只要画两条目标函数等值线,如令 c0和c=6,可看出目 标函数值变化的方向, 即虚线 l1和l2,箭头为产 品的总利润递增的方向。,对应坐标x1=4, x2=2 是最佳的产品组合, 4,2T就是线性规划模型的最优解 使产品的总利润达到最大值maxZ=24+32=14就是目标函数最优值。,沿着箭头方向平移目标函数等值线,达到可行域中的最远点E, E点就是最优点;,尽管最优点的对应坐标可以直接从图中给出,但是在大多数情况下,对实际问题精确地看出一个解答是比较困难的。所以,通常总是用解联立方程的方法求出最优解的精确值。 比如C点对应的坐标值我们可以通过求解下面的联立方程,即求直线AB和CD的交点来求得。 直线AB: x1+2x2=8 直线CD: 4x1=16,结果 有唯一最优解 可行域是一个非空有界区域,可行域有几种可能 ? 解有几种可能 ?,唯一最优解,例3-3 将例3-1中目标要求改为极小化,目标函数和约束条件均不变,则可行域与例3-1相同,目标函数等值线也完全相同,只是在求最优解时,应沿着与箭头相反的方向平移目标函数等值线,求得的结果是有唯一最优解x1=4,x2=2,对应着图中的坐标原点。,无穷多个最优解,沿着箭头的方向平移目标函数等值线,发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合。,结果表明,该线性规划有无穷多个最优解线段AB上的所有点都是最优点,它们都使目标函数取得相同的最大值Zmax=14。,无界解,如图中可行域是一个无界区域,如阴影区所示。虚线为目表函数等值线,沿着箭头指的方向平移可以使目标函数值无限制地增大,但是找不到最优解。这种情况通常称为无“有限最优解” 或“最优解无界”。,如果一个实际问题抽象成像例1-4这样的线性规划模型,比如是一个生产计划问题,其经

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论