運輸問題課件

運輸問題（TransportationProblem）

在線性規(guī)劃問題中，有一類特殊類型的問題－－運輸問題。這類問題主要研究把某種物資從若干個產(chǎn)地調(diào)運到若干個銷地，每個產(chǎn)地的供應(yīng)量和每個銷地的銷售量及從一個產(chǎn)地到一個銷地的運輸費用已知，要求確定一個總運費最少的方案。第13章運輸問題（TransportationProblem）13.1物資調(diào)配問題（MaterialTransferringProblem）13.1.1運輸問題及數(shù)學(xué)模型（ModelforTransportation）13.1.2用表上作業(yè)法求解運輸問題（SolveTransportationProblembyTable）13.1.3運輸問題的進(jìn)-步討論（FurtherDiscussionaboutTransportationProblem）13.1.4應(yīng)用問題舉例（Parexample）13.2網(wǎng)絡(luò)流問題（NetworkFlowProblem）13.2.1圖的基本概念（ConceptoftheDagram）13.2.2最短路（ShortPath）13.2.3最大流問題（TheMaximumFlowProblem）13.2.4最小費用最大流問題（TheMinimumCostsandMaximumFlowProblem）13.1物資調(diào)配問題

在經(jīng)濟(jì)建設(shè)中，經(jīng)常會碰到大宗物資調(diào)運問題，如煤、鋼鐵，木材、糧食等物，在全國有若干生產(chǎn)基地，根據(jù)已有交通網(wǎng)絡(luò)，應(yīng)如何制訂調(diào)運方案，將這些物資運到各銷售地點，而運費最小，效率最高。在物流系統(tǒng)中，物資的調(diào)撥和配送是物流管理決策的一項主要工作。在市場經(jīng)濟(jì)條件下，對資源實行市場實行優(yōu)化配置，有利于國民經(jīng)濟(jì)持續(xù)發(fā)展。13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

本章研究單一品種物資的運輸調(diào)度問題。其典型情況是：設(shè)某種物品有個產(chǎn)地（或供方）Ai（i=1，2，…，m），各產(chǎn)地的產(chǎn)量分別是ai（i=1，2，…，m），有n個銷地Bj（j=1，2，…，n）,各銷地的銷量分別為bj（j=1，2，…，n）。假定從Ai（i=1，2，…，m）產(chǎn)地向銷地Bj（j=1，2，…，n）運輸單位物品的運價是。問怎樣調(diào)運這些物品才能使總運費最小?1.運輸問題數(shù)學(xué)模型13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

這是由多個產(chǎn)地供應(yīng)多個銷地的單品種物品運輸問題。為直觀起見，可列出該問題的運輸表（見下頁）。表中的變量Xij（i=1，2，…，m；j=1，2，…，n）為由產(chǎn)地Ai運往銷地Bj的物品數(shù)量。cij為Ai到Bj的單位運價。有時，將單位運價單獨列入另一個表中，并稱其為運價表。1.運輸問題數(shù)學(xué)模型13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型1.運輸問題數(shù)學(xué)模型運輸單價cij銷售地Bi供應(yīng)量B1B2…Bnai產(chǎn)地AiA1c11c12…c1na1A2c21c22

…c2na2┆┆┆…┆┆Amcm1cm2

…cmnam銷售量bjb1b2…bn分布變量表A1x11x12…x1nA2x21x22

…x2n┆┆┆…┆Amxm1xm2

…xmn13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型1.運輸問題數(shù)學(xué)模型

如果運輸問題的總產(chǎn)量等于其總銷量，即有則稱該運輸問題為產(chǎn)銷平衡運輸問題；反之，稱產(chǎn)銷不平衡運輸問題。13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型1.運輸問題數(shù)學(xué)模型產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型可表示如下：其中，約束條件右側(cè)常數(shù)ai和bj滿足13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

在上頁模型中，目標(biāo)函數(shù)表示運輸總費用極小化；前m個約束條件的意義是：由某一產(chǎn)地運往各個銷地的物品數(shù)量之相等于該產(chǎn)他的產(chǎn)量；中間n個約束條件指：由各產(chǎn)地運往某一銷他的物品數(shù)量之和等于該銷地的銷量。1.運輸問題數(shù)學(xué)模型13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

該模型屬于線性規(guī)劃問題。單純形法是求解線性規(guī)劃問題十分有效的一般方法。因而可用單純形法求解上述運輸問題。但是，當(dāng)用線性規(guī)劃的單純形法求解運輸問題時，先得在每個約束條件中引入一個人工變量，這樣一來，即使對于m＝3,n＝4這樣簡單的運輸問題，變量數(shù)目也會達(dá)到19個之多(未考慮去掉一個多余約束條件)，因而需要尋求更簡便的解法。1.運輸問題數(shù)學(xué)模型13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型（1）運輸問題有有限最優(yōu)解2.運輸問題數(shù)學(xué)模型的特點對前述運輸問題，若令其變量

