離散資源分配問題的最優(yōu)方法

孫建新

(1.紹興文理學(xué)院 數(shù)學(xué)系,浙江 紹興312000；2.浙江越秀外國語學(xué)院 國際教育學(xué)院，浙江 紹興312000)

0 引言

文獻(xiàn)[1]指出：席位分配屬于離散資源分配問題，而適用于離散資源分配的公理總共有7條：部門無偏性公理(Ax.1)，資源單調(diào)性公理(Ax.2)，人數(shù)緊鄰性公理(Ax.3)，資源緊鄰性公理(Ax.4)，分配最優(yōu)性公理(Ax.5)，統(tǒng)一普適性公理(Ax.6)，指標(biāo)無偏性公理(Ax.7).這些公理不全相容，而是存在4個“極大相容公理組”，它們分別是

(ⅰ)ESCA1={Ax.1,Ax.2,Ax.6,Ax.7}；

(ⅱ)ESCA2={Ax.1,Ax.5,Ax.6,Ax.7}；

(ⅲ)ESCA3={Ax.3,Ax.5,Ax.6,Ax.7}；

(ⅳ)ESCA4={Ax.4,Ax.5,Ax.6,Ax.7}.

本文根據(jù)離散資源的不同類型，對應(yīng)地適用不同的極大相容公理組，然后給出該類分配的相應(yīng)數(shù)學(xué)模型以及最優(yōu)的分配方法.

1 離散資源的類型

所謂離散資源分配問題就是：屬于某社會團(tuán)體的成員被劃分成若干部門，而團(tuán)體所擁有的某種一定量的資源被稱為是離散資源，是指分給每個部門的資源量必須是非負(fù)整數(shù)，要解決的問題是團(tuán)體如何將這些離散資源公平地全部分給下屬部門.

在實際問題中，團(tuán)體可以是學(xué)校、醫(yī)院、工廠、農(nóng)莊等企事業(yè)單位，也可以是國家、北約、APEC等政治、軍事、經(jīng)濟(jì)等組織.資源可以是活動空間或場所、交通工具、辦公用具、通訊工具、醫(yī)療衛(wèi)生健身娛樂以及生活用具等物品或準(zhǔn)入票據(jù)(包括俱樂部的會員卡、影戲歌舞盛會的入場券、其他招待券通行證或門票)，也可以是各部門評優(yōu)獎勵或參與團(tuán)體的會議、考察、旅游、宴會以及其他社交活動的限定名額(相當(dāng)于席位問題的代表數(shù)).

首先，離散資源可以分為永久性資源與暫存性資源兩大類，例如席位一般是永久性資源，而入場券則是暫存性資源(一次性資源).其次，永久性資源又分為時變(time variant)與時不變(time invariant)兩型；而暫存性資源又分為獨占性與共享性兩型.

2 離散資源分配的數(shù)學(xué)模型

(1)

其中

wi=aih/a(h),a(h)=∑aih(1≤i≤m),X∈A,a∈A,A={N,P,S,R,T,T-1}.

(2)

約束條件為總資源的完全分配與部門資源的整數(shù)約束，目標(biāo)函數(shù)為指標(biāo)向量偏離理想向量的距離.此外，根據(jù)是否必須滿足文獻(xiàn)[1]公理Ax.4，可以分為緊約束與寬約束兩類資源分配模型：

Ⅰ.資源分配的寬約束模型

(3)

Ⅱ.資源分配的緊約束模型

(4)

注意到，只有作為永久性資源才與時間相關(guān)，只有長時間存在的資源才會發(fā)生某些分配方法的資源非單調(diào)性(例如席位分配的哈密頓法不滿足席位單調(diào)性[2])；反之，對于暫存性資源，人們往往對一次性分配僅僅關(guān)注是否與應(yīng)得份額接近(緊鄰性).由此可見，資源分配的寬約束模型適用于永久性資源的分配,緊約束模型適用于暫存性資源的分配.

