第-7-章-圖論與網(wǎng)絡(luò)模型課件

歡迎各位同學(xué)學(xué)習(xí)第七章內(nèi)容導(dǎo)航

概述7.1運(yùn)輸問題與轉(zhuǎn)運(yùn)問題7.2最短路問題和最大流問題7.3最優(yōu)連線問題與旅行商問題7.4計(jì)劃評審方法和關(guān)鍵路線法

習(xí)題七第7章圖論與網(wǎng)絡(luò)模型歡迎各位同學(xué)學(xué)習(xí)第七章內(nèi)容導(dǎo)航第7章圖論與網(wǎng)絡(luò)模型

本章內(nèi)容概述

本章介紹圖論與網(wǎng)絡(luò)(GraphTheoryandNetwork)的有關(guān)優(yōu)化問題模型。在這里，我們并不打算全面系統(tǒng)介紹圖論與網(wǎng)絡(luò)的知識，而著重介紹與LINDO、LINGO軟件有關(guān)的組合優(yōu)化模型和相應(yīng)的求解過程。如果讀者打算深入地了解圖論與網(wǎng)絡(luò)的更全面的知識，請參閱圖論或運(yùn)籌學(xué)中的有關(guān)書籍.LINDO軟件和LINGO軟件可以求解一些著名的組合優(yōu)化問題，這包括最短路問題、最大流問題、運(yùn)輸和轉(zhuǎn)運(yùn)問題、最優(yōu)匹配和最優(yōu)指派問題、最優(yōu)連線或最小生成樹問題、旅行商問題、關(guān)鍵路線法與計(jì)劃評審方法等。

7.1運(yùn)輸問題與轉(zhuǎn)運(yùn)問題本節(jié)內(nèi)容導(dǎo)航7.1.1運(yùn)輸問題7.1.2指派問題7.1.3轉(zhuǎn)運(yùn)問題7.1運(yùn)輸問題與轉(zhuǎn)運(yùn)問題本節(jié)內(nèi)容導(dǎo)航§7.1.1運(yùn)輸問題

運(yùn)輸問題(TransportationProblem)是圖論與網(wǎng)絡(luò)中的一個重要問題，也是一個典型的線性規(guī)劃問題.例7.1（運(yùn)輸問題）返回導(dǎo)航§7.1.1運(yùn)輸問題返

例7.1就是典型的運(yùn)輸問題，圖7-1給出了個產(chǎn)地，個銷地運(yùn)輸問題的圖形.關(guān)于它的求解方法有兩類，一類是按照圖論的方法求解，另一類是化成線性規(guī)劃問題.這里介紹第二類方法，即用LINDO或LINGO軟件求解運(yùn)輸問題.但為便于后面的敘述，先給出圖論中有關(guān)圖的部分定義.圖7-1:個產(chǎn)地,個銷售地運(yùn)輸問題的圖形例7.1就是典型的運(yùn)輸問題

1.圖的基本定義 從直觀上看,所謂圖是由點(diǎn)和邊組成的圖形,如圖7-1所示.下面我們給出圖的定義. 1.圖的基本定義

注：通常有向圖的邊稱為弧，由弧構(gòu)成的集記為因此，有向圖記為,而無向圖記為.為方便起見，在后面的論述中，有時也用表示有向圖.在無向圖中,每條至多有一條邊的圖稱為簡單圖(SimpleGraph).若每一對不同的頂點(diǎn)都有一條邊相連的簡單圖稱為完全圖(CompleteGraph).若一個圖中的頂點(diǎn)集可以分解為兩個子集和,使得任何一條邊都有一個端點(diǎn)在中,另一個端點(diǎn)在中,這種圖稱為二部圖或偶圖(BipartiteGraph).運(yùn)輸問題所構(gòu)成的圖7-1是偶圖.注：通常有向圖的邊稱為弧，由弧構(gòu)成的集記為2.運(yùn)輸問題的數(shù)學(xué)表達(dá)式第個產(chǎn)地的運(yùn)出量應(yīng)小于或等于該地的生產(chǎn)量，即：第個銷地的運(yùn)入量應(yīng)等于該地的需求量，即：2.運(yùn)輸問題的數(shù)學(xué)表達(dá)式第個產(chǎn)地的運(yùn)出量應(yīng)小于或等于該地因此，運(yùn)輸問題的數(shù)學(xué)表達(dá)式為:稱具有形如式的線性規(guī)劃問題為運(yùn)輸問題.因此，運(yùn)輸問題的數(shù)學(xué)表達(dá)式為:稱具有形如式的線性規(guī)劃問

