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

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

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

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

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

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

6、作業(yè)法,表上作業(yè)法是一種迭代法，迭代步驟為： 1、先按某種規(guī)則找出一個(gè)初始解(初始調(diào)運(yùn)方案)； 2、再對(duì)現(xiàn)行解作最優(yōu)性判別； 3、若這個(gè)解不是最優(yōu)解，就在運(yùn)輸表上對(duì)它進(jìn)行調(diào)整改進(jìn)，得出—個(gè)新解； 4、再判別，再改進(jìn)； 5、直至得到運(yùn)輸問題的最優(yōu)解為止。 迭代過程中得出的所有解都要求是運(yùn)輸問題的基可行解。,例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è)法,沃格爾法計(jì)算步驟：1) 分別算出各行、各列的罰數(shù)。2) 從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進(jìn)行運(yùn)量調(diào)整。3) 對(duì)剩余行、列再分別

8、計(jì)算各行、列的差額。返回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)性檢驗(yàn)－－閉回路法,

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

10、n個(gè)對(duì)偶變量。故解不唯一，其解稱為位勢(shì)。若上述方程的某組解滿足對(duì)偶問題的所有條件，即：,此時(shí)，原問題與對(duì)偶問題均可行，故達(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ùn)輸表中找出這個(gè)空格對(duì)應(yīng)的閉回路，在滿足所有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點(diǎn)的運(yùn)輸量，以得到另一個(gè)更好的基可行解。,

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

12、得出一新的運(yùn)輸方案。該運(yùn)輸方案的總運(yùn)費(fèi)比原運(yùn)輸方案減少，改變量等于換出變量的檢驗(yàn)數(shù)。 然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，加不是最優(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,由于所有非基變量的檢驗(yàn)數(shù)全非負(fù)，故這個(gè)解為最優(yōu)解。又由于非基變

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

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

15、為基變量。,二、表上作業(yè)法,三、運(yùn)輸問題的進(jìn)一步討論,上一節(jié)講述的運(yùn)輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實(shí)際上，在很多運(yùn)輸問題中，總產(chǎn)量不等于總銷量。,表上作業(yè)法 —— 以產(chǎn)銷平衡 為前提。,1、產(chǎn)銷不平衡的運(yùn)輸問題,三、運(yù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)地,運(yùn)價(jià),需求量,

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,三、運(yùn)輸問題的進(jìn)一步討論,,產(chǎn)大于銷,,產(chǎn)銷不平衡,產(chǎn)銷平衡,模型：,三、運(yùn)輸問題的進(jìn)一步討論,設(shè) 為Ai的貯存量。,將多余物原地貯存。,令：,三、運(yùn)輸問題的進(jìn)一步討論,理解： 產(chǎn) >銷 假想有一銷地 j=n+1 銷量為

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

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

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

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

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

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

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

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

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

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

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

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

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