3 資源類型與極大公理相容組的關(guān)系

在永久性資源的分配中，顯然時變型資源的分配應(yīng)該優(yōu)先考慮資源單調(diào)性，即Ax.2，而含Ax.2的極大相容公理組為ESCA1；時不變型資源的分配應(yīng)該優(yōu)先考慮分配最優(yōu)性，即Ax.5，在寬約束模型中含Ax.5的極大相容公理組為ESCA2.

在暫存性資源的分配中，顯然共享型資源的分配應(yīng)該優(yōu)先考慮成員單調(diào)性，即Ax.3，而含Ax.3的極大相容公理組為ESCA3；獨占型資源的分配應(yīng)該優(yōu)先考慮資源緊鄰性，即Ax.4，而含Ax.4的極大相容公理組為ESCA4.

4 時變永久性離散資源的最優(yōu)分配方法

時變永久性離散資源分配的典型問題是編制不固定的團(tuán)體公平地將會議的全部席位分配給所屬部門.著名實例如美國眾議院將席位分給50個州的問題.

以下約定：Ai(s)，Gi(s)，Hi(s)分別表示第i個部門的預(yù)分配率si-與后分配率si+的算術(shù)平均、幾何平均、調(diào)和平均.顯然，分配中分配率小于總分配率s的部門吃虧，s-si稱為分配率絕對偏差，s-Ai(s)稱為分配率算術(shù)平均絕對偏差(Absolute Deviation of Arithmetic Mean of s)，簡記作Adam(s);(s-Ai(s))/pi稱為分配率算術(shù)平均相對偏差，簡記作Rdam(s).所謂“偏差指標(biāo)分配法”就是將資源的初始分配的余額優(yōu)先分給某個(絕對或相對)偏差最大的部門.以分配率算術(shù)平均絕對偏差A(yù)dam(s)作為指標(biāo)的分配法簡稱Adam(s)法；以其相對偏差Rdam(s)作為指標(biāo)的分配法簡稱Rdam(s)法.

定理1 時變永久性離散資源分配的最優(yōu)方法為“Adam(s)法”.

證明如前所述，時變永久性離散資源分配的最優(yōu)方法應(yīng)該滿足極大相容公理組ESCA1，即要求分配方法滿足{Ax.1,Ax.2,Ax.6,Ax.7}.

因為滿足Ax.2必滿足Ax.1(見文獻(xiàn)[1]推論4.3)，由文獻(xiàn)[1]表7.1可知滿足Ax.2則對于數(shù)學(xué)模型(3)有k=1,h=0,X∈{S,R,T,T-1};滿足Ax.6,對于模型(3)有X∈{N,P,S,T};同時滿足Ax.2和Ax.6,必須k=1,h=0,X∈{S,T}，由文獻(xiàn)[1]中推論3.3知指標(biāo)T與S等價.于是僅須考慮模型

(5)

不失一般性,假設(shè)最后一個資源余額的分配部門僅在{1,2}中選擇且si-≤s≤si+,i=1,2.則應(yīng)該將余額分給部門i=1，如果

|s1--s|+|s2+-s|>|s1+-s|+|s2--s|,

即

s-s1-+s2+-s>s1+-s+s-s2-,

這等價于

A1(s)

這就證明了滿足ESCA1的最優(yōu)分配方法應(yīng)該將剩余資源優(yōu)先分給指標(biāo)Ai(s)最小即s-Ai(s)最大的部門即采用Adam(s)法.注意到指標(biāo)Ai(s)與s-Ai(s)都滿足Ax.7，所以時變永久性離散資源分配的最優(yōu)方法是Adam(s)法.

5 時不變永久性離散資源的最優(yōu)分配方法

引理1si+-si-=1/pi.

證明si+-si-=ni+/pi-ni-/pi=(ni+-ni-)/pi=1/pi.

定理2 時不變永久性離散資源分配的最優(yōu)方法為“Rdam(s)法”.