3.運(yùn)輸問題的求解過程為了便于討論，以一個運(yùn)輸問題實(shí)例的求解過程來介紹如何用LINDO或LINGO軟件求解運(yùn)輸問題模型.

例7.2(繼例7.1)設(shè)

即為有3個產(chǎn)地和4個銷地的運(yùn)輸問題，其產(chǎn)量、銷量及單位運(yùn)費(fèi)如表7-1所示.試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總運(yùn)費(fèi). 3.運(yùn)輸問題的求解過程

解：從前面的分析來看，運(yùn)輸問題屬于線性規(guī)劃問題，因此，不論是LINDO軟件或LINGO軟件都可以對該問題求解.為了便于比較兩種軟件的優(yōu)缺點(diǎn)，以及各自的特點(diǎn)，我們用兩種軟件分別求解該運(yùn)輸問題.首先寫出LINDO軟件的模型（程序），程序名：exam0702.ltx.

!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto解：從前面的分析來看，運(yùn)輸問題屬于線性規(guī)劃問!Thesupplyconstraints2)x11+x12+x13+x14<=303)x21+x22+x23+x24<=254)x31+x32+x33+x34<=21!Thedemandconstraints5)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12end!ThesupplyconstraintsLINDO軟件的計(jì)算結(jié)果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000LINDO軟件的計(jì)算結(jié)果如下：X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6X2412.000000事實(shí)上，我們關(guān)心更多的是那些非零變量，因此,可選擇LINDO中的命令（具體方法見第二章的2.3節(jié)),只列出非零變量.

OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000事實(shí)上，我們關(guān)心更多的是那些非零變量，因此,OBJEC

X131.0000000.000000X2113.0000000.000000X2412.0000000.000000X3321.0000000.000000ROWSLACKORSURPLUSDUALPRICES3)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6X131.000000LINDO軟件雖然給出最優(yōu)解，但上述模型還存在著缺點(diǎn)，例如，上述方法不便于推廣的一般情況，特別是當(dāng)產(chǎn)地和銷地的個數(shù)較多時，情況更為突出.下面寫出求解該問題的LINGO程序，并在程序中用到在第三章介紹的集與數(shù)據(jù)段，以及相關(guān)的循環(huán)函數(shù).寫出相應(yīng)的LINGO程序，程序名：exam0702.lg4MODEL:1]!3Warehouse,4CustomerTransportationProblem;2]sets:3]Warehouse/1..3/:a;4]Customer/1..4/:b;LINDO軟件雖然給出最優(yōu)解，但上述模型還存在

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);5]Routes(Warehouse,Cus

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]表示運(yùn)輸問題中目標(biāo)函數(shù)(7.1).第18]

