




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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=
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 肝病科護(hù)理課件教學(xué)
- 姑蘇區(qū)小學(xué)數(shù)學(xué)試卷
- 高中一??荚嚁?shù)學(xué)試卷
- 肝動(dòng)脈CT檢查技術(shù)
- 肌力康復(fù)護(hù)理課件
- 設(shè)備檢修規(guī)程培訓(xùn)課件
- 調(diào)音臺(tái)培訓(xùn)課件
- 2025至2030寵物罐頭發(fā)展趨勢(shì)分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- 2024年航天科技校招招聘筆試真題
- 公辦幼兒園中班數(shù)學(xué)試卷
- 安全生產(chǎn)法律法規(guī)匯編(2025版)
- 【MOOC】森林經(jīng)理學(xué)-北京林業(yè)大學(xué) 中國大學(xué)慕課MOOC答案
- 人防卷材防水層工程檢驗(yàn)批質(zhì)量驗(yàn)收記錄表
- 尾礦庫模施袋筑壩工藝在施工中的應(yīng)用
- 中國34個(gè)省級(jí)行政區(qū)輪廓圖
- 人教版三年級(jí)下冊(cè)數(shù)學(xué)(全冊(cè))同步隨堂練習(xí)一課一練
- 肺小結(jié)節(jié)定位和肺段切除規(guī)劃PPT學(xué)習(xí)課件
- 精品專題資料(2022-2023年收藏)國家電網(wǎng)公司智能電網(wǎng)知識(shí)競(jìng)賽題目
- 目錄-初中數(shù)學(xué)浙教版
- 除塵室PLC控制系統(tǒng)的設(shè)計(jì)
- 鋁粉膏水泥發(fā)泡劑發(fā)氣鋁粉制作配方及生產(chǎn)工藝技術(shù)文集
評(píng)論
0/150
提交評(píng)論