1、第三章 運輸問題,,2,本章內(nèi)容,運輸問題及其數(shù)學模型用表上作業(yè)法求解運輸問題運輸問題的進一步討論應用問題舉例,問題的提出： 一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。,§1運輸問題及其數(shù)學模型,§1運輸問題及其數(shù)學模型,1.經(jīng)典運輸問題——單一品

2、種物資的運輸調(diào)度問題,§1運輸問題及其數(shù)學模型,網(wǎng)絡表示：,,,,5,000,,2,500,,6,000,,,,,,,,,,,,,,,如果運輸問題的總產(chǎn)量等于其總銷量，即有 則稱該運輸問題為產(chǎn)銷平衡運輸問題；反之，稱產(chǎn)銷不平衡運輸問題。,產(chǎn)銷平衡運輸問題的數(shù)學模型可表示如下：,§1運輸問題及其數(shù)學模型,二、運輸問題數(shù)學模型的特點：運輸問題一定

3、有最優(yōu)解；基變量的個數(shù)=m+n-1運輸問題約束條件的系數(shù)矩陣：,§1運輸問題及其數(shù)學模型,運輸問題具有下述特點：(1) 約束條件系數(shù)矩陣的元素等于0或1；(2) 約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次。,§1運輸問題及其數(shù)學模型,對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：(1) 所有結(jié)構(gòu)約

4、束條件都是等式約束；(2) 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。,§1運輸問題及其數(shù)學模型,例1 某部門有3個生產(chǎn)同類產(chǎn)品的工廠(產(chǎn)地)，生產(chǎn)的產(chǎn)品由4個銷售點(銷地)出售，各工廠的生產(chǎn)量、各銷售點的銷售量(假定單位均為t)以及各工廠到各銷售點的單位運價(元／t)示于表3-2中，要求研究產(chǎn)品如何調(diào)運才能使總運費最小?,,表3-2,4,2,8,12,5,4,10,11,3,9,6,11,§1運輸問

5、題及其數(shù)學模型,該問題的數(shù)學模型：,§1運輸問題及其數(shù)學模型,12,本章內(nèi)容,運輸問題及其數(shù)學模型用表上作業(yè)法求解運輸問題運輸問題的進一步討論應用問題舉例,一、表上作業(yè)法的基本思想和步驟：1.基本思想：同單純形法的基本思想,§2 用表上作業(yè)法求解運輸問題,二、表上作業(yè)法的步驟（1）尋找初始基可行解；最小元素法、西北角法、沃格爾法（2）求出非基變量檢

6、驗數(shù)（空格檢驗數(shù)），判斷是否為最優(yōu)解；閉回路法、位勢法（3）換基改進，找到新的基可行解閉回路調(diào)整法（4 ）重復（2）（3）,§2 用表上作業(yè)法求解運輸問題,1.最小元素法 從運價最小的格開始，在格內(nèi)的右下角標上允許取得的最大數(shù)。然后按運價從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。,尋找初始基可行

7、解,,,4,2,8,5,10,11,12,3,4,6,9,11,1.最小元素法,總費用 z= =10×4+6×11+8×2+2×3+14×5+8×6=246,尋找初始基可行解,2.西北角法 從西北角（左上角）格開始，在格內(nèi)的右下角標上允許取得的最大數(shù)。然后按行（列）標下一

8、格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。,尋找初始基可行解,,,2.西北角法,總費用 z= =8×4+8×12+6×10+4×3+8×11+14×6=372,尋找初始基可行解,3.沃格爾法罰數(shù)=次小

9、費用-最小費用找出最大的罰數(shù)行或列所對應的最小費用優(yōu)先安排。重復計算步驟1和2,尋找初始基可行解,,,,3.沃格爾法,,4,10,12,11,3,4,6,9,11,2,8,5,2,0,1,5,1,3,2,2,1,0,1,1,3,2,1,14,,8,,8,,,1,0,2,總費用 z= =244,尋找初始基可行解,最優(yōu)性檢驗

10、就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計算檢驗數(shù)。由于目標要求極小，因此，當所有的檢驗數(shù)都大于或等于零時該調(diào)運方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進行調(diào)整。下面介紹兩種求檢驗數(shù)的方法：閉回路法和對偶變量法。,解的最優(yōu)性檢驗,1.閉回路法 閉回路：從空格出發(fā)，遇到數(shù)字格可以旋轉(zhuǎn)90度，最后回到空格所構(gòu)成的回路； 原理：利用檢驗數(shù)的經(jīng)濟含義； 檢驗數(shù)：非基變量增加一個單位引起的成