19]行表示約束條件(7.2),第21]22]行表示約束條件(7.3).17]!Thesupplyconstraints下面列出LINGO軟件的求解結(jié)果（僅保留非零變量）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下面列出LINGO軟件的求解結(jié)果（僅保留非零變量）Gl從上述求解過程來看，兩種軟件的計(jì)算結(jié)果是相同的，但由于LINGO軟件中采用集、數(shù)據(jù)段和循環(huán)函數(shù)的編寫方式，因此更便于程序推廣到一般形式使用.例如，只需修改運(yùn)輸問題中產(chǎn)地和銷地的個數(shù)，以及參數(shù)a,b,c的值，就可以求解任何運(yùn)輸問題.所以，從程序通用性的角度來看,推薦大家采用LINGO軟件來求解運(yùn)輸問題.從上述求解過程來看，兩種軟件的計(jì)算結(jié)果§7.1.2指派問題例7.3（指派問題）設(shè)有n個人,計(jì)劃作n項(xiàng)工作,其中表示第i個人做第j項(xiàng)工作的收益,現(xiàn)求一種指派方式，使得每個人完成一項(xiàng)工作，使總收益最大.例7.3就是指派問題(AssignmentProblem).指派問題也是圖論中的重要問題，有相應(yīng)的求解方法，如匈牙利算法.從問題的形式來看，指派問題是運(yùn)輸問題的特例，也可以看成0-1規(guī)劃問題.返回導(dǎo)航§7.1.2指派問題例7.3（指派問題）設(shè)有1.指派問題的數(shù)學(xué)表達(dá)式設(shè)變量為,當(dāng)?shù)趥€人作第項(xiàng)工作時，,否則.因此，相應(yīng)的線性規(guī)劃問題為

1.指派問題的數(shù)學(xué)表達(dá)式設(shè)2.指派問題的求解過程

分別用LINDO軟件和LINGO軟件求解指派問題，并對兩種軟件的求解方法與各自的優(yōu)缺點(diǎn)進(jìn)行比較.

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

2.指派問題的求解過程例7.4（!Assignmentmodel!Maximizevalveofassignmentsmax20x11+15x12+16x13+5x14+4x15+7x16+17x21+15x22+33x23+12x24+8x25+6x26+9x31+12x32+18x33+16x34+30x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46-99x51+7x52+10x53+21x54+10x55+32x56-99x61-99x62-99x63+6x64+11x65+13x66subjectto

解：與運(yùn)輸問題一樣，先用LINDO軟件求解.給出LINGO程序，程序名exam0704.ltx!Assignmentmodel解!Eachpersonmustbeassignedtosomejobx11+x12+x13+x14+x15+x16=1x21+x22+x23+x24+x25+x26=1x31+x32+x33+x34+x35+x36=1x41+x42+x43+x44+x45+x46=1x51+x52+x53+x54+x55+x56=1x61+x62+x63+x64+x65+x66=1!Eachjobmustreceiveanassignmentx11+x21+x31+x41+x51+x61=1x12+x22+x32+x42+x52+x62=1x13+x23+x33+x43+x53+x63=1x14+x24+x34+x44+x54+x64=1x15+x25+x35+x45+x55+x65=1x16+x26+x36+x46+x56+x66=1end!Eachpersonmustbeassigned在上述程序中，x51,x61,x62,x63前的系數(shù)均為-99,這是因?yàn)槟橙藷o法做某項(xiàng)工作可以某人做該項(xiàng)工作的收益是,在計(jì)算中通常取一個較大的負(fù)數(shù)就可以.上述程序也沒有說明決策變量是0-1型變量,這是因?yàn)閷τ诖祟悊栴}線性規(guī)劃理論已保證了變量的取值只可能是0或1.LINDO軟件給出的計(jì)算結(jié)果如下（只列出非零變量）:在上述程序中，x51,x61,x62,OBJECTIVEFUNCTIONVALUE1)135.0000VARIABLEVALUEREDUCEDCOSTX111.0000000.000000X231.0000000.000000X321.0000000.000000X441.0000000.000000X561.0000000.000000X651.0000000.000000ROWSLACKORSURPLUSDUALPRICESOBJECTIVEFUNCTIONVALUE

2)0.0000003.0000003)0.00000015.0000005)0.000000-4.0000007)0.000000-19.0000008)0.00000017.0000009)0.00000012.00000010)0.00000018.00000011)0.00000031.00000012)0.00000030.00000013)0.00000032.000000NO.ITERATIONS=202)0.000000即第1個人做第1項(xiàng)工作，第2個人做第3項(xiàng)工作,第3個人做第2項(xiàng)工作，第4個人做第4項(xiàng)工作，第5個人做第6項(xiàng)工作，第6個人做第5項(xiàng)工作.總效益值為135.下面用LINGO程序再求解此問題，程序中仍然用到集、數(shù)據(jù)段和循環(huán)函數(shù).

