最混合整数规划问题 悬赏100分

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

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

告诉我思路就成

图见：http://www.eng.marmara.edu.tr/courses/ie/ie628/hw9.htm

由于要达到绝对多数,也就是2/3,所以如果按照分成5个选区的办法实行,就至少要拿下4个选区.
下面对分区图进行处理,将选票达不到1/2的相邻选区进行合并,我们可以看见一共有3块选区达不到1/2:
2,12+14,(6+7+8+11).
我们要通过组合消除其中两个,只留下一个,因为(6+7+8+11)缺额太大,所以放弃该选区.
下面就很容易了,2的缺额为10000,只要和总超额为10000以上的选区合并即可,方案为:(1+2+5)或(1+2+3+5)
我们将12和14分开,然后分别组合(12+9)和(14+13)就能解决.
10只要和周围任一个组合就可以,这样无论分成6个区还是5个,都只有1个区败选,其他的都胜利.
不知道可不可以,我的本事就这么点啦,呵呵.