1-2-第2部分-线性规划的图解法

二、线性规划的图解法－－－解的几何表示1．什么是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2.图解法举例实施图解法，以求出最优生产计划（最优解）。例1－1121212122311+13314..+3330,0MaxZxxxxstxxxx由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解了。第一步：建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品A的产量，用x2轴表示产品B的产量。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出最优解－－最优生产方案。约束条件的图解:每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。?以第一个约束条件1/3x1+1/3x21为例说明约束条件的图解过程。怎么画边界怎么确定半平面如果全部的劳动工时都用来生产A产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为：1/3x1+1/3×01x13这个结果对应着右图中的点A(3,0),同样我们可以找到B产品最大可能产量对应的点B(0,3)。连接A、B两点得到约束1/3x1+1/3x21所代表的半平面的边界:1/3x1+1/3x2＝1，即直线AB。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X2012yaxbx00ab00ab00ab00abⅠ象限Ⅱ象限Ⅲ象限Ⅳ象限如何确定是哪个半平面？1x2x两个约束条件及非负条件x1,x20所代表的公共部分－－图中黄色区域，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。第二个约束条件的边界－－直线CD:1/3x1+4/3x2=312345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20令Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c＝0和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点就是要求的最优点，它对应的相应坐标x1=1,x2=2就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值Zmax=21+32=8（千元），x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最优点ABCDEX1X20尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如E点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:1/3x1+1/3x2=1直线CD:1/3x1+4/3x2=30123456789x154321x2MaxZ=2x1+3x2st..1/3x+1/3x11/3x+4/3x3x,x0121212（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）例1-2用图解法求解下面的线性规划问题：121212121225422..20,0MaxZxxxxxxstxxxx1xyabykxbaxbyc复习直线方程：12345643215OX2X1X1-x2=2-x1+2x2=2x1+x2=4BCFADZ=0Z=10Z=14对偶规划顺便提及，每一个线性规划都有一个“影像”（一个伴生的线性规划），称之为线性规划的对偶规划。当建立一个线性规划并达到最优目标值时，同时也就解出了对偶规划并达到了另一个不同意义的目标。如例1-1是寻求一个生产计划方案，使得在劳动力和原材料可能供应的范围内，产品的总利润最大，它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力。例1-1的对偶规划如下：MinW=y1+3y2s.t1/3y+1/3y21/3y+4/3y3y,y0121212它的图解见右图。其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递减的方向）的方向平移目标函数等值线（注意：对偶规划中要求对目标函数极小化）得最优点为E,其对应坐标为y1=5,y2=1Wmin=5+3×1=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）某工厂生产A、B、C三种产品，每吨的利润分别为2000元、3000元、1000元，生产单位产品所需的工时及原材料如表1－2所示。若供应的原材料每天不超过3吨，所能利用的劳动力总工时是固定的，应如何制定日生产计划，使三种产品的总利润最大？表1－2生产单位产品所需的工时及原材料表生产每吨产品所需资源产品ABC所需工时占总工时比例1/31/31/3所需原材料（吨）1/34/37/3MaxZ=2x1+3x2+x3s.t1/3x+1/3x+1/3x11/3x+4/3x+7/3x3x,x,x0123123123设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。B点对应着该线性规划的最优解：X*=(1,2,0)T即x1=1（产品A的产量）x2=2（产品B的产量）x3=0（产品C的产量）此时可得产品最大总利润为：Zmax=8由右图可知，可行域为凸五面体OABCDE,粗虚线所围平面为目标函数等值面，平移目标函数等值面得最优点为B点。结论从上面用图解法求解案例1的过程中明显感觉到对具有三个决策变量的线性规划进行图解就麻烦得多了。因此，尽管图解法具有简单、直观的优点，但它的使用是有局限性的，对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解，而对含有三个及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法－－单纯形法来进行求解，这将在§1-3节加以介绍。例1-1和案例1所描述的都是有唯一最优解且可行域是一个非空有界区域的情况。实际上，可行域不仅仅只有这一种可能，解的情况也是各种各样的。讨论用图解法求解线性规划的各种可能的结果无穷多个最优解例1－2maxZ=x1+x2s.t1/3x+1/3x11/3x+4/3x3x,x0121212(1/3)X1+(4/3)X2=3(1/3)X1+(1/3)X2=1ABCD12345678912345X1X20该线性规划的可行域为上图中四边形OAED（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界－－线段AE重合，这个结果表明，该线性规划有无穷多个最优解－－线段AE上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=3。唯一最优解例1-3将例1-1中目标要求改为极小化，目标函数和约束条件均不变，则可行域与例1-1相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是有唯一最优解x1=0,x2=0,对应着图1-6中的坐标原点。无界解例1-4maxZ=x1+2x2s.t-2x+x1x,x01212-2X1+X2=1AB12345612345X1X20本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。这种情况通常称为无“有限最优解”或“最优解无界”。如果一个实际问题抽象成像例1－4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。注意，对于无界可行域的情况，也可能有唯一最优解或无穷多个最优解。比如目标要求为minZ=x1+2x2或maxZ=－2x1+x2，而约束条件不变的例子。x1x2综上，用图解法求解线性规划时，各种求解结果与各种类型的可行域之间的对应关系可以用下图加以描述：解的类型可行域类型唯一最优解无穷多个最优解非空有界最优解无界无界（无“有限最优解”）无解空集（不存在可行域）用图解法求解下面的线性规划0,2224..522121212121xxxxxxxxtsxxMaxZ①画约束条件1,2；画约束条件3并标明可行域；画目标函数等值线；说明如何得到最优解,算出相应的目标函数最优值。课堂练习1-3(2,2)12345x1X2543210C=2C=10a,b,cd,e4、用图解法求解线性规划时需特别注意：第一、线性规划的可行域一定是凸多边形或凸多面体，所以下图中所示阴影区不可能是某个线性规划的可行域，而所示阴影区则有可能。第二、目标函数Z=ax1+bx2的值递增的方向与系数a、b有关下图表示目标函数值递增方向与其系数a、b的关系，其中箭头所指为目标函数值递增的方向。a0，b0ba0，b0aa0，b0a0，b0图解法小结使用条件：仅有两个至多不超过三个决策变量的线性规划。基本步骤：第一步－－建立平面直角坐标系；第二步－－根据约束条件和非负条件画出可行域。第三步－－作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：简单、直观但有局限性。第一次作业——P47习题1：4(1)；5(2);交作业时间：下周四(根据以往作业情况，可免)