运输模型方案的评估

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,運輸模型,方案的評估,某公司有三座工廠均生產相同之產品。該公司另有四個倉庫存放這些產品。請問該公司應如何將,三座工廠,生產之產品分配到四個倉庫而使運輸之成本最低?,從,工廠1,每期可供應量,從,工廠1,到,倉庫,A,之單位運輸成本,倉庫,A,每期可儲存量,每期總需求量,每期總供應量,1,運輸模型,方案的評估,運輸模型所具備之基本假設如下,1.運送之貨物為同質之產品。,2.不論運貨量多寡。每單位運輸成本皆相同,3.各起站到各目的地運輸路線只有一條,求解步驟,1.求初始解,2.最佳解測試,3.改進次佳解,求初始解之方法,1.直覺最低成本法,2.西北角法,3.差額法(,Vogels Approximation Method)VAM,又稱為懲罰法(,Penalty Method),2,運輸模型,求初始解,運輸模型,求初始解,西北角法,求解步驟,1.由西北角方格開始,2.將最大可行量分配給該方格，並劃掉該列或行或兩者,3.繼續由西北角方格重覆步驟2。直到分配完畢,80,20,20,70,70,130,120,10,10,150,150,初始解之總成本,=,80*4+20*7+70*3+120*8+10*8+150*5=2460,3,運輸模型,求初始解,運輸模型,求初始解,直覺最低成本法,求解步驟,1.找最低成本方格,2.將最大可行量分配給該方格，並劃掉該列或行或兩者,3.找次低成本方格重覆步驟2。直到分配完畢,100,60,90,110,60,90,80,10,110,10,10,4,運輸模型,求初始解,運輸模型求初始解差額法求解步驟,1.分別找每列及每行，最低成本與次低成本之差額(,若相同差額=0,),2.選擇,差額最大,之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。,3.重覆步驟1。直到分配完畢,行差額,4,4,1,4,列差額,3,5,3,90,110,5,5,運輸模型,求初始解,運輸模型求初始解差額法求解步驟,1.分別找每列及每行，最低成本與次低成本之差額(,若相同差額=0,),2.選擇,差額最大,之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。,3.重覆步驟1。直到分配完畢,行差額,4,1,4,列差額,3,0,3,90,110,4,100,60,6,運輸模型,求初始解,運輸模型求初始解差額法求解步驟,1.分別找每列及每行，最低成本與次低成本之差額(,若相同差額=0,),2.選擇,差額最大,之行或列中方格成本最低者優先分配，並劃掉該列或行或兩者。,3.重覆步驟1。直到分配完畢,行差額,4,8,3,列差額,0,3,90,110,8,100,60,110,10,60,80,10,7,運輸模型,最佳解測試.,初始解之總成本,=100*1+90*3+110*8+80*8+10*16+60*5=2350,運輸模型,求初始解後最佳解測試,需要評估每個未分配方格是否有改進之可能。評估之方法有兩種,1.,踏石法,2.,修正分配法,100,90,60,80,110,10,8,運輸模型,最佳解測試,.,踏石法,空方格,1-,A,評估,若1-,A,增加一單位1-,D,必須減少一單位,1-,D,減少一單位3-,D,必須增加一單位,3-,D,增加一單位3-,A,必須減少一單位,是否採用,方格,1-,A,就要看成本是否有減少,(+)=4+5=9,(-)=1+8=9,100,90,60,80,110,10,+,-,+,-,所以此改變對成本沒有影響,，,繼續評估,空方格,1-B,1-C,2-A,2-D,3-B,看那個改變成本降低最多,用踏石法建立封閉路徑時，必須選擇最少之,實方格,且實方格數,必須等於,行數+列數-1,若實方格數,行數+列數-1則該矩陣稱為,退化,9,運輸模型,最佳解測試.,踏石法,空方格,1-,B,評估,(+)=7+5+8=20,(-)=1+16+3=20,所以此改變對成本沒有影響,，,繼續評估空方格,1-C,2-A,2-D,3-B,看那個改變成本降低最多,100,90,60,80,110,10,+,-,+,-,+,-,10,運輸模型,最佳解測試.,踏石法,空方格,1-,C,評估,(+)=7+5=12,(-)=1+16=17,所以此改變對成本會,降低5,，,繼續評估,空方格,2-A,2-D,3-B,看那個改變成本降低最多,100,90,60,80,110,10,+,-,+,-,11,運輸模型,最佳解測試,.,踏石法,空方格全部,評估之後若有成本均大於等於0表示此解以是最佳解,若有,負,成本表示，此解可發展出改良解,所以我們從最大負成本開始改良,1-,C,最多可增加10,改良後,，,繼續評估空方格看看是否已經是最佳解,100,90,60,80,110,10,+,-,+,-,12,運輸模型,最佳解測試.,踏石法,空方格,1-,C,評估後成本降低最多,空方格,1-,C,最多可增加101-,D,減少10,3-,D,增加103-,C,減少10,所以此改變後可獲得改進解,100,90,60,80,110,10,+,-,+,-,10,90,70,0,13,運輸模型,最佳解測試.,踏石法,所以此改變後可獲得改進解之總成本,=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,方格)看看是否有改進之可能。,90,80,110,10,90,70,全部空方格(1-,A,1-B,2-A,2-D,3-B,3-C,)成本均大於等於0,所以已經是最佳解了。,14,運輸模型,最佳解測試.,修正分配法,修正分配法(,Russel),1,.首先利用,實方格,找出每列及每行之指數,指定,第一列指數,=0,實方格成本=列指數+行指數,100,90,60,80,110,10,0,1,4,4,12,-4,7,2.,找出每列及每行之指數,後計算空方格之評估值,空方格之評估值,=空方格之成本-(列指數+行指數),15,運輸模型,最佳解測試.,修正分配法,2.,找出每列及每行之指數,後計算空方格之評估值,空方格之評估值=空方格之,成本-(列指數+行指數),100,90,60,80,110,10,0,1,4,4,12,-4,7,16,運輸模型,最佳解測試.,修正分配法,100,90,60,80,110,10,0,1,4,4,12,-4,7,空方格全部,評估之後若有成本均大於等於0表示此解以是最佳解,若有,負,成本表示，此解可發展出改良解,所以我們從最大負成本開始改良,1-,C,最多可增加10 改良後，,繼續評估,空方格看看是否已經是最佳解,17,運輸模型,最佳解測試.,修正分配法,空方格,1-,C,評估後成本降低最多,空方格,1-,C,最多可增加101-,D,減少10,3-,D,增加103-,C,減少10,所以此改變後可獲得改進解,100,90,60,80,110,10,+,-,+,-,10,90,70,0,18,運輸模型,最佳解測試.,修正分配法,修正分配法,1.首先利用,實方格,找出每列及每行之指數,指定,第一列指數,=0,實方格成本=列指數+行指數,90,90,70,80,110,0,1,4,4,7,1,2,10,2.,找出每列及每行之指數,後計算空方格之評估值,空方格之評估值,=空方格之,成本-(列指數+行指數),19,運輸模型,最佳解測試.,修正分配法,2.,找出每列及每行之指數,後計算空方格之評估值,空方格之評估值=空方格之成本-(列指數+行指數),90,90,70,80,110,0,1,4,4,7,1,2,10,空方格全部,評估之後若有成本,評估值,均大於等於0表示此解以是最佳解,全部空方格(1-,A,1-B,2-A,2-D,3-B,3-C,)成本,評估值,均大於等於0 所以已經是最佳解了。,20,特殊運輸模型,並非所有運輸問題都可如上述問題直接處理,若出現不規則性，在求解前必須作一些調整。,常見之不規則性有兩種,1.供需不平衡,2.退化解,實方格數不足，無法評估每個空方格,通常用實方格數是否等於,R+C-1,若實方格數,R+C-1,則有退化解,21,特殊運輸模型供需不平衡,供需不平衡時加入一虛擬行或列,30,70,90,10,10,70,70,22,特殊運輸模型供需不平衡,評估空方格1-,B,2-C,是否為最佳解,30,90,10,70,空方格全部,評估之後若有成本,評估值,均大於等於0表示此解以是最佳解,全部空方格(1-,B,2-C,)成本,評估值,均大於等於0,所以已經是最佳解了。,23,特殊運輸模型退化解,實方格=4個,R+C-1=3+3-1=5,因為實方格數,R+C-1,所以此解為退化解,50,10,40,10,20,20,解決方法,必須將一非常小之,數量,加入其中一個空方格內,才能評估每個空方格,空方格全部,評估之後若所有成本均大於等於0表示此解以是最佳解,若有,負,成本表示，此解可發展出改良解,24,特殊運輸模型退化解,要如何將一非常小之,數量,加入其中一個空方格內,才能評估每個空方格,原則為避免將,放入評估路徑中有-號之,空方格內,且要能評估每個空方格,50,40,10,20,+,25,特殊運輸模型退化解,要如何將一非常小之,數量,加入其中一個空方格內,才能評估每個空方格,原則為避免將,放入評估路徑中有-號之,空方格內,且要能評估每個空方格,50,40,10,20,+,26,特殊運輸模型退化解,要如何將一非常小之,數量,加入其中一個空方格內,才能評估每個空方格,原則為避免將,放入評估路徑中有-號之,空方格內,且要能評估每個空方格,50,40,10,20,27,特殊運輸模型退化解,50,40,10,20,空方格全部,評估之後若有成本,評估值,均大於等於0表示此解以是最佳解,所以已經是最佳解了。,總成本=,40*3+50*1+10*4+20*6+0*7=330,28,