[企業(yè)管理]管理運(yùn)籌學(xué)I本科

1、管 理 運(yùn) 籌 學(xué)主講：陳鼎藩社科系工商管理教研室1 目 錄第1章 線性規(guī)劃第2章 對偶理論第3章 運(yùn)輸問題第4章 整數(shù)規(guī)劃與分配問題 第5章 圖與網(wǎng)絡(luò)分析第6章 方案評審法和關(guān)鍵路線法第7章 目標(biāo)規(guī)劃2第1章 線性規(guī)劃1.1 線性規(guī)劃的數(shù)學(xué)模型1.2 圖解法1.3 單純形法原理與計算步驟1.4 單純形法進(jìn)一步討論1.5 線性規(guī)劃建模3ex1.1:甲企業(yè)方案生產(chǎn)兩種產(chǎn)品、，這兩種產(chǎn)品都要分別在A、B、C、D四種不同設(shè)備上加工，每生產(chǎn)一件產(chǎn)品的設(shè)備加工工時、設(shè)備生產(chǎn)能力、產(chǎn)品單位利潤如下表，問、各生產(chǎn)多少使利潤到達(dá)最大？ 1.1 線性規(guī)劃數(shù)學(xué)模型 生產(chǎn)能力A 2 2 12B 1 2 8C 4 0

2、 16D 0 4 12獲利 2元/件 3元/件4解 設(shè)分別生產(chǎn)、產(chǎn)品數(shù)量為x1、x2 那么利潤Z=2x1+3x2,考慮到設(shè)備的生產(chǎn)能力那么應(yīng)受到以下條件的限制使得2x1+2x212x1 +2x284x1 164x2 12x1，x2 0利潤目標(biāo)為max z=2x1+3x2 A 設(shè)備生產(chǎn)能力約束B 設(shè)備生產(chǎn)能力約束C、D 設(shè)備生產(chǎn)能力約束現(xiàn)實(shí)問題變量非負(fù)Z=2x1 +3x2 max5 線性規(guī)劃模型三要素決策變量variable：指決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問題中要確定的未知量。目標(biāo)函數(shù)objective：問題要到達(dá)的目的要求。約束條件(constrains)：決策變量取值時受到的各種

3、資源的限制。目標(biāo)函數(shù)和約束條件皆為決策變量的線性函數(shù)6 線性規(guī)劃數(shù)學(xué)模型的幾種形式目標(biāo)函數(shù)：maxminz=c1x1 +c2x2 + +cnxna11x1 +a12 x2+ +a1n xn(,=)b1 a21x1 +a22 x2+ +a2n xn (,=)b2 am1x1 +am2 x2+ +amn xn(,=)bm x1 ,x2 ,xn 0.約束條件s.t.簡寫形式7矩陣形式向量形式8標(biāo)準(zhǔn)形式：非標(biāo)準(zhǔn)形式如何轉(zhuǎn)化？目標(biāo)函數(shù)為求極小值約束條件為不等式變量取值無約束目標(biāo)函數(shù)求最大值約束條件取等式變量非負(fù)ex1.2 91.2 圖解法優(yōu)點(diǎn)：直觀性強(qiáng)，便于了解線性規(guī)劃問題解的情況計算步驟：缺點(diǎn)：只能求

4、解兩個變量的線性規(guī)劃模型建立坐標(biāo)系圖示約束條件，確定滿足約束的解的范圍畫出目標(biāo)函數(shù)直線族確定最優(yōu)解10可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860 x1x211線性規(guī)劃問題解的情況唯一最優(yōu)解交于一點(diǎn)無窮多個最優(yōu)解交于一條線段無解無可行域無界解121.3 單純形法解的概念可行解：滿足約束條件的解X=x1, , xnT稱為線性規(guī)劃問題的可行解。可行域：可行解的集合。最優(yōu)解：使目標(biāo)函數(shù)到達(dá)最大值的可行解?；杭僭O(shè)A為約束方程組的mn階系數(shù)矩陣，RA= m, B是A的mm階滿秩子矩陣，那么稱B為線性規(guī)劃問題的一個基。13基向量：B中的每一個列向量pj稱為基向量?；兞浚夯蛄縫j對應(yīng)的變量xj稱為基變量?；?/p>

5、解：在約束方程組 A X = b 中，令所有的非基變量都為零，即 xm+1 = xm+2 = = xn=0， ,又因?yàn)锽滿秩，根據(jù)克拉姆法那么，由m個約束方程組可解出m個基變量的唯一解XBXB=x1,x2, xm ,將這個解加上非基變量取0的值有X= x1,x2, xm，0， 0 T，稱X為線性規(guī)劃問題的基解。基可行解：假設(shè)基解X0，那么X為基可行解。可行基：對應(yīng)于基可行解的基稱為可行基。14ex1.7 找出以下線性規(guī)劃問題的基解、基可行解15凸集及其頂點(diǎn)凸集凸集不是凸集頂點(diǎn)凸集：如果集合C上任意兩個點(diǎn)X1、X2，其連線上的所有點(diǎn)都在集合C上，那么C是凸集。頂點(diǎn):16根本定理定理1：假設(shè)線性規(guī)

6、劃問題存在可行解，那么問題的可行域是凸集。引理1：線性規(guī)劃問題的可行解X=x1,xnT為基可行解的充分必要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。定理2：線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域凸集的頂點(diǎn)。定理3：假設(shè)線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。推論：假設(shè)線性規(guī)劃問題有最優(yōu)解，至少在可行域的一個頂點(diǎn)取得最優(yōu)。17單純形法計算步驟：化為標(biāo)準(zhǔn)型求初始基可行解，列出初始單純形表最優(yōu)性檢驗(yàn)從一個基可行解轉(zhuǎn)換到相鄰的基可行解迭代18單純形表c1 c2 cm cj cn x1 x2 xm xj xn cj c1 x1 b1c2 x2 b2: : : : :cm xm

