摘要：許多領(lǐng)域都涉及資源分配問題，怎樣合理的把各種有限的經(jīng)濟(jì)資源分配給企業(yè)內(nèi)各生產(chǎn)部門，使得本企業(yè)在相對(duì)較低的成本投入下得到較大利潤(rùn)是每一個(gè)企業(yè)所追求的目標(biāo)。于是就產(chǎn)生了如何分配以使工程目標(biāo)或生產(chǎn)目的達(dá)到最優(yōu)的問題。本文針對(duì)這一類資源分配問題，闡述了用動(dòng)態(tài)規(guī)劃方法和多段圖方法的求解思想，并通過實(shí)例比較了兩種算法。

關(guān)鍵詞：資源分配，動(dòng)態(tài)規(guī)劃，多段圖

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)12-20ppp-0c

Comparison and Research for Resource Allocation Algorithm

FAN Chao， ZHU Zhan-li

(School of Computer Science， Xi'an Shiyou University， Xi'an 710065， China)

Abstract: Many fields involving the allocation of resources， how to allocate various kinds of limited economic resources reasonably to production department， and making enterprises get higher profit at lower input costs is the goal for every enterprise.So，the problem of how to allocate recourse to make the project target or the aim of production optimization was brought out. This paper focuses attention on this kind of resource allocation ，and discusses the method of using Dynamic Programming and Multistage Graph.， Then， using examples compare these two algorithms.

Key words: resource allocation; Dynamic Programming; Multistage Graph

1 引言

資源分配問題是現(xiàn)實(shí)中存在的一種決策問題，例如各類工程預(yù)算、自然科學(xué)基金資助項(xiàng)

目的評(píng)審都可以看作資源分配問題來求解。本文定義的資源分配問題是將一定量的資源分配給若干工程以獲得最大效益，這類分配問題滿足一定的條件：待分配的資源是有限的；資源分配給不同的工程所創(chuàng)造的效益是不同的。

動(dòng)態(tài)規(guī)劃和多段圖是解決資源分配的兩種方法。動(dòng)態(tài)規(guī)劃將活動(dòng)過程劃分為若干個(gè)階段，每一階段的決策，依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作，使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段的決策依據(jù)。最優(yōu)性原理：無論過程的初始狀態(tài)和初始決策是什么，其余決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。

令最優(yōu)狀態(tài)為S(2，22)，由此倒推：S(2，22)—>p(2，22)—>S(1，2)—>p(1，2)—>S0，最優(yōu)決策序列，p(1，2)—> p(2，22)，狀態(tài)轉(zhuǎn)移序列：S0—>S(1，2)—> S(2，22)，賴以決策的策略或目標(biāo)，稱為動(dòng)態(tài)規(guī)劃函數(shù)。整個(gè)決策過程，可以遞歸地進(jìn)行，或用循環(huán)迭代的方法進(jìn)行。動(dòng)態(tài)規(guī)劃函數(shù)可以遞歸地定義，也可以用遞推公式來表達(dá)。最優(yōu)決策是在最后階段形成的，然后向前倒推，直到初始階段；而決策的具體結(jié)果及所產(chǎn)生的狀態(tài)轉(zhuǎn)移，卻是由初始階段開始進(jìn)行計(jì)算的，然后向后遞歸或迭代，直到最終結(jié)果。

有向連通賦權(quán)圖G=(V，E，W)，頂點(diǎn)集合V劃分成k個(gè)不相交的子集Vi，1≤i≤k，k≥2，使得 中的任一邊(u，v)，必有u∈Vi，V∈Vi+m，m≥1。稱為多段圖。令|V1|=|Vk|=1，稱S∈V1為源點(diǎn)，t∈Vk為收點(diǎn)。多段圖的最長(zhǎng)路徑問題，是求從源點(diǎn)S到達(dá)收點(diǎn)t的最大花費(fèi)的通路。由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。不失一般性，將多段圖的頂點(diǎn)按照段的順序進(jìn)行編號(hào)，同一段內(nèi)頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為n，則源點(diǎn)S的編號(hào)為0，終點(diǎn)t的編號(hào)為n-1，并且，對(duì)圖中的任何一條邊(u，v)，頂點(diǎn)u的編號(hào)小于頂點(diǎn)v的編號(hào)。

下面將分別用上述兩種方法解決一個(gè)資源分配問題。

2 動(dòng)態(tài)規(guī)劃法

資源r劃分為m個(gè)相等的部分，每份資源為t/m，m為整數(shù)。利潤(rùn)函數(shù)Gi(x)，1≤i≤n，0≤x≤m： x份資源分配給第i個(gè)工程所得到的利潤(rùn)，已知分配m份資源給所有工程，所得到的利潤(rùn)總額為：

fc03.tif

