運(yùn)籌學(xué)-3運(yùn)輸問題.ppt

1、運(yùn)籌學(xué)第三章運(yùn)輸問題,張 紅 歷,本章內(nèi)容,4.應(yīng)用問題舉例,3.運(yùn)輸問題的進(jìn)一步討論,2.表上作業(yè)法,1.運(yùn)輸問題及其數(shù)學(xué)模型,第一節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型,一、運(yùn)輸問題的提出,例：某運(yùn)輸問題的資料如下：,21,二、數(shù)學(xué)模型的一般形式,1. 已知資料如下：,設(shè)某種物品有m個(gè)產(chǎn)地A1，A2，Am，產(chǎn)量 分別是 a1，a2，am個(gè)單位 有n個(gè)銷地B1，B2，Bn，銷量分別為b1， b2，bn個(gè)單位； 從Ai 到Bj運(yùn)輸單位物品 的運(yùn)價(jià)是cij；,2. 運(yùn)輸問題的幾種類型：,產(chǎn)銷平衡問題 產(chǎn)銷不平衡問題 產(chǎn)大于銷 銷大于供,當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：,當(dāng)產(chǎn)大于銷時(shí)，其模型是：,當(dāng)銷大于產(chǎn)時(shí)，其模型

2、是：,三、運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn),（1）運(yùn)輸問題有有限最優(yōu)解。 定理. 運(yùn)輸問題有可行解的充要條件 是：產(chǎn)銷平衡,（2）運(yùn)輸問題約束條件的系數(shù)矩陣,記變量xij對(duì)應(yīng)A中向量為 Aij,矩陣的元素均為1或0； 每一列只有兩個(gè)元素為1，其余元素均為0； 列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中兩個(gè)元素1分別處于第i行和第m+j行。 將該矩陣分塊，特點(diǎn)是：前m行構(gòu)成m個(gè)mn階矩陣，而且第k個(gè)矩陣只有第k行元素全為1，其余元素全為0（k=1，m）；后n行構(gòu)成m個(gè)n階單位陣。,（3）運(yùn)輸問題的解,定義1. 閉回路,閉回路是能折成 形式的變量組集合。其中 i1 , i2 , ， is

3、 互不相同，j1 , j2 , ， js 互不相同。每個(gè)變量稱為閉回路的頂點(diǎn)，連接閉回路相鄰兩頂點(diǎn)的直線段叫做閉回路的邊。,例：x11，x12，x32，x34，x24，x21 就是一個(gè)閉回路。,閉回路的特點(diǎn)：,1.每一個(gè)頂點(diǎn)都有兩條邊與之相接，一條是水平的，一條是鉛直的； 2.每一個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)，與之相鄰的兩個(gè)頂點(diǎn)，分別在它的水平和鉛直方向； 3.每一行（列）如果有閉回路的頂點(diǎn)，則必出現(xiàn)一對(duì)，頂點(diǎn)總個(gè)數(shù)是偶數(shù)； 4.從任何一個(gè)頂點(diǎn)出發(fā)，沿任何一個(gè)方向到它的位于同一行或同一列的相鄰 頂點(diǎn)，如此繼續(xù)下去，經(jīng)過閉回路的所有頂點(diǎn)和邊，最后又回到開始的頂點(diǎn)， 但每一定和邊在閉回路中只經(jīng)過一次。,有關(guān)閉

4、回路的一些重要定理,定理1: 設(shè) 是一個(gè)閉回路，則該閉回路中的變量所對(duì)應(yīng)的系數(shù)列向量 具有下面的關(guān)系：,定理2: 若變量組 中有一個(gè)部分組構(gòu)成閉回路，則該變量組對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。,定理3 r個(gè)變量 對(duì)應(yīng)的系數(shù)列向量線性無關(guān)充要條件是該變量組不包含閉回路。,推論：m+n-1 個(gè)變量 構(gòu)成基的充要條件是它不含閉回路。,第二節(jié) 表上作業(yè)法,一、表上作業(yè)法的基本思想,尋找初始基本可行解 給出基本可行解為最優(yōu)解的判別準(zhǔn)則 給出從目前基本可行解轉(zhuǎn)移到新基本 可行解的方法,Review,Step4.重復(fù)2. 3，直到找到最優(yōu)解為止。,二、表上作業(yè)法的步驟,Step1.找出初始基本可行解（在m*n產(chǎn)銷

