【正文】 ； （ 2 ）若 X 已飽和則結(jié)束，否則進(jìn)行第 3 步； （ 3 ）在 X 中找到一個(gè)非飽和頂點(diǎn) x0 ，作 V1 ← { x 0 } ， V2 ← Φ ； （ 4 ）若 T ( V 1 ) = V 2 則因?yàn)闊o(wú)法匹配而停止，否則任選一點(diǎn) y ∈T ( V 1 ) \ V2 ； （ 5 ）若 y 已飽和則轉(zhuǎn) 6 ，否則做一條 從 x0 → y 的可增廣道路 P ， M← M ⊕ E(P) ，轉(zhuǎn) 2 ； （ 6 ）由于 y 已飽和，所以 M 中有一條邊 (y ， z) ，作 V1 ← V1 ∪ { z } ， V2 ← V 2 ∪ { y } ， 轉(zhuǎn) 4 ； ? 3. 求二部圖最大匹配（指派問題）的匈牙利算法： 關(guān)于求網(wǎng)絡(luò)最大流和最小割的標(biāo)號(hào)算法： 設(shè) G=(V ， E) 是一個(gè)流網(wǎng)絡(luò)，設(shè) c(u ， v) ＝ 0 表示從 u 到 v的管道的流量上限。設(shè) s 為源， t 為匯。 G 的流是一個(gè)函數(shù) f: V V → R ，且滿足下面三個(gè)特征： （ 1 ） 容量限制：對(duì)于所有的 u ， v ∈ V ， 要求 f(u ， v ) = c(u ， v ) （ 2 ） 斜對(duì)稱性：對(duì)于所有的 u ， v ∈ V ， 要求 f(u ， v ) = f(v ， u ) （ 3 ） 流的會(huì)話：對(duì)于所有的 u ∈ V { s ， t} ，要求∑ f(u ， v ) = 0 ； v ∈ V f(u ， v) 稱為從結(jié)點(diǎn) u 到 v 的網(wǎng)絡(luò)流，它可以為正也可以為負(fù)。流 f 的值定義為： | f | = ∑ f ( s ， v ) v ∈ V 即從源出發(fā)的所有流的總和。 ? 最大流問題就是找出給定流網(wǎng)絡(luò)的最大流。網(wǎng)絡(luò)流問題可以歸結(jié)為一類特殊的線性規(guī)劃問題。 ?增廣鏈 ?截集（割集） ?最大流最小截量定理 （ 1 ）標(biāo)號(hào)法的基本思想：從可行流 f 出發(fā)，由 V s 開始，用對(duì) D 中的每個(gè)頂點(diǎn)進(jìn)行標(biāo)號(hào)的辦法找 f 的增廣鏈 ? 。若無(wú)，則 f 為所求的最大流。否則，在增廣鏈上進(jìn)行調(diào)整。 調(diào)整：}m i n),(m i nm i n {ijijijffw??????? 調(diào)整方法：???????????????????),(),(),(jiijjiijjiijijvvfvvfvvff （ 2 ）步驟 ①給出初始可行流 f( 如 f=0) 。 ②給頂點(diǎn)標(biāo)號(hào)，尋找增廣鏈。標(biāo)號(hào) (v i ， L(v i )) 的第一個(gè)標(biāo)號(hào)表示 v i 點(diǎn)而來(lái)，第二個(gè)標(biāo)號(hào) L(v i )表示增廣鏈上中該弧允許的調(diào)整量。 在標(biāo)號(hào)過(guò)程中，每個(gè)屬于且僅屬于下列 集合之一： V o ：已標(biāo)號(hào)未檢驗(yàn)點(diǎn)集， V s ：已標(biāo)號(hào)已檢驗(yàn)的點(diǎn)集，sV：未標(biāo)號(hào)點(diǎn)集。 首先給 v s 標(biāo)號(hào) (0 ， + ? ) ，此時(shí)， V o ={V s } ? ? ，sV={V 1 ? V t } 。 ③若 V o 非空，則反復(fù)按以下①②進(jìn)行，否則按第 ⑤ 步： 在 V o 中任選 v i ，檢查 v i 到sV的弧 (v i ， v j ) ，或sV中的點(diǎn) v j 到 v i 的弧 (v j ， v i ) ，滿足以下條件者給 v j 標(biāo)號(hào)。 a ) 對(duì)正向弧 (v i ， v j ) ，若非飽和，則給點(diǎn) v j 標(biāo)以 (v i ， l (v j )) ，其中 l (V j ) = m i n { l (v j ) ， (w ij－ f ij )} ，同時(shí)把 V j 從sV中除去，歸入 V o ，若 V t ∈ V o 說(shuō)明已找出 f 的增廣鏈 ? 按 ④ 。 b ) 對(duì)反向弧 (v j ， v i ) ，若非零流，則給點(diǎn) V j 標(biāo)以 ( v i ， l (V j )) ，其中 l (V j ) = m i n { l (v j ) ， f ij } ，同時(shí)把 V j 從sV中除去，歸入 V o 把已檢驗(yàn)的點(diǎn) v i ，歸入 V s 。 ④在增廣鏈 ? 上調(diào)整，得新可行流 f ?。返回 (2) 。 ⑤ 寫出最大流 f*={f ij } 的流量 v(f*) ，和最小截集 W (V s*，*sV) ，終止 。 ? 4．求最大流的方法 (FordFulkerson標(biāo)號(hào)法 ) ? ? 貪心法的思想是： 從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。 ? 該算法存在問題： ?不能保證求得的最后解是最佳的； ?不能用來(lái)求最大或最小解問題； ?只能求滿足某些約束條件的可行解的范圍。 ? 實(shí)現(xiàn)該算法的基本思路是： 從問題的某一初始解出發(fā)，重復(fù)判斷如果能朝給定總目標(biāo)前進(jìn)一步，則求出可行解的一個(gè)解元素，直到由所有解元素組合成問題的一個(gè)可行解為止。 ? 組合算法： 提前判斷出某些情況不可能取到最優(yōu)解。 物流網(wǎng)絡(luò)布局問題的建模與求解 概述 ? ? 2. 物流網(wǎng)絡(luò)規(guī)劃的步驟 ?找出物流網(wǎng)絡(luò)規(guī)劃的約束條件 ?根據(jù)約束條件構(gòu)造物流網(wǎng)絡(luò)符合的模型 ?將物流網(wǎng)絡(luò)符合的模型轉(zhuǎn)化成數(shù)學(xué)模型求出多組可行解 ?利用可行的評(píng)估方法或準(zhǔn)則，對(duì)以上求出的多組可行解進(jìn)行評(píng)估，將各可行解進(jìn)行排序，以選取最適合的規(guī)劃方案 不同位置加上一個(gè)權(quán)重 ? i 。此類問題可以用以下的目標(biāo)函數(shù)進(jìn)行評(píng)價(jià)： ? ?? ?? ?????sinsiiiiisxxsZ0)(mi n ?? （ 3 28 ） 或者 ?? ?? ????LsxsxdxsxxdxxsxZ ))(())((m i n0?? （ 3 29 ） 式中i?—— 大街上第i個(gè)位置出現(xiàn)顧客的概率； ix—— 大街上第i個(gè)位置到所選地址的距離； s—— 選擇投資的位置。 式（ 3 28 ）適用于離散模型，而式（ 3 29 ）適用于連續(xù)模型。 對(duì)上面等式求解，需對(duì)等式求微分，然后令其微分值為零，結(jié)果為： 00??? ????nsiisiidsdZ?? （ 3 30 ） 或者? ?? ????sxLsxdxxdxxdsdZ00)()( ?? （ 3 31 ） 上面的計(jì)算結(jié)果表明，所開設(shè)的新店面需在設(shè)置在權(quán)重的中點(diǎn)，即兩面的權(quán)重都是 50% 。 ? 3. 選址問題的一個(gè)簡(jiǎn)單實(shí)例 多元網(wǎng)點(diǎn)布局問題 ? 1．問題描述 ? 多元網(wǎng)點(diǎn)布局問題通常有如圖35所示的系統(tǒng)結(jié)構(gòu)。圖中有 m個(gè)資源點(diǎn) Ai(i=1， 2， … ， m)，各點(diǎn)的資源量為；有個(gè)需求點(diǎn)，各點(diǎn)的需求量為；有個(gè)可能設(shè)置網(wǎng)點(diǎn)的備選地址；需求點(diǎn)可以從設(shè)置的網(wǎng)點(diǎn)中轉(zhuǎn)進(jìn)貨，也可以從資源點(diǎn)直接進(jìn)貨。假定各備選地址設(shè)置網(wǎng)點(diǎn)的基建投資、倉(cāng)儲(chǔ)費(fèi)用和運(yùn)費(fèi)率均為已知，以總成本最低為目標(biāo)確定網(wǎng)點(diǎn)布局的最佳方案。 A 1 A m D 1 D q B 1 B j B n 資源廠 網(wǎng)點(diǎn) 用戶 圖 35網(wǎng)點(diǎn)布局結(jié)構(gòu)示意圖 建模方法如下： ? ? ? ?? ?? ?? ? ? ?? ?? ??????minjqKmiiKKKKijijqKnjKjKjmiqKiKiKXCWFZCYCXCF1 1 1 11 11 1)(m i n（ 3 32 ） ? ?? ???qKnjiijiKaZX1 1 mi ,2,1 ?? ? ?? ???qKmijijKjbZY1 1 nj ,2,1 ?? ? ?? ??minjKiiKYX1 1 qK ,2,1 ?? ????miKiKMWX10 ????被淘汰被選中KKWK01 0, ?ijKjiKZYX 這是一個(gè)混合整數(shù)規(guī)劃模型，解這個(gè)模型求得 X iK ， Y Kj ， Z ij 和W K 的值。 X iK 表示網(wǎng)點(diǎn) K 的進(jìn)貨來(lái)源，??miiKX1決定了該網(wǎng)點(diǎn)的規(guī)模； Y Kj 表示網(wǎng)點(diǎn) K 與用戶的供求關(guān)系與供貨量，相應(yīng)地也就知道了該網(wǎng)點(diǎn)的供貨范圍；其他還有??miijZ1表示直達(dá)供貨部分，??qKKW1為計(jì)劃區(qū)域內(nèi)應(yīng)布局網(wǎng)點(diǎn)的數(shù)目。 ? 2．多元單品種物流網(wǎng)點(diǎn)布局的建模方法 建模方法如下： ? ? ? ? ? ? ???? ? ? ? ? ? ???????plmiplnjplminjijl i jqKl K jl K jqKl i Kl i KYCYCXCF1 1 1 1 1 1 111m i n ? ? ?? ? ??qKmipll i KKKKXCWF1 1 1)( （ 3 33 ） ? ?? ???qKnjlil i jl i KaZX1 1 mi ,2,1 ?? ? ?? ???qKnjlil i jl K jbZY1 1 nj ,2,1 ?? ?????njl K jmil i KYX11 01 1??? ?? ?miplKl i KMWX 01????Kjpll K jMIY ????plKjl K jMIY10 ????點(diǎn)被淘汰點(diǎn)被選中KKWK01 ????無(wú)供需關(guān)系與用戶網(wǎng)點(diǎn)有供需關(guān)系與用戶網(wǎng)點(diǎn)j0jK1KjKI l i KX，l K jY，0?l i jZ 該模型也是一個(gè)混合整數(shù)規(guī)劃模型。解此模型求得l i KX，l K jY，l i jZ以及 0 1 整數(shù)變量KW，KjI的值。? ? l i KX或? ? l k jY決定了網(wǎng)點(diǎn) K 的規(guī)模，? KW表示為計(jì)劃區(qū)域內(nèi)設(shè)置網(wǎng)點(diǎn)的數(shù)目，由KjI確定網(wǎng)點(diǎn) K 與用戶 j 之間是否存在著供需關(guān)系。從而十分清楚地可以看出，當(dāng)KW等于 0 時(shí)，因l i KX和l K jY均為零，故KjI必為 0 ；當(dāng)KW等于 1 時(shí)，KjI可為 0 或 1 ，KjI為 0 時(shí)表示網(wǎng)點(diǎn) K 與用戶 j 無(wú)供需關(guān)系，為 1 時(shí)有供需關(guān)系，并且商品供貨量不小于jE。 ? 3．多元多品種物流網(wǎng)點(diǎn)布局的建模方法 設(shè)施容量問題（ CFLP法） ? CELP法的基本思想是： 首先假定網(wǎng)點(diǎn)布局方案已經(jīng)確定，即給出一組初始網(wǎng)點(diǎn)設(shè)置地址。根據(jù)初始方案按運(yùn)輸規(guī)劃模型求出各初始網(wǎng)點(diǎn)的供貨范圍，然后在各供貨范圍內(nèi)分別移定網(wǎng)點(diǎn)到其他備選地址上，以使各供貨范圍內(nèi)的總成本下降，找到各供貨范圍內(nèi)總成本最小的新網(wǎng)點(diǎn)設(shè)置地址，再將新網(wǎng)點(diǎn)設(shè)置地址代替初始方案，重復(fù)上述過(guò)程直至各供貨范圍內(nèi)總成本不能再下降時(shí)為止。 以圖 36所示的物流網(wǎng)絡(luò)結(jié)構(gòu)為對(duì)象來(lái)介紹 CFLP方法的處理過(guò)程 ? CFLP 法的基本步驟 ?給出網(wǎng)點(diǎn)地址初始方案 ?確定各網(wǎng)點(diǎn)的供貨范圍 ?尋求網(wǎng)點(diǎn)地址的新方案 ? 新舊方案對(duì)比 D 2 D 1 B 1 B j B n 用戶 備選網(wǎng) 點(diǎn) 圖 36網(wǎng)絡(luò)結(jié)構(gòu)圖 數(shù)例：在某計(jì)劃區(qū)域內(nèi)，物流網(wǎng)絡(luò)結(jié)構(gòu)如圖 36所示，其中有 12個(gè)需求點(diǎn)，“△”中的數(shù)字為各點(diǎn)需求量，弧線旁的數(shù)字為運(yùn)價(jià)系數(shù)?，F(xiàn)需要在 12個(gè)需求點(diǎn)的位置上選取 3個(gè)點(diǎn)作為網(wǎng)點(diǎn)設(shè)置地址。假定網(wǎng)點(diǎn)的最大規(guī)模為 13，設(shè)定每個(gè)網(wǎng)點(diǎn)的固定成本為 10。 [ 步驟 1 ] 根據(jù)調(diào)查分析，選定備選區(qū)域中的 4 ， 6 ， 9 組成初始方案，即 ? ? ? ?9,6,43 10 ??KkD 2 12 5 2 4 3 2 11 2 3 3 10 4 2 5 1 9 4 7