7、bm cB 基 b1 0 0 a1j a1n0 1 0 a2j a2n: : : : : : : : :0 0 1 amj amj cj - zj0 0 0 19ex1.8 用單純性法求解以下線性規(guī)劃問題20ex1.9 用單純性法求解以下線性規(guī)劃問題211.4 單純形法進(jìn)一步討論人工變量法22化為標(biāo)準(zhǔn)型：添加人工變量x6、x7：23兩階段法第一階段：求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃模型第二階段：假設(shè)第一階段的模型目標(biāo)函數(shù)值為0,那么原問題有可行解。24解的判別：唯一最優(yōu)解基變量不含人工變量所有的檢驗(yàn)數(shù) 0所有的非基變量的檢驗(yàn)數(shù) =700X1+0.5X2+0.2X3+2X4+0.5X5

8、=300.5X1+X2+0.2X3+2X4+0.8X5=100ENDLINDO 輸入文件：LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000LINDO 輸出文件：30 Ex1.11 某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙，各種牌號糖果

9、中A、B、C含量、原料本錢、各種原料的每月限用量，三種牌號糖果的單位加工費(fèi)及售價如下表所示，問該廠每月生產(chǎn)這三種糖果各多少千克，使該廠獲利最大，建立此問題的數(shù)學(xué)模型并求解。甲 乙 丙 原料本錢 每月限用量 元/kg (kg)A 60% 30% 2.00 2000B 1.50 2500C 20% 50% 60% 1.00 1200加工費(fèi)元/kg售價元/kg 3.40 2.85 2.25 0.5 0.4 0.3 31MAX (3.40-0.5)(X11+X21+X31)+(2.85-0.4)()+(2.25-0.3)(X13+X23+X33)-2.0(X11+X12+X13)-1.50(X21+X

10、22+X23)-1.0(X31+X32+X33)=0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=2000X21+X22+X23 =2500X31+X32+X33=0.6X11+X21+X31X31=0.3 (X12+X22+X32 )X32=0.5X12+X22+X32X33=0.6X13+X23+X33END原始模型：32MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+

11、X12+X13=2000X21+X22+X23 =2500X31+X32+X33=0X31-0.2X11-0.2X21-0.2X31=0X32-0.5X12-0.5X22-0.5X32=0X33-0.6X13-0.6X23-0.6X330 ,那么該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，那么其對應(yīng)的對偶變量一定為零。 49ex 2.3 線性規(guī)劃問題：要求：1寫出其對偶問題；2原問題最優(yōu)解為X*=2，2，4，0，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。506基解的互補(bǔ)性 和變量的對應(yīng)關(guān)系： 線性規(guī)劃問題原問題和對偶問題之間存在一對互補(bǔ)的基解，其中原問題的松弛變量對應(yīng)于對偶問題的變量，

12、對偶問題的剩余變量對應(yīng)原問題的變量，這些互相對應(yīng)的變量如果在一個問題的解中是基變量，那么在另一個問題的解中是非基變量。將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)中，有z=.51LP1LP2y1 對應(yīng) x3 y2 對應(yīng)x4 y3對應(yīng)x5 x1對應(yīng)y4 x2對應(yīng)y5 52LP1的最終單純行表：CB 基bx1x2x3x4x52 x10 x43 x23431000011/2-20010-1/54/51/5zj -cj000101/5CB 基by1y2y3y4y512 y115 y311/5102-4/501-1/21/50-1/5zj -cj004033LP2的最終單純行表532.4 影子價格

13、 bi 是線性規(guī)劃問題約束的右端項，代表第i種資源的擁有量 。而對偶變量 yi 的意義代表對一個單位第i種資源的估價，這種估價不是資源的市場價格，是根據(jù)資源在生產(chǎn)中做出的奉獻(xiàn)而作的估價，稱之為影子價格。541影子價格與市場價格的區(qū)別： 市場價格是數(shù)，相比照較穩(wěn)定，而它的影子價格那么有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格隨之改變。552影子價格 是一種邊際價格563資源的影子價格又 是一種時機(jī)本錢 在純市場經(jīng)濟(jì)條件下，在ex2.4中，當(dāng)?shù)?種資源的市場價格低于1/5時，可以買進(jìn)這種資源；當(dāng)市場價格高于影子價格時，就會賣出這種資源。影子價格最終會與

14、市場價格處于同等水平。574互補(bǔ)松弛性的經(jīng)濟(jì)含義585檢驗(yàn)數(shù)的經(jīng)濟(jì)意義cj 代表第j種產(chǎn)品的產(chǎn)值， 是生產(chǎn)該種產(chǎn)品所消耗各項資源影子價格的總和，即產(chǎn)品的隱含本錢。當(dāng)產(chǎn)品的產(chǎn)值大于本錢時，生產(chǎn)該產(chǎn)品有利可圖，應(yīng)安排該種產(chǎn)品檢驗(yàn)數(shù)大于零的變量作為進(jìn)基變量。596資源影子價格的應(yīng)用 對線性規(guī)劃的求解是確定資源的最有效分配方案，而對其對偶問題的求解那么是確定資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效利用。 資源的影子價格可以作為公司內(nèi)部的結(jié)算價格；社會上可對一些最緊缺的資源，借助影子價格規(guī)定使用這種資源一單位時必須上交的利潤額，以控制某些公司超低本錢使用社會資源，侵蝕公眾福利。602.5 對偶單純

