圖形分析法對(duì)單純形法的有限可代替性

劉雪暉 王中興

（1、遼寧現(xiàn)代服務(wù)職業(yè)技術(shù)學(xué)院，遼寧 沈陽 110164 2、沈陽職業(yè)技術(shù)學(xué)院，遼寧 沈陽 110164）

1 引言

生產(chǎn)活動(dòng)要遵循最大經(jīng)濟(jì)收益的原則來進(jìn)行，這就要用線性規(guī)劃知識(shí)來分析。如一律地都采用線性規(guī)劃的知識(shí)來處理時(shí)，工作量就會(huì)很大。因而要有針對(duì)性的采用方便的方法來進(jìn)行分析。本文給出一類生產(chǎn)規(guī)劃問題中用圖形分析法代替線性規(guī)劃中單純形法的方法。

2 問題的提出用實(shí)例

有多種產(chǎn)品同時(shí)生產(chǎn)時(shí)，每個(gè)產(chǎn)品的產(chǎn)能消耗和經(jīng)濟(jì)收益不同，因而就要對(duì)在一定成本（資源）的前提下對(duì)所有產(chǎn)品進(jìn)行合理的資源（產(chǎn)量）分配，使到整體經(jīng)濟(jì)效益的最大化。這一類問題，習(xí)慣采用線性規(guī)劃中的常用的單純形法來求解。對(duì)于同時(shí)生產(chǎn)兩種或三種產(chǎn)品的情形，采用單純形法來求解非常煩瑣。如果我們選擇圖形分析法，工作量上可減少一半，答案也精確。我們來看一個(gè)簡(jiǎn)單實(shí)例。

某公司生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)每噸所需資源一、資源二和資源三消耗如下：

根據(jù)條件式（5），滿足（1）～（5）的點(diǎn)，必在 x軸的上方、y軸的右邊，即第一象限內(nèi)。

在上圖坐標(biāo)系上，分別以方程

作約束直線 A1A2、B1B2、C1C2。

按條件式（1）、（2）、（3），欲求之點(diǎn)必在五邊形OA1FEC2內(nèi)（圖示陰影部分）。

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

已知，生產(chǎn)每噸甲產(chǎn)品和乙產(chǎn)品的經(jīng)濟(jì)收益分別是7萬元和12萬元。公司有資源一、二、三分別300、360、200。怎樣安排甲、乙兩種產(chǎn)品的生產(chǎn)計(jì)劃才能獲得最大的經(jīng)濟(jì)收益？

假設(shè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品分別為 、噸。故有資源分配滿足于下列各式：

于是問題就成為求出一組x值和y值，使之既能滿足式（1）、（2）、（3）和式（5）的約束條件，雙能使式（4）的目標(biāo)函數(shù)W達(dá)到最大。在沒有線性規(guī)劃方面的知識(shí)時(shí)，敢可用圖形分析法來代替線性規(guī)劃中的單純形法來解決此問題。

在直角坐標(biāo)系xOy上，用x軸代表甲產(chǎn)品的產(chǎn)量；用y軸代表乙產(chǎn)品的產(chǎn)量。

可求得五邊形OA1FEC2五個(gè)頂點(diǎn)的坐標(biāo)分別為：

在（4）式中，令

則

由（6）式得：

經(jīng)過A1的直線為

經(jīng)過C2的直線為

由上圖可知，五邊形OA1FEC2在直線y+的上方和下方，其它直線均從其內(nèi)部穿過，因此W在直線經(jīng)過的點(diǎn)E(20，24)取得最大值。即：

即公司生產(chǎn)甲、乙兩種產(chǎn)品各20噸、24噸時(shí)所創(chuàng)的經(jīng)濟(jì)收益最大。

代入（7）式得：

3 結(jié)論

例中W的最大值是在五邊形OA1FEC2的頂點(diǎn)取得的，這并非偶然。因?yàn)榻?jīng)過多邊形的一系列平行直線中，最下面的一條和最上面的一條必定經(jīng)過多邊形的頂點(diǎn)，所以要求出函數(shù)的最大值和最小值，只需把這個(gè)函數(shù)在相應(yīng)的多邊形的每一個(gè)頂點(diǎn)的數(shù)值計(jì)算出來。其中最大的就是函數(shù)的最大值；最小的也就是函數(shù)的最小值。此算法也適用同時(shí)生產(chǎn)三種產(chǎn)品的情形。只需以三個(gè)產(chǎn)品產(chǎn)量為坐標(biāo)軸建立三維坐標(biāo)系，分析若干個(gè)以各個(gè)資源條件作約束平面的平行平面，求出諸約束平面與三個(gè)坐標(biāo)平面在第一象限圍成的多面體頂點(diǎn)。計(jì)算方法相近，它對(duì)線性規(guī)劃知識(shí)的依賴很低，快而精確。

[1]趙鳳治，線性規(guī)劃計(jì)算方法[M]，科學(xué)出版社..

[2]利奧尼德·尼森·瓦澤斯坦等，線性規(guī)劃導(dǎo)論[M]，機(jī)械工業(yè)出版社.

[3]堵丁柱等，計(jì)算復(fù)雜性導(dǎo)論[M]，高等教育出版社.