基于最短路的多階段決策問(wèn)題研究

摘要：最短路問(wèn)題是圖論中的重要問(wèn)題之一，許多實(shí)際問(wèn)題都可以轉(zhuǎn)化為最短路問(wèn)題。文章重點(diǎn)研究了多階段決策問(wèn)題，如設(shè)備更新和生產(chǎn)策略用Dijkstra算法求解的過(guò)程。該方法清晰直觀，具有通用性和實(shí)用性。

關(guān)鍵詞：最短路問(wèn)題；決策問(wèn)題；Dijkstra算法；鄰接矩陣

一、引言

圖論中的最短路問(wèn)題是研究多階段決策問(wèn)題的可行辦法，關(guān)鍵在于將多階段決策問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，構(gòu)造出相應(yīng)的圖，使圖的頂點(diǎn)、邊、權(quán)值分別反映原問(wèn)題的相關(guān)要素，從而清晰直觀地顯現(xiàn)出問(wèn)題的實(shí)質(zhì)，再通過(guò)求解圖中某些頂點(diǎn)間的最短路來(lái)確定原問(wèn)題的多階段決策。這一問(wèn)題可以利用現(xiàn)成的Dijkstra算法和Floyd算法來(lái)解決。

二、最短路問(wèn)題

最短路是一條路徑，它的任意一段也是最短路。從某一點(diǎn)出發(fā)到其余頂點(diǎn)的最短路會(huì)構(gòu)成一棵以該點(diǎn)為根的樹(shù)，可以采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路。Dijkstra算法可以實(shí)現(xiàn)這一過(guò)程。

設(shè)G為賦權(quán)有向圖或無(wú)向圖，G邊上的權(quán)均非負(fù)，S表示具有永久標(biāo)號(hào)的頂點(diǎn)集。對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（l（v），z（v）），其中l(wèi)（v）表示從頂點(diǎn)到v的一條路的權(quán)，z（v）表示v的父親點(diǎn)，用以確定最短路的路線。算法的基本思想就是在每一步改進(jìn)這兩個(gè)標(biāo)記，是最終l（v）達(dá)到從頂點(diǎn)u0到v的最短路的權(quán)。

具體步驟為：輸入G的帶權(quán)鄰接矩陣W，首先賦初值S={u0，l（u0）=0}，?v∈S=V＼S令l（v）=W（u0，v），z（v）=u0，u←u0；再更新l（v），z（v），?v∈S=V＼S，若l（v）>l（u）+W（u，v），則令l（v）=l（u）+W（u，v），z（v）=u；設(shè)v*是使得l（v）取最小值的S中的頂點(diǎn)，則令S=S∪{v*}；如果S≠?，繼續(xù)更新l（v），z（v），直到S=?停止。如此求出的l（v）就是從u0到v的最短路的權(quán)，再反向追溯得到u0到v的最短路的路線。

三、多階段決策問(wèn)題的轉(zhuǎn)化

在生產(chǎn)過(guò)程中需要考慮生產(chǎn)設(shè)備的更新問(wèn)題。隨著設(shè)備使用時(shí)間的增長(zhǎng)，累積效益也會(huì)增長(zhǎng)，同時(shí)維修費(fèi)用也隨之增加，而購(gòu)買新設(shè)備的所需費(fèi)用越來(lái)越多，舊設(shè)備的折舊費(fèi)卻越來(lái)越少。因此，要合理利用某一設(shè)備就需要考慮在該設(shè)備的使用年限內(nèi)計(jì)劃其更新問(wèn)題，以使得生產(chǎn)效益達(dá)到最優(yōu)。這就是一個(gè)多階段決策過(guò)程。

例1：某學(xué)院數(shù)據(jù)中心有一組教學(xué)設(shè)備，需要在每年年初進(jìn)行評(píng)估，決定是否更換新設(shè)備。該設(shè)備每年年初購(gòu)置價(jià)格如表1所示，不同時(shí)間折舊費(fèi)和維修費(fèi)用如表2所示。其使用年限為五年，現(xiàn)要求制訂一個(gè)設(shè)備更新計(jì)劃，使得五年內(nèi)學(xué)院對(duì)該教學(xué)設(shè)備所支付的總費(fèi)用最少。

要將該問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，先構(gòu)造加權(quán)有向圖G（V，E），該圖為完備圖K6，如圖1所示。

