數學建模席位分配問題.ppt

2.3 2.3 2.3 2.3 公平的席位分配公平的席位分配公平的席位分配公平的席位分配 某校有某校有 200200 名學生，甲系名學生，甲系 100100 名，乙系名，乙系 6060 名，丙系名，丙系 4040 名，若學生代表會議設名，若學生代表會議設 2020 個席位，問三系各有多少個席位？個席位，問三系各有多少個席位？ 按慣例分配席位方案，即按人數比例分配原則按慣例分配席位方案，即按人數比例分配原則 N p qm?? 表示某單位的席位數表示某單位的席位數m 表示某單位的人數表示某單位的人數 p 表示總人數表示總人數N 表示總席位數表示總席位數 q 1 問題的提出（美國憲法 問題的提出（美國憲法 1788 ）） 20 個席位的分配結果 系別系別系別系別人數人數人數人數所占比例所占比例所占比例所占比例分配方案分配方案分配方案分配方案席位數席位數席位數席位數 甲甲100100100/200100/200(50/100)(50/100)?20=10?20=10 乙乙606060/20060/200(30/100)(30/100)?20=6?20=6 丙丙40 40 40/20040/200(20/100)(20/100)?20=4?20=4 現丙系有現丙系有 6 名學生分別轉到甲、乙系各名學生分別轉到甲、乙系各 3 名。名。 系別系別系別系別人數人數人數人數所占比例所占比例所占比例所占比例分配方案分配方案分配方案分配方案席位數席位數席位數席位數 甲甲103103103/200=51.5%103/200=51.5% 51.5 %51.5 %? ?20 20 =10.3=10.3 乙乙636363/200=31.5%63/200=31.5%31.5%31.5%?20=6.3?20=6.3 丙丙34 34 34/200=17.0%34/200=17.0%17.0%17.0%?20=3.4?20=3.4 10 6 4 10 6 4 現象現象 1 1 丙系少了丙系少了 6 6 人，但席位仍為人，但席位仍為 4 4 個。個。 ( ( 不公平?。┎还剑。?Halmiton(1790) 先按整數分配 再按余數較大者 分配 由于在表決提案時可能出現由于在表決提案時可能出現 1010 ：： 1010 的平局，再設的平局，再設 一個席位。一個席位。 2121 個席位的分配結果（個席位的分配結果（ HalmitonHalmiton 方法）方法） 系別系別人數人數所占比例所占比例分配方案分配方案席位數席位數 甲甲103103103/200=51.5%103/200=51.5% 51.5 %51.5 %? ?21 21 =10.815=10.815 乙乙636363/200=31.5%63/200=31.5%31.5%31.5%?21=6.615?21=6.615 丙丙34 34 34/200=17.0%34/200=17.0%17.0%17.0%?21=3.?21=3.570570 11 7 3 現象現象 2 2 總席位增加一席，丙系反而減少一席。（不公平?。┛傁辉黾右幌?，丙系反而減少一席。（不公平?。?慣例分配方法慣例分配方法（（ Halmiton 方法）方法） ：按比例分配完取整數按比例分配完取整數 的名額后，剩下的名額按慣例分給小數部分較大者。的名額后，剩下的名額按慣例分給小數部分較大者。 存在不公平現象（存在不公平現象（ Alabama 悖論），能否給出更公平悖論），能否給出更公平 的分配席位的方案？的分配席位的方案？ 2 建模分析建模分析 目標：建立公平的分配方案。目標：建立公平的分配方案。 反映公平分配的數量指標可用每席位代表的人數來衡量反映公平分配的數量指標可用每席位代表的人數來衡量 。。 系別系別系別系別人數人數人數人數 席位數席位數席位數席位數每席位代表的人數每席位代表的人數每席位代表的人數每席位代表的人數公平程度公平程度公平程度公平程度 甲甲1031031010103/10=10.3103/10=10.3中中中中 乙乙6363 6 6 63/6=10.563/6=10.5差差差差 丙丙34 34 4 4 34/4=8.534/4=8.5好好好好 系別系別系別系別人數人數人數人數席位數席位數席位數席位數每席位代表的人數每席位代表的人數每席位代表的人數每席位代表的人數 甲甲甲甲1001001010100/10=10100/10=10 乙乙乙乙6060 6 6 60/6=1060/6=10 丙丙丙丙40 40 4 4 40/4=1040/4=10 系別系別系別系別人數人數人數人數席位數席位數席位數席位數每席位代表的人每席位代表的人每席位代表的人每席位代表的人 數數數數 公平程度公平程度公平程度公平程度 甲甲1031031111103/11=9.36103/11=9.36中中中中 乙乙6363 7 7 63/7=963/7=9好好好好 丙丙34 34 3 3 34/3=11.3334/3=11.33差差差差 一般地一般地， 單位單位單位單位人數人數人數人數席位數席位數席位數席位數每席位代表的人每席位代表的人每席位代表的人每席位代表的人 數數數數 A A A A B B B B 1 p 2 p 1 n 2 n 1 1 n p 2 2 n p 當當 2 2 1 1 n p n p ? 席位分配公平席位分配公平 但通常不一定相等，席位分配的不公平程度用以但通常不一定相等，席位分配的不公平程度用以 下標準來判斷。下標準來判斷。 準。稱為“絕對不公平”標 ) 1 2 2 1 1 n p n p ? 此值越小分配越趨于公平，但這并不是一個好的衡量標準。此值越小分配越趨于公平，但這并不是一個好的衡量標準。 單位單位單位單位人數人數人數人數 p p 席位數席位數席位數席位數 n n 每席位代每席位代每席位代每席位代 表的人數表的人數表的人數表的人數 絕對不公絕對不公絕對不公絕對不公 平標準平標準平標準平標準 A A 1201201010121212-10=212-10=2 B B 10010010101010 C C 102010201010102102102-100=2102-100=2 D D 100010001010100100 C,D 的不公平程度大為改善！的不公平程度大為改善！ 2 2 ） 相對不公平） 相對不公平 n p 表示每個席位代表的人數，總人數一定時，表示每個席位代表的人數，總人數一定時， 此值越大，代表的人數就越多，分配的席位此值越大，代表的人數就越多，分配的席位 就越少。就越少。 2 2 1 1 n p n p ? 則則 A A 吃虧吃虧 , , 或對或對 A A 是不公平的是不公平的 。。 定義“相對不公平定義“相對不公平 度”度” 則稱，若 2 2 1 1 n p n p ? 1122 12 11 ( ,) A p npn r n n p n - = 對對 A A 的相對不公平值；的相對不公平值； 則稱，若 2 2 1 1 n p n p ? 2211 12 22 ( ,) B pnp n r n n pn - = 對對 B B 的相對不公平值；的相對不公平值； 建立了衡