商人过河问题数学建模中学教育中考_高等教育-大学课件.pdf

《商人过河问题数学建模中学教育中考_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《商人过河问题数学建模中学教育中考_高等教育-大学课件.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、商人过河 一、问题重述 问题一：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 次渡船上的商人数 u(k),v(k)=0,1,2;v(k)第

3、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）数学模型：k+1kS=S+kkD（-1）（1）4kkxx （2）4kkyy （3）k.kxy （4）kkxy （5）模型分析：由（2）（3）（5）可得 44kkxy 化简得 随从 y 商人 x 随从们密约在河的任一岸一旦随从的人数比商人多就杀人越货乘船渡

4、河的方案由商人决定商人们怎样才能安全过河问题二假如小船可以容人请问最多可以有几名商人各带一名随从安全过河二问题分析问题可以看做一个多步决策过程用状态变量表示某一岸的人员状况决策变量表示船上的人员情况可以找出状态随决策变化的规律问题就转换为在状态的允许变化范围内即安全渡河条件确定每一步的决策达到安全渡河的目标三问题假过河途中不会出现不可抗力的自会听从商人的调度四模型构成第次渡河前此岸的商人数第次渡河前此岸的随从数过程的状态允许状态集合第次渡船上的商人数第次渡船上的随从数过程的决策允许决策集合状态因决策而改变状态转移律求使并按转移律由到达随从数 kkxy 综合（4）可得 kkxy 和 (,)|0,

5、0,1,2,3,4kkkkkSxyxy （6）还要考虑 (,)|0,0,1,2,3,4kkkkkSxyxy （7）把（2）（3）带入（7）可得(4,4)|40,40,1,2,3,4kkkkkSxyxy 化简得 (,)|4,0,1,2,3,4kkkkkSxyxy （8）综合（6）（7）（8）式可得 满足条件的情况满足下式 (,)|0,4,0,1,2,3,4;kkkkkkkSxyxyxy （9）所以我们知道满足条件的点如上图所示：点移动由 (,)|4,0,1,2,3,4kkkkkSxyxy （8）到达 (,)|0,0,1,2,3,4kkkkkSxyxy （6）时，可以认为完成渡河。因为移动的格数小

6、于等于2，只有中心点（2，2）到（6）点和（8）点的距离为 2，所以中心点（2,2）成为渡河的关键点。当我们移动到（2,2）点时，就无法进行下去。故 4 个商人，4 个随从，船容量为 2 人时，无法安全渡河。对于问题二，我们可以建立模型为：k+1kS=S+kkD（-1）（10）kkxxM （11）随从们密约在河的任一岸一旦随从的人数比商人多就杀人越货乘船渡河的方案由商人决定商人们怎样才能安全过河问题二假如小船可以容人请问最多可以有几名商人各带一名随从安全过河二问题分析问题可以看做一个多步决策过程用状态变量表示某一岸的人员状况决策变量表示船上的人员情况可以找出状态随决策变化的规律问题就转换为在状

7、态的允许变化范围内即安全渡河条件确定每一步的决策达到安全渡河的目标三问题假过河途中不会出现不可抗力的自会听从商人的调度四模型构成第次渡河前此岸的商人数第次渡河前此岸的随从数过程的状态允许状态集合第次渡船上的商人数第次渡船上的随从数过程的决策允许决策集合状态因决策而改变状态转移律求使并按转移律由到达随从数kkyyM （12）k.kxy （13）kkxy （14）u(k),v(k)=0,1,2,3;（15）通过类似于问题一的步骤可以知道：坐标上的关键点是（3,3），最多可以五名商人带五名随从过去。需要确定五名商人带五名随从的方案可行再确定六名商人带六名随从的方案不可行 1、五名商人带五名随从的情况

8、：（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）首先不可能有三名商人先过河，两名商人一名随从过河，一名商人两名随从过河 （2）三个随从先过河（6,3），回来一个随从（6,4），过去两个随从（6,2

9、）回来一个随从（6,3），过去三个商人（3,3），此时两岸都是（3,3），由坐标法分析知，这是最接近终点的临界点，但是如果回来的时候一定是回来一个商人和一个随从，如果这一步可行，后面就进行不去 综上所述，六个商人带六个随从，小船载三个人的情况下不能渡河 结合 1、2 知，当小船最多载三个人的时候，最多五名商人各带一个随从可以过河。随从们密约在河的任一岸一旦随从的人数比商人多就杀人越货乘船渡河的方案由商人决定商人们怎样才能安全过河问题二假如小船可以容人请问最多可以有几名商人各带一名随从安全过河二问题分析问题可以看做一个多步决策过程用状态变量表示某一岸的人员状况决策变量表示船上的人员情况可以找出状

10、态随决策变化的规律问题就转换为在状态的允许变化范围内即安全渡河条件确定每一步的决策达到安全渡河的目标三问题假过河途中不会出现不可抗力的自会听从商人的调度四模型构成第次渡河前此岸的商人数第次渡河前此岸的随从数过程的状态允许状态集合第次渡船上的商人数第次渡船上的随从数过程的决策允许决策集合状态因决策而改变状态转移律求使并按转移律由到达随从数五、模型的检验与评价 由少数人的过河问题推广到了更多数人的过河问题，使得问题变得明了有规律。六、参考文献 1 章胤，2014 年燕山大学全国大学生数学建模竞赛培训 ppt，2014 年 4月 17 日 随从们密约在河的任一岸一旦随从的人数比商人多就杀人越货乘船渡河的方案由商人决定商人们怎样才能安全过河问题二假如小船可以容人请问最多可以有几名商人各带一名随从安全过河二问题分析问题可以看做一个多步决策过程用状态变量表示某一岸的人员状况决策变量表示船上的人员情况可以找出状态随决策变化的规律问题就转换为在状态的允许变化范围内即安全渡河条件确定每一步的决策达到安全渡河的目标三问题假过河途中不会出现不可抗力的自会听从商人的调度四模型构成第次渡河前此岸的商人数第次渡河前此岸的随从数过程的状态允许状态集合第次渡船上的商人数第次渡船上的随从数过程的决策允许决策集合状态因决策而改变状态转移律求使并按转移律由到达随从数