運(yùn)輸問題數(shù)學(xué)模型及其解法

1、第三章 運(yùn)輸問題 — 數(shù)學(xué)模型及其解法,順風(fēng)而呼，聲非加疾也，而聞?wù)哒谩＜佥涶R者，非利足也，而致千里；假舟楫者，非能水也，而絕江河。君子生非異也，善假于物也。 荀子《勸學(xué)》,©管理與人文學(xué)院 忻展紅 1999，4,2,3.1 運(yùn)輸問題的一般數(shù)學(xué)模型,有m個產(chǎn)地生產(chǎn)某種物資，有n個地區(qū)需要該類物資令a1, a2, …, am表示各產(chǎn)地產(chǎn)量， b1, b2, …, bn表

2、示各銷地的銷量，?ai=?bj 稱為產(chǎn)銷平衡設(shè)xij表示產(chǎn)地 i 運(yùn)往銷地 j 的物資量，wij表示對應(yīng)的單位運(yùn)費(fèi)，則我們有運(yùn)輸問題的數(shù)學(xué)模型如下：,運(yùn)輸問題有m?n個決策變量，m+n 個約束條件。由于產(chǎn)銷平衡條件，只有m+n–1個相互獨立，因此，運(yùn)輸問題的基變量只有m+n–1 個,3,3.2 運(yùn)輸問題的求解方法,約束條件非常有規(guī)律，技術(shù)系數(shù)非 0 即 1基變量的個數(shù)遠(yuǎn)小于決策變量的個數(shù)采用表上作業(yè)法，稱為位勢法和踏石法運(yùn)算中涉

3、及兩個表：運(yùn)費(fèi)表和產(chǎn)銷平衡表(分配表),4,3.2.1 尋找初始可行解的方法,1、西北角法從 x11開始分配，從西北向東南方向逐個分配xij 的分配公式,例3.2.1,5,例3.2.1 西北角法,6,2、最低費(fèi)用法,采用最小費(fèi)用優(yōu)先分配的原則，看一步,f(x)=121，比西北角法低84,7,3、運(yùn)費(fèi)差額法,采用最大差額費(fèi)用(即利用每行或列中最小費(fèi)用與次最小之間的差額中選最大)優(yōu)先分配的原則，看兩步,f(x)=98，比最低費(fèi)用法

4、又低了23,8,3.2.2 利用位勢法檢驗分配方案是否最優(yōu),不采用單純型法，如何獲得xij的檢驗數(shù)找到原問題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件，求出對應(yīng)對偶問題的解，若該對偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解,9,10,位勢法的原理,為滿足互補(bǔ)松弛條件，原問題中xij被選為基變量，即xij?0，則要求對偶問題中ui+vj=wij，即該行的松弛變量為0共有m+n?1個基變量xij ，因此可得m+n?1個等式 ui+

5、vj=wijm+n?1個等式只能解出 m+n?1個 ui 和 vj ，而一共有m+n個 ui 和 vj ，但可令任一個ui 或 vj =0，從而解出其它 m+n?1個的值；這就是位勢法令 zij= ui + vj ，其相當(dāng)原問題xij的機(jī)會費(fèi)用若對所有非基變量有 zij ? wij ? 0，即 ui + vj ? wij，表明當(dāng)前ui 和 vj 是對偶問題的可行解，由互補(bǔ)松弛定理可知當(dāng)前m+n?1個基變量xij 是最優(yōu)解，否則從

6、 zij ? wij > 0 中找最大者，對應(yīng) xij 就是入變量,11,3.2.3 踏石法,1、找入變量從 zij ? wij > 0 中找最大者，對應(yīng) xij 就是入變量2、以 xij 為起點，尋找由原基變量構(gòu)成的閉合回路該回路只在每個拐角各有一個基變量，中間允許穿越某些基變量；因此，閉合回路中必有偶數(shù)個變量(包括 xij )，且回路中每行每列只有兩個變量3、求入變量 xi*j* 的最大值及新基變量的解從 xi

7、j出發(fā)，沿任一個方向?qū)芈饭战巧系幕兞恳来藰?biāo)“?”和“+”，表示“?”和“+” xij ，從而迭代后仍滿足分配的平衡標(biāo)有“?”的變量中最小者就是出變量xi*j* ，對應(yīng) xi*j*的值就是所求入變量 xij 的最大值標(biāo)有“?”的變量減去 xi*j*，標(biāo)有“+”的變量加上 xi*j* 4、用位勢法求新基變量的檢驗數(shù)若所有 zij ? wij ? 0，則達(dá)到最優(yōu)，算法停止；否則返回 1,12,例3.2.1 踏石法，以最低費(fèi)用法所得

8、初始解開始,答：最優(yōu)解如上分配表，OBJ=98,OBJ=121,OBJ=101,,,13,3.3 運(yùn)輸問題迭代中的一些具體問題,3.3.1 閉合回路的畫法從入變量xij出發(fā)，遇到某個基變量則選一個方向拐角，若不能再遇到其它基變量，則返回上一拐角，換一個方向走，采用深探法閉合回路不一定是矩形 3.3.2 產(chǎn)銷不平衡供過于求，即 ?ai > ?bj ，增加一個虛收點Dn+1，bn+1= ?ai - ?bj , 令 wi

9、,n+1=0, i=1,2,…,m供小于求，即 ?ai < ?bj ，增加一個虛發(fā)點Wm+1，am+1= ?bj - ?ai , 令 wm+1,j=0, j=1,2,…,n 3.3.3 關(guān)于退化問題1、初始解退化。即所求初始基變量的個數(shù)少于 m+n?1。必須補(bǔ)足基變量的個數(shù)，否則不能正常解出 m+n個 ui 和 vj所補(bǔ)基變量的值為 0 ，補(bǔ)充的原則：(1)盡量先選運(yùn)費(fèi)小的實變量；(2)補(bǔ)充后不能有某個基變量獨占

10、一行一列,14,3.3.3 關(guān)于退化問題,2、迭代過程中出現(xiàn)退化閉合回路中標(biāo)有“?”的基變量同時有多個達(dá)到最小變換后，有多個原基變量變?yōu)?0，選運(yùn)費(fèi)最大者為出變量，其余保留在新的基礎(chǔ)解中退化較嚴(yán)重時，可能會出現(xiàn)多次迭代只有值為 0 的基變量在轉(zhuǎn)移。此時，一要耐心，二要正確選擇出變量,踏石法迭代中需注意的問題：,1、錯誤地將分配表中基變量的解代入到運(yùn)費(fèi)表中2、不能正確畫閉合回路3、初始解退化，未能補(bǔ)足基變量的個數(shù)。因此在位勢法中