管梅

【摘 要】運(yùn)籌學(xué)是一門研究如何有效地組織和管理人機(jī)系統(tǒng)的科學(xué)，在許多學(xué)科領(lǐng)域及實(shí)際問題中均有應(yīng)用。自從運(yùn)籌學(xué)在20世紀(jì)30年代建立以來，其算法的發(fā)展一直受到電子計(jì)算機(jī)的發(fā)展的影響。由此可見，在本科運(yùn)籌學(xué)教學(xué)中引入適當(dāng)?shù)膶?shí)踐教學(xué)是相當(dāng)有必要的。本文結(jié)合教學(xué)實(shí)踐，介紹了優(yōu)化建模軟件LINGO在運(yùn)輸問題，0-1規(guī)劃和最短路問題中的應(yīng)用，有助于提高學(xué)生的學(xué)習(xí)興趣，感受運(yùn)籌學(xué)課程的實(shí)用性。

【關(guān)鍵詞】運(yùn)籌學(xué)； LINGO；運(yùn)輸問題；0-1規(guī)劃；最短路

0 引言

運(yùn)籌學(xué)是20世紀(jì)30年代末產(chǎn)生的應(yīng)用學(xué)科，已經(jīng)在生產(chǎn)管理、工程技術(shù)、軍事戰(zhàn)爭、科學(xué)實(shí)驗(yàn)、經(jīng)濟(jì)管理以及社會科學(xué)中都得到了極為廣泛的應(yīng)用，與此同時，運(yùn)籌學(xué)的理論應(yīng)用中得到了長足的發(fā)展。20世紀(jì)50年代后，計(jì)算機(jī)的迅猛發(fā)展和廣泛應(yīng)用，為運(yùn)籌學(xué)的發(fā)展創(chuàng)造了有利的技術(shù)條件，使得運(yùn)籌學(xué)的方法論能成功地、及時地解決大量經(jīng)濟(jì)管理中的決策問題[1]。計(jì)算機(jī)的發(fā)展推進(jìn)了運(yùn)籌學(xué)的發(fā)展、普及和應(yīng)用，使得它不僅僅為“運(yùn)作研究”小組那樣的專家所掌握和使用，也成為廣大經(jīng)濟(jì)管理、系統(tǒng)科學(xué)、信息與計(jì)算科學(xué)等專業(yè)的工作者進(jìn)行最優(yōu)決策和有效管理的常用工具之一[2]。在運(yùn)籌學(xué)實(shí)際教學(xué)過程中，很多老師還是重理論輕實(shí)踐，導(dǎo)致很多學(xué)生在學(xué)了運(yùn)籌學(xué)之后，只是覺得運(yùn)籌學(xué)理論高深、具體算法難以實(shí)現(xiàn)，感覺不到運(yùn)籌學(xué)的實(shí)際應(yīng)用價(jià)值。通過優(yōu)化軟件可以使得學(xué)生有機(jī)會自己動手解決有一定規(guī)模的實(shí)際問題，縮小學(xué)生課堂所學(xué)知識與實(shí)際運(yùn)用之間的差距，從而激發(fā)其學(xué)習(xí)興趣。

LINDO/LINGO 是由美國芝加哥大學(xué)的Linus Schrage教授于1980年前后開發(fā)出來的一套專門用于求解最優(yōu)化問題的軟件包，經(jīng)過多年的不斷完善和擴(kuò)充所形成的，并成立LINDO系統(tǒng)公司（LINDO Systems Inc.）進(jìn)行商業(yè)化運(yùn)作，取得巨大的成功[3]。LINGO 是Linear Interactive and General Optimizer的縮寫，即“交互式的線性和通用優(yōu)化求解器”，可以用于求解非線性規(guī)劃，也可以用于一些線性和非線性方程組的求解等。其特色在于可以允許決策變量是整數(shù)（即整數(shù)規(guī)劃，包括0-1整數(shù)規(guī)劃），方便靈活，而且執(zhí)行速度非?？?。

1 實(shí)例應(yīng)用

一般地，使用LINGO 求解運(yùn)籌學(xué)問題可以分為以下兩個步驟來完成：1）根據(jù)實(shí)際問題，建立數(shù)學(xué)模型，即使用數(shù)學(xué)建模的方法建立優(yōu)化模型；2）根據(jù)優(yōu)化模型，利用LINGO 來求解模型，借助于計(jì)算機(jī)來求解。

1.1 在運(yùn)輸問題中的應(yīng)用

