商人过河四商四仆.pdf

商人过河四商四仆

公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08]

2012高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、

电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论

与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果

或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献

的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如

有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A

我们的参赛报名号为（如果赛区设置报名号的话）：J2202

所属学校（请填写完整的全名）：江西环境工程职业学院

参赛队员(打印并签名)：1.杨松泉

2.付琪

3.付建华

指导教师或指导教师组负责人(打印并签名)：教导组

日期：2012年8月

9日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2012高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评

阅

人

评

分

备

注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

摘要

本文研究的是四个商人和四个仆人从河岸的一边过到河的另一边的

问题，过河的工具只有一搜小船，只能同时载两个人过河，包括划船的

人，由他们自己划行。针对商人安全渡河的问题，采用多步决策的过

程，根据各量的空间几何关系，经过严格的数学公式推导。

分别建立两个模型：模型一采用穷举法，对各种过河的方案一一列

举，然后根据商人们要安全过河为前提对各种进行了列举，经过层层筛

选，最终求出商人安全的方案。模型二采用图解法，利用图示表示说明

该题的解法。

最后本文就此问题进行推广，当有M名商人N名随从且小船容量为

K时，将会得到几种解决方案给出了说明。

关键词：渡河问题数学公式

一、问题的提出

当今社会每个人都想当王者，谁都想成为富翁，所以就在这个问题

中仆人们也想成为商人。仆人们密约，在河的任何一边，只要仆人的数

量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，问应

如何设计过河顺序才能让所有人安全地过到河的另一边。

二、模型的分析

四个商人各带一名仆人乘船渡河，一只小船最多能容纳两个人，要

他们都安全到达河的对岸。这个问题可以看成一个多步决策的过程，每

一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员作出

计算，在保证安全的前提下（两岸的商人数都比仆人多）。在有限步内

使人员全部渡河，用状态（变量）表示某一岸的人员数量，决策（变

量）表示船上的人员数量，可以找出状态随决策的变化规律。问题转化

为在状态的允许范围内（安全条件渡河），确定每一步决策，达到渡河

的目的。