運(yùn)輸問題中單價(jià)格系數(shù)變化對(duì)檢驗(yàn)數(shù)的影響

潘蘭蓉 閆海峰 徐躍良

1. 西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 610031

2. 西南交通大學(xué)，數(shù)學(xué)學(xué)院，成都 610031

0 引 言

運(yùn)輸問題是一類特殊的線性規(guī)劃問題，一般指大宗物資調(diào)運(yùn)問題，當(dāng)然許多其他類型的問題經(jīng)過適當(dāng)變換也可歸結(jié)為運(yùn)輸問題，如指派問題、最短路問題等。對(duì)于傳統(tǒng)運(yùn)輸問題的求解，一般使用表上作業(yè)法，其實(shí)質(zhì)是單純形法的一種簡化，但表上作業(yè)法計(jì)算量大，無法利用計(jì)算機(jī)編程實(shí)現(xiàn)。

在運(yùn)輸問題中，隨著時(shí)間的變化，各產(chǎn)銷地之間的運(yùn)價(jià)、產(chǎn)銷量會(huì)頻繁發(fā)生變化，此時(shí)需要重新計(jì)算最優(yōu)解，再次利用表上作業(yè)法將花費(fèi)大量時(shí)間。對(duì)于該問題，許多學(xué)者進(jìn)行了研究，如宋寶琪等[1]對(duì)于一個(gè)或多個(gè)運(yùn)價(jià)發(fā)生變化的情況根據(jù)“矩陣變換法”進(jìn)行了討論；王思亮[2]對(duì)于產(chǎn)銷量發(fā)生變化的情況分總運(yùn)輸量減少與增加兩種情況利用閉回路調(diào)整法給出了得到新最優(yōu)方案的方法；任運(yùn)平[3]針對(duì)總運(yùn)輸量的變化給出了特定條件下的最優(yōu)調(diào)整方案。

當(dāng)價(jià)格系數(shù)變化較小時(shí)，若能夠利用原最優(yōu)解和價(jià)格系數(shù)矩陣的特點(diǎn)，快速判斷最優(yōu)解的變化情況或求得新的最優(yōu)解，將大大簡化計(jì)算，為此本文提出了一種簡便算法，用于計(jì)算單個(gè)基變量價(jià)格系數(shù)發(fā)生變化時(shí)，檢驗(yàn)數(shù)的變化情況。

1 該運(yùn)輸問題的數(shù)學(xué)模型

所謂運(yùn)輸問題[4]：已知生產(chǎn)地點(diǎn) Ai（ i = 1,2,…,m）的產(chǎn)量為 ai，銷售地點(diǎn) Bj（ j = 1 ,2,… ,n ）的銷量為 bj，從 Ai到 Bj的單位運(yùn)價(jià)為 cij，求解同時(shí)滿足 ai和 bj要求下的總運(yùn)費(fèi)最小的調(diào)運(yùn)方案問題可以描述為：

2 非基變量價(jià)格系數(shù)的變化分析

用位勢法求解產(chǎn)銷平衡的運(yùn)輸問題時(shí)，iu與jv是利用基變量檢驗(yàn)數(shù)得出的，當(dāng)某個(gè)非基變量對(duì)應(yīng)的Nijc發(fā)生變化時(shí)，由于未發(fā)生變化，則所有的 u 與 v 也不會(huì)發(fā)生變化。ij因此我們可以得到：

性質(zhì)1 在產(chǎn)銷平衡的運(yùn)輸問題中，在已經(jīng)得到最優(yōu)解的情況下，若第s行t列非基變量 xst的價(jià)格系數(shù)cst變?yōu)閏′st，則xst對(duì)應(yīng)的檢驗(yàn)數(shù)σst變?yōu)棣摇鋝t= c ′st-(us+ vt)，而其余變量的檢驗(yàn)數(shù)均不變。

3 基變量價(jià)格系數(shù)的變化分析

為了研究敘述的方便，給出如下定義：

定義 對(duì)于A和B兩個(gè)參量，當(dāng)A變化為A±a時(shí)，B也變化為B±a，則稱A與B的變化相同；若A變化為A±a時(shí)，B變化為B?a，則稱A與B的變化相反。

