《数学建模》学习笔记01——席位分配问题

问题导入:

       三个系学生共200名(甲系100,乙系60,丙系40),代表 会议共20席,按比例分配,三个系分别为10,6,4席。现因学生转系,问:

(1)三系人数为103, 63, 34, 问20席如何分配?

(2)若增加为21席,又如何分配?

方法(一):比例+惯例

《数学建模》学习笔记01——席位分配问题

请问:上述方法对丙系公平吗?

方法(二):“公平” 分配方法

1.衡量公平分配的数量指标

《数学建模》学习笔记01——席位分配问题

(1)当 p1/n1= p2/n2 时,分配公平。

(2)当 p1/n1 >  p2/n2 时,对A不公平。

称“ p1/n1 -  p2/n2 ”为对A的绝对不公平度。

请问:对A的绝对不公平度可以作为本题衡量标准吗?请看例:

(1)p1=150, n1=10, p1/n1=15

         p 2 =100, n 2 =10, p 2 / n 2 =10             p1/n1– p2/n2=5  

(2)p1=1050, n1=10, p1/n1=105

         p 2 =1000, n 2 =10, p 2 / n 2 =100             p1/n1– p2/n2=5 虽然二者的绝对不公平度相同,但是情况(2)中对A的不公平程度已经大大降低!   方法(三):优化方法(二)——将绝对度量改为相对度量   若 p1/n1 >  p2/n2  时,定义:

《数学建模》学习笔记01——席位分配问题

为对A的相对不公平度,同理可以定义对B的相对不公平度rB(n1,n2)。利用这种分配方式时候应当使得rA,rB尽可能小。优点是是将一次性的席位分配转化为了动态席位分配。

求解当席位增加一个的时候假设以下情况考虑(初始值:p1/n1 >  p2/n2 ):

1.当:p1 / (n1 + 1) > p2 / n2 时,席位应当给A;

2.当:p1 / (n1 + 1) < p2 / n2 时,应当计算rB(n1 +1, n2);

3.当:p1 /n1 >p2 / (n2 + 1) 时,应当计算rA(n1, n2 +1)。

而p1 /n1 < p2 / (n2 + 1) 时一定不会出现!

若rB(n1 +1, n2)< rA(n1, n2 +1),则席位分给A,反之席位分给B。当席位分配给A时,由rA,rB的定义可得:

《数学建模》学习笔记01——席位分配问题

根据上式定义

 

《数学建模》学习笔记01——席位分配问题

由此可得席位应分配给Q值大的一方。同样可以推广至m方分配席位,席位分配给Q值最大的一方。该方法成为“Q值法”。


三个系用“Q值法”重新分配21个席位:

1.按人数比例的整数部分将19席分配完毕:

甲系:p1=103, n1=10

乙系:p2= 63, n2= 6

丙系: p 3 = 34, n 3 = 3   2.用“Q值法”分配第20、第21席位:   (1)分配20席位:   Q1=103*103/10*11=96.4   Q2=63*63/6*7=94.5   Q3=34*34/3*4=96.3   Q1最大,第20席位分给甲系 (2)分配21席位   Q1=103*103/11*12=80.4   Q2、Q3同上保持不变   Q3最大,第21席位分给丙系。   3.结果分析: 席位分配的理想化准则:   已知: m 方人数分别为 p 1 , p 2 ,… , p m , 记总人数为 P = p 1 + p 2 +…+ p m , 待分配的总席位为 N。  

设:理想情况下m方分配的席位分别为n1,n2,… , nm(自然应有n1+n2+…+nm=N)

ni 应是 N和 p1, … , pm 的函数,即ni = ni (N, p1, … , pm )

记qi=Npi /P, i=1,2, … , m, 若qi均为整数,显然应 ni =qi。当qi =Npi /P不全为整数时,ni 应满足的准则:

(1)《数学建模》学习笔记01——席位分配问题

(2)

《数学建模》学习笔记01——席位分配问题

记:《数学建模》学习笔记01——席位分配问题

即当总席位增加时, n i 不应减少   所以:   “ 比例加惯例”方法满足 ( 1 ),但不满足(  2 );   Q 值方法满足(  2 ), 但不满足(  1 )。
上一篇:贪心算法的常见问题Ⅰ(详解!)


下一篇:包装类()