1、,東 北 林 業(yè) 大 學,第三章 運輸問題,3.1運輸問題及其數(shù)學模型,3.2運輸問題的求解方法,3.3運輸模型的應用,東 北 林 業(yè) 大 學,運輸問題一般表述為：某種物資有產(chǎn)地m個, 其產(chǎn)量分別為ai(i=1,2,m), 有需求地(也稱銷地)n個，其需求量(也稱銷量)分別為bj(j=1,2,n), 從產(chǎn)地Ai到銷地Bj的每單位物資的運費為Cij。如何組織調(diào)運（擬定調(diào)運方案）才能使總運輸費用最小。,一、什么是運輸問題,例3.1 問題的提出,有三個林業(yè)局，木材產(chǎn)量分別為70、40和90萬立方米，準備向四個木材加工廠供應原木。各木材加工廠的原木需求量分別為30、60、50和60萬立方米，運輸價格見

2、下表?，F(xiàn)需擬定總運費最小的木材調(diào)運方案 。,3.1運輸問題及其數(shù)學模型,東 北 林 業(yè) 大 學,3.1運輸問題及其數(shù)學模型,運輸問題數(shù)據(jù)表（小方格內(nèi)的數(shù)字是運價,單位：元立方米）,東 北 林 業(yè) 大 學,二、運輸問題的數(shù)學模型,分析：目的- 目標- ,設置變量：,xij表示從第i個林業(yè)局（產(chǎn)地）調(diào)運給第j個木材加工廠（銷地）的木材（物資）數(shù)量。,目標函數(shù)：,1、2、3調(diào)運給B1、B2 、B3、B4 的運費分別為：,東 北 林 業(yè) 大 學,約束條件：,（1）產(chǎn)地的木材應全部運出，,1：,2：,3：,即某產(chǎn)地運出的總量與產(chǎn)量相等。,東 北 林 業(yè) 大 學,（2）銷地的需求應得到滿足，,即調(diào)運給某銷

3、地的總量與其需求量相等.,B1： B2： B3： B4：,（3）變量非負限制。,東 北 林 業(yè) 大 學,3.1運輸問題及其數(shù)學模型,整理得到該問題的數(shù)學模型為:,s.t.,東 北 林 業(yè) 大 學,3.1運輸問題及其數(shù)學模型,若產(chǎn)地為m個，銷地為n個，則數(shù)學模型為:,s.t.,東 北 林 業(yè) 大 學,三、非平衡型運輸問題的數(shù)學模型,（1）產(chǎn)量大于需求量,s.t.,東 北 林 業(yè) 大 學,三、非平衡型運輸問題的數(shù)學模型,（2）產(chǎn)量小于需求量,s.t.,東 北 林 業(yè) 大 學,運輸問題屬于特殊的線性劃劃問題，因其約束條件的系數(shù)矩陣具有特殊的結構，有比單純法更為簡便的求解方法，從而可以大量節(jié)約計算時間

4、；同時這類問題的應用也比較廣泛。 見教材69頁。,3.1運輸問題及其數(shù)學模型,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,鑒于運輸模型的特殊結構，在前面單純形法的基礎上，創(chuàng)造出一種專門求解運輸問題的單純形法。在我國，將這種方法習慣上稱為表上作業(yè)法。,請回顧單純形法的求解過程和關鍵的技術環(huán)節(jié)。,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,表上作業(yè)法的求解思路： 先編制一個初始可行方案，然后對其進行最優(yōu)性檢驗，若最優(yōu)則編制完畢；否則，在此基礎上進行調(diào)整、檢驗，如此重復直至得到最優(yōu)方案為止。,表上作業(yè)法的關鍵技術環(huán)節(jié)：,（）如何編制初始可行方案？,（）如何進行最優(yōu)性檢驗？,（）如何調(diào)整方

5、案？,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,一、確定初始可行方案,最小元素法：基本原則是就近供應，即運價最小的優(yōu)先供應。,C21=1,即2 B1； ,30,0,10,10,0,40,40,0,30,60,30,0,30,30,0,30,0,0,x13=40,x14=30, x21=30,x23=10, x32=60,x34=30, 其余xij=0,Z=340+1030+130+210+460+530=860萬元,初始方案為:,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,最小元素法小結:,設最小元素為 cij,表明Ai向Bj調(diào)運物資,調(diào)運量為:,xij=min(ai,bj)=,

