網(wǎng)絡流模型與方法

網(wǎng)絡流問題與方法圖論與網(wǎng)絡分析（GraphTheoryandNetworkAnalysis）是近幾十年來運籌學領域中發(fā)展迅速，基本網(wǎng)絡概念定義1一個圖包含和有限的稱為節(jié)點（node）的元素，以及連接這些節(jié)點的無序對的集點稱為?。╝rc）。用G（VE）來表示圖，其中V是節(jié)點集，E是弧集。有向圖，每條弧都給定方向。通常，一條弧認為是有序的對（i,j），稱此弧是從節(jié)點i到節(jié)點j的。在圖中通過從節(jié)點i到節(jié)點j的弧使用箭點來指定方向，見圖1。一種通常的表示方法是圖的節(jié)點一弧的關聯(lián)矩陣。通過垂直列出節(jié)點和水平列出弧進行構造。那么在列中弧（i,j）下方，一個+1是在對應的節(jié)點i的位置，而一個-1是在對應于節(jié)點j的位置。圖1的關聯(lián)矩陣表示如下：（1,2）（1,4）（2,3）（2,4）（4,2）（4,3）1(11\2-111-13-1141-1-11—1

一般地，設V={v,…，v}；E={e,…,e}，引進網(wǎng)絡mxn節(jié)點一1m1nij弧關聯(lián)矩陣A（node-arcincidencematrix），其元素a按如下規(guī)則取值：ij1,-1,0,節(jié)點七是弧七的起點;1,-1,0,網(wǎng)絡的流當沿著弧可能存在流，一個流在給定的有向?。╥,j）是一個數(shù)七＞0。流在網(wǎng)絡的弧中必須連接滿足在每個節(jié)點的保存需量。特殊地，除非節(jié)點是發(fā)點和收點（作為下面要討論的），流量在節(jié)點既不能創(chuàng)造也不能流失；進入一個節(jié)點的全部流量必須等于此節(jié)點全部流出的流量。因此在此節(jié)點i中乙E=0

ijkij=1k=1上式第一項的和是從節(jié)點i流出的和，而第二項的和是整個流進i的和。（當然，若從i到j的弧不存在那么X也不存在。）圖2許多實際的網(wǎng)絡流問題均可轉化為這類網(wǎng)絡流規(guī)劃問題，如：圖2運輸問題（transportationproblem）這是最小費用流問題的一個特例。它沒有轉運點，所有節(jié)點分成收點與發(fā)點兩類，各發(fā)點之間沒有弧相連，各收點之間也沒有弧相連，如圖2所示。其網(wǎng)絡圖是偶圖。在運費和供求量給定的條件下考慮某些工廠到某些商店的運輸方案，以使總的運費最小。轉運問題(transshipmentproblem)如果在運輸問題中允許有若干收發(fā)量的平衡的(純)轉運點存在,則稱為轉運問題。分配問題(assignmentproblem)這是運輸問題的一個特例。其中收點與發(fā)點的個數(shù)相同，每個節(jié)點的收量或發(fā)量均為1，而且各弧上的流量只能為0或1。這類問題的實際背景是要把n件活分配給n個工人去做，每人做一件活，而使總的工時(或費用)最少。最短路問題(shortestpathproblem)已知一網(wǎng)絡上各弧的長度，要求出從圖上給定的節(jié)點u到節(jié)點匕的最短的通路。這個問題可以很容易地轉化成最小費用流問題。事實上只要把費用系數(shù)c取為弧e的長度。令b=1，b=-1，其余的b=0，即把單jjsti位貨物從u流到匕，而其余節(jié)點皆為轉運點。各弧上的流量上界〃.可取為1，或者更簡單地取為七二+3，從而取消上界限制。這樣給定各參數(shù)值后求解最小流問題，求出的流程路線必定是最短路。最大流問題(maximumflowproblem)給出一個網(wǎng)絡的每條弧規(guī)定一個流量的上界，再求從節(jié)點u至匕的最大流量，即是最大流問題。最短路問題的算法

伴隨著每個弧(ij是值c.，表示從節(jié)點i至節(jié)點j在此弧的距離。最有效算法解最短路問題只針對c>0，對任意(i，j)WE的情況。問題目的是尋找從節(jié)點1至節(jié)點m在有向圖內的一條最短路。定義0i)是從節(jié)點1至節(jié)點i,i=2,…，m的最短路的長度，并且01)=0。設jj2，…,jm)是(1，2,…，m)的一個變化以使j]=1且0=Q(j)<Q(j)<<Q(j)。

12m構造算法以使在迭代燈1時，"且Q(jm被確定。當j=m時，該程序終止。(1)通常步的討論：設罕外j2,…，j},qw-Sk，且對于所有i^Rk，dJmi」Q(j)+cj,若存在(j,i)GEk")=Ij*8”否則并且(2)d(i*)=mind(i)

