资源描述：
《商人过河问题数学建模.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、商人过河问题数学建模作业1、2:商人过河一、重述问题一:4个商人带着4个随从过河,过河的工具只有一艘小船,只能同时载两个人过河,包括划船的人。随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货。乘船渡河的方案由商人决定。商人们怎样才能安全过河?问题二:假如小船可以容3人,请问最多可以有几名商人各带一名随从安全过河。二、分析问题可以瞧做一个多步决策过程。每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。用状态变量表示某一岸的人员状况,决策变量表示船上的人员情况,可以找出状态随决策变化的规律。问题就转换为在
2、状态的允许变化范围内(即安全渡河条件),确定每一步的决策,达到安全渡河的目标。三.假1、过河途中不会出现不可抗力的自然因素。2、当随从人数大于商人数时,随从们不会改变杀人的计划。3.船的质量很好,在多次满载的情况下也能正常运作。4、随从会听从商人的调度。四、模型构成x(k)~第k次渡河前此岸的商人数x(k),y(k)=0,1,2,3,4;y(k)~第k次渡河前此岸的随从数k=1,2,⋯、、s(k)=[x(k),y(k)]~程的状S~允状集合S={(x,y)x=0,y=0,1,2,3,4;x=4,y=0,1,2,3,4;x=y=1,2,3}u(k)~第k次
3、渡船上的商人数u(k),v(k)=0,1,2;v(k)~第k次渡船上的随从数k=1,2⋯、、商人过河问题数学建模d(k)=(u(k),v(k))~程的决策D~允决策集合D={u,vu+v=1,2,u,v=0,1,2}状因决策而改s(k+1)=s(k)+(-1)^k*d(k)~状移律求d(k)D(k=1,2,⋯、n),使s(k)S并按移律s(k+1)=s(k)+(-1)^k*d(k)由(4,4)到达(0,0)随从y商人x数学模型:k(1)Sk+1=Sk+（-1）Dkxkxk'4(2)ykyk'4(3)xk.yk(4)xk'yk'(5)模型分析:由(2)(3)(5)
4、可得4xk4yk化简得xkyk商人过河问题数学建模综合(4)可得xkyk与Sk(xk,yk)
5、xk0,yk0,1,2,3,4(6)还要考虑S'(x',yk')
6、x'0,yk'0,1,2,3,4(7)kkk把(2)(3)带入(7)可得Sk(4xk,4yk)
7、4xk0,4yk0,1,2,3,4化简得Sk(xk,yk)
8、xk4,yk0,1,2,3,4(8)综合(6)(7)(8)式可得满足条件的情况满足下式Sk(xk,yk)
9、xk0,4,yk0,1,2,3,4;xkyk(9)所以我们知道满足条件的点如上图所示:点移动由Sk(xk,yk)
10、xk4,yk0,1,2,3,4(8)到
11、达S(x,y)
12、xk0,y0,1,2,3,4(6)kkkk时,可以认为完成渡河。因为移动的格数小于等于2,只有中心点(2,2)到(6)点与(8)点的距离为2,所以中心点(2,2)成为渡河的关键点。当我们移动到(2,2)点时,就无法进行下去。故4个商人,4个随从,船容量为2人时,无法安全渡河。对于问题二,我们可以建立模型为:k(10)Sk+1=Sk+（-1）Dkxkxk'M(11)ykyk'M(12)xk.yk(13)商人过河问题数学建模xk'yk'(14)u(k),v(k)=0,1,2,3;(15)通过类似于问题一的步骤可以知道:坐标上的关键点就是(3,3),最多可以
13、五名商人带五名随从过去。需要确定五名商人带五名随从的方案可行再确定六名商人带六名随从的方案不可行1、五名商人带五名随从的情况:(1)首先不可能有三名商人先过河,两名商人一名随从过河,一名商人两名随从过河(2)三个随从先过河(5,2),回来一个随从(5,3),过去两个随从(5,1)回来一个随从(5,2),再过去三个商人(2,2),回来一个商人一个随从(3,3),再过去三个商人(0,3),回来一个随从(0,4),过去三个随从(0,1),回来一个随从(0,2)再过去两个随从(0,0)综上可知:五名商人带五名随从,小船可以载三个人可以过河2、六名商人带六名随从的情况:(1)首
14、先不可能有三名商人先过河,两名商人一名随从过河,一名商人两名随从过河(2)三个随从先过河(6,3),回来一个随从(6,4),过去两个随从(6,2)回来一个随从(6,3),过去三个商人(3,3),此时两岸都就是(3,3),由坐标法分析知,这就是最接近终点的临界点,但就是如果回来的时候一定就是回来一个商人与一个随从,如果这一步可行,后面就进行不去综上所述,六个商人带六个随从,小船载三个人的情况下不能渡河结合1、2知,当小船最多载三个人的时候,最多五名商人各带一个随从可以过河。五、模型的检验与评价由少数人的过河问题推广到了更多数人的过河问题,使得问题变得明
