Lingo編程學(xué)習(xí)(啟航系列之數(shù)學(xué)建模培訓(xùn)資料)

啟航系列之數(shù)學(xué)建模培訓(xùn)資料專題2：Lingo編程介紹Lingo產(chǎn)品介紹Lindo 和 Lingo 是美國 Lindo 系統(tǒng)公司開發(fā)的一套專門用于求解最優(yōu)化問題的軟件包。Lindo 用于求解線性規(guī)劃和二次規(guī)劃問題,Lingo 除了具有 Lindo 的全部功能外,還可以用于求解非線性規(guī)劃問題,也可以用于一些線性和非線性方程(組)的求解,等等。Lindo 和 Lingo 軟件的最大特色在于可以允許優(yōu)化模型中的決策變量是整數(shù)（即整數(shù)規(guī)劃）,而且執(zhí)行速度很快。 Lingo 實際上還是最優(yōu)化問題的一種建模語言,包括許多常用的函數(shù)可供使用者建立優(yōu)化模型時調(diào)用,并提供與其他數(shù)據(jù)文件（如文本文件、Excel電子表格文件、數(shù)據(jù)庫文件等）的接口,易于方便地輸入、求解和分析大規(guī)模最優(yōu)化問題。由于這些特點,Lindo系統(tǒng)公司的線性、非線性和整數(shù)規(guī)劃求解程序已經(jīng)被全世界數(shù)千萬的公司用來做最大化利潤和最小化成本的分析。應(yīng)用的范圍包含生產(chǎn)線規(guī)劃、運輸、財務(wù)金融、投資分配、資本預(yù)算、混合排程、庫存管理、資源配置等等. Lindo/Lingo 軟件作為著名的專業(yè)優(yōu)化軟件，其功能比較強、計算效果比較好，與那些包含部分優(yōu)化功能的非專業(yè)軟件相比，通常具有明顯的優(yōu)勢。此外，Lindo/Lingo 軟件使用起來非常簡便，很容易學(xué)會，在優(yōu)化軟件（尤其是運行于個人電腦上的優(yōu)化軟件）市場占有很大份額，在國外運籌學(xué)類的教科書中也被廣泛用做教學(xué)軟件。Lingo的程序規(guī)范1. Lingo能求解的優(yōu)化模型優(yōu)化模型連續(xù)優(yōu)化整數(shù)規(guī)劃優(yōu)化模型二次規(guī)劃非線性規(guī)劃2. 編寫一個簡單的lingo程序例1 用Lingo解決一個二次規(guī)劃問題解：在lingo命令行中輸入如下代碼，x1+x2=100;!一個簡單例子;max=98*x1+277*X2-x1*x1-0.3*X1*x2-2*X2*x2;x1-2*x2=0;gin(x1);gin(x2);按求解鍵得到結(jié)果如下， Global optimal solution found. Objective value: 11077.50 Extended solver steps: 0 Total solver iterations: 44 Variable Value Reduced Cost X1 35.00000 -8.500002 X2 65.00000 -6.500004在這個例子里要注意如下一些細節(jié)：每一行語句結(jié)尾要有分號;注釋行以!號開頭，;號結(jié)尾Lingo中的變量不區(qū)分字母大小寫系數(shù)和變量之間要有運算符相連“max=”或“min=”表示目標函數(shù)Lingo的語句順序并不重要以開頭的語句表示調(diào)用Lingo自帶的函數(shù)，本例中g(shù)in(x1)表示x1為整數(shù)Lingo中以默認了所有變量都非負對本例結(jié)果的解釋:找到全局最優(yōu)解，使得目標函數(shù)值為，對應(yīng)變量，的值分別為和，對應(yīng)變量，的影子價格分別為，。所謂的影子價格，就是指對應(yīng)的變量增加1單位，其他變量無變化時目標函數(shù)改變的單位數(shù)。3. 建立Lingo優(yōu)化模型需要注意的幾個基本問題(1)、盡量使用實數(shù)優(yōu)化模型，盡量減少整數(shù)變量和整數(shù)約束；(2)、盡量使用光滑優(yōu)化模型，盡量避免使用非光滑函數(shù)。比如應(yīng)盡量避免使用絕對值函數(shù)，符號函數(shù)，求最大最小值函數(shù)，取整函數(shù)等；(3)、盡量使用線性優(yōu)化模型，盡量減少非線性約束和非線性變量的個數(shù)；(4)、合理設(shè)定變量的上下界，盡可能給出變量的初始值；(5)、模型中使用的單位的數(shù)量級要適當。系數(shù)最大數(shù)和最小數(shù)的絕對值超過1000倍以上會彈出警告信息。4. 在Lingo中使用集合4.1 集合的基本用法和lingo模型的基本要素Lingo雖然使用方便，但是如果要解決幾萬個，幾十萬個變量的優(yōu)化問題時，我們總不能一個一個地列出x1,x2,x1000來解決，而這樣的問題在實際企業(yè)的應(yīng)用中也是經(jīng)常遇到的。好在Lingo中設(shè)計了集合語言來表示大規(guī)模變量的輸入，只需一行文字就可以建立起含有大規(guī)模變量的目標函數(shù)和成千上萬條約束。而Lingo的早期版本軟件Lindo卻不包含這樣的功能?，F(xiàn)通過下例來對Lingo的集合、屬性概念進行介紹。例2 SAILCO公司需要決定決定下四個季度的帆船生產(chǎn)量。下四個季度的帆船需求量分別為40條，60條，75條，25條，這些需求必須按時滿足。每個季度正常的生產(chǎn)能力是40條帆船，每條帆船的生產(chǎn)費用為400美元。如果加班生產(chǎn)，每條船的生產(chǎn)費用為450美元。每個季度末，每條船的庫存費用為20美元。假定生產(chǎn)提前期為0，初始庫存為10條船。如何安排生產(chǎn)可使總費用最?。糠治雠c解：用DEM、RP、OP、INV分別表示需求量，正常生產(chǎn)的產(chǎn)量，加班生產(chǎn)的產(chǎn)量，庫存量。則DEM、RP、OP、INV對每個季度都應(yīng)有一個對應(yīng)的值，也就是說他們都應(yīng)該是一個由4個元素組成的數(shù)組，其中DEM已知，而RP，OP，INV未知?，F(xiàn)在我們可以寫出該問題的模型：此外還有各變量非負的約束。記4個季度組成的集合，他們就是DEM、RP、OP、INV等變量的下標集合，對于，都有值與之對應(yīng)。LINGO正是充分利用這種數(shù)組及其下標的關(guān)系，引入了“集合”與“屬性”的概念。本例中我們把稱之為集合，DEM、RP、OP、INV稱為集合具有的屬性(即定義在該集合上的屬性)。下圖表示了這種集合與屬性的關(guān)系。集合QUARTERS的屬性DEMRPOPINV集合QUARTERS1234集合QUARTERS的元素1234定義在集合QUARTERS上的屬性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4)下面我們看看Lingo中具體如何定義集合及其屬性。下面是例2的Lingo代碼：Model:Sets:QUARTERS/1,2,3,4/:DEM,RP,OP,INV;EndsetsMin=sum(QUARTERS:400*RP+450*OP+20*INV);for(QUARTERS(I):RP(I)=40;);for(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);DATA:DEM=40,60,75,25;EnddataEnd我們總結(jié)一下上面代碼的特點：（1）、模型以“MODEL：”開始，以“END”結(jié)束。它們之間由語句組成，可以分成三步分。（2）、集合定義部分以“SETS：”開始，以“ENDSETS”結(jié)束。中間定義了集合和相應(yīng)屬性。語句“QUARTERS/1,2,3,4/:DEM,RP,OP,INV;”定義了集合QUARTERS，以及該集合的屬性DEM、RP、OP、INV，其結(jié)果正是上表里面的16個變量名?？梢远x空集合，比如“Empty set/1，2，3，4/;”空集合的用法將在派生集中講述。（3）、數(shù)據(jù)輸入部分以“DATA：”開始，以“ENDDATA”結(jié)束，語句“DEM=40,60,75,25;”給出了常量DEM的值，即DEM(1)=40,DEM(2)=60，DEM(3)=75,DEM(4)=25. 語句“DEM=40,60,75,25;”也可以寫成語句“DEM=40 60 75 25;”即數(shù)據(jù)之間可以用逗號或空格分開。（4）、其他部分，給出了目標函數(shù)和約束。其中目標函數(shù)（“min=”后面所接的表達式）是用求和函數(shù)“sum=(集合（下標）：關(guān)于集合的屬性的表達式)”的方式定義的，這個函數(shù)的功能是對語句冒號“：”后面的表達式，按照“：”前面的集合指定的下標元素進行求和。本例中目標函數(shù)也可以寫成“Min=sum(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i)”這里“sum”相當于求和符號,而“QUARTERS(i)”相當于“”，而由于本例中已默認對所有的QUARTERS的元素求和，所以實例中可以將下標i省略。約束是用循環(huán)函數(shù)“for(集合（下標）：關(guān)于集合的屬性的約束關(guān)系式)”的方式定義的，意思是對于“：”前面的集合的每個元素(下標)，冒號“：”后面的約束關(guān)系式都要成立。但對于這個約束，實際上I=1時要用到變量，但我們定義屬性變量的時候是從I=1開始的，即是一個常數(shù)，為了區(qū)別I=1和I=2，3，4，我們要將I=1的約束單獨列出來，而對I=2，3，4的約束我們對集合下標做了的約束，即用了“#GT#1”（這個限制條件與集合之間有一個豎線“|”分開，稱為過濾條件），“I#GT#1”就表示，“#GT#”是lingo中的邏輯表達式。小結(jié)一下lingo模型最基本的組成要素：（1） 集合段：以“SETS：”開始，以“ENDSETS”結(jié)束。作用在于定義必要的集合和屬性。注意一個細節(jié)，我們可以定義QUARTERS/1,2,3,4/,若QUARTERS有1000個元素，我們也不必將其一一列出，而可以簡寫為QUARTERS/1.1000/.（2） 目標和約束段：這部分不像其他部分，沒有段的開始和結(jié)束的標記。因此是除去其他段以外的所有語句。（3） 數(shù)據(jù)段：以“DATA：”開始，以“ENDDATA”結(jié)束，作用在于對集合的屬性輸入必要的常數(shù)數(shù)據(jù)，格式為: 屬性=常數(shù)列表;常數(shù)列表中的常數(shù)或以逗號“，”分開，或以空格分開“ ”.（4） 初始段：以“INIT：”開始，以“ENDINIT”結(jié)束。作用在于對集合的屬性定義初值。因為求解算法是迭代算法，所以一個好的初值可以讓程序更快解決。定義初值的格式為： 屬性=常數(shù)列表;（5） 計算段：以“CALC：”開始，以“ENDCALC”結(jié)束，作用在于對一些原始數(shù)據(jù)進行計算處理，這種處理是在輸入數(shù)據(jù)后，求解模型前進行的。例如，對上面的例子，如果我們希望可以得到全年的總需求和季度平均需求，可以增加這個段：CALC:T_DEM=sum(QUARTERS:DEM);!總需求;A_DEM=T_DEM/size(QUARTERS);!平均需求;ENDCALC要注意的是計算段中語句是按順序執(zhí)行的，故上面的兩個語句不能調(diào)換。4.2 基本集合與派生集合例3 建筑工地的位置(用平面坐標a，b表示，單位：km)及水泥日用量d(單位：t)用下表給出。目前兩個臨時料廠位于P(5,1),Q(2,7),日儲量各有20t。求從A，B兩料廠分別向各工地運送多少水泥，使總的噸公里數(shù)最小。兩個新的料場應(yīng)建在何處，節(jié)省的噸公里數(shù)有多大？ 工地編號123456a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611解：記工地的位置為水泥日用量為，料場位置為，日儲量為，從料場j向工地i的運送量為，這個優(yōu)化問題的解為：嘗試將這個模型輸入lingo時，利用前面介紹的集合概念，顯然可以定義需求點demand和供應(yīng)點supply兩個集合，分別有6個和2個元素。但是決策變量是同時與supply和demand相關(guān)的屬性，這該如何定義呢？其實我們可以定義一個由二元對組成的新的集合，然后將定義為該集合的屬性。具體代碼如下：model:sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;enddatainit:x,y=5,1,2,7;endinitmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i););for(supply(i):sum(demand(j):c(j,i)=e(i););for(supply:free(x);free(y););End我們在集合段定義了三個集合，其中l(wèi)ink是在前兩個集合demand和supply的基礎(chǔ)上定義的集合。語句link(demand,supply):c;表示集合link中的元素就是集合demand和supply的元素合成的有序二元組。從數(shù)學(xué)上看就是因此其屬性c也就是6*2的矩陣。像link這樣基于其他集合而派生出來的二維或多維集合我們稱之為派生集合。本模型初始段中的語句“x,y=5,1,2,7”實際的賦值順序是，也就是說lingo對數(shù)據(jù)是按列賦值的，這點要注意了，當然也可以寫成“x=5,2;y=1,7”4.3 稠密集合與稀疏集合我們已經(jīng)介紹了基本集合和派生集合。例3中我們把派生集合link的元素定義為demand和supply的笛卡爾積，即包含了兩個基本集合構(gòu)成的所有的二元有序?qū)?。這種派生集稱為稠密集合，有時候一些屬性肯能只在某些有序?qū)ι嫌幸饬x，我們只要定義有意義的集合，這就產(chǎn)生了稀疏集合的概念。例4 求下圖中城市S至T的最短路徑。6SA1A2A3B1B2C1C2T63365874678956解：用lingo解決最短路問題，代碼如下。集合段定義的cities是基本集合，L是對應(yīng)的屬性變量。Roads是由cities派生的集合，由于只有一部分城市之間有路相連，所以不應(yīng)該把它定義為稠密集合，只能通過枚舉定義成一個稀疏集合。model:sets:cities/s,a1,a2,a3,b1,b2,c1,c2,t/:L; !L表示最優(yōu)行駛路線的線長;roads(cities,cities)/s,a1 s,a2 s,a3a1,b1 a1,b2 a2,b1 a2,b2 a3,b1 a3,b2b1,c1 b1,c2 b2,c1 b2,c2c1,t c2,t/:D;!D表示兩城市間的直接距離;endsetsdata:D=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6;L=0,;enddatafor(cities(i)|i#GT#index(s):L(i)=min(roads(j,i):L(j)+D(j,i););end從本例可以看出，lingo程序可以沒有目標函數(shù)。因此lingo可以用來解方程組和不等式組。此外在數(shù)據(jù)段我們對L進行賦值，但只有L(S)=0是已知的，所以后面的值為空(但位置必須留下來，逗號“，”一個也不能少)。雖然集合cities中的元素不是數(shù)字，但當它以cities(i)的形式出現(xiàn)在循環(huán)中時，引用下標i實際上仍是一個整數(shù)。也就是說，i指的正是元素在集合中的位置，一般稱為元素的索引。我們用index(i)來返回元素i的索引。從上例可以看出定義稀疏集合時用枚舉其元素的方法給出的。但當元素比較多時，這就麻煩了。我們可以用“元素過濾法”來定義稀疏集合。例5 某班8名同學(xué)準備分成4個調(diào)查隊（每隊兩人）前往4個地區(qū)進行社會調(diào)查。假設(shè)這8名同學(xué)兩兩之間組隊的效率如下圖所示，問如何組隊效率最高？學(xué)生S1S2S3S4S5S6S7S8S19342156S2173521S344292S41552S5876S623S74解：本例的數(shù)學(xué)模型如下model:sets:students/s1.s8/;pairs(students,students)|&2#GT#&1:benefit,match;endsetsdata:benefit=9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;enddatamax=sum(pairs(i,j):benefit(i,j)*match(i,j);for(students(i):sum(pairs(j,k)|j#EQ#i#OR#k#EQ#i:match(j,k)=1);for(pairs(i,j):bin(match(i,j);End上面代碼中邏輯關(guān)系式“&2#GT#&1”表示第二個父集合的元素的縮索引值大于第一個元素的索引值。這樣pairs中的元素剛好對應(yīng)于上面表中的嚴格上三角部分的二維下標了。讀者還應(yīng)該注意數(shù)據(jù)段對benefit的賦值方式，體會lingo是按照列的順序?qū)ψ兞吭剡M行賦值的。4.4 集合的使用小結(jié)小結(jié)一下集合的用法（1）、集合的不同類型和關(guān)系集合派生集合基本集合稀疏集合稠密集合元素列表法元素過濾法直接列舉法隱式列舉法（2）、集合的定義方法（中的內(nèi)容是可選項）基本集合： setname/member_list/:attribute_list;派生集合： setname(parent_set_list)/member_list/:attribute_list;5. Lingo中的運算符與函數(shù)5.1 運算符與優(yōu)先級算術(shù)運算符： (求冪)邏輯運算符：（1）#AND#（與），#OR#（或），#NOT#（非）（2）#EQ#（等于），#NE#（不等于），#GT#（大于），#GE#（大于等于），#LT#（小于），#LE#（小于等于）關(guān)系運算符：運算符的優(yōu)先級優(yōu)先級運算符最高#NOT# -(負號）* /+ -#EQ#,#NE#,#GT#,#GE#,#LT#,#LE#AND#,#OR#最低5.2 Lingo函數(shù)（1）、基本數(shù)學(xué)函數(shù)abs(x):絕對值函數(shù)cos(x):余弦函數(shù)exp(x):指數(shù)函數(shù)，返回floor(x):取整函數(shù)LGM(x):返回x的伽瑪函數(shù)的自然對數(shù)值LOG(x):自然對數(shù)函數(shù)MOD(x,y)：模函數(shù)，返回x對y取模的結(jié)果，即x除以y的余數(shù)pow(x,y):指數(shù)函數(shù)，返回sign(x):符號函數(shù)sin(x)：正弦函數(shù)smax(list)：最大值函數(shù)，返回一列數(shù)list的最大值smin(list)：最小值函數(shù)sqr(x)：平方函數(shù)sqrt(x)：平方根函數(shù)tan(x)：正切函數(shù)（2）、集合循環(huán)函數(shù)集合循環(huán)函數(shù)一般調(diào)用格式為：function(setname(set_index_list)|condition:expression_list);其中function是函數(shù)名，setname是集合名，set_index_list是集合索引列表，condition是邏輯表達式的過濾條件。expression_list是一個表達式。集合循環(huán)函數(shù)有如下5個：for()：對集合的每個元素獨立地生成表達式max()：返回集合上的表達式的最大值min()：返回集合上的表達式的最小值prod()：返回集合上的表達式的積sum()：返回集合上的表達式的和（3）、