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

yunjiang

　　 <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>。

yunjiang

　　如果对一切的<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>进行“四舍五入取整”或者“去掉尾数取整”，这样将导致名额多余或者名额不够分配。因此，我们必须寻求新的分配方案。　　　

yunjiang

<><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>

yunjiang

<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>（汉丁顿）提出了一个新方法，简述如下。

yunjiang

　　 <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>
　　第一种情形显然比第二种情形更不公平，但它们具有相同的不公平度，所以“绝对不公平度”不是一个好的数量指标，我们必须寻求新的数量指标。

yunjiang

<><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>

yunjiang

<><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>

yunjiang

<><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>

duanshumo

谢谢你的帖子

coeeoc

<>谢谢</P>