1、7.2 最短路問題和最大流問題,本節(jié)內(nèi)容導(dǎo)航 本節(jié)概述 7.2.1 最短路問題 7.2.2 最大流問題 7.2.3最小費與最大流問題,本節(jié)內(nèi)容概述 最短路問題(Shortest Path Problems)和最大流問題(Maxiumum Flow Problems)是圖論另一類與優(yōu)化有關(guān)的問題，對于這兩在問題，實際上，圖論中已有解決的方法，如最短路問題的求解方法有Dijkstra算法，最大流問題的求解方法有標號算法.這里主要討論的是如何用LINGO軟件來求解最短路和最大流問題，對于LINDO軟件的求解方法，作者可以根據(jù)模型自己設(shè)計相應(yīng)的程序，作為LINDO軟件的訓練和問題的練習.,返 回 導(dǎo)

2、航,7.2.1 最短路問題,例7.7 （最短路問題） 在圖 7-3中，用點表示城市，現(xiàn)有 共7個城市.點與點之間的連線表示城市間有道路相連.連線旁的數(shù)字表示道路的長度.現(xiàn)計劃從城市 到城市 鋪設(shè)一條天然氣管道，請設(shè)計出最小價格管道鋪設(shè)方案.,例7.7的本質(zhì)是求從城市 到城市 的一條最短路.為便于討論，下面給出有關(guān)概念的明確定義.,返 回 導(dǎo) 航,1. 圖的基本概念,定義7.2 (子圖與賦權(quán)圖),定義7.3 (跡和路以及圈),定義7.4（鄰接矩陣和賦權(quán)矩陣）如果 , 則稱 與 鄰接, 具有 個頂點的圖的鄰接矩陣(Adjacency Matrix)是一個 階矩陣 , 其分量為,個頂點的賦權(quán)圖的賦權(quán)

3、矩陣是一個階 矩陣,其分量為,定理7.1 如果存在 到 的途徑, 則一定存 在 到 的路. 如果圖 的頂點個數(shù)為 , 則這 個路的長度小于等于 .,2. 最短路問題的數(shù)學表達式,假設(shè)圖有 個頂點，現(xiàn)需要求從頂點1到頂點 的最短路.設(shè)決策變量為 , 當 , 說明弧 位于頂點1至頂點 的路上；否則. 其數(shù)學規(guī)劃表達式為,3. 最短路問題的求解過程,在第三章中（例3.5）我們接觸到了最短路問題的求解，當時的求解方法是按照Dijkstra算法設(shè)計的，下面介紹的方法是按照規(guī)劃問題 設(shè)計的.,例7.8 (繼例7.7) 求例7.7中，從城市A到城市D的 最短路.,解：寫出相應(yīng)的LINGO程序，程序名: ex

4、am0708.lg4.,MODEL: 1! We have a network of 7 cities. We want to find 2 the length of the shortest route from city 1 to city 7; 3,4sets: 5 ! Here is our primitive set of seven cities; 6 cities/A, B1, B2, C1, C2, C3, D/; 7 8 ! The Derived set roads lists the roads that 9 exist between the cities; 10 r

5、oads(cities, cities)/ 11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/: w, x; 13endsets 14 15data: 16 ! Here are the distances that correspond,17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19enddata 20 21n=size(cities); ! The number of cities; 22min=sum(roads: w*x); 23for(citie

6、s(i) | i #ne# 1 #and# i #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END,在上述程序中， 21句中的n=size(cities)是計 算集cities的個數(shù)，這里的計算結(jié)果是 , 這樣編 寫方法目的在于提高程序的通用性.22句表示目標 函數(shù)(14), 即求道路的最小權(quán)值.23, 24句表示約束 (15) 中 的情況，即最短路中中間點的約束 條件.25句表示約束中 的情況，即最短路中 起點的約束.,約束(15)中 的情況

7、，也就是最短路中終點的 情況，沒有列在程序中，因為終點的約束方程與前 個方程相關(guān).當然，如果你將此方程列入到LINGO 程序中，計算時也不會出現(xiàn)任何問題，因為LINGO,軟件可以自動刪除描述線性規(guī)劃可行解中的多 余方程.,LINGO軟件計算結(jié)果（僅保留非零變量）如下,Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D)

8、 1.000000 0.000000,即最短路是 , 最短路長為6個單位.,例7.9 (設(shè)備更新問題) 張先生打算購買一輛新轎車，轎車的售價是12萬元人民幣.轎車購買后，每年的各種保險費養(yǎng)護費等費用由表7-5所示.如果在5年之內(nèi)，張先生將轎車售出，并再購買新年.5年之內(nèi)的二手車銷售價由表7-6所示.請你幫助張先生設(shè)計一種購買轎車的方案，使5年內(nèi)用車的總費用最少.,表7-5 轎車的維護費,表7-6 二手車的售價,分析： 設(shè)備更新問題是動態(tài)規(guī)劃 的一 類 問 題（事實上，最短路問題也是動態(tài)規(guī)劃的一類問 題）,這里借助于最短路方法解決設(shè)備更新問題.,解： 用6個點（1，2，3，4，5，6）表示各年的