6、ai , aibj,bj , aibj,規(guī)定：每確定一個調(diào)運量，只劃去一行或一列的運價。,滿格：填有調(diào)運量的格。它對應的變量為基變量。 空格：沒填調(diào)運量的格。它對應的變量為非基變量。,滿足可行方的條件是：滿格數(shù)等于（m+n-1)個。,因為基變量的個數(shù)與約束系數(shù)矩陣的秩相等。,當遇到ai=bj時怎么辦？,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,如：a2=b1=30,30,0,0,0,填0的格當作滿格來看待，它所對應的變量是基變量。這樣就可滿足滿格數(shù)等于（m+n-1)個。,東 北 林 業(yè) 大 學,二、最優(yōu)性檢驗,30,0,10,10,0,40,40,0,30,60,30,0,30,30,

7、0,30,0,0,(1)閉回路法,格(1,1)+1m3格(1,3)-1m3 格(2,3)+1m3 格(2,1)-1m3,運費的變化:,+3-3+2-1=1,即非基變量x11的檢驗數(shù)：,閉回路,何為閉回路？,由一個空格和若干個滿格的水平和垂直連線包圍成的封閉回路（72）。,11 1,12,221, 24-1,3310,33 12,由于24-1,所以方案不最優(yōu).,閉回路法的優(yōu)缺點?,(2)位勢法,30,0,10,10,0,40,40,0,30,60,30,0,30,30,0,30,0,0,設ui表示第i行的位勢, vj表示第j列的位勢,則對于滿格有如下關系： cij=ui+vj,u1+v3=c13

8、= 3 u1+v4=c14=10 u2+v1=c21= 1 u2+v3=c23= 2 u3+v2=c32= 4 u3+v4=c34= 5,按上式得如下方程組：,令u1= 0,v3= 3,3,u2=-1,-1,0,v1= 2,v4=10,10,2,u3=-5,-5,v2= 9,9,由閉回路法可知：,類似地可以求得任意空格的檢驗數(shù)為：,1,2,1,-1,10,12,30,0,10,10,0,40,40,0,30,60,30,0,30,30,0,30,0,0,3,-1,0,10,2,-5,9,1,2,1,-1,10,12,三、調(diào)整方案,24-1表明:,1.方案不最優(yōu); 2.A2B4; 3.調(diào)整1m3

9、木材 運費下降一元。,為保證供需平衡， 應按閉回路進行調(diào)整：,+,-,+,-,40,30,10,調(diào)整量是多少？,所有負號處的最小者。本例為10。,調(diào)整后的方案見下表。,30,50,60,30,20,10,x13=50,x14=20, x21=30,x24=10, x32=60,x34=30, 其余xij=0,Z=,850萬元,請思考，當同時出現(xiàn)幾個負的檢驗數(shù)時如何調(diào)整？,該方案是否是最優(yōu)？,30,50,60,30,20,10,四、最優(yōu)性檢驗,用位勢法計算的檢驗數(shù)見表,0,2,2,1,9,12,由于所有的檢驗數(shù)均為非負,所以調(diào)整后的方案是最優(yōu)方案.,3.2運輸問題的求解方法,東 北 林 業(yè) 大

10、學,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,非平衡運輸問題的求解 (1)供給大于需求,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,(1)供給大于需求,東 北 林 業(yè) 大 學,(2)供給小于需求,3.2運輸問題的求解方法,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,(2)供給小于需求,東 北 林 業(yè) 大 學,3.2運輸問題的求解方法,30,50,60,30,20,10,課堂討論：,該方案是否能夠被執(zhí)行？請說明理由。,東 北 林 業(yè) 大 學,3.3運輸模型的應用,例自來水（短缺資源）分配問題,某城市自來水的水源地為、三個水庫，分別由地下管道把水送往該市所轄甲、乙、丙、丁四個區(qū)

11、。但水庫與丁區(qū)之間沒有地下管道。由于地理位置的差別，各水庫通往各區(qū)的輸水管道經(jīng)過的涵洞、橋梁、加壓站和凈水站等設備各不相同,因此該公司對各區(qū)的引水管理費（元/千噸）各不相同，見下表。但是對各區(qū)的其它管理費均為45元千噸，供水單價均為90元千噸。各區(qū)的水需求量見表。該公司應如何分配供水量，才能保障各區(qū)最底需求的基礎上獲利最多。,東 北 林 業(yè) 大 學,3.3運輸模型的應用,東 北 林 業(yè) 大 學,希望用運輸模型來解決該問題.,總利潤=總收入-總成本,總收入=最大供水量供水價格 (是個常數(shù)),總成本=引水管理費+其它管理費 (是個變數(shù)) (是個常數(shù)),綜上,問題轉化為:如何分配供水量,才能保障各區(qū)最底需求的基礎上使總的引水管理費最少。,現(xiàn)在考慮把問題構成一個運輸模型.,關鍵就是將上表轉化為規(guī)范的運輸問題作