用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，每一行（列）都至少有一個(gè)基變量。在已得到最優(yōu)解的情況下，若只有第p行q列的基變量價(jià)格系數(shù) cpq發(fā)生變化，且 up= 0 ，由基變量檢驗(yàn)數(shù)為0的性質(zhì)可知：vq與 cpq的變化相同，而第 p行其余基變量 xpj對(duì)應(yīng)的 vj均不變。通過對(duì)價(jià)格系數(shù)的變化研究，可以得到以下定理和推論：

定理1 用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，在最優(yōu)解表中若只有基變量價(jià)格系數(shù) cpq發(fā)生變化。

（1）若第q列只有一個(gè)基變量 xpq且 up= 0 ，則 vq與 cpq的變化相同，其余的 ui與 vj均不變。

（2）若第p行只有一個(gè)基變量 xpq且 vq= 0 ，則 up與 cpq的變化相同，其余的 ui與 vj均不變。

證明：由于 xpq為基變量，因此 σpq= 0 =cpq-( up+ vq)σpq=0 = cpq- ( up+ vq)，可得 cpq= up+ vq，由up= 0 得到 cpq= vq。利用基變量檢驗(yàn)數(shù)為0的性質(zhì)，可以得到（m+n-1）個(gè)等式；由于第q列只有一個(gè)基變量 xpq，其余基變量檢驗(yàn)數(shù)所對(duì)應(yīng)的（m+n-2）個(gè)等式中均不含 vq；由 up= 0 與其余基變量檢驗(yàn)數(shù)所對(duì)應(yīng)的（m+n-2）個(gè)等式所組成的方程組，可以得到除 vq外其余（m+n-1）個(gè)“位勢”的唯一解，且該解與 vq無關(guān)。因此，定理1（1）得證。同理可證定理1（2）。

推論1 用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，在已得到最優(yōu)解的情況下，若第 q列只有一個(gè)基變量 xpq，其價(jià)格系數(shù) cpq變化為 c ′pq= cpq+ a1，則有且只有該列所有的非基變量檢驗(yàn)數(shù)發(fā)生了變化，且與 cpq的變化相反，即 σi′q=σiq-a1。

證明：不妨設(shè)用位勢法求檢驗(yàn)數(shù)時(shí)，取 up= 0 。根據(jù)“定理1”可得，當(dāng) c ′pq= cpq+ a1時(shí)，有 v ′q= vq+ a1，其余的 ui與 vj均不變。根據(jù)公式 σij= cij-( ui+vj)可以得到：

證畢。

定理2 用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，在最優(yōu)解表中若只有基變量價(jià)格系數(shù)pqc發(fā)生變化。

（1）假設(shè) up= 0 ，則 vq與 cpq變化相同；若第q列有（b+1）個(gè)基變量，分別在第 p ,p1,p2,… ,pb行，則upi與 cpq變化相反；再若第 pi(i = 1 ,2,… ,b )行均僅有一個(gè)基變量，則除 upi和 vq外，其余的 ui與 vj均不變；

（2）假設(shè) vq= 0 ，則 up與 cpq變化相同；若第p行有（b+1）個(gè)基變量，分別在第 q ,q1,q2,… ,qb行，則vqj與 cpq變化相反；再若第 qj( j = 1 ,2,… ,b )列均僅有一個(gè)基變量，則除 up和 vqj外，其余的 ui與 vj均不變。

證明：由于 xpq為基變量，因此， σpq= 0 =cpq-( up+ vq)，可得 cpq= up+ vq，由 up= 0 不變得到 cpq= vq即 vq與 cpq變化相同；假設(shè) cpq變化為 c ′pq= cpq+ a1，則v′q= vq+ a1， 根 據(jù) c ′pi,q- ( u ′pi+ v ′q) = 0 ， 則 u ′pi=c ′pi,q-vq′

= cpi,q- vq- a1= upi- a1，即 upi與 cpq變化相反。

利用基變量檢驗(yàn)數(shù)為0的性質(zhì)可以得到（m+n-1個(gè)等式；由于第 pi(i = 1 ,2,… ,b )行均僅有一個(gè)基變量，其余基變量檢驗(yàn)數(shù)所對(duì)應(yīng)的（m+n-b-2）個(gè)等式中均不含 upi與 vq；由 up= 0 與其余基變量檢驗(yàn)數(shù)所對(duì)應(yīng)（m+n-b-2）個(gè)等式所組成的方程組，可以得到除 upi與 vq外其余（m+n-b-1）個(gè)“位勢”的唯一解，且該解與 upi及 vq無關(guān)。因此，定理2（1）得證。同理可證定理2（2）。

