《第二章——建模方法示例》由会员分享，可在线阅读，更多相关《第二章——建模方法示例（40页珍藏版）》请在金锄头文库上搜索。
1、第二章 建模方法示例2.1 棋子颜色的变化2.1.1. 问题描述任意拿出黑白两种颜色的棋子共 n 个,排成如图 2.1.1 所示的一个圆圈.然后在两颗颜色相同的棋子中间放一颗黑色棋子,在两颗颜色不同的棋子中间放一颗白色棋子,放完后撤掉原来的棋子.再重复以上的过程,这样放下一圈后就拿走前次的一圈棋子,问这样重复进行下去各棋子的颜色会怎样变化呢?请研究不同的 n 对应的规律.2.1.2. 基本假定 若两个图可以通过旋转某个角度后重合, 则认为它们是等价的.2.1.3. 建立模型首先，为了探索棋子颜色的变化规律，我们建立棋子颜色与实数的对应关系，因为“同色为黑，不同色为白” ，正好与实数中“同号乘积
2、为正，异号乘积为负” 对应.于是建立“黑对应+1，白对应-1”的对应关系 .这样我们就可用棋子的对应“值”图2.1.1表示其颜色了.设 aj 表示第 j 个棋子的初值(+1 或-1)，j=1,2,n, 每个棋子的值就是上一步相邻的两个棋子的值之积，为观察每步的变化规律，以 n=5 为例看看 .表 2.1.1初 值 1a2a3a4a5a第 1 步 23451第 2 步 132423524125第 3 步 24a35a41a35a31a第 4 步 61354621635246124652第 5 步 50241505321043505341053发现规律了吗? 第 i 步的指数恰好是二项式 展开式的
3、系数(杨辉三角形)iab一般地,第 i 步第 j 个棋子的值为, (i,j=1,2,3,n),012(,) iiiiCCjjjjfijaa当然下标的值是关于模 n 计算的. 2.1.4. 寻找规律通过对 f(i,j)的分析便可以知道棋子颜色的变化规律, 并且说明其原理.(1)无论棋子数 n 如何,初态如何, 变化最终总是周期性的.这是因为 n 个棋子的布局只有有限种, 且每步的变化规则是相同的.从而每步的布局由上一步的布局唯一确定.(2) 无论棋子数 n 如何, 初态如何, 每一步的白子数如果大于零,则总是偶数.因为每步可以把上一步视为初态, 故只需说明从初态到第一步的变化规律.若初值中有 s
4、 个 -1, 且没有任两个相邻,则第一步就有 2s 个 -1.例如, n=8, ,其余为 1, 则2471a.123456781aaa若初值中有 s 个 -1, 且其中有 t 个相邻间隔,则第一步就有 2s-2t 个 -1.例如, n=8, , 其余为 1, 则其中有 3 个相邻间125681aa隔: . 只有 , 其余为 1.125681, , a:23456781a(3) 当 (m=1,2,)时,第 n 步全部棋子黑色,即n(,),2)fjj如果对 m 应用数学归纳法及其利用组合公式 1 112220mmmkkkjkjjCC可以证明 都是偶数, 故2(1,)mkn，(j=1,2,n)12
5、2(,) 1nCjjjnjfnjaa(4) 当 (m=1,2,)时,第 n+1 步与第 1 步等价2, (j=1,2,n)12111(1,) )nCjjjnjfnjaaaf例如 n=7 时, 第 8 步与第 1 步等价.(5) 当 (m=1,2,)时,第 n-1 步与第 1 步等价21n, (j=1,2,n)121(,) (,)nCjjjnjfaafj例如 n=9 时, 第 8 步与第 1 步等价.2.2 商人们怎样安全过河2.2.1 问题描述三名商人各带一个随从乘船渡河，现此岸有一小船只能容纳两人，由他们自己划行.随从们密谋，在河的任一岸，一旦随从比商人多，就杀人抢劫.但是如何乘船渡河的大权
6、由商人们掌握.商人们怎样才能安全过河？此类问题当然可以通过一番思考，拼揍出一个可行方案来.但是，我们现在希望能找到求解这类问题的规律性，这有利于编程和推广应用.2.2.2 模型的假设模型已理想化，不必再作假设.2.2.3 模型的构成此问题可视为一个多步决策问题，每一步就是一次渡河，每次渡河就是一次状态转移.1. 未考虑船时的安全状态设（x,y）表示此岸有 x 个商人和 y 个随从的状态，商人们安全是指在两岸都安全，故当 x=0,3 时，y=0,1,2,3 均可，而当 x=1,2 时,此岸要求 xy,对岸要求 3-x3-y, 综合即 x=y安全状态= 0,123 0,3y12x当当从而此岸在以下
7、状态时，商人们在两岸都安全 (3,3) (3,2) (3,1) (3,0) (2,2)(1,1) (0,3) (0,2) (0,1) (0,0)2. 考虑船时此岸的安全状态用（x,y,z ）表示此岸的状态，x,y 的含义同前，z 表示此岸的船数.即 z=1 时，船在此岸，z=0 时，船在对岸.此岸的安全状态有：(3,3,1) (3,2,1) (3,1,1) (2,2,1) (3,0,1) (0,3,1) (0,2,1) (1,1,1) (0,1,1)(3,2,0) (3,1,0) (2,2,0) (3,0,0) (0,3,0) (0,2,0) (1,1,0) (0,1,0) (0,0,0)2.
8、2.4 模型求解所谓求解，就是寻找此岸状态从(3,3,1)转移到(0,0,0)的方案.根据题意，状态转移时要满足下面的规则：1. z 从 1 变为 0 与从 0 变为 1 交替进行；2.当 z 从 1 变为 0 时，即船从此岸到对岸，此岸人数减少1 或 2 个；即(x,y,1)(u,v,0)时, ux, vy, u+v=x+y-1 或 u+v=x+y-23. .当 z 从 0 变为 1 时，即船从对岸到此岸，此岸人数增加1 或 2 个；即(x,y,0)(u,v,1)时, ux, vy, u+v=x+y+1 或u+v=x+y+24.不重复已出现过的状态，如(3,3,1)(3,1,0)(3,3,1
9、) ；若一状态 A 可转移到另一状态 B，则我们用一箭号将这两个状态联结起来。按照以上规则，求解过程如图 2.2.1（总人数从多到少排列）(3,3,1) (3,2,0)(3,2,1) (3,1,0)(3,1,1) (2,2,0)(2,2,1) (3,0,0)(3,0,1) (0,3,0)(0,3,1) (0,2,0)(0,2,1) (1,1,0)(1,1,1) (0,1,0)(0,1,1) (0,0,0)其解即：(3,3,1)(3,1,0) 或(2,2,0)(3,2,1) (3,0,0)(3,1,1)(1,1,0)图2.2.1(2,2,1)(0,2,0)(0,3,1) (0,1,0)(0,2,
10、1)或(1,1,1)(0,0,0)可见，有四个渡河方案，每个方案经 11 步.可解释如下:(1) 2 随从(或 1 商人 1 随从)去(7) 2 商人去(2) 1 随从(或 1 商人 )回 (8) 1 随从回(3) 2 随从去 (9) 2 随从去(4) 1 随从回 (10) 1 随从(或 1 商人 )回(5) 2 商人去 (11) 2 随从( 或 1 商人 1 随从)去(6) 1 商人 1 随从回2.2.5 平面坐标解法设 x 为商人数，y 为随从数，在 xoy 平面上作分析.如图，先把此岸的安全状态点标出.用 di 表示第 i 次状态转移，i 为奇数时，船从此岸到对岸，x, y 只能减少，不
11、能增加，且 x+ y 至多减少 2，即移向左下方，且至多移两格.i 为偶数时相反.怎样从状态(3,3)转移到(0,0)? 过程如图 2.2.2 所示.2.2.6 进一步的思考(1)若船的情况不变，则 2 名商人 2 个随从如何安全渡河？ 答案：(2,2)(1,1) 或(2,0)(2,1) (0,1)(1,1) 或(0,2)(0,0) （2）m 名商人 m 个随从(m4)能否安全渡河？答案：m 名商人 m 个随从(m4)无法安全渡河,如 m=4 时的图图 2.2.2d4 d5图 2.2.32.2.4，d7 就无法作不重复的转移.其他情况也一样.（3）一般地，m 个商人 n 个随从,m n 能否安
12、全渡河? 若能,怎样渡河？答案：当 x=0,m 时，y=0,1,2,n 均可，而当 x=1,2,m-1 时,此岸要求 xy,对岸要求 m-xn-y, 综合即 0x-y m-n安全状态=0,12.,n ,-(m)yx12.m-yx， 当， 当此时商人们必能安全渡河.若以 m=4,n=3 为例，则求解过程如图 2.2.52.3 公平的席位分配图 2.2.4图 2.2.52.3.1 问题的提出设某校有 3 个系共 200 名学生，其中甲系 100 人，乙系 60人，丙系 40 人，现要选出 20 名学生代表组成学生会，公平的办法是按学生人数的比例分配席位，即甲乙丙系分别占 10、6、4个席位.若按学
13、生人数的比例分配的席位数不是整数，就会带来一些麻烦.比如甲系 103 人，乙系 63 人，丙系 34 人，怎么分？过去的惯例是这样分配的:先按比例分配,甲、乙、丙系分别应得10.3、6.3 和 3.4 席,舍去小数部分后分别得 10、6、3 席,剩下的 1席分给“损失”最大(即小数部分最大)的丙系,于是三个系仍分别占 10、6、4 席.假定学生会的席位数增加到 21 位，按上述方法重新分配，结果如表 2.3.1 所示，甲乙丙系分别占 11、7、3 席.表 2.3.120 席的分配 21 席的分配系别 人数 比例按比例分 实际分配 按比例分 实际分配甲 103 51.5 10.3 10 10.8
14、15 11乙 63 31.5 6.3 6 6.615 7丙 34 17.0 3.4 4 3.570 3合计 200 100.0 20.0 20 21.000 21此分配结果,对丙系显然是不公平的,因为席位增加了,而丙系得到的席位反而减少了.2.3.2 符号和假设我们要解决的是这样的一个问题：某校共有 m 个系，第 i 系学生数为 ni(i=1,2,m)，校学生会共设 N 个席位.怎样才能公平地把这些席位分配给各系？显然，m，n i(i=1,2,m)应为正整数，全校学生数记为.假设每个系至少应分得一个席位（否则把其剔除） ，至i1多分得 ni(i=1,2,m)个席位，nN m.全校而言，每个席位
15、代表的学生数记为 a=n/N,第 i 系按学生数比例应分得的席位为，最后实际分得的席位数为 Ni(1 Ni ni,整数)，每aNniii个席位代表的学生数为 (i=1,2,m).iiNna2.3.3 确定“公平”的标准我们可以提出不同的标准来衡量分配方案的”公平” 的程度, 例如标准 1 要求 最小（对不同方案而言）; amxz ii标准 2 要求 最小;ii|1标准 3 要求 最大; anz i标准 4 要求 最小;mii)(122.3.4 “判别数 ”分配方法按标准 1, 可认为，a i 越大的系越吃亏，故应尽量优先照顾之. i 取整后，每个席位代表的学生数为 ()(1)iiii iana其中 ，称为判别数. 表示 i 小数部分. i 越大的系越吃iii亏，按标准 1，应优先照顾.分配方法的算法流程如图 2.3.1，其中 .i11 mmiiirN例 2.3.1 对刚才的例子用此算法重新分配, 先算 i， 再算 i 然后进行分配.图2.3.1对 i 较大的 r 个系分配席位 Ni= i+1否是开始输入 ni 与 N计算 n 与 i i 全为整数吗？计算 i 与 rNi= i输出各 Ni结束剔除已分配席位的系和席位数有为 0 的 吗?
