管理運籌學(xué)-第三章運輸問題

1、第三章 運輸問題,北京物資學(xué)院信息學(xué)院2017年4月,北京物資學(xué)院運籌學(xué)教學(xué)課件,本章主要內(nèi)容,第一節(jié) 運輸問題的數(shù)學(xué)模型及其特征第二節(jié) 運輸問題的求解—表上作業(yè)法第三節(jié) 產(chǎn)銷不平衡的運輸問題及應(yīng)用,第一節(jié) 運輸問題的數(shù)學(xué)模型及其特征,運輸問題的定義 運輸問題的數(shù)學(xué)模型 運輸問題的特征,,1. 運輸問題的定義,例1： 某集團新購進一批鋼材，分別存儲在三個倉庫，現(xiàn)在要將這批鋼材運到分布在各地的四個工廠。各倉庫的庫存量、各工廠的

2、需求量以及從各倉庫往各個工廠每運送一噸鋼材所需的費用見下表，問如何調(diào)運才能使總運費降到最低？,運輸問題：有m個供應(yīng)點向n個需求點供應(yīng)某種物資，這m個供應(yīng)點A1、A2、…...Am的供應(yīng)量分別為a1、a2、…...am；n個需求點B1、B2、…...Bn的需求量分別為b1、b2、…...bn；已知從任一供應(yīng)點Ai向任一需求點Bj運輸一個單位物資的費用為cij。問采取什么樣的物資調(diào)運方案才能使總運費最省？,,,2. 運輸問題的數(shù)學(xué)模型,,,

3、,運輸問題的約束方程組系數(shù)矩陣及特征,矩陣A是一個m+n行mn列的矩陣，它的秩為m+n-1。運輸問題應(yīng)該有m+n-1個基變量。系數(shù)矩陣非常稀疏。 xij的系數(shù)列向量為：,,3. 運輸問題的特征,特征1：運輸問題一定有可行解；特征2：運輸問題一定有最優(yōu)解；特征3：運輸問題每一組基對應(yīng) m+n-1個基變量；特征4：運輸問題的 m+n-1個基變量構(gòu)成的變量組不含閉回路；特征5：任意一個非基變量和 m+n-1個基變量組成的變量組中

4、必定存在一條并且只存在唯一一條閉回路； 特征6：如果運輸問題中的供應(yīng)量和需求量都是整數(shù)，則任一基解中各變量的取值也都是整數(shù)。,,閉回路,,定義：凡是能夠排列成下列序列的一組變量的集合就稱為運輸問題的一個閉回路。,并稱集合中每一個變量為此閉回路的一個頂點；稱連接相鄰兩個變量（頂點）以及連接最后一個頂點和第一個頂點的線段為此閉回路的邊。,或,X45,,X41,,X31,,X33,,X13,,X15,,X34,,X32,,,X14,,X12

5、,X35,,X41,X31,,X43,,X13,,X15,,,X11,,X12,,X22,,X24,,X44,,X42,X21,（1）每個頂點都是轉(zhuǎn)折點；（2）閉回路是一條閉合的折線，每一條邊都是水平或垂直的；（3）閉回路上同一行（列）的頂點有偶數(shù)個。,,,閉回路上的點對應(yīng)的系數(shù)列向量線性相關(guān)。,,,Pij,,,,,Pik,Plk,Pls,Pus,Puj,由于,容易證明,,第二節(jié) 運輸問題的求解--表上作業(yè)法,第四步：確定進基變量和

6、出基變量，調(diào)整非最優(yōu)的調(diào)運方案，獲得更好的調(diào)運方案；轉(zhuǎn)第二步。,表上作業(yè)法的基本步驟：,第一步：編制初始調(diào)運方案，即尋找第一個基可行解；,第二步：計算各非基變量的檢驗數(shù)；,,第三步：判斷當(dāng)前的調(diào)運方案是否是最優(yōu)方案，如果已經(jīng)是最優(yōu)，則算法結(jié)束，問題已經(jīng)解決；否則，轉(zhuǎn)第四步；,,第一步：編制初始調(diào)運方案,要求得運輸問題的初始基可行解，必須保證找到 m+n–1 個基變量.,運輸問題的任意m+n-1個變量構(gòu)成一組基變量的充要條件是變量組中不含

