[法學(xué)]第三章運輸問題(編輯修改稿)
2025-02-17 13:19 本頁面
【文章內(nèi)容簡介】 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x11檢驗數(shù)為 64+54=3 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x12檢驗數(shù)為 54+54=2 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x23檢驗數(shù)為 73+45=3 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x31檢驗數(shù)為 74+54+35=2 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x33檢驗數(shù)為 65+34+54=1 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 x34檢驗數(shù)為 85+34=2 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 0 4 2 4 3 0 此解為最優(yōu)解，最低運費為 55（元） 位勢法 當(dāng)運輸問題變量的格數(shù)較多時，用閉回路法計算檢驗數(shù)比較麻煩，而位勢法比較簡便。 對于運輸問題 minf=CX AX=b X≥0 設(shè) B為其一個可行基，則 xij的 檢驗數(shù)為 σ ij=CBB1PijCij 對于運輸問題的對偶問題 maxf=Yb YA≥ C Y無限制 其中， Y =(u1,…, u m,v1, …,v n)為 對偶變量，根據(jù)對偶理論有 Y=CBB1,因此有 σ ij=YPijCij 又因為 Pij的第個 i元素和第個 m+j元素為 1，其它元素為 0，所以有 σ ij=(u1,…, u m,v1, …,v n)PijCij =ui+vjcij 因為所有基變量的檢驗數(shù)為 0，因此有 σ ij = ui+vjcij=0 即 ui+vj=cij 由此可得含有 m+n1個方程的方程組，其中含有 m+n個未知量，可令某一個變量等于零，解得方程組的解，然后可根據(jù) σ ij = ui+vjcij 計算非基變量的檢驗數(shù)。這種計算檢驗數(shù)的方法稱為 位勢法。下面以上面利用伏格爾法求得的初始基可行解為例說明位勢法。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 3 1 2 1 3 3 u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6 u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6 令 u1=0 由 u1+v3=3 得 v3=3 由 u1+v4=4 得 v4=4 由 u2+v4=5 得 u2=1 由 u2+v1=4 得 v1=3 由 u2+v2=4 得 v2=3 由 u3+v2=6 得 u3=3 σ11=u1+v1c11=0+36=3, σ12=u1+v2c12=0+35=2 σ23=u2+v3c23=1+37=4, σ31=u3+v1c31=3+37=1 σ33=u3+v3c33=3+35=1, σ34=u3+v4c34=3+48=1 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2 6 A3 3 銷量 2 4 3 4 13 6 5 4 4 7 6 5 8 7 5 4 3 3 1 2 1 3 3 σ11=3, σ12=2,σ23=4, σ31=1,σ33=1, σ34=1 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 A2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1