承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

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

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

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A
我们的参赛报名号为（如果赛区设置报名号的话）：J2202 __________ 所属学校（请填写完整的全名）：江西环境工程职业学院
参赛队员（打印并签名）：1. ___________________________________
2. ___________________________________________
3. ___________________________________
指导教师或指导教师组负责人（打印并签名）：教练组_____________________________
日期：2012年8月9日赛区评阅编号（由赛区组委会评阅前进行编号）：
编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）:
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
商人过河
摘要
本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。

对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律, 最后利用平而坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。

但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。

基于此目的，利用了 dijkstm算法,得到最短路径的最优解。

但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。

最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。

这也是本文的一大特色。

关键词渡河问题状态集合决策集合平面坐标dijg算法
一、问题的提出
三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。

随从们密约，在河的任意一岸，一旦随从的人数比商人多，就杀人越货.但是如何乘船渡河的大权掌握在商人们手中。

商人们怎样才能安全渡河呢？同时，推广到四名商人带四名随从又如何？
二、问题分析
安全渡河问题可以看成一个多步决策过程。

每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员（商人随从各几人）作出决策，在保证安全的前提下（两岸的商人数都不比随从数少），在有限步内使人员全部过河。

用状态（变量）表示某一岸的人员状况，决策（变虽:）表示船上的人员状况，可以找出状态随决策变化的规律。

问题转化为在状态的允许变化范围内（即安全渡河条件） ,确定每一步的决策，达到渡河的目的。

此类智力问题经过思考，可以拼凑出一个可行方案。

但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。

三、模型假设及符号说明
3.1模型假设
（1）每个商人和随从都会划船：
（2）只有一条船，且每条船上最多只能乘坐两个人：
（3）所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象:
（4）船在渡河的过程中不受外界环境的影响。

3. 2符号说明
A初始状态下，商人和随从所在的一岸：
3初始状态下，商人和随从欲到达的一岸：
忑第*次渡河前，/岸的商人数：
必第*次渡河前，/岸的随从数：
渡河前A岸商人与随从数的状态:
S渡河前/岸商人与随从数的允许状态的集合:
纵第M次渡河时，船上的乘坐商人数：
”第M次渡河时，船上的乘坐随从数：
g 第斤次渡河方案的决策：
D渡河方案的允许决策集合
9第斤次状态的转移
四、模型的建立与求解
4. 1模型的建立
根据题意，可以作出商人渡河初始状态的示意图：
渡河目的：A一一＞B (选择/岸为参考点)
记第it次渡河前/岸的商人数为忑，随从数为必，斤=1,2,…,加，且
旺,” =0,1,2,3
将二维向量S* =(忑,必)定义为状态，安全渡河条件下的状态集定义为允许状态集合，记为S,因此有：
S = {(R域战=0,3; y = 0, 1, 2, 3 x = l;y = 0, 1 x = 2;y = 0, 1,2} (1)
记第&次渡河时，船上的乘坐商人数为随从数为％,将二维向量d k=(u ky v k)定义为第斤次渡河方案的决策，渡河方案的允许决策集合记为D
根据题意可知，船的容量是一定的，因此，得
D = {(M,V)| w+v = 1,2}
(2)
因为当k = 2n-\时，船由/岸驶向3岸：当"2“时，船由3岸驶向/岸。

所以状态：随着/的变化的规律为：
九=£+(-1)乜
(3)
这样，制定安全渡河方案归结为如下的多步决策问题：
即：求决策£€»伙=1,2,..・,加)，使状态S“S。

按照转移规律，由初始
状态S,=(3,3)经有限刃步后到达状态S m+1=(0,0)o
4.2模型的求解
根据(1) (2) (3)式，通过利用matlab编写一段程序来求解多步决策问题是可行的，但是当商人和随从数都不多的情况下还可以用平而坐标法解此模型更为方便。

接下来，我们先用平面坐标法求解此模型，最后再使用计算机仿真，对求解的结果进行验证，并给予推广。

4. 2. 1平而坐标法
设x为商人数，y为随从数。

在my平面坐标系上作分析。

先标出此案的安全状态点。

起始点一一(3,3)：最终点一•(0,0)
即模型求解就是探求从状态(3,3)经过有限次转移之后到达状态(0,0)的方案。

设Q为第斤次状态的转移，当k = 2n-\时，船由/岸驶向B岸，此时只能减少，不能增加。

故坐标点只能向左下方移动。

由于受船的容量的限制，x + y至多减少2,即至多只能向左下方移动两格。

如下图所示：。