数模论坛

 找回密码
 注-册-帐-号
搜索
热搜: 活动 交友 discuz
查看: 12626|回复: 10

第十讲 初等数学模型(3)——代表名额分配问题

  [复制链接]
发表于 2004-7-22 10:03:39 | 显示全部楼层 |阅读模式
   <b>问题的提出</b>
   分配问题是日常生活中经常遇到的问题,它涉及到如何将有限的人力或其他资源以“完整的部分”分配到下属部门或各项不同任务中。分配问题涉及的内容十分广泛,例如:大到召开全国人民代表大会,小到某学校召开学生代表大会,均涉及到将代表名额分配到各个下属部门的问题。代表名额的分配(亦称为席位分配问题)是数学在人类政治生活中的一个重要应用,应归属于政治模型。一个自然的问题是如何分配代表名额才是公平的呢?
<B>  </B><B>模型的分析</B><B>与建立</B><B> </B>
  本讲以某校学生代表大会名额分配为例,介绍解决代表名额分配问题的几种典型的方法及其数学模型。
  在数学上,代表名额分配问题的一般描述是:设名额数为<I>N</I>,共有<I>s</I>个单位,各单位的人数分别为<I>p<SUB>i</SUB></I>,<I>i</I>=1,2,…,<I>s</I>。问题是如何寻找一组整数<SUB><IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image002.gif"> </SUB>使得<SUB> <IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image004.gif"> </SUB>=<I>N</I>,其中<SUB> <IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image006.gif"> </SUB><I><SUB>i</SUB></I>是第<I>i</I>个单位所获得的代表名额数,并且“尽可能”地接近它应得的份额<I>p<SUB>i</SUB>N</I>/(<I>p</I><SUB>1</SUB>+<I>p</I><SUB>2</SUB>+…+<I>p<SUB>s</SUB></I>),即所谓的<B>按人口比例分配的原则</B>。
 楼主| 发表于 2004-7-22 10:03:54 | 显示全部楼层
  如果对一切的<I>i</I>=1,2,…<I>,s</I>,严格的比值<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image008.gif"> </SUB>恰好是整数,则第<I>i</I>个单位分得<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image010.gif"> </SUB><I><SUB>i</SUB></I>个名额,这种分配自然是绝对公平的,每个名额所代表的人数是相同的。但由于人数是整数,名额也是整数,<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image012.gif"> </SUB><I><SUB>i</SUB></I>是整数这种理想情况是极少出现的,这样就出现了用接近于<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image014.gif"> </SUB><I><SUB>i</SUB></I>的整数进行代替的问题。在实际应用中,这个代替的过程会给不同的单位或团体带来不平等。这样,以一种平等、公正的方式选择<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image016.gif"> </SUB><I><SUB>i</SUB></I>便是非常重要的事情了。如何确定尽可能公平(在数学上即不公平程度达到极小)的分配方案?
  设某校有3个系(<I>s</I>=3)共有200名学生,其中甲系100名(<I>p</I><SUB>1</SUB>=100),乙系60名(<I>p</I><SUB>2</SUB>=60),丙系40名(<I>p</I><SUB>3</SUB>=40)。该校召开学生代表大会共有20个代表名额(<I>N</I>=20),公平而又简单的名额分配方案是按学生人数的比例分配,显然甲乙丙三个系分别应占有<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image018.gif"> </SUB><SUB>1</SUB>=10,<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image020.gif"> </SUB><SUB>2</SUB>=6,<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image022.gif"> </SUB><SUB>3</SUB>=4个名额。这是一个绝对公平的分配方案。现在丙系有6名同学转入其他两系学习,这时<I>p</I><SUB>1</SUB>=103,<I>p</I><SUB>2</SUB>=63,<I>p</I><SUB>3</SUB>=34,按学生人数的比例分配,此时<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image023.gif"> </SUB><I><SUB>i</SUB></I>不再是整数,而名额数必须是整数,一个自然的想法是:对<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image025.gif"> </SUB><I><SUB>i</SUB></I>进行“四舍五入取整”或者“去掉尾数取整”,这样将导致名额多余或者名额不够分配。因此,我们必须寻求新的分配方案。   
 楼主| 发表于 2004-7-22 10:04:10 | 显示全部楼层
<><B>  </B><I><b>Hamilton</b></I><b> (哈密顿)方法</b>  
   哈密顿方法具体操作过程如下:
   1. 先让各个单位取得份额<I>n<SUB>i</SUB></I>的整数部分[<I>n<SUB>i</SUB></I>];
   2. 计算<I>r<SUB>i</SUB></I>=<I>n<SUB>i</SUB></I>-[<I>n<SUB>i</SUB></I>],按照从大到小的数序排列,将余下的席位依次分给各个相应的单位,即小数部分最大的单位优先获得余下席位的第一个,次大的取得余下名额的第二个,依此类推,直至席位分配完毕。<I>
   </I>上述三个系的20个名额的分配结果见表2—1。<I>
     </I> 表2—1   按哈密顿方法确定的20个代表名额的分配方案
    <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/2_1.gif">
  哈密顿方法看来是非常合理的,但这种方法也存在缺陷。譬如当<I>s</I>和人数比例<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image026.gif"> </SUB>不变时,代表名额的增加反而导致某单位名额<I>n<SUB>i</SUB></I>的减少。</P>
 楼主| 发表于 2004-7-22 10:04:24 | 显示全部楼层
