姜遠(yuǎn)彥

摘 要：本文通過實(shí)例介紹運(yùn)用LINGO軟件求解線性規(guī)劃問題。

關(guān)鍵詞：線性規(guī)劃問題 LINGO軟件 求解

線性規(guī)劃是運(yùn)籌學(xué)中形成最早、最成熟的一個(gè)分支，是優(yōu)化理論最基礎(chǔ)的部分，也是運(yùn)籌學(xué)最核心的內(nèi)容之一。線性規(guī)劃主要是用來確定具有多個(gè)變量的線性函數(shù)，在變量滿足線性約束條件下的最優(yōu)解。目前廣泛應(yīng)用于工農(nóng)業(yè)、軍事、交通運(yùn)輸、決策管理、物流管理等領(lǐng)域，線性規(guī)劃的方法已經(jīng)成為求解各種優(yōu)化問題的主要方法。

1947 年丹捷格（G.B.Dantzig）提出的單純形方法是求解一般線性規(guī)劃問題的通用方法，對(duì)于數(shù)據(jù)簡(jiǎn)單的線性規(guī)劃問題用這種方法手工求解還是可行的，但對(duì)于數(shù)據(jù)較復(fù)雜的規(guī)劃問題手工求解就變得比較困難，計(jì)算量太大，容易出錯(cuò)，因此運(yùn)用計(jì)算機(jī)相關(guān)軟件求解線性

規(guī)劃問題便成為首選的方式。目前，已有多種軟件可提供線性規(guī)劃問題的計(jì)算機(jī)求解，其中包括專業(yè)優(yōu)化軟件LINDO/LINGO、WINQSB，具備強(qiáng)大計(jì)算功能的MATLAB、MATHEMATICA，以及具有規(guī)劃求解功能的EXCEL軟件。本文介紹運(yùn)用LINGO軟件來求解具體的線性規(guī)劃問題。

一、線性規(guī)劃基本概念

1.線性規(guī)劃的定義

線性規(guī)劃是指如何最有效或最佳地謀劃經(jīng)濟(jì)活動(dòng)。它所研究的問題有兩類：一類是指一定資源的條件下，達(dá)到最高產(chǎn)量、最高產(chǎn)值、最大利潤(rùn)；一類是，任務(wù)量一定，如何統(tǒng)籌安排，以最小的消耗去完成這項(xiàng)任務(wù)。如最低成本問題、最小投資、最短時(shí)間、最短距離等問題。前者是求最大值問題，后者是求最小值問題?？傊?，線性規(guī)劃是在一定限制條件下，求目標(biāo)函數(shù)最值的問題。

2.線性規(guī)劃三要素

（1）目標(biāo)函數(shù)最優(yōu)化——單一目標(biāo)、多重目標(biāo)問題如何處理？

（2）實(shí)現(xiàn)目標(biāo)的多種方法——若實(shí)現(xiàn)目標(biāo)只有一種方法不存在規(guī)劃問題。

（3）生產(chǎn)條件的約束——資源是有限的、資源無限不存在規(guī)劃問題。

3.線性規(guī)劃模型的基本結(jié)構(gòu)

（1）決策變量——未知數(shù)。它是通過模型計(jì)算來確定的決策因素。又分為實(shí)際變量——求解的變量和計(jì)算變量，計(jì)算變量又分松弛變量（上限）和人工變量（下限）。

（2）目標(biāo)函數(shù)——經(jīng)濟(jì)目標(biāo)的數(shù)學(xué)表達(dá)式。目標(biāo)函數(shù)是求變量的線性函數(shù)的極大值和極小值這樣一個(gè)極值問題。

（3）約束條件——實(shí)現(xiàn)經(jīng)濟(jì)目標(biāo)的制約因素。它包括：生產(chǎn)資源的限制（客觀約束條件）、生產(chǎn)數(shù)量、質(zhì)量要求的限制（主觀約束條件）、特定技術(shù)要求和非負(fù)限制。

二、線性規(guī)劃問題的數(shù)學(xué)模型

1.模型建立的步驟

從實(shí)際問題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟：

（1）根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；

（2）由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；

（3）由決策變量所受的限制條件確定決策變量所要滿足的約束條件。

