注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

数模爱好者

这里是湖南大学数学建模协会博客,谢谢大家的访问!欢迎广大会员提出你们的想法!!

 
 
 

日志

 
 

首届华中赛B题  

2008-05-30 23:37:23|  分类: 建模赛题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

选 区 划 分

在—个遥远的国家,Sark Mevo 所领导的政党最终击败了Reguel Tekris王子领导的联合党派。Mevo希望巩固他在首都地区的席位。首都由14个街区组成,这些街区将分组为多个选区。下图是首都地区的示意图。在图中用数字1到14对这些街区进行了编号。每个街区中的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民都必须投票,且选举胜出方必须得到绝对多数选票。一个选区可以由多个相邻的街区组成,且选区内总选民数应在30,000到100,000之间。如果两个街区不相邻,例如12和13,则它们不能组成一个选区。如果某个街区选民人数不少于50,000,则允许此街区单独作为一个选区。但是由于Mevo本人就居住在街区10内,因此迫于舆论压力,他不能将这个街区单独作为一个选区。

    请设计出一个将首都划分为5个选区的方案,以使Mevo得到的席位数最多。如果这样做有困难,可以尝试划分为6个选区。
                                                                        参 考 解 答

一、模型建立

1、分析  我们所考虑的问题是一个划分问题:给定了所有可能存在的选区集合,我们需要选择其中的一个子集,以使每个街区都出现且只出现在其中一个选区中。

假设构成一个选区的街区需两两相邻。首先设计算法,按题目要求计算出所有可能的选区 :{1,2},{1,5},{1,2,5}{2},{2,3},{2,5},{2,3,5},{3,4},{3,5},{4},{4,5},{5,6},{5,10},{6,7},{6,8},{6,7,8},{7,8},{7,9},{7,8,9},{8,9},{8,10},{8,11},{8,9,11},{8,10,11},{9,11},{9,12},{10,11},{10,13},{11,12},{11,13},{12},{12,14},{13,14},这33个可能的选区依次记为第1,2,……,33个选区。

选区i内投给Mevo的选票数超过该选区总票数的一半,

否则

1,

0,

 

2、模型  设ai =  

 

街区j位于选区i中,i=1,2,……,33;j=1,2,……,

否则

1,

0,

 

i=1,2,……,33;bij=  

在划分方案中含选区i,i=1,2,……,33。

否则

1,

0,

 

14;c表示选区的划分数;xi=

假设某候选人获得一个选区总票数的一半,即可获得该区的席位,则目标为max aixi,即最大化所选择的划分方案中Mevo能够获得的席位数。选区数的约束可表示为 xi=c;每个街区只被包含在一个选区中,此约束条件可表示为 bijxi=1,j=1,2,……,14,故可建立如下模型

max aixi

s.t.

 

               bijxi=1   j=1,2,……,14

                                 xi=c

                                xi=0或1,i=1,2……,33

 

二、模型求解

1、计算   首先根据题目所给数据计算出ai,bij,i=1,2,……,33;j=1,2,……,14

再利用LINDO软件包,编程计算。

2、结果  当c=5时,此问题无解。实际上由于总人口为540000人,而每个选区人数都不能超过100000,显然至少需要划分6个选区。当c=6时,得到的划分方案为:{1,2,5},{3,4},{6,7,8},{9,12},{10,11},{13,14},除了选区{6,7,8}外,在其他选区中Mevo均获得了多数票。

 

 

 

  评论这张
 
阅读(113)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018