学生建模报告：海盗分赃问题.docVIP

海 盗 分 赃 问 题 . 问题重述： 从前,在一个小岛上有一伙海盗（共5人），他们刚刚从来往的运金船上抢得了一批金砖，经点算共计1000块。 有一个狡猾的海盗建议，不采取平均分配的原则，而是将5个人按照一种次序，依次提出分赃方法，如果第一个人提出的方法有半数或半数以上的人同意（包括提议人自己），则大家就按他的方法分配，否则就把他干掉，由下一个人继续提出方法；依次类推。前提是这些海盗都非常贪婪和精明，能够多得到一块就不会拱手让给别人，可是他们又很重江湖规矩，一旦决定了分配方法就会按照它执行，不会采用任何非常手段抢夺。到底如何分配，既可以保存自己生命，又可以获得尽可能多的财宝？ 2.模型假设：五名海盗编号，分别为A,B,C,D,E; 3.模型求解：整个过程可以归纳为下表： E 1000 0 1 0 1 D / 1000 0 1 0 C / / 999 0 1 B / / / 999 0 A / / / / 998 从本题中可以看出，在讨论编号次序时，如何将自己放在首位将直接决定所分得的黄金数量。 4．模型进一步思考： （1）.当只在半数以上（不含半数）讨论该问题时，哪个位置是最好的？ （2）.当金块数量为3，人数为6时，哪个位置是最占便宜的？ 5．问题的延伸： 从问题中我们可以看出，在这个问题中，强盗们在同意该提议时，则最后的分配结果，在某种意义上说，是绝对公平的。但是，因为他们都很聪明，所以第一个位置的争夺将是无休止的，也就是说这个问题是无结果的。再者，我们可以把金块等同于其他有待分配的实体。显然，只有给每个人赋予一定的权值求解该问题才是有意义的。 故运用席位分配问题来代替它，以给出某种较公平的分配方法。 6．说明： 设第i方人数为pi，i=1,2,……m,z总人数p= ∑pi 待分配的席位为N,理想化的席位分配结果为Ni,满足N=∑Ni。记qi=N×pi/p,显然若qi,均为整数，则应有Ni=qi.以下研究qi不全为整数的情形. Ni是N和pi 的函数，记Ni=Ni(N,p1,……pm), , 分别为qi向下取整和向上取整，则公平分配方法的理想化原则为： 原则一：[qi]-≤Ni≤ [qi]+ ,i=1,2,……m,即Ni必取 [qi]- , [qi]+ 二者之一。 原则二:Ni(N,p1,……pm) ≤ Ni(N+1,p1,……pm),i=1,2,……m,即总席位增加时Ni不应减少。 我们的初衷是为了迎合这两个原则去选择一种方案,而不是构造出某种方法后再去验证它是否满足它们。我们不得不承认我们的出发点是卑鄙的，甚至是下流的。但是正是在这种思想的指引下，在选择方案的过程中，我们欣喜地发现，我们得到的却是最最振奋人心的结果，换句话说，我们把满足这两条原则的所有分配方案都找到了。我们不妨把这种方法命名为H.W.L方法。它不仅满足这两条原则而且给出了一个非常明确的数量指标。因此，从某种意义上说，席位分配问题获得了圆满的解决。我们可以大胆的说 ，如果它能够得到大家的认可，那么我们现在使用的《数学模型》（第三版）的下一版就应该有所修正，确切地说应该是改正了。 H.W.L方法简介： 设总人数为N，组数为W,各组人数为n;待分配的席位为M。为了满足上述两条原则。我们可以这样来选择分配方案：当待分配席位数M确定后，则每组最理想的分配席位数分别为niM/N。我们来讨论前式含非整数的情况。无妨设前式的小数部分的和为T。显然0=TW，我们只须选其中T个向上取整即可。当待分配席位数为M+1时，我们从上向下取整的一个组加上一个席位且满足原则一。（我们若得不到，则只须调整上步总可得到）但是现在总席位数为M＋1的分配方案是否满足原则二是有待考证的。所以我们无妨采用倒推法。从总席位数等于总人数N一直往下推，按上述方法的逆方法，则原则二显然满足了，我们只须给出一条法则，以保证它满足原则一即可。如下表所示： 总人数 次数 1 2 3 4 5 席位 2000 1999 1998 1997 1996 1995 1 1100 1099.45 1098.9 1098.35 1097.8 1097.25 2 700 699.65 699.3 698.95 698.6 698.25 3 100 99.95 99.9 99.85 99.8 99.75 ... ... ... ... ... ... ... 说明：我们的组是按照大小变化来排列的，从上表中容易得出每一行都是等差数列，而且每组的人数越多，公差越大，也就是总席位每减少一个，则从这一组减少一个席位的几率越大。 考察ni×M/N每减少k个席位。即M减k时，前式就变为 (ni