證明類似地，時不變永久性離散資源分配的最優(yōu)方法應(yīng)該滿足極大相容公理組ESCA2，即要求分配方法滿足{Ax.1,Ax.5,Ax.6,Ax.7}.

由文獻(xiàn)[1]表7.1可知，滿足Ax.1則對于數(shù)學(xué)模型(3)有h=0,X∈{S,R,T,T-1};滿足Ax.5,對于模型(3)有k=2;滿足Ax.6,對于模型(3)有X∈{N,P,S,T},且指標(biāo)T與S等價.于是僅須考慮模型

(6)

不失一般性，假設(shè)最后一個資源余額的分配部門僅在{1,2}中選擇且si-≤s≤si+,i=1,2.則應(yīng)該將余額分給部門i=1，如果

|s1--s|2+|s2+-s|2>|s1+-s|2+|s2--s|2,

即

(s1-)2-2ss1-+(s2+)2-2ss2+>(s1+)2-2ss1++(s2-)2-2ss2-,

由引理1，這等價于

這就證明了滿足ESCA2的最優(yōu)分配方法應(yīng)該將剩余資源優(yōu)先分給指標(biāo)(s-Ai(s))/pi最大的部門即Rdam(s)法.注意到指標(biāo)(s-Ai(s))/pi滿足Ax.7，所以時不變永久性離散資源分配的最優(yōu)方法是Rdam(s)法.

6 獨占暫存性離散資源的最優(yōu)分配方法

記qi=npi/p,ni-=[qi](下取整)，ni+=ni-+1，bi=qi-ni-.將剩余資源優(yōu)先分給尾數(shù)bi最大的部門的分配方法稱為哈密頓法(Hamilton法)[2].

定理3 獨占暫存性離散資源分配的最優(yōu)方法為“Hamilton法”.

證明類似地，獨占暫存性離散資源分配的最優(yōu)方法應(yīng)該滿足極大相容公理組ESCA4，即要求分配方法滿足{Ax.4,Ax.5,Ax.6,Ax.7}.

由文獻(xiàn)[1]表7.1可知，滿足Ax.4則對于數(shù)學(xué)模型(3)有X=N,k∈{1,2};滿足Ax.5,對于模型(3)有k=2;滿足Ax.6,對于模型(3)有X∈{N,P,S,T}；于是僅須考慮模型

(7)

不失一般性，假設(shè)最后一個資源余額的分配部門僅在{1,2}中選擇且ni-≤n≤ni+,i=1,2.則應(yīng)該將余額分給部門i=1，如果

|n1--q1|2+|n2+-q2|2>|n1+-q1|2+|n2--q2|2,

即

(b1)2+(b2-1)2>(b1-1)2+(b2)2,

這等價于

b1>b2.

注意到滿足Ax.7的指標(biāo)

Ai(b)=(bi-+bi+)/2=(qi-ni-+qi-ni+)/2=qi-ni--0.5=bi-0.5,

可知bi與Ai(b)在選擇優(yōu)先分配部門時等價，從而以bi為指標(biāo)的Hamilton法滿足Ax.7.

這就證明了滿足ESCA4的最優(yōu)分配方法應(yīng)該將剩余資源優(yōu)先分給指標(biāo)bi最大的部門即Hamilton法.所以獨占暫存性離散資源分配的最優(yōu)方法是Hamilton法.

7 共享暫存性離散資源的最優(yōu)分配方法

記ai=pi-ni-r,則ai=qir-ni-r=bir.將剩余資源優(yōu)先分給指標(biāo)ai最大的部門的分配方法稱為擬Hamilton法(Quasi-Hamiltonian Method).

定理4 共享暫存性離散資源分配的最優(yōu)方法為“擬Hamilton法”.

證明類似地，共享暫存性離散資源分配的最優(yōu)方法應(yīng)該滿足極大相容公理組ESCA3，即要求分配方法滿足{Ax.3,Ax.5,Ax.6,Ax.7}.