寫出相應(yīng)的LINGO程序，程序名exam0704.lg4.MODEL:1]!AssignmentProblemModel;2]sets:3]Flight/1..6/;4]Assign(Flight,Flight):c,x;即第1個人做第1項(xiàng)工作，第2個人做第3項(xiàng)工作,M

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

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]);END16]!Maximizevalveofassi程序中第12]

13]行中的-99意義與LINDO程序中的意義相同，當(dāng)某人無法做某項(xiàng)工作時，取一個數(shù)值較大的負(fù)值.LINGO軟件計(jì)算結(jié)果如下（只列出非零變量）: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程序中第12]13]行中的-99意義與從上述兩個例子，可以看出LINGO軟件在處理問題方面要大優(yōu)于LINDO軟件，而且便于推廣，只是在編程方面，LINGO程序的編寫稍復(fù)雜一些.在后面的問題求解中，絕大多數(shù)的求解方法是采用LINGO軟件計(jì)算.對于指派問題，也可以考慮人數(shù)不工作數(shù)不相等的情況，和考慮支付最小的情況.第一章的例1.5“混合泳接力隊(duì)員選拔問題”就是屬于這一類情況.

從上述兩個例子，可以看出LINGO軟件在處

例7.5（繼例1.5）用LINGO軟件求解例1.5.

解：在第二章的例2.7給出了該問題的LINDO軟件求解方法，這里給出LINGO軟件的求解方法，讀者可根據(jù)問題的求解過程來考查兩種軟件求解問題的方法，以及每種軟件各自的特點(diǎn).為了便于編寫程序，將5名隊(duì)員的4種泳姿的百米平均成績重新列在表7-3中.

例7.5（繼例1.5）用LINGO軟件求解按第1章所列的規(guī)劃問題（第１章中的式(1.25)式(1.28)）寫出相應(yīng)的LINGO程序，程序名：exam0705.lg4.MODEL:1]!5personsand4jobsAssignmentProblem;2]sets:3]Person/1..5/;4]Job/1..4/;5]Assign(Person,Job):c,x;6]endsets7]!Herearetheparameters;8]data:按第1章所列的規(guī)劃問題（第１章中的式MODEL:

9]c=66.8,75.6,87,58.6,10]57.2,66,66.4,53,11]78,67.8,84.6,59.4,12]70,74.2,69.6,57.2,13]67.4,71,83.8,62.4;14]enddata15]!Theobjective;16][OBJ]min=@sum(Assign:c*x);17]!Thesupplyconstraints;18]@for(Person(i):[SUP]19]@sum(Job(j):x(i,j))<=1);20]!Thedemandconstraints;21]@for(Job(j):[DEM]22]@sum(Person(i):x(i,j))=1);END該程序同樣沒有限制是0－1型變量.9]c=66.8,75.6,87,58下面列出LINGO軟件計(jì)算結(jié)果（僅保留非零變量）:

Globaloptimalsolutionfoundatiteration:9Objectivevalue:253.2000VariableValueReducedCostX(1,4)1.0000000.000000X(2,1)1.0000000.000000X(3,2)1.0000000.000000X(4,3)1.0000000.000000RowSlackorSurplusDualPriceOBJ253.2000-1.000000SUP(5)1.0000000.000000即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,沒有被選拔上.平均成績?yōu)?4ˊ13〞2.下面列出LINGO軟件計(jì)算結(jié)果（僅保留非零變量§7.1.3轉(zhuǎn)運(yùn)問題

所謂轉(zhuǎn)運(yùn)問題(TransshipmentProblem)實(shí)質(zhì)上是運(yùn)輸問題的一種，其區(qū)別就在于不是將工廠生產(chǎn)出的產(chǎn)品直接送的顧客手中，而是要經(jīng)過某些中間環(huán)節(jié)，如倉庫、配送中心等.圖7-2表示的是3水平分配（即有一個中間環(huán)節(jié)）的轉(zhuǎn)運(yùn)問題.

