席位分配问题
一、问题背景
席位分配是日常生活中经常遇到的问题,对于企业、公司、学校、政府等部门都能解决实际的问题。席位可是是代表大会、股东会议、公司企业员工大会等的具体座位。 二、问题提出
学校共1000名学生,235人住在A宿舍,333人住在B宿舍,432人住在C宿舍.学生们要组织一个10人的委员会,试用下列
分配各宿舍的委员数:
(1). 按比例分配取整数的名额后,剩下的名额按惯例分给小数部分较大者; (2). 用?2.1中的Q值方法分配,要求编一个通用程序解决此类分配问题; (3).d’Hondt方法:将A、B、C各宿舍的人数用正整数n=1,2,3,……相除,其商数如下表:
1 2 3 4 5
A 235 117.5 78.3 58.75 …
B 333 166.5 111 83.25 …
C 432 216 144 108 86.4
将所得商数从大到小取前10个(10为席位数),在数字下标以横线,表中A、B、C行有横线的数分别为2,3,5,这就是3个宿舍分配的席位.请解释此方法的原理,并编程求解。 (4)如果委员会从10个人增至15人,用以上3种方法再分配名额,将3种方法两次分配的结果列表比较.
三、模型的建立与求解
(1)通常分配结果的公布与否以每个代表席位所代表的人数相等或相近来衡量,目前沿用的惯例分配方法为按比例分配方法,即: 席位分配数总人数比例总席位数=,
按比例分配取整数的名额后,剩下的名额按惯例分给小数部分较大者,所以分配情况如表一所示。
表一
宿舍 学生人数 学生人数比例 按比例分配的席位 按惯例分配的席位
A 235 0.235 2.35 3
B 333 0.333 3.33 3
C 432 0.432 4.32 4
总和 1000 10 10 学生们要组织的10人的委员会,分配各宿舍的委员数分别为:A宿舍3人,B宿舍3人,C宿舍4人。
ipn(2)Q值法:有m方分配席位的情况,设第方人数为,已占有个席位,im,1,2,,.ii
2pi当总席位增加1席时,计算 应将这一席分给值最大的一方,Q,1,2,,Qim,,i(1)nn,ii
这种席位分配方法称为值法。 Q
(3)、原理是先按各宿舍人数的大小排列依次分一个,再根据席位数的多少,从各宿舍人数
用正整数n=1,2,3,……相除得到的数的大小排列中,依次分配,不断循环直到席位分配完
成。相当于不考虑各宿舍人数占总人数的比例,把席位比较均匀的分配到个宿舍,但这样的
话就不可能解决公平问题。
(4)、把相应的N=10改成N=15,带入程序,可得按惯例分配A、B、C的席位分别为3、
5、6;按d’honht方法三个宿舍分得的细微分别为:3、5、7;按Q值法分配方法三个宿舍
分得的席位为:4、5、6。两种席位数分配
如下表:
分配方法 按惯例分配 d’honht法 Q值法 席位数
N=10 3, 3, 4 2, 3, 5 2, 3 , 5 N=15 4, 5, 6 3, 5, 7 4, 5, 6
三种分配方法程序代码:
clear all
clc
disp('席位分配:')
P=1000;
p=[235 333 432];
N=10;
[x,y]=size(p);
zu=x*y;
disp('惯例分配方法:')
for i = 1:zu
n(i) =p(i)*N/P;
end
n;
m=n-fix(n);
for i=1:zu
if n(i)==max(m)+fix(n(i))
n(i)=fix(n(i))+1;
else
n(i)=fix(n(i));
end
end
n
disp('d’honht方法:')
pp=[];
for i=1:N
pi=p/i;
pp=[pp; pi]; end
pp;
m=zeros(1,zu);
for i=1:N
[x,y]=find(pp==max(pp(:)));
pp(x,y)=0;
m(y)=m(y)+1; end
pp;
m
disp('Q值法分配方法:')
q=ones(1,zu);
Q=[];
p;
for i=1:zu
Q(i)=p(i)*p(i)/(q(i)*(q(i)+1));
end
Q;
xiwei(p,q,Q,N,zu) 其中xiwei(p,q,Q,N,zu)的定义如下: function xiwei(p,q,Q,N,zu)
if sum(q)==N
disp('Q值法分配人数:')
q
return;
else
for i=1:zu
if Q(i)==max(Q)
q(i)=q(i)+1;
Q(i)=p(i)*p(i)/(q(i)*(q(i)+1));
break;
end
end
end
xiwei(p,q,Q,N,zu) 程序运行结果:
席位分配:
惯例分配方法:
n =
3 3 4 d’honht方法:
m =
2 3 5 Q值法分配方法:
q =
2 3 5