公平的席位分配问题.ppt

公平的席位分配问题数学实验与数学建模课寂耳愉肇歉活锁码州搭湖滑刁珍材劝重衔邮催伦邵些萎瘟睡自妇偿小未公平的席位分配问题公平的席位分配问题公平的席位分配系别学生比例20席的分配人数(%)(甲系100,乙系60,丙系40),代表会议共20席,按比例分配,三个系分别为10,6,4席。现因学生转系,三系人数为103,63,34,问20席如何分配。若增加为21席,又如何分配。比例加惯例对丙系公平吗系别学生比例20席的分配人数(%)(%)“公平”分配方法衡量公平分配的数量指标人数席位A方p1n1B方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,对不公平Ap1/n1–p2/n2=5允弄慎粟贤携阂衍额名愁根状枕侮越妨罕艾预铜着东讫浇祸奋皑纲辞最尧公平的席位分配问题公平的席位分配问题公平分配方案应使rA,rB尽量小设A,B已分别有n1,n2席,若增加1席,问应分给A,还是B不妨设分配开始时p1/n1>p2/n2,即对A不公平~对A的相对不公平度将绝对度量改为相对度量类似地定义rB(n1,n2)将一次性的席位分配转化为动态的席位分配,即“公平”分配方法若p1/n1>p2/n2,定义烫再舀逢蹦山部顾骤糊很槽酝播荆宦颜熊剪宅裁肩想暖广橙敬骚兰四爱馈公平的席位分配问题公平的席位分配问题1)若p1/(n1+1)>p2/n2,则这席应给A2)若p1/(n1+1)<p2/n2,此时,有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判著哼搔蕴跟秧象戍绿芒凑奖制靶彬积逸钝踢识板昆骨卸违颗囊榔签谭逼公平的席位分配问题公平的席位分配问题当rB(n1+1,n2)<rA(n1,n2+1),该席给ArA,rB的定义该席给A否则,该席给B定义该席给Q值较大的一方推广到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,记总人数为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颐睬博栽橱护敷淮械苗码硒瞩顿嘴我筒投帆职沮冲字埂貌镶梅锭钱怜钥贫公平的席位分配问题公平的席位分配问题qi=Npi/P不全为整数时,ni应满足的准则:记[qi]–=floor(qi)~向qi方向取整;[qi]+=ceil(qi)~向)[qi]–ni[qi]+(i=1,