第2部分线性规划的图解法ppt课件.ppt
《第2部分线性规划的图解法ppt课件.ppt》由会员分享,可在线阅读,更多相关《第2部分线性规划的图解法ppt课件.ppt(36页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二、二、线性规划的图解法线性规划的图解法 解的几何表示解的几何表示 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1什么是图解法?什么是图解法?线线性性规规划划的的图图解解法法就就是是用用几几何何作作图图的的方法方法分析并求出其最优解分析并求出其最优解的过程。的过程。求求解解的的思思路路是是:先先将将约约束束条条件件加加以以图图解解,求求得得满满足足约约束束条条件件的的解解的的集集合合(即即可可行行域域),然然后后结结合合
2、目目标标函函数数的的要要求求从从可可行行域中找出最优解。域中找出最优解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.图解法举例图解法举例 实施图解法,以求出实施图解法,以求出最优最优生产计划生产计划(最优解最优解)。例例11为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 由于线性规划模型中只有两个决策变量,因由于线性规划模型中只有两个决策变量,因此只需建立平面直角坐标系就可进行图解了。此只需建立平面直角坐标系就可进行图解了。第第第第一一一一步步步步:建建立立平平
3、面面直直角角坐坐标标系系,标标出出坐坐坐坐标标标标原原原原点点点点,坐标轴的指向坐标轴的指向坐标轴的指向坐标轴的指向和和单位长度单位长度单位长度单位长度。用用x1轴轴表表示示产产品品A的的产产量量,用用x2轴轴表表示示产产品品B的产量。的产量。第二步:第二步:第二步:第二步:对约束条件加以图解。对约束条件加以图解。第三步:第三步:第三步:第三步:画出目标函数等值线,结合目标画出目标函数等值线,结合目标函数的要求求出最优解最优生产方案。函数的要求求出最优解最优生产方案。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束条件的图解约
4、束条件的图解:每一个约束不等式在平面直角坐标系中都每一个约束不等式在平面直角坐标系中都代表一个半平面,只要代表一个半平面,只要先画出该半平面的边先画出该半平面的边先画出该半平面的边先画出该半平面的边界界界界,然后,然后确定是哪个半平面确定是哪个半平面确定是哪个半平面确定是哪个半平面。?以第一个约束条件以第一个约束条件 1/3 x1+1/3 x2 1 为例为例 说明约束条件的图解过程。说明约束条件的图解过程。怎么画边界怎么画边界怎么画边界怎么画边界 怎么确定怎么确定怎么确定怎么确定 半平面半平面半平面半平面为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥
5、中小学图书室育人功能 如如果果全全部部的的劳劳动动工工时时都都用用来来生生产产A 产产品品而而不不生生产产B产产品品,那那么么A产产品品的的最最大大可可能能产产量量为为3吨吨,计计算算过过程为:程为:1/3x1+1/30 1 x1 3 这这个个结结果果对对应应着着右右图图中中的的点点A(3,0),同同样样我我们们可可以以找找到到B产产品品最最大大可可能能产产量量对对应应的的点点B(0,3)。连连接接A、B两点得到约束两点得到约束 1/3 x1+1/3 x2 1 所代表的半平面所代表的半平面 的边界的边界:1/3 x1+1/3 x2 1,即直线即直线AB。12345678912345(1/3)x
6、1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能象限象限象限象限象限象限象限象限如何确定是哪如何确定是哪个半平面?个半平面?为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 两个约束条件两个约束条件及非负条件及非负条件x1,x2 0所代表的公共部分所代表的公共部分图中黄色区域,就是满足所有约束条图中黄色区域,就是满足所有约束条件和非负条件的点的集合,即件和非负条件的点的集合,即可行域
7、可行域。在。在这个区域中的每一个点都对应着一个可行这个区域中的每一个点都对应着一个可行的生产方案。的生产方案。第第二二个个约约束束条条件件的边界的边界 直线直线CD:1/3x1+4/3 x2=312345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 令令 Z=2x1+3x2=c,其其中中c c为为为为任任任任选选选选的的的的一一一一个个个个常常常常数数数数,在在图图中中画画出出直直线线 2x1+3x2=c,这这
8、条条直直线线上上的的点点即即对对应应着着一一个个可可行的生产方案,即使两种产品的总利润达到行的生产方案,即使两种产品的总利润达到c。这这样样的的直直线线有有无无数数条条,而而且且相相互互平平行行,称称这这样样的的直直线线为为目目目目标标标标函函函函数数数数等等等等值值值值线线线线。只只只只要要要要画画出出两两两两条条条条目目目目标标标标函函函函数数数数等等等等值值值值线线线线,比如令比如令c0和和c=6,就能看出,就能看出 目标函数值递增的方向目标函数值递增的方向目标函数值递增的方向目标函数值递增的方向,用用箭头标出箭头标出箭头标出箭头标出这个方向。这个方向。图中两条虚线图中两条虚线 l1和和
9、l2就就分别代表分别代表 目标函数等值线目标函数等值线 2x1+3x2=0 和和 2x1+3x2=6,箭头表示使两种产品的总利润递增的方向。箭头表示使两种产品的总利润递增的方向。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 沿着箭头沿着箭头沿着箭头沿着箭头的方向的方向平移平移平移平移目标函数等值线,使其目标函数等值线,使其达到达到达到达到可行域中的最远点可行域中的最远点可行域中的最远点可行域中的最远点
10、E E,E点就是要求的最优点,它对应点就是要求的最优点,它对应的相应坐标的相应坐标 x1=1,x2=2 就是最有利的产品组合,即生就是最有利的产品组合,即生产产A产品产品1吨,吨,B产品产品2吨能使两种产品的总利润达到最吨能使两种产品的总利润达到最大值大值 Zmax=2 1+3 2=8(千元),(千元),x x1 1=1,x=1,x2 2=2=2就是线就是线性规划模型的性规划模型的最优解最优解最优解最优解,Zmax=8Zmax=8就是相应的目标函数就是相应的目标函数就是相应的目标函数就是相应的目标函数最优值最优值最优值最优值。12345678912345(1/3)x1+(4/3)x2=3(1/
11、3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 尽尽尽尽管管管管最最最最优优优优点点点点的的的的对对对对应应应应坐坐坐坐标标标标可可可可以以以以直直直直接接接接从从从从图图图图中中中中给给给给出出出出,但但但但是是是是在在在在大大大大多多多多数数数数情情情情况况况况下下下下,对对对对实实实实际际际际问问问问题题题题精精精精确确确确地地地地看看看看出出出出一一一一个个个个解解解解答答答答是是是是比比比比较较较较困困困困难难难难的的的的。所所所所以以以以,通通通通常常常常总
12、总总总是是是是用用用用解解解解联联联联立立立立方方方方程程程程的的的的方方方方法法法法求求求求出出出出最最最最优优优优解解解解的的的的精精精精确值。确值。确值。确值。比比比比如如如如E E点点点点对对对对应应应应的的的的坐坐坐坐标标标标值值值值我我我我们们们们可可可可以以以以通通通通过过过过求求求求解解解解下下下下面面面面的的的的联联联联立立立立方方方方程程程程,即即即即求求求求直直直直线线线线ABAB和和和和CDCD的的的的交交交交点来求得。点来求得。点来求得。点来求得。直线直线直线直线AB:1/3xAB:1/3x1 1+1/3x+1/3x2 2=1=1 直线直线直线直线CD:1/3xCD:
13、1/3x1 1+4/3x+4/3x2 2=3=3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2(3,0)C=6(9,0)(0,9/4)E E(1 1,2 2)C=0(0,3)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例1-2 用图解法求解下面的用图解法求解下面的线性规划问题:线性规划问题:复习直线方程:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中
14、小学图书室育人功能12345643215OX2X1X1-x2=2-x1+2x2=2x1+x2=4BCFADZ=0Z=10Z=14为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能对偶规划对偶规划 顺便提及,每一个线性规划都有一个顺便提及,每一个线性规划都有一个“影像影像”(一个伴生的线性规划),称之为线性规划的(一个伴生的线性规划),称之为线性规划的对对对对偶规划偶规划偶规划偶规划。当建立一个线性规划并达到最优目标值时,。当建立一个线性规划并达到最优目标值时,同时也就解出了对偶规划并达到了另一个不同意义同时也就解出了对偶规划并达到了另
15、一个不同意义的目标。的目标。如例如例1-1是寻求一个生产计划方案,使得在劳动是寻求一个生产计划方案,使得在劳动力和原材料可能供应的范围内,产品的总利润最大,力和原材料可能供应的范围内,产品的总利润最大,它的对偶问题就是一个价格系统,使在平衡了劳动它的对偶问题就是一个价格系统,使在平衡了劳动力和原材料的直接成本后,所确定的价格系统最具力和原材料的直接成本后,所确定的价格系统最具有竞争力。有竞争力。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例1-1的对偶规划如下的对偶规划如下:为深入学习习近平新时代中国特色社会主义思想和党的十九
16、大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 它它的的图图解解见见右右图图。其其中中L1和和L2分分别别为为两两个个约约束束半半平平面面的的边边界界,虚虚线线为为目目标标函函数数等等值值线线,可可行行域域为为图图中中阴阴影影部部分分,沿沿着着与与箭箭头头(目目标标函函数数值值递递减减的的方方向向)的方向的方向平移目标函数等值线平移目标函数等值线(注意:对偶规划中(注意:对偶规划中 要求对目标函数极小化)要求对目标函数极小化)得得最优点为最优点为最优点为最优点为E E,其其对应坐标为对应坐标为对应坐标为对应坐标为 y y1 1=5,y=5,y2 2=1=1 Wmin=5+31=83
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 部分 线性规划 图解法 ppt 课件
限制150内