由文[1]表7.1可知，滿足Ax.3則對于數(shù)學(xué)模型(3)有X=P,k∈{1,2};滿足Ax.5,對于模型(3)有k=2;滿足Ax.6,對于模型(3)有X∈{N,P,S,T}；于是僅須考慮模型

(8)

不失一般性，假設(shè)最后一個資源余額的分配部門僅在{1,2}中選擇且ni-≤n≤ni+,i=1,2.則應(yīng)該將余額分給部門i=1，如果

|n1-r-p1|2+|n2+r-p2|2>|n1+r-p1|2+|n2-r-p2|2,

即

(a1)2+(r-a2)2>(r-a1)2+(a2)2,

這這等價于

b1>b2.

注意到滿足Ax.7的指標(biāo)

Ai(b)=(bi-+bi+)/2=(qi-ni-+qi-ni+)/2=qi-ni--0.5=bi-0.5,

可知bi與Ai(b)在選擇優(yōu)先分配部門時等價，從而以bi為指標(biāo)的Hamilton法滿足Ax.7.

a1>a2.

這就證明了滿足ESCA4的最優(yōu)分配方法應(yīng)該將剩余資源優(yōu)先分給指標(biāo)ai最大的部門即擬Hamilton法.所以獨占暫存性離散資源分配的最優(yōu)方法是擬Hamilton法.

8 結(jié)論

離散資源的公平分配問題，不同類型的資源各自存在最優(yōu)的分配方法，詳見表1.

表1 不同類型離散資源的最優(yōu)分配方法

特別應(yīng)該指出的是：在1913年之前，美國眾議院分給各州的席位問題屬于時變永久型離散資源的公平分配問題，應(yīng)該優(yōu)先滿足席位單調(diào)性Ax.2,其極大相容公理組為ESCA1,該組包括部門無偏性、席位單調(diào)性、統(tǒng)一普適性與指標(biāo)無偏性，對應(yīng)數(shù)學(xué)模型為

其最優(yōu)分配方法為Adam(s)法，即s的算術(shù)平均絕對偏差法，做法是在進(jìn)行預(yù)分配后，將剩余席位優(yōu)先分給預(yù)-后分配率算術(shù)平均Ai(s)=(si-+si+)/2與總分配率s的偏差s-Ai(s)最大的部門.且指標(biāo)s-Ai(s)最大等價于偏差Hi(r)-r最大，而通常使用的Q值方法相當(dāng)于指標(biāo)Gi(r)-r最大優(yōu)先法，其中H(r)與G(r)表示代表率r=s-1的調(diào)和平均與幾何平均.由于Huntington的Q值法不滿足公理Ax.6,所以相比之下,Adam(s)法優(yōu)于Huntington的Q值法.而在1913年之后，美國國會眾議院的席位就大致固定在435席，所以應(yīng)該采用Rdam(s)法。

哈密頓法不失為一種很好的離散資源分配法，不過應(yīng)該使用于暫存型離散資源的分配，特別是獨占暫存型離散資源的分配.如果用于席位分配，將不滿足席位單調(diào)性.

最后順便指出，所謂最優(yōu)分配方法，是指能滿足最多的相容公理的意義下的最好的分配方法.其他任何較優(yōu)的分配方法，無論是否采用顯式指標(biāo)還是數(shù)學(xué)模型，或者在本質(zhì)上至多與本文的最優(yōu)方法相同，或者只能在某一方面(如接近理想份額)超過它，但是必定在其他別的相容公理上有所缺陷.

參考文獻(xiàn)：

[1] 孫建新.席位分配公理的相容性與完備性[J].數(shù)學(xué)的實踐與認(rèn)識，2011，41(4):78-84.

[2] 姜啟源,謝金星，葉俊.數(shù)學(xué)模型[M].3版.北京：高等教育出版社，2003.

[3] 張建勛.席位分配問題的數(shù)學(xué)模型[J].數(shù)學(xué)的實踐與認(rèn)識，2002，32(4):541-548.