運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法

上傳人:mby****80 文檔編號(hào):253392301 上傳時(shí)間:2024-12-12 格式:PPT 頁(yè)數(shù):14 大?。?15KB
收藏 版權(quán)申訴 舉報(bào) 下載
運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法_第1頁(yè)
第1頁(yè) / 共14頁(yè)
運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法_第2頁(yè)
第2頁(yè) / 共14頁(yè)
運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法_第3頁(yè)
第3頁(yè) / 共14頁(yè)

下載文檔到電腦,查找使用更方便

16 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法》由會(huì)員分享,可在線閱讀,更多相關(guān)《運(yùn)籌學(xué)第3章:運(yùn)輸問(wèn)題-數(shù)學(xué)模型及其解法(14頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第三章 運(yùn)輸問(wèn)題 數(shù)學(xué)模型及其解法,順風(fēng)而呼,聲非加疾也,而聞?wù)哒?。假輿馬者,非利足也,而致千里;假舟楫者,非能水也,而絕江河。君子生非異也,善假于物也。荀子勸學(xué),管理與人文學(xué)院 忻展紅,1999,4,3.1,運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型,有,m,個(gè)產(chǎn)地生產(chǎn),某,種物資,有,n,個(gè)地區(qū)需要該類(lèi)物資,令,a,1,a,2,a,m,表示各產(chǎn)地產(chǎn)量,,b,1,b,2,b,n,表示各銷(xiāo)地的銷(xiāo)量,,a,i,=,b,j,稱(chēng)為產(chǎn)銷(xiāo)平衡,設(shè),x,ij,表示產(chǎn)地,i,運(yùn)往銷(xiāo)地,j,的物資量,,w,ij,表示對(duì)應(yīng)的單位運(yùn)費(fèi),則我們有

2、運(yùn)輸問(wèn)題的數(shù)學(xué)模型如下:,運(yùn)輸問(wèn)題有,m,n,個(gè)決策變量,,m,+,n,個(gè)約束條件。由于產(chǎn)銷(xiāo)平衡條件,只有,m,+,n,1,個(gè)相互獨(dú)立,因此,運(yùn)輸問(wèn)題的基變量只有,m,+,n,1,個(gè),2,3.2,運(yùn)輸問(wèn)題的求解方法,約束條件非常有規(guī)律,技術(shù)系數(shù)非 0 即 1,基變量的個(gè)數(shù)遠(yuǎn)小于決策變量的個(gè)數(shù),采用表上作業(yè)法,稱(chēng)為位勢(shì)法和踏石法,運(yùn)算中涉及兩個(gè)表:運(yùn)費(fèi)表和產(chǎn)銷(xiāo)平衡表(,分配表,),3,3.2.1 尋找初始可行解的方法,1、西北角法,從,x,11,開(kāi)始分配,從西北向東南方向逐個(gè)分配,x,ij,的分配公式,例,3.2.1,4,例3.2.1 西北角法,5,2、最低費(fèi)用法,采用最小費(fèi)用優(yōu)先分配的原則,看

3、一步,f,(,x,)=121,,比,西北角法低,84,6,3、運(yùn)費(fèi)差額法,采用最大差額費(fèi)用(即利用每行或列中最小費(fèi)用與次最小之間的差額中選最大)優(yōu)先分配的原則,看兩步,f,(,x,)=98,,比,最低費(fèi)用法,又低了23,7,3.2.2 利用位勢(shì)法檢驗(yàn)分配方案是否最優(yōu),不采用單純型法,如何獲得,x,ij,的檢驗(yàn)數(shù),找到原問(wèn)題的基礎(chǔ)可行解,保持互補(bǔ)松弛條件,求出對(duì)應(yīng)對(duì)偶問(wèn)題的解,若該對(duì)偶問(wèn)題的解非可行,則原問(wèn)題的解不是最優(yōu)解;否則,達(dá)到最優(yōu)解,8,9,位勢(shì)法的原理,為滿足互補(bǔ)松弛條件,原問(wèn)題中,x,ij,被選為基變量,即,x,ij,0,,則要求對(duì)偶問(wèn)題中,u,i,+,v,j,=,w,ij,,,即該

4、行的松弛變量為0,共有,m,+,n,1,個(gè)基變量,x,ij,,,因此可得,m,+,n,1,個(gè)等式,u,i,+,v,j,=,w,ij,m,+,n,1,個(gè)等式只能解出,m,+,n,1,個(gè),u,i,和,v,j,,,而,一共有,m,+,n,個(gè),u,i,和,v,j,,,但,可令任一個(gè),u,i,或,v,j,=0,,從而,解出其它,m,+,n,1,個(gè),的值;這就是,位勢(shì)法,令,z,ij,=,u,i,+,v,j,,,其相當(dāng)原問(wèn)題,x,ij,的,機(jī)會(huì)費(fèi)用,若對(duì)所有非基變量有,z,ij,w,ij,0,,即,u,i,+,v,j,w,ij,,,表明當(dāng)前,u,i,和,v,j,是,對(duì)偶問(wèn)題的可行解,由互補(bǔ)松弛定理可知當(dāng)前

