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

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

2、示各銷(xiāo)地的銷(xiāo)量，?ai=?bj 稱(chēng)為產(chǎn)銷(xiāo)平衡設(shè)xij表示產(chǎn)地 i 運(yùn)往銷(xiāo)地 j 的物資量，wij表示對(duì)應(yīng)的單位運(yùn)費(fèi)，則我們有運(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è),3,3.2 運(yùn)輸問(wèn)題的求解方法,約束條件非常有規(guī)律，技術(shù)系數(shù)非 0 即 1基變量的個(gè)數(shù)遠(yuǎn)小于決策變量的個(gè)數(shù)采用表上作業(yè)法，稱(chēng)為位勢(shì)法和踏石法運(yùn)算中涉

3、及兩個(gè)表：運(yùn)費(fèi)表和產(chǎn)銷(xiāo)平衡表(分配表),4,3.2.1 尋找初始可行解的方法,1、西北角法從 x11開(kāi)始分配，從西北向東南方向逐個(gè)分配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 利用位勢(shì)法檢驗(yàn)分配方案是否最優(yōu),不采用單純型法，如何獲得xij的檢驗(yàn)數(shù)找到原問(wèn)題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件，求出對(duì)應(yīng)對(duì)偶問(wèn)題的解，若該對(duì)偶問(wèn)題的解非可行，則原問(wèn)題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解,9,10,位勢(shì)法的原理,為滿足互補(bǔ)松弛條件，原問(wèn)題中xij被選為基變量，即xij?0，則要求對(duì)偶問(wèn)題中ui+vj=wij，即該行的松弛變量為0共有m+n?1個(gè)基變量xij ，因此可得m+n?1個(gè)等式 ui+

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

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

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

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

9、,n+1=0, i=1,2,…,m供小于求，即 ?ai < ?bj ，增加一個(gè)虛發(fā)點(diǎn)Wm+1，am+1= ?bj - ?ai , 令 wm+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è) ui 和 vj所補(bǔ)基變量的值為 0 ，補(bǔ)充的原則：(1)盡量先選運(yùn)費(fèi)小的實(shí)變量；(2)補(bǔ)充后不能有某個(gè)基變量獨(dú)占

10、一行一列,14,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ì)法中