<b>  </b>考虑上述某校学生代表大会名额分配问题。因为有20个代表参加的学生代表大会在表决某些提案时可能出现10:10的局面,会议决定下一届增加一个名额。按照哈密顿方法分配结果见表2—2。
             表2—2
  <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/b1.gif">
  显然这个结果对丙系是极其不公平的,因为总名额增加一个,而丙系的代表名额却由4个减少为3个。
  由此可见,哈密顿方法存在很大缺陷,因而被放弃。20世纪20年代初期,由哈佛大学数学家<I>Huntington</I>(汉丁顿)提出了一个新方法,简述如下。
 楼主| 发表于 2004-7-22 10:04:39 | 显示全部楼层
   <B><I>Huntington</I></B><B>(汉丁顿)方法</B>
   易见,<I>p<SUB>i</SUB></I>/<I>n<SUB>i</SUB></I>表示第<I>i</I>个单位每个代表名额所代表的人数。很显然,当且仅当<I>p<SUB>i</SUB></I>/<I>n<SUB>i</SUB></I>全相等时,名额的分配才是公平的。但是,一般来说,它们不会全相等,这就说明名额的分配是不公平的,并且<I>p<SUB>i</SUB></I>/<I>n<SUB>i</SUB></I>中数值较大的一方吃亏或者说对这一方不公平。同时我们看到,在名额分配问题中要达到绝对公平是非常困难的。既然很难作到绝对公平,那么就应该使不公平程度尽可能的小,因此我们必须建立衡量不公平程度的数量指标。
  不失一般性,我们考虑<I>A</I>,<I>B</I>双方席位分配的情形(即<I>s</I>=2)。设<I>A</I>,<I>B</I>双方的人数为<I>p</I><SUB>1</SUB>,<I>p</I><SUB>2</SUB>,占有的席位分别为<I>n</I><SUB>1</SUB>,<I>n</I><SUB>2</SUB>,则<I>A</I>,<I>B</I>的每个席位所代表的人数分别为<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>,<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,如果<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>=<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,则席位分配是绝对公平的,否则就是不公平的,且对数值较大的一方不公平。为了刻划不公平程度,需要引入数量指标,一个很直接的想法就是用数值|<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>-<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>|来表示双方的不公平程度,称之为绝对不公平度,它衡量的是不公平的绝对程度。显然,其数值越小,不公平程度越小,当|<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>-<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>|=0时,分配方案是绝对公平的。故用绝对不公平度可以区分两种不同分配方案的公平程度,例如:
   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image028.gif"></SUB>
   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image030.gif"></SUB>
  显然第二种分配方案比第一种更公平。但是,绝对不公平度有时无法区分两种不公平程度明显不同的情况,例如:
   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image031.gif"></SUB>
   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image033.gif"></SUB>
  第一种情形显然比第二种情形更不公平,但它们具有相同的不公平度,所以“绝对不公平度”不是一个好的数量指标,我们必须寻求新的数量指标。
 楼主| 发表于 2004-7-22 10:04:54 | 显示全部楼层
<><B>  </B>这时自然想到用相对标准,下面我们引入相对不公平的概念。如果<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>&gt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,则说明<I>A</I>方是吃亏的,或者说对<I>A</I>方是不公平的,称
        <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image035.gif"> </SUB>
为对<I>A</I>的相对不公平度;如果<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>&lt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,则称
        <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image037.gif"> </SUB>
为对<I>B</I>的相对不公平度。<I>
  </I>相对不公平度可以解决绝对不公平度所不能解决的问题,考虑上面的例子:
   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image039.gif"> </SUB>
显然均有<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>&gt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,此时
         <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image041.gif"> </SUB>
与前一种情形相比后一种更公平。</P>
 楼主| 发表于 2004-7-22 10:05:10 | 显示全部楼层
<><B>  </B><b>制定分配方案</b>
  建立了衡量分配方案的不公平程度的数量指标<I>r<SUB>A</SUB></I>,<I>r<SUB>B</SUB></I>后,制定分配方案的原则自然是:相对不公平度尽可能的小。<I>
</I>  首先我们作如下的假设:
  (1)每个单位的每个人都具有相同的选举权利;
  (2)每个单位至少应该分配到一个名额,如果某个单位,一个名额也不应该分到的话,则应将其剔除在分配之外;
  (3)在名额分配的过程中,分配是稳定的,不受任何其他因素所干扰。<I>