推論2 用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，在最優(yōu)解表中若只有基變量價(jià)格系數(shù) cpq發(fā)生變化，第 q列有（b+1）個(gè)基變量，分別在第 p ,p1, p2,… ,pb行，而第

pi(i = 1 ,2,… ,b )行均僅有一個(gè)基變量，則有且只有第 q列與第 pi(i = 1 ,2,… ,b )行的非基變量檢驗(yàn)數(shù)發(fā)生變化，第 q列的非基變量檢驗(yàn)數(shù)與 cpq變化相反，第 pi行的非基變量檢驗(yàn)數(shù) cpq變化相同。

證明：不妨設(shè)用位勢法求檢驗(yàn)數(shù)時(shí)，取 up= 0 。

4 求檢驗(yàn)數(shù)的簡單算法

利用上述定理，在指派問題的匈牙利算法的啟發(fā)下，得到了在用位勢法求得產(chǎn)銷平衡運(yùn)輸問題的最優(yōu)解后，當(dāng)單個(gè)基變量價(jià)格系數(shù)發(fā)生變化，計(jì)算檢驗(yàn)數(shù)的簡便算法。

為不失一般性，假定 xpq為基變量，其價(jià)格系數(shù)cpq發(fā)生變化，并取 up= 0 。在原檢驗(yàn)數(shù)表的基礎(chǔ)上，以pqx為起點(diǎn)，按如下步驟進(jìn)行：

Step 1 進(jìn)行標(biāo)記

① 在qv處打√，劃去第q列；

② 若所劃去的列上還存在有行未被劃去的基變量，則在這些基變量所在行的iu處打Δ，并劃去該行，轉(zhuǎn)入③；若不存在，則結(jié)束；

③ 若所劃去的行上還存在有列未被劃去的基變量，則在這些基變量所在列的jv處打√，并劃去該列，轉(zhuǎn)回②；若不存在，則結(jié)束。

Step 2 計(jì)算新位勢

所有打√處的 vj均與 cpq變化相同；所有打Δ處的ui均與 cpq變化相反。

Step 3 計(jì)算非基變量檢驗(yàn)數(shù)

所有只被豎線經(jīng)過的非基變量檢驗(yàn)數(shù)均與 cpq變化相反；所有只被橫線經(jīng)過的非基變量檢驗(yàn)數(shù)均與cpq變化相同；其余非基變量檢驗(yàn)數(shù)不變。

一般情況下，用位勢法求解運(yùn)輸問題時(shí)，都假定u1= 0 。為了便于使用上述計(jì)算方法，這里給出一個(gè)相關(guān)的計(jì)算性質(zhì)2以便計(jì)算。

性質(zhì)2 用位勢法求解標(biāo)準(zhǔn)運(yùn)輸問題時(shí)，在同一組基變量下，記 u1= 0 時(shí)所求得的位勢為 ui， vj，記up= 0 （p≠1）時(shí)所求得的位勢為 ui′， v ′j，記 vq= 0 時(shí)所求得的位勢為 ui′， v′j，則有：

證明：對(duì)于給定的一組基變量，假設(shè)第p行存在基變量pax，相應(yīng)的第a列存在基變量bax，則可得

5 算 例

有運(yùn)輸問題：產(chǎn)地為A1，A2，A3，A4，銷地為B1，B2，B3，B4，B5，B6，其產(chǎn)量和銷量以及單位產(chǎn)品的運(yùn)價(jià)如表1所示，利用表上作業(yè)法求得其最優(yōu)解與對(duì)應(yīng)的檢驗(yàn)數(shù)如表 2所示。假設(shè)：基變量43x的價(jià)格系數(shù)變?yōu)?35c′= 。

（1）根據(jù)性質(zhì) 2，計(jì)算令40u= 時(shí)的表 2中檢驗(yàn)數(shù)的變化情況，得到表3：

表1 產(chǎn)銷量及單位運(yùn)價(jià)Tab.1 Production and sales volumes and unit tariff

表2 檢驗(yàn)數(shù)及對(duì)應(yīng)最優(yōu)解Tab.2 Test numbers and optimal solutions

