运筹学课件第二节图解法
42页1、第二节 图解法 2.1图解法步骤 图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是:先将约束条件加以图解,求得满足约束条件的解的集合(即可行域),然后结合目标函数的要求从可行域中找出最优解。,图解法举例,实施图解法,以求出最优生产计划(最优解),由于线性规划模型中只有两个决策变量,因此只需建立平面直角系就可以进行图解了。,第一步:建立平面直角坐标系,标出坐标原点, 坐标轴的指向和单位长度。 用x1轴表示产品A的产量,用x2轴表示产品B的 产量。 第二步:对约束条件加以图解。 第三步:画出目标函数等值线,结合目标函数 的要求求出最优解-最优生产方案。,约束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面,只要先画出该半平面的边界,然后确定是哪个半平面。,第一个约束条件 1/3 x1+1/3 x2 1,令1/3 x1+1/3 x2 1, 即直线AB。 1/3 x1+1/3 x2 1 所代表的半平面 的边界:,两个约束条件 及非负条件x1,x2 0所代表的公共部分 图中阴影区,就是满足所有约束条件和非负条件的点的集合,即可行域。在这个区域中的每一个点都对应着
2、一个可行的生产方案。,第二个约束条件的边界 直线CD: 1/3x1+4/3 x2 =3,5,4,l,1,3,B,2,D,(,1/3,),x,1,+(4/3)x,2,=3,l,2,1,0,1,2,3,A,4,5,6,7,8,9,C,(1/3),x,1,+(1/3)x,2,=1,令 Z=2x1+3x2=c,其中c为任选的一个常数,在图中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案,即使两种产品的总利润达到c。 这样的直线有无数条,而且相互平行,称这样的直线为目标函数等值线。只要画出两条目标函数等值线,比如令c0和c=6,就能看出 目标函数值递增的方向, 用箭头标出这个方向。 图中两条虚线 l1和l2就 分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头表示使两种产品的 总利润递增的方向。,沿着箭头的方向平移目标函数等值线,使其达到可行域中的最远点E, E点就是要求的最优点,它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合,即生产A产品等于1,B产品等于2能使两种产品的总利润达到最大值 max Z=21+32=8,x1=1,x2=
3、2就是线性规划模型的最优解,Zmax=8就是相应的目标函数最优值。,尽管最优点的对应坐标可以直接从图中给出,但是在大多数情况下,对实际问题精确地看出一个解答是比较困难的。所以,通常总是用解联立方程的方法求出最优解的精确值。 比如E点对应的坐标值我们可以通过求解下面的联立方程,即求直线AB和CD的交点来求得。 直线AB: 1/3x1+1/3x2=1 直线CD: 1/3x1+4/3x2=3,(3,0),C=6,(9,0),(0,9/4),E(1,2),C=0,(0,3),设三种产品的产量分别是x1、x2、x3吨,由于有三个决策变量,用图解法求解下面的线性规划时,必须首先建立空间直角坐标系。,变量超过2个情况,0,x1,x2,5x2=15,6x1+2x2=24,x1+x2=5,x2=-2x1+Z,最优解的确定:可行域使目标函数达到 最优的点,目标函数的Z值逐渐增大, 一直移动到目标函数的直线与约束条 件包围成的凸多边形相切时为止,切 点就是最优解。(x1,x2)=(3.5,1.5),z=8.5,1、无穷多个最优解:将目标函数 max Z=x1+x2 2、无界解:可行域可伸展到无穷,导致目标函
4、数增大到无限。产生无界解的原因是由于在建立实际问题的数学模型中遗漏某些必要的资源约束。 3、无解:不存在满足约束条件的可行域。,2.2线性规划求解的各种可能的结局,2.2.1无穷多个最优解,该线性规划的可行域为上图中四边形OAED(即阴影区),虚线为目标函数等值线,箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线,发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AE重合,这个结果表明,该线性规划有无穷多个最优解线段AE上的所有点都是最优点,它们都使目标函数取得相同的最大值Zmax=3。,2.2.2无界解,本例中的可行域是一个无界区域, 如图中阴影区所示。虚线为目函数 等值线,沿着箭头所指的方向平移可 以使目标函数值无限制地增大,因此 找不到最优解。 如果实际问题是一个生产计划问题,其经济含义就是某些资源是无限的,产品的产量可以无限大,解释不合理。此时应重新检查和修改模型,否则就没有实际意义。,2.2.3无解,2.3图解法得到的启示,1、求解线性规划问题时,解的情况:唯一最优解、无穷多个最优解、无界解,无解。 2、若线性规划的可行域存在,则可行域一定是凸多边形(凸集
《运筹学课件第二节图解法》由会员san****019分享,可在线阅读,更多相关《运筹学课件第二节图解法》请在金锄头文库上搜索。
高中化学实验方案的设计第一节制备实验方案设计
高中生物实验室配置
高中体育与健康课程田径必修模块单元教学方案
高中通用技术方案的构思方法-设计分析教案苏教版必修
高中生物室配置
高中信息技术网络技术应用选修模块教学评价方案
骆小学教师戏曲知识培训方案(I)
麻村小学阳光体育活动计划及实施方案
高桥小学幼小衔接活动方案
马摆小学控辍保学实施方案
金阳街道中心小学未成年人思想道德建设实施方案
龙扬小学第32个爱国卫生月活动方案
魏家井联小学度控辍保学工作方案
高区第九届初中骨干教师课堂教学能力展示活动
长沙县2018年度小学生课外阅读知识竞赛及书目
阳江中心小学一月一事之五月主题活动方案
长营小学校园体育活动实施方案
高考历史备考方案-陈军
高考语文第5课父亲课前预案苏教版选修现代散文选读
高考语文第9课铃兰花课前预案苏教版选修现代散文选读
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页