圖與網(wǎng)絡模型

歡迎各位同學學習第八講內容導航

1

運輸問題與指派問題2

最短路問題和最大流問題3

最優(yōu)連線問題與旅行商問題習題第八講圖與網(wǎng)絡模型1

運輸問題與指派問題本節(jié)內容導航1.1

運輸問題1.2

指派問題§1.1運輸問題

運輸問題(TransportationProblem)是圖論與網(wǎng)絡中的一個重要問題，也是一個典型的線性規(guī)劃問題.例1（運輸問題）返回導航

例1

就是典型的運輸問題，圖1給出了個產(chǎn)地，個銷地運輸問題的圖形.關于它的求解方法有兩類，一類是按照圖論的方法求解，另一類是化成線性規(guī)劃問題.這里介紹第二類方法，即用LINGO軟件求解運輸問題.圖1:個產(chǎn)地,個銷售地運輸問題的圖形2.運輸問題的數(shù)學表達式第個產(chǎn)地的運出量應小于或等于該地的生產(chǎn)量，即：第個銷地的運入量應等于該地的需求量，即：對例1，設xij

代表從第i個產(chǎn)地調運給第j

個銷地的物資數(shù)量。cij表示相應的運費，則目標函數(shù)為因此，運輸問題的數(shù)學表達式為:稱具有形如式

的線性規(guī)劃問題為運輸問題.

3.運輸問題的求解過程為了便于討論，以一個運輸問題實例的求解過程來介紹如何用LINGO軟件求解運輸問題模型.

例2(繼例1)設

即為有3個產(chǎn)地和4個銷地的運輸問題，其產(chǎn)量、銷量及單位運費如表1所示.試求總運費最少的運輸方案，以及總運費.下面寫出求解該問題的LINGO程序，并在程序中用到在第三章介紹的集與數(shù)據(jù)段，以及相關的循環(huán)函數(shù).

寫出相應的LINGO程序，程序名：exam0801.lg4MODEL:1]!3Warehouse,4CustomerTransportationProblem;2]sets:3]Warehouse/1..3/:a;4]Customer/1..4/:b;

5]Routes(Warehouse,Customer):c,x;6]endsets7]!Herearetheparameters;8]data:9]a=30,25,2110]b=15,17,22,12;11]c=6,2,6,7,12]4,9,5,3,13]8,8,1,5;14]enddata15]!Theobjective;16][OBJ]min=@sum(Routes:c*x);

17]!Thesupplyconstraints;18]@for(Warehouse(i):[SUP]19]@sum(Customer(j):x(i,j))<=a(i));20]!Thedemandconstraints;21]@for(Customer(j):[DEM]22]@sum(Warehouse(i):x(i,j))=b(j));END

在上述程序中，第16]表示運輸問題中目標函數(shù)(7.1).第18]

19]行表示約束條件(7.2),第21]22]行表示約束條件(7.3).

下面列出LINGO軟件的求解結果（僅保留非零變量）Globaloptimalsolutionfoundatiteration:6Objectivevalue:161.0000VariableValueReducedCostX(1,1)2.0000000.000000X(1,2)17.000000.000000X(1,3)1.0000000.000000X(2,1)13.000000.000000X(2,4)12.000000.000000X(3,3)21.000000.000000RowSlackorSurplusDualPriceOBJ161.0000-1.000000SUP(1)10.000000.000000§1.2指派問題

例3（指派問題）設有n個人,計劃作n項工作,其中表示第i個人做第j項工作的收益,現(xiàn)求一種指派方式，使得每個人完成一項工作，使總收益最大.

例3就是指派問題(AssignmentProblem).指派問題也是圖論中的重要問題，有相應的求解方法，如匈牙利算法.從問題的形式來看，指派問題是運輸問題的特例，也可以看成0-1規(guī)劃問題.返回導航1.指派問題的數(shù)學表達式

設變量為,當?shù)趥€人作第項工作時，,否則.因此，相應的線性規(guī)劃問題為

2.指派問題的求解過程

下面用一個具體的例子來說明指派問題

例4（繼例3）考慮例3中的情況,即6個人做6項工作的最優(yōu)指派問題，其收益矩陣如表2所示.

下面用LINGO程序再求解此問題，程序中仍然用到集、數(shù)據(jù)段和循環(huán)函數(shù).