其中，，則xij就是前述述運輸問題的一個可行解；另一方面，其目標(biāo)函數(shù)有下界。目標(biāo)函數(shù)值不會趨于-∞。由此可知，運輸問題必存在有限最優(yōu)解。13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型（2）運輸問題約束條件的系數(shù)矩陣2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型即除第i個和第m+j個分量為l外，其它分量全等于0。（2）運輸問題約束條件的系數(shù)矩陣其系數(shù)列向量的結(jié)構(gòu)是：2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

由此可知，運輸問題具有下述特點：（1）約束條件系數(shù)矩陣的元素等于0或1。（2）約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次。對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：所有結(jié)構(gòu)約束條件都是等式約束，各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城市銷售，各煤礦的供應(yīng)量和需求量如下頁表，各城市的需求量其間的距離(或單位運價)cij如表下頁表方格中的數(shù)據(jù)所示，試建立使總運輸量(或總運費)最小的運輸問題數(shù)學(xué)模型。2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型2.運輸問題數(shù)學(xué)模型的特點單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020A2735820A3329440需求量bj30251015808013.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型解：設(shè)Xij為第i煤礦向第j城市的供應(yīng)量，cij表示為第i煤礦向第j城市供應(yīng)煤的單位運價。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是產(chǎn)銷平衡運輸問題。則可寫出其數(shù)學(xué)模型。2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型2.運輸問題數(shù)學(xué)模型的特點13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型

根據(jù)運輸問題的數(shù)學(xué)模型求出的運輸問題的解X=(xij)，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調(diào)運數(shù)量為xij的物品給Bij。前已指出運輸問題是一種線性規(guī)劃問題，可設(shè)想用迭代法進(jìn)行求解，即先找出它的某一個基可行解，再進(jìn)行解的最優(yōu)性檢驗，若它不是最優(yōu)解，就進(jìn)行迭代調(diào)整，以得到一個新的更好的解，繼續(xù)檢驗和調(diào)整改進(jìn)，直至得到最優(yōu)解為止。3.運輸問題的解13.1物資調(diào)配問題13.1.1運輸問題及數(shù)學(xué)模型例1的一個基可行解：3.運輸問題的解單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015

808013.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題

表上作業(yè)法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進(jìn)行。表上作業(yè)法是一種迭代法，迭代步驟為：先按某種規(guī)則找出一個初始解(初始調(diào)運方案)；再對現(xiàn)行解作最優(yōu)性判別；若這個解不是最優(yōu)解，就在運輸表上對它進(jìn)行調(diào)整改進(jìn)，得出一個新解；再判別，再改進(jìn)；直至得到運輸問題的最優(yōu)解為止。如前所述，迭代過程得出的所有解都要求是運輸問題的基可行解。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題步驟：（1）找出初始即可行解，即在產(chǎn)銷平衡表上分配初始調(diào)運方案，保證xij≥0，，并且xij>0的格（又稱實格）必須有m+n-1個；（2）求出各非基變量的檢驗數(shù)σij（空格檢驗數(shù)），σij≥0時停止計算；σij<0時在繼續(xù)調(diào)整調(diào)運方案（換基迭代法）；（3）確定進(jìn)基變量（空格換入變量）和出基變量（實格調(diào)出變量），找出新的基可行解（用空格閉回路法調(diào)整）；（4）重復(fù)第1-3步，直至獲得σij≥0，輸出xij*和minZ=Z*為止。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)

結(jié)合例1詳細(xì)說明表上作業(yè)法的解題步驟:

（1）畫出運輸問題的求解作業(yè)表（見例1），由于，可以轉(zhuǎn)入（2）；（2）找出初始基可行解（又稱分配初始調(diào)運方案）。確定初始調(diào)運方案的方法很多，下面介紹三種常用的方法。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題a.最小元素法容易直觀想到，為了減少運費，應(yīng)優(yōu)先考慮單位運價最小(或運距最短)的供銷業(yè)務(wù)，最大限度地滿足其供銷量。即對所有i和j，找出ci0j0=min(cij)，并將xi0j0=min(ai0,bj0)的物品量由Ai0供應(yīng)給Bj0；若xi0j0=ai0，則產(chǎn)地Ai0的可供物品己用完，以后不再繼續(xù)考慮這個產(chǎn)地，且Bj0的需求量由bj0減少為bj0-ai0。如果xi0j0=bj0

，則銷地bj0的需求已全部得到滿足，以后不再考慮這個銷地，且Ai0的可供量由ai0減少為ai0-bj0。1.給出運輸問題的初始基可行解(初始調(diào)運方案)13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題a.最小元素法然后，在余下的供、銷點的供銷關(guān)系中，繼續(xù)按上述方法安排調(diào)運，直至安排完所有供銷任務(wù)，得到一個完整的調(diào)運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調(diào)運方案)。由于該方法基于優(yōu)先滿足單位運價(或運距)最小的供銷業(yè)務(wù)．故稱為最小元素法。1.給出運輸問題的初始基可行解(初始調(diào)運方案)13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)最小元素法分配的初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015

808013.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)b.西北角法西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務(wù)，而是優(yōu)先滿足運輸表中西北角(即左上角)上空格的供銷需求。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)西北角法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015

