席位分配問題

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

2、0為席位數(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ù)相等或相近來衡量，目前沿用的慣例分配方法為按比例分配方法，即：席位分配數(shù)=總?cè)藬?shù)比例總席位數(shù)按比例分配取整數(shù)的名額后,剩下的名額按慣例分給小數(shù)部分較大者，所以分配情況如表一所示。學(xué)生們要組織的10人的委員會(huì)，分配各宿舍的委員數(shù)分別為：A宿舍3人，B宿舍3人，C宿舍4人。（2）Q值法：有m方分配

3、席位的情況，設(shè)第i方人數(shù)為pi，已占有ni個(gè)席位，i=1,2, ,m.pi2當(dāng)總席位增加1席時(shí)，計(jì)算 Qi=,i=1,2, ,m應(yīng)將這一席分給Q值最大的一方，ni(ni+1)這種席位分配方法稱為Q值法。（3）、原理是先按各宿舍人數(shù)的大小排列依次分一個(gè)，再根據(jù)席位數(shù)的多少，從各宿舍人數(shù)用正整數(shù)n=1,2,3,相除得到的數(shù)的大小排列中，依次分配，不斷循環(huán)直到席位分配完成。相當(dāng)于不考慮各宿舍人數(shù)占總?cè)藬?shù)的比例，把席位比較均勻的分配到個(gè)宿舍，但這樣的話就不可能解決公平問題。（4）、把相應(yīng)的N=10改成N=15，帶入程序，可得按慣例分配A、B、C的席位分別為3、5、6；按dhonht方法三個(gè)宿舍分得的細(xì)

4、微分別為：3、5、7；按Q值法分配方法三個(gè)宿舍分得的席位為：4、5、6。兩種席位數(shù)分配方案如下表：三種分配方法程序代碼：clear allclcdisp(席位分配：)P=1000;p=235 333 432;N=10;x,y=size(p);zu=x*y;disp(慣例分配方法:)for i = 1:zun(i) =p(i)*N/P;endn;m=n-fix(n);for i=1:zuif n(i)=max(m)+fix(n(i)n(i)=fix(n(i)+1;elsen(i)=fix(n(i);endendndisp(dhonht方法:)pp=;for i=1:Npi=p/i;pp=pp;

5、pi;endpp;m=zeros(1,zu);for i=1:Nx,y=find(pp=max(pp(:);pp(x,y)=0;m(y)=m(y)+1;endpp;mdisp(Q值法分配方法:)q=ones(1,zu);Q=;p;for i=1:zuQ(i)=p(i)*p(i)/(q(i)*(q(i)+1); endQ;xiwei(p,q,Q,N,zu)其中xiwei(p,q,Q,N,zu)的定義如下：function xiwei(p,q,Q,N,zu)if sum(q)=Ndisp(Q值法分配人數(shù)：)qreturn;elsefor i=1:zuif Q(i)=max(Q)q(i)=q(i)+1;Q(i)=p(i)*p(i)/(q(i)*(q(i)+1); break;endende