宋占嶺 冀秀春 炮兵指揮學(xué)院，河北宣化 075100

利用動(dòng)態(tài)規(guī)劃求解資源分配問(wèn)題的單表迭代法

宋占嶺 冀秀春 炮兵指揮學(xué)院，河北宣化 075100

將用動(dòng)態(tài)規(guī)劃求解資源分配問(wèn)題時(shí)的各階段迭代表格進(jìn)行統(tǒng)一集成，利用基本方程遞推關(guān)系式在同一表格中進(jìn)行迭代，層次清晰，結(jié)果直觀，利于計(jì)算機(jī)編程實(shí)現(xiàn)。

動(dòng)態(tài)規(guī)劃;資源分配問(wèn)題;迭代法

動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它是解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。這一方法最初是由美國(guó)數(shù)學(xué)家貝爾曼（R. Bellman）等人在20世紀(jì)50年代提出的。它根據(jù)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換成為一系列相互關(guān)聯(lián)的單階段決策問(wèn)題，然后逐個(gè)加以解決。動(dòng)態(tài)規(guī)劃的核心是最優(yōu)性原理，即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。動(dòng)態(tài)規(guī)劃在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等領(lǐng)域中都有廣泛的應(yīng)用，并且取得了顯著的效果。實(shí)踐證明許多問(wèn)題用動(dòng)態(tài)規(guī)劃求解比用線性規(guī)劃或非線性規(guī)劃更加有效，特別是對(duì)離散性問(wèn)題，運(yùn)用解析數(shù)學(xué)無(wú)法解決，而動(dòng)態(tài)規(guī)劃就成為得力的工具。

1. 資源分配問(wèn)題的動(dòng)態(tài)規(guī)劃模型

資源分配問(wèn)題亦稱投資問(wèn)題，其一般提法如下：

設(shè)總投資額為a萬(wàn)元，擬投資于幾個(gè)項(xiàng)目上，已知對(duì)第i個(gè)項(xiàng)目投資xi萬(wàn)元，收益函數(shù)為gi(xi)。問(wèn)應(yīng)如何分配資金才可以使總收益最大?

當(dāng)gi(xi)為線性函數(shù)時(shí)，它是一個(gè)線性規(guī)劃問(wèn)題；當(dāng)gi(xi)為非線性函數(shù)時(shí)，它是一個(gè)非線性規(guī)劃問(wèn)題。為了應(yīng)用動(dòng)態(tài)規(guī)劃方法求解這類靜態(tài)規(guī)劃問(wèn)題，可以人為地賦予它“時(shí)段”的概念，將投資項(xiàng)目排序，假想對(duì)各個(gè)投資項(xiàng)目有先后順序。首先考慮對(duì)項(xiàng)目1的投資，然后考慮對(duì)項(xiàng)目2的投資，依次最后考慮第n項(xiàng)投資，這樣就把原問(wèn)題轉(zhuǎn)化為n階段的決策過(guò)程。把問(wèn)題中的變量xi作為決策變量，將累計(jì)的量或隨遞推過(guò)程變化的量設(shè)為狀態(tài)變量。

狀態(tài)變量sk表示第k階段可用于第k個(gè)到第n個(gè)項(xiàng)目的資金數(shù)，顯然有s1=a，sn=0。

決策變量xk即應(yīng)分配第k個(gè)項(xiàng)目上的投資額。

狀態(tài)轉(zhuǎn)移方程 sk+1=sk－xk。

最優(yōu)指標(biāo)函數(shù)fk(sk) 表示當(dāng)可投資金數(shù)為sk時(shí)，投資于剩余的n－k+1個(gè)項(xiàng)目的最大收益。則基本方程為

求解此類問(wèn)題的常用方法是列出其各階段投資決策收益表，利用基本方程遞推關(guān)系式進(jìn)行逐級(jí)迭代，最后求得f1(a)即為所求問(wèn)題的最大收益，我們稱之為“多表迭代法”。下面以文獻(xiàn)[1]213頁(yè)例1介紹之。

問(wèn)題描述：某工業(yè)部門(mén)根據(jù)國(guó)家計(jì)劃安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三家工廠，各廠獲得這種設(shè)備之后可以為國(guó)家提供盈利如表1所示。問(wèn)這五臺(tái)設(shè)備如何分配給各廠，才能使國(guó)家得到利益最大。

表1

建立模型后，其基本方程為

多表迭代求解過(guò)程如下：

k=3時(shí)，數(shù)值計(jì)算如表2所示。

表2

k=2時(shí)，數(shù)值計(jì)算如表3所示。

表3

k=1時(shí)，數(shù)值計(jì)算如表4所示。

表4

最后按計(jì)算表格順序反推，可知最優(yōu)分配方案有兩個(gè)：甲、乙、丙三廠分別分配0、2、3臺(tái)及2、2、1臺(tái)，均達(dá)到總盈利最大為21萬(wàn)元。

多表迭代法原理清晰，直觀明了，但模型中有幾個(gè)階段就要列出幾個(gè)表格，然后利用表格數(shù)據(jù)進(jìn)行反復(fù)迭代，顯得有些繁瑣，不便于計(jì)算機(jī)編程實(shí)現(xiàn)。為此，筆者將各階段表格進(jìn)行統(tǒng)一集成，利用基本方程遞推關(guān)系式在同一表格中進(jìn)行迭代，以利于計(jì)算機(jī)編程實(shí)現(xiàn)，稱之為“單表迭代法”。

2. 單表迭代法

單表迭代法計(jì)算步驟為：

（1）求出各階段最優(yōu)指標(biāo)函數(shù)值，存放于迭代表中；

（2）將各階段每一可能狀態(tài)條件下的各指標(biāo)函數(shù)與下一階段的最優(yōu)指標(biāo)函數(shù)交叉相加后尋優(yōu)，同時(shí)標(biāo)出最優(yōu)路徑；

（3）根據(jù)最優(yōu)路徑確定最優(yōu)決策。

前述問(wèn)題求解結(jié)果見(jiàn)表5。

表5

單表迭代法在求解較大規(guī)模的問(wèn)題時(shí)，具有很大的優(yōu)越性。表6中的投資分配問(wèn)題中，有6個(gè)單位的資源和4個(gè)方案，各方案在不同投資額條件下收益不同（具體數(shù)值參見(jiàn)表6），建立模型后，其基本方程為

用單表迭代法求解獲益最大的投資結(jié)果見(jiàn)表6 。

由表6中迭代結(jié)果可知，此投資問(wèn)題的最大收益為220個(gè)單位，共有5個(gè)最優(yōu)方案可實(shí)現(xiàn)之。

表6

3. 結(jié)論

利用動(dòng)態(tài)規(guī)劃求解資源分配問(wèn)題的“單表迭代法”將“多表迭代法”的多個(gè)表格統(tǒng)一集成為一個(gè)表格，所有迭代計(jì)算都在同一表格中進(jìn)行，層次清晰，結(jié)果直觀，更便于計(jì)算機(jī)編程實(shí)現(xiàn)。單表迭代法對(duì)于順序遞推基本方程以及最優(yōu)取最小值的資源分配問(wèn)題同樣適用。

[1] 運(yùn)籌學(xué)教材編寫(xiě)組. 運(yùn)籌學(xué)（第三版）[M]. 北京：清華大學(xué)出版社.2001

[2] 張野鵬. 軍事運(yùn)籌基礎(chǔ)[M]. 北京：高等教育出版社.2006

10.3969/j.issn.1001-8972.2011.10.028

作者信息

宋占嶺（1968—），男，河北宣化人，碩士；研究方向：軍事運(yùn)籌學(xué)。