808013.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)c.沃格爾法使用最小元素法有時按某一最小單位運價優(yōu)先安排調(diào)運時，可能導(dǎo)致不得不采用運費很高的其它供銷點對，使整個運輸費用增加。對每一個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數(shù)的值很大，不按最小運價組織運輸就會造成很大損失，故應(yīng)盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。沃格爾法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量ai行罰數(shù)B1B2B3B412345供應(yīng)A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罰數(shù)1213④

221③0

32100

44100

5④200

13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題1.給出運輸問題的初始基可行解(初始調(diào)運方案)

對比以上3種方法的初始調(diào)運方案，可看出，伏格爾法優(yōu)于其他方法，也就是說伏格爾法確定的初始解得目標(biāo)函數(shù)距離最優(yōu)解目標(biāo)函數(shù)最近，因而迭代運算數(shù)為最少，效率高。方法西北角法最小元素法伏格爾法目標(biāo)函數(shù)Z30025022013.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗

要判定運輸問題的某個解是否為最優(yōu)解，可仿照一般單純形法，檢驗這個解的各非基變量(對應(yīng)于運輸表中的空格)的檢驗數(shù)，苦有某空格的檢驗數(shù)為負(fù)，說明將變?yōu)榛兞繉⑹惯\輸費用減少，故當(dāng)前這個解不是最優(yōu)解。若所有空格的檢驗數(shù)全非負(fù)，則不管樣變換解均能使運輸費用降低，即目標(biāo)函數(shù)值已無法改進(jìn)，這個解就是最優(yōu)解。a.閉回路法13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗

現(xiàn)結(jié)合例1中用最小元素法給出的初始解，說明檢驗數(shù)的計算方法。其中一條閉回路a.閉回路法檢驗數(shù)表

銷售地供應(yīng)地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知該解不是最優(yōu)解，還有待調(diào)整改正。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗

閉回路可以是一個簡單的矩形，也可以是由水平和豎直邊線組成的其它更為復(fù)雜的封閉多邊形.a.閉回路法13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗

用閉回路法判定一個運輸方案是否為最優(yōu)方案，需要找出所有空格的閉回路，并計算出其檢驗數(shù)。當(dāng)運輸問題的產(chǎn)地和銷地很多時，空格的數(shù)目很大，計算檢驗數(shù)的工作十分繁重，而用對偶變量法(也稱位勢法)就要簡便得多。b.對偶變量法13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗

對于前述產(chǎn)銷平衡運輸問題，若用u1,u2,…,um分別表示前m個約束等式相應(yīng)的對偶變量，用v1,v2,…,vn分別表示后n個等式約束相應(yīng)的對偶變量，即有對偶變量向量：b.對偶變量法13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗這時可將該運輸問題的對偶規(guī)劃寫成：b.對偶變量法13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題線性規(guī)劃問題變量xj的檢驗數(shù)可表示為2.解的最優(yōu)性檢驗b.對偶變量法

由此可寫出運輸問題某變量xij(對應(yīng)于運輸表中的(Ai,Bj)格)的檢驗數(shù)如下：13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗b.對偶變量法

現(xiàn)設(shè)我們已得到了該運輸問題的一個基可行解，其基變量是由于基變量的檢驗數(shù)等于零．故對這組基變量可寫出方程組13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗b.對偶變量法

若某組解滿足對偶規(guī)劃的所有約束條件，即對所有i和j均有即這組對偶變量(位勢)對偶可行，則互補(bǔ)松弛條件Y(A-C)X=0成立，從而這時得到的解分別為原運輸問題及其對偶問題的最優(yōu)解。若解不滿足約束條件，即非基變量的檢驗數(shù)有負(fù)值存在，則上面得到的運輸問題的解不是最優(yōu)解，需要進(jìn)行解的調(diào)整。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題用位勢法對前述給出的運輸問題的解作最優(yōu)性檢驗。2.解的最優(yōu)性檢驗位勢計算結(jié)果ui

viv1=(0)v2=–1v3=–2v4=1供應(yīng)量aiu1=11621020x11=20u2=7735820x23=10x24=10u3=3329440x31=10x32=25x34=5需求量bj30251015

13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題2.解的最優(yōu)性檢驗位勢法或閉回路法計算空格的檢驗數(shù)結(jié)果

viui

v1=(0)v2=–1v3=–2v4=1供應(yīng)量aiu1=11621020x11=20σ12=6σ13=3σ14=8u2=7735820σ21=0σ22=–3*x23=10x24=10u3=3329440x31=10x32=25σ33=8x34=5需求量bj30251015

