LINGO在圖論中的應(yīng)用課件

第2章LINGO在圖論和

網(wǎng)絡(luò)模型中的應(yīng)用圖是一種直觀形象地描述已知信息的方式，它使事物之間的關(guān)系簡潔明了，是分析問題的有用工具，很多實際問題可以用圖來描述。一、圖的基本概念

圖論是以圖為研究對象的數(shù)學(xué)分支，在圖論中，圖由一些點和點之間的連線所組成．

稱圖中的點為頂點（節(jié)點），稱連接頂點的沒有方向的線段為邊，稱有方向的線段為?。芯€段都沒有方向的圖稱為無向圖，所有線段都有方向的圖稱為有向圖，既有邊也有弧的圖稱為混合圖．點與邊相連接稱為關(guān)聯(lián)，與邊e關(guān)聯(lián)的頂點稱為該邊的端點，與同一條邊關(guān)聯(lián)的兩個頂點稱為相鄰頂點，與同一個頂點關(guān)聯(lián)的邊稱為相鄰邊．無圈的連通圖稱為樹，如果一棵樹T包含了圖G的所有頂點，稱T為G的生成樹．如果圖G的每條邊e都對應(yīng)一個實數(shù)C(e)，稱C(e)為該邊e的權(quán)，稱圖G為賦權(quán)圖．通常稱賦權(quán)的有向圖為網(wǎng)絡(luò)．二、最短路問題1.動態(tài)規(guī)劃法(1)問題的描述給定N個點Pi(i=1,2,...,n)組成集合{Pi}，集合中任一點Pi到另一點Pj的距離用Wij表示，如果Pi到Pj沒有弧聯(lián)結(jié)(無通路)，則規(guī)定Wij=+∞，又規(guī)定，Wii=0(i=1,2,...,n)，指定一個終點PN，要求從Pi點出發(fā)到PN的最短路線。可以用動態(tài)規(guī)劃的方法來求最短路問題，下面舉例說明其算法原理。2.算法原理舉例：圖中A,B,...,G表示7個城市，連線表示城市之間有道路相通，連線旁的數(shù)字表示道路的長度Wij，現(xiàn)要從城市A到G找出一條最短路線。該問題有三個階段，第一階段從A到B或C，第二階段到D,E或F，第三階段到終點G，我們從終點向前倒過來找。AGFEDCB24123133134第一階段，出發(fā)點只有一個A，從A出發(fā)分別經(jīng)過B,C,至終點G的里程分別為：WAB+f(B)=2+4=6WAC+f(C)=4+3=7故A到G的最短路是上述兩者的最小值6，可以寫成f(A)=min{WAj+f(j)}=6，j是上一步考察過的兩個點B,C，現(xiàn)在已經(jīng)到了起點，結(jié)束運算，從A到G的最短路為6。上述算法可以簡寫成N是終點，1是起點，j是與i相聯(lián),上一步考察過，且與終點相通、f(j)為已知的點。編寫LINGO程序如下：model:sets:cities/A,B,C,D,E,F,G/:FL;!定義7個城市;roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;!定義哪些城市之間有路相聯(lián)，W為里程，P用來存放最短路的路徑;endsetsdata:W=24331231134;enddataN=@SIZE(CITIES);FL(N)=0;!終點的F值為0;@for(cities(i)|i#lt#N:FL(i)=@min(roads(i,j):W(i,j)+FL(j)));!遞推計算各城市F值;!顯然，如果P(i,j)=1,則點i到點n的最短路徑的第一步是i-->j，否則就不是。由此，我們就可方便的確定出最短路徑;@for(roads(i,j):P(i,j)=@if(FL(i)#eq#W(i,j)+FL(j),1,0));end程序中的語句roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;定義的集合稱為稀疏集合，本例中cities有7個成員，但是并非每個城市到其它6個城市都有路相通，只有部分城市之間有路，故定義衍生集合roads時用列舉法列出有路相通的每對城市

。2．0－1規(guī)劃法用0－1規(guī)劃法也能求解最短路問題，其思路如下．設(shè)起點為1，終點為n．引入0－1型決策變量Xij，如果弧(i,j)在最短路上，則Xij=1，否則Xij=0．對于除了起點1和終點n以外的任意一個頂點i，如果，說明從i出發(fā)的所有弧中必然有一條弧在最短路上，也就是說最短路經(jīng)過該頂點，此時所有從其它頂點到達(dá)該頂點的弧中必然也有一條弧在最短路上，因而必有：如果，說明最短路不經(jīng)過頂點i，故必有兩種情況可以合并寫成：對于起點1，則必然滿足：對于終點n，則必有：對于上例，編寫LINGO程序如下：model:sets:cities/A,B,C,D,E,F,G/;!定義7個城市;roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,X;!定義哪些城市之間有路相聯(lián)，W為里程，X為0－1型決策變量;endsetsdata:W=24331231134;enddata

N=@SIZE(CITIES);MIN=@SUM(roads:W*X);@FOR(cities(i)|i#GT#1#AND#i#LT#N:@SUM(roads(i,j):X(i,j))=@SUM(roads(j,i):X(j,i)));@SUM(roads(i,j)|i#EQ#1:X(i,j))=1;

@SUM(roads(i,j)|j#EQ#N:X(i,j))=1;end

計算結(jié)果與動態(tài)規(guī)劃法相同．程序中的最后一個約束方程可以去掉，因為有了前面兩個約束條件(共n-1個約束方程)可以導(dǎo)出最后一個約束方程，即終點的約束方程與前面n-1個約束方程線性相關(guān)．保留該約束方程，LINGO求解時也不會產(chǎn)生任何問題，因為LINGO會自動刪除多余的方程．該方法與前面的方法相比，靈活性稍差，它一次只能求出指定起點到指定終點的最短路，如果更改起點，則必須改動程序然后重新求解．TSP是典型的組合優(yōu)化問題，也是公認(rèn)的NP完全難題。不算出發(fā)地。n個城市有(n-1)!種排列方法，每一種旅行路線是排列中的一種，當(dāng)n變大時，計算量呈指數(shù)增長，窮舉法所費時間是難以承受的。為此，多年以來有許多人研究了一些近似算法。我們把TSP問題轉(zhuǎn)化為0-1規(guī)劃，然后用LINGO來求解。1.方法一：判斷各邊是否包含在旅行路線中引入0-1整數(shù)變量xij(且i≠j)：xij=1表示路線從i到j(luò)，即邊i-j在旅行路線中，而xij＝0則表示不走i-j路線目標(biāo)函數(shù)首先必須滿足約束條件：對每個城市訪問一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為引入0-1整數(shù)變量xij(且i≠j)：xij=1表示路線從i到j(luò)，xij＝0則表示不走i-j路線目標(biāo)函數(shù)首先必須滿足約束條件：對每個城市訪問一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為從某個城市到達(dá)j一次且僅一次，表示為：以上建立的模型類似于指派問題的模型，對TSP問題只是必要條件，并不充分。附加約束條件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j。下面證明：(1)任何含子巡回的路線都必然不滿足該約束條件（不管ui如何取值）；(2)全部不含子巡回的整體巡回路線都可以滿足該約束條件（只要ui取適當(dāng)值）。用反證法證明(1),假設(shè)存在子巡回，則至少有兩個子巡回。那么（必然）至少有一個子巡回中不含起點城市1，如上圖中的4－5－6－4，則必有u4-u5+n≤n-1，u5-u6+n≤n-1，u6-u4+n≤n-1，把這三個不等式加起來得到n≤n-1，不可能，故假設(shè)不能成立。而對整體巡回，因為附加約束中j≥2,不包含起點城市1，故不會發(fā)生矛盾。對于整體巡回路線，只要ui取適當(dāng)值，都可以滿足該約束條件：(ⅰ)對于總巡回上的邊，xij=1,ui可取訪問城市i的順序數(shù)，則必有ui-uj＝-1，約束條件ui-uj+nxij≤n-1變成：-1+n≤n-1，必然成立。(ⅱ)對于非總巡回上的邊，因為xij=0，約束條件ui-uj+nxij≤n-1變成-1≤n-1，肯定成立。綜上所述，該約束條件只限止子巡回，不影響其它，于是TSP問題轉(zhuǎn)化成了一個混合整數(shù)線性規(guī)劃問題。data:!距離矩陣;dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;!這里可改為你要解決的問題的數(shù)據(jù);enddata!目標(biāo)函數(shù);min=@sum(link:dist*x);

@FOR(city(K):

!進入城市K;

@sum(city(I)|I#ne#K:x(I,K))=1;

!離開城市K;

@sum(city(J)|J#ne#K:x(K,J))=1;);

!保證不出現(xiàn)子圈;@for(city(I)|I#gt#1:

@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)<=n-1););

!限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;

@for(city(I):u(I)<=n-1);

@for(link:@bin(x));!定義X為0\1變量;end計算結(jié)果：目標(biāo)函數(shù)值：6610路線：1-3-6-2-5-4-12.方法二：對城市排序，找出最優(yōu)排序在現(xiàn)實中的城市交通圖中，有些城市之間有直接道路，有些則沒有，如果兩點之間沒有直接的通路，則兩點之間的距離取最短路（經(jīng)過其它點），即用任意兩點之間的最短路Cij作為圖的距離矩陣，于是該圖可以看成是一個完全圖（即任意一對頂點都有一條邊相連的圖），此時形式上的環(huán)形巡回路線實際上個別點有可能不止經(jīng)過一次。設(shè)某個城市為旅行的出發(fā)地和終點（相當(dāng)于總部所在地），旅行者從該城市出發(fā)到其它n個城市各一次且僅一次，最后回到出發(fā)地。我們把行進路線分成n步，每一步到一個城市（第n+1步返回出發(fā)地），于是一條旅行路線就相當(dāng)于n個城市的一種排列，n個城市共有n!種排列方式。排序不同則總里程（或費用）可能不同，總里程（或總費用）最小的排序就是我們要尋找的最優(yōu)路線。引入0-1型決策變量Xkj，下標(biāo)k表示旅行的步數(shù)，下標(biāo)j表示到達(dá)哪一個城市，Xkj=1表示旅行者第k個目的地（到達(dá)點）是城市j，Xkj=0則表示否。用lj表示總部到各城市的距離，用Cij表示城市i與城市j之間的最短路。從出發(fā)地到第1個點的路程為從最后一個點返回出發(fā)地的里程為

假設(shè)在第k步郵車達(dá)到城市i，在第k+1步達(dá)到支局j，即Xki=Xk+1,j=1，則走過的里程為：Cij·Xki·Xk+1,j從第1點到第n點走過的總里程為目標(biāo)函數(shù)為約束條件有以下2條：(1)每一步到達(dá)一個城市，即(2)每一個城市必須到一次且只需一次，即綜上所述，可以把TSP問題轉(zhuǎn)化成如下非線性0-1

規(guī)劃以上規(guī)劃種允許包含其它約束條件。用LINGO可以求解該規(guī)劃，舉例如下。某縣郵局和10個鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運輸網(wǎng)絡(luò)，已知縣局到各支局的距離和支局之間的距離矩陣（數(shù)據(jù)在程序中）。用一輛郵車完成郵件運輸任務(wù)，郵車從縣局出發(fā)到各支局去一次且只需一次，最后回到縣局，求總路程最短的行駛路線。編寫LINGO程序如下：MODEL:SETS:CITY/1..10/:JL;STEP/1..10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETSDATA:JL=71,56,27,30,28,26,15,9,30,27;C=0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,0,29 98,83,54,57,55,47,29,26,29,0;ENDDATA@FOR(LINE:@BIN(X));M1=@SIZE(STEP);@FOR(CITY(I):@SUM(STEP(N):X(N,I))=1);@FOR(STEP(N):@SUM(CITY(I):X(N,I))=1);L1=@SUM(CITY(I):(X(1,I)+X(M1,I))*JL(I));LX=@SUM(STEP(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));MIN=L1+LX;END在程序運行前需要對LINGO的參數(shù)作必要的設(shè)置。對于非線性規(guī)劃，LINGO提供兩種求解方法，一種是“GlobalSolver”（稱為全局優(yōu)化求解器），另一種是“MultistartSolver”（稱為多起點算法），全局優(yōu)化求解器優(yōu)點是確保找到全局最優(yōu)解，缺點是有時需要較長運行時間。多起點算法的優(yōu)點是節(jié)省運行時間，但不能保證找到的解就是全局最優(yōu)解，多設(shè)置起點數(shù)往往找到的解就是全局最優(yōu)解。點擊菜單“Options”，再打開全局優(yōu)化求解器“GlobalSolver”選項，可以選或不選“GlobalSolver”，當(dāng)選擇多起點算法“MultistartSolver”時，需要設(shè)置起點數(shù)，若選擇“SolverDecides”表示由LINGO決定。對以上程序，我們選擇“GlobalSolver”，點擊菜單“Options”，在全局優(yōu)化求解器“GlobalSolver”選項框內(nèi)打“√”，再點擊“確定”。運行以上程序，費時4分多鐘，得到最優(yōu)解：目標(biāo)函數(shù)值（總路程）260公里郵車的行駛路線為：縣局→8→9→10→7→6→5→4→1→2→3→縣局3.多旅行商問題在現(xiàn)實中問題中，有時候不是由一人走遍所有點，而是由幾個人分工合作，每個人只到其中部分城市，每個點都有人來過一次且只需一次，事先不指定誰到哪些點，求出使總路程最小的旅行規(guī)劃（每個人的行走路線）。例如郵路規(guī)劃中，為了在允許的時間內(nèi)完成郵件運輸任務(wù)，縣局的郵車往往不止1輛，而是用若干輛郵車分工運輸，只要保證每個支局有郵車來過即可，為了節(jié)省行駛費用，需要規(guī)劃幾輛郵車的最佳路線。這就是多旅行商問題。多旅行商問題的提法如下：有n+1個城市，相互間的路程（或旅行費用）為已知，有k個旅行商都從總部所在城市出發(fā)，赴其它城市旅行推銷，分工遍歷其余n個城市，即每個城市各有任意一名旅行商來過一次且僅一次，最后都回到出發(fā)地，目標(biāo)是總路程最短或總費用最省。多旅行商問題在物流配送、郵路優(yōu)化等方面具有較高的實用價值，而在現(xiàn)實問題中，研究對象往往不是單純的旅行商問題，而要考慮各種約束條件，例如時間約束、載重量約束等等。研究這一類帶約束條件的多旅行商問題具有很強的現(xiàn)實意義。

在現(xiàn)實的多旅行商問題中，往往帶有約束條件，例如時間約束、載重量約束等等。帶約束條件的多旅行商問題具有廣泛現(xiàn)實意義，且是極具挑戰(zhàn)性的難題，我們?nèi)匀话阉D(zhuǎn)化為0-1非線性規(guī)劃并編成LINGO程序來求解。實例某縣郵政局管轄16個支局，已知縣局到各支局的距離以及16個支局之間的距離矩陣。寄達(dá)各支局和各支局收寄的郵件(袋)如下表所示：縣郵局和各支局分布圖每一輛郵車最多裝載65袋郵件，郵車的運行成本為3元/公里。試用最少郵車，并規(guī)劃郵車的行駛路線使總費用最省。分析：首先考慮最少郵車數(shù)量，由題目所給表中數(shù)據(jù)，寄達(dá)16個支局的郵件總數(shù)為176袋，從各支局收寄的郵件總數(shù)為170袋，每一輛郵車最多容納65袋郵件，至少需要176/65≈2.7輛郵車，由于郵車數(shù)量為整數(shù)，故最少需要3輛郵車。如果3輛郵車能夠完成郵件運輸任務(wù)，則3輛車就是郵車數(shù)量的最優(yōu)解。

運輸費用與行駛里程成正比，總里程最短對應(yīng)總費用最省。把16個支局放在一起作為一個整體考慮，找出3條郵路，每條郵路都從縣局出發(fā)，到若干支局進行卸裝，最后回到縣局。各郵車路過的支局?jǐn)?shù)量未知，合理安排各郵車的行駛路線，由3輛郵車分別承包運輸，在滿足運載量約束前提下，把3條巡回路線的總里程最小作為優(yōu)化的目標(biāo)。該問題相當(dāng)于附帶約束條件的多旅行商模型。引入0-1型決策變量Xkj,Ykj,Zkj，分別表示3輛郵車第k步到達(dá)支局j，下標(biāo)k表示郵車行走的步數(shù)，下標(biāo)j表示到達(dá)哪一個支局，當(dāng)決策變量Xkj,Ykj,Zkj等于1時分別表示某郵車第k個裝卸點是支局j，等于0時表示否。設(shè)各郵車管轄的支局?jǐn)?shù)量分別為m1,m2,m3，則m1+m2+m3=16。約束條件有以下3條：(1)任何一輛車在任何一步到達(dá)一個支局