使G(m)最大的xi分配方案：(x1，x2，…，xn) 各個(gè)工程按順序編號(hào)，fi(x)：把x份資源分配給前i個(gè)工程時(shí)，所得到的最大利潤(rùn)，di(x)：使fi(x)最大時(shí)，分配給第i個(gè)工程的資源份額。

在第一階段，只把x份資源分配給第一個(gè)工程，有：

在第二階段，只把x份資源分配給前面兩個(gè)工程，有：

一般的，在第i階段，把x份資源分配給前面i個(gè)工程，有：

令第i階段的最大利潤(rùn)為gi，則：

gi=max{fi(1)，…，fi(m)}（3）

設(shè)qi是使gi達(dá)最大時(shí)，分配給前面i個(gè)工程的資源份額，則：

qi=使fi(x)達(dá)最大的x（4）

在每個(gè)階段，把所得到的所有局部決策值fi(x)， di(x)，gi，qi保存起來。最后，在第 階段結(jié)束之后，令全局的最大利潤(rùn)為optg，則：

optg=max{gi ，…，gn}（5）

在全局最大利潤(rùn)下，所分配工程項(xiàng)目的最大編號(hào)（即所分配工程項(xiàng)目的最大數(shù)目）為k，則：

k=使gi達(dá)最大的i（6）

分配給前面k個(gè)工程的最優(yōu)份額為：

optx=與最大的gi相對(duì)應(yīng)的qi（7）

分配給第k個(gè)工程的最優(yōu)份額為：

optqk=dk(optx)

分配給其余k-1個(gè)工程的剩余的最優(yōu)份額為：

optx=optx-dk(optx)

由此回溯，得到分配給前面各個(gè)工程的最優(yōu)份額的遞推關(guān)系式：

由上面的決策過程，可以把求解資源分配問題，劃分為下面四個(gè)步驟：①按(1)(2)式，對(duì)各個(gè)階段i，各個(gè)不同份額x的資源，計(jì)算fi(x)及di(x)；②按(3)(4)式，計(jì)算各個(gè)階段的最大利潤(rùn)gi，及獲得此最大利潤(rùn)的分配份額qi；③按(5)(6)(7)式，計(jì)算全局的最大利潤(rùn)optg，總的最優(yōu)分配份額optx，及編號(hào)最大的工程項(xiàng)目k；

例：有4個(gè)份額的資源，分配給3個(gè)工程，其利潤(rùn)函數(shù)如下：

求資源的最優(yōu)分配方案。

解：在第一階段，只把資源的份額分配給第一個(gè)工程，由(1)式，有：

其次，把資源的份額分配給前面兩個(gè)個(gè)工程

同樣，計(jì)算出f3(x)及d3(x)的值，有：

第二步，按(3)(4)式，求各個(gè)階段的最大利潤(rùn)，及在此利潤(rùn)下的分配份額，有：fc12.tif

第三步，按(5)(6)(7)式，計(jì)算全局的最大利潤(rùn)optg，最大的工程數(shù)目、及總的最優(yōu)分配份額，有：optg=46， optx=4， k=3。

第四步，按(8)式計(jì)算各個(gè)工程的最優(yōu)分配份額，有：fc13.tif

最后的決策結(jié)果：分配給第2、3工程各1個(gè)份額，第1個(gè)工程2個(gè)份額，可得最大利潤(rùn)46。

3 多段圖法

如果把j個(gè)資源分配給第i項(xiàng)工程可獲利潤(rùn)Ｎ(i，j).把資源分配給這n個(gè)項(xiàng)目，要求使總利潤(rùn)達(dá)最大的方法 ．問題可用一個(gè)(n+1)段圖來表示．以段i對(duì)應(yīng)工程項(xiàng)目i（1≤i≤n )，源點(diǎn)S＝V(0，0)，匯點(diǎn)t＝Ｖ（n+1，m），每段有m+1個(gè)頂點(diǎn)Ｖ(i，j)，0≤j≤m，表示共把j個(gè)資源分配給了前i個(gè)工程的利潤(rùn)，圖中所有的邊都具有的形式(1≤i≤n，0≤j≤m)，邊表示N(i+1，j)的利潤(rùn)給工程V(i，j)獲得的利潤(rùn)，最佳分配方案是從圖中S到T的一條最大路徑所確定。

數(shù)組元素cost[i]：存放頂點(diǎn)i到達(dá)收點(diǎn)t的最小花費(fèi)數(shù)組元素path[i]：存放頂點(diǎn)i到達(dá)收點(diǎn)t的最小花費(fèi)通路上的前方頂點(diǎn)編號(hào)數(shù)組route[n]：存放從源點(diǎn)S出發(fā)，到達(dá)收點(diǎn)t的最長(zhǎng)通路上的頂點(diǎn)編號(hào)第一階段，確定第k-1段的所有頂點(diǎn)到達(dá)收點(diǎn)t的花費(fèi)最大的通路。