寫出相應的LINGO程序，程序名exam0804.lg4.MODEL:1]!AssignmentProblemModel;2]sets:3]Flight/1..6/;4]Assign(Flight,Flight):c,x;

5]endsets6]!Hereisincomematrix;7]data:8]c=2015165479]171533128610]9121816301311]1281127191412]-9971021103213]-99-99-9961113;14]enddata15]

16]!Maximizevalveofassignments;

17]max=@sum(Assign:c*x);

18]@for(Flight(i):19]!Eachimustbeassignedtosomej;20]@sum(Flight(j):x(i,j))=1;21]!EachImustreceiveanassignment;22]@sum(Flight(j):x(j,i))=1;23]);END

程序中第12]

13]行中的-99意義與LINDO程序中的意義相同，當某人無法做某項工作時，取一個數(shù)值較大的負值.LINGO軟件計算結果如下（只列出非零變量）:Globaloptimalsolutionfoundatiteration:0Objectivevalue:135.0000VariableValueReducedCostX(1,1)1.0000000.000000X(2,3)1.0000000.000000X(3,2)1.0000000.000000X(4,4)1.0000000.000000X(5,6)1.0000000.000000X(6,5)1.0000000.000000

即第1個人做第1項工作，第2個人做第3項工作,第3個人做第2項工作，第4個人做第4項工作，第5個人做第6項工作，第6個人做第5項工作.總效益值為135.2最短路問題和最大流問題本節(jié)內容導航

本節(jié)概述

2.1最短路問題

2.2最大流問題

2.3

最小費與最大流問題

本節(jié)內容概述

最短路問題(ShortestPathProblems)和最大流問題(MaxiumumFlowProblems)是圖論另一類與優(yōu)化有關的問題，對于這兩在問題，實際上，圖論中已有解決的方法，如最短路問題的求解方法有Dijkstra算法，最大流問題的求解方法有標號算法.這里主要討論的是如何用LINGO軟件來求解最短路和最大流問題§2.1最短路問題

例5

（最短路問題）在圖7-3中，用點表示城市，現(xiàn)有共7個城市.點與點之間的連線表示城市間有道路相連.連線旁的數(shù)字表示道路的長度.現(xiàn)計劃從城市

到城市

鋪設一條天然氣管道，請設計出最小價格管道鋪設方案.

例5的本質是求從城市到城市的一條最短路.下面我們主要就線性規(guī)劃建模求解來分析返回導航2.最短路問題的數(shù)學表達式

假設圖有個頂點，現(xiàn)需要求從頂點1到頂點的最短路.設決策變量為,當,說明弧在定點1到n的路上；否則.目標函數(shù)為尋找一條節(jié)點1到節(jié)點n的通路，使其上權值和最小，故目標函數(shù)為(1)對節(jié)點1恰有一條路徑出去，缺不能有路徑回來，故有(2)對節(jié)點n恰有一條路徑到達，缺不能有路徑出去，故有(3)對其余節(jié)點進去和出去的路徑一樣多，故有(4)對不通的路徑不取，故有故總的線性規(guī)劃模型為

3.最短路問題的求解過程

例6(繼例5)求例5中，從城市A到城市D的最短路.

解：寫出相應的LINGO程序，程序名:exam0806.lg4.MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortestroutefromcity1tocity7;3]4]sets:5]!Hereisourprimitivesetofsevencities;6]cities/A,B1,B2,C1,C2,C3,D/;7]8]!TheDerivedset"roads"liststheroadsthat9]existbetweenthecities;10]roads(cities,cities)/11]A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C312]C1,DC2,DC3,D/:w,x;13]endsets14]15]data:16]!Herearethedistancesthatcorrespond

17]toabovelinks;18]w=24331231134;19]enddata20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(cities(i)|i#ne#1#and#i#ne#n:24]@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));25]@sum(roads(i,j)|i#eq#1:x(i,j))=1;

26]@FOR(roads(i,j):@bin(x(i,j)));END

在上述程序中，21]句中的n=@size(cities)是計算集cities的個數(shù)，這里的計算結果是,這樣編寫方法目的在于提高程序的通用性.22]句表示目標函數(shù)(14),即求道路的最小權值.23],24]句表示約束(15)中的情況，即最短路中中間點的約束條件.25]句表示約束中的情況，即最短路中起點的約束.