15、形法612.6 靈敏度分析 靈敏度分析：對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。62靈敏度分析的步驟1將參數(shù)的改變計算反映到最終的單純形表上2檢查原問題是否仍為可行解3檢查對偶問題是否仍為可行解633檢查對偶問題是否仍為可行解4按下表所列情況得出結(jié)論和決定繼續(xù)計算步驟原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解仍為問題的最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純行表重新計算64分析cj變化的影響65分析bi的變化范圍66增加一個變量的分析增加一個變量的分析在實(shí)際問題中反映為增加一種新產(chǎn)品。e

16、x 2.7 現(xiàn)在該公司方案增加一種新產(chǎn)品x6，該產(chǎn)品單位利潤為4元，p6=(2 4 5)T，原有條件不變，試分析該公司是否生產(chǎn)這種新產(chǎn)品？67增加一個約束條件的分析 增加一個約束條件的分析在實(shí)際問題中反映為增加一道工序或者增加一種資源限制。ex 2.8 增加一個約束條件 3x1+2x214，要求分析最優(yōu)解變化。68第3章 運(yùn)輸問題3.1 運(yùn)輸問題的數(shù)學(xué)模型3.2 表上作業(yè)法3.3 產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用693.1 運(yùn)輸問題的數(shù)學(xué)模型ex3.1 某食品公司經(jīng)銷的主要產(chǎn)品之一就是糖果，其下屬三個生產(chǎn)廠，該公司把這些糖果分別運(yùn)往四個地區(qū)門市部銷售，各加工廠產(chǎn)量、各門市部銷售量及從每個加工廠到各

17、銷售門市部每噸糖果的運(yùn)價如下表所示，問該食品公司應(yīng)如何調(diào)運(yùn)，在滿足各門市部需求量的情況下，使總的運(yùn)費(fèi)支出為最小。 銷地 產(chǎn)地B1 B2 B 3 B4 生產(chǎn)量A1 A2A33 11 3 101 9 2 87 4 10 5749需求量3 6 5 6運(yùn)價70 銷地 Bj 產(chǎn)地 AiB1 Bn 生產(chǎn)量A1 Amc11 c1n cm1 cmna1am需求量b1 bn運(yùn)價cij一般運(yùn)輸問題的運(yùn)輸表7172733.2 運(yùn)輸單純形法 表上作業(yè)法分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價表確定初始調(diào)運(yùn)方案最小元素法orVogel法求檢驗(yàn)數(shù)閉回路法or 位勢法找出絕對值最大的負(fù)檢驗(yàn)數(shù)，閉回路法調(diào)整，得出新的調(diào)運(yùn)方案所有

18、檢驗(yàn)數(shù)0是否得到最優(yōu)方案算出總的運(yùn)費(fèi)迭代74表3-1 表上作業(yè)法計算 銷地 B1B2B 3B4生產(chǎn)量A1 x113113107A219284A3741059需求量3656運(yùn)價產(chǎn)地753.3 產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用ex3.2 設(shè)有A1、A2、A3三個產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為7t、5t、7t，B1、B2、B3、B4四個銷售地需要該物資，銷量分別為2t、3t、4t、6t，又知各產(chǎn)銷地之間的單位運(yùn)價如下表，試決定總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。處理產(chǎn)銷不平衡的思路：轉(zhuǎn)化為產(chǎn)銷平衡問題76 銷地 B1B2B 3B4生產(chǎn)量A1 211347A2103595A378127需求量2346運(yùn)價產(chǎn)地表3-277

19、ex3.3 設(shè)有三個化肥廠供給四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同，各化肥廠年產(chǎn)量，各地區(qū)需要量及從各化肥廠到各地區(qū)單位化肥的運(yùn)價如表3-3所示，試決定使總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。78 產(chǎn)量（萬噸）A1613221750B1413191560C19202350最低需求（萬噸）最高需求（萬噸）3050707003010不限需求地區(qū)化肥廠表3-3運(yùn)價79ex3.4 江南廠按照合同要求需于每個季度末分別完成10、15、25、20臺同一規(guī)格的柴油機(jī)。該廠每個季度生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的本錢如表3-4所示，又如果生產(chǎn)的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)費(fèi)用0.15

20、萬元。要求在完成合同的條件下，制訂使該廠全年生產(chǎn)、儲存和維護(hù)費(fèi)用為最小的決策方案。 季度 生產(chǎn)能力（臺）單臺成本（萬元）12342535301010.811.111.011.3表3-480ex3.5 東海造船廠根據(jù)合同要在當(dāng)年算起的連續(xù)三年年末各提供三條規(guī)格相同的大型貨輪。該廠今后三年的生產(chǎn)能力及生產(chǎn)本錢如表3-5所示。 加班生產(chǎn)情況下每條貨輪本錢比正產(chǎn)生產(chǎn)時多出70萬元，又知造出的貨輪如當(dāng)年不交貨，每條貨輪每積壓一年將增加維護(hù)保養(yǎng)等費(fèi)用為40萬元。在簽訂合同時該廠已有兩條當(dāng)年制造的未交貨的積壓貨輪。該廠希望在第三年年末在交完合同任務(wù)后能儲存一條備用。問該廠應(yīng)該如何生產(chǎn)方案，使在滿足上述要求的

21、條件下，使總的費(fèi)用支出為最小？ 81 年度 正常生產(chǎn)時可完成的貨輪數(shù)加班生產(chǎn)時可完成的貨輪數(shù)正常生產(chǎn)時每條貨輪成本第一年第二年第三年241323500萬600萬550萬表3-582ex3.6 東興煤炭公司下屬桔祥、平安、雙福三個煤礦，年生產(chǎn)能力分別為120、160、100萬t ，公司同三個城市簽訂了下年度的供貨合同：城市1-110萬t,城市2-150萬t,城市3-70萬t,但城市3表示愿意購置剩余的全部煤炭。另有城市4雖未簽訂合同，但也表示只要公司有剩余煤炭，原全部收購。從各礦至四個城市的煤炭單位運(yùn)價見表3-6。 1234吉祥平安雙福856724513235表3 - 6城市煤礦83第4章 整數(shù)