5、,m,+,n,1,個(gè)基變量,x,ij,是最優(yōu)解,否則,從,z,ij,w,ij,0,中找最大者,對(duì)應(yīng),x,ij,就是,入變量,10,3.2.3,踏石法,1、找入變量,從,z,ij,w,ij,0,中找最大者,對(duì)應(yīng),x,ij,就是入變量,2、以,x,ij,為起點(diǎn),,,尋找由原基變量構(gòu)成的,閉合回路,該回路只在每個(gè)拐角各有一個(gè)基變量,中間允許穿越某些基變量;因此,閉合回路中必有偶數(shù)個(gè)變量,(包括,x,ij,),,且回路中每行每列只有兩個(gè)變量,3、求入變量,x,ij,的最大值及新基變量的解,從,x,ij,出發(fā),沿任一個(gè)方向?qū)芈饭战巧系幕兞恳来藰?biāo)“”和“+”,表示“”和“+”,x,ij,,,從而迭代后

6、仍滿足分配的平衡,標(biāo)有“”的變量中最小者就是,出變量,x,ij,*,,,對(duì)應(yīng),x,ij,*,的值就是所,求入變量,x,ij,的最大值,標(biāo)有“”的變量減去,x,ij,*,,,標(biāo)有“+”的變量加上,x,ij,*,4、,用位勢(shì)法求新基變量的檢驗(yàn)數(shù),若所有,z,ij,w,ij,0,,則達(dá)到最優(yōu),算法停止;否則返回,1,11,例3.2.1 踏石法,以最低費(fèi)用法所得初始解開(kāi)始,答:,最優(yōu)解如上分配表,,OBJ,=98,OBJ,=121,OBJ,=101,12,3.3,運(yùn)輸問(wèn)題迭代中的一些具體問(wèn)題,3.3.1 閉合回路的畫(huà)法,從入變量,x,ij,出發(fā),遇到某個(gè)基變量則選一個(gè)方向拐角,若不能再遇到其它基變量,

7、則返回上一拐角,換一個(gè)方向走,采用,深探法,閉合回路不一定是矩形,3.3.2,產(chǎn)銷(xiāo)不平衡,供過(guò)于求,即,a,i,b,j,,,增加一個(gè)虛收點(diǎn),D,n,+1,,,b,n,+1,=,a,i,-,b,j,令,w,i,n,+1,=0,i,=1,2,m,供小于求,即,a,i,b,j,,,增加一個(gè)虛發(fā)點(diǎn),W,m,+1,,,a,m+1,=,b,j,-,a,i,令,w,m,+1,j,=0,j,=1,2,n,3.3.3,關(guān)于退化問(wèn)題,1、初始解退化。,即所求初始基變量的個(gè)數(shù)少于,m,+,n,1。,必須補(bǔ)足基變量的個(gè)數(shù),否則不能正常解出,m,+,n,個(gè),u,i,和,v,j,所補(bǔ)基變量的值為 0,補(bǔ)充的原則:(1),

8、盡量先選運(yùn)費(fèi)小的實(shí)變量,;(2),補(bǔ)充后不能有某個(gè)基變量獨(dú)占一行一列,13,3.3.3,關(guān)于退化問(wèn)題,2、迭代過(guò)程中出現(xiàn)退化,閉合回路中標(biāo)有“,”的基變量同時(shí)有多個(gè)達(dá)到最小,變換后,有多個(gè)原基變量變?yōu)?0,選運(yùn)費(fèi)最大者為,出變量,,其余保留在新的基礎(chǔ)解中,退化較嚴(yán)重時(shí),可能會(huì)出現(xiàn)多次迭代只有值為 0 的基變量在轉(zhuǎn)移。此時(shí),一要耐心,二要正確選擇出變量,踏石法迭代中需注意的問(wèn)題:,1、錯(cuò)誤地將分配表中基變量的解代入到運(yùn)費(fèi)表中,2、不能正確畫(huà)閉合回路,3、初始解退化,未能補(bǔ)足基變量的個(gè)數(shù)。因此在位勢(shì)法中多次令某個(gè),u,i,或,v,j,為,0;,4、在位勢(shì)法中只能令一個(gè),u,i,或,v,j,為,0;若不能求出全部,u,i,和,v,j,,,說(shuō)明基變量未選夠數(shù)或未選對(duì),14,

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
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ì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!