LINGO在運籌學實踐教學中的應用

管梅

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

【關鍵詞】運籌學； LINGO；運輸問題；0-1規劃；最短路

0 引言

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

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

1 實例應用

一般地，使用LINGO 求解運籌學問題可以分為以下兩個步驟來完成：1）根據實際問題，建立數學模型，即使用數學建模的方法建立優化模型；2）根據優化模型，利用LINGO 來求解模型，借助于計算機來求解。

1.1 在運輸問題中的應用

在經濟建設中，經常碰到大宗物資調運問題。如煤、鋼鐵、木材、糧食等物資，在全國有若干生產基地，根據已有的交通網，應如何指定調運方案，將這些物資運到各消費地點，而總運費最小，這就是經典的運輸問題[4]。

表1 產銷量、單位運價表

例1 某煤炭供應商有7個煤礦（產地），開挖的煤炭供應給9個發電站（銷地），各煤礦的生產量、各發電站的需求量（假定單位均為t），以及煤炭從各煤礦運到各個發電站的單位運價示于表1中，要求研究煤炭如何調運才能使總運費最小？

解：設xij（i=1，2，…，7；j=1，2，…，9）為從Ai煤礦運到Bj發電站的煤炭的數量，建立該運輸問題的數學模型如下：

其中cij為將煤炭從Ai煤礦運到Bj發電站的單位運輸費用，ai為煤礦Ai的產煤量，bj為發電站Bj對煤炭的需求量。

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

最優調運方案：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單位。

最小總費用為：890。

1.2 在0-1規劃問題中的應用

0-1規劃是數學規劃的一個重要問題，它的產生源于實際中的一些應用，如選址問題、排班及背包問題等。

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

最優選址方案為：在第一個、第四個、第七個住宅區建立消防站可以確保使盡可能多的人口位于消防應急站5分鐘內到達的范圍。

1.3 在最短路問題中的應用

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

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

圖1 九個城市間的道路圖

解：借助動態規劃法，應用LINGO來求解該模型，只需要在LINGO窗口中輸人以下代碼：

2 結語

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

【參考文獻】

[1]胡運權.運籌學教程[M].3版.北京：清華大學出版社，2007：1-10.

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

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

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

[責任編輯：湯靜]