商人过河优化模型

1、2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反 竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置

2、报名号的话）：所属学校（请填写完整的全名）：西京学院参赛队员（打印并签名）：1.邹高永张大伟钱晓东指导教师或指导教师组负责人（打印并签名）：日期：年 月 日2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）:赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：商人过河摘要本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得 到了在随从没有杀人越货的情况下的渡河方案。对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先 定义了渡河前此岸的状态，

3、并设安全渡河条件下的状态集定义为允许状态集合， 接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后 利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方 案。但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类 问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用 了 dijkstra算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点 很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐 一列出。最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了 “传教士 与野蛮人渡河”，“印度夫妻渡河”等问题

4、通用的模型，并将其进行了推广。这也 是本文的一大特色。关键词渡河问题状态集合决策集合平面坐标dijkstra算法1问题重述三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划 行。随从们密约，在河的任意一岸，一旦随从的人数比商人多，就杀人越货.但 是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢？同时， 推广到四名商人带四名随从又如何？2问题分析安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或 从彼岸驶回此岸，都要对船上的人员（商人随从各几人）作出决策，在保证安全的 前提下（两岸的商人数都不比随从数少），在有限步内使人员全部过河。用状态（变 量）表示

5、某一岸的人员状况，决策（变量）表示船上的人员状况，可以找出状态随决 策变化的规律。问题转化为在状态的允许变化范围内（即安全渡河条件），确定每 一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能 找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。3模型假设及符号说明3.1模型假设（1）每个商人和随从都会划船；（2）只有一条船，且每条船上最多只能乘坐两个人；（3）所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；（4）船在渡河的过程中不受外界环境的影响。3.2符号说明A 初始状态下，商人和随从所在的一岸；B初始状态下，商人和随

6、从欲到达的一岸；七第k次渡河前，A岸的商人数；七 第k次渡河前，A岸的随从数；Sk渡河前A岸商人与随从数的状态；S渡河前A岸商人与随从数的允许状态的集合；七 第k次渡河时，船上的乘坐商人数；匕第k次渡河时，船上的乘坐随从数；dk第k次渡河方案的决策；D渡河方案的允许决策集合Dk第k次状态的转移4模型的建立与求解4.1模型的建立根据题意，可以作出商人渡河初始状态的示意图:渡河（选择A岸为参考点）记第k次渡河前A岸的商人数为七，随从数为yk, k = 1,2, ,m，且 七,yk= 0,1,2,3将二维向量，广（气,*）定义为状态，安全渡河条件下的状态集定义为允许 状态集合，记为S，因此有：S =

7、 （x,y）I x = 0,3; y = 0, 1, 2, 3 或x = 1;y = 0, 1 或x = 2;y = 0, 1,2（ 1）记第k次渡河时，船上的乘坐商人数为七，随从数为匕，将二维向量dk =（七,匕）定义为第k次渡河方案的决策，渡河方案的允许决策集合记为D 根据题意可知，船的容量是一定的，因此，得D = （u, v） I u+v = 1,2 （2）因为当k = 2n-1时，船由A岸驶向B岸；当k = 2n时，船由B岸驶向A岸。所以状态S随着d的变化的规律为： kkSki= Sk +(-1)kdk(3)这样，制定安全渡河方案归结为如下的多步决策问题：即：求决策dk e D(k =

8、 1,2, ,m)，使状态Sk e S。按照转移规律，由初始状态 S =(3,3)经有限m步后到达状态S +1 = (0,0)。4.2模型的求解根据(1)(2)(3)式，通过利用matlab编写一段程序来求解多步决策问 题是可行的，但是当商人和随从数都不多的情况下还可以用平面坐标法解此模型 更为方便。接下来，我们先用平面坐标法求解此模型，最后再使用计算机仿真， 对求解的结果进行验证，并给予推广。4.2.1平面坐标法设x为商人数，y为随从数。在功y平面坐标系上作分析。先标出此案的安 全状态点。起始点-(3,3)；最终点-(0,0)即模型求解就是探求从状态(3,3)经过有限次转移之后到达状态(0,

9、0)的方案。设Dk为第k次状态的转移，当k = 2n -1时，船由A岸驶向B岸，此时x, y只能减少， 不能增加。故坐标点只能向左下方移动。由于受船的容量的限制，x + y至多减 少2，即至多只能向左下方移动两格。如下图所示：从图中可以看出，在这种渡河方案中，时刻都能够确保“两岸安全”，不会 出现随从们“杀人越货”。4.2.2计算机仿真通过利用matlab编写一段程序来求解这种多步决策问题见附件:程序一， 当我们将商人数与随从数以及船的容量按照题意输入时，便会得到商人们的渡河 方案如下：表1 4种可供商人选择的不同渡河方案瓦案 状态方案一方案一方案三方案四（M，N）表示A 岸现在有M个 商人，

