運(yùn)輸模型方案的評(píng)估

1、供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型方案的評(píng)估方案的評(píng)估v某公司有三座工廠均生產(chǎn)相同之產(chǎn)品。該公司另有四個(gè)倉(cāng)庫(kù)存放這些產(chǎn)品。請(qǐng)問(wèn)該公司應(yīng)如何將三座工廠生產(chǎn)之產(chǎn)品分配到四個(gè)倉(cāng)庫(kù)而使運(yùn)輸之成本最低?從工廠1每期可供應(yīng)量從工廠1到倉(cāng)庫(kù)A之單位運(yùn)輸成本倉(cāng)庫(kù)A每期可儲(chǔ)存量每期總需求量每期總供應(yīng)量運(yùn)輸模型方案的評(píng)估方案的評(píng)估v運(yùn)輸模型所具備之基本假設(shè)如下v1.運(yùn)送之貨物為同質(zhì)之產(chǎn)品。v2.不論運(yùn)貨量多寡。每單位運(yùn)輸成本皆相同v3.各起站到各目的地運(yùn)輸路線只有一條v求解步驟1.求初始解2.最佳解測(cè)試3.改進(jìn)

2、次佳解v求初始解之方法求初始解之方法1.直覺(jué)最低成本法2.西北角法3.差額法(Vogels Approximation Method) VAM 又稱為懲罰法(Penalty Method) 供應(yīng)477112388810165450450100200150需求8090120160工廠2工廠3倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A運(yùn)輸模型求初始解v運(yùn)輸模型求初始解西北角法求解步驟v1.由西北角方格開(kāi)始v2.將最大可行量分配給該方格，並劃掉該列或行或兩者v3.繼續(xù)由西北角方格重覆步驟2。直到分配完畢80202070701301201010150150v初始解之總成本v=80*4+20*7+70*3+120*

3、8+10*8+150*5=2460供應(yīng)477112388810165450450100200150需求8090120160工廠2工廠3倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A運(yùn)輸模型求初始解v運(yùn)輸模型求初始解直覺(jué)最低成本法求解步驟v1.找最低成本方格v2.將最大可行量分配給該方格，並劃掉該列或行或兩者v3.找次低成本方格重覆步驟2。直到分配完畢1006090110609080101101010運(yùn)輸模型求初始解v運(yùn)輸模型求初始解差額法求解步驟v1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)v2.選擇差額最大之行或列中方格成本最低者優(yōu)先分配，並劃掉該列或行或兩者。v3. 重覆步驟1。直到分

4、配完畢行差額4414列差額353901105運(yùn)輸模型求初始解v運(yùn)輸模型求初始解差額法求解步驟v1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)v2.選擇差額最大之行或列中方格成本最低者優(yōu)先分配，並劃掉該列或行或兩者。v3. 重覆步驟1。直到分配完畢行差額414列差額30390110410060運(yùn)輸模型求初始解v運(yùn)輸模型求初始解差額法求解步驟v1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)v2.選擇差額最大之行或列中方格成本最低者優(yōu)先分配，並劃掉該列或行或兩者。v3. 重覆步驟1。直到分配完畢行差額483列差額039011081006011010608010供應(yīng)

5、477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.v初始解之總成本v=100*1+90*3+110*8+80*8+10*16+60*5=2350v運(yùn)輸模型求初始解後最佳解測(cè)試求初始解後最佳解測(cè)試需要評(píng)估每個(gè)未分配方格是否有改進(jìn)之可能。評(píng)估之方法有兩種1.踏石法2.修正分配法10090608011010供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.踏石法v空方格空方格1-A評(píng)估v若1-A增加一單位1

6、-D必須減少一單位v1-D減少一單位3-D必須增加一單位v3-D增加一單位3-A必須減少一單位v是否採(cǎi)用方格方格1-A就要看成本是否有減少v(+)=4+5=9v(- )=1+8=910090608011010+-+-v所以此改變對(duì)成本沒(méi)有影響，繼續(xù)評(píng)估空方格1-B,1-C,2-A,2-D,3-B看那個(gè)改變成本降低最多v用踏石法建立封閉路徑時(shí)，必須選擇最少之實(shí)方格v且實(shí)方格數(shù)必須等於行數(shù)+列數(shù)-1v若實(shí)方格數(shù) 行數(shù)+列數(shù)-1則該矩陣稱為退化供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.踏石法v

