Excel求解運輸問題的方法.ppt

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

2、調(diào)運可使總運輸費用最??？,解： 供需平衡問題-總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量（下標(biāo)i表示源，下標(biāo)j表示目的地），得到下列運輸量表：,解-設(shè),例1 供需平衡的運輸,目標(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. 運輸問題模型的一般形式,假設(shè) A1, A2,Am 表示某產(chǎn)品的m個產(chǎn)地；B1,B2,Bn 表示某產(chǎn)品的n個銷地；ai表示產(chǎn)地 Ai 的產(chǎn)量；bj 表示銷地 Bj 的銷量；cij 表示把產(chǎn)品從產(chǎn)地 Ai 運往銷地 Bj 的單位運價。問怎樣調(diào)運這些產(chǎn)品才能使總運費最小？ 如果 則稱該運輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡

4、。,運輸問題數(shù)據(jù)表,運輸問題決策變量表,設(shè) xij 為從產(chǎn)地 Ai 運往銷地 Bj 的運輸量，根據(jù)這個運輸問題的要求，可以建立運輸決策變量表。,運輸問題模型表格形式,產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型,例 2 運輸問題,例2 Big M公司在2個工廠生產(chǎn)一系列大型機器。產(chǎn)品之一是大型機床?，F(xiàn)收到3位顧客的訂單。這些機床會被單獨運送。下表給出了單位運輸成本、工廠產(chǎn)量和客戶的訂貨量。求費用最小的配送方案。,模 型,設(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.供需不平衡的運輸問題,例 3 供需不平衡的運輸問題,某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往銷地的單位運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？,3.供需不平衡的運輸問題,轉(zhuǎn)化為供需平衡,求解,產(chǎn)大于銷運輸問題的數(shù)學(xué)模型,例 4 供需不平衡的運輸問題,某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷

6、量和各產(chǎn)地運往銷地的單位運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？,轉(zhuǎn)化為供需平衡,銷大于產(chǎn)運輸問題的數(shù)學(xué)模型,例5 供需不平衡的運輸問題,某單位有3個生活區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，單位運價如表所示。 由于需大于供，經(jīng)研究決定1區(qū)供應(yīng)量最多可減少300噸，2區(qū)必須滿足需求量，3區(qū)供應(yīng)量不少于1500噸，試求總費用為最低的調(diào)運方案。,模 型,設(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求解,運輸問題線性規(guī)劃的一般模型,容量線路,如果從起點i到終點j的路線有容量Lij ，那么可以增加約束 xij = Mij 。 如果起點i不能向終點j送貨，則增加約束 xij = 0 。,例 6如果起點i不能向終點j送貨，則增加約束 xij = 0,生產(chǎn)能力、需求量和單位運輸費用等數(shù)據(jù)如下表所示。注意工廠3不能向需求4供貨。求解最佳配送方案。,例6 Excel 求解過程,例 7 轉(zhuǎn)運1,求解步驟：,1.

8、 問題轉(zhuǎn)化為表格。 2. 寫出目標(biāo)函數(shù)和約束。 3. 使用解題工具求解。,例7 求解,1.轉(zhuǎ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)運2,例8-1求解結(jié)果（f2r8）,1. 問題轉(zhuǎn)化為表格。 2.

9、 寫出目標(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求解過程,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