Lingo-求解運(yùn)輸問(wèn)題

（LinearInteractiveGeneralOptimizer）

LINGO簡(jiǎn)介L(zhǎng)INGO（LinearInteractiveGeneralOptimizer）

是用來(lái)求解線性和非線性優(yōu)化問(wèn)題的簡(jiǎn)易工具。LINGO內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，利用LINGO高效的求解器可快速求解并分析結(jié)果。例1如何在LINGO中求解如下的LP問(wèn)題：min=2*x1+3*x2;x1+x2>=350;x1>=100;2*x1+x2<=600;然后點(diǎn)擊工具條上的按鈕即可。在模型窗口中輸入如下代碼：例2直接用LINGO來(lái)解如下二次規(guī)劃問(wèn)題：輸入窗口如下：程序語(yǔ)句輸入的備注：LINGO總是根據(jù)“MAX=”或“MIN=”尋找目標(biāo)函數(shù)，而除注釋語(yǔ)句和TITLE語(yǔ)句外的其他語(yǔ)句都是約束條件，因此語(yǔ)句的順序并不重要。限定變量取整數(shù)值的語(yǔ)句為“@GIN(X1)”和“@GIN(X2)”，不可以寫(xiě)成“@GIN(2)”，否則LINGO將把這個(gè)模型看成沒(méi)有整數(shù)變量。LINGO中函數(shù)一律需要以“@”開(kāi)頭，其中整型變量函數(shù)（@BIN、@GIN）和上下界限定函數(shù)（@FREE、@SUB、@SLB）與LINDO中的命令類(lèi)似。而且0/1變量函數(shù)是@BIN函數(shù)。LINGO的基本用法的幾點(diǎn)注意事項(xiàng)LINGO中不區(qū)分大小寫(xiě)字母；變量和行名可以超過(guò)8個(gè)字符，但不能超過(guò)32個(gè)字符，且必須以字母開(kāi)頭。用LINGO解優(yōu)化模型時(shí)已假定所有變量非負(fù)(除非用限定變量取值范圍的函數(shù)@free或@sub或@slb另行說(shuō)明)。變量可以放在約束條件的右端(同時(shí)數(shù)字也可放在約束條件的左端)。但為了提高LINGO求解時(shí)的效率，應(yīng)盡可能采用線性表達(dá)式定義目標(biāo)和約束(如果可能的話)。語(yǔ)句是組成LINGO模型的基本單位,每個(gè)語(yǔ)句都以分號(hào)結(jié)尾，編寫(xiě)程序時(shí)應(yīng)注意模型的可讀性。例如：一行只寫(xiě)一個(gè)語(yǔ)句，按照語(yǔ)句之間的嵌套關(guān)系對(duì)語(yǔ)句安排適當(dāng)?shù)目s進(jìn)，增強(qiáng)層次感。以感嘆號(hào)開(kāi)始的是說(shuō)明語(yǔ)句(說(shuō)明語(yǔ)句也需要以分號(hào)結(jié)束)。LINGO模型最基本的組成要素一般來(lái)說(shuō)，LINGO中建立的優(yōu)化模型可以由五個(gè)部分組成，或稱為五“段”（SECTION）：（1）集合段（SETS）：以“SETS:”開(kāi)始，“ENDSETS”結(jié)束，定義必要的集合變量（SET）及其元素（MEMBER，含義類(lèi)似于數(shù)組的下標(biāo)）和屬性（ATTRIBUTE，含義類(lèi)似于數(shù)組）?；炯系亩x語(yǔ)法基本集合的定義格式為(方括號(hào)“[]”中的內(nèi)容是可選項(xiàng),可以沒(méi)有):setname[/member_list/][:attribute_list];類(lèi)型隱式列舉格式示例示例集合表示的元素?cái)?shù)字型1..n1..51,2,3,4,5字符-數(shù)字型stringM..stringNCar101..car208Car101,car102,…,car208日期（星期）型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002setname[/member_list/][:attribute_list];其中setname為定義的集合名，member_list為元素列表，attribute_list為屬性列表。元素列表可以采用顯式列舉法(即直接將所有元素全部列出,元素之間用逗號(hào)或空格分開(kāi)),也可以采用隱式列舉法，隱式列舉法可以有幾種不同格式。（2）目標(biāo)與約束段：目標(biāo)函數(shù)、約束條件等，沒(méi)有段的開(kāi)始和結(jié)束標(biāo)記，因此實(shí)際上就是除其它四個(gè)段(都有明確的段標(biāo)記)外的LINGO模型。這里一般要用到LINGO的內(nèi)部函數(shù)，尤其是與集合相關(guān)的求和函數(shù)@SUM和循環(huán)函數(shù)@FOR等。（3）數(shù)據(jù)段(DATA)：以“DATA:”開(kāi)始,“ENDDATA”結(jié)束，對(duì)集合的屬性(數(shù)組)輸入必要的常數(shù)數(shù)據(jù)。格式為：“attribute(屬性)=value_list(常數(shù)列表);”常數(shù)列表(value_list)中數(shù)據(jù)之間可以用逗號(hào)“,”分開(kāi)，也可以用空格分開(kāi)(回車(chē)等價(jià)于一個(gè)空格)。（4）初始段(INIT)：以“INIT:”開(kāi)始，“ENDINIT”結(jié)束，對(duì)集合的屬性(數(shù)組)定義初值(因?yàn)榍蠼馑惴ㄒ话闶堑惴?，所以用戶如果能給出一個(gè)比較好的迭代初值，對(duì)提高算法的計(jì)算效果是有益的)。如果有一個(gè)接近最優(yōu)解的初值，對(duì)LINGO求解模型是有幫助的。定義初值的格式為：“attribute（屬性）=value_list（常數(shù)列表）；”這與數(shù)據(jù)段中的用法是類(lèi)似的。（5）計(jì)算段(CALC)：以“CALC:”開(kāi)始，“ENDCALC”結(jié)束，對(duì)一些原始數(shù)據(jù)進(jìn)行計(jì)算處理。在實(shí)際問(wèn)題中，輸入的數(shù)據(jù)通常是原始數(shù)據(jù)，不一定能在模型中直接使用，可以在這個(gè)段對(duì)這些原始數(shù)據(jù)進(jìn)行一定的“預(yù)處理”，得到模型中真正需要的數(shù)據(jù)。邏輯運(yùn)算符運(yùn)算結(jié)果只有“真”(TRUE)和“假”(FALSE)兩個(gè)值(稱為“邏輯值”)，LINGO中用數(shù)字1代表TRUE，其他值(典型的值是0)都是FALSE。在LINGO中，邏輯運(yùn)算(表達(dá)式)通常作為過(guò)濾條件使用,邏輯運(yùn)算符有9種，可以分成兩類(lèi)：#AND#(與),#OR#(或),#NOT#(非)：邏輯值之間的運(yùn)算，它們操作的對(duì)象本身已經(jīng)是邏輯值或邏輯表達(dá)式，計(jì)算結(jié)果也是邏輯值。#EQ#(等于),#NE#(不等于),#GT#(大于),#GE#(大于等于),#LT#(小于),#LE#(小于等于)：是“數(shù)與數(shù)之間”的比較,也就是它們操作的對(duì)象本身必須是兩個(gè)數(shù),計(jì)算得到的結(jié)果是邏輯值。關(guān)系運(yùn)算符表示是“數(shù)與數(shù)之間”的大小關(guān)系，在LINGO中用來(lái)表示優(yōu)化模型的約束條件。LINGO中關(guān)系運(yùn)算符有3種：<(即<=，小于等于),=(等于)，>(即>=，大于等于)(在優(yōu)化模型中約束一般沒(méi)有嚴(yán)格小于、嚴(yán)格大于關(guān)系)運(yùn)算符的優(yōu)先級(jí)優(yōu)先級(jí)最高

