非標(biāo)準(zhǔn)形式的指派模型在資源分配問題中的應(yīng)用

馬錦娟， 姚曉鵬， 鄭 挺

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

1 引 言

1951年美國學(xué)者Richard.Bellman提出了動態(tài)規(guī)劃,用以解決各類多階段決策問題[1]. 其基本原理是Bellman的最優(yōu)性定理并由此導(dǎo)出的最優(yōu)性原理[2]. 其求解步驟:首先建立問題的動態(tài)規(guī)劃模型(劃分階段,選擇問題的狀態(tài)變量和決策變量,列出狀態(tài)轉(zhuǎn)移方程,描述問題的指標(biāo)體系,列出動態(tài)規(guī)劃方程).其次,遞推計(jì)算(按所列出的動態(tài)規(guī)劃方程分階段逐一計(jì)算).最后,以遞推計(jì)算結(jié)果為基礎(chǔ),以狀態(tài)轉(zhuǎn)移方程為紐帶,按與遞推計(jì)算相反方向?qū)ふ易顑?yōu)策略[3].對一類資源平行分配問題,文獻(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)工作只被一人做.效率(或損失)矩陣為

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

設(shè)

則該問題的線性規(guī)劃模型:

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

為了敘述方便,首先給出

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

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

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

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

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

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

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

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

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

4 應(yīng)用舉例

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

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

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

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

(a) 損失矩陣為

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

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) 對第一種分拆12=4+4+2+2表示向四個部門中的兩個部門各派4支衛(wèi)隊(duì),向另外兩個部門各派2支衛(wèi)隊(duì).下面具體的求出向哪兩個部門派4支衛(wèi)隊(duì), 向哪兩個部門派2支衛(wèi)隊(duì).

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

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

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

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

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

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

(c) 由1得U(2244)對應(yīng)的線性規(guī)劃模型(由于2,4在排列中各出現(xiàn)兩次,所以2這個“人”和4這個“人” 對這四項(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部門派4支衛(wèi)隊(duì), 向B部門派2支衛(wèi)隊(duì), 向C部門派2支衛(wèi)隊(duì), 向D部門派4支衛(wèi)隊(duì),最小損失為97.

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

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

由Matlab計(jì)算得

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

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

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

min14x11+35x12+22x13+31x14,

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

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

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

5 結(jié)束語

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

[參 考 文 獻(xiàn)]

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

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

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

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

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

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