物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第三章线性规划 第三节模型求解
29页1、一、图解方法,图解方法一般只能用来解两个变量的线性规划问题,它直 观简便,虽应用范围较小,但有助于理解线性规划问题的几何 意义和解的基本情况。单纯形法是LP问题的一般解法,继图解 方法后再介绍。 例3-3 用图解法求解下面的线性规划问题 maxZ=,s.t.,解:在 直角坐标平面上作直线(图3-2),,一、图解方法,图3-2 图解法 约束条件的每一个不等式都表示一个半平面,满足约束条件 的点集是四个不等式所对应的四个半平面的公共部分,即上述两 条直线及两条坐标轴的边界所围成的凸多边形OAEC的内部及边 界。,一、图解方法,根据以上分析可知,在这个阴影部分的所有点(包括边界上的 点),满足该问题的所有约束条件,这个范围以外的点,则不能同 时满足上述各约束条件。 满足所有约束条件的点称为可行点。 每一点代表该线性规划问题的一个可行方案,即一个可行解。 所有可行点的集合,是该问题的可行域。 图3-2中四边形OAEC内部及边界构成的阴影部分即为可行域,故 该问题的可行解有无数个。 一般说来,决策者感兴趣的不是可行域中所有的可行解,而是能 使目标函数值达到最优值(最大值或最小值)的可行解,这种解
2、称 为最优可行解,简称最优解。,一、图解方法,为寻找最优解,将目标函数写成:50x1+40x2 = k,其中为 任意常数。当为不同值时,此函数表示相互平行的等值线。 令=0,先作通过原点的等值线 l3: 50x1+40x2 = 0 它与可行域有交点。将这条直线沿目标函数增大的右上方 平移,过顶点E时,Z在可行域中取最大值;如继续向右上方 平移,则等值线将离开可行域(等值线与可行域没有交 点)。故E点坐标就是最优解。求l1和l2交点E坐标,得到: x1=10,x2=15,这时最优值Z=1100。 即例1中,甲产品产量为10件,乙产品产量为15件时,所获利润最大,最大利润为1100元。,一、图解方法,归纳图解法求解线性规划问题的步骤: (1)在x1ox2直角坐标平面上,根据约束条件作出可行域的图形(一般为一个凸多边形)。 (2)作出目标函数的0等值线,即目标函数值等于0的过原点的直线。 (3)将0等值线沿目标函数增大的方向平移,当等值线移至与可行域的最后一个交点(一般是可行域的一个顶点)时,该交点就是所求的最优点。若等值线与可行域的一条边界重合,则最优点为无穷多个(见例3-5)。 (4)求
3、出最优点坐标(两直线交点坐标可联立直线方程求解),即得到最优解(x1, x2),及最优值Z(x1, x2)。,一、图解方法,例3-4 用图解法求解下列线性规划问题,maxZ =,s.t.,解:在 直角坐标系中作直线(图3-3),,得可行域OAEC。 作0等值线:,一、图解方法,E(10,15),l1,l2,20,40,20,10,10,该等值线l3斜率与l2 斜率相等,当向右上方平移到与边界线EC重合时,目标函数值最大。故边界EC上的所有点,包括两个端点E(10,15)和C(0,20)都是此问题的最优解,此时目标函数的最优值为: Z(10,15)=Z(0,20)=800 这是线性规划问题有无穷多个最优解的情况。它同时说明,即使在最优解非唯一时,最优解还是会出现在可行域的一个顶点上。,图3-3 图解法,一、图解方法,例3-5 用图解法求解下列线性规划问题,maxZ=,s.t.,解:在 直角坐标系中作直线,x1,x2,l1,O,2,图3-4图解法,由图可知,可行域沿 轴无限延伸。作0等值线 并将它向右上方平移,因可行域无界,目标函数趋于无穷,该线性规划问题无有限最优解。 在实际应用中,应对
4、数学模型认真检查,适当修改,增加必要的约束条件,使可行域变为有界,再求解。,L,一、图解方法,例3-6 用图解法求解下列线性规划问题,maxZ =,s.t.,解:在 直角坐标系中作直线(图3-5),x2,l1,l2,图3-5 图解法,各不等式对应的半平面无公共部分,即可行域是空的。不存在任一可行解,更没有最优解。 在实际应用中,可去掉一些互相矛盾的约束条件,再求解。,二、单纯形法,(一)标准形式及转化为标准形式的方法 1标准形式 线性规划模型的标准形式要求: (1)所有约束条件都由等式表示,并且等式右端的常数为非负; (2)所有决策变量为非负; (3)目标函数求最大值(也可用求最小值问题作为标准形式,本 书对目标函数统一成求最大值)。 故线性规划模型的标准形式为:,maxZ =,s.t., +,二、单纯形法,(一)标准形式及转化为标准形式的方法 2一般形式化为标准形式的方法 线性规划问题的一般形式都能变换成标准形式。变 换的方法主要有以下两种: (1)若约束条件有不等式时,可在不等式的左边加 上或减去一个非负变量,使之成为等式。加入的变量 叫松弛变量,减去的变量则叫剩余变量,它们在目标
《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第三章线性规划 第三节模型求解》由会员E****分享,可在线阅读,更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第三章线性规划 第三节模型求解》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页