11、本變化量。 當所有非基變量的檢驗數(shù)均大于或等于零時，現(xiàn)行的調(diào)運方案就是最優(yōu)方案，因為此時對現(xiàn)行方案作任何調(diào)整都將導致總的運輸費用增加。 閉回路法的主要缺點是：當變量個數(shù)較多時，尋找閉回路以及計算兩方面都會產(chǎn)生困難。,解的最優(yōu)性檢驗,1.閉回路法（結(jié)合最小元素法的初始解）,,解的最優(yōu)性檢驗,8,14,10,2,6,8,檢驗數(shù)σ11=c11-c21+c23-c13=4-2+3-4=1σ24=c24-c1

12、4+c13-c23=9-11+4-3=-1<0,故知該最小元素法的解不是最優(yōu)解,位勢：設對應基變量xij的m+n-1個i、j ，存在ui,vj 滿足ui+vj=cij,i=1,2,..,m; j=1,2 ,… ,n稱這些ui , vj 為該基本可行解對應的位勢。,解的最優(yōu)性檢驗,2.對偶變量法（位勢法）,解的最優(yōu)性檢驗,2.對偶變量法（位勢法）,設對偶變量向量為,解的最優(yōu)性檢驗,對偶規(guī)劃為,解

13、的最優(yōu)性檢驗,,檢驗數(shù)：目標函數(shù)的系數(shù)減去對偶變量之和,原問題檢驗數(shù)：σij=cij-(ui+vj),特別對于m+n-1個基變量，有 σij=0,σj = C j- CBB-1 Pj = Cj - Y Pj σij = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, …,um, v1, v2, …,vn) Pij

14、 = Cij - ( ui+ vj ) 當xij 為基變量時 σij = Cij - ( ui+ vj )=0 由此，任選一個對偶變量為0，可求出其余所有的ui， vj 。 再根據(jù)σij = Cij - ( ui+ vj )求出所有非基變量的檢驗數(shù)。,解的最優(yōu)性檢驗,解的最優(yōu)性檢驗,表3-9,1.增加一位勢列和位勢行并計算位勢

15、,,其中,解的最優(yōu)性檢驗,2.計算檢驗數(shù),（+2）,4.解的改進——閉回路調(diào)整法,解的最優(yōu)性檢驗,改進的方法是在運輸表中找出這個空格對應的閉回路Lij，在滿足所有約束條件的前提下，使xij盡量增大并相應調(diào)整此閉回路上其他頂點的運輸量，以得到另一個更好的基可行解。,,,,,（-2）,（+2）,（-2）,5、需要注意的問題 （一）多個空格（非基變量）的檢驗數(shù)為負，任一個都可作為換入變量。一般σij<0中

16、最小的對應變量作為換入變量。 （二）最優(yōu)解時，如果有某非基變量的檢驗數(shù)為0，則說明該運輸問題有無窮多最有解。 （三）退化解。,解的最優(yōu)性檢驗,本章內(nèi)容,運輸問題及其數(shù)學模型用表上作業(yè)法求解運輸問題運輸問題的進一步討論應用問題舉例,§3運輸問題進一步討論,產(chǎn)銷不平衡的運輸問題有轉(zhuǎn)運的運輸問題,1.當產(chǎn)大于銷時，即,產(chǎn)銷不平衡問題,平衡后的數(shù)學模型為：,加入假想銷地（假想倉庫），銷量為

17、 ，由于實際并不運送，它們的運費為 = 0；,產(chǎn)銷不平衡問題,2.當銷大于產(chǎn)時，即,加入一個虛設的產(chǎn)地去生產(chǎn)不足的物資；它的產(chǎn)量為,產(chǎn)銷不平衡問題,有轉(zhuǎn)運的運輸問題,,表3-15 有轉(zhuǎn)運輸問題的運輸表,有轉(zhuǎn)運的運輸問題,有轉(zhuǎn)運的運輸問題,表3-16 有轉(zhuǎn)運輸問題的運價表,,例 5,有轉(zhuǎn)運的運輸問題,圖3-3示出了一個運輸系統(tǒng)，它包括兩個產(chǎn)地(①和②)、兩個銷地(④和⑤)及一個中間轉(zhuǎn)運站(③)，各