約束(15)中的情況，也就是最短路中終點的情況，沒有列在程序中，因為終點的約束方程與前個方程相關.當然，如果你將此方程列入到LINGO程序中，計算時也不會出現(xiàn)任何問題，因為LINGO

軟件可以自動刪除描述線性規(guī)劃可行解中的多余方程.

LINGO軟件計算結果（僅保留非零變量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCost

X(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000

即最短路是,最短路長為6個單位.

例7(設備更新問題)張先生打算購買一輛新轎車，轎車的售價是12萬元人民幣.轎車購買后，每年的各種保險費養(yǎng)護費等費用由表5所示.如果在5年之內，張先生將轎車售出，并再購買新年.5年之內的二手車銷售價由表6所示.請你幫助張先生設計一種購買轎車的方案，使5年內用車的總費用最少.

表5轎車的維護費車齡/年01234費用/萬元245912表6二手車的售價車齡/年12345售價/萬元76210

分析：設備更新問題是動態(tài)規(guī)劃的一類問題（事實上，最短路問題也是動態(tài)規(guī)劃的一類問題）,這里借助于最短路方法解決設備更新問題.

解：用6個點（1，2，3，4，5，6）表示各年的開始，各點之間的邊從邊表示左端點開始年至表示右端點結束所花的費用，這樣構成購車消費的網(wǎng)絡圖，如圖圖4所示.

記表示第年開始到年結束購車的總銷費,即由此得到寫出相應的LINGO程序，程序名：exam0807.lg4MODEL:1]sets:2]nodes/1..6/;3]arcs(nodes,nodes)|&1#lt#&2:c,x;4]endsets5]data:6]w=7122131447]71221318]712219]71210]7;11]enddata12]n=@size(nodes);13]min=@sum(arcs:c*x);14]@for(nodes(i)|i#ne#1#and#i#ne#n:15]@sum(arcs(i,j):x(i,j))=@sum(arcs(j,i):x(j,i)));16]@sum(arcs(i,j)|i#eq#1:x(i,j))=1;

17]@FOR(arcs(i,j):@bin(x(i,j)));END

程序中的第3]句中&1#1t#&2是邏輯運算語句，表示所說明的變量只有行小于列的部分，因此所說明的矩陣是上三角陣.LINGO軟件的計算結果（僅保留非零變量）如下

Globaloptimalsolutionfoundatiteration:0Objectivevalue:31.00000VariableValueReducedCostX(1,2)1.0000000.000000X(2,4)1.0000000.000000X(4,6)1.0000000.000000即第1年初購買轎車，第2年初賣掉，再購買新車，到第4年初賣掉，再購買新車使用到第5年末，總費用31萬元.

當然，上述方案不是唯一的，例如還有和,但無論何種方案，總費用均是31萬.某單位使用一臺設備，在每年年初，領導都要決定是購置新設備代替原來的舊設備，還是繼續(xù)使用舊設備。若購置新設備，需要支付一定的購置費用；若繼續(xù)使用舊設備，則需支付一定的維修費用。設該種設備在每年年初的價格如下表所示，使用不同時間（年）的設備所需要的年維修費用如下表所示。試制定一個五年之內的設備更新計劃，使總費用最少？第i年12345價格（萬元）1112131213使用年數(shù)xx≤11<x≤22<x≤33<x≤44<x≤5維修費用（萬元／年）5681118例8，思考(設備更新)：解用點vi表示“第i年年初購進一臺新設備”這種狀態(tài)i=1,2,…,5，用v6表示第5年底的狀態(tài)。對每個i=1,2,…,5，從vi到vi＋1,…,v6各畫一條弧，弧(vi,vj)表示在第

i年初購進一臺設備一直使用到第

j年初（即第

j-1年底）?；?vi,vj)的權為在第

i年初購進一臺新設備一直使用到第

j-1年年底所發(fā)生的總費用。例如(v1,v4)表示第1年年初購進一臺新設備，一直使用到第3年底。第i年12345價格（萬元）1112131213使用年數(shù)xx≤11<x≤22<x≤33<x≤44<x≤5維修費用(萬元／年)5681118第1年年初購進一臺新設備，需支付11萬元，一直使用到第3年底，需維修費5+6+8=19萬元，故該弧的權為30。第i年12345價格（萬元）1112131213使用年數(shù)xx≤11<x≤22<x≤33<x≤44<x≤5維修費用（萬元／年）5681118用Dijkstra算法求解，最短路線為(v1,v4,v6)，總費用為53萬元。這樣就可得到一個賦權有向網(wǎng)絡。所求問題等價于尋找從v1到v6的最短路問題。Lingo求解VariableValueF(1)53.00000F(2)42.00000F(3)32.00000F(4)23.00000F(5)18.00000F(6)0.000000

