運籌學(xué)課件第三章----運輸問題

1、第三章 運輸問題,一、運輸問題及其數(shù)學(xué)模型二、表上作業(yè)法三、運輸問題的進(jìn)一步討論四、應(yīng)用舉例,,,,,一、運輸問題及其數(shù)學(xué)模型,供應(yīng)地,運價,需求地,引例：,運輸問題網(wǎng)絡(luò)圖,,供應(yīng)地約束,需求地約束,,,一、運輸問題及其數(shù)學(xué)模型,運輸問題的描述： 設(shè)某種物品有m個產(chǎn)地A1,A2,...,Am，各產(chǎn)地的產(chǎn)量分別是a1,a2,...,am；有n個銷地B1,B2,...,Bn，各銷地的銷量分別為b1,b

2、2,....bn。假定從產(chǎn)地Ai(i=1,2,…,m)向銷地出Bj(j＝l,2,….n)運輸單位物品的運價是cij，問怎樣調(diào)運這些物品才能使總運費最小?,一、運輸問題及其數(shù)學(xué)模型,運價表,一、運輸問題及其數(shù)學(xué)模型,產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型表示：,一、運輸問題及其數(shù)學(xué)模型,該模型是一個線性規(guī)劃模型，可以用單純形法求解。但是變量數(shù)目非常多。如3個產(chǎn)地，4個銷地。變量數(shù)目會有19個之多。因此應(yīng)該尋求更簡便的解法。為了說明適于求解運輸問題

3、的更好的解法，先分析運輸問題數(shù)學(xué)模型的特點。,一、運輸問題及其數(shù)學(xué)模型,運輸問題數(shù)學(xué)模型的特點：1．運輸問題有有限最優(yōu)解,是一個可行解。同時，目標(biāo)函數(shù)有下界，且不會趨于負(fù)無窮。所以，必存在有限最優(yōu)解。,一、運輸問題及其數(shù)學(xué)模型,2．運輸問題約束條件的系數(shù)矩陣,,,,n 行,m 行,系數(shù)列向量：,一、運輸問題及其數(shù)學(xué)模型,由此可知，運輸問題具有下述特點： (1)約束條件系數(shù)矩陣的元素等于0或1； (2)約束條件系數(shù)矩陣的每一列

4、有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次；對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：(3)所有結(jié)構(gòu)約束條件都是等式約束；(4)各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。 秩 ( A) =m+n-1運輸問題的基可行解中應(yīng)包含m+n-1個基變量.,一、運輸問題及其數(shù)學(xué)模型,3.運輸問題的解(1)解x必須滿足模型中的所有約束條件；(2)基變量對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān)

5、；(3)解中非零變量xij的個數(shù)不能大于(m+n-1)個，原因是運輸問題中雖有(m+n)個結(jié)構(gòu)約束條件，但由于總產(chǎn)量等于總銷量，故只有(m+n-1)個結(jié)構(gòu)約束條件是線性獨立的；(4)為使迭代順利進(jìn)行，基變量的個數(shù)在迭代過程中保持為 (m+n-1)個。運輸問題解的每一個分量，都唯一對應(yīng)其運輸表中的一個格 填有數(shù)字的格 或 空格,一、運輸問題及其數(shù)學(xué)模型,下表給出了例1的一個解。,一、運輸問題及其數(shù)學(xué)模型,二、表上

6、作業(yè)法,表上作業(yè)法是一種迭代法，迭代步驟為： 1、先按某種規(guī)則找出一個初始解(初始調(diào)運方案)； 2、再對現(xiàn)行解作最優(yōu)性判別； 3、若這個解不是最優(yōu)解，就在運輸表上對它進(jìn)行調(diào)整改進(jìn)，得出—個新解； 4、再判別，再改進(jìn)； 5、直至得到運輸問題的最優(yōu)解為止。 迭代過程中得出的所有解都要求是運輸問題的基可行解。,例1：,二、表上作業(yè)法,,,,,,,,8,2,10,14,8,

7、6,所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝246,二、表上作業(yè)法,1、初始基可行解－－最小元素法,在滿足約束條件下盡可能的給最左上角的變量最大值.,8,8,6,4,8,14,,,,,,,,所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝372,1、初始基可行解－－西北角法,二、表上作業(yè)法,沃格爾法計算步驟：1) 分別算出各行、各列的罰數(shù)。2) 從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進(jìn)行運量調(diào)整。3) 對剩余行、列再分別

