Excel求解運(yùn)輸問(wèn)題的方法.ppt

1、運(yùn)輸問(wèn)題的建模與優(yōu)化,title,中央財(cái)經(jīng)大學(xué) 信息學(xué)院吳 靖,運(yùn)輸問(wèn)題建模和優(yōu)化,在供應(yīng)鏈管理中，運(yùn)輸是一項(xiàng)重要環(huán)節(jié)，包括：原材料生產(chǎn)商，生產(chǎn)商倉(cāng)庫(kù)，倉(cāng)庫(kù)零售商 在運(yùn)輸環(huán)節(jié)中，如何進(jìn)行優(yōu)化安排，降低成本，是供應(yīng)鏈管理中的一項(xiàng)重要內(nèi)容。 要素： 供應(yīng)地點(diǎn)供應(yīng)量 需求地點(diǎn)需求量 從供應(yīng)地點(diǎn)到需求地點(diǎn)的單位運(yùn)輸成本,1. 簡(jiǎn)單運(yùn)輸問(wèn)題網(wǎng)絡(luò)圖,已知： 供應(yīng)地點(diǎn)供應(yīng)量 需求地點(diǎn)需求量 從供應(yīng)地點(diǎn)到需求地點(diǎn)的單位運(yùn)輸成本,運(yùn)輸成本最??？,例1 供需平衡的運(yùn)輸問(wèn)題,某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地分別運(yùn)往各銷地的單位運(yùn)費(fèi)如下表所示。問(wèn)：應(yīng)如何

