第1章 2 线性规划问题的图解法

一、线性规划的图解法－－－解的几何表示1．什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2.图解法举例12max23Zxx12121228416412,0xxxxxx≤≤≤≥例1-19—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+2x28(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x204x1164x212图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216可行域图解法9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1+2x284x1164x216可行域BCDEA图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEA2x1+3x2=6图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEAx1+2x2=84x1=16最优解(4,2)图解法图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。约束条件及非负条件x1,x20代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案（可行解）。1242x1641x85678221xxx1A3x2BCDE4123102F令Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线2x1+3x2=c,即对应着一组可行的生产结果，使两种产品的总利润达到c。这样的直线有无数条，且相互平行，称这样的直线为目标函数等值线。只要画两条目标函数等值线，如令c＝0和c=6，可看出目标函数值变化的方向,即虚线l1和l2,箭头为产品的总利润递增的方向。最优点1242x1641x85678221xxx1A3x2BCDE4123102F对应坐标x1=4,x2=2是最佳的产品组合,[4,2]T就是线性规划模型的最优解使产品的总利润达到最大值maxZ=24+32=14就是目标函数最优值。沿着箭头方向平移目标函数等值线，达到可行域中的最远点E,E点就是最优点;最优点1242x1641x85678221xxx1A3x2BCDE4123102F尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如C点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:x1+2x2=8直线CD:4x1=16总结线性规划问题的有关概念（1）可行解：满足约束条件与非负限制的变量的值，称为可行解。（2）可行域：全部可行解的集合称为可行域。（3）最优解：使目标函数取得最优值的可行解，称为最优解。maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0练习1maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解（4/3，14/3）64-860x1x2练习1答案练习2：某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+x2=600x1x22x1+3x2=1200100200300400500600100200300400600500x1=125x1+x2=3502x1+x2=600x1x2Q2x1+3x2=12002x1+3x2=9002x1+3x2=800用图解法求解线性规划的各种可能的结果可行域有几种可能?解有几种可能?讨论3、线性规划问题求解的几种可能结果(a)唯一最优解目标函数MaxZ=2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1、x2≥0x26—5—4—3—2—1—0|||||||||123456789x1(b)无穷多最优解6—5—4—3—2—1—0x2|||||||||123456789x1线性规划问题求解的几种可能结果目标函数MaxZ=X1+2X2约束条件X1+2X2≤84X1≤164X2≤12X1、X2≥0无穷多个最优解{c1,c2}12max23Zxx12121228416412,0xxxxxx≤≤≤≥212maxxxZ85678221xxx13x24123102BA沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合。结果表明，该线性规划有无穷多个最优解－－线段AB上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=14。(c)无界解MaxZ=x1+x2s.t.-2x1+x24x1-x22x1、x20x2x1线性规划问题求解的几种可能结果该可行域无界，目标函数值可增加到无穷大42如图中可行域是一个无界区域，如阴影区所示。虚线为目标函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。如果一个实际问题抽象成像上面这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，这说明模型忽略了一些必要的约束条件。此时应重新检查和修改模型，否则就没有实际意义。(d)无可行解MaxZ=2x1+3x2s.t.x1+2x284x1164x212-2x1+x24x1、x20线性规划问题求解的几种可能结果该问题可行域为空集，即无可行解，也不存在最优解。85678221xxx13x24123102图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。