第三章運輸問題北京物資學(xué)院信息學(xué)院北京物資學(xué)院運籌學(xué)教學(xué)課件本章主要內(nèi)容第一節(jié)運輸問題的數(shù)學(xué)模型及其特征第二節(jié)運輸問題的求解—表上作業(yè)法第三節(jié)產(chǎn)銷不平衡的運輸問題及應(yīng)用第一節(jié)運輸問題的數(shù)學(xué)模型及其特征

運輸問題的定義

運輸問題的數(shù)學(xué)模型

運輸問題的特征1.運輸問題的定義例1：某集團(tuán)新購進(jìn)一批鋼材，分別存儲在三個倉庫，現(xiàn)在要將這批鋼材運到分布在各地的四個工廠。各倉庫的庫存量、各工廠的需求量以及從各倉庫往各個工廠每運送一噸鋼材所需的費用見下表，問如何調(diào)運才能使總運費降到最低？工廠B1工廠B2工廠B3工廠B4庫存量倉庫A1291079倉庫A213425倉庫A384257需求量3846運輸問題：有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)運方案才能使總運費最?。緽1B2…Bn供應(yīng)量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam需求量b1b2…bn2.運輸問題的數(shù)學(xué)模型運輸問題的約束方程組系數(shù)矩陣及特征矩陣A是一個m+n行mn列的矩陣，它的秩不超過m+n-1。運輸問題一般有m+n-1個基變量。系數(shù)矩陣非常稀疏。

xij的系數(shù)列向量為：m行n行3.運輸問題的特征特征1：運輸問題一定有可行解；特征2：運輸問題一定有最優(yōu)解；特征3：運輸問題每一組基對應(yīng)m+n-1個基變量；特征4：運輸問題的m+n-1個基變量構(gòu)成的變量組不含閉回路；特征5：任意一個非基變量和m+n-1個基變量組成的變量組中必定存在一條并且只存在唯一一條閉回路；

特征6：如果運輸問題中的供應(yīng)量和需求量都是整數(shù)，則任一基解中各變量的取值也都是整數(shù)。

閉回路定義：凡是能夠排列成下列序列的一組變量的集合就稱為運輸問題的一個閉回路。并稱集合中每一個變量為此閉回路的一個頂點；稱連接相鄰兩個變量（頂點）以及連接最后一個頂點和第一個頂點的線段為此閉回路的邊。或B1B2B3B4B5A1A2A3A4X45X41X31X33X13X15B1B2B3B4B5A1A2A3A4X34X32X14X12B1B2B3B4B5A1A2A3A4X35X41X31X43X13X15B1B2B3B4B5A1A2A3A4X11X12X22X24X44X42X21（1）每個頂點都是轉(zhuǎn)折點；（2）閉回路是一條閉合的折線，每一條邊都是水平或垂直的；（3）閉回路上同一行（列）的頂點有偶數(shù)個。閉回路上的點對應(yīng)的系數(shù)列向量線性相關(guān)。PijPikPlkPlsPusPuj由于容易證明第二節(jié)運輸問題的求解--表上作業(yè)法第四步：確定進(jìn)基變量和出基變量，調(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)成一組基變量的充要條件是變量組中不含閉回路.關(guān)鍵:找出m+n-1個不含閉回路的變量。西北角法（左上角法）最小元素法Vogel法問題：如何使得一個選定的變量不包含在閉回路中？B1B2B3B4庫存量A1291079A213425A384257需求量3846623163對應(yīng)的總運費為

C

1=2×3+9×6+3×2+4×3+2×1+5×6=110西北角法(左上角法)-3-3-6-6-2-2-3-3-1-1-6-6最小元素法B1B2B3B4庫存量A1291079A213425A384257需求量3846523443對應(yīng)的總運費為

C

2=9×5+7×4+1×3+2×2+4×3+2×4=100-3-3-4-4-2-2-3-3-4-4-5-5Vogel法B1B2B3B4庫存量A1291079A213425A384257需求量3846154533對應(yīng)的總運費為

C

