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

第三章運輸問題 一、運輸問題及其數(shù)學(xué)模型 二、表上作業(yè)法 三、運輸問題的進一步討論 四、應(yīng)用舉例2312341一、運輸問題及其數(shù)學(xué)模型s2=27s3=19s1=14供應(yīng)量供應(yīng)地運價d1=22d2=13d3=12d4=13需求量需求地6753842759106

引例：運輸問題網(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,b2,....bn。假定從產(chǎn)地Ai(i=1,2,…,m)向銷地出Bj(j＝l,2,….n)運輸單位物品的運價是cij，問怎樣調(diào)運這些物品才能使總運費最小?一、運輸問題及其數(shù)學(xué)模型運價表銷地產(chǎn)地B1B2…Bn產(chǎn)量A1C11C12…C1na1x11x12…x1nA2C12C22…C2na2x21x22…x2n……..…………………AmC1mC2m…Cmnamxm1xm2…xmn銷量b1b2…bm一、運輸問題及其數(shù)學(xué)模型產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型表示：（Ⅰ）一、運輸問題及其數(shù)學(xué)模型該模型是一個線性規(guī)劃模型，可以用單純形法求解。但是變量數(shù)目非常多。如3個產(chǎn)地，4個銷地。變量數(shù)目會有19個之多。因此應(yīng)該尋求更簡便的解法。為了說明適于求解運輸問題的更好的解法，先分析運輸問題數(shù)學(xué)模型的特點。一、運輸問題及其數(shù)學(xué)模型運輸問題數(shù)學(xué)模型的特點：1．運輸問題有有限最優(yōu)解是一個可行解。同時，目標(biāo)函數(shù)有下界，且不會趨于負(fù)無窮。所以，必存在有限最優(yōu)解。一、運輸問題及其數(shù)學(xué)模型2．運輸問題約束條件的系數(shù)矩陣A=n

行m行系數(shù)列向量：第i個第m+j個一、運輸問題及其數(shù)學(xué)模型由此可知，運輸問題具有下述特點：

(1)約束條件系數(shù)矩陣的元素等于0或1；

(2)約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(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)；(3)解中非零變量xij的個數(shù)不能大于(m+n-1)個，原因是運輸問題中雖有(m+n)個結(jié)構(gòu)約束條件，但由于總產(chǎn)量等于總銷量，故只有(m+n-1)個結(jié)構(gòu)約束條件是線性獨立的；(4)為使迭代順利進行，基變量的個數(shù)在迭代過程中保持為(m+n-1)個。運輸問題解的每一個分量，都唯一對應(yīng)其運輸表中的一個格填有數(shù)字的格或空格一、運輸問題及其數(shù)學(xué)模型銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116826A2210391010A38511622148銷量814121448下表給出了例1的一個解。一、運輸問題及其數(shù)學(xué)模型二、表上作業(yè)法表上作業(yè)法是一種迭代法，迭代步驟為：

1、先按某種規(guī)則找出一個初始解(初始調(diào)運方案)；

2、再對現(xiàn)行解作最優(yōu)性判別；

3、若這個解不是最優(yōu)解，就在運輸表上對它進行調(diào)整改進，得出—個新解；

4、再判別，再改進；

5、直至得到運輸問題的最優(yōu)解為止。迭代過程中得出的所有解都要求是運輸問題的基可行解。例1：銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448二、表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量81412144882101486所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝246二、表上作業(yè)法1、初始基可行解－－最小元素法在滿足約束條件下盡可能的給最左上角的變量最大值.銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214488864814所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝3721、初始基可行解－－西北角法二、表上作業(yè)法沃格爾法計算步驟：1)分別算出各行、各列的罰數(shù)。2)從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進行運量調(diào)整。3)對剩余行、列再分別計算各行、列的差額。返回1)、2)。二、表上作業(yè)法1、初始基可行解－－沃格爾法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量81412144814所以，初始基可行解為：……目標(biāo)函數(shù)值Z＝244881224二、表上作業(yè)法4-4=03-2=16-5=14-2=210-5=54-3=19-6=3018-6=24-2=24-3=19-6=3銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448821014861211012-1二、表上作業(yè)法2、解的最優(yōu)性檢驗－－閉回路法某空格的檢驗數(shù)是以該空格為第一個頂點，某回路的奇數(shù)頂點運價和減去其偶數(shù)頂點運價和。原問題設(shè)其對偶變量為：2、解的最優(yōu)性檢驗－－對偶變量法二、表上作業(yè)法對偶問題:考慮原問題變量xj的檢驗數(shù)為：二、表上作業(yè)法假設(shè)已得到一個基可行解，其基變量為：則有：s=m+n-1則運輸問題變量xij的檢驗數(shù)為：二、表上作業(yè)法方程組有m+n-1個方程。因為運輸表中每行和每列均有基變量，因此上面方程組含有全部m+n個對偶變量。故解不唯一，其解稱為位勢。若上述方程的某組解滿足對偶問題的所有條件，即：此時，原問題與對偶問題均可行，故達到最優(yōu)。其解分別為：二、表上作業(yè)法例：銷地產(chǎn)地B1B2B3B4產(chǎn)量UiA141241116A22103910A38511622銷量814121448Vj82101486二、表上作業(yè)法10-429310121-11012改進的方法是在運輸表中找出這個空格對應(yīng)的閉回路，在滿足所有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點的運輸量，以得到另一個更好的基可行解。3、解的改進－閉回路調(diào)整法二、表上作業(yè)法解改進的具體步驟(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數(shù)頂點，沿閉回路的順(或逆)時針方向前進，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的頂點(格子)，以該格中的變量為換出變量；(4)以換出變量的運輸量為調(diào)整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減去這一數(shù)值，從而得出一新的運輸方案。該運輸方案的總運費比原運輸方案減少，改變量等于換出變量的檢驗數(shù)。然后，再對得到的新解進行最優(yōu)性檢驗，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。二、表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例：821014861211012-1二、表上作業(yè)法min(6,2)=22-2=00+2=26-2=410+2=12銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例：821214840229121由于所有非基變量的檢驗數(shù)全非負(fù)，故這個解為最優(yōu)解。又由于非基變量有零檢驗數(shù)，所以有無窮多最優(yōu)解。二、表上作業(yè)法練習(xí)題銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414A28427278136A35910619613銷量22131213二、表上作業(yè)法練習(xí)題練習(xí)題銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414557A284272781369A35910619-11-3613銷量22131213二、表上作業(yè)法練習(xí)題練習(xí)題銷地產(chǎn)地B1B2B3B4產(chǎn)量A16753141455-4A284272721312-2A35910619681113銷量22131213二、表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531415513A2842727213122A35910619198114銷量22131213銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314113A284272721312A3591061919銷量22131213答案二、表上作業(yè)法1）若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負(fù)，在繼續(xù)進行迭代時，取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取小于零的檢驗數(shù)中最小者對應(yīng)的變量為換入變量。

2）當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重(無窮多)最優(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，以表明其為基變量。二、表上作業(yè)法三、運輸問題的進一步討論上一節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上，在很多運輸問題中，總產(chǎn)量不等于總銷量。

（Ⅰ）表上作業(yè)法——以產(chǎn)銷平衡為前提。1、產(chǎn)銷不平衡的運輸問題三、運輸問題的進一步討論2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運價需求量需求地6753842759106

例：假設(shè)供應(yīng)量大于需求量+55d5=5假想銷地000s3=24三、運輸問題的進一步討論產(chǎn)大于銷產(chǎn)銷不平衡產(chǎn)銷平衡模型：三、運輸問題的進一步討論設(shè)為Ai的貯存量。將多余物原地貯存。令：三、運輸問題的進一步討論理解：產(chǎn)>銷假想有一銷地j=n+1銷量為運價模型：三、運輸問題的進一步討論銷地產(chǎn)地B1B2…BnBn+1（貯存）產(chǎn)量A1C11C12…C1n0a1x11x12…x1nx1,n+1A2C12C22…C2n0a2x21x22…x2nx2,n+1……..………………………AmC1mC2m…Cmn0amxm1xm2…xmnxm,n+1銷量b1b2…bmΣa-Σb三、運輸問題的進一步討論例：某市有三個造紙廠A1，A2，A3，其紙的產(chǎn)量分別為8，5和9個單位，有4個集中用戶B1，B2，B3，B4，其需用量分別為4，3，5和6個單位。由各造紙廠到各用戶的單位運價如表3—15所示，請確定總運費最少的調(diào)運方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1312348A2112595A367159銷量4356三、運輸問題的進一步討論解：由于總產(chǎn)量22大于總銷量18，故本問題是個產(chǎn)銷不平衡運輸問題。增加一假想銷地B5，用表上作業(yè)法求解。銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A13123408A21125905A3671509銷量43564三、運輸問題的進一步討論銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A13123408418634A211259050302-8A3671509-2954-4銷量43564銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A1312340844A21125905032A367150954銷量43564三、運輸問題的進一步討論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)濟。因此，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進去。三、運輸問題的進一步討論2、有轉(zhuǎn)運的運輸問題轉(zhuǎn)運量t1t2t3t4t5t6t7A2A3A1a2=27a3=19a1=14供應(yīng)量需求量B2B3B4B1a5=0a6=0a4=0a7=0A2A3A1b4=22b5=13b6=12b7=13B2B3B4B1b1=0b2=0b3=0xij轉(zhuǎn)運量t1t2t3t4t5t6t7假設(shè)單位運轉(zhuǎn)費用為ti，則線性規(guī)劃模型為：三、運輸問題的進一步討論第二項為常數(shù)，對求解結(jié)果無影響，可去掉。模型變?yōu)橄铝行问剑哼@是一個產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型?？梢粤谐銎溥\價表，用表上作業(yè)法求解。銷地產(chǎn)地A1A2A3B1B2B3B4產(chǎn)量A1A2A3B1B2B3B4銷量其運價表形式如下（注意其中對角線上的運價值）：建立一般意義上的數(shù)學(xué)模型，設(shè)：ai：第i個產(chǎn)地的產(chǎn)量(凈供應(yīng)量)；bj：第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=-cia1…a5b1…b5Qc1…c5c11…c55例：如圖所示是一個運輸系統(tǒng)，它包括二個產(chǎn)地（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)運輸方案。銷地產(chǎn)地A1A2B3C4C5產(chǎn)量A1A2B3C4C5銷量銷地產(chǎn)地A1A2B3C4C5產(chǎn)量A1-4532M60A25-12M490B332-35550C42M5-3650C5M456-550銷量5050508070運用最小元素法，求初始運輸方案，如下表：最優(yōu)運輸方案如下表：302020一、回答問題1、在運輸問題數(shù)學(xué)模型中，為什么模型的(m+n)個約束中最多只有(m+n-1)個是獨立的?2．試述用最小元素法確定運輸問題的初始基可行解的基本思路。3．如何用閉回路法求檢驗數(shù)？4．沃格爾法的基本思想是什么？什么是罰數(shù)？5．在解的改進過程中，如何確定調(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，Σ

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)量和銷地的銷量均為整數(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,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模型為：四、運用舉例由于不能缺貨，并考慮到是不平衡問題（虛設(shè)收點5）建立如下運輸表格四、運用舉例10410203525101014321最小費用為：w*=7730(萬元）123451108109.5111112.50252M111112.51140353MM110111.50304MMM1130101015252030四、運用舉例例2某航運公司承擔(dān)六個港口城市A.B.C.D.E.F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)見表：航線起點城市終點城市每天航線1ED32BC23AF14DB1每條航線使用相同型號的船只，各城市間的航程天數(shù)如表：四、運用舉例每條船只每次裝卸貨物的時間各需一天。？該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求。終點起點ABCDEFA0121477B1031388C23015557851703F7852030四、運用舉例ABCDEF2311173713每天載貨航程所需的船只數(shù)：每天到達數(shù)每天需求數(shù)余缺數(shù)ABCDEF四、運用舉例分析：1）所需船只可分為兩部分：載貨航程所需的船只數(shù)、各港口間調(diào)度所需的船只數(shù)。

2）每天載貨航程所需的船只數(shù)：

3）每天各港口調(diào)度所需船只數(shù)。