版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第三章 運(yùn)輸問題,,2,本章內(nèi)容,運(yùn)輸問題及其數(shù)學(xué)模型用表上作業(yè)法求解運(yùn)輸問題運(yùn)輸問題的進(jìn)一步討論應(yīng)用問題舉例,問題的提出: 一般的運(yùn)輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地,在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知,并知道各地之間的運(yùn)輸單價的前提下,如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案。,§1運(yùn)輸問題及其數(shù)學(xué)模型,§1運(yùn)輸問題及其數(shù)學(xué)模型,1.經(jīng)典運(yùn)輸問題——單一品
2、種物資的運(yùn)輸調(diào)度問題,§1運(yùn)輸問題及其數(shù)學(xué)模型,網(wǎng)絡(luò)表示:,,,,5,000,,2,500,,6,000,,,,,,,,,,,,,,,如果運(yùn)輸問題的總產(chǎn)量等于其總銷量,即有 則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題;反之,稱產(chǎn)銷不平衡運(yùn)輸問題。,產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型可表示如下:,§1運(yùn)輸問題及其數(shù)學(xué)模型,二、運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn):運(yùn)輸問題一定
3、有最優(yōu)解;基變量的個數(shù)=m+n-1運(yùn)輸問題約束條件的系數(shù)矩陣:,§1運(yùn)輸問題及其數(shù)學(xué)模型,運(yùn)輸問題具有下述特點(diǎn):(1) 約束條件系數(shù)矩陣的元素等于0或1;(2) 約束條件系數(shù)矩陣的每一列有兩個非零元素,這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次,在后n個約束方程中也出現(xiàn)一次。,§1運(yùn)輸問題及其數(shù)學(xué)模型,對產(chǎn)銷平衡運(yùn)輸問題,除上述兩個特點(diǎn)外,還有以下特點(diǎn):(1) 所有結(jié)構(gòu)約
4、束條件都是等式約束;(2) 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。,§1運(yùn)輸問題及其數(shù)學(xué)模型,例1 某部門有3個生產(chǎn)同類產(chǎn)品的工廠(產(chǎn)地),生產(chǎn)的產(chǎn)品由4個銷售點(diǎn)(銷地)出售,各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量(假定單位均為t)以及各工廠到各銷售點(diǎn)的單位運(yùn)價(元/t)示于表3-2中,要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小?,,表3-2,4,2,8,12,5,4,10,11,3,9,6,11,§1運(yùn)輸問
5、題及其數(shù)學(xué)模型,該問題的數(shù)學(xué)模型:,§1運(yùn)輸問題及其數(shù)學(xué)模型,12,本章內(nèi)容,運(yùn)輸問題及其數(shù)學(xué)模型用表上作業(yè)法求解運(yùn)輸問題運(yùn)輸問題的進(jìn)一步討論應(yīng)用問題舉例,一、表上作業(yè)法的基本思想和步驟:1.基本思想:同單純形法的基本思想,§2 用表上作業(yè)法求解運(yùn)輸問題,二、表上作業(yè)法的步驟(1)尋找初始基可行解;最小元素法、西北角法、沃格爾法(2)求出非基變量檢
6、驗(yàn)數(shù)(空格檢驗(yàn)數(shù)),判斷是否為最優(yōu)解;閉回路法、位勢法(3)換基改進(jìn),找到新的基可行解閉回路調(diào)整法(4 )重復(fù)(2)(3),§2 用表上作業(yè)法求解運(yùn)輸問題,1.最小元素法 從運(yùn)價最小的格開始,在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價從小到大順序填數(shù)。若某行(列)的產(chǎn)量(銷量)已滿足,則把該行(列)的其他格劃去。如此進(jìn)行下去,直至得到一個基本可行解。,尋找初始基可行
7、解,,,4,2,8,5,10,11,12,3,4,6,9,11,1.最小元素法,總費(fèi)用 z= =10×4+6×11+8×2+2×3+14×5+8×6=246,尋找初始基可行解,2.西北角法 從西北角(左上角)格開始,在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行(列)標(biāo)下一
8、格的數(shù)。若某行(列)的產(chǎn)量(銷量)已滿足,則把該行(列)的其他格劃去。如此進(jìn)行下去,直至得到一個基本可行解。,尋找初始基可行解,,,2.西北角法,總費(fèi)用 z= =8×4+8×12+6×10+4×3+8×11+14×6=372,尋找初始基可行解,3.沃格爾法罰數(shù)=次小
9、費(fèi)用-最小費(fèi)用找出最大的罰數(shù)行或列所對應(yīng)的最小費(fèi)用優(yōu)先安排。重復(fù)計算步驟1和2,尋找初始基可行解,,,,3.沃格爾法,,4,10,12,11,3,4,6,9,11,2,8,5,2,0,1,5,1,3,2,2,1,0,1,1,3,2,1,14,,8,,8,,,1,0,2,總費(fèi)用 z= =244,尋找初始基可行解,最優(yōu)性檢驗(yàn)
10、就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同,即計算檢驗(yàn)數(shù)。由于目標(biāo)要求極小,因此,當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時該調(diào)運(yùn)方案就是最優(yōu)方案;否則就不是最優(yōu),需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法:閉回路法和對偶變量法。,解的最優(yōu)性檢驗(yàn),1.閉回路法 閉回路:從空格出發(fā),遇到數(shù)字格可以旋轉(zhuǎn)90度,最后回到空格所構(gòu)成的回路; 原理:利用檢驗(yàn)數(shù)的經(jīng)濟(jì)含義; 檢驗(yàn)數(shù):非基變量增加一個單位引起的成
11、本變化量。 當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時,現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案,因?yàn)榇藭r對現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。 閉回路法的主要缺點(diǎn)是:當(dāng)變量個數(shù)較多時,尋找閉回路以及計算兩方面都會產(chǎn)生困難。,解的最優(yōu)性檢驗(yàn),1.閉回路法(結(jié)合最小元素法的初始解),,解的最優(yōu)性檢驗(yàn),8,14,10,2,6,8,檢驗(yàn)數(shù)σ11=c11-c21+c23-c13=4-2+3-4=1σ24=c24-c1
12、4+c13-c23=9-11+4-3=-1<0,故知該最小元素法的解不是最優(yōu)解,位勢:設(shè)對應(yīng)基變量xij的m+n-1個i、j ,存在ui,vj 滿足ui+vj=cij,i=1,2,..,m; j=1,2 ,… ,n稱這些ui , vj 為該基本可行解對應(yīng)的位勢。,解的最優(yōu)性檢驗(yàn),2.對偶變量法(位勢法),解的最優(yōu)性檢驗(yàn),2.對偶變量法(位勢法),設(shè)對偶變量向量為,解的最優(yōu)性檢驗(yàn),對偶規(guī)劃為,解
13、的最優(yōu)性檢驗(yàn),,檢驗(yàn)數(shù):目標(biāo)函數(shù)的系數(shù)減去對偶變量之和,原問題檢驗(yàn)數(shù):σij=cij-(ui+vj),特別對于m+n-1個基變量,有 σij=0,σj = C j- CBB-1 Pj = Cj - Y Pj σij = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, …,um, v1, v2, …,vn) Pij
14、 = Cij - ( ui+ vj ) 當(dāng)xij 為基變量時 σij = Cij - ( ui+ vj )=0 由此,任選一個對偶變量為0,可求出其余所有的ui, vj 。 再根據(jù)σij = Cij - ( ui+ vj )求出所有非基變量的檢驗(yàn)數(shù)。,解的最優(yōu)性檢驗(yàn),解的最優(yōu)性檢驗(yàn),表3-9,1.增加一位勢列和位勢行并計算位勢
15、,,其中,解的最優(yōu)性檢驗(yàn),2.計算檢驗(yàn)數(shù),(+2),4.解的改進(jìn)——閉回路調(diào)整法,解的最優(yōu)性檢驗(yàn),改進(jìn)的方法是在運(yùn)輸表中找出這個空格對應(yīng)的閉回路Lij,在滿足所有約束條件的前提下,使xij盡量增大并相應(yīng)調(diào)整此閉回路上其他頂點(diǎn)的運(yùn)輸量,以得到另一個更好的基可行解。,,,,,(-2),(+2),(-2),5、需要注意的問題 (一)多個空格(非基變量)的檢驗(yàn)數(shù)為負(fù),任一個都可作為換入變量。一般σij<0中
16、最小的對應(yīng)變量作為換入變量。 (二)最優(yōu)解時,如果有某非基變量的檢驗(yàn)數(shù)為0,則說明該運(yùn)輸問題有無窮多最有解。 (三)退化解。,解的最優(yōu)性檢驗(yàn),本章內(nèi)容,運(yùn)輸問題及其數(shù)學(xué)模型用表上作業(yè)法求解運(yùn)輸問題運(yùn)輸問題的進(jìn)一步討論應(yīng)用問題舉例,§3運(yùn)輸問題進(jìn)一步討論,產(chǎn)銷不平衡的運(yùn)輸問題有轉(zhuǎn)運(yùn)的運(yùn)輸問題,1.當(dāng)產(chǎn)大于銷時,即,產(chǎn)銷不平衡問題,平衡后的數(shù)學(xué)模型為:,加入假想銷地(假想倉庫),銷量為
17、 ,由于實(shí)際并不運(yùn)送,它們的運(yùn)費(fèi)為 = 0;,產(chǎn)銷不平衡問題,2.當(dāng)銷大于產(chǎn)時,即,加入一個虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資;它的產(chǎn)量為,產(chǎn)銷不平衡問題,有轉(zhuǎn)運(yùn)的運(yùn)輸問題,,表3-15 有轉(zhuǎn)運(yùn)輸問題的運(yùn)輸表,有轉(zhuǎn)運(yùn)的運(yùn)輸問題,有轉(zhuǎn)運(yùn)的運(yùn)輸問題,表3-16 有轉(zhuǎn)運(yùn)輸問題的運(yùn)價表,,例 5,有轉(zhuǎn)運(yùn)的運(yùn)輸問題,圖3-3示出了一個運(yùn)輸系統(tǒng),它包括兩個產(chǎn)地(①和②)、兩個銷地(④和⑤)及一個中間轉(zhuǎn)運(yùn)站(③),各
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 運(yùn)籌學(xué)胡運(yùn)權(quán)版第三章運(yùn)輸問題課后習(xí)題答案
- 運(yùn)籌學(xué)(胡運(yùn)權(quán)版)第三章運(yùn)輸問題課后習(xí)題答案
- 管理運(yùn)籌學(xué)-第三章運(yùn)輸問題
- 運(yùn)籌學(xué)課件第三章----運(yùn)輸問題
- 運(yùn)籌學(xué)第三章運(yùn)輸問題課件
- 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版-胡運(yùn)權(quán)第三章
- 運(yùn)籌學(xué)教案(胡運(yùn)權(quán)版)
- 管理運(yùn)籌學(xué)第四版第三章習(xí)題答案
- 運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課后答案,運(yùn)籌作業(yè)
- 《運(yùn)籌學(xué)教程》胡云權(quán) 第五版 運(yùn)籌學(xué)復(fù)習(xí)
- 《運(yùn)籌學(xué)》胡運(yùn)權(quán)-第4版-第二章--線性規(guī)劃的對偶理論及靈敏度分析
- 運(yùn)籌學(xué)教程第二版胡運(yùn)權(quán)課后答案精校版
- 運(yùn)籌學(xué)-運(yùn)輸問題
- 運(yùn)籌學(xué)教程第二、三版課后答案胡運(yùn)權(quán)清華大學(xué)黃皮版
- 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版胡運(yùn)權(quán)課后答案
- 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版胡運(yùn)權(quán)課后答案
- 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版胡運(yùn)權(quán)課后答案
- 運(yùn)籌學(xué)(第三版)
- 第3章-運(yùn)籌學(xué)對偶問題
- 第三章-肌-學(xué)
評論
0/150
提交評論