馬錦娟， 姚曉鵬， 鄭 挺

(浙江工商大學(xué) 統(tǒng)計(jì)與數(shù)學(xué)學(xué)院，杭州 310018)

1 引 言

1951年美國(guó)學(xué)者Richard.Bellman提出了動(dòng)態(tài)規(guī)劃,用以解決各類(lèi)多階段決策問(wèn)題[1]. 其基本原理是Bellman的最優(yōu)性定理并由此導(dǎo)出的最優(yōu)性原理[2]. 其求解步驟:首先建立問(wèn)題的動(dòng)態(tài)規(guī)劃模型(劃分階段,選擇問(wèn)題的狀態(tài)變量和決策變量,列出狀態(tài)轉(zhuǎn)移方程,描述問(wèn)題的指標(biāo)體系,列出動(dòng)態(tài)規(guī)劃方程).其次,遞推計(jì)算(按所列出的動(dòng)態(tài)規(guī)劃方程分階段逐一計(jì)算).最后,以遞推計(jì)算結(jié)果為基礎(chǔ),以狀態(tài)轉(zhuǎn)移方程為紐帶,按與遞推計(jì)算相反方向?qū)ふ易顑?yōu)策略[3].對(duì)一類(lèi)資源平行分配問(wèn)題,文獻(xiàn)[4]給出一種匈牙利方法.由資源平行分配的特點(diǎn),我們根據(jù)人數(shù)少于任務(wù)數(shù)的指派模型(非標(biāo)準(zhǔn)指派模型[3])給出一種求解的方法.

2 人數(shù)少于任務(wù)數(shù)的指派模型

設(shè)有n人,m項(xiàng)工作(n≤m),每人可做多項(xiàng)工作,每項(xiàng)工作只被一人做.效率(或損失)矩陣為

問(wèn)如何安排可使總的效率達(dá)到最大(或損失最小).

設(shè)

則該問(wèn)題的線(xiàn)性規(guī)劃模型:

3 資源平行分配問(wèn)題的“人數(shù)少于任務(wù)數(shù)的指派模型”求解方法

為了敘述方便,首先給出

定義[5]設(shè)n,n1,n2,…,nk均為正整數(shù),稱(chēng)n=n1+n2+…+nk為整數(shù)n的一個(gè)k分部的分拆.若該分拆與n1,n2,…,nk的順序有關(guān),則稱(chēng)為有序分拆;否則稱(chēng)為無(wú)序分拆.另外,若對(duì)ni(i=1,2,…,k)有限制,則稱(chēng)為有限制分拆,否則稱(chēng)為無(wú)限制分拆.

在資源平行分配中,正整數(shù)n的分拆中允許ni=0(i=1,2,…,k).

對(duì)于資源總量為n,被分配的部門(mén)數(shù)量為k及效率(或收益或損失等)矩陣為A=(aij)(aij表示第j部門(mén)分配到第i種資源的數(shù)量)的分配問(wèn)題,下面我們總是假設(shè)需要資源的部門(mén)稱(chēng)為指派問(wèn)題中的“任務(wù)”(有幾個(gè)部門(mén)即表示有幾項(xiàng)“任務(wù)”),資源的一種分配稱(chēng)為指派問(wèn)題中的“人”(有幾種資源的分配即表示有幾個(gè)“人”).

指定n的k分部有限制無(wú)序分拆n=y1+y2+…+yk,對(duì)應(yīng)一個(gè)效率矩陣U(y1y2…yk),其第i行為A中的第yi行.若yi=yj,此時(shí)出現(xiàn)第i行與第j行相同,則只寫(xiě)一行,相同的行不重復(fù)寫(xiě).此時(shí)還需要特別強(qiáng)調(diào)的是,由yi(資源的一種分配)這個(gè)“人”與yj這個(gè)“人”相同,所以,yi這個(gè)“人”需要完成兩項(xiàng)“任務(wù)”.

下面是所介紹的方法的具體步驟:

(a) 寫(xiě)出分配問(wèn)題的效率矩陣A和資源總量n的所有k(個(gè)部門(mén))分部有限制無(wú)序分拆;

(b) 對(duì)每一個(gè)分拆y1,y2,…,yk,寫(xiě)出對(duì)應(yīng)的效率(或收益或損失)矩陣U(y1,y2,…yk);

(c) 根據(jù)1的內(nèi)容,寫(xiě)出U(y1,y2,…yk)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型(若有ni個(gè)yi相同,則表示yi這個(gè)“人”需要完成ni項(xiàng)任務(wù))并求解;

(d) 所有解中的最大者(或最小者)即為所求.

4 應(yīng)用舉例

某警衛(wèi)部門(mén)有12支衛(wèi)隊(duì)負(fù)責(zé)A, B, C, D四個(gè)要害部門(mén),每個(gè)部門(mén)需要2-4支衛(wèi)隊(duì)巡邏.派出的衛(wèi)隊(duì)數(shù)不同,則各部門(mén)預(yù)期在一段時(shí)間內(nèi)可能造成的損失有差別,如下表所示:

預(yù) 期 損 失部 門(mén)衛(wèi) 隊(duì) 數(shù)A BCD2183824 34314352231410312125

問(wèn)應(yīng)往各部門(mén)派多少支衛(wèi)隊(duì)巡邏,可使總的預(yù)期損失最小？

解此問(wèn)題中,資源總量為12,部門(mén)有四個(gè): A, B, C, D,對(duì)應(yīng)于指派問(wèn)題中有四項(xiàng)“任務(wù)”;資源分配有三種:2，3，4,對(duì)應(yīng)于指派問(wèn)題中有三個(gè)“人”.四項(xiàng)任務(wù)被三人完成.

(a) 損失矩陣為

令變量yi(i=1,2,3,4)為派往第i部門(mén)的衛(wèi)隊(duì)數(shù).于是得整數(shù)12的所有4部有限制的無(wú)序分拆為

12=y1+y2+y3+y4, 2≤yi≤4, 1≤i≤4.

共有三種不同分拆:

12=4+4+2+2 12=4+3+3+2 12=3+3+3+3.

(b) 對(duì)第一種分拆12=4+4+2+2表示向四個(gè)部門(mén)中的兩個(gè)部門(mén)各派4支衛(wèi)隊(duì),向另外兩個(gè)部門(mén)各派2支衛(wèi)隊(duì).下面具體的求出向哪兩個(gè)部門(mén)派4支衛(wèi)隊(duì), 向哪兩個(gè)部門(mén)派2支衛(wèi)隊(duì).

將四個(gè)部門(mén)A, B, C, D稱(chēng)為四項(xiàng)“任務(wù)”;由于該分拆(y1=y2=4,y3=y4=2)中只有2,4兩個(gè)不同的數(shù)(是資源的兩種不同分配),由于2,4在排列中各出現(xiàn)兩次,此時(shí)損失矩陣U(2244)(由A中2和4所在的行組成,即由A中第一和第三行組成,相同的行不重復(fù)寫(xiě))為

對(duì)第二種分拆12=4+3+3+2表示向四個(gè)部門(mén)中的兩個(gè)部門(mén)各派4支和2支衛(wèi)隊(duì),向另外兩個(gè)部門(mén)各派3支衛(wèi)隊(duì),下面具體的求出向哪兩個(gè)部門(mén)分別派4支和2支衛(wèi)隊(duì),向哪兩個(gè)部門(mén)各派3支衛(wèi)隊(duì).

四項(xiàng)“任務(wù)” A, B, C, D被2,3,4這三個(gè)“人”來(lái)做.由于該分拆中只有2,3,4三個(gè)不同的數(shù),此時(shí)損失矩陣為(由矩陣A中2,3,4所在的行組成,相同的行不重復(fù)寫(xiě))

對(duì)第三種分拆12=3+3+3+3,表示向四個(gè)部門(mén)各派3支衛(wèi)隊(duì).

