席位公平分配的最小极差法

摘要：提出了席位公平分配的最小极差法及其数学规划模型 ，比较分析了多种不同席位分配方法 ，并提出了非完全分配的概念及其数学模型。从而得到一套更完善的席位公平分配方法。

关键词：席位公平分配 最小极差 非完全分配

前言

早在1982年，Burghes D.N.等人在《A Course in Mathematical Modeling》书中选录了席位公平分配问题及其Q值法，而在国内较有影响的数学建模教材也介绍了这一问题与解法，对这个问题，后来有相继出现了几种不同的解法：新Q值法、判别数法与0-1规划法。在这些解法中，由于衡量“公平度”的标准不同，故其解也往往不一致。本文提出更公平合理的衡量“公平度”的新标准，即“最小极差”以及相应的数学规划模型，并且对各种标准作出对比分析。同时再提出一个“非完全分配”的新概念及其数学模型。

以某校学生会的席位分配为例而贯穿始终，我们要解决的是这样的一个问题：某校共有m个系，第i系学生数为ni([i]=1,2,L,m)，校学生会共设N个席位，怎样才能公平地把这些席位分配给各系？

显然，m，ni([i]=1,2,L,m)应为正整数，全校学生数记为n=[i=1mni]。假设每个系至少应分得一个席位（否则把其剔除），至多分得ni([i]=1,2,L,m)个席位，n[>N≥m]。全校而言，每个席位代表的学生数记为[α=n/N]。第i系按学生数比例应分得的席位为bi=niN/n=ni/[α]，且记pi=bi，最后实际分得的席位数为xi(1[≤xi≤]ni，整数）每个席位代表的学生数为ai=/nixi(i=1,2,L,m)。另记y=[miniαi,z=maxiαi,r=N-i=1mpi=i=1m]，其中[]表示[bi]的小数部分。

1.数学模型的建立

根据以上标准，使用上述符号，即可建立数学规划模型(1)[minf=z-y]

s.t.[z≥ni/xi≥y,(i=1,2,L,m)i=1mxi=N1≤xi≤ni,整数（i=1,2,L,m)](1)

模型(1)中，m，N，[ni]为已知常数，[xi]，y,z为变量，[xi]([i]=1,2,L,m)为正整数，就是各系最后得到的席位数。必要时，也可通过变量替换：[u=1/y,v=1/z]把模型(2)。

min[f=1/v-1/u]

s.t.[v≤xi/ni≤u,(i=1,2,L,m)i=1mxi=N1≤xi≤ni,整数（i=1,2,L,m)] (2)

1.1 模型(1)的性质

性质1：[z≥α≥y)] ，说明[αi]的两极总在a的两旁。

性质2 ：若z[>y,则z>α>y]，说明当[αi]的两极不相等时，任一极都不等于[α]。

性质3 ：模型(1)必有最优解

性质4： 模型(1)的最优解为零的充要条件是b[i]([i]=1,2,L,m)都是正整数

1.2 几种方法的对比分析

“Q值法”、“新Q值法”与“0-1规划法”都有一个共同点，即先给各系按人数比例取整分配，然后再将剩余席位逐一增加给较吃亏的系。这样，相当于对各[xi]([i]=1,2,L,m)附加了约束条件：p[i≤xi≤pi+1(i=1,2,L,m])，在这约束条件下求得的解未必是最佳的（指[αt]的极差最小）。除最小极差法外，其他3种方法的解的极差都较大，即“公平度”较差。

另外，我们还发现，“新Q值法”并不见得总比“Q值法”好，有时甚至还差得多，而“判别数法”虽然没有对各[xi]([i]=1,2,L,m)附加约束条件：p[i≤xi≤pi+1(i=1,2,L,m])，但有时也不如“最小极差法”。

顺便指出衡量“公平度”的另外两个标准：(A)[i=1mα-αi]最小；(B)[miniαi]最大。但其解相应的[αi]极差也往往较大。

还有这样一个模型：

[minf=i=1m(a-ni/xi)2]

s.t.[i=1mxi=N1≤xi≤ni,整数（i=1,2,L,m)](3)

模型(3)的解也不能保证[αi]的极差最小。

综上所述，[α-αi]最小或[(α-αi)2]最小都不能保证[αi]的极差最小，即不能让[αi]最集中。

“0-1规划法”是对模型(3)作变量替换[xi=pi+yi(i=1,2,L,m)]，其中[yi]为0-1变量而得的。顺便指出，模型(3)与“0-1规划法”并不等价。两模型的解不同。模型(3)的解比“0-1规划法”的好。

通过以上各个不同标准，不同方法的对比分析，可见较公平合理还是模型(1)的解，即“最小极差法”的解。它能使各[αi]最高度地集中在[α]的附近。

2.席位的“非完全分配法”

前面讨论的都是“要把N各席位全部分配出去，如何分配更公平”这样的问题。我们不妨把这种废排放称为“完全分配法”。但有些情况，若采用“完全分配法”，则无论怎样分，都总显得不公平。例如，要把5个席位全部分给甲乙两个学生人数相同的系，怎样分？显然最公平的分配方法应是舍弃1席后，各分2席。我们把这种为了追求“最公平”而舍弃一些席位的分配方法称为“非完全分配法”。

“非完全分配法”的数学模型可由模型(1)稍加改动即可，即模型(4)。

[minf=z-y]

s.t.[z≥ni/xi≥y,(i=1,2,L,m)i=1mxi≤N1≤xi≤ni,整数（i=1,2,L,m)] (4)

模型(4)必有最优解，因为[xi=1(i=1,2,L,m)]就是一个可行解，且[xi]的取值只有有限个。采用“非完全分配法”，“公平度”往往会有很大的改善。

3.结束语

综上所述，最小极差法能较完善地解决席位公平分配问题。当愿意舍弃一些席位而追求“最公平”时，可使用模型(4)，当不愿意浪费席位时，可使用模型(1)。当然，后者的“公平度”就可能要差一些了。由于现在计算机软件的先进技术，模型的求解并非难事。

参考文献

[1] 姜启源.数学模型(第二版)M.北京：高等教育出版社，1993.

[2] 洪毅，贺德化，昌志华.经济数学模型M.广州：华南理工大学出版社，1998.

[3] 刘来福，曾文艺.数学模型与数学建模M.北京：北京师范大学出版社，1997.

[4] 岳林.关于Q值法的一种新定义J.系统工程，1995(4):70-72.