公平的席位分配等四个数学模型例子

补例1赛程安排问题方案1：设有n人报名参赛，下面对n为不同的值进行讨论。（2）若，则存在一个正整数k，使得（1）若，第一轮比赛有场，…1/4决赛有场，半决赛有2场，冠亚军比赛1场，合计（场）：场数为第一轮的比赛次数是，人轮空，剩下的人数为，这样之后的k－1轮比赛中的第一页第二页，共43页。补例1赛程安排问题所以一共要比赛：若本轮比赛的人数为偶数，则没有轮空；若人数为奇数，则有1人轮空。从而比赛轮空的人数不大于k－1人方案2：设有n人报名参赛，每一轮允许有轮空现象。例1：某校有11位同学参加围棋单淘汰赛，应该进行几场比赛？则存在一个正整数k，使得第二页第三页，共43页。补例1赛程安排问题二、单循环赛：设有n队参加比赛，则每队都要与其余的n－1支队分别比赛一场。当n为偶数时，则要举行n－1轮比赛；当n为奇数时，则要举行n轮比赛，且每轮有1队轮空单循环赛就是参加比赛的每一个人都要和其他人比赛一次，然后根据总体成绩排定名次。如果和其他人比赛两次，则称为双循环赛。定理：设有n队参加比赛，则比赛的总场数是场。例2：某校共有26个班，举行排球比赛，在不同的赛制下各要比多少场？第三页第四页，共43页。补例1赛程安排问题优缺点分析：（略）例3：参加排球比赛的26个班级，先分成3个小组，其中两个组为9队，另一个组为8队，在小组中，先用单循环赛产生每个小组的前两名，接下来，每小组的前两名共6个队再进行单循环赛。以8支队的小组为例，对赛程进行合理安排。解：在第一阶段：场在第二阶段：场一共比赛的场数为100+15＝115场。第四页第五页，共43页。补例1赛程安排问题用表示八支代表对，则A1——A2A3——A4A5——A6A7——A8A1——A3A5——A2A7——A4A8——A6A1——A5A7——A3A8——A2A6——A4A1——A7A8——A5A6——A3A4——A2A1——A8A6——A7A4——A5A2——A3A1——A6A4——A8A2——A7A3——A5A1——A4A2——A6A3——A8A5——A7第五页第六页，共43页。补例1赛程安排问题A1A2A3A4A5A6A7A8A115259211317A2120166262311A3520224151027A4251621912722A596241932814A6212615123188A7132310728184A81711272214844+4+4+3+2+2＝192+4+4+4+3+2＝194+4+3+2+2+2＝172+2+4+4+4+3＝194+3+2+2+2+4＝172+2+2+4+4+4＝183+2+2+2+4+4＝17由以上表格可知该安排是合理的3+3+3+3+3+3＝18每两场间隔场次第六页第七页，共43页。

作业：当7支队参加单循环赛的排球比赛时，试合理的安排其赛程。第七页第八页，共43页。补例2洗衣节水问题我国淡水资源有限，节约用水势在必行。那么如何在洗衣服中合理地用水，使得既能把衣服洗干净，又能节约用水的问题就摆在我们的面前。一般洗衣服的过程是先将衣服用洗涤剂浸泡，然后一次次地用水漂洗。洗衣机的运行过程分别为加水—>漂洗—>脱水—>加水—>漂洗—>脱水……这么一个循环过程。我们的问题是在保证一定洗涤效果下，洗衣服分成多少次（或在洗衣机中应循环几次），每一次的用水量是否一致，使得总的用水量最为节省？问题提出：第八页第九页，共43页。

衣服洁净的问题实际上是比较复杂的，它不仅有物理原理，还有化学原理（如果是洗衣机，则与机械原理有关）。补例2洗衣节水问题问题分析：其基本原理就是将吸附在衣物上的污物溶于水中，通过脱水而荡涤污物。节水目标为在一定量的用水条件下，在洗衣过程中如何合理地分配这些水，使得能达到把衣服洗净的目的。第九页第十页，共43页。我们在问题的分析中已经知道了洗衣的原理是将吸附在衣物上的污物溶于水中，通过拧干（脱水）而荡涤污物。因此我们有以下的两个假设：

补例12洗衣节水问题1）在漂洗时间足够的前提下，衣服上的污物能被洗涤剂完全溶解在水中。2）每次拧干后衣服中残留的水量是一致的。模型假设：第十页第十一页，共43页。补例2洗衣节水问题问题归结为：在水的总量为的条件下，将水分成次洗涤，每次用量分别为。问经过这次洗涤，衣服上还剩下多少污物？

