《公平的席位分配等四个数学模型例子》由会员分享，可在线阅读，更多相关《公平的席位分配等四个数学模型例子（43页珍藏版）》请在金锄头文库上搜索。
1、补例1 赛程安排问题,问题提出：1. 某校组织乒乓球比赛，因报名人数较多，决 定采用单淘汰进行比赛。请问如何合理地安排赛程？ 2. 某校举办排球比赛，比赛形式为单循环赛。请问应如何 安排比赛？,问题分析：1. 选择赛制（不同的赛制决定赛程安排的差异） 2. 比赛的总场次、比赛的轮数及轮空人数等问题,模型建立与求解：,一、单淘汰赛：,方案1. 允许在第一轮中有轮空现象,方案2. 在每一轮都要保证尽可能多的 运动员参赛,补例1 赛程安排问题,方案1：设有n人报名参赛，下面对n为不同的值进行讨论。,（2）若 ，则存在一个正整数 k，使得,（1）若 ，第一轮比赛有 场，1/4决赛有 场，半决赛有2场，
2、冠亚军比赛1场，合计（场）：,补例1 赛程安排问题,所以一共要比赛：,若本轮比赛的人数为偶数，则没有轮空 ； 若人数为奇数，则有1人轮空。 从而比赛轮空的人数不大于k1人,方案2：设有n人报名参赛，每一轮允许有轮空现象。,例1：某校有11位同学参加围棋单淘汰赛，应该进行几场比赛？,则存在一个正整数 k，使得,补例1 赛程安排问题,二、单循环赛：,设有n队参加比赛，则每队都要与其余的n1支队分别比赛一场。当n为偶数时，则要举行n1轮比赛；当n为奇数时，则要举行n轮比赛，且每轮有1队轮空,单循环赛就是参加比赛的每一个人都要和其他人比赛一次， 然后根据总体成绩排定名次。如果和其他人比赛两次，则 称为
3、双循环赛。,定理：设有n队参加比赛，则比赛的总场数是 场。,例2：某校共有26个班，举行排球比赛，在不同的赛制下各要比多少场？,补例1 赛程安排问题,优缺点分析：（略）,例3：参加排球比赛的26个班级，先分成3个小组，其中两个 组为9队，另一个组为8队，在小组中，先用单循环赛产生每 个小组的前两名，接下来，每小组的前两名共6个队再进行单 循环赛。以8支队的小组为例，对赛程进行合理安排。,解： 在第一阶段： 场,在第二阶段： 场,一共比赛的场数为100+15115场。,补例1 赛程安排问题,用 表示八支代表对，则,A1A2 A3A4 A5A6 A7A8,A1A3 A5A2 A7A4 A8A6,A
4、1A5 A7A3 A8A2 A6A4,A1A7 A8A5 A6A3 A4A2,A1A8 A6A7 A4A5 A2A3,A1A6 A4A8 A2A7 A3A5,A1A4 A2A6 A3A8 A5A7,补例1 赛程安排问题,由以上表格可知该安排是合理的,作业：当7支队参加单循环赛的排球比赛时，试合理的安排其赛程。,补例2 洗衣节水问题,我国淡水资源有限，节约用水势在必行。那么如何在洗衣服中合理地用水，使得既能把衣服洗干净，又能节约用水的问题就摆在我们的面前。一般洗衣服的过程是先将衣服用洗涤剂浸泡，然后一次次地用水漂洗。洗衣机的运行过程分别为加水漂洗脱水加水漂洗脱水这么一个循环过程。我们的问题是在保
5、证一定洗涤效果下，洗衣服分成多少次（或在洗衣机中应循环几次），每一次的用水量是否一致，使得总的用水量最为节省？,问题提出：,衣服洁净的问题实际上是比较复杂的，它不仅有物理原理，还有化学原理（如果是洗衣机，则与机械原理有关）。,补例2 洗衣节水问题,问题分析：,其基本原理就是将吸附在衣物上的污物溶于水中，通过脱水而荡涤污物。,节水目标为在一定量的用水条件下，在洗衣过程中如何 合理地分配这些水，使得能达到把衣服洗净的目的。,我们在问题的分析中已经知道了洗衣的原理是将吸附在衣物上的污物溶于水中，通过拧干（脱水）而荡涤污物。因此我们有以下的两个假设：,补例12 洗衣节水问题,1）在漂洗时间足够的前提下
6、，衣服上的污物能被洗涤剂完全溶解在水中。,2）每次拧干后衣服中残留的水量是一致的。,模型假设：,补例2 洗衣节水问题,问题归结为：在水的总量为 的条件下，将水分成 次洗涤，每次用量分别为 。问经过这 次洗涤，衣服上还剩下多少污物？,模型建立与求解：,设洗衣服一开始浸泡时的用水量为 ，按照问题的分析， 可看成是一个常量。,经拧干后残留污物的质量为 ，记第 次拧干后残留于衣服中的污物（ 还包含了洗涤剂的质量）为 ，同时记衣服中残留的水量为 ，再设洗衣服的总水量为 ，,补例2 洗衣节水问题,我们引入洗涤剂的浓度概念 （单位质量水中所含的污物质量）（ 表示第 次漂洗污物的浓度），第一次漂洗时的浓度为,
7、我们引入洗涤剂的浓度概念 （单位质量水中所含的污物质量）（ 表示第 次漂洗污物的浓度），第一次漂洗时的浓度为,补例2 洗衣节水问题,仿此，可得第二次漂洗时的浓度,此时拧干残留的污物为,依此类推，可得第 此漂洗之后，衣服上的残留污 物量为,补例2 洗衣节水问题,（2）式可化为,（3）式为一递推关系式，以下导出 关于初始值 的 表达式。,因此由数学归纳法证得,补例2 洗衣节水问题,洗衣服的目的是要使污物越来越少，即在漂洗过程中洗涤剂浓度越来越少，转化为数学语言就是在一定条件下，如何选取 方能使 达到最小。,（5）式还可以改写为,我们将它总结为以下定理：,定理： 在总用水量一定的条件下，平均分配每次
8、加水量，实现的洗涤效果最好。,证：,补例2 洗衣节水问题,补例2 洗衣节水问题,补例2 洗衣节水问题,模型分析：从残留在衣服中污物量的浓度变化可知 ，即每多洗涤一次，污物就少一些。实际上 在每次洗涤加水量相同的条件下，由(5)式得,关于 是单调递减的函数。即漂洗衣服最好少量多次。,(8)式说明了当水的总量一定的时候，无论你怎样洗涤，不 管次数多少，最后的结果是不可能一点污物都不残留的。,补例2 洗衣节水问题,补例2 洗衣节水问题,先引入一个清洁度 的定义。设 是洗净衣服上的污物量与 第一次浸泡后残留在衣服上的污物量之比，即,进一步讨论:,如何确定洗涤的次数 。,我们用 来反映衣物洗净的清洁程度
9、。,洗涤的次数大约为3，即洗涤3次可使衣服洁净到一定程度， 这一结果与我们生活实际情况也是相符的。,补例2 洗衣节水问题,一. 比例代表制 例：有A、B、C、D四个政党，代表50万选民，各政党的选民数为： A党：199,000 B党：127,500 C党：124,000 D党： 49,500 要选出5名代表： A党：2席 B党：1席 C党：1席 D党：0席 缺少1席，如何分配这最后一席呢？,补例3 公平的席位分配,最大余数法 按每10万选民1席分配后，按余数大小排序，多余的席位分给余数较大的各党。 党名 代表选民数 整数席 余 数 余额席 总席数 A 199,000 1 99,000 1 2
10、B 127,500 1 27,500 0 1 C 124,000 1 24,000 0 1 D 49,500 0 49,500 1 1,补例3 公平的席位分配,洪德(dHondt)规则 分配办法是：把各党代表的选民数分别被1、2、3、除，按所有商数的大小排序，席位按此次序分配。即若A党的人数比D党的人数还多，那么给A党3席、给D党0席也是合理的。 除数 A党 B党 C党 D党 1 199,000(1) 127,500(2) 124,000(3) 49,500 2 99,500 (4) 63,750 62,000 24,750 3 66,333 (5) 42,500 41,333 16,500
11、4 49,750 31,875 总席位 3 1 1 0,补例3 公平的席位分配,北欧折衷方案 作法与洪德规则类似，所采用的除数依次为1.4、3、5、7、 A党 B党 C党 D党 2 2 1 0 三种分配方案，得到了完全不同的结果，最大余数法显然对小党比较有利，洪德规则则偏向最大的党，北欧折衷方案对最大和最小党都不利,补例3 公平的席位分配,二份额分配法(Quota Method) 一种以“相对公平”为标准的席位分配方法，来源于著名的“阿拉巴玛悖论”(Alabama Paradox)。 美国宪法第1条第2款对议会席位分配作了明确规定，议员数按各州相应的人数进行分配。最初议员数只有65席，因为议会
12、有权改变它的席位数，到1910年，议会增加到435席。宪法并没有规定席位的具体分配办法，因此在1881年，当考虑重新分配席位时，发现用当时的最大余数分配方法，阿拉巴玛州在299个席位中获得8个议席，而当总席位增加为300席时，它却只能分得7个议席。这一怪事被称为有名的“阿拉巴玛悖论”。,补例3 公平的席位分配,问题,三个系学生共200名（甲系100，乙系60，丙系40），代表会议共20席，按比例分配，三个系分别为10，6，4席。,现因学生转系，三系人数为103, 63, 34, 问20席如何分配。,若增加为21席，又如何分配。,比例加惯例,对丙系公平吗,补例3 公平的席位分配,“公平”分配方法
13、,衡量公平分配的数量指标,当p1/n1= p2/n2 时，分配公平,p1/n1 p2/n2 对A的绝对不公平度,p1=150, n1=10, p1/n1=15 p2=100, n2=10, p2/n2=10,p1=1050, n1=10, p1/n1=105 p2=1000, n2=10, p2/n2=100,p1/n1 p2/n2=5,但后者对A的不公平程度已大大降低!,虽二者的绝对不公平度相同,若 p1/n1 p2/n2 ，对 不公平,A,p1/n1 p2/n2=5,公平分配方案应使 rA , rB 尽量小,不妨设分配开始时 p1/n1 p2/n2 ，即对A不公平, 对A的相对不公平度,将
14、绝对度量改为相对度量,类似地定义 rB(n1,n2),将一次性的席位分配转化为动态的席位分配, 即,“公平”分配方法,若 p1/n1 p2/n2 ，定义,1）若 p1/(n1+1) p2/n2 ，,则这席应给 A,2）若 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/n1p2/(n2+1) 是否会出现？,A,否!,若rB(n1+1, n2) rA(n1, n2+1), 则
15、这席应给 B,当 rB(n1+1, n2) rA(n1, n2+1), 该席给A,该席给A,否则, 该席给B,推广到m方分配席位,该席给Q值最大的一方,Q 值方法,三系用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席给甲系,进一步的讨论,Q值方法比“比例加惯例”方法更公平吗？,席位分配的理想化准则,已知: m方人数分别为 p1, p2, , pm,
