商人过河问题.doc

《商人过河问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、商人过河数学建模论文 摘要 4个商人带着4个仆人过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，问应如何设计过河顺序才能让所有人都安全地过到河的另一边。 经典的商人过河问题可以看做一个多步决策过程。每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员情况，可以找出状态随决策变化的规律。问题就转换为在状态的允许变化范围内（即安全渡河条

2、件），确定每一步的决策，达到安全渡河的目标。 分别建立两个模型：模型一采用穷举法，对各种过河的方案一一列举，然后根据商人们要安全过河为前提对各种进行了列举，经过层层筛选，最终求出商人安全的方案。模型二采用图解法，利用图示表示说明该题的解法。 关键词：穷举法  多步决策  图解法  安全渡河 一、问题提出 4个商人带着4个仆人过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，问应如何设计过河顺序才能让所有安全过河。二、模型的假设和符号说明⑴模

3、型假设： ①过河途中不会出现不可抗力的自然因素 ②当仆人数大于商人数时，随从们不会改变杀人的计划 ③船很结实，不会发生任何的意外（2）符号的说明（A,B）表示商人和仆人的个数，A表示商人，B表示仆人三、模型的建立模型一(穷举法）： 此岸船彼岸（4,4）（0,0）（0,0）（3,3）（1,1,）（0,0）（3,3）（1,0）（0,1）（3,2）（1,1）（0,1）（3,2）（0,1）（1,1）（2,2）（1,1）（1,1）（2.2）（0,1）（2,1）（2,2,）（0,0）（2,2）这样如果商人回去，彼岸的商人就比仆人多了，如果仆人过去，此岸

4、的仆人就会比商人多了。所以无法达到（0,0）这样的最终结果。⑵模型二（图解法）：         四人过河模型图 允许步骤数L是沿方格线移动1格或2格，L为奇数时向左.下方移动，L为偶数时向右.上方移动，要确定一系列的L，使初始状态（4，4）最终变为（0，0），无论怎样走都必须经过中间点（2，2），然后奇数次到达Y轴,，而无论怎么变化人数都也只能到达此点后不能继续走下去，只能循环走，达不到最终的目标（0，0）。