P(1,4)1.000000P(2,6)1.000000P(3,6)1.000000

P(4,6)1.000000P(5,6)1.000000

例9（無向圖的最短路問題）求圖5中到的最短路.

分析：不論是例7、例8均屬于有向圖的最短路問題，本例是處理無向圖的最短路問題，在處理方式上與有向圖的最短路有一些差別.

解：對于無向圖的最短路問題，可以這樣理解，從點到點和點到點的邊看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路問題來編程序，但按照這種方法編寫LINGO程序相當邊（?。┰黾恿艘槐?這里選擇鄰接矩陣和賦權矩陣的方法編寫LINGO程序.寫出相應的LINGO程序，程序名：exam0809.lg4MODEL:1]sets:2]cities/1..11/;3]roads(cities,cities):p,w,x;4]endsets5]data:6]p=011100000007]001010000008]010111100009]0010001000010]0110010110011]0010101010012]0011010011013]0000100010114]0000111101115]0000001010116]00000000000;17]w=0281000000018]2060100000019]8607512000020]1070009000021]0150030290022]0010304060023]0029040031024]0000200070925]0000963701226]0000001010427]00000009240;28]enddata29]n=@size(cities);30]min=@sum(roads:w*x);31]@for(cities(i)|i#ne#1#and#i#ne#n:32]@sum(cities(j):p(i,j)*x(i,j))33]=@sum(cities(j):p(j,i)*x(j,i)));

34]@sum(cities(j):p(1,j)*x(1,j))=1;END

在上述程序中，第6]行到第16]行給出了圖的鄰接矩陣，到和到的邊按單向計算，其余邊雙向計算.第17]行到第27]行給出了圖的賦權矩陣,注意：由于有了鄰接矩陣，兩點無道路連接時，權值可以定義為0.其它的處理方法基本上與有向圖相同.用LINGO軟件求解，得到（僅保留非零變量）

Globaloptimalsolutionfoundatiteration:20Objectivevalue:13.00000

VariableValueReducedCostX(1,2)1.0000000.000000X(2,5)1.0000000.000000X(3,7)1.0000000.000000X(5,6)1.0000000.000000X(6,3)1.0000000.000000X(7,10)1.0000000.000000X(9,11)1.0000000.000000X(10,9)1.0000000.000000

即最短路徑為,最短路長度.為13§

2.2最大流問題

例11（最大流問題）現(xiàn)需要將城市s的石油通過管道運送到城市t，中間有4個中轉站和,城市與中轉站的連接以及管道的容量如圖6所示，求從城市s到城市t的最大流.返回導航

圖6給出的有一個源和一個匯的網(wǎng)絡.

網(wǎng)絡中每一條邊有一個容量,除此之外,

對邊還有一個通過邊的流(Flow),記為.

顯然,邊上的流量不會超過該邊上的容量

,即稱滿足不等式（17）的網(wǎng)絡是相容的.

對于所有中間頂點,流入的總量應等于流出的總量,即:

一個網(wǎng)絡

的流量(Valueofflow)值定義為從源流出的總流量,即

由式(18)和(19)式可以看出,的流量值也為流入?yún)R的總流量,即:

稱滿足式(21)的網(wǎng)絡為守恒的.

定義6如果流滿足不等式(17)和式(21),則稱流是可行的.如果存在可行流,使得對所有的可行流均有則稱為最大流(MaximumFlow).

2.最大流問題的數(shù)學規(guī)劃表示形式通過上述推導得到最大流的數(shù)學規(guī)劃表達式3.最大流問題的求解方法

下面用例子說明，如何用LINGO軟件求解最大流問題.

例12

（繼例7.11）用LINGO軟件求解例11.

解：寫出相應的LINGO程序，程序名:0812.lg4.MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,f;5]endsetsMODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,f;5]endsets6]data:7]c=8759925610;8]enddata9]max=flow;

程序的第10]到12]行表示約束(23),第13]行表示有界約束(24).LINGO軟件的計算結果（只保留流值）如下:Globaloptimalsolutionfoundatiteration:6Objectivevalue:14.00000VariableValueReducedCostFLOW14.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000

