数学模型第二章1.doc

第二章 建模方法示例2.1棋子颜色的变化2.1.1. 问题描述 任意拿出黑白棋子共n个,排成一圈.然后在两颗颜色相同的棋子中间放一颗黑色棋子,在两颗颜色不同的棋子中间放一颗白色棋子,放完后撤掉原来的棋子.再重复以上的过程.问这样进行下去各棋子的颜色会怎样变化呢? 图2.1.12.1.2. 基本假定 若两个图可以通过旋转某个角度后重合, 则认为它们是等价的.2.1.3. 建立模型首先，为了探索棋子颜色的变化规律，我们建立棋子颜色与实数的对应关系，因为“同色为黑，不同色为白”，正好与实数中“同号乘积为正，异号乘积为负” 对应.于是建立“黑对应+1，白对应-1”的对应关系.这样我们就可用棋子的对应“值”表示其颜色了.设aj表示第j个棋子的初值(+1或-1)，j=1,2,n, 每个棋子的值就是上一步相邻的两个棋子的值之积，为观察每步的变化规律，以n=5为例看看.表 2.1.1初值第0步第1步第2步第3步第4步第5步规律：（1）第j列首个a的下标为j；（2）每项a的下标按1递增（mod n）；（3）第i步每项共有i+1个a；（4）第i步每项的指数是杨辉三角形的第i+1行.杨辉三角形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 7 21 35 35 21 7 11 8 28 56 70 56 28 8 1模型：第i步第j个棋子的值为当然下标的值是按mod n计算的. 2.1.4. 两个重要的性质 (一) 当时,第n步全部棋子黑色,即 .已知有组合公式从而有这可以证明：都是偶数故 ，(j=1,2,n)(二) 每一步白子数总是偶数.情形一，有s个“-1”且没有任两个相邻，即每个“-1”的两旁都是“+1”，则在下一步，每一个“-1”变出两个“-1”，共有2s个“-1”. 例s=6如下-1-1-1-1-1-1+1+1+1+1-1-1-1-1-1-1-1-1-1+1+1+1+1-1-1-1-1-1-1情形二，有s个“-1”且有t个“-1”与“-1”间的间隔，则在下一步，由于相邻的“-1”间不插入“-1”，故可把相邻的几个“-1”视为一个“-1”，即化为有s-t个“-1”的情形一.2.2 商人们怎样安全过河2.2 安全过河问题2.2.1问题描述三名商人各带一个随从乘船渡河，现此岸有一小船只能容纳两人，由他们自己划行.随从们密谋，在河的任一岸，一旦随从比商人多，就杀人抢劫.但是如何乘船渡河的大权由商人们掌握.商人们怎样才能安全过河？此类问题当然可以通过一番思考，拼揍出一个可行方案来.但是，我们现在希望能找到求解这类问题的规律性，这有利于编程和推广应用.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安全状态=从而此岸在以下状态时，商人们在两岸都安全 (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.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)；若一状态A可转移到另一状态B，则我们用一箭号将这两个状态联结起来。按照以上规则，求解过程如图2.2.1（总人数从多到少排列）图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)(0,2,0)(0,3,1)(0,1,0)(0,2,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只能减少，不能增加，且x+ y至多减少2，即移向左下方，且至多移两格.i为偶数时相反.怎样从状态(3,3)转移到(0,0)? 过程如图2.2.2所示.图2.2.22.2.6进一步的思考(1)若船的情况不变，则2名商人和2个随从如何安全渡河？ 答案：(2,2)(1,1) 或(2,0)(2,1)(0,1)(1,1) 或(0,2)(0,0) d4d5图2.2.3（2）m名商人m个随从(m4)能否安全渡河？答案：m名商人m个随从(m4)无法安全渡河。如m=4时的图2.2.4，d7就无法作不重复的转移.其他情况也一样.图2.2.4（3）一般地，m个商人n个随从,mn能否安全渡河? 若能,怎样渡河？答案：当x=0,m时，y=0,1,2,n均可，而当x=1,2,m-1时,此岸要求xy,对岸要求m-xn-y,综合即0x-ym-n安全状态=此时商人们必能安全渡河.若以m=5, n=3为例，则安全点的布局：图2.2.5d1d2d4d3d5d6d8d7d13d9d10d11d12(0,0)(1,1)(5,3)(3,1)跳转过程如下：一般此过程实际上分为三大步：（1）从(m,n)到(m-n+1,1),4步一周，走n-1周;（2）从(m-n+1,1)到(1,1),2步一周，走m-n周;（3）从(1,1)到(0,0),走1步。故得结论：时必能安全过河，且总步数：2.3公平的席位分配2.3.1问题的提出设某校有3个系共200名学生，其中甲系100人，乙系60人，丙系40人，现要选出20名学生代表组成学生会，公平的办法是按学生人数的比例分配席位，即甲乙丙系分别占10、6、4个席位.若按学生人数的比例分配的席位数不是整数，就会带来一些麻烦.比如甲系103人，乙系63人，丙系34人，怎么分？Hamilton分配方法：（1）各方按人数比例算出应得席位数(通常带小数);（2）各方都放弃小数部分，只取整数部分；（3）把剩余席位分给小数部分较大的各方(每方至多添1席)若按Hamilton方法分配,则甲、乙、丙系分别应得10.3、6.3和3.4席,舍去小数部分后分别得10、6、3席,剩下的1席分给小数部分最大的丙系,于是三个系仍分别占10、6、4席.假定学生会的席位数增加到21位，按上述方法重新分配，结果甲乙丙系分别占11、7、3席.系别人数比例20席的分配21席的分配按比例分实际分配按比例分实际分配甲10351.510.31010.81511乙6331.56.366.6157丙3417.03.443.5703合计200100.020.02021.00021此分配结果, 对丙系显然是不公平的,因为席位增加了,而丙系得到的席位反而减少了.Alabama悖论：当总席位数增加后，反而某一方分到的席位数减少.2.3.2符号和假设要解决的问题：某校共有m个系，第i系学生数为ni(i=1,2,m)，校学生会共设N个席位.怎样才能公平地把这些席位分配给各系？ - 总人数；N - 席位总数； - 全校平均每个席位代表的人数；-第i方按人数比例应分得的席位数(通常带小数)；Ni -第i方实际分得的席位数(整数)； - 一个分配方案； - 第i方平均每个席位代表的人数；注：越大的一方就越吃亏，越小的一方就越占便宜.是度量分配“公平”程度的最重要指标.假设参与分配的每一方至少分到一个席位.2.3.3确定“公平”的标准可以提出不同的标准来衡量分配方案的”公平”的程度, 例如标准1 要求最小（对不同方案而言）;标准2 要求最小;标准3 要求最大;标准4 要求最小.为了帮助理解标准1与标准3，看下例方案1方案2方案335.643.748.748.242.337.838.653.142.353.538.238.553.553.148.735.638.237.8按标准1，认为方案3最公平，其思想是：别让最吃亏一方太亏；按标准3，认为方案2最公平，其思想是：别让最占便宜一方占太多便宜.标准2与标准4的思想是：认各尽量靠近a,减少它们的差异.2.3.4 “判别数”分配方法标准1认为ai越大的系越吃亏，故应尽量优先照顾之.其中，称为判别数.表示i小数部分.i越大的系越吃亏，按标准1，应优先照顾.分配方法的算法流程如图2.3.1，其中.图2.3.1对i较大的r个系分配席位Ni=i+1否是开始输入ni与N计算n与ii全为整数吗？计算i与rNi=i输出各Ni结束剔除已分配席位的系和席位数有为0的吗?若有k个=0,则对应的k个Ni=1分配完了吗?是是否否例2.3.1对刚才的例子用此算法重新分配, 先算i， 再算i 然后进行分配.系别人数21席的分配iiNi甲10310.8150.081510乙636.6150.10257丙343.5700.19004合计20021.00021r=21-(10+6+3)=2，且3与2较大N2=6+1=7, N3=3+1=4这样已分出11席，剩余10席自然给甲系， 即N1=10.例2.3.2 N=25, n=2500，具体数据如下表.第一轮计算 系别人数ii一110511.050.0045二6486.480.0800三3623.620.2067四2482.480.2400五1371.370.3700合计250025r =25-(11+6+3+2+1)=2，且5与4较大N5=1+1=2, N4=2+1=3分出5席，剩余20席.第二轮计算 系别人数ii一110510.44920.04492二6486.12770.02128三3623.42310.14103合计211520r=20-(10+6+3)=1，且3较大N3=3+1=4分出4席，剩余16席.第三轮计算 系别人数ii一110510.0860.0086二6485.9140.1828合计175316r=16-(10+5)=1，且2较大N2=5+1=6分出6席，剩余10席. 自然给一系，即N1=10.即各系席位数分别为：10，6，4，3，2.可以证明，用此分配法，当N增加时，各Ni不会减少.2.3.5、进一步的讨论（1） 更公平的标准-最小极差法要求最小,令,.则相应的数学模型为： （*）例1 m=5,N=25,n=2476,具体数据如下所示.系nii最小极差法判别数法NiaiNiai一3393.4233113.00484.75二1131.1411113.00256.50三6696.755795.576111.50四8558.633995.008106.88五5005.0485100.005100.00极差18.0055.00从表可见，用检验数法求得的解，极差为55. 而用最小极差法求得的解，极差只有18，“公平度”大大提高。（2）“非完全分配法”前面讨论的都是“要把N个席位全部分配出去，如何分配更公平”这样的问题.我们不妨把这种分配法称为“完全分配法”.但有些情况，若采用“完全分配法”，则无论怎样分，都总显得不公平.例如，要把5个席位全部分给甲乙两个学生人数相同的系，怎样分？甲2席乙3席不妥，甲3席乙2席也不公平.显然最公平的分配方法应是舍弃1席后，各分2席.我们把这种为了追求“最公平”而舍弃一些席位的分配方法称为“非完全分配法”。“非完全分配法”的数学模型可由模型（*）稍加改动就得，即模型（*）. （*）模型（*）必有最优解，因为Ni=1(i=1,2,m)就是一个可行解，且Ni的取值只有有限个.采用“非完全分配法”，“公平度”往往会有很大的改善.如对于例1的数据可得下表.系nii模型(*)模型(*)NiaiNiai一3393.4233113.003113.00二1131.1411113.001113.00三6696.755795.576111.50四8558.633995.008106.88五5005.0485100.005100.00极差18.0013.00舍弃2席后，分配出23席，此时a=107.65，由表最后一列可见，ai的集中度大大提高，ai的极差从18缩小到13.2.4 作业安排一 问题有多项作业要做，每项给定了完成期限，若无法全部按时完成，则应怎样安排，使能按时完成的作业数最多。例1. 设某学生有6项作业要完成，如下表，第一行列出课程名称，第二行是各项作业完成的限期（从现在算起，以天为单位），第三行是完成各项作业所需时间（以天为单位），试安排这些作业，使能按期完成的项目最多。课程数学经济学物理化学英语文学限期31019243648需时21215101518二假设设共有n项作业要完成，第j项的完成期限是Tj(j=1,2,n) (序数)，且不妨设。第j项的需耗用时间为tj(j=1,2,n). 三Hodgson算法以下给出求解作业安排问题的Hodgson算法流程，其中m-已检查过的作业数，k-在已检查过的作业中，能按时完成的作业数，T0-完成k项作业共需时间，it-能按时完成的作业序号。开始输入n,tj,Tj(j=1,2,n); m=0,k=0,T0=0m=n?m=m+1k=k+1, ik=m+1T0= T0+tm+1结束输出令删除第i0项，调整it.YesYesNoNo四例1求解过程(0) n=6, m=0, k=0, T0=0;(1) T0+t1=2T2=10, ,i0=2, 删去第2项，T0=T0+t2-t2=2, m=m+1=2;(3) T0+t3=2+15=17T4=24, ,i0=3, 删去第3项，调整i2=4, T0=T0+t4-t3=12, m=m+1=4;(5) T0+t5=12+15=27T5=36, k=k+1=3, i3= m+1=5, T0=T0+t5=27, m=m+1=5;(6) T0+t6=27+18=45T6=48, k=k+1=4, i4= m+1=6, T0=T0+t6=45, m=m+1=6.输出： 即按照数学、化学、英语、文学的顺序，可以按时完成四项作业。共需时间45天。五0-1规划模型这题其实就是要决定各项作业做与不做，故可用0-1规划来描述。设f表示能完成的作业总数，则模型为对于例1，模型为最优解为 x=(1,0,0,1,1,1).2.5 动物的身长与体重2.5.1问题四足动物的躯干与其体重之间有什么关系？此问题有一定的实际意义，比如在生猪收购站，工作人员希望能从生猪的身长估计出它的体重.类比方法:假如我们直接研究现象A的规律比较困难，但又发现现象B与现象A十分类似且有成熟的结果，于是我们就可以借用现象B的结果来研究现象A的规律，这是研究方法的一种捷径.2.5.2模型的构成图2.5.1对此问题如果陷入生物学复杂的生理结构的研究