22、規(guī)劃與分配問題4.1 整數(shù)規(guī)劃的特點(diǎn)及作用4.2 分配問題與匈牙利法4.3 分枝定界法 4.4 整數(shù)規(guī)劃建模844.1 整數(shù)規(guī)劃的特點(diǎn)及作用整數(shù)規(guī)劃：要求一局部或全部決策變量必須取整數(shù) 的規(guī)劃問題整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的定義和分類85純整數(shù)規(guī)劃：全部決策變量取整數(shù)的線性規(guī)劃?；旌险麛?shù)規(guī)劃：只要求一局部決策變量取整數(shù)的線 性規(guī)劃問題。0-1規(guī)劃：要求決策變量取0或1邏輯值的規(guī)劃問題。86邏輯變量在建模中的用法1 m個約束條件中只有k個起作用872 約束條件的右端項可能是r個值中的某一個883 兩組條件滿足其中一組894 用以表示含固定費(fèi)用的函數(shù)90ex4.1 現(xiàn)有資金總額為B，可供選擇的工程為n

23、個。工程jj=1n所需投資額和預(yù)期收益分別為aj和cj。此外，由于種種原因，有三個附加條件：第一：假設(shè)選擇工程1就必須選擇工程2；第二：工程3和4至少選擇一個；第三：工程5、6、7恰好選擇兩個。問應(yīng)當(dāng)如何選擇投資工程，才能使總收益最大？試建立此問題的數(shù)學(xué)模型。914.2 分配問題與匈牙利法 m件任務(wù)分別由m個人完成，第jj=1m個人完成第i i=1m件任務(wù)的本錢費(fèi)用為cij，問應(yīng)如何分配任務(wù)可使總費(fèi)用最小。 人員Bj 任務(wù)AiB1 Bm A1 Amc11 c1m cm1 cmm 本錢 cij分配問題Assignment Problem的數(shù)學(xué)模型9293匈牙利法 1955年，庫恩利用匈牙利數(shù)學(xué)家

24、康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解分配問題的一種算法，習(xí)慣上稱之為匈牙利法。 匈牙利法的關(guān)鍵是利用了分配問題最優(yōu)解的以下性質(zhì)：假設(shè)從分配問題的系數(shù)矩陣稱為效率矩陣的某行或某列的各元素分別減去一個常數(shù)k ，得到一個新的矩陣，那么以新矩陣為系數(shù)矩陣的分配問題與原分配問題的最優(yōu)解相同。因?yàn)橄禂?shù)矩陣的這種變化并不影響到數(shù)學(xué)模型的約束方程組，而只是使目標(biāo)函數(shù)減少了常數(shù)k,所以最優(yōu)解不發(fā)生變化。94變換效率矩陣 確定獨(dú)立零元素是否有m個獨(dú)立零元素NY未劃去零元素是否構(gòu)成閉回路每行減去本行最小元素每列減去本列最小元素從“行找，“列畫線從“列找，“行畫線Y最優(yōu)解間隔指派沿閉回路N找到未被直線覆蓋最小

25、元素k，畫線的行Ui=0，否那么Ui=k,畫線的列vj=-k，否那么vj=0匈牙利法計算步驟 :每一元素分別減去Ui和vj95ex4.2 有一份說明書要分別翻譯成英、日、德、俄四種文字，交給甲、乙、丙、丁四個人去完成。因個人專業(yè)不同，他們完成不同文字的翻譯所需的時間如表4-1所示，應(yīng)如何分配翻譯任務(wù)，使這四個人分別完成四項任務(wù)總的時間為最小。 甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119表4 - 1 人工作96一般的分配問題1 人數(shù)和事數(shù)不等的問題 人少事多，一人只做一件事：添上一些虛擬的人，這些虛擬人完成各事的費(fèi)用系數(shù)為0，即這些費(fèi)用不會發(fā)生的。

26、 人少事多，事情必須全部完成：意味著某些人要完成假設(shè)干件事情，那么可將該人化作相同的幾個人來接受指派，這幾個“相同的人做同一件事的費(fèi)用系數(shù)當(dāng)然也相同。 人多事少：添上一些虛擬的事，當(dāng)然完成虛擬事的費(fèi)用為0。972 某事不能由某人做的分配問題 假設(shè)某件事一定不能由某個人來做，那么可將相應(yīng)的費(fèi)用系數(shù)取任意大的系數(shù) M 即可。3 最大化分配問題 目標(biāo)函數(shù)是求最大值，按照以下方法轉(zhuǎn)化為最小分配問題:找出效率矩陣B中最大的元素 m，用m 分別減去原效率矩陣 B 的每一個元素，得出新的效率矩陣 C,那么以C為效率矩陣的最小化分配問題和以B為效率矩陣的最大化分配問題最優(yōu)解相同，求解C 。9899ex4.3

27、某商業(yè)公司方案開辦5家新商店，為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建，建筑公司Aii=15對新商店Bii=15的建造費(fèi)用的報價是cij，見表4-3，商業(yè)公司如何來分配建造任務(wù)，才能使總的建造費(fèi)用最少？ B1B2B3B4B5A1A2A3A4A547666899797171214121514861012107106表4 - 3 建筑商商店報價100ex4.4 對于ex4.2中的分配問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，而讓技術(shù)力量相對較強(qiáng)的建筑公司A1 、A2 和A3來承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一家或二家商店。求使總費(fèi)用最少的指派方案。 B1B

