線性規(guī)劃模型的計算機(jī)求解

羅 平

（興義民族師范學(xué)院， 貴州 興義 562400）

線性規(guī)劃模型的計算機(jī)求解

羅 平

（興義民族師范學(xué)院， 貴州 興義 562400）

線性規(guī)劃是運籌學(xué)的一個重要分支，在經(jīng)濟(jì)、管理等領(lǐng)域有著非常廣泛的應(yīng)用，通過對某一特定的線性規(guī)劃問題，建立線性規(guī)劃模型并分別用Lingdo、Mathematical、Matlab軟件及office軟件中的Excel進(jìn)行求解，并對四種軟件進(jìn)行對比分析，發(fā)現(xiàn)Lingdo、Mathematical、Matlab軟件是專業(yè)化的軟件，需要具備一定的數(shù)學(xué)基礎(chǔ)，Excel軟件是大眾化的軟件，更便于一般人掌握。

線性規(guī)劃；模型；計算機(jī)

線性規(guī)劃是運籌學(xué)的重要分支，它是一門實用性很強的應(yīng)用數(shù)學(xué)學(xué)科，這門學(xué)科產(chǎn)生于20世紀(jì)30年代。1939年，前蘇聯(lián)數(shù)學(xué)家康拓洛維奇在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中，最早提出和研究了線性規(guī)劃問題。1947年美國數(shù)學(xué)家丹澤格提出了一般的線性規(guī)劃模型和求解線性規(guī)劃的通用方法—單純形法，為這門學(xué)科奠定了基礎(chǔ)[1]。50年代后人們對線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于計算機(jī)科學(xué)與計算機(jī)技術(shù)的發(fā)展，使一些復(fù)雜的大型運籌學(xué)模型的求解成為可能，極大的推動了運籌學(xué)的發(fā)展。

運用單純形法雖然可以給出一般線性規(guī)劃的最優(yōu)解，也可以給出某些參數(shù)的靈敏度分析，但是決策變量較多時，計算量會非常大。因此借助計算機(jī)軟件，眾多的約束條件和決策變量的線性規(guī)劃問題的求解也能很快解出來。

本文我們將對某一類線性規(guī)劃問題，分別用Lingdo、Mathematical、matlab 及 Excel軟件來求解。

一、線性規(guī)劃模型的建立

1.線性規(guī)劃問題的提出

例[2]：某日化廠生產(chǎn)洗衣粉和洗滌劑。生產(chǎn)原料由市場供應(yīng)：每千克5元，供應(yīng)量無限制.該廠加工1kg原料可產(chǎn)出0.5kg普通洗衣粉和0.3kg普通洗滌劑.工廠還可以對普通洗衣粉級普通洗滌劑進(jìn)行精加工.加工1kg普通洗衣粉可得到0.5kg濃縮洗衣粉,加工1kg普通洗滌劑可產(chǎn)出0.25kg高級洗滌劑,加工示意圖見圖一.市場售價為每千克普通洗衣粉為8元;每千克濃縮洗衣粉為24元;每千克普通洗滌劑為12元;每千克高級洗滌劑為55元.每加工1kg原料的加工成本為1元，每千克精加工產(chǎn)品的加工成本為3元，工廠設(shè)備每天最多可處理4t原料,而對精加工沒有限制.若市場對產(chǎn)品也沒有限制,問該廠如何安排生產(chǎn)能使每日利潤最大？

設(shè)每日生產(chǎn)普通洗衣粉的產(chǎn)量為x1kg,生產(chǎn)濃縮洗衣粉的產(chǎn)量為x2kg,生產(chǎn)普通洗滌劑的產(chǎn)量為x3kg,生產(chǎn)高級洗滌劑的產(chǎn)量為x4kg,每日加工原料為x5kg.該問題的數(shù)學(xué)模型如為：

二、線性規(guī)劃模型的求解

1.Lindo軟件求解

Lindo是美國Lindo系統(tǒng)公司開發(fā)的一套專門用于求解最優(yōu)化問題的軟件包。由于Lindo執(zhí)行速度很快、易于方便輸入、求解和分析數(shù)學(xué)規(guī)劃問題。因此在數(shù)學(xué)、科研和工業(yè)界得到廣泛應(yīng)用。常用于求解線性規(guī)劃、整數(shù)規(guī)劃、二次規(guī)劃問題。按照Lindo格式要求輸入：

點擊solve求解得：x1=0,x2=1000,x3=0,x4=300,x5=4000,利潤z=12600元.

2.Mathematical軟件求解[3]

函數(shù)LinearProgramming[c,m]用來求解如下形式的線性規(guī)劃問題.

從上面的形式可以看出,如果參數(shù)只寫出[c,m,b]的形式，那么只能求解約束條件是的≥模型.對于一般模型，將函數(shù)中參數(shù)b改寫成{bi,si}，即LinearProgramming[c,m,{bi,si}]的形式,就可以求解.LinearProgramming[c,m,{bi,si}]形式的意思是當(dāng)si=1 時，表示 mx≥bi；當(dāng) si=0 時，表示 mx=bi；當(dāng) si=-1時，表示mx≤bi.

