簡表法解決的一類資源分配問題

李承耕，劉 波

(韓山師范學院 數學與統計系,廣東 潮州 521041)

簡表法解決的一類資源分配問題

李承耕，劉 波

(韓山師范學院 數學與統計系,廣東 潮州 521041)

針對宏觀管理與系統規(guī)劃中的設點問題,給出將靜態(tài)規(guī)劃轉化為動態(tài)規(guī)劃的思路,并提出用簡表法完成階段尋優(yōu)問題,并由此獲得資源分配問題的最優(yōu)結果．

設點決策;靜態(tài)規(guī)劃;動態(tài)規(guī)劃;最優(yōu)策略;階段尋優(yōu)

動態(tài)規(guī)劃也稱多階段決策,是一種重要的算法設計思想,在算法設計中具有廣泛的應用,動態(tài)規(guī)劃具有空間換時間(空間消耗大,時間效率高)的特點,當然也有一部分時間效率不高,仍然存在優(yōu)化的余地,本文通過將動態(tài)規(guī)劃用簡表法來實現來達到空間換時間,以節(jié)省大量計算量的目的．

1 經濟背景與數學模型

在社會經濟活動中,作為生產宏觀管理部門會經常遇到資源的分配問題,在資源有限的情況下,如何將資源分配到各個項目子系統,從而使得系統的總收益最大或總投入最小．根據以上經濟問題,我們可以作如下假設

1.設目標函數的最大收益為maxz,或最小開支為minz.

2.第i個 項目投入的資源量為xi,設資源總數m.

3.已知資源函數與收益函數分別為gi(xi).

2 基本算法討論

我們可以用動態(tài)規(guī)劃的方法來處理這類問題．

1)將每個項目的投資看成是動態(tài)規(guī)劃的一個階段．

2)將每個項目的投資數x確定為狀態(tài)變量．

3)將收益函數(或投入函數)gk(y)看作階段指標,前k-1個區(qū)位上x-y個項目所產生的最大收益(或最小投入)fk(x-y)即為最優(yōu)指標函數．

4)顯然原倆問題是要求fn(m)．

由此,我們得到動態(tài)規(guī)劃的遞Bellman推式(依順序解法)

求fn(m)

3 應用舉例

(1)利潤最大化問題

實例1:設有某種資源5個單位,可以投入4種生產,可以獲得利潤如下表1所示:

表1 各單位利潤

問如何分配資源,使得總利潤最大．

有f0(y)=0,所以f1(x)=g1(y)由以下遞推式得階段尋優(yōu)表．

表2 利潤最大化

從表2可以得出最大利潤為f4(5)=14,最優(yōu)解為x1=3,x3=2,x2=x4=0;

或x1=4,x3=1,x2=x4=0;

所以最優(yōu)決策為投資第一項目3個資源,第三個項目2個資源,其他項目0個資源,或第一個項目4個資源,第三個項目1個資源,其它項目0個資源,最大利潤為14．

(2)最小化問題

實例2某一警衛(wèi)部門工有九支巡邏隊,負責A,B,C三個要害部門的巡邏,對每個部門可以派出2～4支巡邏隊,其中預期損失如下表3所示,問如何分派巡邏隊可以使得總損失最?。?/p>

表3 預期損失 (單位為:萬元)

設xk為第k個部門所派的巡邏隊的數目,sk為前k-1個部門的巡邏隊的數目,則有sk=sk+1-xk用順序解法我們有如下遞推式:

表4 最小損失

由表4我們可以知道最小損失為f3(s4)=69(萬元)

最優(yōu)決策為x1=3,x2=4,x3=2或x1=4,x2=3,x3=2,即警衛(wèi)部門應該在A區(qū)派3支巡邏隊,在B區(qū)派4支巡邏隊,在C區(qū)派2支巡邏隊,或在A區(qū)派4支巡邏隊,在B區(qū)派3支巡邏隊,在C區(qū)派2支巡邏隊．這樣才能使得預期損失最?。?/p>

4 結束語

簡表法實際上是將動態(tài)規(guī)劃的問題在表上實現,對于狀態(tài)變量是自然數的這一類整點問題,利用簡表法較Bellman遞推式法,在處理數據方面更加有條理,由階段最優(yōu)點尋找整體最優(yōu)決策更方便．總之,簡表法對于很多種資源分配問題和設點問題都是行之有效的．

[1] 羅榮桂.新編運籌學題解[M].武漢:華中科技大學出版社,2002

[2] 胡運權.運籌學基礎與應用[M].北京:高等教育出版社,2004

[3] 程叢電,唐恒永.一類資源分配與排序問題[J].數學實踐與認識,2006(1):5-28

[4] 徐玖平,胡知能,李 軍.運籌學[M].北京:科技出版社,2004

A Type of Resourse Allocation Problem with Abridged Table to Deal with

Li Chenggeng, Liu Bo

(Department of Mathematics and Applied Mathematics,Hanshan Normal University,Chaozhou 521041, China)

To aim at the problem of set-point in the macro-management and systems organization, give a thought which transform the problem of static progromming to the problem of dynamic progromming. furthermore,we can resovle the problem of stage optimization with the method of abridged table, so we also can obtain the optimum solution of resourse allocation problem.

set-point decision;static programming;dynamic programming;optimal strategy;stage optimization

2014-11-25 基金項目:韓山師范學院2013年“創(chuàng)新強校工程”科研與學科建設項目．

李承耕(1969-),男,湖北云夢人，碩士,韓山師范學院講師,主要從事非線性泛函理論研究．

1672-2027(2015)01-0017-03

O221.3

A