8、計算各行、列的差額。返回1)、2)。,二、表上作業(yè)法,1、初始基可行解－－沃格爾法,14,,,,,,,,所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝244,8,8,12,2,4,二、表上作業(yè)法,4-4=0,3-2=1,6-5=1,4-2=2,10-5=5,4-3=1,9-6=3,0,1,8-6=2,4-2=2,4-3=1,9-6=3,8,2,10,14,8,6,1,2,1,10,12,-1,,二、表上作業(yè)法,2、解的最優(yōu)性檢驗－－閉回路法,

9、某空格的檢驗數(shù)是以該空格為第一個頂點，某回路的奇數(shù)頂點運價和減去其偶數(shù)頂點運價和。,,,,,,,,,原問題,設(shè)其對偶變量為：,2、解的最優(yōu)性檢驗－－對偶變量法,二、表上作業(yè)法,對偶問題:,考慮原問題變量xj的檢驗數(shù)為：,,二、表上作業(yè)法,假設(shè)已得到一個基可行解，其基變量為：,則有：,s=m+n-1,,則運輸問題變量xij的檢驗數(shù)為：,二、表上作業(yè)法,方程組有m+n-1個方程。因為運輸表中每行和每列均有基變量，因此上面方程組含有全部m+

10、n個對偶變量。故解不唯一，其解稱為位勢。若上述方程的某組解滿足對偶問題的所有條件，即：,此時，原問題與對偶問題均可行，故達(dá)到最優(yōu)。其解分別為：,二、表上作業(yè)法,例：,8,2,10,14,8,6,二、表上作業(yè)法,,1,0,-4,2,9,3,10,1,2,1,-1,10,12,改進(jìn)的方法是在運輸表中找出這個空格對應(yīng)的閉回路，在滿足所有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點的運輸量，以得到另一個更好的基可行解。,

11、3、解的改進(jìn)－閉回路調(diào)整法,二、表上作業(yè)法,解改進(jìn)的具體步驟(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數(shù)頂點，沿閉回路的順(或逆)時針方向前進(jìn)，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的頂點(格子)，以該格中的變量為換出變量；(4)以換出變量的運輸量為調(diào)整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減去這一數(shù)值，從而

12、得出一新的運輸方案。該運輸方案的總運費比原運輸方案減少，改變量等于換出變量的檢驗數(shù)。 然后，再對得到的新解進(jìn)行最優(yōu)性檢驗，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。,二、表上作業(yè)法,例：,二、表上作業(yè)法,,,,,min(6,2)=2,2-2=0,0+2=2,6-2=4,10+2=12,例：,8,2,12,14,8,4,0,2,2,9,12,1,由于所有非基變量的檢驗數(shù)全非負(fù)，故這個解為最優(yōu)解。又由于非基變

13、量有零檢驗數(shù)，所以有無窮多最優(yōu)解。,二、表上作業(yè)法,練習(xí)題,二、表上作業(yè)法,練習(xí)題,練習(xí)題,二、表上作業(yè)法,練習(xí)題,練習(xí)題,二、表上作業(yè)法,答案,二、表上作業(yè)法,1）若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負(fù)，在繼續(xù)進(jìn)行迭代時，取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取小于零的檢驗數(shù)中最小者對應(yīng)的變量為換入變量。 2）當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重(無窮

14、多)最優(yōu)解。,4、需要說明的幾個問題,二、表上作業(yè)法,3）（二 ）退化 某一基變量 的值為0初始解 在確定初始解的供需關(guān)系時，若在確定（i, j ） 的數(shù)字時，要劃去第i行,第j列。為使在產(chǎn)銷平衡表上有m+n-1個數(shù)字格，須在第i 行或j列中 （ 非i,j ) 選一數(shù)字格為0。退化解 閉回路中有（ - ）標(biāo)記中有兩個或以上相等的最小數(shù)。調(diào)整后出現(xiàn)退化解，必須在一數(shù)字格中填入0，以表明其

15、為基變量。,二、表上作業(yè)法,三、運輸問題的進(jìn)一步討論,上一節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上，在很多運輸問題中，總產(chǎn)量不等于總銷量。,表上作業(yè)法 —— 以產(chǎn)銷平衡 為前提。,1、產(chǎn)銷不平衡的運輸問題,三、運輸問題的進(jìn)一步討論,2,3,2,1,3,4,1,,,,,,,,,,,,,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供應(yīng)量,供應(yīng)地,運價,需求量,