5、平衡表上尋找初始調(diào)運(yùn)方案，一般m+n-1個(gè)數(shù)字格），用最小元素法、西北角法、伏格爾法；,Step2.求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用閉回路或位勢(shì)法計(jì)算；,Step3.改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；,1.求初始方案（尋找初始基可行解）,Step1. 選擇一個(gè)xij，,對(duì)xij的選擇采用不同的規(guī)則就形成各種不同的方法，比如每次總是在作業(yè)表剩余的格子中選擇運(yùn)價(jià)（或運(yùn)距）最小者對(duì)應(yīng)的xij，則構(gòu)成最小元素法，若每次都選擇左上角格子對(duì)應(yīng)的xij就形成西北角法（也稱左上角法）。,Step2. 調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別

6、減去xij的值，若ai-xij=0，則劃去產(chǎn)地Ai所在的行，即該產(chǎn)地產(chǎn)量已全部運(yùn)出無剩余，而銷地Bj尚有需求缺口bj-ai；若bj-xij =0，則劃去銷地Bj所在的列，說明該銷地需求已得到滿足，而產(chǎn)地Ai尚有存余量ai-bj； Step3.當(dāng)作業(yè)表中所有的行或列均被劃去，說明所有的產(chǎn)量均已運(yùn)到各個(gè)銷地，需求全部滿足，xij的取值構(gòu)成初始方案。否則，在作業(yè)表剩余的格子中選擇下一個(gè)決策變量，返回步驟（2）。,按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取值非負(fù)，且總數(shù)是m+n-1個(gè)，因此構(gòu)成運(yùn)輸問題的基本可行解。,從單位運(yùn)價(jià)表中選最小元素，然后比較產(chǎn)量和銷量，如果產(chǎn)銷，則劃去列，若銷產(chǎn)，則劃去

7、行； 修改ai或bj的值； 再從劃去一列和一行后的單位運(yùn)價(jià)表中找最小元素，繼續(xù)下去； 直到單位運(yùn)價(jià)表的所有元素劃去為止。,步 驟：,最小元素法,例,3,1,4,6,3,3,西北角法,基本思想： 優(yōu)先滿足運(yùn)輸表中左上角（即西北角）空格的供銷要求。,3,4,2,2,3,3,6,伏格爾法（Vogel 逼近法. VAM）,最小元素法的缺點(diǎn)：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其它處要多花幾倍的運(yùn)費(fèi)。若不能按最小運(yùn)費(fèi)就近供應(yīng)，就選擇次最小運(yùn)費(fèi)，差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。 每行（列）中次最小價(jià)格元素與最小價(jià)格元素的數(shù)值之差，稱為該行（列）的行（列）罰數(shù)最大差額費(fèi)用。 對(duì)罰數(shù)最大處，采用最

8、小運(yùn)費(fèi)調(diào)運(yùn)。,在求一個(gè)可行解的過程中注意到包含在矩陣模型中的成本信息。它通過建立“罰數(shù)”來達(dá)到此目的。罰數(shù)表示對(duì)一方格不進(jìn)行分配的可能的成本罰款。,步 驟：,Step1. 給定一個(gè)平衡的運(yùn)輸矩陣，分別計(jì)算行罰數(shù)和列罰數(shù)；,Step2. 確定具有最大罰數(shù)的行或列，然后在罰數(shù)所在行（或 列）中選擇最小價(jià)格元素，將可能的最大單位數(shù)分配 給此方格，將相應(yīng)的行（或列）的供應(yīng)量和需求量減 去這個(gè)量，并劃去完全滿足的行（或列）；,Step3. 重復(fù)step1，step2，直到給出初始解為止。,2 5 1 3,6,2 1 3,2 1 2, 1 2, 2,Z=53+210+31 +1 8+64+ 35 = 85

9、,2. 解的最優(yōu)性檢驗(yàn),（1）閉回路法 以確定了初始調(diào)運(yùn)方案的作業(yè)表為基礎(chǔ)，以一個(gè)非基變量作為起始頂點(diǎn)，尋求閉回路。 該閉回路的特點(diǎn)是：除了起始頂點(diǎn)是非基變量外，其他頂點(diǎn)均為基變量（對(duì)應(yīng)著填上數(shù)值的格）。 可以證明，如果對(duì)閉回路的方向不加區(qū)別，對(duì)于每一個(gè)非基變量而言，以其為起點(diǎn)的閉回路存在且唯一。,判別的方法是計(jì)算空格(非基變量)的檢驗(yàn)數(shù)，因運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，故當(dāng)所有的檢驗(yàn)數(shù)0時(shí)，為最優(yōu)解。 常用兩種求空格檢驗(yàn)數(shù)的方法為：閉回路法和位勢(shì)法。,對(duì)調(diào)運(yùn)方案中每一空格按閉回路法求出檢驗(yàn)數(shù) 若所有檢驗(yàn)數(shù)大于等于零，則此方案為最優(yōu)方案； 若存在檢驗(yàn)數(shù)小于零，則需對(duì)此方案進(jìn)行調(diào)整。,1,