2=2×3+9×5+7×1+2×5+4×3+2×4=88-3-3-1-1-5-5-3-3-5-5-4-4B1B2B3B4供應(yīng)量A178143A226535A314278需求量2176105262退化情況的處理-2-2-1-1-5-5-2-2-6-6用西北角法求下列運輸問題的第一個基可行解B1B2B3供應(yīng)量A11842A25251A35737需求量217172-2-2-1-1-7-7注意：每次只能劃去一行或一列，不能同時劃去行和列。當(dāng)只剩下一行（列）時，只能劃去列（行）。想一想：為什么？00用最小元素法求下列運輸問題的第一個基可行解第二步：計算各非基變量的檢驗數(shù)1.閉回路法；2.位勢法。檢驗數(shù)的定義：非基變量的取值每增加1時，總運費的增加量。運輸問題的最優(yōu)性條件：檢驗數(shù)非負(fù)1.閉回路法基變量不含閉回路，但任何一個非基變量都可以與基變量構(gòu)成唯一一條閉回路B1B2B3B4庫存量A1291079A213425A384257需求量3846623163含義：x14每增加一個單位，總運費增加-6個單位+1+1+1-1-1-1623163所有非基變量的檢驗數(shù)見上表B1B2B3B4庫存量A12910790-6A2134255-5A384257143需求量38462.位勢法位勢：運輸問題的對偶變量稱為位勢。因為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ù)的求法由于基變量的檢驗數(shù)為0，所以可以利用m+n-1個基變量求出位勢B1B2B3B4庫存量A1291079A213425A384257需求量3846623163029-610-8130-65-5143第四步：調(diào)整調(diào)運方案1.確定入基變量：選取最小負(fù)檢驗數(shù)對應(yīng)的非基變量入基2.確定出基變量和調(diào)整量將進(jìn)基變量對應(yīng)的閉回路中的頂點分為奇頂點和偶頂點，令θ=min{閉回路上所有偶頂點對應(yīng)的運量xij

}則θ即為調(diào)整量，選取一個運量等于θ的偶頂點為出基變量。3.調(diào)整：閉回路上奇頂點上的運量增加θ，偶頂點上的運量減少θ。閉回路以外頂點的運量不變。上例中：若選x14進(jìn)基，則=min{6,3,6}=3,出基變量為x23,調(diào)整后得：B1B2B3B4庫存量A12910790-6A2134255-5A384257143需求量3846623163總運費：

C=2×3+9×3+7×3+3×5+2×4+5×3=92<110x32進(jìn)基，則=min{3,3}=3,出基變量選x34,調(diào)整后得：B1B2B3B4庫存量A1291079A213425A384257需求量38463543330-6-2294756618-3檢驗數(shù)全部非負(fù)，已經(jīng)是最優(yōu)調(diào)運方案；總費用C*=2×3+9×0+7×6+3×5+4×3+2×4=83

B1B2B3B4庫存量A1291079A213425A384257需求量38460543360-6-529773531113表上作業(yè)法計算中應(yīng)注意的問題1.解的情況

唯一：非基變量檢驗數(shù)全部大于0；

無窮多解：至少存在一個非基變量檢驗數(shù)等于0。2.退化情況：在確定初始基可行解的時候，當(dāng)填(i,j)格子時，若ai=bj,

則xij=ai=bj,但此時只能劃去一行或一列，在后面的填充過程中相應(yīng)格子要填0。3.調(diào)整時，若閉回路上出現(xiàn)兩個或兩個以上偶頂點取值同時達(dá)到最小，只能選一個變量出基。課堂練習(xí)用表上作業(yè)法求解下列運輸問題.B1B2B3B4供應(yīng)量A13113107A219284A3741059需求量3656B1B2B3B4供應(yīng)量A13113107A219284A3741059需求量3656431363B1B2B3B4供應(yīng)量A13113107A219284A3741059需求量36564313630310-12-59121-11012調(diào)整量為

min{3,1}=1，出基變量為x23.B1B2B3B4供應(yīng)量A13113107A219284A3741059需求量3656531362最優(yōu)解:0310-23-590221912由于x11的檢驗數(shù)為0，所以最優(yōu)解不唯一。B1B2B3B4供應(yīng)量A13113107A219284A3741059需求量36565133620310-23-592219120最優(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è)xin+1是產(chǎn)地Ai的儲存量，化成標(biāo)準(zhǔn)形其中引入一個虛擬的銷地（需求量等于），并令各個產(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千噸；四個城市今年的蔬菜需求量分別為2千噸、3千噸、4千噸和6千噸；從每個蔬菜產(chǎn)地平均運輸1千噸蔬菜到各個城市的單位費用(萬元)見下表，你能否替他們編制一個總運費最省的蔬菜調(diào)運方案？

單位運費B1B2B3B4供應(yīng)量A1211347A2103595A378127需求量2346

需求地生產(chǎn)地B1B2B3B4B5供應(yīng)量A12113407A21035905A3781207需求量2346400-220430825723343222387最優(yōu)解中x15=2,x25=2，表示兩個產(chǎn)地沒有運出去的蔬菜量。假如例2中各產(chǎn)地的蔬菜總產(chǎn)量不是19千噸，而是12千噸，就成了一個供不應(yīng)求的運輸問題。

單位運費B1B2B3B4供應(yīng)量A1211343A2103594A378125需求量2346

單位運費B1B2B3B4供應(yīng)量A1211344A2103593A378125A400003需求量2346

引入一個虛擬產(chǎn)地例3設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各個化肥廠到各地區(qū)單位化肥的運價如下表所示，試決定使總運費最省的化肥調(diào)撥方案。

需求地區(qū)化肥廠IIIIIIIV產(chǎn)量（萬噸）A1613221750B1413191560C192023-50最低需求（萬噸）3070

010最高需求（萬噸）507030不限這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量160萬噸，四個地區(qū)的最低需求量為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第四個地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于總產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一