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

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

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

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

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

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

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

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

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