ki(1)(2)這算法基于下列定理(證明省略)定理5.1dk(i*)=Q(i*)并且j+1=i*。式(5.1)的dk(i)能逐此計算。特別地，因為Sk=Sk1U{j}dk(i)=min{dk1(i),Q(j「+—}(3)對于所有iERk。下面最短路算法基于(5.3)式。最短路算法第一步：初始化，k=1,Sk={1},Rk={2,…，m},dk(1)=0,dk(滬七若(1,i)EE;dk(i)=8若(1,gE。設P(i)=1，所有#1，這里P(i)是一個指示使用于識別一條最短路的邊，轉第二步。

第二步：設d(i*)=mind(i)。若i*。m，設R=R/{i*}且轉第三步。ki—kk"1k若i*=m,設Q(m)=d(i*)且轉第四步。k第三步：對于所有iWRk+1，設d(i)=min{d(i),d(i*)+c}若d(i)=d(i*)+c記P(i)=i*。設k=k+1，且返回第二步。第四步：追尋最優(yōu)路，設=P(i*)且記(j,i*)作為一條最短路的一條弧。若j=1，終止。若j￥1,轉至第二步。第五步：記i*=j且返回第四步。注意在第二步的最后執(zhí)行中，(P(m),m)是從節(jié)點1到節(jié)點m的最短路的一條弧。由此第四、五步辨認一條最短路的弧。若需要，通過加入某些附加計算的記錄方案，P(i)列舉能刪除。最短路算法計算下圖考慮在圖5.4所顯示的圖，％是伴隨?、?的數(shù)，尋找節(jié)點1與6間的一條最短路?？紤]在圖5.4所顯示的圖，％是伴隨?、?的數(shù)，尋找節(jié)點1步1初始化，R1={2，3，4，5，6}，d1(1)=0,d1(2)=7,d1(3)=9,d1(4)=d1(5)=d1(6)=8,P(i)=1,i=2,???,6。步2i*=2,Q(2)=7,R2={3，4，5，6}。步3d2(3)=8,P(3)=2,d2(4)=14,P(4)=2;d2(i)=d1(i)。否則，步2i*=3,03)=8,烏={4,5,6},步3d3(5)=14,P(5)=3;d3(i)=d2(i)。否則，*步2i*=4,5,g(4)=Q(5)=14,烏={6}。步3d4(6)=20,P(6)=5。步2i*=6,Q(6)=20o步4j=P(6)=5,路(5,6)o步5i*=5o步4j=P(5)=3,路(3,5,6)o步5i*=3o步4j=P(3)=2,路(2,3,5,6),步5i*=2。步4j=P(2)=1,路(1,2,3,5,6)o最短路示長為20的(1,2,3,5,6)o注意在執(zhí)行步2有星號注，對于式(5.2)有替換解。所有的替換解在一次迭代中使用，盡管此算法只尋找一條最短路，然而容易修正尋找從節(jié)點1至節(jié)點m的所有最短路。此例使用LINGO軟件求解，程序編制如下：MODEL:SETS：!Wehaveanetworkof6points.Wewanttofindthelengthoftheshortestroutefrompoint1topoint6.;!Hereisourprimitivesetofsixpoints,whereF(i)representstheshortestpathdistancefromcityitothelastcity;CITIES/1..6/:F;!ThederivedsetROADSliststheroadsthat

existbetweenthepoints;ROADS(CITIES,CITIES)/TOC\o"1-5"\h\z1,32,43,54,65,6/:D;!D(i,j)isthedistancefromcityitoj;ENDSETSDATA:!Herearethedistancesthatcorrespondtotheabovelinks;D=791626;ENDDATAIfyouarealreadyinpoint6,thenthecosttotraveltopoint6is0;F(@SIZE(CITIES))=0;@FOR(CITIES(i)|i#LT#@SIZE(CITIES):F(i)=@MIN(ROADS(i,j)：D(i,j)+F(j)));END在LINGO中使用SOLVE命令，數(shù)值結果如下（相同于前面計算的結果）：Feasiblesolutionfoundatstep:ValueVariableD(D(D(D(D(D(D(D(ValueD(D(D(D(D(D(D(D(D(F(F(F(F(F(F(1,1,2,2,3,3,4,4,5,1)2)3)4)5)6)2)3)3)4)4)5)5)6)6)20.0000013.0000012.000007.0000006.0000000.00000007.0000009.0000001.0000007.0000006.0000006.0000002.0000007.0000006.000000Row12345SlackorSurplus0.00000000.00000000.00000000.00000000.00000000.0000000最短路的應用（最短路問題解決多階段決策問題）對于最優(yōu)化問題中的多階段決策問題，?？捎脛討B(tài)規(guī)劃（見后面一章）來處理。它的特點是先將一個復雜的問題分解成相互聯(lián)系的若干階段，每個階段即為一個小問題，然后逐個處理。一旦每一個階段的決策確定后，整個過程的決策也隨之確定。但動態(tài)規(guī)劃不存在一種標準的數(shù)學形式，可以說動態(tài)規(guī)劃的使用是一種技巧，需要根據(jù)不同的實際問題列出相應的動態(tài)規(guī)劃遞推關系式，再求解遞推關系，而不同的遞推關系式有不同的解法，沒有一個統(tǒng)一的程序。對某些多階段決策問題，要寫出其動態(tài)規(guī)劃遞推關系式難度很大。而最短路問題可以解決多階段決策問題，它可以用現(xiàn)成的最短路算法求解。因此，對某些較復雜的多階段決策問題，可以通過構造適當?shù)膱D，將它轉化成最短路問題，從而使問題變得清晰、百觀。而一旦轉化成功，剩下的就只是用標準的最短路算法程序求解了。要將一個多階段決策問題化為最短路問題，關鍵在于對該問題構造出相應的圖，使圖的頂點、邊、權分別對應于該問題的某些要素，從而圖中某些頂點間的最短路就對應于該問題的解。有時對同一個問題可以構造出不同的圖。下面通過一個實例來說明構造圖的方法。例2（設備更新問題）企業(yè)使用一臺設備，每年年初，企業(yè)領導就要確定是購置新的，還是繼續(xù)使用舊的。若購置新設備，就要支付一定的購置費用；若繼續(xù)使用，這需支付一定的維修費用?，F(xiàn)要制定一個五年之內的設備更新計劃，使得五年內總的支付費用最少。已知該種設備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213使用不同時間設備所需維修費為:使用年限0-11-22-33-44-5維修費5681118此問題也可構造如下圖所示的加權有向圖G(V,E)v5v4^9-10G2(V?E)G(V,E)的含義是：頂點集V=｛；,v,v,v,v,v｝，其中，v表示第i年(i=1，123456i2，……，5)初購置新設備的決策，v6表示第五年底?；〖疎=《,v)i=1,2,3,4,5;i<j<6)，弧(v,v)表示第i年初購ijij進一臺設備一直使用到第j年初的決策，其權W(v,v.)表示由這一決策在第i年初到第j年初的總費用，如W(v「v4)=11+5+6+8=30問題轉化為求v1到v6的最短路問題，求得兩條最短路為v-v-v,v-v-v，權為53，與圖G(V,E)的解相同。146136運輸問題類模型運輸問題模型：設有m個發(fā)點A,,A含有發(fā)量分別為a，…,a；n1m1m個收點B，…,B含有收量分別為b…b，從發(fā)點A到收點B的單位費1m1mii用為C，這些數(shù)據(jù)可匯總于產銷單位的運費表（含C部分），見下表:表、運量、\銷f-r-單位運價、地產地B1B2…Bn產量A1xu、C11x12、e…%..、氣a1Ax21、％1212x22、c22…X2廠C2?a2-212122222n2n-An、、C,氣疽、e渲…x、Ca銷量m1m1bm2m2b…mnmn—bn假設運輸系統(tǒng)是平衡的，即互=￡biji=1j=1這里a和b,i=1,...,m;j=1,...,n都是非負的。事實上，實際應用中，這些數(shù)量也是非負的?，F(xiàn)要求在產銷平衡的條件下，即能滿足發(fā)點和收點中所有的需求的情況下，以使整個運輸費用最小。使用數(shù)學模型術語，設x,i=1,2,...,m;j=1,2,...,n表示從發(fā)點A到收點B.的運量（流量）。附錄于產銷單位的運量表（見上表含x?部分，）：這樣運輸問題的數(shù)學模型為min室exijiji=1j=1（4）s.t.Ex=a,i=（4）j=1Ex=b,j=1,...,ni=1x>0,i=1,...m;j=1,...,n此問題有mn個變量，必須滿足m+n個約束。解釋運輸問題和其對偶問題的經濟意義假定前n個約束等式對應的對偶變量分別是u,u,,u，后m個12nTOC\o"1-5"\h\z約束等式對應的對偶變量分別是V,V，…,V，則其對偶變量向量12mw=（u,u,…,u,V,V，…,V），則對偶的數(shù)學模型為：12n12mmax￡ub+?ajjlljTl=1s.t.u+v.<c,i-1,2,—,m;j-1,2,.?.,n現(xiàn)在給出此對偶模型得實際經濟解釋，設想運輸調度人為使更有效的運輸，設法使制造商在產地買他的產品，在銷地能銷售他運到產品，運輸調度人所訂的產品價格是產品從某產地到某銷地的費用。當然，他必須制訂的價格在制造商中有競爭力。對于運輸調度人來說，必須選擇在產地（發(fā)點）的價格為-V，-V，…，-V，而在銷地（收點）的價格為u,u，…,u，為使有競爭12m12n力，使用的運輸費用模型必須為滿足七+V.<%，對任意的i,j，這是由于u.+V?表示制造商必須在產地賣每產品的單價（在第i產地）并在第j個銷地買此產品單價凈支出，基于此約束，運輸調度人將制定他的價格能有最大收益。由此，該模型正如上述對偶形式。運輸問題實例的計算例3某公司有三個倉庫，庫存原料量分別為：氣一21噸，A2—12噸，A3—27噸。該公司把這些產品分別運往四個工廠。各工廠需量分別為：B—9噸，B—18噸，B—15噸，B4—18噸。已知從各倉庫到各工廠的單位產品運價如表3.2所示。問該公司應如何調運產品，在滿足各工廠的需求量的前提下，使總運費為最少。解：先列出這問題的暢銷平衡和單位運價表。見表3.2：表3.2供需平衡和單位運價表單位：噸使用LINGO軟件解運輸問題使用lingo軟件編制程序基于產大于銷的不平衡模型，即一般地?z￡b.，那么運輸問題的數(shù)學模型為:i=1j=1min室e*.i=1j=1s.t尤x>bj=1,...,mi=1Ex>a,i=1,...,nj=1x>0,i=1,...,n;j=1,...,m.使用LINGO使用LINGO軟件，上述運輸問題的程序編制如下:（倉庫Warehouse，工廠記Customer)model:!A3Warehouse,4CustomerTransportationProblem;SETS:CAPACITY;DEMAND;COST,VOLUME;WAREHOUSE/WH1,CAPACITY;DEMAND;COST,VOLUME;CUSTOMER/C1,C2,C3,C4/ROUTES(WAREHOUSE,CUSTOMER)ENDSETSTheobjective;[OBJ]MIN=@SUM(ROUTES:COST*VOLUME);!Thedemandconstraints;@FOR(CUSTOMER(J):[DEM]@SUM(WAREHOUSE(I):VOLUME(I,J))>=DEMAND(J));!Thesupplyconstraints;@FOR(WAREHOUSE(I):[SUP]@SUM(CUSTOMER(J):VOLUME(I,J))<=CAPACITY(I));!Herearetheparameters;DATA:CAPACITY=21,12,27;DEMAND=9,18,15,18;COST=6,22,6,20,2,18,4,16,14,8,20,10;ENDDATAend現(xiàn)在來研究此程序的執(zhí)行表述.首先集SET柵，在第1行，WAREHOUSE集使用3個元素分別表示3個發(fā)點，每個發(fā)點賦于發(fā)量(CAPACITY),第3行4個元素的CUSTOMER集創(chuàng)建4個收點，同樣賦于需量為DEMAND.第4行，ROUTES集來自于發(fā)點WAREGIYSE和收點CUSTOMER集合。定義集合ROUTES(WAREHOUSE,CUSTOMER)表示ROUTES中每個元素是有序對，從WAREHOUSE之一至CUSTOMER之一，列表表示為：C1C2C3C4WH1WH—C1WH—C2WH—C3WH—C4WH2WH2T1WH2T2WH2T3WH2T4WH3WH3T1WH3T2WH3T3WH3T4有序對伴隨著VOLUME所求的每個發(fā)點至收運量為多少。每個ROUTES并賦已知費用COST。目標函數(shù)在第7行求總費用最小，在第9和第10行，保證約束的每個發(fā)點和需點的量都被滿足。在第15行開始為數(shù)據(jù)DATA取值。選用Generate命令將出現(xiàn):Rows=8Vars=12Negervars=0(allarelinear)Nonzeros=43Constraintnonz=24(24are+-1)Density=0.413Smallestandlargestelementsinabsvalue=1.0000030.0000No.<:3No.=:0No.>:4,Obj=MIN,GUBs<=4Singlecols=0MIN10VOL(WH3,C4)+20VOL(WH3,C3)+8VOL(WH3,C2)+14VOL(WH3,C1)+16VOL(WH2,C4)+4VOL(WH2,C3)+18VOL(WH2,C2)+2VOL(WH2,C1)+20VOL(WH1,C4)+6VOL(WH1,C3)+22VOL(WH1,C2)+6VOL(WH1,C1)SUBJECTTO2]VOL(WH3,C1)+VOL(WH2,C1)+VOL(WH1,C1)>=93]VOL(WH3,C2)+VOL(WH2,C2)+VOL(WH1,C2)>=184]VOL(WH3,C3)+VOL(WH2,C3)+VOL(WH1,C3)>=155]VOL(WH3,C4)+VOL(WH2,C4)+VOL(WH1,C4)>=186]VOL(WH1,C4)+VOL(WH1,C3)+VOL(WH1,C2)+VOL(WH1,C1)<=217]VOL(WH2,C4)+VOL(WH2,C3)+VOL(WH2,C2)+VOL(WH2,C1)<=128]VOL(WH3,C4)+VOL(WH3,C3)+VOL(WH3,C2)+VOL(WH3,C1)<=27END在LINGO軟件中使用SOLVE命令，得數(shù)值結果如下(同表上作業(yè)法一樣)：Rows=8Vars=12Negervars=0(allarelinear)Nonzeros=43Constraintnonz=24(24are+-1)Density=0.413Smallestandlargestelementsinabsvalue=1.0000027.0000No.<:3No.=:0No.>:4,Obj=MIN,GUBs<=4Singlecols=0Optimalsolutionfoundatstep:8Objectivevalue:510.0000VariableValueReducedCostCAPACITY(WH1)21.000000.0000000CAPACITY(WH2)12.000000.0000000CAPACITY(WH3)27.000000.0000000DEMAND(C1)9.0000000.0000000DEMAND(C2)18.000000.0000000DEMAND(C3)15.000000.0000000DEMAND(C4)18.000000.0000000COST(WH1,C1)6.0000000.0000000COST(WH1,C2)22.000000.0000000

COST(WH1,C3)6.0000000.0000000COST(WH1,C4)20.000000.0000000COST(WH2,C1)2.0000000.0000000COST(WH2,C2)18.000000.0000000COST(WH2,C3)4.0000000.0000000COST(WH2,C4)16.000000.0000000COST(WH3,C1)14.000000.0000000COST(WH3,C2)8.0000000.0000000COST(WH3,C3)20.000000.0000000COST(WH3,C4)10.000000.0000000VOLUME(WH1,C1)0.00000000.0000000VOLUME(WH1,C2)0.00000004.000000VOLUME(WH1,C3)15.000000.0000000VOLUME(WH1,C4)6.0000000.0000000VOLUME(WH2,C1)9.0000000.0000000VOLUME(WH2,C2)0.00000004.000000VOLUME(WH2,C3)0.00000002.000000VOLUME(WH2,C4)3.0000000.0000000VOLUME(WH3,C1)0.000000018.00000VOLUME(WH3,C2)18.000000.0000000VOLUME(WH3,C3)0.000000024.00000VOLUME(WH3,C4)9.0000000.0000000RowSlackorSurplusDualPriceOBJ510.00001.000000DEM(C1)0.0000000-6.000000DEM(C2)0.0000000-18.00000DEM(C3)0.0000000-6.000000DEM(C4)0.0000000-20.00000SUP(WH1)0.00000000.0000000SUP(WH2)0.00000004.000000SUP(WH3)0.000000010.00000例4使用LINGO軟件計算6個發(fā)點8個收點得最小費用運輸問題，產銷單位運費表如下:.單位\銷地-------運費、\產地B1B2B3B4B5B6B7B8產量氣62674259601A249538582552A52197433513A476739271434A.23957265415A5522814352銷量3537223241324338使用LINGO軟件程序編制如下：(發(fā)量Warehouse、收點Vendor)MODEL:!A6Warehouse8VendorTransportationProblem;SETS:WAREHOUSES/WH1WH2WH3WH4WH5WH6/:CAPACITY;VENDORS/V1V2V3V4V5V6V7V8/:DEMAND;LINKS(WAREHOUSES,VENDORS):COST,VOLUME;ENDSETS!Theobjective;MIN=@SUM(LINKS(I,J):COST(I,J)*VOLUME(I,J));!Thedemandconstraints;@FOR(VENDORS(J):@SUM(WAREHOUSES(I):VOLUME(I,J))=DEMAND(J));!Thecapacityconstraints;@FOR(WAREHOUSES(I):@SUM(VENDORS(J):VOLUME(I,J))<=CAPACITY(I));!Hereisthedata;DATA:CAPACITY=605551434152;DEMAND=3537223241324338;COST=626742594953858252197433767392712395726555228143;ENDDATAEND類似于上例，WAREHOUSE集6個元素表示6個發(fā)點，并賦于發(fā)量(CAPACITY),集VEBDORS有8個元素為收量賦于需量(DEMAND),集合ROUTES(,)為6X8個有序對。使用LINGO求解，得結果如下(去掉已知不重要的數(shù)據(jù))為：Rows=15Vars=48Negervars=0(allarelinear)Nonzeros=

158Constraintnonz=96(96are+-1)Density=0.215Smallestandlargestelementsinabsvalue=1.0000060.00000,Obj=MIN,GUBs<=8No.<:Singleco6No.=:8No.ls=0>:Optimalsolutionfoundatstep:16Objectivevalue:664.0000VariableValueReducedCostVOLUME(WH1,V1)0.00000005.000000VOLUME(WH1,V2)19.000000.0000000VOLUME(WH1,V3)0.00000005.000000VOLUME(WH1,V4)0.00000007.000000VOLUME(WH1,V5)41.000000.0000000VOLUME(WH1,V6)0.00000002.000000VOLUME(WH1,V7)0.00000002.000000VOLUME(WH1,V8)0.000000010.00000VOLUME(WH2,V1)0.00000000.0000000VOLUME(WH2,V2)0.00000004.000000VOLUME(WH2,V3)0.00000001.000000VOLUME(WH2,V4)32.000000.0000000VOLUME(WH2,V5)0.00000001.000000VOLUME(WH2,V6)0.00000002.000000VOLUME(WH2,V7)0.00000002.000000VOLUME(WH2,V8)1.0000000.0000000VOLUME(WH3,V1)0.00000004.000000VOLUME(WH3,V2)12.000000.0000000VOLUME(WH3,V3)22.000000.0000000VOLUME(WH3,V4)0.00000009.000000VOLUME(WH3,V5)0.00000003.000000VOLUME(WH3,V6)0.00000004.000000VOLUME(WH3,V7)17.000000.0000000VOLUME(WH3,V8)0.00000004.000000VOLUME(WH4,V1)0.00000004.000000VOLUME(WH4,V2)0.00000002.000000VOLUME(WH4,V3)0.00000004.000000VOLUME(WH4,V4)0.00000001.000000VOLUME(WH4,V5)0.00000003.000000VOLUME(WH4,V6)6.0000000.0000000VOLUME(WH4,V7)0.00000002.000000VOLUME(WH4,V8)37.000000.0000000VOLUME(WH5,V1)35.000000.0000000VOLUME(WH5,V2)6.0000000.0000000VOLUME(WH5,V3)0.00000007.000000

VOLUME(WH5,V4)0.00000004.000000VOLUME(WH5,V5)0.00000002.000000VOLUME(WH5,V6)0.00000001.000000VOLUME(WH5,V7)0.00000002.000000VOLUME(WH5,V8)0.00000005.000000VOLUME(WH6,V1)0.00000003.000000VOLUME(WH6,V2)0.00000002.000000VOLUME(WH6,V3)0.00000000.0000000VOLUME(WH6,V4)0.00000001.000000VOLUME(WH6,V5)0.00000003.000000VOLUME(WH6,V6)26.000000.0000000VOLUME(WH6,V7)26.000000.0000000VOLUME(WH6,V8)0.00000003.000000RowSlackorSurplusDualPrice1664.00001.00000020.0000000-4.00000030.0000000-5.00000040.0000000-4.00000050.0000000-3.00000060.0000000-7.00000070.0000000-3.00000080.0000000-6.00000090.0000000-2.000000100.00000003.0000001122.000000.0000000120.00000003.000000130.00000001.000000140.00000002.000000150.00000002.000000TOC\o"1-5"\h\z計算得最優(yōu)解尤*=19,x*=41,x*=32,x*=12,x*=12,x*=22,x*=17,x*=6,1215242832333746x*=37,x*=35,x*=6,x*=26,x*=26,其他尤*=0;最優(yōu)值為z*=664,迭代16次4851526667ij得到.轉運問題*現(xiàn)討論轉運問題，即運輸網(wǎng)絡中存在轉運點。例5工廠F，G，H要運送某種貨物到倉庫a,P叮，8去，所有供需量及費用系數(shù)見下表所示。

aPY8供量F70110408040G60100309050H50902010030需量20403030但現(xiàn)在所有這些工廠或倉庫又都有可作為轉運點。例如工廠F的貨物也可先運至工廠G，再從那里發(fā)往各倉庫。假定在工廠與倉庫間，沿兩個相反方向的運輸費用是相同的，而工廠及倉庫間的費用為：CFCFGHF02030G20025H30250CaPY8a0502020P5004035Y204001582035150現(xiàn)要在允許轉運的條件下決定費用最小的調運方案。這樣，等價的運輸問題中各點的供應量可見下表的右側與下方所示。所有的費用系數(shù)由前面幾張表獲得。于是可用本節(jié)所介紹的方法算出這個問題的最優(yōu)解，它們便是載入上表內的數(shù)據(jù)（空格皆為零值）。其含義是：先將三各工廠的貨物全部運到倉庫y，然后再從倉庫Y按各倉庫的實際需量轉運出去，這樣的方案費用最小。對一般的轉運問題，可把節(jié)點分成純發(fā)點，純發(fā)點及既可發(fā)又可收的轉運點三類。把純發(fā)點與轉運點皆作為發(fā)點，其發(fā)量為凈供給量加上一個足夠大的正數(shù)M（例如￡七）。并把純收點與轉運點皆作為收點，其收量為凈需求量加上M。再規(guī)定各轉運點到其自身的費用系數(shù)為0。然后就可求解等價的運輸問題，從而得到轉運問題的解。讀者使用LINGO編制程序計算此例。非線性運輸問題模型在某些運輸網(wǎng)絡問題中，運輸費用隨著沿著每條弧的運輸量的變化，如果曾經駕馳，將經歷這種現(xiàn)象。由于路中車輛增加，從時間觀念來說，從A點至B點的費用將增加。在許多情況下，費用并不是線性增加的。這里使用實際問題來說明這種非線性運輸問題模型，設有3個發(fā)點運到4個收點的運輸問題，然而從一個特定的發(fā)點運到一個特定的目的地時間遵循下列公式Time=Rate*Flow/（1-Flow/Limit）其中，Rate（比率）——如果在此過程沒有堵塞，運輸每單位所化的時間。Flow（流）——沿著此弧所產生的數(shù)量Limit（限制）沿著此弧能運的最大量在SETS節(jié)中，類似于運輸問題發(fā)點集合ORIG和收點集合DEST,表示法相同。在第6行集ORIG使用三個元素定義發(fā)點。在第7行，DEST的4個元素被命名，在第8行，建立OXD，“OriginperDestination"在運輸網(wǎng)絡中，已知每條弧中Rate（率）和Limits（限制），并且已知每個發(fā)點的供量和每個收點的需量。這些注意將在DATA節(jié)中找到。使用LINGO軟件，程序編制如下：MODEL:!Trafficcongestiontransportationproblem.Cost/unitincreasestoinfinityastrafficonlinkapproachesitslinkcapacity.TruncatedvariationofanAMPLexample;SETS:ORIG/CHICCINCERIE/:SUPPLY;DEST/HAMAKRCOLDAY/:DEMAND;OXD（ORIG,DEST）:RATE,LIMIT,TRAF;ENDSETSDATA:SUPPLY=12008001400;DEMAND=10001200700500;RATE=3914111427912924141713;LIMIT=:500100010001000500800800800800600600600;ENDDATA[TOTCOST]MIN=@SUM(OXD:RATE*TRAF/(1-TRAF/LIMIT));@FOR(ORIG(I):@SUM(OXD(I,J):TRAF(I,J))=SUPPLY(I));@FOR(DEST(J):@SUM(OXD(I,J):TRAF(I,J))=DEMAND(J));@FOR(OXD:@BND(0,TRAF,LIMIT););END模型程序最優(yōu)化的目標是使產地的供量運到目的地并滿足其需求的總費用最小。變量TRAF為沿著每條弧的運量，在第21?22行是使目標沿著弧的總費用最小化。在模型中有三個約束，第25行表示每個發(fā)點運量滿足等于供量，在第28行，每個收點的運輸量等于需量，在第30行沿著每條弧的運輸量要求滿足零至弧的最大限制(LIMIT)。應用@BND()函數(shù)在軟件中正好表示上、下有界的簡單限制，使它不成為約束而為存儲點。使用LINGO求解，得結果如下(去掉已知不重要的數(shù)據(jù))為：迭代23次得最優(yōu)值為120316.9,最優(yōu)解參見變量TRAF(,)的計算結果.容量生產能力工廠選址和運輸問題模型計劃投資建造m個工廠A,A，…,A，已知m個工廠生產能力12m為a,a，…,a，而投資m個工廠的投資費用為d,d，…,d。其工廠生12m12m成同一產品將運輸?shù)絥個銷售地記為％B2，...,Bn，設勺的需求量為b疽=12：.,n。從A,到B,的運輸費用單價為匕。建立數(shù)學模型來制定如何規(guī)劃投資工廠，使整個投資費用和總運輸費用最少？建立模型：設從A到B的運量為x，則二者之間的運費為cx，iJiJi]i]總的工廠生產能力為a=Ya,，總需求量為b=Ub.。一般地，顯然i=1J=1有a>b，否則都要建所有工廠。設第i個工廠建造與否為七,i=1,2,...,n，則[1,第，個工廠投資建造y=<i[0,否則從上述可以歸納為更為復雜的運輸問題和加上投資費用問題，那么模型為：minzScx+^y

ijijiii=1j=1i=1Azb.,j=1,2，…,ni=1s.t.Ex<ay,i=1,2,.?.,mijiij=1x>0,i=1,2,...,m;j=1,2,...,ny=0or1,i=1,2,…，mis.t.現(xiàn)在來看一個例子，有三個工廠需投資p,p,P。投資費用分別為91，12370，24單位；其生產能力分別為39,35,31；產品運輸至4個銷售點q,C2,C3,C4，需求量分別為15，17，22，12o顯然，a〉b.每個單位產品運輸費用如下表所示:C1C2C3C4P16267P24953P38815使用LINGO軟件編制求解程序如下：MODEL:!CapacitatedPlantLocationProblem;SETS:PLANTS/P1,P2,P3/:FCOST,CAP,OPEN;CUSTOMERS/C1,C2,C3,C4/:DEM;ARCS(PLANTS,CUSTOMERS):COST,VOL;ENDSETSDATA:!Fixedcostofopeningateachorigin;TOC\o"1-5"\h\zFCOST=91,70,24;Capacitiesateachorigin;CAP=39,35,31;Demandsateachdestination;DEM=15,17,22,12;Thecost/unitshipmentmatrix;COST=6,2,6,7,4,9,5,3,8,8,1,5;ENDDATA!Theobjective;[TTL_COST]MIN=@SUM(ARCS:COST*VOL)+@SUM(PLANTS:FCOST*OPEN);!Thedemandconstraints;@FOR(CUSTOMERS(J):[DEMAND]@SUM(PLANTS(I):VOL(I,J))>=DEM(J));!Thesupplyconstraints;@FOR(PLANTS(I):[SUPPLY]@SUM(CUSTOMERS(J):VOL(I,J))<=CAP(I)*OPEN(I));!MakeOPENbinary(0/1);@FOR(PLANTS:@BIN(OPEN));END其第一段如運輸問題建立了集合和運輸弧集合，而集合工廠(PLANTS),加上了投資費用，以及是否開工變量(OPEN)。第二段建立數(shù)據(jù)，第三段求總費用最少，第四段建立滿足銷售點的各個需求約束，第五段建立若開工提供各工廠供應量的約束條件;第六段建立是否開某廠的約束條件，即0-1變量約束。LINGO求解結果如下：多種生產品的中轉運輸點選址模型下面給出具體數(shù)值的多種生產品的中轉運輸點選址模型，有三個工廠P1，P2,P3生產兩種產品A，B。工廠的產品將運輸?shù)綄⑦x址的4個中轉運輸點DC1，DC2，DC3,DC4，每個投資中轉點均有固定投資費用，然后由中轉點將產品運輸?shù)戒N售點C1，C2,C3,C4,C5。設第i種產品從i工廠運到第j個中轉點的每單位運輸費用為c泓，記矩陣為C。第i種產品從第j個中轉點運到第k個銷售點每單位費用為孔，其中第i工廠生產第i種產品能力為七，i=1，2,3；i=1，2，第j個中轉點投資費用f.,j=1，2,3,4,第i種產品在第k個銷售點的需量為匕，k=1，2,3,4,5；i=1，2。設第i種產品在第i個工廠運輸?shù)降趈個中轉點的量為ji=1，…，3；j=1，…，4；i=1，2；第j個中轉站投資為z.，j=1，…，4。z.=1，投資；Zj=0，不投資。設第j個中轉點服務于第k個售點為j廣1，...，4；k=1，…，5。yik為0-1變量，等于1時服務，否則不服務。模型為：目標函數(shù)min￡￡￡cx+￡￡￡gdy+￡fzjijkjklkikijji=1i=1j=1i=1j=1k=1j=1其中第一項為從工廠轉運到中轉點的費用，第二項為從中轉點轉到銷售點的費用，第三項是中轉點投資費用。約束條件分析供量約束:￡x<s,i=1，2,3；i=1，2j=1中轉點平衡分析：￡x=￡dy,i=1，2；j=1，2,i=1k=1需求約束：zy=1,k=1,2,,5j=1j若第個中轉點無服務于第個銷售點約束：y.k<z_,j=1,2,3,4;k=1,2,3,4,5Mf1，第j個中轉點服務于第"銷售點y=〈.0,否則[1，第/個中轉點開z=〈j0,否則下面使用LINGO編制2種產品，3個工廠，4個投資中轉點和5個消費點的投資模型：MODEL:!MULLDC;!MultilevelDClocationmodel,basedonGeoffrion/Graves,Man.Sci.,Jan.,1974;!OriginalLINGOmodelbyKamarynTanner;SETS:!Twoproducts;PRODUCT/A,B/;!Threeplants;PLANT/P1,P2,P3/;!EachDChasanassociatedfixedcost,F,andan"open"indicator,Z.;DISTCTR/DC1,DC2,DC3,DC4/:F,Z;!Fivecustomers;CUSTOMER/C1,C2,C3,C4,C5/;!D=Demandforaproductbyacustomer.;DEMLINK(PRODUCT,CUSTOMER):D;!S=Capacityforaproductataplant.;SUPLINK(PRODUCT,PLANT):S;!EachcustomerisservedbyoneDC,indicatedbyY.;YLINK(DISTCTR,CUSTOMER):Y;!C=Cost/tonofaproductfromaplanttoaDC,X=tonsshipped.;CLINK(PRODUCT,PLANT,DISTCTR):C,X;!G=Cost/tonofaproductfromaDCtoacustomer.;GLINK(PRODUCT,DISTCTR,CUSTOMER):G;ENDSETSDATA:

PlantCapacities;S=80,40,75,20,60,75;!Shippingcosts,planttoDC;C=1,3,3,5,!ProductA;4,4.5,1.5,3.8,2,3.3,2.2,3.2,1,2,2,5,!ProductB;4,4.6,1.3,3.5,1.8,3,2,3.5;!DCfixedcosts;F=100,150,160,139;!Shippingcosts,DCtocustomer;G=5,5,3,2,4,!ProductA;5.1,4.9,3.3,2.5,2.7,3.5,2,1.9,4,4.3,1,1.8,4.9,4.8,2,5,4.9,3.3,2.5,4.1,!ProductB;5,4.8,3,2.2,2.5,3.2,2,1.7,3.5,4,1.5,2,5,5,2.3;!CustomerDemands;D=25,30,50,15,35,25,8,0,30,30;ENDDATAObjectivefunctionminimizescosts.;[OBJ]MIN=SHIPDC+SHIPCUST+FXCOST;SHIPDC=@SUM(CLINK:C*X);SHIPCUST=@SUM(GLINK(I,K,L):G(I,K,L)*D(I,L)*Y(K,L));FXCOST=@SUM(DISTCTR:F*Z);SupplyConstraints;@FOR(PRODUCT(I):@FOR(PLANT(J):@SUM(DISTCTR(K):X(I,J,K))<=S(I,J)));DCbalanceconstraints;@FOR(PRODUCT(I):@FOR(DISTCTR(K):@SUM(PLANT(J):X(I,J,K))=@SUM(CUSTOMER(L):D(I,L)*Y(K,L))))；!Demand;@FOR(CUSTOMER(L):@SUM(DISTCTR(K):Y(K,L))=1);!ForceDCKopenifitservescustomerL;@FOR(CUSTOMER(L):@FOR(DISTCTR(K):Y(K,L)<=Z(K)));!Ybinary;@FOR(DISTCTR(K):@FOR(CUSTOMER(L):@BIN(Y(K,L))));END計算結果如下：分配問題的數(shù)學模型標準分配問題模型設有n個人被分配去做n件事，規(guī)定每個人只做一件工作，每件工作只由一個人去做。已知第/個人去做第j件工作的效率(時間或費用)為%(i=1,2,...,n;j=1,2,...,n)，并假設c?>0。問應如何分配才能使總效率(總時間或總費用最少等)最高？設決策變量[1,若分配第i個人去做第?件工作x=5i〔0,否則；(其中i,j=1,2,...,n)。那么第i個人做第j件工作的效率為cx。從而i=1,...,n;j=1,...,n;的綜合即為總效率。每件工作都有人去做，使用數(shù)學表達式為、=1,(j=1,2，…n);i=1同樣，每個人都有工作做，為"=1,(i=1,2...,n);于是分配問題的數(shù)j=1學模型為：minz=工乙x.；i=1j=1Ex=1,(i=1,2,.?.,n);j=1S.t.<Ex。=1,(j=1,2,...,n);i=1..x=0或1,(i,j=1,2,…，n).類似對運輸問題特點的分析可知，分配問題約束條件系數(shù)矩陣A的秩為2n-1，故它的基可行解中共有2n-1個基變量。但實際上只需要找出n個1即可(即分配n個人去做n件不同的工作)，而其余n-1個基變量取值為0,因此這是一個高度退化的線性規(guī)劃問題。分配問題和匈牙利算法第一步：將原分配問題的效益矩陣(c)進行變換得矩陣(c/)，使各行ijij各列中都出現(xiàn)零元素。其方法是：從效益矩陣(c)得每行元素中減去該行得最小元素；ij再從所得效益矩陣得每列元素中減去該列得最小元素。第二步：進行試分配，求此按以下步驟進行。從零元素最少的行(或列)開始，給這個零元素加“橫杠”，記作0。然后劃去該零元素所在列（或行）得其它零元素，記作4。（2）給只有一個零元素的列（或行）中的零元素加“橫杠”0，然后劃去該零元素所在行（或列）的零元素，記作4。（3）反復進行（1），（2）兩步，直到所有零元素都被“橫杠”劃出或劃去為止。（4）若仍有沒有被“橫杠”劃出或劃去的零元素，且同行（或歹U）的零元素至少有兩個。這時可用不同的方案去試探。從剩有零元素最少的行（或列）開始，比較這行零元素所在列中零元素的數(shù)目，選擇零元素較少的那列的這個零元素加“橫杠”，然后劃去同行同列的其它零元素。如此反復進行，直到所有的零元素都已劃出或劃去。（5）若0元素的數(shù)目m等于矩陣的階數(shù)乃，那么這個分配問題的最優(yōu)解已經得到，令劃“橫杠”處的變量X,.二1，其余變量X.=0，即為所求的最優(yōu)解。否則，若m<n，則轉入下一^步。第三步：尋找覆蓋所有零元素的最少直線，以確定該矩陣中能找到的最多的獨立零元素的個數(shù)。為此按以下步驟進行。（1）對沒有0的行打*號；（2）對已打*號的行中所有含4元素的列打*號；（3）再對打有*號的列中含有0元素的行打*號；（4）重復（2）,（3）,直到得不出新的打*號的行、列為止。（5）對沒有打*號的行劃橫線，有打*號的列劃縱線，這就得到覆蓋所有零元素的最少直線數(shù)。令這百線數(shù)為/。若1<n，說明必須再變換當前的矩陣，才能找到n個獨立零元素，則轉第四步；若1=n，而m<n，則返回第三步（4），另彳丁試探。第四步：調整（c/），使之增加一些零元素。為此按如下步驟進行。ij（1）在沒有被直線段覆蓋的元素中，找出最小元素0;（2）在沒有被直線段覆蓋的元素中，減去這個最小元素0；（3）在被兩條直線段覆蓋（橫線和縱線交叉處）的元素加上這個最小元素0;（4）被一條直線覆蓋（橫線和縱線）的元素不變。得新的縮減矩陣（C2），再返回第二步。ij例4設有五項工作A，B，C，D，E，需分配甲、乙、丙、丁、戊五個人去完成。每個人只能完成一件工作，每件工作只能由一個人去完成。五個人分別完成各項工作所需得費用如表4.1所示。問如何分配工作才能使費用最?。縇INGO軟件計算實例model:!A5Worker,5JobAssigmentProblem;SETS:WORKER/W1,W2,W3,W4,W5/:CAPACITY;JOB/J1,J2,J3,J4,J5/:DEMAND;ROUTES(WORKERJOB):COST,VOLUME;ENDSETS!Theobjective;[OBJ]MIN=@SUM(ROUTES:COST*VOLUME);!Thedemandconstraints;@FOR(JOB(J):[DEM]@SUM(WORKER(I):VOLUME(I,J))=DEMAND(J));!Thesupplyconstraints;@FOR(WORKER(I):[SUP]@SUM(JOB(J):VOLUME(I,J))=CAPACITY(I));!Herearetheparameters;DATA:CAPACITY=1,1,1,1,1;DEMAND=1,1,1,1,1;COST=8,6,10,9,12,9,12,7,11,9,7,4,3,5,8,9,5,8,11,8,4,6,7,5,11;ENDDATAend程序各行執(zhí)行的含義分析見運輸問題，而與運輸問題比較改變的是發(fā)量和需量，其分配問題的發(fā)量和需量都為1。例6設有七項工作A、B、C、D、E、F、G需分配a、b、c、d、e、f、g七個人去完成。每個人只能完成一件工作，每件工作只能由

一個人去完成。七個人分別完成各項工作所需得費用如表4.2所示。問如何分配工作才能使費用最省？MODEL:!A7Workers,7JobsAssigmentProblem;SETS:WORKERS/W1W2W3W4W5W6W7/:CAPACITY;JOBS/J1J2J3J4J5J6J7/:DEMAND;LINKS(WORKERS,JOBS):COST,VOLUME;ENDSETS!Theobjective;MIN=@SUM(LINKS(I,J):COST(I,J)*VOLUME(I,J));!Thedemandconstraints;@FOR(JOBS(J):@SUM(WORKERS(I):VOLUME(I,J))=DEMAND(J));!Thecapacityconstraints;@FOR(WORKERS(I):@SUM(JOBS(J):VOLUME(I,J))<=CAPACITY(I));!Hereisthedata;DATA:CAPACITY=1111111;DEMAND=1111111;COST=6267425495385852197437673927239572655228114923124510;ENDDATAEND使用SOLVE命令，得到數(shù)值計算結果如下：匹配問題匹配問題模型：有N件物體，設法以最小的費用來匹配成對。例如，假設班級同學分配宿舍，每個宿舍兩人，對于對（I,J）和（j,i）是難以分辨的，即等同的，所以我們只需要以1<J的配對，換句話表示，我們并不需要通常多余i和j有序對，而只需要那些I<j的對（I,J），下面描述匹配問題的LINGO軟件程序設計。MODEL:SETS：ANALYSTS/1..8/;PAIRS(ANALYSTS,ANALYSTS)RATING,MATCH;ENDSETS|&2#GT#&1:DATA:RATING=9342156173521442921552876234;ENDDATAMIN=@SUM(PAIRS(I,J):RATING(I,J)*MATCH(I,J));@FOR(ANALYSTS(I):@SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K))=1);@FOR(PAIRS(I,J)：@BIN(MATCH(I,J)));END第4行定義8個所要匹配的事件。第6行PAIR(OBJ,OBJ)I&1#LT#2:C;X；表示對LT兩類元素都來自于原始集合OBJ。這里建立對集中元素對(OBJ,OBJ)必須滿足&1小于(#LT#)&2。解LINGO軟件，解x(I,J)只有存在I<(<=)J形式而序對(J,I)與(I,J)相同。使用SOLVE命令，得到數(shù)值計算結果如下：(求得最優(yōu)解x*=x*=x*=x*=1，其余尤*=0。目標函數(shù)最優(yōu)值：16273845ijz*=6。二次分配問題模型本節(jié)中補充使用LINGO軟件中二次分配問題模型和求解，現(xiàn)從例子作簡單解釋。給定飛機間轉機認輸和登機門間的距離，二次分配問題將解出如何安排飛機至登機門總的轉換飛機人的總距離最??？具體問題為，有三架飛機和四個登機口，此模型求解三架飛機和4個登機們，N表示飛機間轉換人數(shù)，T為登機門間距離，分別使用集合FLIGHT和集合GATE賦值，登機口間的距離矩陣為T，而飛機間轉機人數(shù)矩陣為N，K程序分別使用GXG（?，?）和FXF（?，?）來賦值，這里r051014:50r051014:50510T=10406[151050Jr0305'N=200000400?MODEL:Aquadraticassignmentproblem:Giventransfersbetweenflightsanddistancebetweengates,assignflightstogatestominimizetotaltransferdistance;SETS:FLIGHT/1..3/;!Therearethreeflights;GATE/1..4/;!Therearefivegates;FXG(FLIGHT,GATE):X;!Flight-gateassignment;GXG(GATE,GATE):T;!Distancebetweengates;FXF(FLIGHT,FLIGHT):N;!Transfersbtwnflights;ENDSETSDATA:N=030500;!No.transfersbetweenflights;2030040T=051014!distancebetweengates;5051010406151050;ENDDATASETS:!Transferbetween2flightsmustberequiredandrelatedto2differentgates.Warning:thissetgetsbigfast.;TGTG(FLIGHT,GATE,FLIGHT,GATE)|&1#LT#&3#AND#((N(&1,&3)#NE#(T(&2,&4)#NE#0)#OR#(N(&3,#AND#(T(&4,&2)#NE#0)):Y;ENDSETS0)&1)#AND##NE#0)!Eachflight,B,mustbeassignedtoagate;@FOR(FLIGHT(B):@SUM(GATE(J):X(B,J))=1);!Eachgate,J,canreceiveatmostoneflight;@FOR(GATE(J):@SUM(FLIGHT(B):X(B,J))<=1);!ForceY(B,J,C,K)=1ifBassignedtoJandCassignedtoK;!AssumestheTandNmatricesarenonnegative;@FOR(TGTG(B,J,C,K):Y(B,J,C,K)>=X(B,J)+X(C,K)-1);!Minthesumoftransfers*distance;MIN=@SUM(TGTG(B,J,C,K):Y(B,J,C,K)*(N(B,C)*T(J,K)+N(C,B)*T(K,J)));!MaketheX's0/1(Y'swillnaturallybe0/1);@FOR(FXG:@BIN(X));END求解得X(I,J)為飛機I和登機門j間分配。K=(B,J,C,K)=1表示B分配至J和C分配至K。求得總的轉機人的總距離最短，最優(yōu)值為Objectivevalue.使用SOLVE命令，得到數(shù)值結果如下：迭代150次獲得最優(yōu)值為760單位，最優(yōu)解為尸=1,心=2,心=1,其余112233x*=0;ij而y(1,1,2,2)=1,y(1,1,3,3)=1,y(2,2,3,3)=1,其余y(i,j,c,k)=0;即飛機1分配于第一個登機口，飛機2分配于第2個登機口，飛機3分配于第3個登機口。分配問題的應用多次分組會議的最佳安排方案(本問題由97年美國大學生數(shù)模賽題簡化而得)問題：某公司舉行一個由29個委員參加的會議。會議分七場進行，每場會議又知個小組，每個小組人數(shù)均衡?，F(xiàn)要求給出7場會議的每一場各個組中，有哪些委員參加的安排表。

這個安排方案應盡可能使任二個委員之間有相互交流的機會。最大流問題從一個給定的發(fā)點到一個收點中滿足弧的能力約束，決定最大的可能流。一個初步的問題，它的解是解網(wǎng)絡流問題的方法的基本結構問題，既在有向圖中簡單決定從一節(jié)點到另一節(jié)點的路。定義2一個容量網(wǎng)絡是一個網(wǎng)絡中某些弧分配非負容量，在那些弧中定義最大的允許流量?；。╥j的容量記為u，并且此容量在圖上使用數(shù)七伴隨該弧來指示。max最大流問題考慮一個容量網(wǎng)絡問題，兩個特殊節(jié)點稱為發(fā)點和收點被區(qū)別，分別記為節(jié)點1和m。所有其他節(jié)點假設設有截流，既凈流量進入這些節(jié)點必是零。同時，發(fā)點必有發(fā)量而收點必有進量。發(fā)量f在發(fā)點上將等于收點的入量，并經過所有其他節(jié)點作為轉運過程。一系列滿足這樣條件的弧流稱之為在值f的網(wǎng)絡的一個流。最大流問題是在這樣網(wǎng)絡中，來確定最大流。當表示時，形式為maxfs.t.Ex—Ex-f=0,TOC\o"1-5"\h\zijj1j=1j=1（5）Ex-1Lx=0,i豐1,mijjij=1j=1（5）Ex.-Ex.+f=0,j=1j=10<xVu,i,j=1,2,,m這里對應于弧的那些i,j的對被允許。問題能使用更簡練的使用節(jié)點一弧關聯(lián)矩陣的表示形式。設X是

弧流X,.的向量(以任意方式排列)。設〃是上限約束向量按對應X,.排列，設A是對應的節(jié)點一弧關聯(lián)矩陣。最后，設e是一個向量。維數(shù)等于節(jié)點的數(shù)目，以及在節(jié)點1有一個分量為+1，在節(jié)點m有分量-1，并且其他所有的分量都為零。由此，使用向量與矩陣形式表示最大流問題為(6)maxfs.t.Ax-fe=0該問題的系數(shù)矩陣等于節(jié)點一弧關聯(lián)矩陣加上作為流變量f附加列。最大流算法(Ford-Fulkerson算法)第0步：第1(6)該問題的系數(shù)矩陣等于節(jié)點一弧關聯(lián)矩陣加上作為流變量f附加列。最大流算法(Ford-Fulkerson算法)第0步：第1步：第2步：標節(jié)點1為(-,8)，所有另外節(jié)點都未標號。選取任意標號的節(jié)點/作為檢查。記此節(jié)點有(u,c)。對于所有未標號節(jié)點.以使(,,j)是有X<k這樣的弧，'分配標記(,,c)，這里c=minC,k-x｝。對于所有未標號節(jié)點j以使jj,、,lL,j(j,i)是有x.>0這樣的弧，分配記號(,,c.)，其中c.=minC.,x｝。第3步:反復第2步直至或者節(jié)點m第3步:第4步：(擴展)如果節(jié)點m被標號(i,c)，那么增加f并且在弧(i,m)的流由c。沿著由節(jié)點確定的擴展路繼續(xù)返回執(zhí)行，在此路上每條圖增加流c。返回第1步。此算法的有效是相當明顯的。并可建立此算法的有限性。定理2最大流算法最多有限次迭代收斂。(證明省略)。下面我們來看一個最大流問題的例題。例5求下圖所示網(wǎng)絡的最大流(弧(i,j)旁的數(shù)字為u.)。

10圖5.8解：以零流為初始流，用標號法求可擴鏈（?。╢,j）旁的數(shù)偶為[X,〃.]）。而頂點上數(shù)偶為分配標記（土i,c），±號表示前（后）置點。圖5.9中ww為一可擴鏈，△=10；修改后得到新的可行流（見1246圖5.10），流量f=10。圖5.10找到可擴鏈VVVV，△=6；修改后的可行流見圖5.11，f=16。1356找到可擴鏈VVVV，△=6；修改后得下圖，f=22。1256

(0,(5,4)(0,(5,4)找到可擴鏈vwvw，A=4;修改后得圖5.13。134256(0,此時不再存在可擴鏈，故已經找到最大流x*=16，X*=(0,此時不再存在可擴鏈，故已經找到最大流x*=16，X*=10，13x*=6，24x*34X*=10，x*=6，35x*=10，46x；6=16而最大流量f*=26。使用LINGO軟件，編制最大流問題的程序如下:!MaximumFlowProblem;MODEL:SETS:NODES/1..6/;ARCS(NODES,NODES)/1,21,32,42,53,43,54,65,66,1/:CAP,FLOW;ENDSETSMAX=FLOW(6,1);@FOR(ARCS(I,J):FLOW(I,j)<CAP(I,J));@FOR(NODES(I):@SUM(ARCS(J,I):FLOW(J,I))=@SUM(ARCS(I,J):FLOW(I,J)));DATA:CAP=16,20,10,10,6,6,10,16,1000;ENDDATAEND使用LONGO軟件中得SOLVE命令求解所得結果如下(數(shù)值與例題計算一致)：allarelinear)

2Sre+-1)Density=0.231

1000.00

9Rows=allarelinear)

2Sre+-1)Density=0.231

1000.00

9Nonzeros=373onstraintnonz=27(Smallestandlargestelementsinabsvalue=1.00000No.<:9No.=:6No.>:0,Obj=MAX,GUBs<=Singlecols=0

Optimalsolutionfoundatstep:2Objectivevalue:26.00000VariableValueReducedCostCAP(1,2)16.000000.0000000CAP(1,3)20.000000.0000000CAP(2,4)10.000000.0000000CAP(2,5)10.000000.0000000CAP(3,4)6.0000000.0000000CAP(3,5)6.0000000.0000000CAP(4,6)10.000000.0000000CAP(5,6)16.000000.0000000CAP(6,1)1000.0000.0000000FLOW(1,2)16.000000.0000000FLOW(1,3)10.000000.0000000FLOW(2,4)6.0000000.0000000FLOW(2,5)10.000000.0000000FLOW(3,4)4.0000000.0000000FLOW(3,5)6.0000000.0000000FLOW(4,6)10.000000.0000000FLOW(5,6)16.000000.0000000FLOW(6,1)26.000000.0000000RowSlackorSurplusDualPrice126.000001.00000020.00000000.0000000310.000000.000000044.0000000.000000050.00000000.000000062.0000000.000000070.00000000.000000080.00000001.00000090.00000001.00000010974.00000.0000000110.00000000.0000000120.00000000.0000000130.00000000.0000000140.00000000.0000000150.00000000.0000000160.0000000-1.000000最小費用流問題例1在有些實際問題中，網(wǎng)絡圖不僅應考慮流量，而且應考慮費用。即網(wǎng)絡中的每條邊與兩個數(shù)對應，其中一個數(shù)表示容量;另一個數(shù)表示運送單位流量所需費用等，在這節(jié)考慮基本的最小費用流問題，其為略微廣些的運輸問題。最小費用流問題：考慮某網(wǎng)絡有〃節(jié)點，對應于每個節(jié)點'，存在數(shù)b(b>0)表示在此節(jié)點的供給量。(若b<0，則存在需求量。)假設該網(wǎng)絡是平衡的，即Ub=0。i

i=1伴隨著每個弧(i,j)是值c.，表示流量沿著此弧的單位費用。最小費用流問題是決定流量X>0，在每條弧中以使凈流量流入每個節(jié)點i是b.滿足，并且最小的整個費用。使用數(shù)學模型表示，問題是minZcxijij(i,j)eEs.t.1Lx-1Lx=b,i=1,2,...,n(7)j=1k=1七>0,i,j=1,2,...,n運輸問題是此問題的特殊情況，對應的網(wǎng)絡的弧只是從供點到需點進行，這表示的事實是從一個發(fā)點到一個收點直接運輸?shù)募s束問題。更一般的問題允許任意網(wǎng)絡輪廓，以使流量從一個供點可能在達到它的目的地并經過n個中轉節(jié)點。更通常問題名為轉運問題。最小生成樹模型設T={V,E}是賦權圖G={V,E}的一棵生成樹，稱礦中全部邊上的權數(shù)之和為生成樹T的權，記為w(T)。即w(T)=Zw。［『/T如果生成樹T*的權W(T*)是G的所有生成樹的權中最小者，則稱T*是G的最小生成樹，簡稱為最小樹。即w(T*)=min{w(T)}T(7.2)

式中對G的所有生成樹T取最小。求最小樹通常用以下兩種方法。（1（1）破圈法：在給定連通圖G中，任取一圈，去掉一條最大權邊（如果有兩條或兩條以上的邊都是權最大的邊，則任意去掉其中一條），在余圖中（是圖G的生成子圖）任取一圈，去掉一條最大權邊，重復下去，直到余圖中無圈為止，即可得到圖G的最小樹。（2）避圈法（Kruskal算法）：在連通圖g中，任取權值最小的一條邊（若有兩條或兩條以上權相同且最小，則任取一條），在未選邊中選一條權值最小的邊，要求所選邊與已選邊不構成圈，重復下去，直到不存在與已選邊不構成圈的邊為止。已選邊與頂點構成的圖T就是所求最小樹。最小生成樹（minimalspanningtree,MST）模型概括為：給定網(wǎng)絡中一些點和這些點之間的距離，尋找連接所有這些點的最小總距離。使用最小生成樹程序應用求解下面具體例子。例6已知五個城市Atlan