7、閉回路.關(guān)鍵:找出m+n-1個不含閉回路的變量。,西北角法（左上角法）最小元素法Vogel 法,問題：如何使得一個選定的變量不包含在閉回路中？,對應(yīng)的總運費為 z 1= 2×3 + 9×6 + 3×2 + 4×3 + 2×1 + 5×6 = 110,,,,,,,西北角法(左上角法),,最小元素法,對應(yīng)的總運費為 z 2= 9×5 + 7×4 +

8、 1×3 + 2×2 + 4×3 + 2×4 = 100,,,,,,,,,Vogel 法,對應(yīng)的總運費為 z 3= 2×3 + 9×5 + 7×1 + 2×5 + 4×3 + 2×4 =88,,,,,,,,,,,,,,退化情況的處理,用西北角法求下列運輸問題的第一個基可行解,,,,,,注意：每次只能劃去一行或一列，不能同時劃去行和列。

9、當(dāng)只剩下一行（列）時，只能劃去列（行）。想一想：為什么？,,用最小元素法求下列運輸問題的第一個基可行解,第二步：計算各非基變量的檢驗數(shù),1. 閉回路法；2. 位勢法。,檢驗數(shù)的定義：非基變量的取值每增加1時，總運費的 增加量。運輸問題的最優(yōu)性條件：檢驗數(shù)非負,1. 閉回路法,,基變量不含閉回路，但任何一個非基變量都可以與基變量構(gòu)成唯一一條閉回路,,,,,,,含義：x14 每增加一個單位，總運費增加-6個單位,+1,+1,+

10、1,-1,-1,-1,所有非基變量的檢驗數(shù)見上表,,2. 位勢法,位勢：運輸問題的對偶變量稱為位勢。因為m個供應(yīng)點n個需求點的運輸問題有m+n個約束，因此運輸問題就有m+n個位勢。,,行位勢:關(guān)于供應(yīng)點Ai的約束對應(yīng)的對偶變量，記為 ui, i=1,2,…m。列位勢:關(guān)于需求點Bj的約束對應(yīng)的對偶變量，記為vj, j = 1,2,…,n。,定理：運輸問題變量xij的檢驗數(shù),證明：,位勢及檢驗數(shù)的求法,由于基變量的檢驗

11、數(shù)為0，所以可以利用m+n-1 個基變量求出位勢,,,0,2,9,-6,10,-8,13,0,-6,,5,-5,14,3,第四步：調(diào)整調(diào)運方案,1. 確定進基變量：選取最小負檢驗數(shù)對應(yīng)的非基變量進基,2. 確定出基變量和調(diào)整量,將進基變量對應(yīng)的閉回路中的頂點分為奇頂點和偶頂點，令θ= min{ 閉回路上所有偶頂點對應(yīng)的運量xij } 則θ即為調(diào)整量，選取一個運量等于θ的偶頂點為出基變量。,3.調(diào)整：閉回路上奇頂點上的運量增加θ，偶頂點

12、上的運量減少θ。閉回路以外頂點的運量不變。,上例中：若選x14進基，則?=min{6,3,6}=3, 出基變量為x23,調(diào)整后得：,,,,,,,總運費： z= 2×3 + 9×3 + 7×3 + 3×5 + 2×4 + 5×3 = 92 < 110,,x32進基，則?=min{3,3}=3, 出基變量選x34,調(diào)整后得：,0,-6,-2,2,9,4,7,5,6,6,1,

13、8,-3,,,,,檢驗數(shù)全部非負，已經(jīng)是最優(yōu)調(diào)運方案；總費用z*= 2×3 + 9×0 + 7×6 + 3×5 + 4×3 + 2×4 = 83,0,-6,-5,2,9,7,7,3,5,3,1,11,3,表上作業(yè)法計算中應(yīng)注意的問題,1.解的情況 唯一：非基變量檢驗數(shù)全部大于0； 無窮多解：至少存在一個非基變量檢驗數(shù)等于0。,2.退化情況：在確定初始基可行解的時

