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

二、 线性规划的图解法 －－－解的几何表示 2. 图解法举例 实施图解法，以求出最优生产计划（最优解）。 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解了。 如果全部的劳动工时都用来生产A 产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为： 1/3x1+1/3×0?1 ?x1?3 这个结果对应着右图中的点A(3,0),同样我们可以找到B产品最大可能产量对应的点B(0,3)。连接A、B两点得到约束 1/3 x1+1/3 x2 ?1 所代表的半平面 的边界: 1/3 x1+1/3 x2 ＝1， 即直线AB。 两个约束条件及非负条件x1,x2 ?0所代表的公共部分－－图中黄色区域，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。 第二个约束条件的边界－－ 直线CD: 1/3x1+4/3 x2 =3 令 Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。 这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c＝0和c=6，就能看出 目标函数值递增的方向， 用箭头标出这个方向。 图中两条虚线 l1和l2就 分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头表示使两种产品的总利润递增的方向。 沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E, E点就是要求的最优点，它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值 Zmax=2?1+3?2=8（千元），x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。 对偶规划 顺便提及，每一个线性规划都有一个“影像”（一个伴生的线性规划），称之为线性规划的对偶规划。当建立一个线性规划并达到最优目标值时，同时也就解出了对偶规划并达到了另一个不同意义的目标。 如例1-1是寻求一个生产计划方案，使得在劳动力和原材料可能供应的范围内，产品的总利润最大，它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力。 例1-1的对偶规划如下： 它的图解见右图。其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递减的方向）的方向平移目标函数等值线（注意：对偶规划中 要求对目标函数极小化） 得最优点为E, 其对应坐标为 y1=5,y2=1 Wmin=5+3×1=8 将例1-1稍作改动形成案例1，仍使用图解法来求解。 （案例1）某工厂生产A、B、C三种产品，每吨的利润分别为2000元、3000元、1000元，生产单位产品所需的工时及原材料如表1－2所示。若供应的原材料每天不超过3吨，所能利用的劳动力总工时是固定的，应如何制定日生产计划，使三种产品的总利润最大？ B点对应着该线性规划的最优解： X*=(1,2,0)T 即 x1=1 （产品A的产量） x2=2 （产品B的产量） x3=0 （产品C的产量） 此时可得产品最大总利润为： Zmax=8 结 论 从上面用图解法求解案例1的过程中明显感觉到对具有三个决策变量的线性规划进行图解就麻烦得多了。因此，尽管图解法具有简单、直观的优点，但它的使用是有局限性的，对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解，而对含有三个及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法－－单纯形法来进行求解，这将在§1-3节加以介绍。 例1-1和案例1所描述的都是有唯一最优解且可行域是一个非空有界区域的情况。实际上，可行域不仅仅只有