7、空方格空方格1-B評(píng)估v(+)=7+5+8=20v(- )=1+16+3=20v所以此改變對(duì)成本沒(méi)有影響，繼續(xù)評(píng)估空方格,1-C,2-A,2-D,3-B看那個(gè)改變成本降低最多10090608011010+-+-+-供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.踏石法v空方格空方格1-C評(píng)估v(+)=7+5=12v(- )=1+16=17v所以此改變對(duì)成本會(huì)降低5，繼續(xù)評(píng)估空方格2-A,2-D,3-B看那個(gè)改變成本降低最多10090608011010+-+-供應(yīng)4771123888101654

8、50450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.踏石法v空方格全部空方格全部評(píng)估之後若有成本均大於等於0表示此解以是最佳解v若有負(fù)成本表示，此解可發(fā)展出改良解v所以我們從最大負(fù)成本開(kāi)始改良v1-C最多可增加10v改良後，繼續(xù)評(píng)估空方格看看是否已經(jīng)是最佳解10090608011010+-+-空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-1供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.踏石法v空方格空方格1-

9、C評(píng)估後成本降低最多v空方格空方格1-C最多可增加101-D減少10v3-D增加103-C減少10v所以此改變後可獲得改進(jìn)解10090608011010+-+-空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-11090700供應(yīng)477112388810165450450100200150需求8090120160工廠2工廠3倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A運(yùn)輸模型最佳解測(cè)試.踏石法v所以此改變後可獲得改進(jìn)解之總成本v=10*7+90*1+90*3+110*8+80*8+70*5=2300v繼續(xù)評(píng)估空方格(1-A,1-B,2-A,2-D,3-B,3-C方格)看看是否有改進(jìn)之可能。

10、9080110109070空方格1-A1-B2-A2-D3-B3-C成本0+5+7+6+4+5n全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本均大於等於0n所以已經(jīng)是最佳解了。供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.修正分配法v修正分配法(Russel)v1.首先利用實(shí)方格找出每列及每行之指數(shù)指定第一列指數(shù)=0實(shí)方格成本=列指數(shù)+行指數(shù)10090608011010014412-47v2.找出每列及每行之指數(shù)後計(jì)算空方格之評(píng)估值空方格之評(píng)估值=空方格之成本-(列指數(shù)+行

11、指數(shù))供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.修正分配法v2.找出每列及每行之指數(shù)後計(jì)算空方格之評(píng)估值空方格之評(píng)估值=空方格之成本-(列指數(shù)+行指數(shù))10090608011010014412-47空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-1供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.修正分配法10090608011010014412-47空方格1-A1-B

12、1-C2-A2-D3-B成本00-5+12+11-1n空方格全部空方格全部評(píng)估之後若有成本均大於等於0表示此解以是最佳解n若有負(fù)成本表示，此解可發(fā)展出改良解n所以我們從最大負(fù)成本開(kāi)始改良n1-C最多可增加10 改良後，繼續(xù)評(píng)估空方格看看是否已經(jīng)是最佳解供應(yīng)477112388810165450450倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A100200150需求8090120160工廠2工廠3運(yùn)輸模型最佳解測(cè)試.修正分配法v空方格空方格1-C評(píng)估後成本降低最多v空方格空方格1-C最多可增加101-D減少10v3-D增加103-C減少10v所以此改變後可獲得改進(jìn)解10090608011010+-+-空方格1-

13、A1-B1-C2-A2-D3-B成本00-5+12+11-11090700供應(yīng)477112388810165450450100200150需求8090120160工廠2工廠3倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A運(yùn)輸模型最佳解測(cè)試.修正分配法v修正分配法v1.首先利用實(shí)方格找出每列及每行之指數(shù)指定第一列指數(shù)=0實(shí)方格成本=列指數(shù)+行指數(shù)90907080110014471210v2.找出每列及每行之指數(shù)後計(jì)算空方格之評(píng)估值空方格之評(píng)估值=空方格之成本-(列指數(shù)+行指數(shù))供應(yīng)477112388810165450450100200150需求8090120160工廠2工廠3倉(cāng)庫(kù)B倉(cāng)庫(kù)C倉(cāng)庫(kù)D工廠1倉(cāng)庫(kù)A運(yùn)輸模

