第一章1.2.1 线性规划问题的图解法

一、线性规划的图解法－－－解的几何表示1．什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2.图解法举例实施图解法，以求出最优生产计划（最优解）,给出最优值。12max23Zxx12121228416412,0xxxxxx≤≤≤≥例1-1由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。第一步：建立平面直角坐标系标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品A的产量，用x2轴表示产品B的产量。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。第四步：最优解带入目标函数，得出最优值。约束条件的图解:每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。?以第一个约束条件:为例,说明图解过程。怎麽画边界怎麽确定半平面1228xx≤代表一个半平面其边界:x1+2x2=8x1+2x2=8及x1，x2≥0△AOB点A、B连线AB经济含义？△A0B1228xx≤1203x24123x185678221xxQ4BA点A(8,0)：连接AB：设备全部占用所生产Ⅰ、Ⅱ数量对应的点的集合。全部的设备都用来生产Ⅰ产品而不生产Ⅱ产品,那么Ⅰ产品的最大可能产量为8台,计算过程为：x1+2×08x18△Ａ0B：设备没有全部占用所生产Ⅰ、Ⅱ数量对应的点的集合。1203x24123x185678221xxQ4BA约束条件及非负条件x1,x20代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。另两个约束条件的边界直线CD、EF:4x1≤16，4x2≤121242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就是目标函数最优值。沿着箭头方向平移目标函数等值线，达到可行域中的最远点c,c点就是最优点;最优点1242x1641x85678221xxx1A3x2BCDE4123102F尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如C点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:x1+2x2=8直线CD:4x1=1612121228416412,0xxxxxx≤≤≤≥12max23Zxx最优点1242x1641x85678221xxx1A3x2BCDE4123102F将例1-1稍作改动形成案例1，仍使用图解法来求解。（案例1）某工厂生产A、B、C三种产品，每吨的利润分别为2000元、3000元、1000元，生产单位产品所需的工时及原材料如表1-2所示。应如何制定日生产计划，使三种产品的总利润最大？表1-2生产单位产品所需的工时及原材料表12140材料B（kg）16104材料A（kg）8121设备（台）资源限量ⅢⅡⅠ产品资源MaxZ=2x1+3x2+x3s.t0x,x,x12x+4x16x+4x8x+2x+x3213231321设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。结果有唯一最优解可行域是一个非空有界区域用图解法求解线性规划的各种可能的结果可行域有几种可能?解有几种可能?讨论唯一最优解例1-3将例1-1中目标要求改为极小化，目标函数和约束条件均不变，则可行域与例1-1相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是有唯一最优解x1=4,x2=2,对应着图1-6中的坐标原点。无穷多个最优解{c1,c2}12max23Zxx12121228416412,0xxxxxx≤≤≤≥212maxxxZ85678221xxx13x24123102BA沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合。结果表明，该线性规划有无穷多个最优解－－线段AB上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=14。无界解121212242,0xxxxxx≤≤≥12maxZxx2406x212543x1如图中可行域是一个无界区域，如阴影区所示。虚线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。这种情况通常称为无“有限最优解”或“最优解无界”。如果一个实际问题抽象成像例1-4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大。此时应重新检查和修改模型，否则就没有实际意义。注意，对于无界可行域的情况，也可能有唯一最优解或无穷多个最优解。