• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2015-03-11 14:03:42潘蘭蓉閆海峰徐躍良
    關(guān)鍵詞:位勢定理運(yùn)輸

    潘蘭蓉 閆海峰 徐躍良

    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.

    猜你喜歡
    位勢定理運(yùn)輸
    J. Liouville定理
    含Hardy位勢的非線性Schr?dinger-Poisson方程正規(guī)化解的多重性
    一類帶強(qiáng)制位勢的p-Laplace特征值問題
    A Study on English listening status of students in vocational school
    含變號(hào)位勢的ρ-Kirchhoff型方程組無窮多個(gè)高能量解的存在性
    “三共定理”及其應(yīng)用(上)
    含位勢的非線性雙調(diào)和方程解的存在性
    受阻——快遞運(yùn)輸“快”不起來
    專用汽車(2016年4期)2016-03-01 04:13:39
    比甩掛更高效,交換箱漸成運(yùn)輸“新寵”
    專用汽車(2016年1期)2016-03-01 04:13:08
    關(guān)于道路運(yùn)輸節(jié)能減排的思考
    东宁县| 宜都市| 巴彦淖尔市| 昌吉市| 平泉县| 咸丰县| 基隆市| 永德县| 鹤山市| 广平县| 大石桥市| 巢湖市| 怀柔区| 泰顺县| 塔河县| 瑞金市| 永定县| 夏津县| 顺昌县| 霍林郭勒市| 长兴县| 临西县| 合阳县| 曲靖市| 青川县| 文登市| 永嘉县| 陆河县| 保康县| 武安市| 岐山县| 金湖县| 尖扎县| 汝州市| 乡宁县| 电白县| 那曲县| 庐江县| 邹平县| 建阳市| 禹州市|