F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000

因此，該網(wǎng)絡的最大流為14，F(xiàn)的值對應弧上的流，如圖7-7所示,其中網(wǎng)絡中的第一個數(shù)為容量，第二個數(shù)為流量.

在上面的程序中，采用稀疏集的編寫方法，下面介紹的程序編寫方法是利用鄰接矩陣，這樣可以不使用稀疏集的編寫方法，更便于推廣到復雜網(wǎng)絡.MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes):p,c,f;4]endsets5]data:6]p=0110007]0011008]0000109]00100110]00010111]000000;

12]c=08700013]00590014]00009015]00200516]000601017]000000;18]enddata19]max=flow;20]@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):21]@sum(nodes(j):p(i,j)*f(i,j))22]=@sum(nodes(j):p(j,i)*f(j,i)));23]@sum(nodes(i):p(1,i)*f(1,i))=flow;24]@for(arcs:@bnd(0,f,c));END在上述程序中，由于使用了鄰接矩陣，當兩點之間無弧時，定義弧容量為零.計算結果與前面程序的結果完全相同，這里就不再列出了.§

2.3最小費用最大流問題

例13（最小費用最大流問題）（續(xù)例11）由于輸油管道的長短不一，或地質等原因，使每條管道上運輸費用也不相同，因此，除考慮輸油管道的最大流外，還需要考慮輸油管道輸送最大流的最小費用，圖8所示是帶有運費的網(wǎng)絡，其中第1個數(shù)字是網(wǎng)絡的容量，第2個數(shù)字是網(wǎng)絡的單位運費.返回導航

例13所提出的問題就是最小費用最大流問題(Minimum-costmaximumflow)，即考慮網(wǎng)絡在最大流情況下的最小費用.例12雖然給出了例11最大流一組方案，但它是不是關于費用的最優(yōu)方案呢？這還需要進一步討論.1.最小費用流的數(shù)學表達式

min

s.t.

其中

當為網(wǎng)絡的最大流進，數(shù)學規(guī)劃表示的就是最小費用最大流問題.2.最小費用流的求解過程

例14（繼例13）用LINGO軟件求解例13.

解：按照最小費用流的數(shù)學規(guī)劃寫出相應的LINGO程序，程序名：exam0814.lg4.MODEL:1]sets:2]nodes/s,1,2,3,4,t/:d;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,u,f;5]endsets6]data:7]d=140000-14;

8]c=285231647;

9]u=8759925610;10]enddata11]min=@sum(arcs:c*f);

12]@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):13]@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));14]@sum(arcs(i,j)|i#eq#1:f(i,j))=d(1);15]@for(arcs:@bnd(0,f,u));END

程序的第11]行是目標函數(shù)(25),第12],13],14]行是約束條件(26),第15]行是約束的上下界(27).LINGO軟件的計算結果（僅保留流值)如下:Globaloptimalsolutionfoundatiteration:3Objectivevalue:205.0000VariableValueReducedCostF(S,1)8.000000-1.000000F(S,2)6.0000000.000000F(1,2)1.0000000.000000F(1,3)7.0000000.000000F(2,4)9.0000000.000000F(3,2)2.000000-2.000000F(3,T)5.000000-7.000000F(4,T)9.0000000.000000因此，最大流的最小費用是205單位.而原最大流費用為210單位，原方案并不是最優(yōu)的.3最優(yōu)連線問題與旅行商問題本節(jié)內容導航

本節(jié)概述

3.1最優(yōu)連線問題

3.2旅行商問題

本節(jié)內容概述

最優(yōu)連線問題也是最小生成樹問題(MinimumSpaningTreeProblem)是求網(wǎng)絡中長度最小的生成樹,旅行商問題(TravelingSalesmanProblem)也稱貨郎擔問題，是求最優(yōu)的Hamilton圈(HamiltonianCycle).這兩個問題是圖論或組合優(yōu)化中十分重要的問題，有著各自的解決方法，例如，求解最小生成樹問題常用“破圈法”或“貪心法”.但旅行商問題目前沒有有效的算法求解，屬于NP完全問題.當最小生成樹問題或旅行商問題頂點的個數(shù)較大時，目前比較有效的方法是遺傳算法.

