运输模型方案的评估

供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型方案的評估某公司有三座工廠均生產相同之產品。該公司另有四個倉庫存放這些產品。請問該公司應如何將三座工廠生產之產品分配到四個倉庫而使運輸之成本最低?從工廠1每期可供應量從工廠1到倉庫A之單位運輸成本倉庫A每期可儲存量每期總需求量每期總供應量運輸模型方案的評估運輸模型所具備之基本假設如下1.運送之貨物為同質之產品。2.不論運貨量多寡。每單位運輸成本皆相同3.各起站到各目的地運輸路線只有一條求解步驟1.求初始解2.最佳解測試3.改進次佳解求初始解之方法1.直覺最低成本法2.西北角法3.差額法(Vogel’sApproximationMethod)VAM又稱為懲罰法(PenaltyMethod)供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型求初始解運輸模型求初始解西北角法求解步驟1.由西北角方格開始2.將最大可行量分配給該方格，並劃掉該列或行或兩者3.繼續由西北角方格重覆步驟2。直到分配完畢80202070701301201010150150初始解之總成本=80*4+20*7+70*3+120*8+10*8+150*5=2460供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型求初始解運輸模型求初始解直覺最低成本法求解步驟1.找最低成本方格2.將最大可行量分配給該方格，並劃掉該列或行或兩者3.找次低成本方格重覆步驟2。直到分配完畢1006090110609080101101010供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型求初始解運輸模型求初始解差額法求解步驟1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)2.選擇差額最大之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。3.重覆步驟1。直到分配完畢行差額4414列差額353901105供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型求初始解運輸模型求初始解差額法求解步驟1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)2.選擇差額最大之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。3.重覆步驟1。直到分配完畢行差額414列差額30390110410060供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型求初始解運輸模型求初始解差額法求解步驟1.分別找每列及每行，最低成本與次低成本之差額(若相同差額=0)2.選擇差額最大之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。3.重覆步驟1。直到分配完畢行差額483列差額039011081006011010608010供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.初始解之總成本=100*1+90*3+110*8+80*8+10*16+60*5=2350運輸模型求初始解後最佳解測試需要評估每個未分配方格是否有改進之可能。評估之方法有兩種1.踏石法2.修正分配法10090608011010供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.踏石法空方格1-A評估若1-A增加一單位→1-D必須減少一單位1-D減少一單位→3-D必須增加一單位3-D增加一單位→3-A必須減少一單位是否採用方格1-A就要看成本是否有減少(+)=4+5=9(-)=1+8=910090608011010+-+-所以此改變對成本沒有影響，繼續評估空方格1-B,1-C,2-A,2-D,3-B看那個改變成本降低最多用踏石法建立封閉路徑時，必須選擇最少之實方格且實方格數必須等於行數+列數-1若實方格數行數+列數-1則該矩陣稱為退化供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.踏石法空方格1-B評估(+)=7+5+8=20(-)=1+16+3=20所以此改變對成本沒有影響，繼續評估空方格,1-C,2-A,2-D,3-B看那個改變成本降低最多10090608011010+-+-+-供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.踏石法空方格1-C評估(+)=7+5=12(-)=1+16=17所以此改變對成本會降低5，繼續評估空方格2-A,2-D,3-B看那個改變成本降低最多10090608011010+-+-供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.踏石法空方格全部評估之後若有成本均大於等於0表示此解以是最佳解若有負成本表示，此解可發展出改良解所以我們從最大負成本開始改良1-C最多可增加10改良後，繼續評估空方格看看是否已經是最佳解10090608011010+-+-空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-1供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.踏石法空方格1-C評估後成本降低最多空方格1-C最多可增加10→1-D減少103-D增加10→3-C減少10所以此改變後可獲得改進解10090608011010+-+-空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-11090700供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型最佳解測試.踏石法所以此改變後可獲得改進解之總成本=10*7+90*1+90*3+110*8+80*8+70*5=2300繼續評估空方格(1-A,1-B,2-A,2-D,3-B,3-C方格)看看是否有改進之可能。9080110109070空方格1-A1-B2-A2-D3-B3-C成本0+5+7+6+4+5全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本均大於等於0所以已經是最佳解了。供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.修正分配法修正分配法(Russel)1.首先利用實方格找出每列及每行之指數指定第一列指數=0實方格成本=列指數+行指數10090608011010014412-472.找出每列及每行之指數後計算空方格之評估值空方格之評估值=空方格之成本-(列指數+行指數)供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.修正分配法2.找出每列及每行之指數後計算空方格之評估值空方格之評估值=空方格之成本-(列指數+行指數)10090608011010014412-47空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-1供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.修正分配法10090608011010014412-47空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-1空方格全部評估之後若有成本均大於等於0表示此解以是最佳解若有負成本表示，此解可發展出改良解所以我們從最大負成本開始改良1-C最多可增加10改良後，繼續評估空方格看看是否已經是最佳解供應477112388810165450450倉庫B倉庫C倉庫D工廠1倉庫A100200150需求8090120160工廠2工廠3運輸模型最佳解測試.修正分配法空方格1-C評估後成本降低最多空方格1-C最多可增加10→1-D減少103-D增加10→3-C減少10所以此改變後可獲得改進解10090608011010+-+-空方格1-A1-B1-C2-A2-D3-B成本00-5+12+11-11090700供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型最佳解測試.修正分配法修正分配法1.首先利用實方格找出每列及每行之指數指定第一列指數=0實方格成本=列指數+行指數909070801100144712102.找出每列及每行之指數後計算空方格之評估值空方格之評估值=空方格之成本-(列指數+行指數)供應477112388810165450450100200150需求8090120160工廠2工廠3倉庫B倉庫C倉庫D工廠1倉庫A運輸模型最佳解測試.修正分配法2.找出每列及每行之指數後計算空方格之評估值空方格之評估值=空方格之成本-(列指數+行指數)90907080110014471210空方格1-A1-B2-A2-D3-B3-C成本0+5+7+6+4+5空方格全部評估之後若有成本評估值均大於等於0表示此解以是最佳解全部空方格(1-A,1-B,2-A,2-D,3-B,3-C)成本評估值均大於等於0所以已經是最佳解了。特殊運輸模型並非所有運輸問題都可如上述問題直接處理若出現不規則性，在求解前必須作一些調整。常見之不規則性有兩種1.供需不平衡2.退化解實方格數不足，無法評估每個空方格通常用實方格數是否等於R+C-1若實方格數R+C-1則有退化解特殊運輸模型─供需不平衡供需不平衡時加入一虛擬行或列供應5942200170100工廠2100倉庫A倉庫B需求8090工廠1供應590420200200倉庫A倉庫B虛擬C工廠1100工廠2100需求80903030709010107070特殊運輸模型─供需不平衡評估空方格1-B,2-C是否為最佳解供應590420200200倉庫A倉庫B虛擬C工廠1100工廠2100需求80903030901070空方格1-B2-C成本+6+1空方格全部評估之後若有成本評估值均大於等於0表示此解以是最佳解全部空方格(1-B,2-C)成本評估值均大於等於0所以已經是最佳解了。特殊運輸模型─退化解實方格=4個R+C-1=3+3-1=5因為實方格數R+C-1所以此解為退化解供應325814776120120倉庫A倉庫B倉庫C工廠140工廠260工廠320需求405030501040102020解決方法,必須將一非常小之數量ε加入其中一個空方格內才能評估每個空方格空方格全部評估之後若所有成本均大於等於0表示此解以是最佳解若有負成本表示，此解可發展出改良解特殊運輸模型─退化解要如何將一非常小之數量ε加入其中一個空方格內才能評估每個空方格原則為避免將ε放入評估路徑中有-號之空方格內且要能評估每個空方格供應325814776120120倉庫A倉庫B倉庫C工廠140工廠260工廠320需求40503050401020ε+供應32581477