因此，對于建立的模型，在平臺中輸入函數(shù)后，按：組合鍵“shift+回車”得出結(jié)果如下：結(jié)果表示x1=0,x2=1000,x3=0,x4=300,x5=4000.

3.Matlab軟件求解

在Matlab中函數(shù)linprog（）是求解線性規(guī)劃問題的函數(shù)，Matlab中以求極小為標(biāo)準(zhǔn)。函數(shù)linprog的具體格式為：

其中X是解向量，c是目標(biāo)函數(shù)的系數(shù)構(gòu)成的向量，A是系數(shù)矩陣，b是右端向量。Aeq和Beq表示線性規(guī)劃中等式的系數(shù)矩陣和右端向量。LB和UB是約束變量的下界和上界向量，X0是給定的變量的初始值，Opertions為控制規(guī)劃的參數(shù)系列。

在matlab7.0中編程計算如下：

運行后結(jié)果為：x=（0，1000，0，300，4000）T.表明普通洗衣粉不生產(chǎn),生產(chǎn)濃縮洗衣粉的1000kg,普通洗滌劑不生產(chǎn),生產(chǎn)高級洗滌劑300kg,每日加工原料為4000kg.

4.EXCEL求解

Excel能對不同形式的線性規(guī)劃問題求解。對本例而言，可以用表1表示成計算機(jī)能夠識別的形式。

表1

輸入公式：G3=SUMPRODUCT（B3:F3,B10:F10）

G4=SUMPRODUCT（B4:F4,B10:F10）

G5=SUMPRODUCT（B5:F5,B10:F10）

G6=SUMPRODUCT（B6:F6,B10:F10）

SUMPRODUCT表示對應(yīng)的乘積之和。

選擇工具菜單欄中的規(guī)劃求解，在彈出的對話框中，完成以下設(shè)置：

（1）定一個目標(biāo)單元格，它包含計算目標(biāo)函數(shù)值的公式（本例中為G3）。

（2）對目標(biāo)單元格選擇求最大還是最小。

（3）確定變量所在的單元格。

（4）確定約束條件

參數(shù)設(shè)置完之后，點擊求解按鈕，求出最優(yōu)解為

x1 x2 x3 x4 x5目標(biāo)函數(shù)系數(shù)約束條件系數(shù)總計 限制8 21 12 52 -6 12600-1-2000.50＝0 00-1-40.30＝0 0 0 0 0 14000＜4000輸出：解決方案x1 x2 x3 x4 x5 z 0 1000 0 300 4000

三、結(jié)論

通過以上四種軟件求解，我們發(fā)現(xiàn)計算結(jié)果都是相同的，普通洗衣粉不生產(chǎn),生產(chǎn)濃縮洗衣粉的1000kg,普通洗滌劑不生產(chǎn),生產(chǎn)高級洗滌劑300kg,每日加工原料為4000kg.獲得最大利潤為12600元。對比四種軟件，Lindo求解只需要按格式要求直接輸入模型就可以求解出結(jié)果；Mathematical軟件和Matlab軟件共同點是調(diào)用函數(shù)命令求解，按照函數(shù)格式要求輸入向量求解，但是對比計算發(fā)現(xiàn)Mathematical的線性規(guī)劃函數(shù)格式要求比Matlab軟件簡單；Excel求解是在工作簿中來進(jìn)行，把模型轉(zhuǎn)化為計算機(jī)能識別的形式，點擊工具菜單欄中的規(guī)劃求解即可。Lindo、Mathematical、Exce不僅可以求最優(yōu)解，還可以求目標(biāo)函數(shù)值，Mathematical軟件只能求最優(yōu)解。Lindo、Mathematical、Matlab軟件是專業(yè)的數(shù)學(xué)軟件，必須具備一定的數(shù)學(xué)基礎(chǔ)，Excel是常用的辦公軟件,操作也是很簡單的，易于一般工作人員掌握。

總之，運用計算機(jī)求解運籌學(xué)線性規(guī)劃模型，簡單、高效、實用。伴隨著社會和計算機(jī)技術(shù)的發(fā)展，運用計算機(jī)求解運籌學(xué)線性規(guī)劃模型將逐步取代繁瑣的手工計算，成為管理者實施現(xiàn)代化管理的重要手段。

[1]胡運權(quán).運籌學(xué)基礎(chǔ)及應(yīng)用(第六版)[M].高等教育出版社,2014.

[2]何堅勇.運籌學(xué)基礎(chǔ)[M].清華大學(xué)出版社,2008.

[3]郭志軍.線性規(guī)劃模型的建立及Mathematica求解[J].長沙大學(xué)學(xué)報，2010（5）.

The Computer Solving in Linear Programming Model

LUO Ping
（Xingyi Normal University for Nationalities,Xingyi,Guizhou,562400,China）

Linear programming which has a very wide range of applications in the economic and management, is an important branch of operational research. In accordance with a given linear programming problem, linear programming model is set up .We will solve the model respectively by Lindo, Mathematical, Matlab, software and office software of Excel. It reflects the diversity of computer solving method of linear programming computer

linear programming；model；computer

1009—0673（2015）01—0121—04

C931.1

A

2014—12—22

羅平（1983— ），女，云南昆明人，興義民族師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院講師，碩士研究生，主要從事運籌學(xué)教學(xué)和研究。

責(zé)任編輯：彭光明