第2部分线性规划的图解法ppt课件.ppt

为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二、二、 线性规划的图解法线性规划的图解法 解的几何表示解的几何表示 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1 1什么是图解法？什么是图解法？ 线性规划的图解法就是用线性规划的图解法就是用几何作图几何作图的的方法方法分析并求出其最优解分析并求出其最优解的过程 求解的思路是：求解的思路是：先先将约束条件加以图将约束条件加以图解，求得满足约束条件的解的集合（即可解，求得满足约束条件的解的集合（即可行域）行域），然后然后结合目标函数的要求从可行结合目标函数的要求从可行域中找出最优解域中找出最优解为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2. 2. 图解法举例图解法举例 实施图解法，以求出最优最优生产计划（最优解最优解） 例11为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解了。

第一步：第一步：建立平面直角坐标系，标出坐标原坐标原点点, 坐标轴的指向坐标轴的指向和单位长度单位长度 用x1轴表示产品A的产量，用x2轴表示产品B的产量 第二步：第二步：对约束条件加以图解 第三步：第三步：画出目标函数等值线，结合目标函数的要求求出最优解最优生产方案为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束条件的图解约束条件的图解: : 每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边先画出该半平面的边界界，然后确定是哪个半平面确定是哪个半平面 ? 以第一个约束条件 1/3 x1+1/3 x2 1 为例 说明约束条件的图解过程 怎么画边界怎么画边界 怎么确定怎么确定 半平面半平面为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 如果全部的劳动工时都用来生产A 产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为： 1/3x1+1/301 x13 这个结果对应着右图中的点A(3,0),同样我们可以找到B产品最大可能产量对应的点B(0,3)。

连接A、B两点得到约束 1/3 x1+1/3 x2 1 所代表的半平面 的边界: 1/3 x1+1/3 x2 1， 即直线AB12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 象限象限象限象限象限象限象限象限如何确定是哪如何确定是哪个半平面？个半平面？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 两个约束条件两个约束条件及非负条件及非负条件x x1 1,x ,x2 2 0 0所代表的公共部分所代表的公共部分图中黄色区域，就是满足所有约束条图中黄色区域，就是满足所有约束条件和非负条件的点的集合，即件和非负条件的点的集合，即可行域可行域在这个区域中的每一个点都对应着一个可行这个区域中的每一个点都对应着一个可行的生产方案的生产方案 第二个约束条件第二个约束条件的边界的边界 直线直线CD: CD: 1/3x 1/3x1 1+4/3 x+4/3 x2 2 =3 =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,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。

这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线目标函数等值线只要只要画出两条目标函数等值线两条目标函数等值线，比如令c0和c=6，就能看出 目标函数值递增的方向目标函数值递增的方向， 用箭头标出箭头标出这个方向 图中两条虚线 l1和l2就分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头表示使两种产品的总利润递增的方向12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 沿着箭头沿着箭头的方向平移平移目标函数等值线，使其达到达到可行域中的最远点可行域中的最远点E E, E点就是要求的最优点，它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值 Zmax=21+32=8（千元），x x1 1=1,x=1,x2 2=2=2就是线性规划模型的最优解最优解，Zmax=8Zmax=8就是相应的目标函数就是相应的目标函数最优值最优值。

12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 尽管最优点的对应坐标可以直接从图中尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的所以，通确地看出一个解答是比较困难的所以，通常总是常总是用解联立方程的方法求出最优解的精用解联立方程的方法求出最优解的精确值 比如比如E E点对应的坐标值我们可以通过求点对应的坐标值我们可以通过求解下面的联立方程，即求直线解下面的联立方程，即求直线ABAB和和CDCD的交的交点来求得点来求得 直线直线AB: 1/3xAB: 1/3x1 1+1/3x+1/3x2 2=1=1 直线直线CD: 1/3xCD: 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 用图解法求解下面的线性规划问题：复习直线方程：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能12345643215OX2X1X1-x2=2-x1+2x2=2x1+x2=4BCFADZ=0Z=10Z=14为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能对偶规划对偶规划 顺便提及，每一个线性规划都有一个“影像”（一个伴生的线性规划），称之为线性规划的对偶规对偶规划划。

当建立一个线性规划并达到最优目标值时，同时也就解出了对偶规划并达到了另一个不同意义的目标 如例1-1是寻求一个生产计划方案，使得在劳动力和原材料可能供应的范围内，产品的总利润最大，它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例1-1的对偶规划如下： 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 它的图解见右图其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递减的方向）的方向平移目标函数等值线（注意：对偶规划中 要求对目标函数极小化） 得最优点为最优点为E E, 其对应坐标为对应坐标为 y y1 1=5,y=5,y2 2=1=1 Wmin=5+31=83(1/3)y1+(4/3)y2=3(1/3)y1+(1/3)y2=2ECDAB1234567891245最优点y1y20L2L1为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 其经济意义：对包工工时及原材料的单位定对包工工时及原材料的单位定价（影子价格）价（影子价格），若工厂自己不生产产品A和B，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）力（包工及原材料的总价格最低）。

可以看到，当原问题和对偶问题都取得最优解时，这对线性规划对应的目标函数值是相等的： Zmax=Wmin=8 考察原问题和对偶问题的解，给做决策的管理者另一个自由度，比如除了研究怎样利用已有的资源以取得最大利润的同时，还可以进一步探进一步探讨讨怎样通过增加更多的资源或使用不同类型的资怎样通过增加更多的资源或使用不同类型的资源来增加利润源来增加利润为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能将例1-1稍作改动形成案例1，仍使用图解法来求解 （案例（案例1 1）某工厂生产）某工厂生产A A、B B、C C三种产品，三种产品，每吨的利润分别为每吨的利润分别为20002000元、元、30003000元、元、10001000元，元，生产单位产品所需的工时及原材料如表生产单位产品所需的工时及原材料如表1 12 2所所示若供应的原材料每天不超过示若供应的原材料每天不超过3 3吨，所能利吨，所能利用的劳动力总工时是固定的，应如何制定日生用的劳动力总工时是固定的，应如何制定日生产计划，使三种产品的总利润最大？产计划，使三种产品的总利润最大？ 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 设三种产品的产量分别是设三种产品的产量分别是x x1 1、x x2 2、x x3 3吨，由于有三个决策变量，用图吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首解法求解下面的线性规划时，必须首先建立空间直角坐标系。

先建立空间直角坐标系为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 B点对应着该线性规划的最优解： X*=(1,2,0)T 即 x1=1 （产品A的产量） x2=2 （产品B的产量） x3=0 （产品C的产量） 此时可得产品最大总利润为： Zmax=8 由右图可知，可行域为凸五面体OABCDE,粗虚线所围平面为目标函数等值面，平移目标函数等值面得最优点为B点 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能结结 论论 从上面用图解法求解案例1的过程中明显感觉到对具有三个决策变量的线性规划进行图解就麻烦得多了因此，尽管图解法具有简单、直观的优点，但它的使用是有局限性的，对仅含有两个至多不超过三个决策变对仅含有两个至多不超过三个决策变量。