最低運(yùn)算符#NOT#—(負(fù)號(hào))^*/+—(減法)#EQ##NE##GT##GE##LT##LE##AND##OR#<=>例4使用LINGO軟件計(jì)算6個(gè)發(fā)點(diǎn)8個(gè)收點(diǎn)的最小費(fèi)用運(yùn)輸問(wèn)題。產(chǎn)銷(xiāo)單位運(yùn)價(jià)如下表。單位銷(xiāo)地

運(yùn)價(jià)產(chǎn)地B1B2B3B4B5B6B7B8產(chǎn)量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352銷(xiāo)量3537223241324338

68minz=cijxij

i=1j=18s.t.xij≤ai

（i=1,2,……,6)

j=1

6xij=bj

（j=1,2,……,8)

i=1xij0（i=1,2,……,6

；j=1,2,……,8)建立模型：（產(chǎn)大于銷(xiāo)）設(shè)xij為從第i個(gè)產(chǎn)地調(diào)運(yùn)給第j個(gè)銷(xiāo)地的物資數(shù)量model:!6發(fā)點(diǎn)8收點(diǎn)運(yùn)輸問(wèn)題;sets:warehouses/wh1..wh6/:capacity;vendors/v1..v8/:demand;links(warehouses,vendors):cost,volume;endsets!目標(biāo)函數(shù);