14、候，當(dāng)填(i,j)格子時，若ai=bj, 則xij=ai=bj, 但此時只能劃去一行或一列，在后面的填充過程中相應(yīng)格子要填0。,3.調(diào)整時，若閉回路上出現(xiàn)兩個或兩個以上偶頂點取值同時達到最小，只能選一個變量出基。,課堂練習(xí)用表上作業(yè)法求解下列運輸問題.,,,,,,,0,3,10,-1,2,-5,9,1,2,1,-1,10,12,,,,,調(diào)整量為 min{3,1}=1，出基變量為x23.,最優(yōu)解:,0,3,10,-2,3,-5,9,0,

15、2,2,1,9,12,由于x11的檢驗數(shù)為0，所以最優(yōu)解不唯一。,,,,,0,3,10,-2,3,-5,9,2,2,1,9,12,0,最優(yōu)解:,,第三節(jié) 產(chǎn)銷不平衡的運輸問題及應(yīng)用,表上作業(yè)法是以產(chǎn)銷平衡為前提的：,實際中，往往遇到產(chǎn)銷不平衡的運輸問題,1.產(chǎn)大于銷（供過于求）,2.銷大于產(chǎn)（供不應(yīng)求）,產(chǎn)銷不平衡運輸問題向產(chǎn)銷平衡運輸問題的轉(zhuǎn)化,產(chǎn)大于銷的運輸問題：,數(shù)學(xué)模型,設(shè)xi n+1 是產(chǎn)地Ai 的儲存量，化成標(biāo)準(zhǔn)形,其中

16、,引入一個虛擬的銷地（需求量等于 ），并令各個產(chǎn)地到虛擬銷地的單位運費為0。,產(chǎn)小于銷的運輸問題：,引入一個虛擬的產(chǎn)地（產(chǎn)量等于 ），并令該虛擬產(chǎn)地到各銷地的單位運費為0。,總供應(yīng)量為19千噸，而總需求量為15千噸,例2： A1、A2、A3三個蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、B2、B3、B4四個城市。已知三個產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計分別為7千噸、5千噸和7千噸；四個城市今年的蔬菜需求量分別為

17、2千噸、3千噸、4千噸和6千噸；從每個蔬菜產(chǎn)地平均運輸1千噸蔬菜到各個城市的單位費用(萬元)見下表，你能否替他們編制一個總運費最省的蔬菜調(diào)運方案？,0,0,-2,2,0,4,3,0,8,2,5,7,2,3,8,7,最優(yōu)解中x15=2, x25=2，表示兩個產(chǎn)地沒有運出去的蔬菜量。,假如例2中各產(chǎn)地的蔬菜總產(chǎn)量不是19千噸，而是12千噸，就成了一個供不應(yīng)求的運輸問題。,引入一個虛擬產(chǎn)地,例3 設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。假定等量

18、的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各個化肥廠到各地區(qū)單位化肥的運價如下表所示，試決定使總運費最省的化肥調(diào)撥方案。,這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量160萬噸，四個地區(qū)的最低需求量為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第四個地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于總產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，其產(chǎn)量為50萬噸。由于各個地區(qū)的需求量包含兩部分，其中

19、最低需求量不能由假想的化肥廠D供應(yīng)，令運價為M，而另一部分滿足或不滿足均可以，故也可以由假想的化肥廠供應(yīng)，令相應(yīng)運價為0。把需求是兩種情況的看成兩個地區(qū)，得到這個問題的產(chǎn)銷平衡表。,根據(jù)表上作業(yè)法可以求得這個問題的最優(yōu)方案,,,,,,,,,,運輸問題的求解軟件（WINQSB）,進入WINQSB選擇Network Modeling模塊選取Transportation Problem；輸入問題名稱、產(chǎn)地數(shù)目、銷地數(shù)目、選擇目標(biāo)函數(shù)類型，數(shù)