商人过河优化模型.doc

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： J2202 所属学校（请填写完整的全名）： 江西环境工程职业学院 参赛队员 (打印并签名) ：1. 罗妮娜 2. 肖思彦 3. 熊明远 指导教师或指导教师组负责人 (打印并签名)： 教练组 日期： 2012 年 8月 9日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：商人过河摘要本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。关键词 渡河问题 状态集合 决策集合 平面坐标 算法 一 、问题的提出三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任意一岸，一旦随从的人数比商人多，就杀人越货但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢？同时，推广到四名商人带四名随从又如何？二、问题分析安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。三、 模型假设及符号说明3.1 模型假设（1）每个商人和随从都会划船；（2）只有一条船，且每条船上最多只能乘坐两个人；（3）所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；（4）船在渡河的过程中不受外界环境的影响。3.2 符号说明 初始状态下，商人和随从所在的一岸； 初始状态下，商人和随从欲到达的一岸； 第次渡河前，岸的商人数； 第次渡河前，岸的随从数； 渡河前岸商人与随从数的状态； 渡河前岸商人与随从数的允许状态的集合； 第次渡河时，船上的乘坐商人数； 第次渡河时，船上的乘坐随从数； 第次渡河方案的决策； 渡河方案的允许决策集合 第次状态的转移四、 模型的建立与求解4.1 模型的建立根据题意，可以作出商人渡河初始状态的示意图：AB渡河目的：（选择岸为参考点）记第次渡河前岸的商人数为，随从数为，且将二维向量定义为状态，安全渡河条件下的状态集定义为允许状态集合，记为，因此有： （1）记第次渡河时，船上的乘坐商人数为，随从数为，将二维向量定义为第次渡河方案的决策，渡河方案的允许决策集合记为根据题意可知，船的容量是一定的，因此，得 （2）因为当时，船由岸驶向岸；当时，船由岸驶向岸。所以状态随着的变化的规律为： （3）这样，制定安全渡河方案归结为如下的多步决策问题：即：求决策，使状态。按照转移规律，由初始状态经有限步后到达状态。4.2 模型的求解根据（1）（2）（3）式，通过利用matlab编写一段程序来求解多步决策问题是可行的，但是当商人和随从数都不多的情况下还可以用平面坐标法解此模型更为方便。接下来，我们先用平面坐标法求解此模型，最后再使用计算机仿真，对求解的结果进行验证，并给予推广。4.2.1 平面坐标法设为商人数，为随从数。在平面坐标系上作分析。先标出此案的安全状态点。起始点-；最终点-即模型求解就是探求从状态经过有限次转移之后到达状态的方案。设为第次状态的转移，当时，船由岸驶向岸，此时只能减少，不能增加。故坐标点只能向左下方移动。由于受船的容量的限制，至多减少2，即至多只能向左下方移动两格。如下图所示：2X 商人Y仆人13123 如图1.3商仆过河的示意图 从图中可以看出，在这种渡河方案中，时刻都能够确保“两岸安全”，不会出现随从们“杀人越货”。4.2.2 计算机仿真通过利用matlab编写一段程序来求解这种多步决策问题见附件：程序一，当我们将商人数与随从数以及船的容量按照题意输入时，便会得到商人们的渡河方案如下：表 1 4种可供商人选择的不同渡河方案方案状态方案一方案二方案三方案四（，）表示岸现在有个商人，个随从（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）经检验，结果与使用平面坐标法得到的结果完全一致。通过计算机仿真，当题目中给定出任意数量的商人，随从，以及规定出任意船的容量，都可以判断出“商人们能否安全渡河？”以及解决“如果能，那么安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。五、 模型的评价与改进1.模型的评价（1） 模型的优点:（1）采用了较为成熟的数学理论建立模型，可行度比较高；（2）在讨论商人安全渡河的方案时，运用了图表，比较直观；（3）模型的求解运用了强大的matlab软件，结果可信度高，便于推广；（4）通过matlab程序，能判断出“当任意个商人任意个随从船的容量 任意时，商人能否安全渡河？”及解决了“如果能，那么渡河方案又是什么？”的问题，使得所建模型更加全面。5.1.2 模型的缺点:（1）利用平面坐标法求解该模型时，出现了明显的遗漏，考虑的不够全面；（2）没有找到商人数随从数及船的容量之间的数量关系；（3）没有考虑到实际生活中，在安全渡河的前提下，商人过河的优先级应高于随从。5.2 模型的改进基于以上求解模型用到的方法，我们明显意识到了结果考虑到的不够全面。为此，我们利用dijkstra算法，通过相应程序求解前面模型见附件：程序二，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低。而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。综合以上的努力，我们与致力于研究出一套方案：即给出任意个商人与任意个随从以及船的容量任意的时候，都可以给出安全渡河的方案；并且在给出商人数、随从数、船的容量中任意两者，并要使其能够安全渡河情况下的第三者的取值范围，以及得到最优的渡河方案。由于水平有限，我们只能提出这个美好的想法，用某种方法能把在所有安全状态集合和决策集合中，搜索出所有可能的解，从而从其中找出最优的解。六、模型的推广“商人渡河”模型适合于解决很多问题，如“传教士与野蛮人渡河”，“印度夫妻渡河”等。这些问题本质上都是相同或相似的，由此可见这个趣味问题流传的广泛性。另外还有所谓“人狗鸡米过河”问题，也是颇有趣味的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计