因σ22=–3<0，故知該解不是最優(yōu)解，還有待調(diào)整改正。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題解改進(jìn)的具體步驟為:(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數(shù)頂點．沿閉回路的順(或逆)時針方向前進(jìn)，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的頂點(格子)，以該格中的變量為換出變量；3.解的改進(jìn)13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題3.解的改進(jìn)(4)以為調(diào)整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減去這一數(shù)值，從而得出一新的運輸方案。該運輸方案的總運費比原運輸方案減少，改變量等于。然后，再對得到的新解進(jìn)行最優(yōu)性檢驗，如不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題對例1中用最小元素法得出的解進(jìn)行改進(jìn)。3.解的改進(jìn)調(diào)整圖

重新調(diào)整調(diào)運方案，現(xiàn)再用位勢法或閉回路法求這個新解各非基變量的檢驗數(shù)，結(jié)果示于下頁表中。由于所有非基變量的檢驗數(shù)全非負(fù)，故這個解為最優(yōu)解。13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題3.解的改進(jìn)

viui

v1=(0)v2=–1v3=–2v4=1供應(yīng)量aiu1=11621020x11=20σ12=6σ13=0σ14=8u2=7735820σ21=2x22=10x23=10σ24=3u3=3329440x31=10x32=15σ33=5x34=15需求量bj30251015

位勢法或閉回路法計算新檢驗數(shù)結(jié)果13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題4.需要說明的幾個問題（1）若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負(fù)，在繼續(xù)進(jìn)行迭代時，取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常δij<0取中最小者對應(yīng)的變量為換入變量;（2）當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重(無窮多)最優(yōu)解;13.1物資調(diào)配問題13.1.2用表上作業(yè)法求解運輸問題（3）當(dāng)運輸問題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運量時需同時劃去運輸表的一行和一列，這時就出現(xiàn)了退化。在運輸問題中，退化解是時常發(fā)生的。為了使表上作業(yè)法的迭化工作進(jìn)行下去，退化時應(yīng)在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格子中的變量是取值為0的基變量，使迭代過程中基可行解的分量恰好為m+n-1個。4.需要說明的幾個問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論

上—節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上在很多運輸問題中，總產(chǎn)量不等于總銷量。這時，為了使用前述表上作業(yè)法求解，就需將產(chǎn)銷不平衡運輸問題化為產(chǎn)銷平衡運輸問題。1.產(chǎn)銷不平衡的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論如果總產(chǎn)量大于總銷量，即這時的數(shù)學(xué)模型是1.產(chǎn)銷不平衡的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論

為借助于產(chǎn)銷平衡時的表上作業(yè)法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產(chǎn)地Ai(i=1,2,…,m)調(diào)運到這個假想銷地的物品數(shù)量xi,n+1(相當(dāng)于松弛變量)，實際上是就地存貯在Ai的物品數(shù)量。就地存貯的物品不經(jīng)運輸，故其單位運價ci,n+1(i=1,2,…,m)。1.產(chǎn)銷不平衡的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論若令假想銷地的銷量為bn+1，且則模型變?yōu)?.產(chǎn)銷不平衡的運輸問題對應(yīng)的運輸表見下頁。13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論1.產(chǎn)銷不平衡的運輸問題

總銷量大于總產(chǎn)量的情形可仿照上述類似處理，即增加一個假想的產(chǎn)地Am+1，它的產(chǎn)量等于

由于這個假想的產(chǎn)地并不存在，求出的由它發(fā)往各個銷地的物品數(shù)量，實際上是各銷地所需物品的欠缺額，顯然有13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論

在以上討論中，假定物品由產(chǎn)地直接運送到銷售目的地，不經(jīng)中間轉(zhuǎn)運。但是，常常會遇到這種情形：需先將物品由產(chǎn)地運到某個中間轉(zhuǎn)運站(可能是另外的產(chǎn)、銷地或中間轉(zhuǎn)運倉庫)，然后再轉(zhuǎn)運到銷售地。有時，經(jīng)轉(zhuǎn)運比直接運到目的地更為經(jīng)濟(jì)。總之，很多情況下，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進(jìn)去。顯然．考慮轉(zhuǎn)運將使運輸問題變得更為復(fù)雜。

2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論2.有轉(zhuǎn)運的運輸問題(a)無轉(zhuǎn)運(b)包含轉(zhuǎn)運13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論

假定m個產(chǎn)地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點相接收物品的地點都有m+n個。這樣一來，我們就得到了一個擴(kuò)大了的運輸問題。2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論為建立其數(shù)學(xué)模型，令：ai：第個i產(chǎn)地的產(chǎn)量(凈供應(yīng)量)；bj：第j個銷他的銷量(凈需要量)；xij：由第i個發(fā)送地運到第j個接收地的物品數(shù)量；cij：由第i個發(fā)送地到第j個接收地的單位運價；ti：第i個地點轉(zhuǎn)運物品的數(shù)量；ci：第i個地點轉(zhuǎn)運單位物品的費用。2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有假定為平衡運輸問題，即有2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論根據(jù)前面對平衡運輸問題的討論，可得該擴(kuò)大了的運輸問題的數(shù)學(xué)模型如下：2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論在上述模型中:(a)指的是：第i個產(chǎn)地發(fā)送到各個地方的物品數(shù)量之和，等于該產(chǎn)地的產(chǎn)量加上經(jīng)它轉(zhuǎn)運的物品數(shù)量；(b)的意義同上，但由于它們原為銷地，不生產(chǎn)物品，故約束條件的右側(cè)常數(shù)僅為該地的轉(zhuǎn)運量；(c)和(d)的意義為由各地運到第j地的物品數(shù)量之和，前者等于其轉(zhuǎn)運量，后者等于凈需要量加上轉(zhuǎn)運量。2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論將上述模型中的各約束等式右側(cè)的或移到等號左側(cè)，然后在各式等號兩端分別加上Q，并今，則可把模型寫成：2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論2.有轉(zhuǎn)運的運輸問題