模型建立与求解：设洗衣服一开始浸泡时的用水量为，按照问题的分析，可看成是一个常量。经拧干后残留污物的质量为，记第次拧干后残留于衣服中的污物（还包含了洗涤剂的质量）为，同时记衣服中残留的水量为，再设洗衣服的总水量为，第十一页第十二页，共43页。补例2洗衣节水问题我们引入洗涤剂的浓度概念（单位质量水中所含的污物质量）（表示第次漂洗污物的浓度），第一次漂洗时的浓度为我们引入洗涤剂的浓度概念（单位质量水中所含的污物质量）（表示第次漂洗污物的浓度），第一次漂洗时的浓度为第十二页第十三页，共43页。补例2洗衣节水问题仿此，可得第二次漂洗时的浓度此时拧干残留的污物为依此类推，可得第此漂洗之后，衣服上的残留污物量为第十三页第十四页，共43页。补例2洗衣节水问题（2）式可化为（3）式为一递推关系式，以下导出关于初始值的表达式。

因此由数学归纳法证得第十四页第十五页，共43页。补例2洗衣节水问题洗衣服的目的是要使污物越来越少，即在漂洗过程中洗涤剂浓度越来越少，转化为数学语言就是在一定条件下，如何选取方能使达到最小。（5）式还可以改写为我们将它总结为以下定理：定理：在总用水量一定的条件下，平均分配每次加水量，实现的洗涤效果最好。第十五页第十六页，共43页。

证：补例2洗衣节水问题第十六页第十七页，共43页。补例2洗衣节水问题第十七页第十八页，共43页。补例2洗衣节水问题模型分析：从残留在衣服中污物量的浓度变化可知，即每多洗涤一次，污物就少一些。实际上在每次洗涤加水量相同的条件下，由(5)式得关于是单调递减的函数。即漂洗衣服最好少量多次。下一个问题：是否在用水量一定的条件下，洗涤的次数足够多，便可以使趋向于零，即衣服的污物被完全清除呢？即当趋向于无穷大时，是否趋向于无穷小？第十八页第十九页，共43页。

(8)式说明了当水的总量一定的时候，无论你怎样洗涤，不管次数多少，最后的结果是不可能一点污物都不残留的。补例2洗衣节水问题第十九页第二十页，共43页。补例2洗衣节水问题先引入一个清洁度的定义。设是洗净衣服上的污物量与第一次浸泡后残留在衣服上的污物量之比，即进一步讨论:如何确定洗涤的次数。我们用来反映衣物洗净的清洁程度。第二十页第二十一页，共43页。洗涤的次数大约为3，即洗涤3次可使衣服洁净到一定程度，这一结果与我们生活实际情况也是相符的。补例2洗衣节水问题第二十一页第二十二页，共43页。一.比例代表制例：有A、B、C、D四个政党，代表50万选民，各政党的选民数为：A党：199,000B党：127,500C党：124,000D党：49,500要选出5名代表：A党：2席B党：1席C党：1席D党：0席缺少1席，如何分配这最后一席呢？补例3公平的席位分配第二十二页第二十三页，共43页。最大余数法按每10万选民1席分配后，按余数大小排序，多余的席位分给余数较大的各党。党名代表选民数整数席余数余额席总席数A199,000199,00012B127,500127,50001C124,000124,00001D49,500049,50011补例3公平的席位分配第二十三页第二十四页，共43页。洪德(d

Hondt)规则分配办法是：把各党代表的选民数分别被1、2、3、…除，按所有商数的大小排序，席位按此次序分配。即若A党的人数比D党的人数还多，那么给A党3席、给D党0席也是合理的。除数A党B党C党D党1199,000(1)127,500(2)124,000(3)49,500299,500(4)63,75062,00024,750366,333(5)42,50041,33316,500449,75031,875－－总席位3110补例3公平的席位分配第二十四页第二十五页，共43页。北欧折衷方案作法与洪德规则类似，所采用的除数依次为1.4、3、5、7、…A党B党C党D党2210三种分配方案，得到了完全不同的结果，最大余数法显然对小党比较有利，洪德规则则偏向最大的党，北欧折衷方案对最大和最小党都不利补例3公平的席位分配第二十五页第二十六页，共43页。二．份额分配法(QuotaMethod)一种以“相对公平”为标准的席位分配方法，来源于著名的“阿拉巴玛悖论”(AlabamaParadox)。美国宪法第1条第2款对议会席位分配作了明确规定，议员数按各州相应的人数进行分配。最初议员数只有65席，因为议会有权改变它的席位数，到1910年，议会增加到435席。宪法并没有规定席位的具体分配办法，因此在1881年，当考虑重新分配席位时，发现用当时的最大余数分配方法，阿拉巴玛州在299个席位中获得8个议席，而当总席位增加为300席时，它却只能分得7个议席。这一怪事被称为有名的“阿拉巴玛悖论”。补例3公平的席位分配第二十六页第二十七页，共43页。系别学生比例20席的分配人数（%）比例结果甲10351.5乙6331.5丙3417.0总和200100.020.02021席的分配比例结果10.8156.6153.57021.00021问题三个系学生共200名（甲系100，乙系60，丙系40），代表会议共20席，按比例分配，三个系分别为10，6，4席。现因学生转系，三系人数为103,63,34,问20席如何分配。若增加为21席，又如何分配。比例加惯例对丙系公平吗系别学生比例20席的分配人数（%）比例结果甲10351.510.3乙6331.56.3丙3417.03.4总和200100.020.020系别学生比例20席的分配人数（%）比例结果甲10351.510.310乙6331.56.36丙3417.03.44总和200100.020.02021席的分配比例结果10.815116.61573.570321.00021补例3公平的席位分配第二十七页第二十八页，共43页。“公平”分配方法衡量公平分配的数量指标人数席位A方p1