28、2B3B4B5A1A2A3476899717121514812107 建筑商商店1014.3 分枝定界法Branch and Bound method102分枝定界法的思路和步驟1求解整數(shù)規(guī)劃的松弛問題 設(shè)整數(shù)規(guī)劃問題為A，它的松弛問題為B，那么A的可行域是B 的可行域的子集 。假設(shè)B無可行解那么A無可行解；假設(shè)B的最優(yōu)解是A的可行解滿足A整數(shù)要求，那么也是A的最優(yōu)解；否那么B的最優(yōu)解不滿足A的整數(shù)要求就是A最優(yōu)解的上界求極大時或下界值求極小時，轉(zhuǎn)2。1032分枝 對問題B，任選一個不符合整數(shù)要求的變量進(jìn)行分枝。1043定界 對B的子問題求最優(yōu)解，假設(shè)該解滿足A的約束，即找到了A的一個可行解，

29、否那么該解為所屬分枝的邊界值求極大化時為上界，求極小化時為下界。 假設(shè)所有的子問題的最優(yōu)解均非A的可行解，那么選取其邊界值最大求極大值時或最小求極小值時的子問題進(jìn)一步細(xì)分子問題求解 分枝過程一直進(jìn)行下去，直到找到A的一個可行解為止。假設(shè)計算時同時出現(xiàn)兩個以上可行解，那么選取其中最大求極大值時或最小求極小值時的一個保存，轉(zhuǎn)4。1054剪枝 將各子問題的邊界值與保存的可行解的值進(jìn)行比較，把邊界值劣于可行解的分枝剪去。假設(shè)除保存下來的可行解外，其余分枝均被剪去，那么該可行解就是A的最優(yōu)解；否那么回到2，選取邊界值最優(yōu)的一個繼續(xù)分枝。 假設(shè)計算中又出現(xiàn)新的可行解，那么與原可行解進(jìn)行比較，保存最優(yōu)的，并

30、重復(fù)上述步驟。106 L0X1=3.25 X2=2.5 Z=14.75 L1X1=3.5 X2=2 Z=14.5 L2X1=2.5 X2=3 Z=13.5 L11X1=3 X2=2 Z=13 L12X1=4 X2=1 Z=14X22X23X13X14分枝定界過程1074.4 整數(shù)規(guī)劃建模ex4.6 東方大學(xué)計算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生代號1、2、3、4和2名研究生代號5、6值班答疑。每人從周一至周五每天最多可安排的值班時間及每人每小時值班報酬如下表學(xué)生代號報酬(元/h)每天最多可安排的值班時間 周一 周二 周三 周四 周五1 2345610.010.0 9.9 9.810.811.3 6 0 6

31、 0 7 0 6 0 6 0 4 8 3 0 5 5 5 6 0 4 3 0 4 8 0 0 6 0 6 3 108 該實(shí)驗(yàn)室開放時間是8：00至晚上10：00，開放時間須有且僅須一名學(xué)生值班。規(guī)定大學(xué)生每周值班不少于8小時，研究生每周不少于7小時。每名學(xué)生每周值班不超過3次，每次值班不少于2小時，每天安排值班的學(xué)生不超過3人。且其中必須有一名研究生。試為該實(shí)驗(yàn)室安排一張人員的值班表，試總支付報酬最小。109Ex4.7 下表為某醫(yī)院每天的護(hù)士值班最低需求人數(shù)。護(hù)士連續(xù)工作5天必須休息2天。在正常工作日5天周工資為300元；周六上班額外補(bǔ)助25元；周日上班額外補(bǔ)助35元。試安排護(hù)士值班方案，使醫(yī)

32、院的總工資支出最少。DayMonTueWedThu Fri Sat SunReq15171414151920110Ex4.8 鞍山街郵局周一到周日每天所需值班人員如下表所示：DayMonTueWedThu Fri Sat SunReq15171414151920 1規(guī)定郵局職工每周上班5天，休息2天，具體上班和休息時間由郵局安排，但保證每名職工每周至少有一個休息日安排在周六和周日。問該郵局至少應(yīng)配備多少名職工，試建立數(shù)學(xué)模型并求解； 2在上述給定條件的根底上，又假定該郵局有主任、副主任各一人，上級規(guī)定每天值班人員中至少有一名主任或副主任，又同樣保證主任或副主任每周至少休一個周六或周日，試建立數(shù)

33、學(xué)模型并求解。111 ex4.9 紅星日用化工廠為發(fā)運(yùn)產(chǎn)品,下一年度需6種不同容積的包裝箱，每種包裝箱的需求量及生產(chǎn)一個可變費(fèi)用如下表：包裝箱代號123456容積(m3)需求量(個)可變費(fèi)用(元/個) 0.085005.00.15508.00.1270010.00.1590012.10.2045016.30.2540018.2 由于生產(chǎn)不同容積包裝箱時需進(jìn)行專門準(zhǔn)備、下料等，生產(chǎn)某一容積包裝箱的固定費(fèi)用為1200元。又假設(shè)某一容積包裝箱數(shù)量不夠時，可用比它容積大的代替，試問該化工廠應(yīng)訂做哪幾種代號的包裝箱各多少個，使費(fèi)用最節(jié)省。112ex4.10 春江市方案為新建的5個居民小區(qū)中的兩個分別各設(shè)

34、一所小學(xué)，下表給出了各小區(qū)內(nèi)及各小區(qū)間的步行時間min,及各居民小區(qū)小學(xué)生人數(shù)。要求為該市提供決策建議，兩所小學(xué)應(yīng)分別建在哪兩個小區(qū)，以及各居民小區(qū)的小學(xué)生應(yīng)分到哪所小學(xué)上學(xué)，使學(xué)生總的上學(xué)步行時間為最短。 小學(xué)位于該區(qū)小學(xué)生人數(shù) 至其他區(qū)步行時間（min） 1234512345200180300160350 5 20 15 25 10 20 4 20 15 25 15 20 6 25 15 25 15 25 4 12 10 25 15 12 5113ex4.11 清遠(yuǎn)市下設(shè)8個區(qū)，下表給出救護(hù)車從一個區(qū)至另一個區(qū)的車程min，該市擬建救護(hù)中心，要求各區(qū)離救護(hù)中心的車程必須在8min內(nèi)，試為該

