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

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

2、運(yùn)輸問題的數(shù)學(xué)模型如下：,運(yùn)輸問題有,m,n,個(gè)決策變量，,m,+,n,個(gè)約束條件。由于產(chǎn)銷平衡條件，只有,m,+,n,1,個(gè)相互獨(dú)立，因此，運(yùn)輸問題的基變量只有,m,+,n,1,個(gè),2,3.2,運(yùn)輸問題的求解方法,約束條件非常有規(guī)律，技術(shù)系數(shù)非 0 即 1,基變量的個(gè)數(shù)遠(yuǎn)小于決策變量的個(gè)數(shù),采用表上作業(yè)法，稱為位勢法和踏石法,運(yùn)算中涉及兩個(gè)表：運(yùn)費(fèi)表和產(chǎn)銷平衡表(,分配表,),3,3.2.1 尋找初始可行解的方法,1、西北角法,從,x,11,開始分配，從西北向東南方向逐個(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 利用位勢法檢驗(yàn)分配方案是否最優(yōu),不采用單純型法，如何獲得,x,ij,的檢驗(yàn)數(shù),找到原問題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件，求出對應(yīng)對偶問題的解，若該對偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解,8,9,位勢法的原理,為滿足互補(bǔ)松弛條件，原問題中,x,ij,被選為基變量，即,x,ij,0，,則要求對偶問題中,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è),的值；這就是,位勢法,令,z,ij,=,u,i,+,v,j,，,其相當(dāng)原問題,x,ij,的,機(jī)會(huì)費(fèi)用,若對所有非基變量有,z,ij,w,ij,0，,即,u,i,+,v,j,w,ij,，,表明當(dāng)前,u,i,和,v,j,是,對偶問題的可行解，由互補(bǔ)松弛定理可知當(dāng)前

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

7、則返回上一拐角，換一個(gè)方向走，采用,深探法,閉合回路不一定是矩形,3.3.2,產(chǎn)銷不平衡,供過于求，即,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)于退化問題,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)于退化問題,2、迭代過程中出現(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í)，一要耐心，二要正確選擇出變量,踏石法迭代中需注意的問題：,1、錯(cuò)誤地將分配表中基變量的解代入到運(yùn)費(fèi)表中,2、不能正確畫閉合回路,3、初始解退化，未能補(bǔ)足基變量的個(gè)數(shù)。因此在位勢法中多次令某個(gè),u,i,或,v,j,為,0；,4、在位勢法中只能令一個(gè),u,i,或,v,j,為,0；若不能求出全部,u,i,和,v,j,，,說明基變量未選夠數(shù)或未選對,14,