图形分析法对单纯形法的有限可代替性

刘雪晖 王中兴

（1、辽宁现代服务职业技术学院，辽宁 沈阳 110164 2、沈阳职业技术学院，辽宁 沈阳 110164）

1 引言

生产活动要遵循最大经济收益的原则来进行，这就要用线性规划知识来分析。如一律地都采用线性规划的知识来处理时，工作量就会很大。因而要有针对性的采用方便的方法来进行分析。本文给出一类生产规划问题中用图形分析法代替线性规划中单纯形法的方法。

2 问题的提出用实例

有多种产品同时生产时，每个产品的产能消耗和经济收益不同，因而就要对在一定成本（资源）的前提下对所有产品进行合理的资源（产量）分配，使到整体经济效益的最大化。这一类问题，习惯采用线性规划中的常用的单纯形法来求解。对于同时生产两种或三种产品的情形，采用单纯形法来求解非常烦琐。如果我们选择图形分析法，工作量上可减少一半，答案也精确。我们来看一个简单实例。

某公司生产甲、乙两种产品。生产每吨所需资源一、资源二和资源三消耗如下：

根据条件式（5），满足（1）～（5）的点，必在 x轴的上方、y轴的右边，即第一象限内。

在上图坐标系上，分别以方程

作约束直线 A1A2、B1B2、C1C2。

按条件式（1）、（2）、（3），欲求之点必在五边形OA1FEC2内（图示阴影部分）。

????????????????????? ?? ?? ?????? ?：? ?? ：?

已知，生产每吨甲产品和乙产品的经济收益分别是7万元和12万元。公司有资源一、二、三分别300、360、200。怎样安排甲、乙两种产品的生产计划才能获得最大的经济收益？

假设计划生产甲、乙两种产品分别为 、吨。故有资源分配满足于下列各式：

于是问题就成为求出一组x值和y值，使之既能满足式（1）、（2）、（3）和式（5）的约束条件，双能使式（4）的目标函数W达到最大。在没有线性规划方面的知识时，敢可用图形分析法来代替线性规划中的单纯形法来解决此问题。

在直角坐标系xOy上，用x轴代表甲产品的产量；用y轴代表乙产品的产量。

可求得五边形OA1FEC2五个顶点的坐标分别为：

在（4）式中，令

则

由（6）式得：

经过A1的直线为

经过C2的直线为

由上图可知，五边形OA1FEC2在直线y+的上方和下方，其它直线均从其内部穿过，因此W在直线经过的点E(20，24)取得最大值。即：

即公司生产甲、乙两种产品各20吨、24吨时所创的经济收益最大。

代入（7）式得：

3 结论

例中W的最大值是在五边形OA1FEC2的顶点取得的，这并非偶然。因为经过多边形的一系列平行直线中，最下面的一条和最上面的一条必定经过多边形的顶点，所以要求出函数的最大值和最小值，只需把这个函数在相应的多边形的每一个顶点的数值计算出来。其中最大的就是函数的最大值；最小的也就是函数的最小值。此算法也适用同时生产三种产品的情形。只需以三个产品产量为坐标轴建立三维坐标系，分析若干个以各个资源条件作约束平面的平行平面，求出诸约束平面与三个坐标平面在第一象限围成的多面体顶点。计算方法相近，它对线性规划知识的依赖很低，快而精确。

[1]赵凤治，线性规划计算方法[M]，科学出版社..

[2]利奥尼德·尼森·瓦泽斯坦等，线性规划导论[M]，机械工业出版社.

[3]堵丁柱等，计算复杂性导论[M]，高等教育出版社.