返回導(dǎo)航§7.1.3轉(zhuǎn)運(yùn)問題所謂轉(zhuǎn)運(yùn)問題(Tra1.轉(zhuǎn)運(yùn)問題的數(shù)學(xué)表達(dá)式1.轉(zhuǎn)運(yùn)問題的數(shù)學(xué)表達(dá)式第-7-章--圖論與網(wǎng)絡(luò)模型ppt課件1.轉(zhuǎn)運(yùn)問題的求解方法以一個例子為例，給出求解轉(zhuǎn)運(yùn)問題的兩種求解方法.

例7.6（轉(zhuǎn)運(yùn)問題）設(shè)有兩個工廠A,B,產(chǎn)量分別為9,8個單位.四個顧客1,2,3,4,需求量分別為3,5,4,5.和三個倉庫x,y,z.其中工廠到倉庫、倉庫到顧客的運(yùn)費(fèi)單價分別由表7-4所示.試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總運(yùn)費(fèi).1.轉(zhuǎn)運(yùn)問題的求解方法以一個例子為AB1234x1３5７－－y2１９６７－z－２－６７４表7-4工廠到倉庫、倉庫到顧客的運(yùn)費(fèi)單價說明：其中--表示兩地?zé)o道路通行.

解：寫出相應(yīng)的LINGO程序，程序名：exam0706a.lg4.AB1234x1３5７－－y2１９６７－z－２－６７４表7-MODEL:1]!2plants,3warehousesand4customers2]TransshipmentProblem;3]sets:4]Plant/A,B/:produce;5]Warhouse/x,y,z/;6]Customer/1..4/:require;7]LinkI(Plant,Warhouse):cI,xI;8]LinkII(Warhouse,Customer):cII,xII;9]endsets10]!Herearetheparameters;11]data:12]produce=9,8;MODEL:13]require=3,5,4,5;14]cI=1,2,100,15]3,1,2;16]cII=5,7,100,100,17]9,6,7,100,18]100,8,7,4;19]enddata20]!Theobjective;

21][OBJ]min=@sum(LinkI:cI*xI)+@sum(LinkII:cII*xII);22]!Thesupplyconstraints;23]@for(Plant(i):[SUP]24]@sum(Warhouse(j):xI(i,j))<=produce(i));13]require=3,5,4,5;

25]!Thewarhouseconstraints;26]@for(Warhouse(j):[MID]27]@sum(Plant(i):xI(i,j))=@sum(Customer(k):xII(j,k)));28]!Thedemandconstraints;29]@for(Customer(k):[DEM]30]@sum(Warhouse(j):xII(j,k))=require(k));END在上述程序中，由14]至15]行定義的cI是工廠到倉庫的運(yùn)費(fèi)，由16]至18]行定義的cII是倉庫到顧客的運(yùn)費(fèi).我們的目標(biāo)是求最小運(yùn)費(fèi)，因此當(dāng)兩點(diǎn)無道路時，認(rèn)為是運(yùn)費(fèi)無窮大.為了便于計(jì)算，只要取較大的數(shù)值就可以了，這里的取值為100.25]!Thewarhouseconstrain程序的第21]行表示目標(biāo)函數(shù)（7，9）,第23],24]行表示約束條件(7.10),第26],27]行表示約束條件(11),第29],30]行表示約束條件(7.12).

LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如下:Globaloptimalsolutionfoundatiteration:9Objectivevalue:121.0000VariableValueReducedCostXI(A,X)3.0000000.000000XI(A,Y)6.0000000.000000XI(B,Y)3.0000000.000000程序的第21]行表示目標(biāo)函數(shù)（7，9）,第23],2XI(B,Z)5.0000000.000000XII(X,1)3.0000000.000000XII(Y,2)5.0000000.000000XII(Y,3)4.0000000.000000XII(Z,4)5.0000000.000000即工廠A向倉庫x,y,z分別運(yùn)輸3,6,0個單位，工廠B向倉庫x,y,z分別運(yùn)輸0,3,5個單位，倉庫x向顧客1運(yùn)輸3個單位，倉庫y向顧客2,3分別運(yùn)輸5,4個單位，倉庫z向顧客4運(yùn)輸5個單位.總運(yùn)費(fèi)為121個單位.XI(B,Z)5.0如果將轉(zhuǎn)運(yùn)問題看成運(yùn)輸問題，可以得到另一種程序的編寫方法，程序名：exam0706b.lg4.MODEL:1]!2plants,3warehousesand4customers2]TransshipmentProblem;3]sets:4]Plant/A,B/:produce;5]Warhouse/x,y,z/;6]Customer/1..4/:require;7]Link(Plant,Warhouse,Customer):poss,cost,x;8]endsets9]!Herearetheparameters;如果將轉(zhuǎn)運(yùn)問題看成運(yùn)輸問題，可以得到另一種程

10]data:11]produce=9,8;12]require=3,5,4,5;13]poss=1,1,0,0,14]1,1,1,0,15]0,0,0,0,16]1,1,0,0,17]1,1,1,0,18]0,1,1,1;19]cost=6,8,0,0,20]11,8,9,0,21]0,0,0,0,22]8,10,0,0,10]data:

23]10,7,8,0,24]0,10,9,6;25]enddata26]!Theobjective;27][OBJ]min=@sum(Link:poss*cost*x);28]!Thesupplyconstraints;29]@for(Plant(i):[SUP]30]@sum(Warhouse(j):31]@sum(Customer(k):poss(i,j,k)*x(i,j,k)))<=produce(i));32]!Thedemandconstraints;33]@for(Customer(k):[DEM]34]@sum(Plant(i):35]@sum(Warhouse(j):poss(i,j,k)*x(i,j,k)))=require(k));END23]10,7,8,0,

排列的.由于引入了參數(shù)poss,當(dāng)兩點(diǎn)間無路時，可以定義其長度為0（實(shí)際上可以定義成任何數(shù)，因?yàn)榇藭rposs對應(yīng)的位置為0，因此，0乘任何數(shù)均為0）.程序中采用的其他方法基本上與運(yùn)輸問題是相同的.排列的.由于引入了參數(shù)poss,LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如下Globaloptimalsolutionfoundatiteration:11Objectivevalue:121.0000VariableValueReducedCost

X(A,X,1)3.0000000.000000X(A,Y,2)5.0000000.000000X(A,Y,3)1.0000000.000000X(B,Y,3)3.0000000.000000X(B,Z,4)5.0000000.000000LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如下Gl從上述求解過程可以看出，轉(zhuǎn)運(yùn)問題仍屬于線性規(guī)劃問題，因此也可以用LINDO軟件求解，讀者可將此問題作為LINDO軟件的訓(xùn)練，用LINDO軟件求解例7.6,并與LINGO軟件的結(jié)果相比較.從上述求解過程可以看出，轉(zhuǎn)運(yùn)問題仍屬于線性7.2最短路問題和最大流問題本節(jié)內(nèi)容導(dǎo)航

本節(jié)概述7.2.1最短路問題7.2.2最大流問題7.2.3最小費(fèi)與最大流問題7.2最短路問題和最大流問題本節(jié)內(nèi)容導(dǎo)航

本節(jié)內(nèi)容概述

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

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

到城市

鋪設(shè)一條天然氣管道，請?jiān)O(shè)計(jì)出最小價格管道鋪設(shè)方案.

例7.7的本質(zhì)是求從城市到城市的一條最短路.為便于討論，下面給出有關(guān)概念的明確定義.返回導(dǎo)航§7.2.1最短路問題例7.7（最短路1.圖的基本概念定義7.2(子圖與賦權(quán)圖)

定義7.3(跡和路以及圈)

1.圖的基本概念定義7.2(子圖與賦權(quán)圖)定義定義7.4（鄰接矩陣和賦權(quán)矩陣）如果,則稱與鄰接,具有個頂點(diǎn)的圖的鄰接矩陣(AdjacencyMatrix)是一個階矩陣,其分量為