要特別注意，在此模型中，對所有i=j，cij=-ci。由于目標(biāo)函數(shù)中這一項為常數(shù)，它不影響求最優(yōu)解，在優(yōu)化過程中可不予考慮。該模型的運輸表和運價表見下頁。當(dāng)不考慮轉(zhuǎn)運費時，可令。13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論2.有轉(zhuǎn)運的運輸問題運輸表

接收地供應(yīng)地

供應(yīng)地

銷售地發(fā)送量1…mm+1…m+n供應(yīng)地1x11…x1mx1,m+1…x1,m+nQ+a1……………………mxm.,1…xmmxm,m+1…xm,m+nQ+am銷售地m+1xm+1,1…xm+1,mxm+1,m+1…xm+1,m+nQ……………………m+nxm+n,1xm+1,n+mxm+n,m+1…xm+n,m+nQ接收量Q…QQ+bm+1…Q+bm+n13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論2.有轉(zhuǎn)運的運輸問題運價表

接收地供應(yīng)地

供應(yīng)地

銷售地發(fā)送量1…mm+1…m+n供應(yīng)地1-c1…c1mc1,m+1…c1,m+nQ+a1……………………mcm.,1…-cmcm,m+1…cm,m+nQ+am銷售地m+1cm+1,1…cm+1,mcm+1…cm+1,m+nQ……………………m+ncm+n,1cm+n,mvm+n,m+1…-cm+nQ接收量Q…QQ+bm+1…Q+bm+n13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論

例2：已知A1，A2，A3三個飲料廠生產(chǎn)同一規(guī)格的飲料，用相同價格供應(yīng)B1，B2，B3三個銷售網(wǎng)點銷售。有兩個轉(zhuǎn)運站T1，T2，并且產(chǎn)品運輸可以在各產(chǎn)地，各銷售地及各轉(zhuǎn)運站之間轉(zhuǎn)運。已知各產(chǎn)地、銷地、中轉(zhuǎn)站相互之間每噸貨物的單位運價和產(chǎn)量，見下頁表。2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論2.有轉(zhuǎn)運的運輸問題各產(chǎn)地、銷地、中轉(zhuǎn)站之間的關(guān)系產(chǎn)地轉(zhuǎn)運站銷售地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A1862━410830A2851395910A3654228720轉(zhuǎn)運站T12148463T2━328232銷售地B149242━5B2105863━4B38973254銷售量15351013.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論（1）對擴(kuò)大的運輸問題建立運價表。對于沒有運輸路線的去任意大的正數(shù)M；對自己運輸?shù)倪\價cij=0。（2）所有轉(zhuǎn)運站的轉(zhuǎn)運量等于銷量，即Q=30+20+10=15+35+10=60,取T1，T2的產(chǎn)量與運量均為60t。（3）在原來的產(chǎn)量與銷量的數(shù)值在加上調(diào)運量，三個產(chǎn)地的產(chǎn)量為90t，70t，80t,銷量均為60t；三個銷量為75t,95t,70t,產(chǎn)量均為60t.如下頁表所示。2.有轉(zhuǎn)運的運輸問題13.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論用表上作業(yè)法求解的最優(yōu)方案2.有轉(zhuǎn)運的運輸問題

運量銷售地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060銷售量606060606075957013.1物資調(diào)配問題13.1.3運輸問題的進(jìn)—步討論實際最優(yōu)方案及最優(yōu)運輸路線如圖，最小費用為300。2.有轉(zhuǎn)運的運輸問題A1A2A3B1B2B3T1T2301510201515202051013.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念有八種顏料A、B、C、D、P、R、S、T要放進(jìn)貯藏室保管。出于安全原因，下列各組顏料不能貯在同一室內(nèi)：A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D，問貯存這八種顏料至少需要多少間貯藏室。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念供應(yīng)鏈?zhǔn)侵腹┴浬?、生產(chǎn)企業(yè)、客戶、以及供貨商的供貨商、客戶的客戶、……所組成的一個網(wǎng)絡(luò)。某家電公司生產(chǎn)電腦的工廠有多個，分布在國內(nèi)不同的地區(qū)；公司在國內(nèi)的各個省市都設(shè)有經(jīng)營部，負(fù)責(zé)當(dāng)?shù)劁N售，這時可以表示出電腦在工廠與經(jīng)營部以及經(jīng)營部之間的運輸情況。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念有5名學(xué)生要參加6門課程的考試，大家選修的課程不同，并且考試的門數(shù)也不相同，這種情況也可以用圖來表示。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