在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到大宗物資調(diào)運(yùn)問題。如煤、鋼鐵、木材、糧食等物資，在全國有若干生產(chǎn)基地，根據(jù)已有的交通網(wǎng)，應(yīng)如何指定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，而總運(yùn)費(fèi)最小，這就是經(jīng)典的運(yùn)輸問題[4]。

表1 產(chǎn)銷量、單位運(yùn)價(jià)表

例1 某煤炭供應(yīng)商有7個煤礦（產(chǎn)地），開挖的煤炭供應(yīng)給9個發(fā)電站（銷地），各煤礦的生產(chǎn)量、各發(fā)電站的需求量（假定單位均為t），以及煤炭從各煤礦運(yùn)到各個發(fā)電站的單位運(yùn)價(jià)示于表1中，要求研究煤炭如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？

解：設(shè)xij（i=1，2，…，7；j=1，2，…，9）為從Ai煤礦運(yùn)到Bj發(fā)電站的煤炭的數(shù)量，建立該運(yùn)輸問題的數(shù)學(xué)模型如下：

其中cij為將煤炭從Ai煤礦運(yùn)到Bj發(fā)電站的單位運(yùn)輸費(fèi)用，ai為煤礦Ai的產(chǎn)煤量，bj為發(fā)電站Bj對煤炭的需求量。

應(yīng)用LINGO來求解該模型，只需要在LINGO窗口中輸人以下代碼：

最優(yōu)調(diào)運(yùn)方案：A1→B6：59單位；A2→B6：28單位；A2→B8：69單位；A3→B1：16單位；A3→B6：6單位；A3→B7：47單位；A4→B3：77單位；A5→B2：76單位；A5→B3：6單位；A5→B9：1單位；A6→B9：61單位；A7→B5：68單位；A7→B7：8單位。

最小總費(fèi)用為：890。

1.2 在0-1規(guī)劃問題中的應(yīng)用

0-1規(guī)劃是數(shù)學(xué)規(guī)劃的一個重要問題，它的產(chǎn)生源于實(shí)際中的一些應(yīng)用，如選址問題、排班及背包問題等。

例2 （選址問題）廬陽區(qū)有9個大型住宅區(qū)，要選3個來建消防應(yīng)急站。各消防站的消防車從一個住宅區(qū)到另一住宅區(qū)所需時間如表2所示，住在各住宅區(qū)的人口如表3所示。問應(yīng)如何選址才能使盡可能多的人口位于消防應(yīng)急站5分鐘內(nèi)到達(dá)的范圍？

最優(yōu)選址方案為：在第一個、第四個、第七個住宅區(qū)建立消防站可以確保使盡可能多的人口位于消防應(yīng)急站5分鐘內(nèi)到達(dá)的范圍。

1.3 在最短路問題中的應(yīng)用

最短路問題是重要的最優(yōu)化問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題，如管道建設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等，而且經(jīng)常作為一個基本工具，用于解決其它的優(yōu)化問題[4]。

例3 在圖1中，用點(diǎn)表示城市，現(xiàn)有S，A1，A2，A3，B1，B2，C1，C2，T共九個城市，點(diǎn)與點(diǎn)之間的連線表示城市間有道路相連。連線旁的數(shù)字表示道路的長度。現(xiàn)準(zhǔn)備從城市S運(yùn)送急需物品到城市T，請找出路程最短的運(yùn)送方案。

圖1 九個城市間的道路圖

解：借助動態(tài)規(guī)劃法，應(yīng)用LINGO來求解該模型，只需要在LINGO窗口中輸人以下代碼：

2 結(jié)語

以上三個實(shí)例由于變量個數(shù)多，如果是借助算法進(jìn)行手工計(jì)算工作量是非常大的，會讓學(xué)生感到繁瑣不易學(xué)會，而借助LINGO作為輔助工具來進(jìn)行實(shí)踐教學(xué)，不僅使學(xué)生從大量的計(jì)算中解脫出來，更能激發(fā)學(xué)生對運(yùn)籌學(xué)課程的學(xué)習(xí)興趣，提高實(shí)際應(yīng)用能力，體會到應(yīng)用數(shù)學(xué)的實(shí)用性。

【參考文獻(xiàn)】

[1]胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].3版.北京：清華大學(xué)出版社，2007：1-10.

[2]韓伯棠.管理運(yùn)籌學(xué)[M].2版.北京：高等教育出版社，2005：1-8.

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

[4]《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M].2版.北京：清華大學(xué)出版社，2009，1：80-90.

[責(zé)任編輯：湯靜]