35、市提供決策建議：至少建立多少個救護(hù)中心，建于何處？ 至從 2 3456781234567891011127131378141187881712101410151410916712114ex4.12 某公司需生產(chǎn)2000件某種產(chǎn)品，該種產(chǎn)品可利用A、B、C、D設(shè)備中任意一種加工，每種設(shè)備的生產(chǎn)準(zhǔn)備結(jié)束費(fèi)、生產(chǎn)該產(chǎn)品時的單件本錢以及每種設(shè)備限定的最大加工能力件如下表所示，問如何安排產(chǎn)品生產(chǎn)，使得總費(fèi)用最低。試建立該問題的數(shù)學(xué)模型。 設(shè)備準(zhǔn)備結(jié)束費(fèi)(元)生產(chǎn)成本（元/件）生產(chǎn)能力（件）ABCD1000 980 800 70020241628 900100012001600115ex4.13 漢光汽車

36、制造廠生產(chǎn)珠江、松花江、黃河三種牌號的汽車。各生產(chǎn)1臺時的鋼材、勞動力消耗及單位利潤，每月可供使用的鋼材及勞動力小時數(shù)見下表所示：珠江松花江黃河每月可供量鋼材（t）勞動力（h）1.53003.02505.0400 6 000 600 000預(yù)期利潤（元）200030004000 上述三種汽車的的經(jīng)濟(jì)批量均為月產(chǎn)1000臺以上，即各牌號汽車或不生產(chǎn)或大于1000臺/月，試為該廠找出一個使利潤最大的生產(chǎn)方案方案。116第5章 圖與網(wǎng)絡(luò)分析5.1 圖的根本概念與模型5.2 樹圖和圖的最小生成樹5.3 最短路問題5.4 網(wǎng)絡(luò)最大流5.5 最小費(fèi)用流1175.1 圖的根本概念與模型哥尼斯堡七橋難題 Se

37、ven Bridges PuzzleAB 瑞士數(shù)學(xué)家歐拉E Euler于1736年發(fā)表了題為“依據(jù)幾何位置的解題方法的論文，有效地解決了七橋難題，被認(rèn)為是圖論的創(chuàng)始人。118環(huán)球旅行問題 1857年，愛爾蘭數(shù)學(xué)家哈密爾頓Hamilton創(chuàng)造了一種游戲，他用一個實(shí)心正12面體象征地球，正12面體的20個頂點(diǎn)分別代表世界上20座名城，要求游戲者從任一城市出發(fā)，尋找一條可經(jīng)由每個城市一次且僅一次再回到出發(fā)點(diǎn)的路，這就是“環(huán)球旅行問題。119 它與七橋問題不同，前者要在圖中找一條經(jīng)過每邊一次且僅一次的路，通稱歐拉回路，而后者是要在圖中找一條經(jīng)過每個點(diǎn)一次且僅一次的路，通稱為哈密爾頓回路。 在這一時期，

38、還有許多諸如迷宮問題、博奕問題以及棋盤上馬的行走路線之類的游戲難題，吸引了許多學(xué)者。這些看起來似乎無足輕重的游戲卻引出了許多有實(shí)用意義的新問題，開辟了新學(xué)科。 運(yùn)籌學(xué)中的“中國郵路問題：一個郵遞員從郵局出發(fā)要走遍他所負(fù)責(zé)的每條街道去送信，問應(yīng)如何選擇適當(dāng)?shù)穆肪€可使所走的總路程最短。這個問題是由我國管梅谷教授在1962年首先提出，因此國際上成為“中國郵路問題。它與歐拉回路有密切的關(guān)系。而著名的“貨郎擔(dān)問題那么是一個帶權(quán)的哈密爾頓回路問題。120龐加萊猜測 任何一個封閉的三維空間，只要它里面所有封閉曲線都可以收縮成一點(diǎn)，這個空間就一定是一個三維圓球這就是法國數(shù)學(xué)家龐加萊于1904年提出的猜測。20

39、00年5月，美國的克萊數(shù)學(xué)研究所為每道題懸賞百萬美元求解。 2006年6月3日，中山大學(xué)朱熹平教授和曹懷東以一篇長達(dá)300多頁的論文，給出了龐加萊猜測的完全證明。破解了國際數(shù)學(xué)界關(guān)注上百年的重大難題龐加萊猜測。運(yùn)用漢密爾頓、佩雷爾曼等的理論根底，朱熹平和曹懷東第一次成功處理了猜測中“奇異點(diǎn)的難題，從而完全破解了困擾世界數(shù)學(xué)家多年的龐加萊猜測。121 圖：如果用點(diǎn)表示研究的對象，用邊表示這些對象之間的聯(lián)系，那么圖G可以定義為點(diǎn)和邊的集合，記作G = V，E 。式中V是點(diǎn)的集合，E是邊的集合當(dāng)V、E都是有限集合時稱G為有限圖，否那么為無限圖。 網(wǎng)絡(luò)圖：如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)，如距離

40、、費(fèi)用、容量等，把這樣的圖稱為網(wǎng)絡(luò)圖，記作N。 122 上圖中的點(diǎn)(又稱頂點(diǎn)或節(jié)點(diǎn))用“v 表示，邊用“e 表示，對每條邊可用它所聯(lián)結(jié)的點(diǎn)表示，如記作e1=v1,v2。如果邊vi, vj的端點(diǎn)有序，即它表示以vi為始點(diǎn) ，vj為終點(diǎn)的有向邊或稱弧此時圖G稱之為有向圖。否那么為無向圖。圖的表示v4v2v3v1v2v1e1123 端點(diǎn)，關(guān)聯(lián)邊，相鄰 假設(shè)有邊e可表示為是e=vi, vj,稱vi、 vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj關(guān)聯(lián)邊。 假設(shè)點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；假設(shè)邊ei和ej具有公共的端點(diǎn)，稱邊 ei和ej相鄰。 124環(huán)，多重邊，簡單圖 如果邊e的兩個端點(diǎn)

