資源描述：
《圖論模型的LINGO算法課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、圖論與網(wǎng)絡(luò)模型最短路問題(ShortestPathProblems)和最大流問題(MaxiumumFlowProblems)是圖論另一類與優(yōu)化有關(guān)的問題，對(duì)于這兩在問題，實(shí)際上，圖論中已有解決的方法，如最短路問題的求解方法有Dijkstra算法，最大流問題的求解方法有標(biāo)號(hào)算法。這里主要討論的是如何用LINGO軟件來求解最短路和最大流問題，對(duì)于LINDO軟件的求解方法，作者可以根據(jù)模型自己設(shè)計(jì)相應(yīng)的程序，作為L(zhǎng)INDO軟件的訓(xùn)練和問題的練習(xí).最短路問題和最大流問題§7.2.1最短路問題例7.7（最短路問題）在圖7-3中，用點(diǎn)表示城市，現(xiàn)有共7個(gè)城市.點(diǎn)與點(diǎn)之間的連線
2、表示城市間有道路相連.連線旁的數(shù)字表示道路的長(zhǎng)度.現(xiàn)計(jì)劃從城市到城市鋪設(shè)一條天然氣管道，請(qǐng)?jiān)O(shè)計(jì)出最小價(jià)格管道鋪設(shè)方案.例7.7的本質(zhì)是求從城市到城市的一條最短路.1.最短路問題的數(shù)學(xué)表達(dá)式假設(shè)有向圖有n個(gè)頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)n的最短路.設(shè)0-1決策變量為xij,當(dāng)xij=1,說明弧(i,j)位于頂點(diǎn)1至頂點(diǎn)j的最短路上；否則xij=0.其數(shù)學(xué)規(guī)劃表達(dá)式為2.最短路問題的求解過程前面我們接觸到了最短路問題的求解，當(dāng)時(shí)的求解方法是按照Dijkstra算法設(shè)計(jì)的，下面介紹的方法是按照規(guī)劃問題(14)-(15)設(shè)計(jì)的.例7.8(繼例7.7)求例7.7中，從城市A到
3、城市D的最短路.解：寫出相應(yīng)的LINGO程序，程序名:exam0708.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(cit
4、ies,cities)/11]A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C312]C1,DC2,DC3,D/:w,x;13]endsets14]15]data:16]!Herearethedistancesthatcorrespond17]!toabovelinks;18]w=24331231134;19]enddata20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(cities(i)
5、i#ne#1#and#i#ne#n:24]@sum(r
6、oads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));25]@sum(roads(i,j)
7、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)中的情況，也就是最短路中終點(diǎn)的情況，沒有列在程序中，因?yàn)榻K點(diǎn)的約束方程與前個(gè)方程相關(guān).
8、當(dāng)然，如果你將此方程列入到LINGO程序中，計(jì)算時(shí)也不會(huì)出現(xiàn)任何問題，因?yàn)長(zhǎng)INGO軟件可以自動(dòng)刪除描述線性規(guī)劃可行解中的多余方程.LINGO軟件計(jì)算結(jié)果（僅保留非零變量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCostX(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路長(zhǎng)為6個(gè)單位.例7.9(設(shè)備更新問題)張先生打算購(gòu)買一輛新轎車，
9、轎車的售價(jià)是12萬元人民幣.轎車購(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)車齡/年01234費(fèi)用/萬元245912表7-6二手車的售價(jià)車齡/年12345售價(jià)/萬元76210分析：設(shè)備更新問題是動(dòng)態(tài)規(guī)劃的一類問題（事實(shí)上，最短路問題也是動(dòng)態(tài)規(guī)劃的一類問題）,這里借助于最短路方法解決設(shè)備更新問題.解：用6個(gè)點(diǎn)（1，2，3，4，5，6）表示各年的開始，各點(diǎn)之間的邊從邊表示左端點(diǎn)開始年至表示右端
10、點(diǎn)結(jié)束所花