第二階段，用第一階段的信息，確定第k-2段的所有頂點(diǎn)到達(dá)收點(diǎn)t的花費(fèi)最大的通路。

如此依次進(jìn)行，直到最后確定源點(diǎn)S到達(dá)收點(diǎn) 的花費(fèi)最大的通路。最后，從源點(diǎn)S的path信息中，確定它的前方頂點(diǎn)編號(hào)p1，從p1的path信息中，確定p1的前方頂點(diǎn)編號(hào)p2，如此遞推，直到收點(diǎn)r。

path[i]=使Cij+cost[j]最小的j，i

算法步驟：①對(duì)所有的i，0≤i≤n，把cost[i]初始化為最大值，path[i]初始化為-1；cost[n-1]初始化為0；②令i=n-2；③根據(jù)（1）式和（2）式計(jì)算cost[i]和path[i]；④ i=i-1，若i≥0，轉(zhuǎn)3；否則，轉(zhuǎn)5；⑤令i=0，route[i]=0；⑥如果route[i]=n-1，算法結(jié)束；否則，轉(zhuǎn)7；⑦i=i+1，route[i]=path[route[i-1]]；轉(zhuǎn)6；

由于沒有第4個(gè)工程，所以給第4個(gè)工程分幾份資源所創(chuàng)造的利潤(rùn)都是0。

最后，得到最大利潤(rùn)的路徑a，d，j，p，q，利潤(rùn)為46，分配個(gè)第1個(gè)工程2個(gè)份額，分配給第2，3工程各1個(gè)份額。

4 結(jié)束語(yǔ)

動(dòng)態(tài)規(guī)劃法和多段圖法是是解決資源分配問題的兩種算法，經(jīng)過實(shí)例計(jì)算，兩種算法均可得到資源分配的最優(yōu)解。動(dòng)態(tài)規(guī)劃算法先計(jì)算各個(gè)階段在各種不同份額下的利潤(rùn)，然后計(jì)算各個(gè)階段的最大利潤(rùn)gi，及獲得此最大利潤(rùn)的分配份額qi；最后計(jì)算全局的最大利潤(rùn)optg，總的最優(yōu)分配份額optx，及編號(hào)最大的工程項(xiàng)目k。若工程數(shù)為n，資源數(shù)為m，資源分配算法的時(shí)間復(fù)雜性是O(nm2)，空間復(fù)雜性是O(nm)。多段圖算法在初始化后進(jìn)行分段決策，分別計(jì)算各個(gè)頂點(diǎn)到收點(diǎn)的最大利潤(rùn)，確定各個(gè)頂點(diǎn)到收點(diǎn)的最大利潤(rùn)路徑的前方頂點(diǎn)，因?yàn)轫旤c(diǎn)根據(jù)多段圖的不相交子集順序預(yù)先按照字母編號(hào)，字母順序靠后的頂點(diǎn)首先計(jì)算，保證了在對(duì)每一個(gè)頂點(diǎn)進(jìn)行決策和計(jì)算時(shí)，其到收點(diǎn)路徑上的所有前方頂點(diǎn)都已計(jì)算和決策完畢，所以可直接利用前方頂點(diǎn)的信息，進(jìn)行全局的最優(yōu)決策時(shí)，首先從源點(diǎn)開始，遞推的確定其前方頂點(diǎn)，直到收點(diǎn)為止，多段圖算法時(shí)間復(fù)雜性：O(n+M)，空間復(fù)雜性是O(n)。動(dòng)態(tài)規(guī)劃算法在工程數(shù)和資源數(shù)比較小的情況下可以較快的得到最優(yōu)解，在工程數(shù)和資源數(shù)都較大的情況下，動(dòng)態(tài)規(guī)劃算法在空間和時(shí)間復(fù)雜性上都比多段圖算法復(fù)雜，利用多段圖算法求解資源的最佳分配可以較快的獲得結(jié)果。

參考文獻(xiàn)：

[1] 鄭宗漢，鄭曉明.算法分析與設(shè)計(jì)[M].北京:清華大學(xué)出版社，2005.

[2] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007.

[3] 朱站立.數(shù)據(jù)結(jié)構(gòu)[M].西安：西安交通大學(xué)出版社，2005.

[4] 霍紅衛(wèi).算法設(shè)計(jì)與分析[M].西安：西安電子大學(xué)出版社，2005.

[5] 魏寶剛，陳越，王申康.數(shù)據(jù)結(jié)構(gòu)與算法分析（C語(yǔ)言版）[M].浙江：浙江大學(xué)出版社，2006.

[6] （美）塞奇威克.算法分析導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.

收稿日期：2008-01-12

作者簡(jiǎn)介：樊超（1983-），男，陜西西安人，在讀研究生，研究方向：人工智能與專家系統(tǒng)。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>