在一個圖中．記點的集合為V(要求V是非空集)，邊的集合為E，將這個圖記為：G(V,E)。這兒對點表示從點vi到點vj的單向邊，表示vi與vj之間的無向邊。所以，無向邊等價于兩條有向邊。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

在一個圖G中．如果所有的邊都是無向的，則稱G為無向圖；否則，即至少有一條邊是有向的，則稱G是有向圖。由于無向邊可以等價為兩條有向邊，所以，下面就對有向圖給出一些概念。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

若邊，則稱(u,v)是e的端點，也稱u,v是相鄰的，稱e是點u及v點。的關(guān)聯(lián)邊。若圖G中，某個邊e的兩個端點相同，則稱e是環(huán)；若兩個點之間有多于一條的邊，則稱這些邊為多重邊。一個無環(huán)、無多重邊的圖稱為簡單圖，一個無環(huán)、但有多重邊的圖稱為多重圖。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

給定一個圖G=(V,E)，設(shè)是G中的一個點邊交錯的序列，如果這個序列對均有，則稱該序列為從vi1到vik的一條路。若路的第一個點和最后一個點相同，即vi1=vik，則稱之為回路。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

若在路中，點互不相同，則稱這條路為初等路。一條回路中，若除vi1外其他點互不相同，則稱之為初等回路。在路中，若所含的互不相同，則稱之為簡單路。既是簡單路，又是回路的路，稱之為簡單回路。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念試運用上述概念分析下面的簡單網(wǎng)絡(luò)圖。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

給定兩個圖G(V,E)及G’(V’,E’)，如果，則稱G’是G的一個子圖。進(jìn)而，若，則稱G’是G的一個支撐子圖。子圖支撐子圖13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

在圖G中，如果從點u到點v有路，則稱從點u可以到達(dá)點v。如果對圖G中的任意兩個點，從u都可以到達(dá)v,則稱G是連通圖；否則稱為不連通圖。若G是不連通圖，它的每個連通的部分稱為G的一個連通子圖。13.2網(wǎng)絡(luò)流問題13.2.1圖的基本概念

一個沒有回路的連通圖稱為樹。設(shè)圖G(V,E)是圖G’(V’,E’)的支撐子圖，如果圖G’是一個樹，則稱G’是G的一個支撐樹。13.2網(wǎng)絡(luò)流問題13.2.2最短路

已知如圖所示的交通網(wǎng)絡(luò)圖，每條邊上的數(shù)字表示通過這條路所需要的費用。某公司將倉庫建在了v1處，現(xiàn)在需要通過這個交通圖，將貨物運送到銷售地v7去，求使交通總費用最小的運貨路線。1.問題的提出13.2網(wǎng)絡(luò)流問題13.2.2最短路1.問題的提出

給定一個賦權(quán)有向圖G(V,E)，其中，即對圖G中的每一條邊,有相應(yīng)的權(quán)值w(e)，簡記為wij。vs,vt是G中給定的兩個點。設(shè)P是G中從vs至vt的一條路，定義路P的權(quán)值是P中所有邊的權(quán)值之和，記為w(P)。最短路問題就是在所有從vs至vt的路中，求一條權(quán)值最小的路，即求一條從vs至vt的路P0，使稱P0是從vs至vt的最短路。路P0的權(quán)值也稱為從vs至vt的距離,記為。13.2網(wǎng)絡(luò)流問題13.2.2最短路

顯然，在最短路問題中，可以假定相應(yīng)的圖是簡單圖。因為如果G中有環(huán)，可以刪掉環(huán)；如果G中有多重邊，可以根據(jù)問題的具體含義刪掉多余的邊，使得任意兩點之間只剩下一條邊，或者將多重邊合并為一條．而將多重邊的權(quán)值相加之和作為合并后的邊的權(quán)值。這樣做不會影響以上最短路問題的實質(zhì)。1.問題的提出13.2網(wǎng)絡(luò)流問題13.2.2最短路

最短路問題大量地出現(xiàn)于實際問題中，如管道鋪設(shè)(陸袖管道、天然氣管道等等)，運輸線路安排，廠區(qū)布局，以及計算機(jī)網(wǎng)絡(luò)(包括因特網(wǎng))中通信線路的選擇(路由算法)等等。最短路問題的算法也常作為解決其他優(yōu)化問題的基本工具。1.問題的提出13.2網(wǎng)絡(luò)流問題13.2.2最短路

由動態(tài)規(guī)劃的最優(yōu)性原理，我們知道，如果P是G中從vs至vt的最短路，vi是P中的一個點，那么，從vs出發(fā)沿P到vi的路也是從vs到vi的最短路。因為如果這個結(jié)論不成立，假設(shè)Q是從vs至vi的最短路，令P’是從vs沿Q到vi，再從vi沿P到vt的路，那么P’的權(quán)值就比P的權(quán)值小，這與P是從vs至vt的最短路矛盾。2.最短路的一般算法13.2網(wǎng)絡(luò)流問題13.2.2最短路