10、2,1,-1,10,12,不是最優(yōu)解,經(jīng)濟(jì)含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個(gè)單位運(yùn)量而成為基變量時(shí)目標(biāo)函數(shù)值的變化量。,（2）對(duì)偶變量法（位勢(shì)法）,定理：任何基可行解對(duì)應(yīng)的方程組都有解。,位勢(shì)：方程組的任意一組解叫做位勢(shì)。,對(duì)于運(yùn)輸問題的一個(gè)基可行解，用位勢(shì)法得到的檢驗(yàn)數(shù)是唯一的（位勢(shì)可能不同）。,對(duì)基變量，反復(fù)利用公式,求出空格的檢驗(yàn)數(shù)。,求出位勢(shì)后，就可由公式,成本表Cij,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10,u10 v12 u2 1 v2 9 u3 5 v3 3 v4 10,(ui+vj

11、),按ij=cij(ui+vj) 計(jì)算檢驗(yàn)數(shù)，并以ij0 檢驗(yàn)，或用(ui+vj) cij 0 檢驗(yàn)。,cij,(ui+vj),表中還有負(fù)數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。,ij,0,-1,-5,1,2,1,-1,10,12,10,2,9,3,3. 解的改進(jìn)閉回路調(diào)整法,當(dāng) ij 0 時(shí)，調(diào)運(yùn)方案需要改進(jìn),(-1),(+1),(-1),(+1),閉回路的偶數(shù)頂點(diǎn)的最小值,偶次頂點(diǎn) “調(diào)整量”；奇次頂點(diǎn) “ +調(diào)整量”,ij 0 得到最優(yōu)解,4. 幾點(diǎn)說明,（1） 換入變量的選擇,若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)進(jìn)行迭代時(shí)，取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值

12、得到改善，但通常取ij 0中最小者對(duì)應(yīng)的變量為換入變量。,（2） 無窮多最優(yōu)解,當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí)，如果某個(gè)非基變量的檢驗(yàn)數(shù)為0，說明該問題有無窮多最優(yōu)解。以此格為調(diào)入格，作閉回路，經(jīng)調(diào)整后得另一最優(yōu)解。,（3） 退化,用表上作業(yè)法求解運(yùn)輸問題出現(xiàn)退化時(shí)，在相應(yīng)的格中一定要填一個(gè)0，以表示此格為數(shù)字格。,當(dāng)確定初始解時(shí)，若在（i，j）格填入某數(shù)字后，出現(xiàn) ai = bj，這時(shí)在在運(yùn)價(jià)表上相應(yīng)的要?jiǎng)澣ヒ恍泻鸵涣?，需特別注意的是：要在劃去的那行和那列的任一空格處填一個(gè)“0”，這樣才能保證運(yùn)輸表上有m+n-1個(gè)數(shù)字格。,在用閉回路法調(diào)整時(shí)，當(dāng)閉回路上奇頂點(diǎn)有幾個(gè)相同的最小值時(shí)，調(diào)整后只能有一

13、個(gè)空格，其余均要保留數(shù)“0”，以保證m+n1個(gè)基變量要求的需要。,已知資料如下表所示，問如何供電能使總的輸電費(fèi)用為最?。?電力供需表,單位輸電費(fèi)用,作業(yè)：,初始方案,100,100,50,250,400,100,單位輸電費(fèi)用,電力供需表,成本表,(ui+vj),調(diào)運(yùn)方案,ij,- (ui+vj),=,cij,成本表,調(diào)運(yùn)方案,(ui+vj),ij,- (ui+vj),=,cij,C=5200,第三節(jié) 運(yùn)輸問題的進(jìn)一步討論,一、產(chǎn)銷不平衡的運(yùn)輸問題,增加虛擬銷地,增加虛擬產(chǎn)地,產(chǎn)銷平衡的運(yùn)輸問題,對(duì)應(yīng)的運(yùn)距（或運(yùn)價(jià)） ？,1、產(chǎn)大于銷：模型,先將原問題變成平衡問題，需假設(shè)一個(gè)銷地Bn+1 ，該銷

