07 運(yùn)輸問(wèn)題數(shù)學(xué)模型

運(yùn)輸問(wèn)題

勤務(wù)指揮系部隊(duì)管理教研室教學(xué)內(nèi)容教學(xué)內(nèi)容運(yùn)輸問(wèn)題的模型及其特點(diǎn)求解運(yùn)輸問(wèn)題的表上作業(yè)法產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題

（一）運(yùn)輸問(wèn)題的數(shù)學(xué)模型講課提綱一、軍事案例實(shí)際軍事案例(油料運(yùn)輸規(guī)劃)：某團(tuán)野外駐訓(xùn)期間要從A1、A2兩個(gè)聯(lián)勤加油庫(kù)調(diào)送油料到B1、B2、B3三個(gè)駐訓(xùn)地。各油庫(kù)的儲(chǔ)存量、各駐訓(xùn)地的需求量以及從各油庫(kù)運(yùn)往各駐訓(xùn)地的單位油料的運(yùn)價(jià)如下表所示。問(wèn)題：如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?/p>

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200A2655300需求量150150200

一、軍事案例

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）數(shù)學(xué)模型：講課提綱二、運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型運(yùn)輸問(wèn)題（一般提法）：把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)撥到若干個(gè)銷(xiāo)地；已知:每個(gè)產(chǎn)地的供應(yīng)量、如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。如果運(yùn)輸問(wèn)題的總產(chǎn)量等于總銷(xiāo)量，則稱(chēng)運(yùn)輸問(wèn)題為產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題；反之，稱(chēng)產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題。每個(gè)銷(xiāo)地的需求量、各地之間的運(yùn)輸單價(jià)；什么是運(yùn)輸問(wèn)題：二、運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型已知有m個(gè)地點(diǎn)可以供應(yīng)某種物資(通稱(chēng)產(chǎn)地，用i=1,…,m表示)，有n個(gè)地點(diǎn)需要該種物資(通稱(chēng)銷(xiāo)地，用j=1,…,n表示)；m個(gè)產(chǎn)地的可供量(通稱(chēng)產(chǎn)量)為a1,a2,…am(可通寫(xiě)為ai)；n個(gè)銷(xiāo)地的需求量(通稱(chēng)銷(xiāo)量)b1,b2,…bn(可通寫(xiě)為bj)；從第i個(gè)產(chǎn)地到第j個(gè)銷(xiāo)地的單位物資運(yùn)價(jià)為cij。一般數(shù)學(xué)模型：二、運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型設(shè)xij為從第i個(gè)產(chǎn)地調(diào)運(yùn)給第j個(gè)銷(xiāo)地的物資的單位數(shù)量，那么產(chǎn)銷(xiāo)平衡的條件下，得到一般運(yùn)輸問(wèn)題的數(shù)學(xué)模型：產(chǎn)量約束銷(xiāo)量約束目標(biāo)：運(yùn)費(fèi)最小一般數(shù)學(xué)模型：二、運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題與一般線(xiàn)性規(guī)劃問(wèn)題的聯(lián)系：

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200A2655300需求量150150200

m個(gè)產(chǎn)地=2n個(gè)銷(xiāo)地=3二、運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型決策變量：約束方程：系數(shù)矩陣：基變量（秩）：產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題與線(xiàn)性規(guī)劃問(wèn)題的聯(lián)系：

m個(gè)產(chǎn)地=2n個(gè)銷(xiāo)地=3m×n個(gè)m+n個(gè)，且全部為等式約束每一個(gè)列向量中只有兩個(gè)元素是1，其余元素都是0m+n-1個(gè)講課提綱三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200→300A2655300需求量150150200600500

三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

≤300x21+x22+x23

≤300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646300A2655300需求量150150200三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

≤300x21+x22+x23

≤300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

+a1=300x21+x22+x23

+a2=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）,a1,a2≥0a1+a2=100三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0a1+0a2s.t.x11+x12+x13

+a1=300x21+x22+x23

+a2=300x11+

x21=150x12+x22=150x13+x23=200a1+a2=100xij≥0(i=1,2；j=1,2,3）,a1,a2≥0三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)【添加人工變量的物理意義】

駐地油庫(kù)B1B2B3B4存儲(chǔ)量A16460300A26550300需求量150150200100600600

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型等價(jià)轉(zhuǎn)換添加一個(gè)假想的需求地B4，令其需求量為產(chǎn)量過(guò)剩值，即產(chǎn)量-銷(xiāo)量。并令各油庫(kù)到B4的運(yùn)費(fèi)單價(jià)為0。為什么是0？只能是0嗎？產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)【添加人工變量的物理意義】

