席位分配問(wèn)題

1、席位分配問(wèn)題一、問(wèn)題背景席位分配是日常生活中經(jīng)常遇到的問(wèn)題，對(duì)于企業(yè)、公司、學(xué)校、政府等部門都能解決實(shí)際的問(wèn)題。席位可是是代表大會(huì)、股東會(huì)議、公司企業(yè)員工大會(huì)等的具體座位。二、問(wèn)題提出學(xué)校共 1000 名學(xué)生， 235 人住在 a 宿舍， 333 人住在 b 宿舍， 432 人住在 c宿舍 .學(xué)生們要組織一個(gè)10 人的委員會(huì)，試用下列辦法分配各宿舍的委員數(shù)：（1）. 按比例分配取整數(shù)的名額后, 剩下的名額按慣例分給小數(shù)部分較大者; （2）. 用 2.1 中的 q值方法分配，要求編一個(gè)通用程序解決此類分配問(wèn)題；（3）.d hondt 方法：將a、b、c各宿舍的人數(shù)用正整數(shù)n=1,2,3,相除，其

2、商數(shù)如下表：將所得商數(shù)從大到小取前10 個(gè)（ 10 為席位數(shù)），在數(shù)字下標(biāo)以橫線，表中a 、 b、c行有橫線的數(shù)分別為2，3，5，這就是3 個(gè)宿舍分配的席位. 請(qǐng)解釋此方法的原理，并編程求解。（4）如果委員會(huì)從10 個(gè)人增至15 人，用以上3 種方法再分配名額，將3 種方法兩次分配的結(jié)果列表比較. 三、模型的建立與求解（1）通常分配結(jié)果的公布與否以每個(gè)代表席位所代表的人數(shù)相等或相近來(lái)衡量，目前沿用的慣例分配方法為按比例分配方法，即：=席位分配數(shù)總?cè)藬?shù)比例總席位數(shù)按比例分配取整數(shù)的名額后, 剩下的名額按慣例分給小數(shù)部分較大者，所以分配情況如表一所示。表一宿舍學(xué)生人數(shù)學(xué)生人數(shù)比例按比例分配的席位按

3、慣例分配的席位a 235 0.235 2.35 3 b 333 0.333 3.33 3 c 432 0.432 4.32 4 總和1000 10 10 學(xué)生們要組織的10 人的委員會(huì)，分配各宿舍的委員數(shù)分別為：a宿舍 3 人， b宿舍 3 人， c宿舍 4 人。（2）q值法：有m方分配席位的情況，設(shè)第i方人數(shù)為ip， 已占有in個(gè)席位，1,2,.im 1 2 3 4 5 a b c 235 117.5 78.3 58.75 333 166.5 111 83.25 432 216 144 108 86.4 當(dāng)總席位增加1 席時(shí)，計(jì)算2,1,2,(1)iiiipqimn n應(yīng)將這一席分給q值最大

4、的一方，這種席位分配方法稱為q值法。（3） 、原理是先按各宿舍人數(shù)的大小排列依次分一個(gè)，再根據(jù)席位數(shù)的多少，從各宿舍人數(shù)用正整數(shù)n=1,2,3,相除得到的數(shù)的大小排列中，依次分配，不斷循環(huán)直到席位分配完成。相當(dāng)于不考慮各宿舍人數(shù)占總?cè)藬?shù)的比例，把席位比較均勻的分配到個(gè)宿舍，但這樣的話就不可能解決公平問(wèn)題。（4） 、把相應(yīng)的n=10 改成 n=15，帶入程序，可得按慣例分配a、b、c 的席位分別為3、5、6；按 dhonht 方法三個(gè)宿舍分得的細(xì)微分別為：3、5、7；按 q 值法分配方法三個(gè)宿舍分得的席位為：4、5、6。兩種席位數(shù)分配方案如下表：分配方法席位數(shù)按慣例分配dhonht 法q 值法n

5、=10 3, 3, 4 2, 3, 5 2, 3 , 5 n=15 4, 5, 6 3, 5, 7 4, 5, 6 三種分配方法程序代碼：clear all clc disp(席位分配： ) p=1000; p=235 333 432; n=10; x,y=size(p); zu=x*y; disp(慣例分配方法:) for i = 1:zu n(i) =p(i)*n/p; end n; m=n-fix(n); for i=1:zu if n(i)=max(m)+fix(n(i) n(i)=fix(n(i)+1; else n(i)=fix(n(i); end end n disp(dhonh

6、t方法 :) pp=; for i=1:n pi=p/i; pp=pp; pi; end pp; m=zeros(1,zu); for i=1:n x,y=find(pp=max(pp(:); pp(x,y)=0; m(y)=m(y)+1; end pp; m disp(q值法分配方法 :) q=ones(1,zu); q=; p; for i=1:zu q(i)=p(i)*p(i)/(q(i)*(q(i)+1); end q; xiwei(p,q,q,n,zu) 其中 xiwei(p,q,q,n,zu)的定義如下：function xiwei(p,q,q,n,zu) if sum(q)=n disp(q值法分配人數(shù)：) q return; else for i=1:zu if q(i)=max(q) q(i)=q(i)+1; q(i)=p(i)*p(i)/(q(i)*(q(i)+1); break;