商人过河优化模型

《商人过河优化模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：J2202所属学校（请填写完整的全名）：江西环境工程职业学院参赛队员(打印并签名)：1.罗妮娜2.肖思彦3.熊明远指导教师或指导教师组负责人(打印并签名)：教练组日期：2012年8月9日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评

3、阅前进行编号）：商人过河摘要本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广

4、泛的问题。基于此目的，利用了算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。关键词渡河问题状态集合决策集合平面坐标算法一、问题的提出三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任意一岸，一旦随从的人数比商人多，就杀人越货．但是如何乘船渡河的

5、大权掌握在商人们手中。商人们怎样才能安全渡河呢？同时，推广到四名商人带四名随从又如何？二、问题分析安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行

6、方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。三、模型假设及符号说明3.1模型假设（1）每个商人和随从都会划船；（2）只有一条船，且每条船上最多只能乘坐两个人；（3）所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；（4）船在渡河的过程中不受外界环境的影响。3.2符号说明初始状态下，商人和随从所在的一岸；初始状态下，商人和随从欲到达的一岸；第次渡河前，岸的商人数；第次渡河前，岸的随从数；渡河前岸商人与随从数的状态；渡河前岸商人与随从数的允许状态的集合；第次渡河时

7、，船上的乘坐商人数；第次渡河时，船上的乘坐随从数；第次渡河方案的决策；渡河方案的允许决策集合第次状态的转移四、模型的建立与求解4.1模型的建立根据题意，可以作出商人渡河初始状态的示意图：AB渡河目的：——>（选择岸为参考点）记第次渡河前岸的商人数为，随从数为，，且将二维向量定义为状态，安全渡河条件下的状态集定义为允许状态集合，记为，因此有：（1）记第次渡河时，船上的乘坐商人数为，随从数为，将二维向量定义为第次渡河方案的决策，渡河方案的允许决策集合记为根据题意可知，船的容量是一定的，因此，得（2）因为当时，船由岸驶向岸；

8、当时，船由岸驶向岸。所以状态随着的变化的规律为：（3）这样，制定安全渡河方案归结为如下的多步决策问题：即：求决策，使状态。按照转移规律，由初始状态经有限步后到达状态。4.2模型的求解根据（1）（2）（3）式，通过利用matlab编写一段程序来求解多步决策问题是可行的，但是当商人和随从数都不多的情况下还可以用平面坐标法解此模型更为方