，即(2)任何一個支局必須有一輛郵車到達(dá)一次且只需要一次，即

(3)在郵車行進的任何路段上，裝載的郵件不超過65袋。

設(shè)寄達(dá)各支局的郵件量為Pj，各支局收寄的郵件量為Qj。

裝載量是動態(tài)變化的，以第1輛郵車為例，出發(fā)時的裝載量為到第1個支局卸裝以后，裝載量變?yōu)樵谛旭傔^程中，裝載量的遞推公式為約束條件為綜上所述，建立多旅行商問題的0-1規(guī)劃模型如下：裝載量的計算公式為：編寫LINGO程序如下：MODEL:SETS:STATION/1..16/:JL,P,Q;STEPX/1..6/:WX;STEPY/1..5/:WY;STEPZ/1..5/:WZ;LINEX(STEPX,STATION):X;LINEY(STEPY,STATION):Y;LINEZ(STEPZ,STATION):Z;LINKS(STATION,STATION):C;ENDSETSDATA:JL=27361711243144403020252121182736;P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10,16;C=031273851587167574752482141526131019332732456453476157524856632719014273447493929423838293844

3833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918

526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090;ENDDATA@FOR(LINEX:@BIN(X));@FOR(LINEY:@BIN(Y));@FOR(LINEZ:@BIN(Z));M1=@SIZE(STEPX);M2=@SIZE(STEPY);M3=@SIZE(STEPZ);@FOR(STATION(I):@SUM(STEPX(N):X(N,I))+@SUM(STEPY(N):Y(N,I))+@SUM(STEPZ(N):Z(N,I))=1);@FOR(STEPX(N):@SUM(STATION(I):X(N,I))=1);@FOR(STEPY(N):@SUM(STATION(I):Y(N,I))=1);@FOR(STEPZ(N):@SUM(STATION(I):Z(N,I))=1);WX0=@SUM(STATION(I):P*@SUM(STEPX(N):X(N,I)));WY0=@SUM(STATION(I):P*@SUM(STEPY(N):Y(N,I)));WZ0=@SUM(STATION(I):P*@SUM(STEPZ(N):Z(N,I)));WX(1)=WX0-@SUM(STATION(J):(P(J)-Q(J))*X(1,J));WY(1)=WY0-@SUM(STATION(J):(P(J)-Q(J))*Y(1,J));WZ(1)=WZ0-@SUM(STATION(J):(P(J)-Q(J))*Z(1,J));@FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-@SUM(STATION(J):(P(J)-Q(J))*X(N,J)));@FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Y(N,J)));@FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Z(N,J)));WX0<=65;WY0<=65;WZ0<=65;@FOR(STEPX(N):WX(N)<=65);@FOR(STEPY(N):WY(N)<=65);@FOR(STEPZ(N):WZ(N)<=65);L1=@SUM(STATION(I):(X(1,I)+X(M1,I))*JL(I));L2=@SUM(STATION(I):(Y(1,I)+Y(M2,I))*JL(I));L3=@SUM(STATION(I):(Z(1,I)+Z(M3,I))*JL(I));LX=@SUM(STEPX(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));LY=@SUM(STEPY(N)|N#LT#M2:@SUM(LINKS(I,J):C(I,J)*Y(N,I)*Y(N+1,J)));LZ=@SUM(STEPZ(N)|N#LT#M3:@SUM(LINKS(I,J):C(I,J)*Z(N,I)*Z(N+1,J)));MIN=L1+L2+L3+LX+LY+LZ;END三輛郵車各自負(fù)責(zé)的支局?jǐn)?shù)量有若干種分配方法，例如有6,5,5、6,6,4、7,5,4等不同分組法。經(jīng)過試驗，以6,5,5方案最優(yōu)。目標(biāo)函數(shù)值（3條郵路的總里程）為343km。第一條郵路：縣局→10→9→8→7→5→6→縣局，總里程121km，沿途各段郵件的裝載量為64,56,58,63,65,61,65袋。注意：如果支局5和6的先后次序倒過來，即走7→6→5→縣局，則里程為106km，減少15km，但是在支局6卸裝以后，郵件達(dá)69袋，超過了裝載量約束，看來先到支局5，后到支局6是因為避免超載的原因，被迫繞路，整體上仍然保持最優(yōu)。第二條郵路：縣局→14→15→16→11→12→縣局，總里程105km，沿途各段郵件的裝載量為61,55,52,54,49,54袋。第三條郵路：縣局→13→1→2→3→4→縣局，總里程117km，沿途各段郵件的裝載量為51,53,52,51,50,51袋。三條郵路的圖形如圖所示

四、最小生成樹和最優(yōu)連線問題的提出：要建造一個連接若干城市的通訊網(wǎng)絡(luò)，已知城市i與j之間架設(shè)通訊線路所需費用為cij，請設(shè)計一個既能使所有城市都能接通，又使總費用最小的的方案。在圖論中，連通并且無圈的無向圖稱為樹。設(shè)G是具有n個頂點的無向連通圖，則G是樹的充分必要條件是G有n-1條邊。若T是包含G的全部頂點的子圖，它又是樹，則稱T是G的生成樹。如果圖的邊有權(quán)（對應(yīng)于邊的實數(shù)），則權(quán)的和最小的生成樹稱為最小生成樹，最優(yōu)連線就是尋找圖的最小生成樹(MinimalSpanningTree，簡稱MST)。許多實際問題都可以歸結(jié)為最小生成樹。例如,如何修筑一些公路把若干個城鎮(zhèn)連接起來；如何架設(shè)通訊網(wǎng)絡(luò)將若干個地區(qū)連接起來；如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等。為了說明問題,以下面的問題作為范例。范例：假設(shè)某電力公司計劃在七個村莊架設(shè)電線，各村莊之間的距離如圖所示。試求出使電線總長度最小的架線方案。節(jié)點1表示樹根，點i到點j的距離用Cij表示，當(dāng)兩個節(jié)點之間沒有線路相通時，兩點之間距離用M(很大的實數(shù))表示。引入0-1整數(shù)變量xij：xij=1(且i≠j)表示從i到j(luò)的邊在樹中，xij＝0則表示邊不在樹中。目標(biāo)函數(shù)約束條件：(1)除樹根外每個點都有線路通到(且只需要一次)表示為(2)至少有一條線路從1出來以上約束條件是必要條件，但不充分，類似于TSP問題，增加一個變量u，再附加約束條件：(1)限制uj的取值范圍為：u1=0，1≤uj≤n-1，j=2,3,...,n；用以下不等式可以達(dá)到目的：uj≥1且uj≤

n-1-(n-2)x1j，j>1，(2)如果線路從j到k，則uk=uj+1，且避免來回重復(fù)和圈，約束條件為:uj≥uk+xkj-(n-2)(1-xkj)+(n-3)xjk，1≤k≤n，2≤j≤nj≠k；最優(yōu)連線(最小生成樹)轉(zhuǎn)化為混合整數(shù)規(guī)劃：編寫LINGO程序如下：MODEL:sets:city/1..7/:u;!定義7個城市;link(city,city):dist,x;!距離矩陣和決策變量;endsetsn=@size(city);data:!dist是距離矩陣;dist=034710010010030324100100430100571007210002100610045201410010071001021001001006420;!這里可改為你要解決的問題的數(shù)據(jù);enddata

min=@sum(link:dist*x);!目標(biāo)函數(shù);U(1)=0;@for(link:@bin(x));!定義X為0\1變量;@FOR(city(K)|K#GT#1:@sum(city(I)|I#ne#K:x(I,K))=1;@for(city(J)|J#gt#1#and#J#ne#K:

u(J)>=u(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K);););@sum(city(J)|J#GT#1:x(1,J))>=1;@for(city(K)|K#gt#1:U(K)>=1;U(K)<=N-1-(N-2)*X(1,K););end計算結(jié)果：目標(biāo)函數(shù)值(最優(yōu)連線的長度)為13，最優(yōu)連線的構(gòu)成如圖所示4123567五、最大流問題1．問題的描述設(shè)有一批物資，要從A市通過公路網(wǎng)絡(luò)（內(nèi)含一些中轉(zhuǎn)站）運往B市，已知每段公路的運輸能力有限制（流量限制），問應(yīng)如何安排運輸方案，才能使總運量最大？這就是網(wǎng)絡(luò)最大流問題．例：下圖是從發(fā)貨地①到目的地⑥的有向運輸網(wǎng)絡(luò)，稱點①為發(fā)點（源），點⑥為收點（匯），有向邊（?。┡赃叺臄?shù)字是該弧的流量（運輸能力）限制，求①－⑥的最大流．2、數(shù)學(xué)模型

對每一條弧(頂點i到j(luò))，定義f(i,j)為該弧上從頂點i到頂點j的流量，用Cij表示其上的流量限制．則對任意一個中轉(zhuǎn)點，流進與流出相等，但頂點①只有流出，頂點⑥只有流進，并且兩者大小相等(方向相反)，如果我們在圖上虛擬一條從⑥－①的弧，其流量不受限制，并假設(shè)從①流到⑥的總量又從該虛擬弧上返回①，整個網(wǎng)絡(luò)系統(tǒng)構(gòu)成一個封閉的不停流動的回路，則對任意頂點都滿足流進等于流出．

目標(biāo)函數(shù)是maxf(n,1)，n是收點，1是發(fā)點.約束條件有兩條：(1)對每個頂點，流進等于流出，即等式左邊的求和是