n1B方p2n2当p1/n1=p2/n2时，分配公平

p1/n1–p2/n2~对A的绝对不公平度p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100p1/n1–p2/n2=5但后者对A的不公平程度已大大降低!虽二者的绝对不公平度相同若p1/n1>p2/n2，对不公平A

p1/n1–p2/n2=5第二十八页第二十九页，共43页。公平分配方案应使rA

,rB

尽量小不妨设分配开始时p1/n1>p2/n2，即对A不公平~对A的相对不公平度将绝对度量改为相对度量类似地定义rB(n1,n2)将一次性的席位分配转化为动态的席位分配,即“公平”分配方法若p1/n1>p2/n2，定义设A,B已分别有n1,n2席，若增加1席，问应分给A,还是B第二十九页第三十页，共43页。1）若p1/(n1+1)>p2/n2，则这席应给A2）若p1/(n1+1)<p2/n2，3）若p1/n1>p2/(n2+1)，应计算rB(n1+1,n2)应计算rA(n1,n2+1)若rB(n1+1,n2)<rA(n1,n2+1),则这席应给应讨论以下几种情况初始p1/n1>p2/n2

问：p1/n1<p2/(n2+1)

是否会出现？A否!若rB(n1+1,n2)>rA(n1,n2+1),则这席应给B第三十页第三十一页，共43页。当rB(n1+1,n2)<rA(n1,n2+1),该席给ArA,rB的定义该席给A否则,该席给B定义该席给Q值较大的一方推广到m方分配席位该席给Q值最大的一方Q值方法计算，第三十一页第三十二页，共43页。三系用Q值方法重新分配21个席位按人数比例的整数部分已将19席分配完毕甲系：p1=103,n1=10乙系：p2=63,n2=6丙系：p3=34,n3=3用Q值方法分配第20席和第21席第20席第21席同上Q3最大，第21席给丙系甲系11席，乙系6席，丙系4席Q值方法分配结果公平吗？Q1最大，第20席给甲系第三十二页第三十三页，共43页。进一步的讨论Q值方法比“比例加惯例”方法更公平吗？席位分配的理想化准则已知:m方人数分别为p1,p2,…,pm,记总人数为P=p1+p2+…+pm,待分配的总席位为N。设理想情况下m方分配的席位分别为n1,n2,…,nm(自然应有n1+n2+…+nm=N)，记qi=Npi/P,i=1,2,…,m,ni应是N和p1,…,pm

的函数，即ni

=ni(N,p1,…,pm)若qi

均为整数，显然应ni=qi第三十三页第三十四页，共43页。

qi=Npi/P不全为整数时，ni

应满足的准则：记[qi]–=floor(qi)~向

qi方向取整；[qi]+=ceil(qi)~向

qi方向取整.1)[qi]–

ni

[qi]+(i=1,…,m),2)ni

(N,p1,…,pm)

ni

(N+1,p1,…,pm)(i=1,…,m)

即ni必取[qi]–,[qi]+之一即当总席位增加时，ni不应减少“比例加惯例”方法满足1），但不满足2）Q值方法满足2）,但不满足1）。令人遗憾！第三十四页第三十五页，共43页。

作业：

学校共1000名学生，235人住在A宿舍,333人住在B宿舍,432人住在C宿舍.学生要组织一个10人的委员会,使用下列办法分配各宿舍的委员数:

1)按比例分配取整数的名额后,剩下的名额按惯例分给小数部分较大者.

2)用Q值法进行分配.

若委员会人数从10增至15人,又如何分配呢?请分别用上述两种方法给出过程及结果.第三十五页第三十六页，共43页。

补例4铺地砖问题地面被划分为6×7的方格，方形地砖大小等同于方格的大小。问题提出：某人买了20块长方形砖，其一块大小等于方形地砖的两块。请问：1.能否完整地铺设如图1所示的地面？2.若在图1所示的地面中，有一格不用铺设，问长方形地砖能否完整地铺设地面？3.若在图1所示的地面中，左上角和右上角的格不用铺设，问长方形地砖能否完整地铺设地面？（图1）1234567123456第三十六页第三十七页，共43页。

补例4铺地砖问题问题分析：1块长方形地砖等于2块方形地砖，即（图1）1234567123456长方形地砖恰好能覆盖两个相邻的格子。问题转化为：在给定的图形中，满足条件的覆盖是否存在。模型建立与求解：设有m×n的格子盘（m，n都是正整数），首先给出格子盘被完全覆盖的充要条件。定理1：

m×n的格子盘被完全覆盖的充要条件是：m、n中至少有一个为偶数第三十七页第三十八页，共43页。