41、相重，稱該邊為環(huán)。如果兩個點(diǎn)之間的邊多于一條，稱為具有多重邊。對無環(huán)、無多重邊的圖稱作簡單圖。 次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn) 與某一個點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)的次(也叫做度或線度)，記作d(vi)。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。 任何圖中頂點(diǎn)次數(shù)的總合等于邊數(shù)的兩倍，任何圖中奇點(diǎn)必為偶數(shù)個。125用點(diǎn)的次數(shù)來求解一筆畫問題：126鏈，圈，路，回路，連通圖 圖中有些點(diǎn)和邊的交替序列 = v0 , e1 ，v1, e2 ， ，ek ， vk ，假設(shè)其中各邊el，e2， ，ek 互不相同，且任意vi，t-1 和 vi，t (2tk)均相鄰，稱為鏈 如果鏈中所有的頂點(diǎn)

42、 v0，v1， ，vk也不相同，這樣的鏈稱為路。 對起點(diǎn)與終點(diǎn)相重合的鏈稱作圈，起點(diǎn)與終點(diǎn)重合的路稱作回路 假設(shè)在一個圖中，如果每一對頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否那么稱該圖是不連通的 127完全圖，偶圖 一個簡單圖中假設(shè)任意兩點(diǎn)之間均有邊相連，稱這樣的圖為完全圖含有n個頂點(diǎn)的完全圖，其邊數(shù)有n(n-1)/2條 如果圖的頂點(diǎn)能分成兩個互不相交的非空集合V1和V2，使在同一集合中任意兩個頂點(diǎn)均不相鄰，稱這樣的圖為偶圖(也稱二分圖) 如果偶圖的頂點(diǎn)集合V1和V2之間的每一對不同頂點(diǎn)都有一條邊相連，稱這樣的圖為完全偶圖 完全偶圖中V1含m個頂點(diǎn)，V2含n個頂點(diǎn)，那么其邊數(shù)共mn條.

43、128子圖，局部圖 圖G1=V1，E1和圖G2=V2，E2如果有V1 V2和E1 E2，稱G1是G2的一個子圖假設(shè)有V1=V2，E1 E2，那么稱G1是G2的一個局部圖. 注意局部圖也是子圖，但子圖不一定是局部圖 129ex5.1 證明在9個工廠之間，不可能每個工廠只與其它3個工廠有業(yè)務(wù)聯(lián)系，也不可能只有4個工廠與偶數(shù)個工廠有業(yè)務(wù)聯(lián)系。 ex5.2 6個人圍成圓圈就座，每個人恰好只與相鄰者不相識，是否可以重新就座，使每個人都與鄰座相識？ 130ex5.3 有甲、乙、丙、丁、戊、己六名運(yùn)發(fā)動報名參加A、B、C、D、E、F六個工程的比賽下表中打“的是各運(yùn)發(fā)動報名參加的比賽工程問六個工程的比賽順序應(yīng)