14、型最佳解測(cè)試.修正分配法v2.找出每列及每行之指數(shù)後計(jì)算空方格之評(píng)估值空方格之評(píng)估值=空方格之成本-(列指數(shù)+行指數(shù))90907080110014471210空方格1-A1-B2-A2-D3-B3-C成本0+5+7+6+4+5n空方格全部空方格全部評(píng)估之後若有成本評(píng)估值均大於等於0表示此解以是最佳解n全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本評(píng)估值均大於等於0 所以已經(jīng)是最佳解了。特殊運(yùn)輸模型v並非所有運(yùn)輸問(wèn)題都可如上述問(wèn)題直接處理v若出現(xiàn)不規(guī)則性，在求解前必須作一些調(diào)整。v常見(jiàn)之不規(guī)則性有兩種v1.供需不平衡v2.退化解 實(shí)方格數(shù)不足，無(wú)法評(píng)估每個(gè)空方格通常用實(shí)方格數(shù)是

15、否等於R+C-1若實(shí)方格數(shù)R+C-1則有退化解特殊運(yùn)輸模型供需不平衡v供需不平衡時(shí)加入一虛擬行或列供應(yīng)5942200170100工廠2100倉(cāng)庫(kù)A倉(cāng)庫(kù)B需求8090工廠1供應(yīng)590420200200倉(cāng)庫(kù)A倉(cāng)庫(kù)B虛擬C工廠1100工廠2100需求80903030709010107070特殊運(yùn)輸模型供需不平衡v評(píng)估空方格1-B,2-C是否為最佳解供應(yīng)590420200200倉(cāng)庫(kù)A倉(cāng)庫(kù)B虛擬C工廠1100工廠2100需求80903030901070空方格1-B2-C成本+6+1n空方格全部空方格全部評(píng)估之後若有成本評(píng)估值均大於等於0表示此解以是最佳解n全部空方格(1-B,2-C)成本評(píng)估值均大於等於

16、0n所以已經(jīng)是最佳解了。特殊運(yùn)輸模型退化解v實(shí)方格=4個(gè)vR+C-1=3+3-1=5v因?yàn)閷?shí)方格數(shù)R+C-1v所以此解為退化解供應(yīng)325814776120120倉(cāng)庫(kù)A倉(cāng)庫(kù)B倉(cāng)庫(kù)C工廠140工廠260工廠320需求405030501040102020v解決方法,必須將一非常小之?dāng)?shù)量數(shù)量加入其中一個(gè)空方格內(nèi)v才能評(píng)估每個(gè)空方格v空方格全部空方格全部評(píng)估之後若所有成本均大於等於0表示此解以是最佳解v若有負(fù)成本表示，此解可發(fā)展出改良解特殊運(yùn)輸模型退化解v要如何將一非常小之?dāng)?shù)量數(shù)量加入其中一個(gè)空方格內(nèi)v才能評(píng)估每個(gè)空方格v原則為避免將原則為避免將放入評(píng)估路徑中有放入評(píng)估路徑中有- -號(hào)之號(hào)之空方格內(nèi)空方

17、格內(nèi)v且要能評(píng)估每個(gè)空方格供應(yīng)325814776120120倉(cāng)庫(kù)A倉(cāng)庫(kù)B倉(cāng)庫(kù)C工廠140工廠260工廠320需求40503050401020+供應(yīng)325814776120120倉(cāng)庫(kù)A倉(cāng)庫(kù)B倉(cāng)庫(kù)C工廠140工廠260工廠320需求405030特殊運(yùn)輸模型退化解v要如何將一非常小之?dāng)?shù)量數(shù)量加入其中一個(gè)空方格內(nèi)v才能評(píng)估每個(gè)空方格v原則為避免將原則為避免將放入評(píng)估路徑中有放入評(píng)估路徑中有- -號(hào)之號(hào)之空方格內(nèi)空方格內(nèi)v且要能評(píng)估每個(gè)空方格50401020+特殊運(yùn)輸模型退化解v要如何將一非常小之?dāng)?shù)量數(shù)量加入其中一個(gè)空方格內(nèi)v才能評(píng)估每個(gè)空方格v原則為避免將原則為避免將放入評(píng)估路徑中有放入評(píng)估路徑中有- -號(hào)之號(hào)之空方格內(nèi)