表3 令40u= 時(shí)的檢驗(yàn)數(shù)

Tab.3 Test numbers when40u=

產(chǎn)地 銷 地 ui B1 B2 B3 B4 B5 B6 A1 7 12 0 0 3 0 2 A2 0 3 4 22 0 1 1 A3 1 15 5 4 0 3 -1 A4 7 0 0 0 0 2 0 vj 1 6 3 7 5 -2 —

（2）在43x處畫圈表示此為起點(diǎn)進(jìn)行標(biāo)記，得到表4：表4 利用簡單算法標(biāo)記后的最優(yōu)解

Tab.4 Table of optimal solution after marking

產(chǎn)地 銷地 ui B1 B2 B3 B4 B5 B6 A1 - - 4 - - 2 Δ A2 4 - - - 1 - -A3 - - - - 2 - -A4 - 4 ② 2 1 - -vj - - √ - - √ —

（3）根據(jù)簡便算法，對(duì)打 Δ處的u1減少 2，打√

處的v3,v6均增加2，檢驗(yàn)數(shù)檢驗(yàn)數(shù)σ11,σ12,σ14,σ15均增加2，其新檢驗(yàn)數(shù)如表5所示。

表5 新檢驗(yàn)數(shù)Tab.5 New test numbers

（4）表5中存在26σ為負(fù)數(shù)，則最優(yōu)解發(fā)生變化。

（5）將26x作為換入變量，利用閉回路調(diào)整法繼續(xù)計(jì)算，直至求出最優(yōu)解（略）。

該算例演示了在已經(jīng)得到最優(yōu)解的情況下，當(dāng)某個(gè)基變量的價(jià)格系數(shù)發(fā)生變化時(shí)，如何利用本文所給的算法在原有檢驗(yàn)數(shù)表的基礎(chǔ)上求解新檢驗(yàn)數(shù)表，從而判斷最優(yōu)解是否發(fā)生變化，若最優(yōu)解發(fā)生變化，如何迅速給出換入變量利用閉回路調(diào)整法進(jìn)行計(jì)算。

6 結(jié)束語

現(xiàn)實(shí)生活中運(yùn)輸問題的規(guī)模龐大，并且其價(jià)格系數(shù)也常常發(fā)生改變，在已經(jīng)得到最優(yōu)解的情況下，利用該簡單算法可以輕易的在新價(jià)格系數(shù)條件下得到新的檢驗(yàn)數(shù)表，從而判斷出原最優(yōu)解是否發(fā)生變化。

然而，本文提出的簡單算法針對(duì)的是運(yùn)輸問題中單個(gè)價(jià)格系數(shù)發(fā)生變化的情況，而對(duì)于多個(gè)價(jià)格系數(shù)同時(shí)發(fā)生變化的情況未加考慮，這將是未來繼續(xù)研究的方向。

[ 1 ] 宋寶琪，劉舒燕. 運(yùn)輸問題的靈敏度分析[J]. 武漢水運(yùn)工程學(xué)院學(xué)報(bào)，1989，4（13）：82-88.

[ 2 ] 王思亮. 運(yùn)輸問題靈敏度分析[J]. 江蘇廣播電視大學(xué)學(xué)報(bào)，1995，（1）：83-86.

[ 3 ] 任運(yùn)平. 運(yùn)輸問題的靈敏度分析[J]. 運(yùn)城高等?？茖W(xué)校學(xué)報(bào)，2000，3（18）：4-5.

[ 4 ] 錢頌迪，郭耀煌等. 運(yùn)籌學(xué)[M]. 北京：清華大學(xué)出版社，1990：79-80.

[ 5 ] 曾梅清，田大鋼. 線性規(guī)劃問題的算法綜述[J]. 科學(xué)技術(shù)與工程，2010，10（1）：152-159.

[ 6 ] 勒曉陽，李松仁，賈春霖. 線性規(guī)劃靈敏度分析模型[J]. 中南礦冶學(xué)院學(xué)報(bào)，1990，21（6）：602-609.

[ 7 ] 王煥雄. 線性規(guī)劃的靈敏度分析及應(yīng)用[J]. 吉林化工學(xué)院學(xué)報(bào)，1984，（3）：54-68.

[ 8 ] 李維錚，郭耀煌等. 運(yùn)籌學(xué)[M]. 北京：清華大學(xué)出版社，2005：83-86.