</I>  假设<I>A</I>,<I>B</I>双方已经分别占有<I>n</I><SUB>1</SUB>,<I>n</I><SUB>2</SUB>个名额,下面我们考虑这样的问题,当分配名额再增加一个时,应该给<I>A</I>方还是给<I>B</I>方,如果这个问题解决了,那么就可以确定整个分配方案了,因为每个单位至少应分配到一个名额,我们首先分别给每个单位一个席位,然后考虑下一个名额给哪个单位,直至分配完所有名额。<I>
  </I>不失一般性,假设<I>p</I><SUB>1</SUB>/<I>n</I><SUB>1</SUB>&gt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,这时对<I>A</I>方不公平,当再增加一个名额时,就有以下三种情形:
  情形1:<I>p</I><SUB>1</SUB>/(<I>n</I><SUB>1</SUB>+1)&gt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,这表明即使<I>A</I>方再增加一个名额,仍然对<I>A</I>方不公平,所以这个名额应当给<I>A</I>方;
  情形2:<I>p</I><SUB>1</SUB>/(<I>n</I><SUB>1</SUB>+1)&lt;<I>p</I><SUB>2</SUB>/<I>n</I><SUB>2</SUB>,这表明<I>A</I>方增加一个名额后,就对<I>B</I>方不公平,这时对<I>B</I>的相对不公平度为
         <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image043.gif"> </SUB>;</P>
 楼主| 发表于 2004-7-22 10:05:26 | 显示全部楼层
<><B>  </B>公平的名额分配方法应该是使得相对不公平度尽可能的小,所以若情形1发生,毫无疑问增加的名额应该给<I>A</I>方;否则需考察<I>r<SUB>B</SUB></I>(<I>n</I><SUB>1</SUB>+1,<I>n</I><SUB>2</SUB>)和
<I>r<SUB>A</SUB></I>(<I>n</I><SUB>1</SUB>,<I>n</I><SUB>2</SUB>+1)的大小关系,如果<I>r<SUB>B</SUB></I>(<I>n</I><SUB>1</SUB>+1,<I>n</I><SUB>2</SUB>)&lt;<I>r<SUB>A</SUB></I>(<I>n</I><SUB>1</SUB>,<I>n</I><SUB>2</SUB>+1),则增加的名额应该给<I>A</I>方,否则应该给<I>B</I>方。<I>
  </I>注意到<I>r<SUB>B</SUB></I>(<I>n</I><SUB>1</SUB>+1,<I>n</I><SUB>2</SUB>)&lt;<I>r<SUB>A</SUB></I>(<I>n</I><SUB>1</SUB>,<I>n</I><SUB>2</SUB>+1)等价于
            <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image047.gif"> </SUB>,
而且若情形1发生,仍然有上式成立。记
            <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image049.gif"> </SUB>,
则增加的名额应该给<I>Q</I>的值较大的一方。<I>
  </I>上述方法可以推广到<I>s</I>个单位的情形,设第<I>i</I>个单位的人数为<I>p<SUB>i</SUB></I>,已经占有<I>n<SUB>i</SUB></I>个名额,<I>i</I>=1,2,…,<I>s</I>,当总名额增加一个时,计算
            <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/sxjm10.files/image051.gif"> </SUB>,
则这个名额应该分给<I>Q</I>值最大的那个单位。<I>
  </I><a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_02_10/sxjm_10/htm/08.htm#" target="_blank" ><FONT color=#0000cc>表2—3</FONT></A>是利用汉丁顿法重新分配三个系21个名额的计算结果。丙系保住了险些丧失的一个名额。<I>
  </I>其中括号外数字是Q值,括号内数字是名额序数,而前三个名额已经按每个单位都至少有一个名额原则平均分配完毕。
  <b>模型评注 </b>
  名额(席位)分配问题应该对各方公平是理所当然的,问题的关键是在于建立衡量公平程度的即合理又简明的数量指标。汉丁顿法所提出的数量指标是相对不公平值<I>r<SUB>A</SUB></I>,<I>r<SUB>B</SUB></I>,它是确定分配方案的前提。在这个前提下导出的分配方案—分给<I>Q</I>值最大的一方——无疑是公平的。但这种方法也不是尽善尽美的,这里不再探讨。</P>
发表于 2004-7-24 00:36:54 | 显示全部楼层
谢谢你的帖子
发表于 2004-8-10 02:44:11 | 显示全部楼层
<>谢谢</P>
您需要登录后才可以回帖 登录 | 注-册-帐-号

本版积分规则

小黑屋|手机版|Archiver|数学建模网 ( 湘ICP备11011602号 )

GMT+8, 2024-10-4 12:30 , Processed in 0.076782 second(s), 18 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表