2.線性規(guī)劃問題數(shù)學(xué)模型的基本形式

（1）線性規(guī)劃問題數(shù)學(xué)模型的一般形式是：

三、線性規(guī)劃問題的具體實(shí)例以及模型的建立

1.具體實(shí)例

某奶制品加工廠用牛奶生產(chǎn)，兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時(shí)加工成3 公斤，或者在設(shè)備乙上用8小時(shí)加工成4 公斤，且12每公斤獲利24元，每公斤獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的工作時(shí)間為480小時(shí)，并且設(shè)備甲每天至多能加工100公斤，設(shè)備乙的加工能力沒有限制。試為該廠制定一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大。

2.模型建立

每天50 桶牛奶，工人總工作時(shí)間共480小時(shí)，至多加工100公斤.設(shè)用桶牛奶生產(chǎn)，用桶牛奶生產(chǎn)，下面給出該問題的目標(biāo)函數(shù)和約束條件：

四、利用LINGO軟件求解

1. LINGO軟件簡(jiǎn)介

LINGO是美國(guó)LINDO系統(tǒng)公司開發(fā)的一套專門用于求解最優(yōu)化問題的軟件包。LINGO用于求解求解線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃，以及一些線性和非線性方程組的求解、代數(shù)方程求根等。

一般地，使用LINGO求解運(yùn)籌學(xué)問題可以分為以下兩個(gè)步驟來完成：

（1）根據(jù)實(shí)際問題，建立數(shù)學(xué)模型，即使用數(shù)學(xué)建模的方法建立優(yōu)化模型；

（2）根據(jù)優(yōu)化模型，利用LINGO 來求解模型。主要是根據(jù)LINGO 軟件，把數(shù)學(xué)模型轉(zhuǎn)譯成計(jì)算機(jī)語言，借助于計(jì)算機(jī)來求解。

2. LINGO軟件求解

以下應(yīng)用LINGO9.0軟件求解。點(diǎn)開軟件，首先在LINGO 界面輸入以下程序 ：

MODEL：

max=72*x1+64*x2；

x1+x2<=50；

12*x1+8*x2<=480；

3*x1<=100；

END

然后點(diǎn)擊計(jì)算 ，可得出下列結(jié)果 ：

Global optimal solution found.

Objective value： 3360.000

Total solver iterations： 2

Variable Value Reduced Cost

X1 20.00000 0.000000

X2 30.00000 0.000000

Row Slack or Surplus Dual Price

1 3360.000 1.000000

2 0.000000 48.00000

3 0.000000 2.000000

4 40.00000 0.000000

從上面結(jié)果中不僅可以得到20桶牛奶生產(chǎn)，30桶牛奶生產(chǎn)，總利潤(rùn)為3360元，還可以得到靈敏度分析的結(jié)果。分析結(jié)果：當(dāng)兩個(gè)變量，增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的減少為零（即目標(biāo)函數(shù)不變）。對(duì)于三種資源：原料無剩余，時(shí)間無剩余，加工能力剩余40小時(shí)，其中“資源”剩余為零的約束為緊約束（有效約束），即原料和時(shí)間為緊約束；原料增加1單位， 利潤(rùn)增加48，時(shí)間增加1單位， 利潤(rùn)增加2 ，加工能力增減不影響利潤(rùn)。

結(jié)語

線性規(guī)劃是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，在工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)管理、交通運(yùn)輸?shù)确矫娑加袠O其廣泛的應(yīng)用。但其建立數(shù)學(xué)模型的正確與否，手算的繁瑣復(fù)雜程度給線性規(guī)劃廣泛的推廣與應(yīng)用帶來了許多不便。但是通過使用LINGO軟件，只需編寫很簡(jiǎn)單的幾行程序，就可以輕松求解，同時(shí)也提高了精確度。因此，利用LINGO軟件求解線性規(guī)劃問題逐漸成為科學(xué)界的共識(shí)。

參考文獻(xiàn)

[1]昊祈宗.運(yùn)籌學(xué)[M].北京：機(jī)械工業(yè)出版社，2002.

[2]謝金星，薛毅.優(yōu)化建模LINDO/LINGO軟件[M].北京：清華大學(xué)出版社，2005.