定義7.4（鄰接矩陣和賦權(quán)矩陣）如果個頂點(diǎn)的賦權(quán)圖的賦權(quán)矩陣是一個階矩陣

其分量為定理7.1如果存在到的途徑,則一定存在到的路.如果圖的頂點(diǎn)個數(shù)為,則這個路的長度小于等于.個頂點(diǎn)的賦權(quán)圖的賦權(quán)矩陣是一個階矩陣其2.最短路問題的數(shù)學(xué)表達(dá)式假設(shè)圖有個頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)的最短路.設(shè)決策變量為,當(dāng),說明弧位于頂點(diǎn)1至頂點(diǎn)的路上；否則.其數(shù)學(xué)規(guī)劃表達(dá)式為2.最短路問題的數(shù)學(xué)表達(dá)式假設(shè)圖有個頂

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

在第三章中（例3.5）我們接觸到了最短路問題的求解，當(dāng)時的求解方法是按照Dijkstra算法設(shè)計(jì)的，下面介紹的方法是按照規(guī)劃問題設(shè)計(jì)的.

例7.8(繼例7.7)求例7.7中，從城市A到城市D的最短路.解：寫出相應(yīng)的LINGO程序，程序名:exam0708.lg4.MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortestroutefromcity1tocity7;3]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]!Herearethedistancesthatcorrespond4]sets:

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;END17]toabovelinks;在上述程序中，21]句中的n=@size(cities)是計(jì)算集cities的個數(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)的約束方程與前個方程相關(guān).當(dāng)然，如果你將此方程列入到LINGO程序中，計(jì)算時也不會出現(xiàn)任何問題，因?yàn)長INGO

在上述程序中，21]句中的n=@size(c軟件可以自動刪除描述線性規(guī)劃可行解中的多余方程.

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

X(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路長為6個單位.軟件可以自動刪除描述線性規(guī)劃可行解中的多

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

表7-5轎車的維護(hù)費(fèi)車齡/年01234費(fèi)用/萬元245912例7.9(設(shè)備更新問題)張先生打算表7-6二手車的售價車齡/年12345售價/萬元76210分析：設(shè)備更新問題是動態(tài)規(guī)劃的一類問題（事實(shí)上，最短路問題也是動態(tài)規(guī)劃的一類問題）,這里借助于最短路方法解決設(shè)備更新問題.解：用6個點(diǎn)（1，2，3，4，5，6）表示各年的開始，各點(diǎn)之間的邊從邊表示左端點(diǎn)開始年至表示右端點(diǎn)結(jié)束所花的費(fèi)用，這樣構(gòu)成購車消費(fèi)的網(wǎng)絡(luò)圖，如圖圖7.4所示.表7-6二手車的售價12345售價/萬元76210記表示第年開始到年結(jié)束購車的總銷費(fèi),即記表示第年開始到由此得到由此得到寫出相應(yīng)的LINGO程序，程序名：exam0709.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;寫出相應(yīng)的LINGO程序，程序名：exam0709.lg411]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;END程序中的第3]句中&1#1t#&2是邏輯運(yùn)算語句，表示所說明的變量只有行小于列的部分，因此所說明的矩陣是上三角陣.11]enddata程序中的第3]句中LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如下

Globaloptimalsolutionfoundatiteration:0Objectivevalue:31.00000VariableValueReducedCostX(1,2)1.0000000.000000X(2,4)1.0000000.000000X(4,6)1.0000000.000000即第1年初購買轎車，第2年初賣掉，再購買新車，到第4年初賣掉，再購買新車使用到第5年末，總費(fèi)用31萬元.LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如下即第1年初當(dāng)然，上述方案不是唯一的，例如還有和,但無論何種方案，總費(fèi)用均是31萬.

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

分析：不論是例7.7、例7.9還是第三章的例3.5處理的問題均屬于有向圖的最短路問題，本例是處理無向圖的最短路問題，在處理方式上與有向圖的最短路有一些差別.當(dāng)然，上述方案不是唯一的，例如還有