14、地的總需要量為 ，即在運(yùn)輸表上增加一虛擬列,相應(yīng)的單位運(yùn)價(jià)為0。,解決方法,例題：,因?yàn)橛校?所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。,表中A2不可達(dá)B1，用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷量為b5=180160=20的銷地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列,這樣可得新的運(yùn)價(jià)表：,下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個(gè)單位沒有運(yùn)出。,將原問題變成平衡問題，需假設(shè)一個(gè)產(chǎn)地Am+1 ，該產(chǎn)地的產(chǎn)量為 ，即在運(yùn)輸表上增加一虛擬行,相應(yīng)的單位運(yùn)價(jià)為0。,2、銷大于產(chǎn),解決方法,上例中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。,需求量不

15、確定的運(yùn)輸問題,先作如下分析：（1）總產(chǎn)量為180，B1，B4的最低需求量 20+50+35+45=150，這時(shí)屬產(chǎn)大于銷；,（2）B1，B4的最高需求是60+70+35+45=210，這時(shí)屬銷大于產(chǎn),（3）虛設(shè)一個(gè)產(chǎn)地A5，產(chǎn)量是210180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。,（4）將B1與B2各分成兩部分 的需求量是20， 的需求量是40， 的需求量分別是50與20，因此 必須由A1，A4供應(yīng)， 可由 A1、A5供應(yīng)。,（5）上述A5不能供應(yīng)某需求地的運(yùn)價(jià)用大M表示，A5到 其他 的運(yùn)價(jià)為零。得到下表的產(chǎn)銷平衡表。,得到這樣的平衡表后，計(jì)算得到最優(yōu)方案表。,表中：x131=0是基變量,

16、說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實(shí)際收到產(chǎn)品數(shù)量分別是50，50，35和45個(gè)單位。,二、有轉(zhuǎn)運(yùn)的運(yùn)輸問題,是所調(diào)運(yùn)的物資不是由產(chǎn)地直接運(yùn)送到銷地，而是經(jīng)過若干中轉(zhuǎn)站送達(dá)。,特點(diǎn),把問題中所有的產(chǎn)地、中轉(zhuǎn)站和銷地都既看作產(chǎn)地，又都看作銷地，把“轉(zhuǎn)運(yùn)問題”變成擴(kuò)大后的產(chǎn)銷平衡的運(yùn)輸問題處理。,求解思路,求解轉(zhuǎn)運(yùn)問題的步驟,Step1：將產(chǎn)地、轉(zhuǎn)運(yùn)點(diǎn)、銷地重新編排，轉(zhuǎn)運(yùn)點(diǎn)既作為產(chǎn)地又作為銷地； Step2:各地之間的運(yùn)距（或運(yùn)價(jià)）在原問題運(yùn)距（運(yùn)價(jià)）表基礎(chǔ)上進(jìn)行擴(kuò)展：從一地運(yùn)往自身的單位運(yùn)距（運(yùn)價(jià)）記為零，不存在運(yùn)輸線路的則記為M（一個(gè)足夠大的正數(shù)）； S

17、tep3:由于經(jīng)過轉(zhuǎn)運(yùn)點(diǎn)的物資量既是該點(diǎn)作為銷地的需求量，又是該點(diǎn)作為產(chǎn)地時(shí)的供應(yīng)量，但事先又無法獲取該數(shù)量的確切值，因此通常將調(diào)運(yùn)總量作為該數(shù)值的上界。 對(duì)于產(chǎn)地和銷地也作類似的處理,第四節(jié) 應(yīng)用問題舉例,有三個(gè)產(chǎn)地A1，A2，A3和三個(gè)銷地B1，B2，B3，各產(chǎn)地至銷地的單位運(yùn)價(jià)見下表，各銷地的需求量分別為10，4，6個(gè)單位。由于客觀條件的限制和銷售需要，產(chǎn)地A1至少要發(fā)出6個(gè)單位的產(chǎn)品，最多只能生產(chǎn)11個(gè)單位； A1必須發(fā)出7個(gè)單位； A3至少要發(fā)出4個(gè)單位。,解：當(dāng) a1= 6，a2=7 時(shí)，,例6（p100),總產(chǎn)量總銷量,在下列不平衡運(yùn)輸問題中，已知三個(gè)收點(diǎn)的需求量一旦不能滿足，就要承擔(dān)缺貨損失費(fèi)。單位物資的缺貨損失費(fèi)分別為4、3 和 7,試建立運(yùn)輸模型。,例8,解：增加虛擬產(chǎn)地 A3,某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)。已知(1)各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)（表1）;(2)各城市間的航行時(shí)間（表2）；（3）所有航線都使用同一種船只，船只每次裝卸的時(shí)間均需1天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿足所有航線的要求。,例9（p101),表1,解： 該公司所需配備船只分兩部分： （1）載貨航程需要的周轉(zhuǎn)船只數(shù),載貨需要 57+10+9+15=