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

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

。0－1規(guī)劃法建模對(duì)于上例，編寫(xiě)LINGO程序如下：model:sets:cities/A,B,C,D,E,F,G/;!定義7個(gè)城市;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計(jì)算結(jié)果與動(dòng)態(tài)規(guī)劃法相同．程序中的最后一個(gè)約束方程可以去掉，因?yàn)橛辛饲懊鎯蓚€(gè)約束條件(共n-1個(gè)約束方程)可以導(dǎo)出最后一個(gè)約束方程，即終點(diǎn)的約束方程與前面n-1個(gè)約束方程線性相關(guān)．保存該約束方程，LINGO求解時(shí)也不會(huì)產(chǎn)生任何問(wèn)題，因?yàn)長(zhǎng)INGO會(huì)自動(dòng)刪除多余的方程．該方法與前面的方法相比，靈活性稍差，它一次只能求出指定起點(diǎn)到指定終點(diǎn)的最短路，如果更改起點(diǎn)，那么必須改動(dòng)程序然后重新求解．二、旅行售貨商模型旅行售貨商問(wèn)題(又稱貨郎擔(dān)問(wèn)題，TravelingSalesmanProblem簡(jiǎn)稱TSP模型〕，是運(yùn)籌學(xué)的一個(gè)著名命題。模型：有一個(gè)推銷商，從某個(gè)城市出發(fā)，要遍訪假設(shè)干城市各一次且僅一次，最后返回出發(fā)城市。從城市i到j(luò)的旅費(fèi)為Cij，問(wèn)他應(yīng)按怎樣的次序訪問(wèn)這些城市，使得總旅費(fèi)最少？稱能到每個(gè)城市一次且僅一次的路線為一個(gè)巡回(圈)。TSP是典型的組合優(yōu)化問(wèn)題，也是公認(rèn)的NP完全難題。不算出發(fā)地。n個(gè)城市有(n-1)!種排列方法，每一種旅行路線是排列中的一種，當(dāng)n變大時(shí)，計(jì)算量呈指數(shù)增長(zhǎng)，窮舉法所費(fèi)時(shí)間是難以承受的。為此，多年以來(lái)有許多人研究了一些近似算法。我們把TSP問(wèn)題轉(zhuǎn)化為0-1規(guī)劃，然后用LINGO來(lái)求解。1.方法一：判斷各邊是否包含在旅行路線中引入0-1整數(shù)變量xij(且i≠j)：xij=1表示路線從i到j(luò)，即邊i-j在旅行路線中，而xij＝0那么表示不走i-j路線目標(biāo)函數(shù)首先必須滿足約束條件：對(duì)每個(gè)城市訪問(wèn)一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為引入0-1整數(shù)變量xij(且i≠j)：xij=1表示路線從i到j(luò)，xij＝0那么表示不走i-j路線目標(biāo)函數(shù)首先必須滿足約束條件：對(duì)每個(gè)城市訪問(wèn)一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為從某個(gè)城市到達(dá)j一次且僅一次，表示為：以上建立的模型類似于指派問(wèn)題的模型，對(duì)TSP問(wèn)題只是必要條件，并不充分。例如，用圖示路線連接六個(gè)城市，滿足以上兩個(gè)約束條件，但這樣的路線出現(xiàn)了兩個(gè)子回路，兩者之間不通，不構(gòu)成整體巡回路線。為此需要考慮增加充分的約束條件以防止產(chǎn)生子巡回。下面介紹一種方法：增加變量ui,i=2,3,…,n，〔它的大小可以取整數(shù)：例如從起點(diǎn)出發(fā)所到達(dá)的城市u=2,依此類推〕。312456附加約束條件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j。TSP問(wèn)題可以表示為規(guī)劃：TSP問(wèn)題的LINGO模型!旅行售貨員問(wèn)題;model:sets:city/1..6/:u;!定義6個(gè)城市;link(city,city):dist,!距離矩陣;x;!決策變量;endsetsn=@size(city);data:!距離矩陣;dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;!這里可改為你要解決的問(wèn)題的數(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āi)城市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問(wèn)題的最優(yōu)解;

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

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

規(guī)劃以上規(guī)劃種允許包含其它約束條件。用LINGO可以求解該規(guī)劃，舉例如下。某縣郵局和10個(gè)鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運(yùn)輸網(wǎng)絡(luò)，縣局到各支局的距離和支局之間的距離矩陣〔數(shù)據(jù)在程序中〕。用一輛郵車完成郵件運(yùn)輸任務(wù)，郵車從縣局出發(fā)到各支局去一次且只需一次，最后回到縣局，求總路程最短的行駛路線。編寫(xiě)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在程序運(yùn)行前需要對(duì)LINGO的參數(shù)作必要的設(shè)置。對(duì)于非線性規(guī)劃，LINGO提供兩種求解方法，一種是“GlobalSolver”〔稱為全局優(yōu)化求解器〕，另一種是“MultistartSolver”〔稱為多起點(diǎn)算法〕，全局優(yōu)化求解器優(yōu)點(diǎn)是確保找到全局最優(yōu)解，缺點(diǎn)是有時(shí)需要較長(zhǎng)運(yùn)行時(shí)間。多起點(diǎn)算法的優(yōu)點(diǎn)是節(jié)省運(yùn)行時(shí)間，但不能保證找到的解就是全局最優(yōu)解，多設(shè)置起點(diǎn)數(shù)往往找到的解就是全局最優(yōu)解。點(diǎn)擊菜單“Options”，再翻開(kāi)全局優(yōu)化求解器“GlobalSolver”選項(xiàng)，可以選或不選“Glob