1、 運(yùn)輸問題的建模與優(yōu)化TITLE中央財(cái)經(jīng)大學(xué) 信息學(xué)院吳 靖 運(yù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ǎng)絡(luò)圖 已知： 供應(yīng)地點(diǎn)供應(yīng)量 需求地點(diǎn)需求量 從供應(yīng)地點(diǎn)到需求地點(diǎn)的單位運(yùn)輸成本運(yùn)輸成本最小？例1 供需平衡的運(yùn)輸問題產(chǎn)地銷 地產(chǎn)量B1B2B3A1646200A2655300銷量150150200 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)

2、量、各銷地的銷量和各產(chǎn)地分別運(yùn)往各銷地的單位運(yùn)費(fèi)如下表所示。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？解： 供需平衡問題-總產(chǎn)量 = 總銷量設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量（下標(biāo)i表示源，下標(biāo)j表示目的地），得到下列運(yùn)輸量表：解-設(shè)產(chǎn)地銷 地產(chǎn)量B1B2B3A1X11X12X13200A2X21X22X23300銷量150150200模 型目標(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

3、x13 + x23 = 200 xij0(i=1、2；j=1、2、3）決策結(jié)果配送方案 銷地產(chǎn)地B1 B2 Bn產(chǎn)量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmna1 a2 am銷量b1 b2 bn運(yùn)輸問題數(shù)據(jù)表運(yùn)輸問題決策變量表 銷地產(chǎn)地B1 B2 Bn產(chǎn)量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmna1 a2 am銷量b1 b2 bn 設(shè) xij 為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問題的要求，可以建立運(yùn)輸決策變量表。運(yùn)輸問題模型表格形式 銷地產(chǎn)地B1B2Bn產(chǎn)量A1 c11x11 c12 x1

4、2 c1n x1na1 A2 c21 x21 c22 x22 c2n x2na2 Am cm1 xm1 cm2 xm2 cmn xmnam銷量b1b2bn例 2 運(yùn)輸問題Shipping CostFactoryCustomer1Customer2Customer3Outputf1 700.00 900.00 800.00 12f2 800.00 900.00 700.00 15Order Size1089例2 Big M公司在2個(gè)工廠生產(chǎn)一系列大型機(jī)器。產(chǎn)品之一是大型機(jī)床。現(xiàn)收到3位顧客的訂單。這些機(jī)床會(huì)被單獨(dú)運(yùn)送。下表給出了單位運(yùn)輸成本、工廠產(chǎn)量和客戶的訂貨量。求費(fèi)用最小的配送方案。模 型設(shè)

5、：xij 為工廠到客戶的配送量目標(biāo)函數(shù)：z=700 x11+900 x12+800 x13 +800 x21+900 x22+700 x23 s.t. X11 + x21 + x31 = 12 x21 + x22 + x23 = 15 x11 + x21 = 10 x12 + x22 = 8 x13 + x23 = 9 xij = 0模型的Excel描述：3.供需不平衡的運(yùn)輸問題例 3 供需不平衡的運(yùn)輸問題產(chǎn)地銷 地產(chǎn)量B1B2B3A1646300A2655300銷量150150200 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往銷地的單

6、位運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？3.供需不平衡的運(yùn)輸問題轉(zhuǎn)化為供需平衡轉(zhuǎn)化：產(chǎn)銷平衡產(chǎn)地銷 地產(chǎn)量B1B2B3B4A16460300A26550300銷量150150200100求解轉(zhuǎn)化：產(chǎn)銷平衡產(chǎn)地銷 地產(chǎn)量B1B2B3B4A16460300A26550300銷量150150200100產(chǎn)地銷 地產(chǎn)量B1B2B3B4A1x11x12x13x14300A2x21x22x23x24300銷量150150200100求解運(yùn)輸方案產(chǎn)地銷 地產(chǎn)量B1B2B3B4A115015000300=300A200200100300=300供應(yīng)量150150200100=運(yùn)輸費(fèi)用銷量15015

7、02001002500產(chǎn)大于銷運(yùn)輸問題的數(shù)學(xué)模型例 4 供需不平衡的運(yùn)輸問題產(chǎn)地銷 地產(chǎn)量B1B2B3A1646200A2655300銷量250200200 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往銷地的單位運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？銷大于產(chǎn)運(yùn)輸問題的數(shù)學(xué)模型例5 供需不平衡的運(yùn)輸問題銷 地 及 單 位 運(yùn) 費(fèi)產(chǎn)地1區(qū)2區(qū)3區(qū)產(chǎn)量山西盂縣1.81.71.554000河北臨城1.61.51.751500需求量300010002000 某單位有3個(gè)生活區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、

8、山西盂縣兩處煤礦負(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)方案。目標(biāo)函數(shù)：H18：=SUMPRODUCT(C6:E7,C13:E14)約束：F13：=SUM(C13:E13)F14：=SUM(C14:E14)C17：=SUM(C13:C14)D17：=SUM(D13:D14)E17：=SUM(E13:E14)例5 EXCEL求解運(yùn)輸問題線性規(guī)劃的一般模型容量線路 如果從起點(diǎn)i到終點(diǎn)j的路線有容量Lij ，那么可以增加約束 xij =

9、 Mij 。 如果起點(diǎn)i不能向終點(diǎn)j送貨，則增加約束 xij = 0 。 例 6如果起點(diǎn)i不能向終點(diǎn)j送貨，則增加約束 Xij = 0生產(chǎn)廠需求1 需求2需求3需求4產(chǎn)量F11613221750F21413191560F3192023-50最低需求量3070010最高需求量507030不限生產(chǎn)能力、需求量和單位運(yùn)輸費(fèi)用等數(shù)據(jù)如下表所示。注意工廠3不能向需求4供貨。求解最佳配送方案。例6 EXCEL 求解過程例 7 轉(zhuǎn)運(yùn)11h4f1h3R5R6R7233f226364465R8600400200150350300求解步驟：1. 問題轉(zhuǎn)化為表格。2. 寫出目標(biāo)函數(shù)和約束。3. 使用解題工具求解。例

10、7 求解1.轉(zhuǎn)運(yùn)站的輸入=輸出2.所有不可配送單元格=0目標(biāo)函數(shù)：K15：=SUMPRODUCT(C2:H5,C9:H12)約束： I9：=C9+D9I10：=C10+D10I11：=SUM(E11:H11)I12：=SUM(E12:H12)C13：=C9+C10D13：=D9+D10E13：=E11+E12F13：=F11+F12G13：=G11+G12H13：=H11+H12C11:D12=0E9:H10=0例 8 轉(zhuǎn)運(yùn)2例8-1求解結(jié)果（F2R8）1. 問題轉(zhuǎn)化為表格。2. 寫出目標(biāo)函數(shù)和約束。3. 使用解題工具求解。EXCEL求解目標(biāo)函數(shù)：K15：=SUMPRODUCT(C2:H5,C

11、9:H12)約束： I9：=C9+D9I10：=C10+D10+H10I11：=SUM(E11:H11)I12：=SUM(E12:H12)C13：=C9+C10D13：=D9+D10E13：=E11+E12F13：=F11+F12G13：=G11+G12H13：=H10+H11+H12C11:D12=0E9:H9=0E10:G10=0F2向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：=H14C15：=SUM(C10:C11)D15：=SUM(D10:D11)E15：=SUM(E10:E14)F15：=SUM(F10:F14)G15：=SUM(G10:G14)-I14H15：=SUM(H10:H14)E10：H10=0E11：G11=0C12：D14=0E14：G14=