2、調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,解： 供需平衡問(wèn)題-總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量（下標(biāo)i表示源，下標(biāo)j表示目的地），得到下列運(yùn)輸量表：,解-設(shè),例1 供需平衡的運(yùn)輸,目標(biāo)函數(shù)：Min z= 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0(i=1、2；j=1、2、3）,模 型,目標(biāo)函數(shù)： Min z= 6x11+ 4x12+ 6x13+ 6x21+

3、 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0(i=1、2；j=1、2、3）,決策結(jié)果配送方案,2. 運(yùn)輸問(wèn)題模型的一般形式,假設(shè) A1, A2,Am 表示某產(chǎn)品的m個(gè)產(chǎn)地；B1,B2,Bn 表示某產(chǎn)品的n個(gè)銷地；ai表示產(chǎn)地 Ai 的產(chǎn)量；bj 表示銷地 Bj 的銷量；cij 表示把產(chǎn)品從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的單位運(yùn)價(jià)。問(wèn)怎樣調(diào)運(yùn)這些產(chǎn)品才能使總運(yùn)費(fèi)最??？ 如果 則稱該運(yùn)輸問(wèn)題為產(chǎn)銷平衡問(wèn)題；否則，稱產(chǎn)銷不平衡

4、。,運(yùn)輸問(wèn)題數(shù)據(jù)表,運(yùn)輸問(wèn)題決策變量表,設(shè) xij 為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸決策變量表。,運(yùn)輸問(wèn)題模型表格形式,產(chǎn)銷平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型,例 2 運(yùn)輸問(wèn)題,例2 Big M公司在2個(gè)工廠生產(chǎn)一系列大型機(jī)器。產(chǎn)品之一是大型機(jī)床?，F(xiàn)收到3位顧客的訂單。這些機(jī)床會(huì)被單獨(dú)運(yùn)送。下表給出了單位運(yùn)輸成本、工廠產(chǎn)量和客戶的訂貨量。求費(fèi)用最小的配送方案。,模 型,設(shè)：xij 為工廠到客戶的配送量 目標(biāo)函數(shù)：z=700 x11+900 x12+800 x13 +800 x21+900 x22+700 x23 s.t. X11 + x21 + x31 = 1

5、2 x21 + x22 + x23 = 15 x11 + x21 = 10 x12 + x22 = 8 x13 + x23 = 9 xij = 0,模型的Excel描述：,Excel 求解,3.供需不平衡的運(yùn)輸問(wèn)題,例 3 供需不平衡的運(yùn)輸問(wèn)題,某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往銷地的單位運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,3.供需不平衡的運(yùn)輸問(wèn)題,轉(zhuǎn)化為供需平衡,求解,產(chǎn)大于銷運(yùn)輸問(wèn)題的數(shù)學(xué)模型,例 4 供需不平衡的運(yùn)輸問(wèn)題,某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷

6、量和各產(chǎn)地運(yùn)往銷地的單位運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？,轉(zhuǎn)化為供需平衡,銷大于產(chǎn)運(yùn)輸問(wèn)題的數(shù)學(xué)模型,例5 供需不平衡的運(yùn)輸問(wèn)題,某單位有3個(gè)生活區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，單位運(yùn)價(jià)如表所示。 由于需大于供，經(jīng)研究決定1區(qū)供應(yīng)量最多可減少300噸，2區(qū)必須滿足需求量，3區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。,模 型,設(shè)： 目標(biāo)函數(shù)： s.t. Excel求解結(jié)果：,目標(biāo)函數(shù)： H18：=SUMPRODUCT(C6:E7,C13:E14) 約束： F

7、13：=SUM(C13:E13) F14：=SUM(C14:E14) C17：=SUM(C13:C14) D17：=SUM(D13:D14) E17：=SUM(E13:E14),例5 Excel求解,運(yùn)輸問(wèn)題線性規(guī)劃的一般模型,容量線路,如果從起點(diǎn)i到終點(diǎn)j的路線有容量Lij ，那么可以增加約束 xij = Mij 。 如果起點(diǎn)i不能向終點(diǎn)j送貨，則增加約束 xij = 0 。,例 6如果起點(diǎn)i不能向終點(diǎn)j送貨，則增加約束 xij = 0,生產(chǎn)能力、需求量和單位運(yùn)輸費(fèi)用等數(shù)據(jù)如下表所示。注意工廠3不能向需求4供貨。求解最佳配送方案。,例6 Excel 求解過(guò)程,例 7 轉(zhuǎn)運(yùn)1,求解步驟：,1.

8、 問(wèn)題轉(zhuǎn)化為表格。 2. 寫(xiě)出目標(biāo)函數(shù)和約束。 3. 使用解題工具求解。,例7 求解,1.轉(zhuǎn)運(yùn)站的輸入=輸出 2.所有不可配送單元格=0,目標(biāo)函數(shù)： K15：=SUMPRODUCT(C2:H5,C9:H12) 約束： I9：=C9+D9 I10：=C10+D10 I11：=SUM(E11:H11) I12：=SUM(E12:H12) C13：=C9+C10 D13：=D9+D10 E13：=E11+E12 F13：=F11+F12 G13：=G11+G12 H13：=H11+H12 C11:D12=0 E9:H10=0,例 8 轉(zhuǎn)運(yùn)2,例8-1求解結(jié)果（f2r8）,1. 問(wèn)題轉(zhuǎn)化為表格。 2.

9、 寫(xiě)出目標(biāo)函數(shù)和約束。 3. 使用解題工具求解。,Excel求解,目標(biāo)函數(shù)： K15：=SUMPRODUCT(C2:H5,C9:H12) 約束： I9：=C9+D9 I10：=C10+D10+H10 I11：=SUM(E11:H11) I12：=SUM(E12:H12) C13：=C9+C10 D13：=D9+D10 E13：=E11+E12 F13：=F11+F12 G13：=G11+G12 H13：=H10+H11+H12 C11:D12=0 E9:H9=0 E10:G10=0,F2向R8送貨,Excel求解過(guò)程,Excel公式： K16：=SUMPRODUCT(C2:H6,C10:H14) I10：=SUM(C10:H10) I11：=SUM(C11:H11) I12: =SUM(C12:H12) I13: =SUM(C13:H13) I14：=H14 C15：=SUM(C10:C11) D15：=SUM(D10:D11) E15：=SUM(E10:E14) F15：=SUM(F10:F14) G15：=SUM(G10:G14)-I14 H15：=SUM(H10:H14) E10：H10=0 E11：G11=0