【正文】 繼續(xù)第 (4)步 。同時可以確定最小割集， 記已標(biāo)號的點集為 V,未標(biāo)號的點集合為 V′,(V,V′)為網(wǎng)絡(luò)的最小割。） (2) 用標(biāo)號的方法找一條增廣鏈 首先給發(fā)點 s標(biāo)號 (∞),標(biāo)號中的數(shù)字表示允許的最大調(diào)整量。) Page 101 網(wǎng)絡(luò)的最大流 求網(wǎng)絡(luò)最大流的標(biāo)號算法： [基本思想 ] 由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。) 推論 2 最大流量 v＊ (f )不大于最小割集的容量，即： v＊ (f ) ? min{c(V, V180。, V) ? f(V, V180。) [證明 ] w= f(V, V180。, V) 推論 1 對網(wǎng)絡(luò) N中任意流量 v(f )和割集 (V, V180。)為任意一個割集，則 v(f ) = f(V, V180。并有 ，稱弧的集合 {(v1,v3),(v2,v4)}是一個割，且 的流量為 18。割容量是組成割集合中的各條弧的容量之和，用 表示。（零流即是可行流） 網(wǎng)絡(luò)最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使 v(f)值達(dá)到最大。容量網(wǎng)絡(luò)上所有的弧滿足： 0≤fij≤cij 中間點平衡條件。 滿足以下條件的一組流稱為 可行流 。 3. 流與可行流 流 是指加在網(wǎng)絡(luò)各條弧上的實際流量，對加在弧 (vi,vj)上的負(fù)載量記為 fij。容量網(wǎng)絡(luò)中通常規(guī)定一個 發(fā)點 (也稱源點，記為 s)和一個 收點 (也稱匯點，記為 t)，網(wǎng)絡(luò)中其他點稱為 中間點 。 ? ? ,),(|),(m i n)( Bjijiklb j ??Page 94 最短路問題 例 求下圖 v1到 v7的最短路長及最短路線 ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 2 3 5 3 4 2 10 5 7 0 8 6 2 2 5 4 4 11 14 7 5 10 7 12 11 v7已標(biāo)號，計算結(jié)束。 v1 v2 v3 v4 v5 Page 93 最短路問題 求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點是 vs,終點是 vt ,以 vi為起點 vj為終點的弧記為 (i, j) 距離為 dij P標(biāo)號 (點標(biāo)號 )： b(j) — 起點 vs到點 vj的最短路長； T標(biāo)號 (邊標(biāo)號 )： k(i,j)=b(i)+dij， 步驟： 1. 令起點的標(biāo)號； b(s)＝ 0。 Page 91 最短路問題 求最短路有兩種算法 : 狄克斯屈拉 (Dijkstra)標(biāo)號算法 逐次逼近算法 Page 92 最短路問題 狄克斯屈拉 (Dijkstra)標(biāo)號算法的基本思路： 若序列 { vs,v1…..v n1,vn }是從 vs到 vt間的最短路，則序列{ vs,v1…..v n1 } 必為從 vs 到 vn1的最短路。 v1 v2 v3 v4 v5 v6 Page 90 最短路問題 問題描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路 . 有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。 性質(zhì) 4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。 性質(zhì) 2： n 個頂點的樹必有 n1 條邊。 A B C D E F G H 運動員 Page 88 樹與圖的最小樹 例 某企業(yè)的組織機構(gòu)圖也可用樹圖表示。在自然和社會領(lǐng)域應(yīng)用極為廣泛。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A Page 84 圖的基本概念與模型 圖的矩陣描述： 如何在計算機中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有： 鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。如果 2個項目有同一名運動員參加，在代表這兩個項目的點之間連一條線，可得下圖。 A B C D E F 甲 √ √ 乙 √ √ √ 丙 √ √ 丁 √ √ 戊 √ √ √ 己 √ √ √ Page 83 圖的基本概念與模型 解：用圖來建模。下表中打 √的是各運動員報告參加的比賽項目。 ※ 有向圖中，所有頂點的入次之和等于所有頂點的出次之和。 端點無序的賦權(quán)圖稱為 無向網(wǎng)絡(luò) ，端點有序的賦權(quán)圖稱為 有向網(wǎng)絡(luò)。 2121 EEVV ?? 和2121 EEVV ?，＝v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 v3 e4 e8 e5 e6 v2 v4 v5 v3 e7 e4 e8 e6 e2 e3 v1 v2 v4 v5 (a) (b) （ G圖） Page 80 圖的基本概念與模型 網(wǎng)絡(luò)（賦權(quán)圖） 設(shè)圖 G＝（ V， E），對 G的每一條邊 (vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij， wij稱為邊 (vi,vj)的 權(quán) ,賦予權(quán)的圖 G稱為網(wǎng)絡(luò) (或 賦權(quán)圖） 。 Page 79 圖的基本概念與模型 子圖，部分圖 (支撐子圖 ) 圖 G1={V E1}和圖 G2={V2， E2}如果有 稱 G1是 G2的一個 子圖 。,使得同一集合中任意兩個頂點均不相鄰，稱這樣的圖為偶圖。如果每一對頂點之間至少存在一條鏈，稱這樣的圖為 連通圖 ，否則稱圖不連通。 Page 77 圖的基本概念與模型 鏈，圈，連通圖 圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意 vi,t1和vit均相鄰稱為 鏈 。次為奇數(shù)的點稱作 奇點 ，次為偶數(shù)的點稱作 偶點 ，次為 1的點稱為 懸掛點 ，次為 0的點稱作 孤立點 。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 Page 76 圖的基本概念與模型 次，奇點，偶點，孤立點 與某一個點 vi相關(guān)聯(lián)的邊的數(shù)目稱為點 vi的 次 （也叫做度），記作 d(vi)。如右圖中邊 e1為環(huán)。若點 vi、 vj與同一條邊關(guān)聯(lián)，稱點 vi和 vj相鄰；若邊 ei和 ej具有公共的端點，稱邊 ei和 ej相鄰 。 e2=[v1,v2]。 Page 74 圖的基本概念與模型 定義 : 圖中的點用 v表示，邊用 e表示。 Page 73 圖的基本概念與模型 (v1) 趙 (v2)錢 孫 (v3) 李 (v4) 周 (v5) 吳 (v6) 陳 (v7) e2 e1 e3 e4 e5 (v1) 趙 (v2)錢 (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 e2 e1 e3 e4 e5 可見圖論中的圖與幾何圖、工程圖是不一樣的。 圖的定義： 若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖 G可以定義為點和邊的集合，記作： },{ EVG ?其中 : V—— 點集 E—— 邊集 ※ 圖 G區(qū)別于幾何學(xué)中的圖。nigsberg橋?qū)?yīng)的圖 Page 72 圖的基本概念與模型 圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 Euler1736年證明了不可能存在這樣的路線。nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。 多目標(biāo)規(guī)劃問題的解法大致可分為兩類：直接解法和間接解法 . 到目前為止，常用的多為間接解法，即根據(jù)問題的實際背景和特征，設(shè)法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，從而得到滿意解的方法 . Page 65 1) 主要目標(biāo)法 在多目標(biāo)優(yōu)化問題中，若能從p個目標(biāo)中，確定一個目標(biāo)為主要目標(biāo)，例如1()fx，而把其余目標(biāo)作為次要目標(biāo)，并根據(jù)實際情況，確定適當(dāng)?shù)慕缦拗?，這樣就可以把次要目標(biāo)作為約束來處理，而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為求解如下的線性或非線性規(guī)劃問題： 1m in ( )( ) 0 , 1 , 2 , ,. . ( ) , 2 , 3 , ,ijjfg i mstf a j p???????xxx Page 66 令? ?( ) 0 , 1 , 2 , , 。 工作人員 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 Page 58 整數(shù)規(guī)劃的特點及應(yīng)用 設(shè) ????工作時人做不分配第工作時人做分配第jijixij 01數(shù)學(xué)模型如下： 4443424134333231242322211413121188809086907983829578879590739285m a xxxxxxxxxxxxxxxxxZ??????????????????要求每人做一項工作，約束條件為： ???????????????????????111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage 59 整數(shù)規(guī)劃的特點及應(yīng)用 每項工作只能安排一人 ， 約束條件為： ???????????????????????111144342414433323134232221241312111xxxxxxxxxxxxxxxx變量約束： 0 1 1 , 2 , 3 , 4ijx i j??或 ， 、對于指派問題等 01 整數(shù)規(guī)劃問題，可以直接利用Matlab 的函數(shù) bintprog 進(jìn)行求解。問應(yīng)如何分配才能使總效率最高？ 設(shè)決策變量 1j( , 1 , 2 , . . . , )0 i jijx i j n?????指 派 第