動態(tài)規(guī)劃人員分配算法研究

鄧競偉

（西北民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，蘭州　730030）

動態(tài)規(guī)劃人員分配算法研究

鄧競偉

（西北民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，蘭州730030）

0　引言

近年來，突發(fā)事件頻繁發(fā)生，對突發(fā)事件的應(yīng)急管理也引起了國家的高度重視，例如，2014年，云南魯?shù)?.5級地震災(zāi)害，9月重慶洪澇災(zāi)害，新疆和田7.3級地震災(zāi)害動態(tài)規(guī)劃在許多領(lǐng)域中得到越來越廣泛的應(yīng)用，例如經(jīng)濟(jì)領(lǐng)域、工程技術(shù)領(lǐng)域、交通領(lǐng)域等，特別是在世界各地的資源分配中應(yīng)用更為普遍。在資源分配中應(yīng)用動態(tài)規(guī)劃可以使資源得到充分的應(yīng)用，可以得到更大的效益。用動態(tài)規(guī)劃解決資源分配問題是把復(fù)雜的問題劃分為若干個(gè)階段，并逐步解決，最終達(dá)到全局最優(yōu)［1］。Dechter等人分析了常用的Floyd-Warshall算法［2］，從二十世紀(jì)五十年代初美國數(shù)學(xué)家R.E.Bellman［3］等在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理?，F(xiàn)實(shí)生活中已經(jīng)證明許多問題用動態(tài)規(guī)劃求解比用線性規(guī)劃更有效［4］。經(jīng)過多年的科研發(fā)展和實(shí)際應(yīng)用，動態(tài)規(guī)劃日益完善。近幾年，在我國動態(tài)規(guī)劃應(yīng)用越來越普遍，例如：1991年，林學(xué)鈦［5］等對平頂山市地表水和地下水的聯(lián)合管理研究中，運(yùn)用動態(tài)規(guī)劃方法對白龜山水庫進(jìn)行優(yōu)化調(diào)度，取得了良好的效果。實(shí)踐證明，將最短路徑問題、資源分配利用、排序等問題，運(yùn)用動態(tài)規(guī)劃比其他方法更為方便。我們研究資源分配應(yīng)用中的優(yōu)、缺點(diǎn)，能夠使資源得到充分利用，提高資源利用率并創(chuàng)造更大的利潤，可以為動態(tài)規(guī)劃在其他領(lǐng)域的應(yīng)用中提供了很好的幫助。

1　算法實(shí)現(xiàn)

在人工智能領(lǐng)域中，現(xiàn)實(shí)生活中的大多數(shù)問題可以轉(zhuǎn)化為約束滿足規(guī)劃調(diào)度問題來解決［4-5］。動態(tài)規(guī)劃應(yīng)用十分廣泛，本文主要研究動態(tài)規(guī)劃在資源分配中的應(yīng)用，建立模型是解決資源分配問題的方法之一。數(shù)學(xué)模型是指對于現(xiàn)實(shí)世界的一個(gè)特定對象，為了一個(gè)特定目標(biāo)，根據(jù)特有的內(nèi)在規(guī)律，做出一些很有必要的假設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具得到的一個(gè)數(shù)據(jù)結(jié)構(gòu)［5-6］。

動態(tài)規(guī)劃系統(tǒng)的最優(yōu)化是用來解決具有一定序列的確定性系統(tǒng)和隨機(jī)性系統(tǒng)等的最優(yōu)化問題。最優(yōu)化決策是不考慮初始狀態(tài)的，根據(jù)最優(yōu)化過程以相反的順序進(jìn)行的特點(diǎn)，因此，對系統(tǒng)的每個(gè)元素按同樣的順序進(jìn)行編寫號碼。建立一個(gè)合理的動態(tài)規(guī)劃模型，需要從以下幾個(gè)方面進(jìn)行考慮：

（1）把問題按時(shí)間的先后順序劃分為若干個(gè)階段，選出階段變量，這些階段必須是有順序的。

（2）選出狀態(tài)變量，因?yàn)闋顟B(tài)變量能夠表示整個(gè)過程的狀態(tài)轉(zhuǎn)移規(guī)律。

（3）選出決策變量，然后，根據(jù)狀態(tài)之間的遞推關(guān)系得出最終的狀態(tài)轉(zhuǎn)移方程。

（4）建立指標(biāo)函數(shù)和列出動態(tài)規(guī)劃方程，給出最終條件；然后，用逆推的方法推出各個(gè)階段的最優(yōu)決策，再按順序求出整個(gè)問題的最優(yōu)決策，動態(tài)規(guī)劃的基本方程的逆序形式為［6］：

在具體求解時(shí)，從邊界條件n=k開始，從前向后逆推逐個(gè)階段求出最優(yōu)決策和每個(gè)過程的最優(yōu)值，一直到求出f1（x1）的解就是計(jì)算具體問題的最優(yōu)解。

2　具體實(shí)例

根據(jù)具體實(shí)例來分析動態(tài)規(guī)劃在資源分配中的具體應(yīng)用。例如，某一個(gè)公司有A、B、C，3個(gè)車間，現(xiàn)在此公司有4位員工要分配到3個(gè)車間，已知各個(gè)車間獲得這種設(shè)備所能創(chuàng)造的利潤，如表1所示：

表1　員工數(shù)與創(chuàng)造的利潤

此時(shí)，考慮如何將這4位員工分配到3個(gè)車間才能使此公司得到最大的利潤。