44、如何安排，做到每名運(yùn)發(fā)動都不連續(xù)地參加兩項比賽 ABCDEF甲乙丙丁戊己1315.2 樹圖和圖的最小生成樹 樹圖(簡稱樹，記作T (V，E)是一類簡單而十分有用的圖樹圖的定義是無圈的連通圖 這類圖與大自然中樹的特征相似，因而得名樹圖鐵路專用線、管理組織機(jī)構(gòu)、學(xué)科分類和一些決策過程往往都可以用樹圖的形式表示 24351132性質(zhì)1：任何樹中必存在次為1的點(diǎn) 樹的性質(zhì) 以后稱次為1的點(diǎn)為懸掛點(diǎn)，與懸掛點(diǎn)關(guān)聯(lián)的邊稱為懸掛邊很顯然，如果從樹圖中拿掉懸掛點(diǎn)及與其關(guān)聯(lián)的懸掛邊，余下的點(diǎn)和邊構(gòu)成的圖形仍連通且無圈，那么還是一個樹圖 性質(zhì)2：具有n個頂點(diǎn)的樹的邊數(shù)恰好為(n-1)條 性質(zhì)3：任何具有n個頂點(diǎn)

45、、(n-1)條邊的連通圖是樹 133 兩點(diǎn)說明： 1樹是無圈連通圖中邊數(shù)最多的，在樹圖上只要任意再加上一條邊，必定會出現(xiàn)圈 2由于樹圖是無圈的連通圖，即樹圖的任意兩個點(diǎn)之間有一條且僅有一條惟一通路因此樹圖也是最脆弱的連通圖只要從樹圖中取走任一條邊，圖就不連通因此一些重要的網(wǎng)絡(luò)不能按樹的結(jié)構(gòu)設(shè)計 134圖的最小生成樹定理1：圖中任一個點(diǎn)i，假設(shè)j是與i相鄰點(diǎn)中距離最近的，那么邊i，j必含在該圖的最小局部樹內(nèi) 如果G1是G2的局部圖，又是樹圖，那么稱G1是G2的局部樹(或支撐樹)樹圖的各條邊稱為樹枝(假定各邊均有權(quán)重)，一般圖G，含有多個局部樹，其中樹枝總長最小的局部樹，稱為該圖的最小生成樹(也稱

46、最小支撐樹，minimum spanning tree) 推論：把圖的所有點(diǎn)分成V和 兩個集合，那么兩集合之間連線的最短邊一定包含在最小局部樹。135用破圈法求最小生成樹方法：從網(wǎng)絡(luò)圖N中任取一回路，去掉這個回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N1在N1中再任取一回路，再去掉回路中權(quán)數(shù)最大的一條邊，得N2如此繼續(xù)下去，一直到剩下的子圖中不再含回路止該子圖就是N的最小局部樹 v1v2v3v5v7v6v4527274263161365.3 最短路問題 最短路問題，一般來說就是從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間權(quán)數(shù)最短的一條路。權(quán)數(shù)可以是距離、時間、費(fèi)用等。 有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更

47、新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題，也可以歸結(jié)為求最短路問題。 求最短路有兩種算法，一是求從某一點(diǎn)到其他各點(diǎn)之間最短距離的Dijkstra1959算法，另一種是求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短距離的矩陣算法。137Dijkstra算法(標(biāo)號算法)的根本思路和步驟 Dijkstra算法由荷蘭計算機(jī)大師Dijkstra于1959年提出，可用于求解指定兩點(diǎn)間的最短路，或從指定點(diǎn)到其余點(diǎn)的最短路，目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路的最好算法。13824351全局最短，局部必最短。 假設(shè)用dij表示圖中兩相鄰點(diǎn)i和j的距離，假設(shè)i和j不相鄰，令dij =，顯然dii =0，假設(shè)用Lsi表示從s到i點(diǎn)的最短距離，

48、現(xiàn)要求從s點(diǎn)到某一點(diǎn)t的最短路，用Dijkstra 算法的步驟如下：139 1從點(diǎn)s出發(fā)，因Lss=0，將此值標(biāo)在s旁的小方框內(nèi)，表示s點(diǎn)已經(jīng)標(biāo)號； 2從s點(diǎn)出發(fā)，找出與s相鄰的點(diǎn)中距離最小的一個，設(shè)為r,將Lsr = Lss +dsr的值標(biāo)在r旁的小方框內(nèi)，說明點(diǎn)r已有標(biāo)號； 3從已標(biāo)號的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號點(diǎn)p，假設(shè)有Lsp = min Lss+ dsp; Lsr + drp,那么對p點(diǎn)標(biāo)號，并將Lsp的值標(biāo)注在p旁小方框中； 4重復(fù)第3步，一直到t點(diǎn)得到標(biāo)號為止。140ex5.5 一艘貨輪在A港裝貨后駛往F港，中途需靠港加油和淡水，從A港到F港全部可能的航線及距離如以下圖

49、所示，F(xiàn)港有三個碼頭F1、F2、F3，試求最合理的停靠的碼頭及航線，使總路程最短。50AB1B2C1C2C3D1D2F1F2F345203060403050604030555030204030141ex5.4 某工廠使用一臺設(shè)備，每年年初工廠都要作出決策，如果繼續(xù)使用舊的，要付維修費(fèi)，假設(shè)購置新設(shè)備，要付購置費(fèi)。試制定一個5年的更新方案，使總支出最少。 設(shè)備在各年的購置費(fèi)，及不同機(jī)器役齡時的殘值與維修費(fèi)，如下表所示：第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210142Floyd算法矩陣算法 以任意兩點(diǎn)i,j間的距

50、離來構(gòu)造矩陣：D=d i jn n，假設(shè)i,j 相鄰那么d i j= l i j ,不相鄰那么 d i j = ，顯然 d i i = 0。143v1v2v3v5v7v6v452727426316144ex5.5 某地區(qū)的交通網(wǎng)絡(luò)如以下圖所示，其中點(diǎn)代表居民小區(qū)，邊代表公路，權(quán)值為公路距離，問區(qū)中心醫(yī)院應(yīng)該建在哪個小區(qū)，可使離醫(yī)院最遠(yuǎn)的居民小區(qū)就診時所走的路程最近?302060203018251515v1v2v3v4v5v6v71455.4 最大流問題 最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流，等等。

51、 20世紀(jì)50年代福特Ford、富克遜Fulkerson建立的“網(wǎng)絡(luò)流理論，是網(wǎng)絡(luò)應(yīng)用的重要組成局部。 146最大流有關(guān)概念 容量網(wǎng)絡(luò)是指對網(wǎng)絡(luò)上的每條弧vi，vj)都給出一個最大的通過能力，稱為該弧的容量，記為cvi，vj)或簡寫為cij。 在容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中既非發(fā)點(diǎn)又非收點(diǎn)的其他點(diǎn)稱為中間點(diǎn)。 網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量對有多個發(fā)點(diǎn)和多個收點(diǎn)的網(wǎng)絡(luò)，可以另外虛設(shè)一個總發(fā)點(diǎn)和一個總收點(diǎn)，并將其分別與各發(fā)點(diǎn)、收點(diǎn)連起來，就可以轉(zhuǎn)換為只含一個發(fā)點(diǎn)和一個收點(diǎn)的網(wǎng)絡(luò)所以下面只研究具有一個發(fā)點(diǎn)和一個收點(diǎn)的網(wǎng)絡(luò) 147v1v2v3v5v7v6527274316148 流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量。 對加在弧vi , vj)上的負(fù)載量記作fvi , vj) ，或簡寫為fij 假設(shè)網(wǎng)絡(luò)上所有的fij =0，這個流稱為零流 稱在容量網(wǎng)絡(luò)上滿足以下條件的一組流為可行流： (1)容量限制條件對所有弧有： 0 fvi , vj) cvi , vj) (2)中間點(diǎn)j平衡條件： fvi , vj) = fvj , vk) 假設(shè)以 v (f) 表示網(wǎng)絡(luò)中從s t的流量那么有 fvs , vj) = fvj , vt) 149割和流量 割是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使s f的流中斷的一組