min=@sum(links:cost*volume);!需求約束;

@for(vendors(J):

@sum(warehouses(I):volume(I,J))=demand(J));!產(chǎn)量約束;

@for(warehouses(I):

@sum(vendors(J):volume(I,J))<=capacity(I));

!這里是數(shù)據(jù);然后點(diǎn)擊工具條上的按鈕即可。使用LINGO軟件，編制程序如下：data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend集合的屬性相當(dāng)于以集合的元素為下標(biāo)的數(shù)組。這里的相當(dāng)于二維數(shù)組。它的兩個(gè)下標(biāo)分別來(lái)自集合warehouses和vendors，因此可以定義一個(gè)由二元對(duì)組成的新的集合，然后將定義成這個(gè)新集合的屬性。本例中集合的概念利用集合的概念，可以定義產(chǎn)地warehouses和銷(xiāo)地vendors兩個(gè)集合，分別有6個(gè)和8個(gè)元素(下標(biāo))，其屬性分別為產(chǎn)量capacity和銷(xiāo)量demand。但從各個(gè)產(chǎn)地到銷(xiāo)地的單位運(yùn)價(jià)和決策變量(運(yùn)送量)與集合warehouses和集合vendors都有關(guān)系的。該如何定義這樣的屬性？輸入程序

定義了三個(gè)集合，其中l(wèi)inks在前兩個(gè)集合warehouses和vendors的基礎(chǔ)上定義model:!6發(fā)點(diǎn)8收點(diǎn)運(yùn)輸問(wèn)題;sets:warehouses/wh1..wh6/:capacity;vendors/v1..v8/:demand;links(warehouses,vendors):cost,volume;endsets!目標(biāo)函數(shù);

min=@sum(links:cost*volume);!需求約束;

@for(vendors(J):

@sum(warehouses(I):volume(I,J))=demand(J));!產(chǎn)量約束;

@for(warehouses(I):

@sum(vendors(J):volume(I,J))<=capacity(I));

!這里是數(shù)據(jù);LINGO建模語(yǔ)言也稱為矩陣生成器（MATRIXGENERATOR）。類(lèi)似warehouses和vendors直接把元素列舉出來(lái)的集合，稱為基本集合(primaryset),而把links這種基于其它集合而派生出來(lái)的二維或多維集合稱為派生集合(derivedset)。由于是warehouses和vendors生成了派生集合links，所以warehouses和vendors稱為links的父集合。data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend表示集合links中的元素就是集合warehouses和vendors的元素組合成的有序二元組，從數(shù)學(xué)上看link是warehouses和vendors的笛卡兒積，也就是說(shuō)links={（S，T）|Swarehouses，Tvendors}因此，其屬性cost和volume也就是一個(gè)6*8的矩陣（或者說(shuō)是含有48個(gè)元素的二維數(shù)組）。2023/5/718目標(biāo)函數(shù)的定義方式@SUM(集合（下標(biāo)）：關(guān)于集合的屬性的表達(dá)式)對(duì)語(yǔ)句中冒號(hào)“：”后面的表達(dá)式，按照“：”前面的集合指定的下標(biāo)（元素）進(jìn)行求和。約束的定義方式循環(huán)函數(shù)@FOR(集合(下標(biāo))：關(guān)于集合的屬性的約束關(guān)系式)對(duì)冒號(hào)“：”前面的集合的每個(gè)元素（下標(biāo)），冒號(hào)“：”后面的約束關(guān)系式都要成立。例5分配問(wèn)題（指派問(wèn)題，AssignmentProblem）要求給每個(gè)人分配一項(xiàng)工作，并要求分配完這些工作，以使完成全部任務(wù)的總時(shí)間為最小。該問(wèn)題可表示如下：這是個(gè)給n個(gè)人分配n項(xiàng)工作以獲得某個(gè)最高總效果的問(wèn)題。第i個(gè)人完成第j項(xiàng)工作需要平均時(shí)間。

顯然，此問(wèn)題可看作是運(yùn)輸問(wèn)題的特殊情況?？蓪⒋藛?wèn)題看作具有n個(gè)源和n個(gè)匯的問(wèn)題，每個(gè)源有1單位的可獲量，而每個(gè)匯有1單位的需要量。從表面看，這問(wèn)題要求用整數(shù)規(guī)劃以保證能取0或1。然而，幸運(yùn)的是