由此可知，從vs至vj的最短路，也是從vs到達(dá)其路徑上各個點的最短路，利用動態(tài)規(guī)劃的基本思想，很容易得到下面的最優(yōu)方程。對，記；對。則以上的最優(yōu)方程可等價地寫為：2.最短路的一般算法13.2網(wǎng)絡(luò)流問題13.2.2最短路2.最短路的一般算法算法：最短路算法步驟1：設(shè)節(jié)點數(shù)為n,s=1;步驟2：開始時，令。步驟3；令t=t+1，步驟4：判斷對所有的與是否相等。不成立，轉(zhuǎn)入步驟3；若全都相等，則算法終止，表示vs到vj的最短路的權(quán)值。13.2網(wǎng)絡(luò)流問題13.2.2最短路2.最短路的一般算法

若想進(jìn)一步求從v1到各點的最短路，我們可以利用動態(tài)規(guī)劃法中的方法，按計算順序反推之，逐步求出v1到各個點的最優(yōu)路線?；蛘撸部梢越o每一個點都設(shè)一個λ值：；在迭代過程中，如果則把這時的修改為i*。迭代終止時，根據(jù)各點λ值，從后往前依次遞推，得到從vs到各點的最短路。13.2網(wǎng)絡(luò)流問題13.2.2最短路2.最短路的一般算法

由動態(tài)規(guī)劃的理論可知，是在至多包含t-1個中間點的限制條件下，從vs至vj的最短路的權(quán)。若，表示從s到j(luò)之間不存在一條至多包含t-1個中間點的路。因此，當(dāng)存在j，使時，該圖為不連通圖。13.2網(wǎng)絡(luò)流問題13.2.2最短路2.最短路的一般算法由動態(tài)規(guī)劃理論易知以下定理成立。定理：若上算法進(jìn)行到某一步時，例如第k步時，有則是vs至vj的最短路的權(quán)值。以上定理說明算法在終止時得到的是最短路的權(quán)值。13.2網(wǎng)絡(luò)流問題13.2.2最短路練習(xí)：求下圖所示的賦權(quán)有向圖中從v1到各點的最短路。2.最短路的一般算法13.2網(wǎng)絡(luò)流問題13.2.2最短路

Dijkstra方法的基本思想是從vs出發(fā)，逐步地探尋最短路。在執(zhí)行過程中，與每個點對應(yīng)，記錄下一個數(shù)(稱為這個點的標(biāo)號)，它或者表示從vs到該點的最短的權(quán)值(稱為該點的P標(biāo)號)、或者是從vs到該點的最短路的權(quán)值的上界(稱為該點的T標(biāo)號)，方法的每一步是去修改每一個點的了標(biāo)號，并且把某一個具T標(biāo)號的點改變?yōu)榫逷標(biāo)號的點，從而使G中具P標(biāo)號的點的數(shù)量多一個，這樣，就可以求出從vs到各點的最短路。3.一種常用的方法：Dijkstra算法13.2網(wǎng)絡(luò)流問題13.2.2最短路3.一種常用的方法：Dijkstra算法

Dijkstra方法的具體步驟：(1)令，對每一個，令(2)如果，算法終止，這時，對每個則轉(zhuǎn)入下一步。(3)考察每個使的點vj，如果，修改，把修改為k;否則轉(zhuǎn)入下一步。13.2網(wǎng)絡(luò)流問題13.2.2最短路3.一種常用的方法：Dijkstra算法(4)令，即點vji是T標(biāo)號值最小的點；如果，則把的T標(biāo)號變?yōu)镻標(biāo)號，且令把i換成i+1，轉(zhuǎn)入步驟2；否則，算法終止，這時，對每—個，而對每—個。13.2網(wǎng)絡(luò)流問題13.2.2最短路用Dijkstra方法去求圖中從v1到各個點的最短路。3.一種常用的方法：Dijkstra算法13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論水力輸送圖

一個輸送方案13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

給定一個有向圖G(V,E)，我們在圖G中指定一點，稱為發(fā)點，記作vs

；并指定另外一個點作為收點．記作vt

；其余的點是中間點。如果圖G中的每一條邊都對應(yīng)有一個最大通過能力，稱為邊的容量，我們用表示。通常，我們把這樣的圖G稱為網(wǎng)絡(luò)，記作。同前面一樣，這里僅考慮簡單圖。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

稱定義在邊集合置上的任意一個函數(shù)為網(wǎng)絡(luò)G上的一個流，其中表示邊上的流量，這是因為每條邊的流量不能超過該邊的最大通過能力，這個條件也稱之為“容量限制條件”?？珊唽憺閒ij。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

對每個點，流出這點的量與流人這點的量的差．稱為是該點的凈輸出量，也稱為是該點的流量。顯然，點的流量與流f有關(guān)。在流f下，點i的流量為：在實際的流量問題中，對發(fā)點vs來說常常是輸出多于輸人，因此其流量是正的。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

對收點vt來說，則常常是輸入大于輸出，即流量是負(fù)的；我們這里僅考慮平衡系統(tǒng)，即發(fā)點的凈輸出量與收點的凈輸入量相等，因此有：由于中間點只起過渡的作用，所以要求中間點處的流出量等于流入量，即其流量為零，也即對每個有：以上式子被稱之為“平衡條件”。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題