駐地油庫(kù)B1B2B3B4存儲(chǔ)量A16460300A26550300需求量150150200100600600三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型運(yùn)費(fèi)單價(jià)為只能是0嗎?產(chǎn)銷(xiāo)不平衡：產(chǎn)大于銷(xiāo)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）

駐地油庫(kù)B1B2B3B4存儲(chǔ)量A16460300A26550300需求量150150200100600600三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

≤

250x12+x22

≤

150x13+x23

≤200xij≥0(i=1,2；j=1,2,3）產(chǎn)銷(xiāo)不平衡：銷(xiāo)大于產(chǎn)

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200A2655300需求量250150200500600三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：銷(xiāo)大于產(chǎn)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0a1+0a2+0a3s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+a1=250x12+x22

+a2=150x13+x23

+a3=200a1+a2+a3=100xij≥0(i=1,2；j=1,2,3）,a1,a2≥0三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：銷(xiāo)大于產(chǎn)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x31+0x32+0x33s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+x31=250x12+x22

+x32=150x13+x23

+x33=200x31+x32+x33=100xij≥0(i=1,2,3；j=1,2,3）三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)銷(xiāo)不平衡：銷(xiāo)大于產(chǎn)【添加人工變量的物理意義】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x31+0x32+0x33s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+x31=250x12+x22

+x32=150x13+x23

+x33=200x31+x32+x33=100xij≥0(i=1,2,3；j=1,2,3）

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200A2655300A3000100需求量250150200600600三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型等價(jià)轉(zhuǎn)換添加一個(gè)假想的產(chǎn)地A3，令其產(chǎn)量為需求過(guò)剩值，即銷(xiāo)量-產(chǎn)量。并令A(yù)3到各駐地的運(yùn)費(fèi)單價(jià)為0。產(chǎn)銷(xiāo)不平衡：銷(xiāo)大于產(chǎn)【添加人工變量的物理意義】

駐地油庫(kù)B1B2B3存儲(chǔ)量A1646200A2655300A3000100需求量250150200600600三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型產(chǎn)量大于銷(xiāo)量：建立一個(gè)假想的需求地，并令其需求量為原問(wèn)題中總供應(yīng)量與總需求量的差值，令各供應(yīng)地到該需求地的運(yùn)輸單價(jià)為0，由此可把原問(wèn)題轉(zhuǎn)化成供求平衡的運(yùn)輸問(wèn)題。產(chǎn)量小于銷(xiāo)量：建立一個(gè)假想的供應(yīng)地，并令其供應(yīng)量為原問(wèn)題中總需求量與總供應(yīng)量的差值，令從該供應(yīng)地到各需求地的運(yùn)輸單價(jià)為0，由此可把原問(wèn)題轉(zhuǎn)化成供求平衡的運(yùn)輸問(wèn)題。經(jīng)驗(yàn)總結(jié)：三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型由于供不應(yīng)求，經(jīng)總部統(tǒng)籌安排決定： B1供應(yīng)量可減少0~300噸， B2必須全部滿(mǎn)足， B3供應(yīng)量不得少于1500噸。試求出總運(yùn)費(fèi)最低的調(diào)撥方案。試試這道題：

駐地油庫(kù)B1B2B3存儲(chǔ)量A11.801.701.554000A21.601.501.751500需求量30001000200055006000≥2700≥1500需要添加剩余變量！三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型試試這道題：

minz=1.8x11+1.7x12+1.55x13+1.6x21+1.5x22+1.75x23

s.t.x11+x12+x13=4000x21+x22+x23=1500x11+

x21

≥2700x11+

x21

≤3000x12+

x22=1000

x13+

x23

≥1500x13+

x23

≤2000xij≥0(i=1,2；j=1,2,3）x11+

x21

–s1=2700x13+

x23

–s2=1500標(biāo)準(zhǔn)化后，系數(shù)矩陣找不到單位陣，怎么辦？三、產(chǎn)銷(xiāo)不平衡的數(shù)學(xué)模型等價(jià)轉(zhuǎn)換添加一個(gè)假想的產(chǎn)地，令其需求量為產(chǎn)量過(guò)剩值，即產(chǎn)量-銷(xiāo)量。將駐地的需