【正文】 況下，線性規(guī)劃至少有一個(gè)有限的最優(yōu)解，有時(shí)它還會(huì)有多重的最優(yōu)解。系統(tǒng)仿真方法正是提供了這種環(huán)境。 ?模擬仿真活動(dòng)有時(shí)要耗費(fèi)大量的時(shí)間和物資，花費(fèi)高昂的代價(jià)才能夠取得成果；而某些物流系統(tǒng)活動(dòng)則不能或者很難做仿真實(shí)驗(yàn) 。 ?數(shù)學(xué)模型，包括原始系統(tǒng)數(shù)學(xué)模型和仿真系統(tǒng)數(shù)學(xué)模型。 ? 計(jì)劃中或設(shè)計(jì)中的過程系統(tǒng)尚不存在。 ? 模型的預(yù)測(cè)性。試求面積為一定值的矩形中，周長(zhǎng)和為最小時(shí)的各邊長(zhǎng)度。 ?在物流供應(yīng)鏈系統(tǒng)建模中的應(yīng)用 第 3章 物流系統(tǒng)優(yōu)化的運(yùn)籌規(guī)劃方法 ? 本章將就物流系統(tǒng)中常見的規(guī)劃模型形式及求解方法進(jìn)行研究，并以一個(gè)物流網(wǎng)絡(luò)布局問題的建模與求解作為實(shí)例說明該方法的一般應(yīng)用過程。 產(chǎn)銷平衡的運(yùn)輸問題存在以下關(guān)系式： ?? ? ?? ??? ? ?? ??????????????????miinjnjmiijminjijjaxxb11 1 11 1 對(duì)于產(chǎn)銷不平衡問題同樣也可以建立線性規(guī)劃模型。 ????)(1)(0段在回路的段不在回路的rXrXXijiji j r 則問題可以構(gòu)成一個(gè)數(shù)學(xué)模型如下： ? ? ??? ? ?11 0 0m i nnrnjnii j rijXC (3 8) 約束條件： njnrXXnkjkj k rnjiii j r,...,2,11,...,2,110,0????? ?????? ( 各段首尾相接 ) (3 9) ? ??????njnri j rniX011, . . . ,1,01 ( 任意點(diǎn) i 必須連在一個(gè)回路中 ) ( 3 1 0 ) ????)(X)(XXijiji j r在回路的r段1不在回路的r段0 ( 3 1 1 ) ? 2. 物流配送計(jì)劃的制定問題 對(duì)于一個(gè)已知標(biāo)準(zhǔn)尺寸的集裝箱或則矩形容器，以及一種已知尺寸的待裝箱的長(zhǎng)方體盒子，集裝箱拼箱及裝箱問題的目標(biāo)是確定一種裝載方案，以便盡可能多的將盒子裝入容器，提高容器的空間利用率。,...,2,10,0)193(,...,2,1)()183(,...2,1)173(,...,2,1)163(,...,2,1)153(,...,2,1143,...,2,1..1111 111或）（iijkininiimkiikimkljijkijniijnikkiZljmkxxniQGiFik i C iZiniPZniVZxnixxljMxmkAxts ? 4. 物流網(wǎng)絡(luò)布局問題的數(shù)學(xué)模型 牛頓法的基本思想 是用二次函數(shù)在極小點(diǎn)附近逼近)( xf，假設(shè)已得到極小的某個(gè)近似點(diǎn) X(k)，將)( xf在 )( kx 作泰勒展開，略去二次以上的項(xiàng)得： )) . ((.)(21).()()()()()()(2)()()()( kkTkkTkTkxxxfxxxxxfxfxxf ????????? ? 取)( x?的極小點(diǎn)作為)( xf的極小點(diǎn)的下一個(gè)近似點(diǎn) )1( ?kx 。,2,1( pjni ?? ??函數(shù)，然后對(duì) Z 函數(shù)求極小值，即可求得原問題的最優(yōu) 解。,2,1()()()(),( mupjXgXhXfXL uujj ?? ????? ? ? ??? ③構(gòu)成 Z 函數(shù)),2,1。 ?步驟 圖 單純形法的求解過程 考慮等式約束問題 其中，),2,1(, ljhf j ??是二次連續(xù)可微函數(shù)， nRx ? 運(yùn)用乘子法，首先定義增廣拉格朗日函數(shù)（乘子懲罰函數(shù)）： ? ?? ????ljljjjjxhxhxfux1 12)(2)()(),(???? )()(2)()( xhxhxhxfTT ?? ??? 其中：0,))(,),(),(()(,),( 2121 ??? ????? TlT xhxhxhxhl ?? ),( ??? x與拉格朗日函數(shù)),( ?xL的區(qū)別在于增加了懲罰項(xiàng))()(2xhxhT?, 而與懲罰函數(shù)的區(qū)別在于增加了乘子項(xiàng)))(( xhT??. 這種區(qū)別使得增廣拉格朗日函數(shù)與拉格朗日函數(shù)及懲罰函數(shù)具有不同的性態(tài)。 （ 2 ）目標(biāo)規(guī)劃法 先分別求出各個(gè)分目標(biāo)函數(shù)的最優(yōu)值)( *xf j，然后根據(jù)多目標(biāo)函數(shù)優(yōu)化設(shè)計(jì)的總體要求，作適當(dāng)調(diào)整，制定出理想的最優(yōu)值)0(jf。因此，最優(yōu)設(shè)計(jì)方案應(yīng)是： qq/121),( ???? ??直到 最大值 （ 4 ）乘除法 如果能將多目標(biāo)函數(shù)優(yōu)化問題中的全部 q 個(gè)目標(biāo)分為：目標(biāo)函數(shù)法愈小愈好的所謂費(fèi)用類（如材料、工時(shí)、成本、重量等）和目標(biāo)函數(shù)值愈大愈好的所謂效益類（如產(chǎn)量、產(chǎn)值、利潤(rùn)、效益等），且前者有 s 項(xiàng) [ ∑ f i ( X ) ] ， ( i = 1 ，2 ， ? ， s) ，后者有 (q s) 項(xiàng) [ ∑ f j ( X ) ] ， ( j = s + 1 ， s + 2 ， ? ， q) ，則統(tǒng)一目標(biāo)函數(shù)可取為 : f ( X ) = ∑ f i ( X ) / ∑f j (X) 使 f(X) 直到 min 可得最優(yōu)解。b 是分?jǐn)?shù)，不滿足整數(shù)解的要求。ib及39。 注意到： 0,0 ?? jij xf ??????nmjijijifxff11 （ 3 25 ） 由于（ 3 23 ）式左端是整數(shù)，由（ 3 25 ）式，可知應(yīng)是小于1 的整數(shù)，所以有 ?????nmjjijixff10 （ 3 26 ） （ 1 ）給定原問題的初始上界 z （ 2 ）給定原問題的初始下界z （ 3 ）將一個(gè)線性規(guī)劃問題分為兩枝 （ 4 ）分別求解上述一對(duì)分枝 ，某個(gè)分枝的可能情況： ①可行解：不必由此繼續(xù)分枝 ②到整數(shù)最優(yōu)解：不由此繼續(xù)分枝。如是，則由節(jié)點(diǎn) 1 繼續(xù)分枝下去，可能得到最優(yōu)解；如否，則不必由節(jié)點(diǎn) 1 再分枝下去，因?yàn)橛晒?jié)點(diǎn) 1 不可能引出可行解。在已得到迄今為止最好的可行解的情況下，判斷各節(jié)點(diǎn)是否繼續(xù)分枝。那么，以? ?ijb為價(jià)值系數(shù)矩陣的新的指派問題的最優(yōu)解與原指 派問題的最優(yōu)解相同，但其最優(yōu)值比原來減小 k 。 作最少的直線覆蓋當(dāng)前所有 0 元素，打 \ 號(hào)得矩陣②， 對(duì)矩陣②進(jìn)行行變換，以增加其 0 元素，當(dāng)矩陣具有 n 個(gè)獨(dú)立的 0 元素時(shí)，即得到了最優(yōu)解?？晒┻x擇的所有全過程策略構(gòu)成允許策略集合，即策略的取值范圍，用)( 1,1 xP n。記作)。指標(biāo)函數(shù)在第 k 階段一個(gè)階段內(nèi)的取值，稱為第 k 階段的指標(biāo)函數(shù)，記作),( kkk uxv。允許策略),( 21,1????? nn uuup ?是最優(yōu)策略的充要條件是：對(duì)任一個(gè))1( nkk ??，當(dāng)初始狀態(tài)為1x時(shí)，有 ????????????????)。( ,1,1,1 nkkn ppp ??，),( 111 ???? kkkk uxTx，kx是由給定的初始狀態(tài) 1x 和子策略1,1 ?kp所確定的第 k階段的狀態(tài)。設(shè) vs和 vt是 D 中任意兩頂點(diǎn)，求一條路，使它是從 vs到 vt的所有路中總權(quán)最小的路。給 vi點(diǎn) P 標(biāo)號(hào)時(shí)，表示從 vs到 vi點(diǎn)的最短路權(quán)， vi的標(biāo)號(hào)不再改變。如果點(diǎn) vj不能由 T 標(biāo)號(hào)變?yōu)?P 標(biāo)號(hào)，則說明 vs到 vj不存在路。則停止。否則，置 k=k+1 。 匈牙利算法是基于 Hall 定理中充分性證明的思想，其基本步驟為： （ 1 ）任給初始匹配 M ； （ 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法匹配而停止，否則任選一點(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的管道的流量上限。 ? 最大流問題就是找出給定流網(wǎng)絡(luò)的最大流。否則，在增廣鏈上進(jìn)行調(diào)整。 在標(biāo)號(hào)過程中，每個(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)集。 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 。 ? 4．求最大流的方法 (FordFulkerson標(biāo)號(hào)法 ) ? ? 貪心法的思想是： 從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。 ? 組合算法： 提前判斷出某些情況不可能取到最優(yōu)解。 對(duì)上面等式求解，需對(duì)等式求微分，然后令其微分值為零，結(jié)果為： 00??? ????nsiisiidsdZ?? （ 3 30 ） 或者? ?? ????sxLsxdxxdxxdsdZ00)()( ?? （ 3 31 ） 上面的計(jì)算結(jié)果表明，所開設(shè)的新店面需在設(shè)置在權(quán)重的中點(diǎn)，即兩面的權(quán)重都是 50% 。 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 的值。? ? 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)系。 以圖 36所示的物流網(wǎng)絡(luò)結(jié)構(gòu)為對(duì)象來介紹 CFLP方法的處理過程 ? 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à)