07 運輸問題數(shù)學模型

運輸問題

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

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

駐地油庫B1B2B3存儲量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ù)學模型：講課提綱二、運輸問題的一般數(shù)學模型運輸問題（一般提法）：把某種產(chǎn)品從若干個產(chǎn)地調(diào)撥到若干個銷地；已知:每個產(chǎn)地的供應量、如何確定一個使得總的運輸費用最小的方案。如果運輸問題的總產(chǎn)量等于總銷量，則稱運輸問題為產(chǎn)銷平衡運輸問題；反之，稱產(chǎn)銷不平衡運輸問題。每個銷地的需求量、各地之間的運輸單價；什么是運輸問題：二、運輸問題的一般數(shù)學模型已知有m個地點可以供應某種物資(通稱產(chǎn)地，用i=1,…,m表示)，有n個地點需要該種物資(通稱銷地，用j=1,…,n表示)；m個產(chǎn)地的可供量(通稱產(chǎn)量)為a1,a2,…am(可通寫為ai)；n個銷地的需求量(通稱銷量)b1,b2,…bn(可通寫為bj)；從第i個產(chǎn)地到第j個銷地的單位物資運價為cij。一般數(shù)學模型：二、運輸問題的一般數(shù)學模型設xij為從第i個產(chǎn)地調(diào)運給第j個銷地的物資的單位數(shù)量，那么產(chǎn)銷平衡的條件下，得到一般運輸問題的數(shù)學模型：產(chǎn)量約束銷量約束目標：運費最小一般數(shù)學模型：二、運輸問題的一般數(shù)學模型產(chǎn)銷平衡運輸問題與一般線性規(guī)劃問題的聯(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）

駐地油庫B1B2B3存儲量A1646200A2655300需求量150150200

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

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

駐地油庫B1B2B3存儲量A1646200→300A2655300需求量150150200600500

三、產(chǎn)銷不平衡的數(shù)學模型

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)銷不平衡：產(chǎn)大于銷

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

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)銷不平衡：產(chǎn)大于銷

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)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：產(chǎn)大于銷【添加人工變量的物理意義】

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)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：產(chǎn)大于銷【添加人工變量的物理意義】

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)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：產(chǎn)大于銷【添加人工變量的物理意義】

駐地油庫B1B2B3B4存儲量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)銷不平衡的數(shù)學模型等價轉(zhuǎn)換添加一個假想的需求地B4，令其需求量為產(chǎn)量過剩值，即產(chǎn)量-銷量。并令各油庫到B4的運費單價為0。為什么是0？只能是0嗎？產(chǎn)銷不平衡：產(chǎn)大于銷【添加人工變量的物理意義】

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

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）

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

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)銷不平衡：銷大于產(chǎn)

駐地油庫B1B2B3存儲量A1646200A2655300需求量250150200500600三、產(chǎn)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：銷大于產(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)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：銷大于產(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)銷不平衡的數(shù)學模型產(chǎn)銷不平衡：銷大于產(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）

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

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

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

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標準化后，系數(shù)矩陣找不到單位陣，怎么辦？三、產(chǎn)銷不平衡的數(shù)學模型等價轉(zhuǎn)換添加一個假想的產(chǎn)地，令其需求量為產(chǎn)量過剩值，即產(chǎn)量-銷量。將駐地的需