運籌學-3運輸問題.ppt

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

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

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

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

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

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

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

8、小運費調(diào)運。,在求一個可行解的過程中注意到包含在矩陣模型中的成本信息。它通過建立“罰數(shù)”來達到此目的。罰數(shù)表示對一方格不進行分配的可能的成本罰款。,步 驟：,Step1. 給定一個平衡的運輸矩陣，分別計算行罰數(shù)和列罰數(shù)；,Step2. 確定具有最大罰數(shù)的行或列，然后在罰數(shù)所在行（或 列）中選擇最小價格元素，將可能的最大單位數(shù)分配 給此方格，將相應(yīng)的行（或列）的供應(yīng)量和需求量減 去這個量，并劃去完全滿足的行（或列）；,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)性檢驗,（1）閉回路法 以確定了初始調(diào)運方案的作業(yè)表為基礎(chǔ)，以一個非基變量作為起始頂點，尋求閉回路。 該閉回路的特點是：除了起始頂點是非基變量外，其他頂點均為基變量（對應(yīng)著填上數(shù)值的格）。 可以證明，如果對閉回路的方向不加區(qū)別，對于每一個非基變量而言，以其為起點的閉回路存在且唯一。,判別的方法是計算空格(非基變量)的檢驗數(shù)，因運輸問題的目標函數(shù)是要求實現(xiàn)最小化，故當所有的檢驗數(shù)0時，為最優(yōu)解。 常用兩種求空格檢驗數(shù)的方法為：閉回路法和位勢法。,對調(diào)運方案中每一空格按閉回路法求出檢驗數(shù) 若所有檢驗數(shù)大于等于零，則此方案為最優(yōu)方案； 若存在檢驗數(shù)小于零，則需對此方案進行調(diào)整。,1,

10、2,1,-1,10,12,不是最優(yōu)解,經(jīng)濟含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標函數(shù)值的變化量。,（2）對偶變量法（位勢法）,定理：任何基可行解對應(yīng)的方程組都有解。,位勢：方程組的任意一組解叫做位勢。,對于運輸問題的一個基可行解，用位勢法得到的檢驗數(shù)是唯一的（位勢可能不同）。,對基變量，反復(fù)利用公式,求出空格的檢驗數(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) 計算檢驗數(shù)，并以ij0 檢驗，或用(ui+vj) cij 0 檢驗。,cij,(ui+vj),表中還有負數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。,ij,0,-1,-5,1,2,1,-1,10,12,10,2,9,3,3. 解的改進閉回路調(diào)整法,當 ij 0 時，調(diào)運方案需要改進,(-1),(+1),(-1),(+1),閉回路的偶數(shù)頂點的最小值,偶次頂點 “調(diào)整量”；奇次頂點 “ +調(diào)整量”,ij 0 得到最優(yōu)解,4. 幾點說明,（1） 換入變量的選擇,若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)進行迭代時，取它們中的任一變量為換入變量均可使目標函數(shù)值

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

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

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

15、確定的運輸問題,先作如下分析：（1）總產(chǎn)量為180，B1，B4的最低需求量 20+50+35+45=150，這時屬產(chǎn)大于銷；,（2）B1，B4的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn),（3）虛設(shè)一個產(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)某需求地的運價用大M表示，A5到 其他 的運價為零。得到下表的產(chǎn)銷平衡表。,得到這樣的平衡表后，計算得到最優(yōu)方案表。,表中：x131=0是基變量,

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

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