優(yōu)化建模與LINGO第07章1.ppt

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

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

3、矩陣是一個(gè)階 矩陣,其分量為,定理7.1 如果存在 到 的途徑, 則一定存 在 到 的路. 如果圖 的頂點(diǎn)個(gè)數(shù)為 , 則這 個(gè)路的長(zhǎng)度小于等于 .,2. 最短路問(wèn)題的數(shù)學(xué)表達(dá)式,假設(shè)圖有 個(gè)頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn) 的最短路.設(shè)決策變量為 , 當(dāng) , 說(shuō)明弧 位于頂點(diǎn)1至頂點(diǎn) 的路上；否則. 其數(shù)學(xué)規(guī)劃表達(dá)式為,3. 最短路問(wèn)題的求解過(guò)程,在第三章中（例3.5）我們接觸到了最短路問(wèn)題的求解，當(dāng)時(shí)的求解方法是按照Dijkstra算法設(shè)計(jì)的，下面介紹的方法是按照規(guī)劃問(wèn)題 設(shè)計(jì)的.,例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)是計(jì) 算集cities的個(gè)數(shù)，這里的計(jì)算結(jié)果是 , 這樣編 寫方法目的在于提高程序的通用性.22句表示目標(biāo) 函數(shù)(14), 即求道路的最小權(quán)值.23, 24句表示約束 (15) 中 的情況，即最短路中中間點(diǎn)的約束 條件.25句表示約束中 的情況，即最短路中 起點(diǎn)的約束.,約束(15)中 的情況

7、，也就是最短路中終點(diǎn)的 情況，沒(méi)有列在程序中，因?yàn)榻K點(diǎn)的約束方程與前 個(gè)方程相關(guān).當(dāng)然，如果你將此方程列入到LINGO 程序中，計(jì)算時(shí)也不會(huì)出現(xiàn)任何問(wèn)題，因?yàn)長(zhǎng)INGO,軟件可以自動(dòng)刪除描述線性規(guī)劃可行解中的多 余方程.,LINGO軟件計(jì)算結(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,即最短路是 , 最短路長(zhǎng)為6個(gè)單位.,例7.9 (設(shè)備更新問(wèn)題) 張先生打算購(gòu)買一輛新轎車，轎車的售價(jià)是12萬(wàn)元人民幣.轎車購(gòu)買后，每年的各種保險(xiǎn)費(fèi)養(yǎng)護(hù)費(fèi)等費(fèi)用由表7-5所示.如果在5年之內(nèi)，張先生將轎車售出，并再購(gòu)買新年.5年之內(nèi)的二手車銷售價(jià)由表7-6所示.請(qǐng)你幫助張先生設(shè)計(jì)一種購(gòu)買轎車的方案，使5年內(nèi)用車的總費(fèi)用最少.,表7-5 轎車的維護(hù)費(fèi),表7-6 二手車的售價(jià),分析： 設(shè)備更新問(wèn)題是動(dòng)態(tài)規(guī)劃 的一 類 問(wèn) 題（事實(shí)上，最短路問(wèn)題也是動(dòng)態(tài)規(guī)劃的一類問(wèn) 題）,這里借助于最短路方法解決設(shè)備更新問(wèn)題.,解： 用6個(gè)點(diǎn)（1，2，3，4，5，6）表示各年的

9、開(kāi)始，各點(diǎn)之間的邊從邊表示左端點(diǎn)開(kāi)始年至表示右端點(diǎn)結(jié)束所花的費(fèi)用，這樣構(gòu)成購(gòu)車消費(fèi)的網(wǎng)絡(luò)圖，如圖圖7.4所示.,記 表示第 年開(kāi)始到 年結(jié)束購(gòu)車的總銷費(fèi), 即,由此得到,寫出相應(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軟件的計(jì)算結(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)的值對(duì)應(yīng)弧上的流，如圖7-7所示, 其中網(wǎng)絡(luò)中的第一個(gè)數(shù)為容量，第二個(gè)數(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,在上述程序中，由于使用了鄰接矩陣，當(dāng)兩點(diǎn)之間無(wú)弧時(shí)，定義弧容量為零.計(jì)算結(jié)果與前面程序的結(jié)果完全相同，這里就不再列出了., 7.2.3 最小費(fèi)用最大流問(wèn)題,例7.13（最小費(fèi)用最大流問(wèn)題）（續(xù)例7.11）由于輸油管道的長(zhǎng)短不一，或地質(zhì)等原因，使每條管道上運(yùn)輸費(fèi)用也不相同，因此，除考慮輸油管道的最大流外，還需要考慮輸油管道輸送最大流的最小費(fèi)用，圖7-8所示是帶有運(yùn)費(fèi)的網(wǎng)絡(luò)，其中第1個(gè)數(shù)字是網(wǎng)絡(luò)的容量，第2個(gè)數(shù)字是網(wǎng)絡(luò)的單位運(yùn)費(fèi).,返 回 導(dǎo) 航,例7.13所提出的問(wèn)題就是最小費(fèi)用最大流問(wèn)題(Minimum-cost maximum flow)，即考慮網(wǎng)絡(luò)在最大流情況下的最小費(fèi)用.例7.

16、12雖然給出了例7.11最大流一組方案，但它是不是關(guān)于費(fèi)用的最優(yōu)方案呢？這還需要進(jìn)一步討論.,1. 最小費(fèi)用流的數(shù)學(xué)表達(dá)式,min,s.t.,其中,當(dāng) 為網(wǎng)絡(luò)的最大流進(jìn)，數(shù)學(xué)規(guī)劃 表 示的就是最小費(fèi)用最大流問(wèn)題.,2. 最小費(fèi)用流的求解過(guò)程,例7.14（繼例7.13）用LINGO軟件求解例7.13. 解： 按照最小費(fèi)用流的數(shù)學(xué)規(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行是目標(biāo)函數(shù)(25), 第12, 13, 14行是約 束條件(26), 第15行是約束的上下界(27).,LINGO軟件的計(jì)算結(jié)果（僅保留流值 )如下:,Global optimal solution found at iteration: 3 Objective value: 205.0000 Variable Value