資源描述：
《利用lingo建立最優(yōu)化模型》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、利用LINGO建立最優(yōu)化模型洪文1，朱云鵑1，金震1，王其文21（安徽大學(xué)商學(xué)院合肥230039）2（北京大學(xué)光華管理學(xué)院北京100871）摘要：本文借助于最優(yōu)化軟件LINGO建立了最小樹、最短路、最大流、最小費用流和貨郎擔(dān)問題的LINGO模型，并對模型中的難點給出了注釋。利用本文提供的模型，可以很容易地求出上述5個最優(yōu)化問題的最優(yōu)解。關(guān)鍵詞：最小樹、最短路、最大流、最小費用流、貨郎擔(dān)問題、LINGO中圖分類號：0211.6文獻(xiàn)標(biāo)識碼：A文章編號：0引言求解最小樹、最短路、最大流、最小費用流和貨郎擔(dān)問
2、題的方法雖然很多，但是利用最優(yōu)化求解軟件LINGO建立相應(yīng)的模型來求解上述5個問題是一種新的嘗試。本文建立的模型有兩個突出的特點。第一個特點是模型的數(shù)據(jù)與公式完全分離，這樣使得問題的求解變得特別方便（對于不同的問題只要更換數(shù)據(jù)即可）。第二個特點是這五個模型都是利用最優(yōu)化求解軟件LINGO編寫而成，可進(jìn)行快速求解。1LINGO簡介LINGO是一個簡單而實用的最優(yōu)化軟件。利用線性和非線性最優(yōu)化的方法，LINGO可以用公式簡明地表示復(fù)雜的規(guī)劃問題，并可以快速地求出問題的最優(yōu)解。LINGO是由美國芝加哥LIN
3、DO系統(tǒng)公司研制。該公司根據(jù)用戶信息、線性和非線性規(guī)劃的理論和方法及計算機發(fā)展的需要不斷推出新的版本。目前LINGO已成為世界上最為流行的最優(yōu)化軟件之一。LINGO在我國已經(jīng)有了相當(dāng)多的用戶。它的主要特點是：1）LINGO含有一系列的接口函數(shù)。這些接口函數(shù)可用在文本文件、電子表格和數(shù)據(jù)庫中，可與外部的輸入/輸出源進(jìn)行連接。2）LINGO可以直接嵌入到Excel中，也可以將Excel嵌入到LINGO模型中。這樣就可以將數(shù)據(jù)與模型分離，使得模型的維護(hù)和調(diào)試變得非常容易。3）LINGO使用Windows的窗
4、口展開優(yōu)化分析功能，使用對話框展示各種功能。清晰、直觀、易學(xué)易用。104）LINGO具有強大的計算功能。眾所周知，建模難，求解模型更難。利用LINGO就可以擺脫復(fù)雜繁瑣的計算煩惱。2LINGO與LINDO的關(guān)系LINGO與LINDO都是美國LINDO系統(tǒng)公司的產(chǎn)品。利用它們都可以求解線性規(guī)劃，這是它們的共同點。但是兩者還是有區(qū)別的。1）如果要輸入5x+4y<70這樣一個約束，在LINDO模型中可以直接輸入，不需要變動。而在LINGO模型中一定要改成：5*x+4*y<70。后者比前者復(fù)雜，但這也正是后者
5、的特點：LINGO可以求解非線性規(guī)劃，而LINDO只能求解線性規(guī)劃。2）LINGO的集合函數(shù)功能非常強大，它可以使我們很容易地處理數(shù)據(jù)。例如可以利用集合語言將電子表格中數(shù)據(jù)調(diào)入模型，計算后將結(jié)果輸出到電子表格中。這樣，數(shù)據(jù)和模型就完全分離了，LINGO模型可以不因數(shù)據(jù)的變動而改動。3）利用LINGO的集合函數(shù)可以使我們擺脫處理復(fù)雜冗長表達(dá)式的煩惱。例如，假設(shè)a表示一個單位的職工集合，x表示職工的工資，工資總和就可以用@sum(a:x)來表示。不管這個單位是10個人，100個人人還是1000個人，表達(dá)式
6、不變，4）如果要在LINGO模型中輸入已經(jīng)建立的LINDO模型，只要使用importlindofile命令即可；如果要將已經(jīng)建立的LINGO模型變成LINDO模型，只要使用generate命令即可。也就是說LINDO與LINGO線性模型可以相互轉(zhuǎn)換。鑒于LINGO集合函數(shù)的強大功能，下面5個最優(yōu)化問題實例都是LINGO模型。3最小樹問題和模型3.1最小生成樹問題在圖論中，稱無圈的連通圖為樹。現(xiàn)實中樹的例子很多。例如通訊網(wǎng)、電網(wǎng)、自來水管網(wǎng)和暖氣供應(yīng)網(wǎng)都可以看成是樹。這些網(wǎng)絡(luò)的特點一是連通，二是不會形成
7、圈。在一個連通圖G中，如果保留全部頂點，并選擇適當(dāng)?shù)倪厴?gòu)成一個子圖，并且使這個子圖是一棵樹，則稱這個子圖為圖G的生成樹（或支撐樹）。連通圖G生成樹上各邊的權(quán)數(shù)之和稱為該生成樹的權(quán)。連通圖G的權(quán)數(shù)最小的生成樹為圖G的最小生成樹或稱最小樹。許多實際問題都可以歸結(jié)為求最小生成樹。例如，如何修筑一些公路把若干個城鎮(zhèn)連接起來；如何架設(shè)通訊網(wǎng)絡(luò)將若干個地區(qū)連接起來；如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等。為了說明問題，請看下面的范例1。范例1：假設(shè)某電話公司計劃在六個村莊架設(shè)電話線，各村莊之間的距離如
8、圖1所示。試求出使電話線總長度最小的架線方案。圖1六個村莊電話線路圖103.2最小樹模型規(guī)定：節(jié)點V1表示樹根；當(dāng)兩個節(jié)點之間沒有線路時，規(guī)定兩個節(jié)點之間的距離為M（利用計算機進(jìn)行求解時換成一個大數(shù)，在本例中所有權(quán)重之和小于100，可以設(shè)M=100）。最小樹整數(shù)規(guī)劃模型如下（加重黑線部分根據(jù)問題大小做相應(yīng)調(diào)整）：MODEL[1]SETS:[2]CITY/1..6/:;!定義了圖1的點集CITY;[3]LINK(CITY,CITY):DIST,X,Y;!定
