Lingo在圖論中的應(yīng)用

LINGO在圖論中的應(yīng)用一、最短路問題AGFEDCB24123133134目標(biāo)函數(shù)是最短路上的各條弧的長度之和(總里程)最小，于是最短路問題可以用如下0－1規(guī)劃來描述：式中表示全體邊的集合

。0－1規(guī)劃法建模對于上例，編寫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會自動刪除多余的方程．該方法與前面的方法相比，靈活性稍差，它一次只能求出指定起點到指定終點的最短路，如果更改起點，那么必須改動程序然后重新求解．二、旅行售貨商模型旅行售貨商問題(又稱貨郎擔(dān)問題，TravelingSalesmanProblem簡稱TSP模型〕，是運籌學(xué)的一個著名命題。模型：有一個推銷商，從某個城市出發(fā)，要遍訪假設(shè)干城市各一次且僅一次，最后返回出發(fā)城市。從城市i到j(luò)的旅費為Cij，問他應(yīng)按怎樣的次序訪問這些城市，使得總旅費最少？稱能到每個城市一次且僅一次的路線為一個巡回(圈)。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問題只是必要條件，并不充分。例如，用圖示路線連接六個城市，滿足以上兩個約束條件，但這樣的路線出現(xiàn)了兩個子回路，兩者之間不通，不構(gòu)成整體巡回路線。為此需要考慮增加充分的約束條件以防止產(chǎn)生子巡回。下面介紹一種方法：增加變量ui,i=2,3,…,n，〔它的大小可以取整數(shù)：例如從起點出發(fā)所到達(dá)的城市u=2,依此類推〕。312456附加約束條件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j。TSP問題可以表示為規(guī)劃：TSP問題的LINGO模型!旅行售貨員問題;model:sets:city/1..6/:u;!定義6個城市;link(city,city):dist,!距離矩陣;x;!決策變量;endsetsn=@size(city);data:!距離矩陣;dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;!這里可改為你要解決的問題的數(shù)據(jù);enddata!目標(biāo)函數(shù);min=@sum(link:dist*x);

@FOR(city(K):

!進(jìn)入城市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ā)地。我們把行進(jìn)路線分成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”選項，可以選或不選“Glob