圖1中有頂點(diǎn)集V={vi，i=1，2，3，4，5

，6}，其中vi表示第i年（i=1，2，3，4，5）年初購(gòu)置新設(shè)備的決策，v6表示第五年年底的情況；邊集E={（vi，vj），i=1，2，3，4，5；i

寫(xiě)出帶權(quán)鄰接矩陣為

0 3 8 15 24 27

0 5 10 17 26

0 6 11 18

0 8 13

0 10

0

迭代步驟如表3所示。

通過(guò)迭代得到從v1到v6的最短路徑為v1-v2-v3-v6、v1-v2-v4-v6、v1-v3-v6，權(quán)值為26。也就是說(shuō)有三種設(shè)計(jì)方法更新設(shè)備所需費(fèi)用都最省，最省費(fèi)用為26萬(wàn)元。

類似的還有生產(chǎn)策略問(wèn)題。合理安排生產(chǎn)率對(duì)生產(chǎn)效益會(huì)有決定性的作用：生產(chǎn)率高了，一方面剩余產(chǎn)品會(huì)有積壓損壞，另一方面流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率不夠，供不應(yīng)求，利潤(rùn)明顯達(dá)不到最大值。所以，生產(chǎn)部門應(yīng)該密切注意市場(chǎng)需求的變化，適時(shí)調(diào)整生產(chǎn)率，以獲取最大利潤(rùn)。該問(wèn)題要轉(zhuǎn)化為最短路問(wèn)題，關(guān)鍵在于設(shè)置合理的點(diǎn)集和邊集，計(jì)算出準(zhǔn)確的邊的加權(quán)值。

例2：某加工廠生產(chǎn)某種產(chǎn)品，該產(chǎn)品在年初的需求量為60萬(wàn)單位并以每月10萬(wàn)單位遞增。供大于求時(shí)，該廠每月花費(fèi)0.2元保管剩余單位產(chǎn)品；供不應(yīng)求時(shí)，該廠每月單位產(chǎn)品的短期損失費(fèi)為0.4元。預(yù)計(jì)每調(diào)整一次生產(chǎn)率需要花費(fèi)10萬(wàn)元的費(fèi)用，現(xiàn)設(shè)計(jì)合理的年生產(chǎn)策略，使工廠的總損失最小。

同樣的要先構(gòu)造加權(quán)有向圖G（V，E），該圖仍為完備圖K13（圖略）。用頂點(diǎn)vi表示第i月（i=1，2，3，4，5，6，7，8，9，10，11，12）月初的決策，v13表示第12月月底的情況；用邊（vi，vj）（i=1，2，3，4，5，6，7，8，9，10，

11，12；i

每月之間的庫(kù)存保管費(fèi)和短期損失費(fèi)的算式為M1=（x-60）*0.2，顯然最小值為0，下個(gè)月的產(chǎn)量調(diào)整費(fèi)用為10萬(wàn)元，所以邊（vi，vi+1）的權(quán)值為10，特別的（v12，v13）權(quán)值為0。

每?jī)蓚€(gè)月之間的庫(kù)存保管費(fèi)和短期損失費(fèi)的算式為：（1）M1=（x-60）*0.2；（2）如果（2x-60）≥70，則賦值M2=（2x-130）*0.2，否則賦值M2=（130-2x）*0.4，解得M1+M2的最小值為1，所以邊（vi，vi+2）的權(quán)值為11，特別的（v11，v13）權(quán)值為1。

同理可得（vi，vi+3）的權(quán)值為14，（v10，v13）權(quán)值為4；（vi，vi+4）的權(quán)值為20，（v9，v13）權(quán)值為10；（vi，vi+4）的權(quán)值為30，（v8，v13）權(quán)值為20；（vi，vi+5）的權(quán)值為42，（v7，v13）權(quán)值為32；（vi，vi+6）的權(quán)值為59，（v6，v13）權(quán)值為49；（vi，vi+7）的權(quán)值為82，（v5，v13）權(quán)值為72；（vi，vi+8）的權(quán)值為112，（v4，v13）權(quán)值為102；（vi，vi+9）的權(quán)值為150，（v3，v13）權(quán)值為140；（vi，vi+10）的權(quán)值為194，（v2，v13）權(quán)值為184；（vi，vi+11）的權(quán)值為235。

于是可以得到帶權(quán)鄰接矩陣，通過(guò)迭代得到從v1到v13的最短路徑為v1-v4-v7-v10-v13，權(quán)值為46。也就是說(shuō)該加工廠應(yīng)該在4月初、7月初和10月初改變生產(chǎn)率總損耗最少，該方案的損耗費(fèi)用為46萬(wàn)元。

Dijkstra算法的計(jì)算過(guò)程，除了可以直接用鄰接矩陣迭代求解，也可以編寫(xiě)matlab程序?qū)嵤?。所以。把多階段決策問(wèn)題轉(zhuǎn)化為最短路問(wèn)題能客觀形象地展示問(wèn)題本身，同時(shí)輕松有效地解決實(shí)際問(wèn)題。

參考文獻(xiàn)：

[1]趙靜，但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].北京：高等教育出版社，2003.

[2]劉曉妍，麻興斌，王曉明.基于最短路的設(shè)備更新問(wèn)題的數(shù)學(xué)建模[J].河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版，2013（04）.

[3]管志忠，劉永明.圖論中最短路問(wèn)題的MATLAB程序?qū)崿F(xiàn)[J].安慶師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2007（01）.

（作者單位：天津機(jī)電職業(yè)技術(shù)學(xué)院）