解：對于無向圖的最短路問題，可以這樣理解，從點(diǎn)到點(diǎn)和點(diǎn)到點(diǎn)的邊看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路問題來編程序，但按照這種方法編寫LINGO程序相當(dāng)邊（?。┰黾恿艘槐?這里選擇鄰接矩陣和賦權(quán)矩陣的方法編寫LINGO程序.解：對于無向圖的最短路問題，可以這樣寫出相應(yīng)的LINGO程序，程序名：exam0710.lg4MODEL:1]sets:2]cities/1..11/;3]roads(cities,cities):p,w,x;4]endsets5]data:6]p=011100000007]001010000008]010111100009]0010001000010]01100101100寫出相應(yīng)的LINGO程序，程序名：exam0710.lg4M11]0010101010012]0011010011013]0000100010114]0000111101115]0000001010116]00000000000;17]w=0281000000018]2060100000019]8607512000020]1070009000021]0150030290022]0010304060011]001010101023]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;END23]002904003在上述程序中，第6]行到第16]行給出了圖的鄰接矩陣，到和到的邊按單向計(jì)算，其余邊雙向計(jì)算.第17]行到第27]行給出了圖的賦權(quán)矩陣,注意：由于有了鄰接矩陣，兩點(diǎn)無道路連接時，權(quán)值可以定義為0.其它的處理方法基本上與有向圖相同.用LINGO軟件求解，得到（僅保留非零變量）

Globaloptimalsolutionfoundatiteration:20Objectivevalue:13.00000

VariableValueReducedCost在上述程序中，第6]行到第16]行給出了圖的鄰X(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即最短路徑為,最短路長度.為13X(1,2)1.§

7.2.2最大流問題

例7.11（最大流問題）現(xiàn)需要將城市s的石油通過管道運(yùn)送到城市t，中間有4個中轉(zhuǎn)站和,城市與中轉(zhuǎn)站的連接以及管道的容量如圖7-6所示，求從城市s到城市t的最大流.返回導(dǎo)航§7.2.2最大流問題圖7-6給出的有一個源和一個匯的網(wǎng)絡(luò).網(wǎng)絡(luò)中每一條邊有一個容量,除此之外,對邊還有一個通過邊的流(Flow),記為.顯然,邊上的流量不會超過該邊上的容量,即圖7-6給出的有一個源和一個匯的網(wǎng)絡(luò).稱滿足不等式（17）的網(wǎng)絡(luò)是相容的.對于所有中間頂點(diǎn),流入的總量應(yīng)等于流出的總量,即:

一個網(wǎng)絡(luò)的流量(Valueofflow)值定義為從源流出的總流量,即由式(18)和(19)式可以看出,的流量值也為流入?yún)R的總流量,即:稱滿足不等式（17）的網(wǎng)絡(luò)是相容的.

稱滿足式(21)的網(wǎng)絡(luò)為守恒的.稱滿足式(21)的網(wǎng)絡(luò)為守恒的.定義7.6如果流滿足不等式(17)和式(21),則稱流是可行的.如果存在可行流,使得對所有的可行流均有則稱為最大流(MaximumFlow).

2.最大流問題的數(shù)學(xué)規(guī)劃表示形式通過上述推導(dǎo)得到最大流的數(shù)學(xué)規(guī)劃表達(dá)式定義7.6如果流滿足不等式(3.最大流問題的求解方法下面用例子說明，如何用LINGO軟件求解最大流問題.

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

解：寫出相應(yīng)的LINGO程序，程序名:m0712.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]endsets3.最大流問題的求解方法下面用例子說明，如何用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]endsets6]data:7]c=8759925610;8]enddata9]max=flow;程序的第10]到12]行表示約束(23),第13]行表示有界約束(24).MODEL:程序的第10]到12]行表示約LINGO軟件的計(jì)算結(jié)果（只保留流值）如下: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.000000LINGO軟件的計(jì)算結(jié)果（只保留流值）如下:Glo因此，該網(wǎng)絡(luò)的最大流為14，F(xiàn)的值對應(yīng)弧上的流，如圖7-7所示,其中網(wǎng)絡(luò)中