本節(jié)介紹如何用LINGO軟件求解最小生成樹問題和旅行商問題，其基本思想是將所求問題化為0--1整數(shù)規(guī)劃，因此當所求問題的頂點數(shù)較大時，計算速度可能會比較慢.返回導航

例15（最優(yōu)連線問題）我國西部的SV地區(qū)共有1個城市（標記為1）和9個鄉(xiāng)鎮(zhèn)（標記為2--10）組成，該地區(qū)不久將用上天然氣，其中城市1含有井源.現(xiàn)要設計一供氣系統(tǒng)，使得從城市1到每個鄉(xiāng)鎮(zhèn)（2--10）都有一條管道相邊，并且鋪設的管子的量盡可能的少.圖9給出了SV地區(qū)的地理位置圖，表給出了城鎮(zhèn)之間的距離.§3.1最優(yōu)連線問題返回導航例15就是最優(yōu)連線問題，實際上是求連接各城鎮(zhèn)之間的最小生成樹問題.Kruskal在1956年給出求最優(yōu)生成樹的一個算法（稱Kruskal算法），該方法是“避圈法”的推廣.

算法7.1

（Kruskal算法）

(1)選擇邊,使得盡可能小;(2)若已選定邊,則從中選取邊使得①為無圈圖;②是滿足①的盡可能小的權.(3)當(2)不能繼續(xù)執(zhí)行時,停止.

3.最優(yōu)連線問題（最小生成樹）的數(shù)學表達式將最優(yōu)連線問題寫成數(shù)學規(guī)劃的形式還需要一定的技巧.設是兩點與之間的距離，或1（1表示連接，0表示不連接），并假設頂點1是生成樹的根.則數(shù)學表達式為:2.求最優(yōu)生成樹的算法4.最優(yōu)連線問題的求解過程

例16

（繼例15）已知SV地區(qū)各城鎮(zhèn)之間距離（見表），求FSV地區(qū)（見圖9）的最優(yōu)連線.

解：按照數(shù)學規(guī)劃問題寫出相應的LINGO程序，程序名：exam0816.lg4.MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]121693081061515

13]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Theremustbeanarcoutofcity1;23]@sum(cities(i)|i#gt#1:x(1,i))>=1;24]!Forcityi,exceptthebase(city1);25]@for(cities(i)|i#gt#1:26]!Itmustbeentered;27]@sum(cities(j)|j#ne#i:x(j,i))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;29]@for(cities(j)|j#gt#1#and#j#ne#i:30]level(j)>=level(i)+x(i,j)31]-(n-2)*(1-x(i,j))+(n-3)*x(j,i);32]);33]!Thelevelofcityisatleast1butnomoren-1,34]andis1ifitlinkstobase(city1);35]@bnd(1,level(i),999999);36]level(i)<=n-1-(n-2)*x(1,i);37]);38]!Makethex's0/1;39]@for(link:@bin(x));END在上述程序中，利用水平變量(level)來保證所選的邊不構成圈.計算結果如下：Globaloptimalsolutionfoundatiteration:34Objectivevalue:60.00000VariableValueReducedCostX(1,2)1.0000008.000000X(1,3)1.0000005.000000X(3,4)1.0000007.000000X(3,7)1.0000007.000000X(4,5)1.0000003.000000X(5,8)1.0000006.000000X(7,9)1.0000006.000000X(9,6)1.0000008.000000X(9,10)1.00000010.00000連接這10個城鎮(zhèn)的最小距離為60公里，其連接情況如圖10所示.圖10SV地區(qū)的最優(yōu)連線§3.2旅行商問題

例17

（旅行商問題）某公司計劃在SV地區(qū)(見例15）作廣告宣傳，推銷員從城市1出發(fā)，經(jīng)過各個鄉(xiāng)鎮(zhèn)，再回到城市1，為節(jié)約開支，公司希望推銷員走過這10個城鎮(zhèn)的總距離最少.

解：例17屬于旅行商問題，旅行商問題本質上是求最優(yōu)Hamilton（哈密頓）回路.返回導航旅行商問題的數(shù)學表達式

例18（繼例17）用LINGO軟件求解例17.

解：按照數(shù)學規(guī)劃問題寫出相應的LINGO程序，程序名：exam0818.lg4.

MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;

21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Forcityi;23]@for(cities(i):24]!Itmustbeentered;25]@sum(cities(j)|j#ne#i:x(j,i))=1;26]!I