第3章321 线性规划问题的图解法

1、 实施图解法，以求出实施图解法，以求出生产计生产计划划（）, 给出给出12max23Zxx12121228416412, 0 xxxxx x 例例3-1建立平面直角坐标系建立平面直角坐标系 标出坐标原点标出坐标原点, 坐标轴的指向和单位坐标轴的指向和单位长度。用长度。用x1轴表示产品轴表示产品A的产量，用的产量，用x2轴表示产品轴表示产品B的产量。的产量。对约束条件加以图解。对约束条件加以图解。 画出目标函数等值线，结合目标函数画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。的要求求出最优解：最优生产方案。最优解带入目标函数，得出最优值。最优解带入目标函数，得出最优值。 约束条

2、件的图解约束条件的图解: 每一个约束不等式在平面直角坐标系中每一个约束不等式在平面直角坐标系中都代表一个半平面，只要都代表一个半平面，只要，然后，然后。 ? 以第一个约束条件以第一个约束条件: 为例为例, 说明图解过程。说明图解过程。1228xx代表一个半平面代表一个半平面其边界其边界: x1+2 x2 =8x1+2 x2 =8及及x1，x2 0 AOB1228xx1203x24123x185678221 xxQ4设备全部占用所生产设备全部占用所生产、数量对应的点数量对应的点的集合。的集合。 全部的设备都用来生产全部的设备都用来生产产品而不生产产品而不生产产品产品,那么那么产品的最大可能产量为

3、产品的最大可能产量为8台台,计计算过程为：算过程为： x1+20 8 x1 8设备没有全部占用所设备没有全部占用所生产生产、数量对应数量对应的点的集合的点的集合。1203x2412 3x185 6 78221 xxQ4 1242x1641x85678221 xxx13x24123102 令令 Z=2x1+3x2=c, 其中其中，在图，在图 中画出直线中画出直线 2x1+3x2=c, 即对应着即对应着一个可行的生产结果，即使两种产品的总利润一个可行的生产结果，即使两种产品的总利润达到达到c。 这样的直线有无数条，且相互平行，称这样的直线有无数条，且相互平行，称这样的直线为这样的直线为。画两条画两

4、条目标函数目标函数，如令，如令 c0和和c=6，可看出，可看出, 即虚线即虚线 l1和和l2,箭头为产箭头为产 品的总利润递增的方向。品的总利润递增的方向。1242x1641x85678221 xxx13x24123102对应坐标对应坐标x1=4, x2=2 是最佳的产品组合是最佳的产品组合, 4,2T就是线性规划模型的就是线性规划模型的使产品的总利润达到最大值使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数就是目标函数方向方向目标函数等值线，达到目标函数等值线，达到, E点就是点就是1242x1641x85678221 xxx13x24123102 尽管最优点的对应坐标可以

5、直接从图中尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通确地看出一个解答是比较困难的。所以，通常总是常总是 比如比如C点对应的坐标值我们可以通过求点对应的坐标值我们可以通过求解下面的联立方程，即求直线解下面的联立方程，即求直线AB和和CD的交的交点来求得。点来求得。 直线直线AB: x1+2x2=8 直线直线CD: 4x1=1612121228416412, 0 xxxxx x12max23Zxx1242x1641x85678221 xxx13x24123102结果 用图解法求解线性规划的各种

6、可能的结果用图解法求解线性规划的各种可能的结果讨论讨论 12max23Zxx12121228416412, 0 xxxxx x212maxxxZ85678221xxx13x24123102 沿着箭头的方向平移目标函数等值线，沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将发现平移的最终结果是目标函数等值线将与可行域的一条边界线段与可行域的一条边界线段AB重合。重合。 结果表明，该线性规划有结果表明，该线性规划有线段线段AB上的所有点都是最优上的所有点都是最优点，它们都使目标函数取得相同的最大值点，它们都使目标函数取得相同的最大值Zmax=14。 121212242,0 xxxxx x12maxZxx2406x212543x1 如图中可行域是一个无界区域，如阴影区所示。如图中可行域是一个无界区域，如阴影区所示。虚线为目表函数等值线，沿着箭头指的方向平移可虚线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。以使目标函数值无限制地增大，但是找不到最优解。这种情况通常称为这种情况通常称为”。 如果一个实际问题抽象成像例如果一个实际问题抽象成像例1-4这样的线性规这样的线性规划模型，比如是一个生产计划问题，其经济含义就是划模型，比如是一个