2014数学建模.pdf

2011 高高教教社社杯杯全全国国大大学学生生数数学学建建模模竞竞赛赛 承承 诺诺 书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮 件 网上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问 题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他 公开的资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反 竞赛规则的行为 我们将受到严肃处理 我们参赛选择的题号是 从 A B C D 中选择一项填写 我们的参赛报名号为 如果赛区设置报名号的话 所属学校 请填写完整的全名 参赛队员 打印并签名 1 2 3 指导教师或指导教师组负责人 打印并签名 日期 年 月 日 赛区评阅编号 由赛区组委会评阅前进行编号 2011 高高教教社社杯杯全全国国大大学学生生数数学学建建模模竞竞赛赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 摘摘要要 投票是生活中经常被用到的在一定时间内有效且公平的推选出一定人数的 一种决策方法 投票规则的制定与评委人数 参选人数和当选人数都紧密相关 在一定的已知投票条件下 不同的投票规则会产生不同的投票结果 因此 对不 同的投票条件制定对应的投票规则显得尤为重要 本文就是对一定投票条件下的 投票规则的制定 完善与推广 对于问题一 我们先假设每个评委投赞成票的数目相同 再用概率统计的知 识根据下面的式子 11 11 11 39 2727 139 2828 1 nn iii nn CC P iC CC 算出每个候选人被选中的概率 由 11 11 11 39 39 2727 39 26 2828 28 1 nn iii nn i CC TC CC 一次投票后能够选出的人数 当 人数小于规定需投出的人数时再进行第二次投票 再用 matlab 和 Excel 画出一次 或两次投票选出人数和需投的票数的关系 用 spss 软件分析出投票数与选出人 数的函数关系式 32 0 0090 1961 1171 484Tnnn 用非线性规划求出最优 的投票规则 当投票次数为1次并且每位评委投赞成票的数目为18票时最简便 省时 此时选出的先进工作者为12人 对于问题二 利用一中的式子 代入18算出具体值 当n1 18时 11 11 11 39 39 2727 239 26 2828 1 nn iii nn i CC P iC CC 44 94 则一次投票成功的概率P 14 73 当第二次投票成功时 第1次投票每位评委投赞成票数为1 14 第二次评委投赞成票为18 两次候 选人选出人数为12人 成功的概率为14 73 第1次投票每位评委投赞成票数为15 第二次评委投赞成票为17 两次候选 人选出人数为11人 成功的概率为11 17 第1次投票每位评委投赞成票数为16 第二次评委投赞成票为15 两次候选 人选出人数为12人 成功的概率为13 第1次投票每位评委投赞成票数为17 第二次评委投赞成票为12 两次候选 人选出人数为10人 成功的概率为23 87 对于问题三 在matlab中 随机输入每位评委投赞成票的数目 第一次选 出的人数T如果大于13则报输入错误 如果小于10则进入循环 进行第二次 投票 如果恰好在10到13之间则依次投票得出结果 对于问题四 问题五 候选人获赞成票记为1 获反对票或弃权票记为0 构造投票计分矩阵 m个候选人 n个评委 编程思路 将每位候选人得分累计与2 3n进行比较 大于2 3n时 选出该 候选人 若选出候选人数超过k 选出前k名评分高的 若选出的候选人数在 4 5k k 人之间 则投票成功 若选出的候选人数少于 4 5k 人 则对剩下的候选 人进行下一轮投票 关键词 概率统计 非线性规划 投票计分矩阵 一一 问问题题重重述述 1 1 引言 投票制度是指根据投票人的选择以选出结果的方法 多用于授奖 选出行动 计划 由电脑程式决定复杂问题的解决方案 它规定了选民表达民意的方式 通 常是以 少数服从多数 的理念为基础 票多者为胜 然而 当可供选择的方案多于两个 可能没有一个获得规定的支持票数 采 用不同的投票制度便会产生不同的结果 所以 投票制度的选取对选举结果有重 要影响 制定一个既能实现评选的公平合理 又能快速评选出当选人的有效的投 票规则是十分重要的 1 2 问题的提出 现有一些常见的投票规则 1 采用无记名方式 每位评委对每个候选人投 票 在赞成 弃权和反对中必须选一个且只能选一个 2 每个候选人获得赞成 的票数必须大于等于评委的三分之二才能当选 3 如果第一次投票选出的当选 人数小于规定人数 需要进行第二次投票 第三次投票 直至选出的人数 等于规定人数或者相差不大 但不能超过规定人数 先请解决以下问题 1 某单位要评选 10 13 名先进工作者 共 28 为候选人 39 位评委 请你 设计一个比较公平合理 简单省时的投票规则 包括投票次数 每次投票时美味 评委投赞成票的数目等 2 分析第一问中所提出的规则一次投票成功的可能性的大小 如果该规则 有第二次投票 分析两次投票成功的可能性 3 设计一个仿真实验 验证第一问中提出的投票规则 4 如规定 美味评委投赞成票的数目可以小于也可以等于但不能超过规定 的赞成票数 请设计一个投票规则 5 将你设计的投票规则推广到以下情形 m 个候选人 n 个评委 4 5 k 当选人数 k 二二 模模型型假假设设与与符符号号说说明明 1 模型的假设 1 k 个评委之间的投票是相互独立的 2 每个候选人入选的概率相同 3 选中人数随着投票次数的增加是收敛的 在有限次投票内一定会投票成功 2 符号的约定与说明 符号 符符号号的的意意义义 n1 第一次投票每位评委投赞成票数 n2 第二次投票每位评委投赞成票数 P1 i 第一次投票每个候选人获得 i 票的概率 P2 i 第一次投票每个候选人选中的概率 T 第一次投票选中人数 P3 i 第二次投票每个候选人选中的概率 T2 第二次投票选中人数 三三 模模型型建建立立与与求求解解 1 问问题题分分析析 要设计公平合理的投票规则 就是要保证每个候选人获得的赞成票数必须大 于等于评委数的三分之二 如果第一次投票选出的人数远小于规定人数 需要进 行第二次 第三次投票 直至选出人数等于规定人数或相差不大并且不超过规 定人数 要设计简便省时的投票规则 就是要使投票次数少并且评委投票数少才省时 及要进行非线性规划 找到简便省时时的投票次数和评委投票数 问问题题求求解解 1 第一次投票 每个评委可投 n1票 则每个候选人获得 i 票的概率为 11 11 11 39 2727 139 2828 1 nn iii nn CC P iC CC 候选人要当选 获得的赞成票数必须大于或等于评委数的三分之二 即 26 则 每个候选人当选的概率为 11 11 11 39 39 2727 239 26 2828 1 nn iii nn i CC P iC CC 则候选人可以选中的人数为 11 11 11 39 39 2727 39 26 2828 28 1 nn iii nn i CC TC CC 在 matlab 中画出第一次投票候选人选中人数与评委投赞成票数的关系如图 所示 051015202530 0 5 10 15 20 25 30 评委投赞成票数 候选人选中人数 投票一次 图 1 第一次投票候选人选中人数与评委投赞成票数对应曲线 由图 1 可以得出候选人选中人数与评委投赞成票数的关系如表 1 表 1 第一次投赞成票数和候选人当选人数对应关系 第第一一次次 投投赞赞成成 票票数数 1 14 15 16 17 18 19 20 21 22 25 26 28 第第一一次次 候候选选人人 当当选选人人 数数 取取整整 0 1 4 7 12 17 22 25 27 28 用SPSS软件分析投赞成票数和候选人当选人数关系 表2 投赞成票和候选人选中人数关系 M Mo od de el l S Su um mm ma ar ry y a an nd d P Pa ar ra am me et te er r E Es st ti im ma at te es s Dependent Variable VAR00001 Equation Model Summary Parameter Estimates R Square F df1 df2 Sig Constant b1 b2 b3 Cubic 943 71 535 3 13 000 1 484 1 117 196 009 Exponenti al 817 67 114 1 15 000 2 126E 19 3 177 The independent variable is VAR00002 用立方曲线对数据进行拟合 图2 立方曲线对数据进行拟合 可以看出 当第一次投赞成票数小于 18 票时 投赞成票数和候选人当选人 数关系近似于立方曲线 即 32 0 0090 1961 1171 484Tnnn 由表1可知 第一次投票每位评委投赞成票必须小于19票 否则选出的先 进工作者数将超过规定的10 13名 当每位评委投赞成票数等于18票时 选出的先进工作者为12人 满足题目要 求 故此时一次投票就可以成功 当每位评委投赞成票数小于 18 票时 选出的先进工作者远小于 10 13 名 此 时要进行第二次投票 2 第二次投票 只有第一次评委投赞成票数小于 18 票时 即第一次投票选出的人数 T 取 0 1 4 7 由表 1 知 才进行第 2 次投票 第二次投票时 每位评委可投 n2票 第一次投票评选出的先进工作者数为 T 则第二次每个候选人选中的概率为 22 22 11 39 39 2727 339 26 2828 28 1 nn jjj TT nn j TT CC P iTC CC 用 matlab 编程 得出当第一次投票选出人数为 T T 取 0 1 4 7 时 第二次 投票选出人数与评委投赞成票的关系如表 3 表 3 第二次投票选出人数与评委投赞成票的关系 第二次投第一次投票 第一次投票第一次投票第一次投票 赞成票数选出人数0人选出人数1人 选出人数4人选出人数7人 13 41E 278 33E 271 49E 253 88E 24 21 43E 193 43E 195 74E 181 38E 16 33 32E 157 81E 151 22E 132 66E 12 43 55E 128 16E 121 18E 102 32E 09 56 93E 101 56E 092 07E 083 64E 07 64 58E 081 00E 071 22E 061 89E 05 71 42E 063 03E 063 34E 050 00044962 82 52E 055 22E 050 000513850 0059186 9 0 000288680 000578090 00503890 048646 100 00232150 00448520 0341510 27013 110 0139140 0258430 16931 069 120 0648610 115340 639023 1283 130 242620 411161 89016 9596 140 745531 1984 475812 066 151 91542 90258 632616 809 164 17115 927513 78919 719 177 785610 32318 62620 788 1812 58415 51321 93220 986 1917 81420 41723 4821 2022 41224 0323 92921 2125 58826 0223 99621 2227 23826 78824 2327 84226 97524 2427 98226 99924 2527 99927 262827 272827 2828 在 excel 中拟合出 4 组数据的曲线 两次投票 0 5 10 15 20 25 30 051015202530 第二次评委投赞成票数 第二次投票选出人数 系列1 系列2 系列3 系列4 图 3 第二次投票选出人数与评委投赞成票的关系 第二次投票成功 就是要使第一次和第二次投票选中人数在 10 13 之间 表 4 两次投票成功的情况 二二次次 第第一一次次评评委委投投 投投票票选选中中人人数数 赞赞成成票票数数 取取整整 第第二二次次评评委委 投投赞赞成成票票数数 1 14 第第 一一 次次 投投 票票 选选 出出 人人 数数 0 人人 15 第第 一一 次次 投投 票票 选选 出出 人人 数数 1 人人 16 第第 一一 次次 投投 票票 选选 出出 人人 数数 4 人人 17 第第 一一 次次 投投 票票 选选 出出 人人 数数 7 人人 12 10 15 12 17 11 18 12 由题目要求可知 要评选出 10 13 名先进工作者 1 若投票 1 次成功 从表 1 可知 当每位评委投赞成票数为 18 票时 候选人当 选人数为 12 人 2 若投票 2 次成功 从表 3 可知 有 17 种情况 第 1 次投票每位评委投赞成票数为 1 14 第二次评委投赞成票为 18 两次候 选人选出人数为 12 人 第 1 次投票每位评委投赞成票数为 15 第二次评委投赞成票为 17 两次候选 人选出人数为 11 人 第 1 次投票每位评委投赞成票数为 16 第二次评委投赞成票为 15 两次候选 人选出人数为 12 人 第 1 次投票每位评委投赞成票数为 17 第二次评委投赞成票为 12 两次候选 人选出人数为 10 人 考虑到投票规则要简便省时 则要求投票次数少并且每位评委投票数少 可以 看出 1 次投票成功评委投赞成票数为 18 票 2 次投票成功评委投赞成票数最少 为 19 票 从简便省时考虑 投票 1 次比较简便省时 这里讨论投票 2 次时的投票数 要进行非线性规划 找到简便省时的评委投 票数 再与投票 1 次的评委投票数进行比较 min n n2 s t 1 n 17 1 n2 28 T T 0 009n3 0 196n2 1 117n 1 484 用 Matlab 求解 n 18 n2 0 用非线性规划求出最优的投票规则 当投票次数为 1 次并且每位评委投赞成 票的数目为 18 票时最简便省时 此时选出的先进工作者为 12 人 2 问问题题求求解解 由 1 可知 当一次投票成功时 每位评委投赞成票数为 18 票 每个候选人选中的 概率为 11 11 11 39 39 2727 239 26 2828 1 nn iii nn i CC P iC CC 当 n1 18 时 11 11 11 39 39 2727 239 26 2828 1 nn iii nn i CC P iC CC 44 94 则一次投票成功的概率 121216 28 0 4494 0 5506 14 73 PC 当第二次投票成功时 第1次投票每位评委投赞成票数为1 14 第二次评委投赞成票为18 两次候 选人选出人数为12人 成功的概率为 121216 28 0 4494 0 5506 14 73 C 第1次投票每位评委投赞成票数为15 第二次评委投赞成票为17 两次候选 人选出人数为11人 成功的概率为 127101017 2827 1 0 068 0 932 0 3823 0 6177 11 17 CC 第1次投票每位评委投赞成票数为16 第二次评委投赞成票为15 两次候选 人选出人数为12人 成功的概率为 44248816 2824 1 0 149 0 851 0 3597 0 6403 13 CC 第 1 次投票每位评委投赞成票数为 17 第二次评委投赞成票为 12 两次候选 人选出人数为 10 人 成功的概率为 77213318 2821 1 0 278 0 632 0 149 0 851 23 87 CC 3 在在 matlab 中中进进行行实实验验 从屏幕中输入第一次评委投赞成票数 计算该次投票选出的先进工作者人数 如果评出的先进工作者人数少于10人 则进行第二次投票 从屏幕输入第二次 评委投赞成票数 计算该次投票选出的先进工作者人数 如果评出的先进工作者 人数大于13人 则退出程序 如果评出的先进工作者人数在10 13人之间 停 止投票 即投票成功 当输入第一次评委投赞成票数为18票时 当输入第一次评委投赞成票数超过18票时 当输入第一次评委投赞成票数少于 18 票且二次投票成功时 当输入第一次评委投赞成票数少于 18 票且二次投票不成功时 4 问问题题求求解解 投票规则 设候选人的集合为 1228 Mm mm 第 i 个评委对第 k 个候选人投票记为 i k m 假设某候选人获赞成票记为 1 获反对票和弃权票均记为 0 即 1 候选人获赞成票 mi 0 候选人获反对票和弃权票 对每个候选人获得的票数累积计分并统计 由此构造投票计分矩阵为 139 11 139 2828 mm A mm K MOM L 则 39 个评委对第 k 个候选人的评分累计为 39 1 i k i Rm 当候选人评分大于 26 时 选出该候选人 若选出候选人数超过 13 选出前 13 名评分高的 若选出的候选人数在 10 13 人之间 则投票成功 若选出的候 选人数少于 10 人 则对剩下的候选人进行下一轮投票 在 matlab 中进行一次仿真实验 随机生成投票计分矩阵 39 个评委对第 k 个 候选人的评分累计为 13 15 15 16 17 17 17 18 18 19 19 20 20 21 21 21 22 22 22 22 22 22 22 22 23 23 23 24 27 5 问问题题求求解解 有 m 个候选人 n 个评委 4 5 k 当选人数 k 由第 4 问可类推 候选人的集合为 12 m Mm mm 第 i 个评委对第 k 个候选人投票记为 i k m 假设某候选人获赞成票记为 1 获反对票和弃权票均记为 0 即 1 候选人获赞成票 mi 0 候选人获反对票和弃权票 对每个候选人获得的票数累积计分并统计 由此构造投票计分矩阵为 1 11 1 n n mm mm A mm K MOM L 则 39 个评委对第 k 个候选人的评分累计为 1 n i k i Rm 当候选人评分大于 26 时 选出该候选人 若选出候选人数超过 13 选出前 13 名评分高的 若选出的候选人数在 10 13 人之间 则投票成功 若选出的候选人 数少于 10 人 则对剩下的候选人进行下一轮投票 四四 模模型型的的优优缺缺点点及及改改进进方方向向 1 模型的优点 1 投票公平合理 简单省时 2 问题一中第一次投票时 选中人数与评委投赞成票数用 SPSS 拟合 操作 简单 3 问题一的非线性规划可得到最优投票规则 4 模型易于推广 2 模型的缺点 1 模型只讨论了最多两次投票的情况 2 问题三中仿真实验输入的为每位评委投赞成票数 没有输入评委的具体投 票情况 3 模型的改进方向 讨论多次投票的情况 五五 参参考考文文献献 1 张文彤主编 SPSS 统计分析高级教程 M 北京 高等教育出版社 2004 2 姜启源 谢金星 叶俊 数学模型 第三版 M 北京 高等教育出版社 2003 3 吴松 常用投票规则比较和其防操纵性分析 硕士论文 2005 4 文益民 基于可信多数投票的快速概念漂移检测 湖南大学学报 2010 附附录录 附附录录 1 第第一一次次投投票票候候选选人人选选中中人人数数与与评评委委投投赞赞成成票票数数图图形形绘绘制制 clear all t 1 28 for n 1 28 for i 26 39 p i 25 nchoosek 39 i nchoosek 27 n 1 nchoosek 28 n i 1 nchoo sek 27 n 1 nchoosek 28 n 39 i end P n sum p 候选人选中的概率 T n 28 P n end plot t T xlabel 评委投赞成票数 ylabel 候选人选中人数 title 投票一次 grid 附附录录 2 第第二二次次投投票票候候选选人人选选中中人人数数与与评评委委投投赞赞成成票票数数关关系系 clear all clc n input Please input the number of the first votes T input Please input the number of the first