同時滿足“容量限制條件”和“平衡條件”的網(wǎng)絡(luò)流f就稱為可行流?？尚辛骺偸谴嬖诘?。比如令所有邊的流量，就得到了一個可行流，其流量稱此可行流為零流。最大流問題就是求一個可行流使其流量達(dá)到最大，即1.模型與基本結(jié)論13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

在網(wǎng)絡(luò)中，設(shè)是點集的兩個互不相交的子集，我們把始點在S，終點在T中的所有邊構(gòu)成的集合，記作(S,T)，即若點集V被剖分為兩個非空集合V1和，使，則稱邊集是分離vs和vt的截集，也稱為割集。給定一個滿足條件的集合V1，就可以得到一個截集。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

引理：如果對于一個可行流f*，網(wǎng)絡(luò)中有一個截集使，則f*必是最大流，而必定是G的所有截集中，容量最小的一個，即最小截集。給定一個可行流，我們把網(wǎng)絡(luò)中流量的邊稱為飽和邊；把的邊稱為非飽和邊。把的邊稱為零流邊，的邊稱為非零流邊。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

先不考慮網(wǎng)絡(luò)圖G中有向邊的方向，將其視為一個無向圖G’。設(shè)μ是圖G’中從發(fā)點vs到收點vt的一條路；把路μ放回到有向圖G中，根據(jù)方向的一致性，路上所有的邊被分成了兩類：若邊的方向與路μ的方向一致，則稱之為前向邊。前向邊的全體記作

。另一類是邊的方向與路μ的方向相反的邊，稱之為后向邊。后向邊的全體記作

。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題1.模型與基本結(jié)論

給定一個可行流f，μ是一條從vs到vt的路，若它滿足下列兩個條件，則稱μ為關(guān)于可行流f的一條增廣鏈，（1）對邊，有，即中的每一條邊都是非飽和邊；（2）對邊，有，即中的每一條邊都是非零流邊。引理：若f*是網(wǎng)絡(luò)G中的最大流，則G中不存在關(guān)于f*的增廣鏈。13.2網(wǎng)絡(luò)流問題13.2.3最大流問題定理1：可行流f*是G中最大流，當(dāng)且僅當(dāng)G中不存在關(guān)于f*的增廣鏈。定理（最大流量小截定理)2：在任意一個網(wǎng)絡(luò)G中，從vs到vt的最大流量等于分離vs和vt的最小截集的容量。1.模型與基本結(jié)論13.2網(wǎng)絡(luò)流問題

在尋求實際問題中的最大流時，其基本思路與上面分析的相同：從一個可行流f出發(fā)(若網(wǎng)絡(luò)中沒有給定f，則可以設(shè)f是零流)。經(jīng)過標(biāo)號過程和調(diào)整過程，這種方法稱之為標(biāo)號法。2.尋求最大流的標(biāo)號法13.2.3最大流問題13.2網(wǎng)絡(luò)流問題標(biāo)號過程:

在這個過程中，對網(wǎng)絡(luò)中的各點進(jìn)行標(biāo)號，標(biāo)號后的點又分為已檢查的點和未檢查的點兩種。每個標(biāo)號點的標(biāo)號內(nèi)容包含兩部分：第一個標(biāo)號表明它的前一步是哪一點以方便找出增廣鏈；第二個標(biāo)號是為確定增廣鏈的調(diào)整量θ，改進(jìn)f用的。2.尋求最大流的標(biāo)號法13.2.3最大流問題13.2網(wǎng)絡(luò)流問題2.尋求最大流的標(biāo)號法13.2.3最大流問題

從vs開始，先給vs標(biāo)上(0,+∞)，這時vs成為標(biāo)號而未檢查的點；其余的都是未標(biāo)號的點。然后對網(wǎng)絡(luò)中各未標(biāo)號點按照下列步驟進(jìn)行標(biāo)號。一般地，取一個標(biāo)號而未檢查的點vi，對所有的末標(biāo)號點vj，做以下的工作：

第一步，若邊(vi,vj)上的fij<cij，則給vj標(biāo)號。這里vi表示vj的標(biāo)號從點vi得來,。這時vj成為標(biāo)號而未檢查的點。13.2網(wǎng)絡(luò)流問題2.尋求最大流的標(biāo)號法13.2.3最大流問題

第二步，若邊(vj,vi)上的fji>0，則給vj標(biāo)號。標(biāo)號中意義同上；但，這時vj成為標(biāo)號而未檢查的點。這時vi是標(biāo)號且已檢查過的點。在標(biāo)號過程中，G中的有些點有可能被標(biāo)上多個標(biāo)號。有的標(biāo)號可能來自第一步，有的可能來自第二步，這時，保留l(vj)由第一步得到的標(biāo)號；若從第一步得到的標(biāo)號也有多個，則保留值最大的一個作為標(biāo)號。這樣可以加快找到最大流的速度。13.2網(wǎng)絡(luò)流問題

然后取另一個標(biāo)號而未檢查的點．重復(fù)上述步驟，一