四項(xiàng)“任務(wù)” A, B, C, D被3這一個(gè)“人”來(lái)完成.由于該分拆中只有3這一個(gè)數(shù),此時(shí)損失矩陣為

U(3333)=(14 35 22 31).

(c) 由1得U(2244)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型(由于2,4在排列中各出現(xiàn)兩次,所以2這個(gè)“人”和4這個(gè)“人” 對(duì)這四項(xiàng)工作各做兩項(xiàng)):

min18x11+38x12+24x13+34x14+10x21+31x22+21x23+25x24，

由文獻(xiàn)[6]中Matlab計(jì)算得

x12=x13=x21=x24=1, 其它xij=0.

即向A部門(mén)派4支衛(wèi)隊(duì), 向B部門(mén)派2支衛(wèi)隊(duì), 向C部門(mén)派2支衛(wèi)隊(duì), 向D部門(mén)派4支衛(wèi)隊(duì),最小損失為97.

繼續(xù)由1得U(2334)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型(注意到該分拆中,2出現(xiàn)一次,3出現(xiàn)兩次,4出現(xiàn)一次,這說(shuō)明,2這個(gè)“人”只做一項(xiàng)工作,3這個(gè)“人”做兩項(xiàng)工作,4這個(gè)“人”做一項(xiàng)工作):

min18x11+38x12+24x13+34x14+14x21+35x22+22x23+31x24+10x31+31x32+21x33+25x34,

由Matlab計(jì)算得

x13=x21=x22=x34=1, 其它xij=0.

即向A部門(mén)派3支衛(wèi)隊(duì), 向B部門(mén)派3支衛(wèi)隊(duì), 向C部門(mén)派2支衛(wèi)隊(duì), 向D部門(mén)派4支衛(wèi)隊(duì),最小損失為98.

由1得U(3333)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型(注意到該分拆中,3出現(xiàn)四次,所以,3這個(gè)“人”要完成4項(xiàng)“任務(wù)”):

min14x11+35x12+22x13+31x14,

此時(shí)最小損失顯然為14+35+22+31=102.

(d) 由min{97,98,102}=97知,應(yīng)該選擇方案:

向A部門(mén)派4支衛(wèi)隊(duì),向B部門(mén)派2支衛(wèi)隊(duì), 向C部門(mén)派2支衛(wèi)隊(duì),向D部門(mén)派4支衛(wèi)隊(duì).最小損失為97.

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

文獻(xiàn)[4]中,對(duì)n的任一個(gè)k分部劃分(分拆),用FORTRAN77程序必須求解一個(gè)有k2個(gè)決策變量且有2k個(gè)約束條件的0-1規(guī)劃問(wèn)題.當(dāng)某個(gè)分拆中有相同的數(shù)時(shí),本文模型中有著決策變量少且約束條件少的優(yōu)點(diǎn).如3的例中,分拆2244對(duì)應(yīng)的0-1規(guī)劃模型中,決策變量只需8個(gè),約束條件6個(gè);若用[4]中的方法,決策變量需要16個(gè),約束條件要8個(gè).

[參 考 文 獻(xiàn)]

[1] 楊超，熊偉，白亞根. 運(yùn)籌學(xué)[M]. 北京:科學(xué)出版社,2004:232-234.

[2] 陳華友. 運(yùn)籌學(xué)[M]. 合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,2008:191-195.

[3] 吳祈宗. 運(yùn)籌學(xué)[M]. 北京:北京理工大學(xué)出版社,2011:157-158,168-169.

[4] 趙茂先，萬(wàn)賢美，黃珍. 匈牙利方法在資源分配問(wèn)題中的應(yīng)用[J]. 山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2001(2):18-20.

[5] 盧開(kāi)澄，盧華明. 組合數(shù)學(xué)[M]. 北京:清華大學(xué)出版社,2002:80-85.

[6] 張伯生，范君暉，田書(shū)格. 運(yùn)籌學(xué)[M]. 北京:科學(xué)出版社, 2008:158-161.