16、需求地,6,7,5,3,8,4,2,7,5,9,10,6,例：假設(shè)供應(yīng)量大于需求量,+5,5,,,,d5=5,假想銷地,0 0 0,s3=24,三、運輸問題的進(jìn)一步討論,,產(chǎn)大于銷,,產(chǎn)銷不平衡,產(chǎn)銷平衡,模型：,三、運輸問題的進(jìn)一步討論,設(shè) 為Ai的貯存量。,將多余物原地貯存。,令：,三、運輸問題的進(jìn)一步討論,理解： 產(chǎn) >銷 假想有一銷地 j=n+1 銷量為

17、 運價,模型：,三、運輸問題的進(jìn)一步討論,三、運輸問題的進(jìn)一步討論,例： 某市有三個造紙廠A1，A2，A3，其紙的產(chǎn)量分別為8，5和9個單位，有4個集中用戶B1，B2，B3，B4，其需用量分別為4，3，5和6個單位。由各造紙廠到各用戶的單位運價如表3—15所示，請確定總運費最少的調(diào)運方案。,三、運輸問題的進(jìn)一步討論,解：由于總產(chǎn)量22大于總銷量18，故本問題是個產(chǎn)銷不平衡運輸問題。增加一假想銷地B5，用表上作業(yè)法求解。,三、運輸問題

18、的進(jìn)一步討論,三、運輸問題的進(jìn)一步討論,2、有轉(zhuǎn)運的運輸問題,在以上討論中，假定物品由產(chǎn)地直接運送到銷售目的地，不經(jīng)中間轉(zhuǎn)運。但是，常常會遇到這種情形：需先將物品由產(chǎn)地運列某個中間轉(zhuǎn)運站(可能是另外的產(chǎn)地、銷地或中間轉(zhuǎn)運倉庫)，然后再轉(zhuǎn)運到銷售目的地。有時，經(jīng)轉(zhuǎn)運比直接運到目的地更為經(jīng)濟(jì)。因此，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進(jìn)去。,三、運輸問題的進(jìn)一步討論,2、有轉(zhuǎn)運的運輸問題,轉(zhuǎn)運量 t1t2t3t4t5t6

19、t7,供應(yīng)量,需求量,xij,,轉(zhuǎn)運量 t1t2t3t4t5t6t7,假設(shè)單位運轉(zhuǎn)費用為ti，則線性規(guī)劃模型為：,,三、運輸問題的進(jìn)一步討論,,,,,,第二項為常數(shù)，對求解結(jié)果無影響，可去掉。,,模型變?yōu)橄铝行问剑?這是一個產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型?？梢粤谐銎溥\價表，用表上作業(yè)法求解。,其運價表形式如下（注意其中對角線上的運價值）：,,建立一般意義上的數(shù)學(xué)模型，設(shè)：ai：第i個產(chǎn)地的產(chǎn)量(凈供應(yīng)量)；bj：

20、第j個銷地的銷量(凈需要量)；xij：由第i個發(fā)送地運到第j個接收地的物品數(shù)量；cij：由第i個發(fā)送地到第j個接收地的單位運價，ti：第i個地點轉(zhuǎn)運物品的數(shù)量；ci：第i個地點轉(zhuǎn)運單位物品的費用。 將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面。銷地排在后面，則有：,令：,建立數(shù)學(xué)模型：,,注：所有i=j，cij=-ci,a1…a5b1…b5Qc1…c5c11…c55,例：如圖所示是一個運輸系統(tǒng)，它包括二個產(chǎn)地（

21、1和2）、二個銷地(4和5)及一個中間轉(zhuǎn)運站(3)，各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點處箭線旁的數(shù)字表示，節(jié)點聯(lián)線上的數(shù)字表示其間的運輸單價，節(jié)點旁的數(shù)字為該地的轉(zhuǎn)運單價，試確定最優(yōu)運輸方案。,運用最小元素法，求初始運輸方案，如下表：,最優(yōu)運輸方案如下表：,一、回答問題1、在運輸問題數(shù)學(xué)模型中，為什么模型的(m+n)個約束中最多只有(m+n-1)個是獨立的?2．試述用最小元素法確定運輸問題的初始基可行解的基本思路。3．如何用閉回

22、路法求檢驗數(shù)？4 ．沃格爾法的基本思想是什么？什么是罰數(shù)？5．在解的改進(jìn)過程中，如何確定調(diào)整量？6．如何把一個產(chǎn)銷不平衡的運輸問題(含產(chǎn)大于銷和銷大于產(chǎn))轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題。,練習(xí)題,二、判斷下列說法是否正確(1)運輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解；(2)在運輸問題中，只要給出一組合(m+n-1)個非零的{xij}，且滿足Σxij=ai