9、開始，各點之間的邊從邊表示左端點開始年至表示右端點結(jié)束所花的費用，這樣構(gòu)成購車消費的網(wǎng)絡(luò)圖，如圖圖7.4所示.,記 表示第 年開始到 年結(jié)束購車的總銷費, 即,由此得到,寫出相應(yīng)的LINGO程序，程序名： exam0709.lg4,MODEL: 1sets: 2 nodes/1.6/; 3 arcs(nodes, nodes)|,11enddata 12n=size(nodes); 13min=sum(arcs:c*x); 14for(nodes(i) | i #ne# 1 #and# i #ne# n: 15 sum(arcs(i,j):x(i,j) = sum(arcs(j,i):x(j,

10、i); 16sum(arcs(i,j)|i #eq# 1 : x(i,j)=1; END,程序中的第3句中 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5endsets,Model: 1 sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5 endsets 6 data: 7 c = 8 7 5 9 9 2 5 6 10; 8 enddata 9 max=flow

11、; 10 for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 11 sum(arcs(i,j):f(i,j) - sum(arcs(j,i):f(j,i)=0); 12 sum(arcs(i,j)|i #eq# 1 : f(i,j) = flow; 13 for(arcs: bnd(0, f, c);,程序的第10到 12行表示約束(23), 第13行表示 有界約束(24).,LINGO軟件的計算結(jié)果（只保留流值 ）如下:,Global optimal solution found at iteration: 6 Objective value:

12、 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.0

13、00000,因此，該網(wǎng)絡(luò)的最大流為14，F(xiàn)的值對應(yīng)弧上的流，如圖7-7所示, 其中網(wǎng)絡(luò)中的第一個數(shù)為容量，第二個數(shù)為流量.,在上面的程序中，采用稀疏集的編寫方法，下面介紹的程序編寫方法是利用鄰接矩陣，這樣可以不使用稀疏集的編寫方法，更便于推廣到復(fù)雜網(wǎng)絡(luò).,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes): p, c, f; 4endsets 5data: 6 p = 0 1 1 0 0 0 7 0 0 1 1 0 0 8 0 0 0 0 1 0 9 0 0 1 0 0 1 10 0 0 0 1 0 1 11 0 0 0 0 0 0

14、;,12 c = 0 8 7 0 0 0 13 0 0 5 9 0 0 14 0 0 0 0 9 0 15 0 0 2 0 0 5 16 0 0 0 6 0 10 17 0 0 0 0 0 0; 18enddata 19max = flow; 20for(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); 23sum(nodes(i):p(1,i)*f(1,i) = flow; 24for(arcs:bnd(0, f, c);

15、 END,在上述程序中，由于使用了鄰接矩陣，當兩點之間無弧時，定義弧容量為零.計算結(jié)果與前面程序的結(jié)果完全相同，這里就不再列出了., 7.2.3 最小費用最大流問題,例7.13（最小費用最大流問題）（續(xù)例7.11）由于輸油管道的長短不一，或地質(zhì)等原因，使每條管道上運輸費用也不相同，因此，除考慮輸油管道的最大流外，還需要考慮輸油管道輸送最大流的最小費用，圖7-8所示是帶有運費的網(wǎng)絡(luò)，其中第1個數(shù)字是網(wǎng)絡(luò)的容量，第2個數(shù)字是網(wǎng)絡(luò)的單位運費.,返 回 導(dǎo) 航,例7.13所提出的問題就是最小費用最大流問題(Minimum-cost maximum flow)，即考慮網(wǎng)絡(luò)在最大流情況下的最小費用.例7.

16、12雖然給出了例7.11最大流一組方案，但它是不是關(guān)于費用的最優(yōu)方案呢？這還需要進一步討論.,1. 最小費用流的數(shù)學表達式,min,s.t.,其中,當 為網(wǎng)絡(luò)的最大流進，數(shù)學規(guī)劃 表 示的就是最小費用最大流問題.,2. 最小費用流的求解過程,例7.14（繼例7.13）用LINGO軟件求解例7.13. 解： 按照最小費用流的數(shù)學規(guī)劃寫出相應(yīng)的LINGO程序，程序名： exam0714.lg4.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/:d; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c,

17、 u, f; 5endsets 6data: 7 d = 14 0 0 0 0 -14;,8 c = 2 8 5 2 3 1 6 4 7; 9 u = 8 7 5 9 9 2 5 6 10; 10enddata 11min=sum(arcs:c*f); 12for(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); 14sum(arcs(i,j)|i #eq# 1 : f(i,j)=d(1); 15for(arcs:bnd(0,f,u); END,程序的第 11行是目標函數(shù)(25), 第12, 13, 14行是約 束條件(26), 第15行是約束的上下界(27).,LINGO軟件的計算結(jié)果（僅保留流值 )如下:,Global optimal solution found at iteration: 3 Objective value: 205.0000 Variable Value