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

补例1赛程安排问题,问题提出：1.某校组织乒乓球比赛，因报名人数较多，决定采用单淘汰进行比赛。请问如何合理地安排赛程？2.某校举办排球比赛，比赛形式为单循环赛。请问应如何安排比赛？,问题分析：1.选择赛制（不同的赛制决定赛程安排的差异）2.比赛的总场次、比赛的轮数及轮空人数等问题,模型建立与求解：,一、单淘汰赛：,方案1.允许在第一轮中有轮空现象,方案2.在每一轮都要保证尽可能多的运动员参赛,补例1赛程安排问题,方案1：设有n人报名参赛，下面对n为不同的值进行讨论。,（2）若，则存在一个正整数k，使得,（1）若，第一轮比赛有场，1/4决赛有场，半决赛有2场，冠亚军比赛1场，合计（场）：,补例1赛程安排问题,所以一共要比赛：,若本轮比赛的人数为偶数，则没有轮空；若人数为奇数，则有1人轮空。从而比赛轮空的人数不大于k1人,方案2：设有n人报名参赛，每一轮允许有轮空现象。,例1：某校有11位同学参加围棋单淘汰赛，应该进行几场比赛？,则存在一个正整数k，使得,补例1赛程安排问题,二、单循环赛：,设有n队参加比赛，则每队都要与其余的n1支队分别比赛一场。当n为偶数时，则要举行n1轮比赛；当n为奇数时，则要举行n轮比赛，且每轮有1队轮空,单循环赛就是参加比赛的每一个人都要和其他人比赛一次，然后根据总体成绩排定名次。如果和其他人比赛两次，则称为双循环赛。,定理：设有n队参加比赛，则比赛的总场数是场。,例2：某校共有26个班，举行排球比赛，在不同的赛制下各要比多少场？,补例1赛程安排问题,优缺点分析：（略）,例3：参加排球比赛的26个班级，先分成3个小组，其中两个组为9队，另一个组为8队，在小组中，先用单循环赛产生每个小组的前两名，接下来，每小组的前两名共6个队再进行单循环赛。以8支队的小组为例，对赛程进行合理安排。,解：在第一阶段：场,在第二阶段：场,一共比赛的场数为100+15115场。,补例1赛程安排问题,用表示八支代表对，则,A1A2A3A4A5A6A7A8,A1A3A5A2A7A4A8A6,A1A5A7A3A8A2A6A4,A1A7A8A5A6A3A4A2,A1A8A6A7A4A5A2A3,A1A6A4A8A2A7A3A5,A1A4A2A6A3A8A5A7,补例1赛程安排问题,由以上表格可知该安排是合理的,作业：当7支队参加单循环赛的排球比赛时，试合理的安排其赛程。,补例2洗衣节水问题,我国淡水资源有限，节约用水势在必行。那么如何在洗衣服中合理地用水，使得既能把衣服洗干净，又能节约用水的问题就摆在我们的面前。一般洗衣服的过程是先将衣服用洗涤剂浸泡，然后一次次地用水漂洗。洗衣机的运行过程分别为加水漂洗脱水加水漂洗脱水这么一个循环过程。我们的问题是在保证一定洗涤效果下，洗衣服分成多少次（或在洗衣机中应循环几次），每一次的用水量是否一致，使得总的用水量最为节省？,问题提出：,衣服洁净的问题实际上是比较复杂的，它不仅有物理原理，还有化学原理（如果是洗衣机，则与机械原理有关）。,补例2洗衣节水问题,问题分析：,其基本原理就是将吸附在衣物上的污物溶于水中，通过脱水而荡涤污物。,节水目标为在一定量的用水条件下，在洗衣过程中如何合理地分配这些水，使得能达到把衣服洗净的目的。,我们在问题的分析中已经知道了洗衣的原理是将吸附在衣物上的污物溶于水中，通过拧干（脱水）而荡涤污物。因此我们有以下的两个假设：,补例12洗衣节水问题,1）在漂洗时间足够的前提下，衣服上的污物能被洗涤剂完全溶解在水中。,2）每次拧干后衣服中残留的水量是一致的。,模型假设：,补例2洗衣节水问题,问题归结为：在水的总量为的条件下，将水分成次洗涤，每次用量分别为。问经过这次洗涤，衣服上还剩下多少污物？,模型建立与求解：,设洗衣服一开始浸泡时的用水量为，按照问题的分析，可看成是一个常量。,经拧干后残留污物的质量为，记第次拧干后残留于衣服中的污物（还包含了洗涤剂的质量）为，同时记衣服中残留的水量为，再设洗衣服的总水量为，,补例2洗衣节水问题,我们引入洗涤剂的浓度概念（单位质量水中所含的污物质量）（表示第次漂洗污物的浓度），第一次漂洗时的浓度为,我们引入洗涤剂的浓度概念（单位质量水中所含的污物质量）（表示第次漂洗污物的浓度），第一次漂洗时的浓度为,补例2洗衣节水问题,仿此，可得第二次漂洗时的浓度,此时拧干残留的污物为,依此类推，可得第此漂洗之后，衣服上的残留污物量为,补例2洗衣节水问题,（2）式可化为,（3）式为一递推关系式，以下导出关于初始值的表达式。,因此由数学归纳法证得,补例2洗衣节水问题,洗衣服的目的是要使污物越来越少，即在漂洗过程中洗涤剂浓度越来越少，转化为数学语言就是在一定条件下，如何选取方能使达到最小。,（5）式还可以改写为,我们将它总结为以下定理：,定理：在总用水量一定的条件下，平均分配每次加水量，实现的洗涤效果最好。,证：,补例2洗衣节水问题,补例2洗衣节水问题,补例2洗衣节水问题,模型分析：从残留在衣服中污物量的浓度变化可知，即每多洗涤一次，污物就少一些。实际上在每次洗涤加水量相同的条件下，由(5)式得,关于是单调递减的函数。即漂洗衣服最好少量多次。,(8)式说明了当水的总量一定的时候，无论你怎样洗涤，不管次数多少，最后的结果是不可能一点污物都不残留的。,补例2洗衣节水问题,补例2洗衣节水问题,先引入一个清洁度的定义。设是洗净衣服上的污物量与第一次浸泡后残留在衣服上的污物量之比，即,进一步讨论:,如何确定洗涤的次数。,我们用来反映衣物洗净的清洁程度。,洗涤的次数大约为3，即洗涤3次可使衣服洁净到一定程度，这一结果与我们生活实际情况也是相符的。,补例2洗衣节水问题,一.比例代表制例：有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公平的席位分配,最大余数法按每10万选民1席分配后，按余数大小排序，多余的席位分给余数较大的各党。党名代表选民数整数席余数余额席总席数A199,000199,00012B127,500127,50001C124,000124,00001D49,500049,50011,补例3公平的席位分配,洪德(dHondt)规则分配办法是：把各党代表的选民数分别被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公平的席位分配,北欧折衷方案作法与洪德规则类似，所采用的除数依次为1.4、3、5、7、A党B党C党D党2210三种分配方案，得到了完全不同的结果，最大余数法显然对小党比较有利，洪德规则则偏向最大的党，北欧折衷方案对最大和最小党都不利,补例3公平的席位分配,二份额分配法(QuotaMethod)一种以“相对公平”为标准的席位分配方法，来源于著名的“阿拉巴玛悖论”(AlabamaParadox)。美国宪法第1条第2款对议会席位分配作了明确规定，议员数按各州相应的人数进行分配。最初议员数只有65席，因为议会有权改变它的席位数，到1910年，议会增加到435席。宪法并没有规定席位的具体分配办法，因此在1881年，当考虑重新分配席位时，发现用当时的最大余数分配方法，阿拉巴玛州在299个席位中获得8个议席，而当总席位增加为300席时，它却只能分得7个议席。这一怪事被称为有名的“阿拉巴玛悖论”。,补例3公平的席位分配,问题,三个系学生共200名（甲系100，乙系60，丙系40），代表会议共20席，按比例分配，三个系分别为10，6，4席。,现因学生转系，三系人数为103,63,34,问20席如何分配。,若增加为21席，又如何分配。,比例加惯例,对丙系公平吗,补例3公平的席位分配,“公平”分配方法,衡量公平分配的数量指标,当p1/n1=p2/n2时，分配公平,p1/n1p2/n2对A的绝对不公平度,p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10,p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100,p1/n1p2/n2=5,但后者对A的不公平程度已大大降低!,虽二者的绝对不公平度相同,若p1/n1p2/n2，对不公平,A,p1/n1p2/n2=5,公平分配方案应使rA,rB尽量小,不妨设分配开始时p1/n1p2/n2，即对A不公平,对A的相对不公平度,将绝对度量改为相对度量,类似地定义rB(n1,n2),将一次性的席位分配转化为动态的席位分配,即,“公平”分配方法,若p1/n1p2/n2，定义,1）若p1/(n1+1)p2/n2，,则这席应给A,2）若p1/(n1+1)p2/(n2+1)，,应计算rB(n1+1,n2),应计算rA(n1,n2+1),若rB(n1+1,n2)p2/n2,问：,p1/n1rA(n1,n2+1),则这席应给B,当rB(n1+1,n2)=2,j=2）时，由于mi=2,nj=2,不妨设所剪去的那块白格是某个33格子盘中的格子。,则原来的格子盘被划分为若干个小格子盘,中至少有一个为偶数，由定理1知每个小格子盘都可被完全覆盖。,而对于33的格子盘中剪去的白格无论在边上还是在中间都可被完全覆盖，所以结论成立。,补例4铺地砖问题,对于mn格子盘，其中m