23、， Σ xij=bj，就可以作為一個初始基可行解；(3)表上作業(yè)法實質(zhì)上就是求解運輸問題的單純形法；(4)按最小元素法(或伏格爾法)給出的初始基可行解，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路；,練習(xí)題,(5)如果運輸問題單位運價表的某一行(或某一列)元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化；(6)如果運輸問題單位運價表的某一行(或某一列)元素分別乘上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化；(7)當(dāng)所有產(chǎn)地產(chǎn)量和

24、銷地的銷量均為整數(shù)值時，運輸問題的最優(yōu)解也為整數(shù)值,1，2，6不對,練習(xí)題,三、用位勢法（對偶變量法）求其檢驗數(shù)。,練習(xí)題,四、運用舉例,例 1 、某飛機制造廠生產(chǎn)一種民用噴氣式飛機，生產(chǎn)的最后階段是制造噴氣發(fā)動機，以及把發(fā)動機安裝到已完成的飛機骨架上（一種很快的操作）。為了不誤合同規(guī)定的交貨期，第一.二.三.四月必須安裝發(fā)動機的臺數(shù)分別為：10 ,15, 25 ,20。但受生產(chǎn)能力等條件的限制，這些月份的最高生產(chǎn)臺數(shù)分別為：25,35

25、 ,30 , 10。每月單臺發(fā)動機的存儲費用為1.5萬元。已知一、二、三、四月份的單臺生產(chǎn)費用各為：108 、111、 110、113萬元。試安排這四個月的生產(chǎn)計劃，使生產(chǎn)費用和存儲費用之和最小。 1）建立此問題的一般LP模型。 2）把此問題作為運輸問題來處理，試建立相應(yīng)的運輸表格。 3）求此“運輸問題”的最優(yōu)解。,解：1）設(shè)xi表示第i個月生產(chǎn)發(fā)動機的臺數(shù)，yi表示第個月的存儲臺數(shù)，則一般LP模型為：,四、運用舉例,由于不能缺貨

26、，并考慮到是不平衡問題（虛設(shè)收點5）建立如下運輸表格,四、運用舉例,最小費用為： w*=7730(萬元）,四、運用舉例,例2 某航運公司承擔(dān)六個港口城市A.B.C.D.E.F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)見表：,每條航線使用相同型號的船只，各城市間的航程天數(shù)如表：,四、運用舉例,每條船只每次裝卸貨物的時間各需一天。？該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求。,

27、四、運用舉例,每天載貨航程所需的船只數(shù)：,四、運用舉例,分析：1）所需船只可分為兩部分：載貨航程所需的船只數(shù)、各港口間調(diào)度所需的船只數(shù)。 2）每天載貨航程所需的船只數(shù)：,3） 每天各港口調(diào)度所需船只數(shù)。,四、運用舉例,為使配備船只數(shù)最少，就應(yīng)將C.D.F的船只調(diào)運到A.B.E,由表上作業(yè)法，最優(yōu)調(diào)運為：,四、運用舉例,所以，每天用于調(diào)度的最少船只數(shù)為：5*2+13*1+17*1+7*1=47 最少總需求為

28、91+47=138（條）,四、運用舉例,例3：某玩具公司分別生產(chǎn)三種新型玩具，每月可供量分別為l000件，2000件，2000件，它們分別被送到甲、乙、丙三個百貨商店銷售。已知每月百貨商店各類玩具預(yù)期銷售量均為1500件，由于經(jīng)營方面原因，各商店銷售不同玩具的盈利額不同(見表)。又知丙百貨商店要求至少供應(yīng)C玩具1000件、而拒絕進(jìn)A種玩具。求滿足上述條件下使總盈利額為最大的供銷分配方案。,四、運用舉例,四、運用舉例,例4： 有甲、乙、

29、丙三個城市，每年分別需要煤炭320，250，350(萬噸)，出A，B兩個煤礦負(fù)責(zé)供應(yīng)。已知煤礦年產(chǎn)量分別A為400萬噸，B為450萬噸，從兩煤礦至各城市煤炭運價(萬元／萬噸)如表3—23所示。由于需求大于產(chǎn)量，經(jīng)協(xié)商平衡，甲城市必要時可少供0~30萬噸，乙城市需求量須全部滿足，丙城市需求量不少于270萬噸。試求將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運費為最低的調(diào)運方案。,四、運用舉例,四、運用舉例,作 業(yè),3.7（2）