第二周数模选修课作业
1. 问题的提出
学校共1000名学生，235人住在A楼，333人住在B楼，432人住在c楼。学生要组织一个10人委员会，试用最大剩余方法和Q值方法分配各楼的委员数，并比较结果。
2. 最大剩余法
符号说明
\(N\): 委员会人数
\(p_{i}\)： i楼拥有的人数
\(r_{i}\)： i楼占的人口比例
\(d_{i}\)： i楼理想占有的席位数
\(n_{i}\)： i楼占有的席位数
模型的建立
我们可以知道在理想情况下，每个楼层占有的席位数为：
\[d_{i}=N\times r_{i}\]其中，\(r_{i}\)的计算方法为：
\[r_{i}=\frac{p_{i}}{\sum_{i=A,B,C}p_{i}}\qquad\]
最终表达式如下:
\[d_{i}=\frac{N\times p_{i}}{\sum_{i=A,B,C}p_{i}}\qquad\]
模型的求解
我们将题目中的5个数据带入模型，可得到如下结果：
| 楼号(\(i\)) | 学生人数(\(p_{i}\)) | 比例(\(r_{i}\)) | 理想席位数(\(d_{i}\)) | 最终结果(\(n_{i}\)) |
|---|---|---|---|---|
| A | 235 | 0.235 | 2.35 | 3 |
| B | 333 | 0.333 | 3.33 | 3 |
| C | 432 | 0.432 | 4.32 | 4 |
可知由最大剩余法分配的结果为A楼3位委员，B楼3位委员，C楼4位委员。
3. Q值法
符号说明
\(n_{i}\): i方已经占有的席位
\(p_{i}\)： i楼拥有的人数
\(R_{i}\)：i方的不公平度
模型的建立
我们不妨从三方中取出两方来分析这个问题：
不公平度指标
设两方的人数分别为\(p_{1}\)，\(p_{2}\)，占有委员数分别为\(n_{1}\)，\(n_{2}\)，则比值\(\frac {q_{1}}{n_{1}}, \frac {q_{2}}{n_{2}}\)为两方每个委员所代表的人数。显然只有两个比值相等的时候分配才是完全公平的，但是因为人数和席位都是整数，所以通常不相等。
因此我们用相对标准来定义：
\[R_{A}(n_{1},n_{2})=\frac {p_{1}/n_{1}-p_{2}/n_{2}}{p_{2}/n_{2}}\]
为对A的相对不公平度。
对B的相对不公平度同理：
\[R_{B}(n_{1},n_{2})=\frac {p_{2}/n_{2}-p_{1}/n_{1}}{p_{1}/n_{1}}\]
则我们制定席位分配的原则是使它们尽可能小。
Q值
假设A，B，C方已分别占有委员数\(n_{1}\)，\(n_{2}\)，利用相对不公平度\(R_{A}\)，\(R_{B}\)，\(R_{C}\)讨论每当委员增加一人时，应该分配给哪一方。
可知可能出现下面三种情况：
- \(\frac {p_{1}}{n_{1}+1}>\frac {p_{2}}{n_{2}}\)，说明即使A增加1人仍然对A不公平，应该分配给A。
-
\(\frac {p_{1}}{n_{1}+1}<\frac {p_{2}}{n_{2}}\)，说明A增加1人将对B不公平，计算出B的不公平度为：
\[R_{B}(n_{1}+1,n_{2})=\frac {p_{2}(n_{1}+1)}{p_{1}n_{2}}-1\] -
\(\frac {p_{1}}{n_{1}}>\frac {p_{2}}{n_{2}+1}\)， 说明B增加1人将对A不公平，计算出A的相对不公平度为：
\[R_{A}(n_{1},n_{2}+1)=\frac {p_{1}(n_{2}+1)}{p_{2}n_{1}}-1\]
在使相对不公平度尽量小的分配原则下，如果
\[R_{B}(n_{1}+1,n_{2}) < R_{A}(n_{1},n_{2}+1)\]
则增加的1人应分配给A，反之分配给B。上式等价为：
\[\frac {P_{2}^{2}}{n_{2}(n_{2}+1)} < \frac {P_{1}^{2}}{n_{1}(n_{1}+1)}\]
于是我们得到结论：当上式成立时应分配给A，否则分配给B。
这种方法可以推广到有\(m\)方分配人数的情况。计算
\[Q_{i}=\frac {p_{i}^{2}}{n_{i}(n_{i}+1)}, i=1,2,…,m\]
增加的一个名额应该分配给Q值最大的一方。模型的求解
我们可以将A，B，C三楼最初的委员数都设为0，利用上述的Q值法每次增加1人，得到最终的人数。
我们借助Python编程来解决这个问题：
#先将各项的值初始化
n_A=n_B=n_C=1
p_A=235
p_B=333
p_C=432
while (n_A+n_B+n_C)<10:
Q_A=float(p_A**2)/float(n_A*(n_A+1))
Q_B=float(p_B**2)/float(n_B*(n_B+1))
Q_C=float(p_C**2)/float(n_C*(n_C+1))
if Q_A>=Q_B and Q_A>=Q_C:
n_A+=1
elif Q_B>=Q_A and Q_B>=Q_C:
n_B+=1
else:
n_C+=1
print "A楼有%d位委员，B楼有%d位委员，C楼有%d位委员"%(n_A,n_B,n_C)最后得到结果：A楼有2位委员，B楼有3位委员，C楼有5位委员
17.3.12凌晨1点更新：
将文中python程序部分进行修改，提高代码的可重用性，如下：
n_all=int(raw_input('请输入需要分配的阵营数：'))
n_sum=int(raw_input('请输入需要分配的席位数：'))
p=[]#每个阵营的人数数组
n=[]#每个阵营席位数
Q=[0 for x in range(n_all)]#每个阵营当前的Q值
for i in range(n_all):
p.append(input("请输入第%d个阵营的总人数："%(i+1)))
for i in range(n_all):#给每个阵营初始分配1个席位，防止Q值无法计算
n.append(1)
while sum(n)<n_sum:#当席位没有分配完时继续循环
for i in range(n_all):#计算每个阵营当前的Q值
Q[i]=float(p[i]**2)/float(n[i]*(n[i]+1))
for i in range(n_all):#将Q值最大的阵营的席位加1
if Q[i]==max(Q):
n[i]+=1
for i in range(n_all):
print "第%d个阵营分配%d个席位"%(i+1,n[i])