首先，假設(shè)3個(gè)車間分別為A、B、C，其中，x表示從第i個(gè)車間分配到第j個(gè)車間的員工數(shù)，xi表示分配到第i個(gè)車間的員工總數(shù)，由此可以得到，從第i+1個(gè)車間分配到第j個(gè)車間的員工總數(shù)為：xi+1=x-xi；fi（x）表示將x位員工從第i個(gè)車間分配到第j個(gè)車間所得到的利潤；gi（xi）表示將xi位員工分配到第i個(gè)車間所得到的利潤。因此，可以得出動態(tài)規(guī)劃模型為：

當(dāng)i=3時(shí)，就是把4位員工都分給第3車間，

同理，當(dāng)i=2時(shí)，就是把4位員工分給第2和3車間，

那么當(dāng)x=0時(shí)，

此時(shí)最優(yōu)決策方案為：d2（x2）=0。

當(dāng)x=1時(shí)，

此時(shí)最優(yōu)決策方案為：d2（x2）=1。

當(dāng)x=2時(shí)，

此時(shí)最優(yōu)決策方案為：d2（x2）=2。

當(dāng)x=3時(shí)，

此時(shí)最優(yōu)決策方案為：d2（x2）=0。

當(dāng)x=4時(shí)，

此時(shí)最優(yōu)決策方案為：d2（x2）=1。

當(dāng)i=1時(shí)，即將公司員工分配給第1和2車間；

同理可得：

此時(shí)最優(yōu)決策方案為：d2（x2）=0。

此時(shí)最優(yōu)決策方案為：d2（x2）=0。

此時(shí)最優(yōu)決策方案為：d2（x2）=0。

此時(shí)最優(yōu)決策方案為：d2（x2）=0或1。

此時(shí)最優(yōu)決策方案為：d2（x2）=2。

因此，可以看出最優(yōu)分配方案有兩種：

第一種：第1個(gè)車間不分配員工，4位員工分別分配給第2和3車間，當(dāng)i=2時(shí)，發(fā)現(xiàn)f2（4）的最優(yōu)規(guī)劃決策方案所得利潤最高。所以，應(yīng)分配1位員工到第2車間，分配3位員工到第3車間。

第二種：第3個(gè)車間不分配員工，4位員工分別分配給第1和2車間，當(dāng)i=1時(shí)，發(fā)現(xiàn)f1（4）的最優(yōu)規(guī)劃決策方案所得利潤最高。所以，應(yīng)分配2位員工到第1車間，分配2位員工到第2車間。

從上面分析可以看出，在這兩種分配方案中，A、B、C，3個(gè)車間的總效益都是15。

3　結(jié)語

動態(tài)規(guī)劃在資源分配中已經(jīng)被廣泛應(yīng)用，這說明動態(tài)規(guī)劃是在解決資源分配這類問題的有效方法。在資源的分配決策中，動態(tài)規(guī)劃使得資源的利用率最高，避免了資源的浪費(fèi)，從而可以使有限的資源創(chuàng)造出最大的經(jīng)濟(jì)利潤。動態(tài)規(guī)劃的應(yīng)用為我們解決了很多實(shí)際問題，對如何建立應(yīng)急資源管理機(jī)制也具有很好理論基礎(chǔ)和現(xiàn)實(shí)意義。

［1］徐瑞，徐曉飛，崔平遠(yuǎn).基于時(shí)間約束網(wǎng)絡(luò)的動態(tài)規(guī)劃調(diào)度算法.計(jì)算機(jī)集成制造系統(tǒng)-CISM［J］，2004.10（1）：188-194.

［2］Muscettola N，Nayak P P，Pell B，Williams B.Remote agent：to boldly go where no AI system has gone before［J］.Artificial Intelligence.1998.103（1-2）：5-47.

［3］滕宇，梁方楚.動態(tài)規(guī)劃原理及應(yīng)用［M］.西南交通大學(xué)出版社.2011.12.

［4］袁佳樂，黃兆華，曹玉紅.動態(tài)規(guī)劃在資源分配上的應(yīng)用.西安文理學(xué)院學(xué)報(bào)：自然科學(xué)版［J］，2008，11（3）：66-69.

［5］盧向南.應(yīng)用運(yùn)籌學(xué)［M］.浙江大學(xué)出版社，2005.

［6］孫寶，王希云.基于MATLAB的動態(tài)規(guī)劃常用算法的實(shí)現(xiàn).太原師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2008，7（4）：26-30.

Dynamic Algorithm；Policy Decision；Planning and Scheduling；Resource Allocation

Research on Dynamic Planning Assignment Algorithm

DENG Jing-wei

（School of Mathematics and Computer Science，Northwest University for Nationalities，Lanzhou 730124）

教育部人文社會科學(xué)研究青年基金項(xiàng)目（No.13YJCZH029、No.12YJCZH027）、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目（No.31920150039）

1007-1423（2015）26-0046-03

10.3969/j.issn.1007-1423.2015.26.012

鄧競偉（1980-），女，甘肅蘭州人，碩士，研究方向?yàn)樽顑?yōu)化理論、算法設(shè)計(jì)與分析

2015-08-04

2015-09-08

如何快速準(zhǔn)確地進(jìn)行資源調(diào)度是突發(fā)事件應(yīng)急資源的重要研究問題，并且及時(shí)有效的資源供給促進(jìn)救援工作的順利進(jìn)行。動態(tài)規(guī)劃在許多領(lǐng)域中都得到十分廣泛的應(yīng)用。介紹動態(tài)規(guī)劃方法、最優(yōu)化原理和動態(tài)規(guī)劃模型，并通過實(shí)例進(jìn)行分析和討論。

動態(tài)算法；決策；規(guī)劃調(diào)度；資源分配

How to carry out resource scheduling is the important research problem of the emergency resources，and the timely and effective resources supply to promote the smooth progress of the rescue work.Dynamic programming is widely used in many fields.Introduces the dynamic programming method，the optimization principle and the dynamic programming model，analyzes and discusses the examples.