10、N个随从(3,3)(3,3)(3,3)(3,3)(2,2)(3,1)(2,2)(3,1)(3,2)(3,2)(3,2)(3,2)(3,0)(3,0)(3,0)(3,0)(3,1)(3,1)(3,1)(3,1)(1,1)(1,1)(1,1)(1,1)(2,2)(2,2)(2,2)(2,2)(0,2)(0,2)(0,2)(0,2)(0,3)(0,3)(0,3)(0,3)(0,1)(0,1)(0,1)(0,1)(0,2)(0,2)(1,1)(1,1)(0,0)(0,0)(0,0)(0,0)经检验，结果与使用平面坐标法得到的结果完全一致。通过计算机仿真，当题目中给定出任意数量的商人，随从，以及规定出任

11、 意船的容量，都可以判断出“商人们能否安全渡河？ ”以及解决“如果能，那么 安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。5模型的评价与改进5.1模型的评价5.1.1模型的优点（1）采用了较为成熟的数学理论建立模型，可行度比较高；（2）在讨论商人安全渡河的方案时，运用了图表，比较直观；（3）模型的求解运用了强大的matlab软件，结果可信度高，便于推广；（4）通过matlab程序，能判断出“当任意个商人、任意个随从、船的容量任意 时，商人能否安全渡河？”及解决了“如果能，那么渡河方案又是什么？”的问 题，使得所建模型更加全面。5.1.2模型的缺点利用平面坐标法求解该模型时

12、，出现了明显的遗漏，考虑的不够全面；没有找到商人数、随从数及船的容量之间的数量关系；没有考虑到实际生活中，在安全渡河的前提下，商人过河的优先级应高于 随从。5.2模型的改进基于以上求解模型用到的方法，我们明显意识到了结果考虑到的不够全面。 为此，我们利用dijkstra算法，通过相应程序求解前面模型见附件：程序二， 得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低。 而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。综合以上的努力，我们与致力于研究出一套方案：即给出任意个商人与任 意个随从以及船的容量任意的时候，都可以给出安全渡河的方案；并且在给出商 人数、随从数

13、、船的容量中任意两者，并要使其能够安全渡河情况下的第三者的 取值范围，以及得到最优的渡河方案。由于水平有限，我们只能提出这个美好的想法，用某种方法能把在所有安 全状态集合和决策集合中，搜索出所有可能的解，从而从其中找出最优的解。6模型的推广“商人渡河”模型适合于解决很多问题，如“传教士与野蛮人渡河”， “印度夫妻渡河”等。这些问题本质上都是相同或相似的，由此可见这个趣 味问题流传的广泛性。另外还有所谓“人狗鸡米过河”问题，也是颇有趣味 的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人 不在时，狗会吃鸡，鸡会吃米，问如何设计安全过河方案。我们完全可以仿 照商人渡河问题建立一个多步决策模型，将上述算法稍作修改，就可以得到 它的解。这里就不再赘述了。另外，用一定容积的若干油瓶倒出一定量的油 的问题也属此类问题。7参考文献1数学建模