(正版)商人过河优化模型[9页]

《(正版)商人过河优化模型[9页]》由会员分享，可在线阅读，更多相关《(正版)商人过河优化模型[9页]（9页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

6、随从所在的一岸：3初始状态下，商人和随从欲到达的一岸：忑 第*次渡河前，/岸的商人数：必 第*次渡河前，/岸的随从数：渡河前A岸商人与随从数的状态:S渡河前/岸商人与随从数的允许状态的集合:纵 第M次渡河时，船上的乘坐商人数：”第M次渡河时，船上的乘坐随从数：g 第斤次渡河方案的决策：D渡河方案的允许决策集合9第斤次状态的转移四、模型的建立与求解4. 1模型的建立根据题意，可以作出商人渡河初始状态的示意图：渡河目的：A一一B (选择/岸为参考点)记第it次渡河前/岸的商人数为忑，随从数为必，斤=1,2,加，且旺,” =0,1,2,3将二维向量S* =(忑,必)定义为状态，安全渡河条件下的状态集

7、定义为允许 状态集合，记为S,因此有：S = (R域战=0,3; y = 0, 1, 2, 3 x = l;y = 0, 1 x = 2;y = 0, 1,2(1)记第&次渡河时，船上的乘坐商人数为随从数为,将二维向量 dk=(ukyvk)定义为第斤次渡河方案的决策，渡河方案的允许决策集合记为D根据题意可知，船的容量是一定的，因此，得D = (m,v)| w+v = 1,2(2)因为当k = 2n-时，船由/岸驶向3岸：当2“时，船由3岸驶向/岸。所以状态：随着/的变化的规律为：九=+(-1)乜(3)这样，制定安全渡河方案归结为如下的多步决策问题：即：求决策伙=1,2,.,加)，使状态S“S。

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

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

10、)|(3,1)(3,1)(3,2)(3,2)(32)（3）(3,0)(3,0)(3,0)(3,0)(3,1)(3,1)(3,1)(3,1)在有A/个商人，（1）(1,1)(1,1)(1,1)N个随从(2,2)(2,2)(22)(2,2)(0,2)(0,2)(02)(0,2)(0,3)(0,3)(0,3)(0,3)(0,1)(0,1)(0,1)(0,1)(1,1)(0,0)(0,0)(0,0)(0,0)经检验，结果与使用平而坐标法得到的结果完全一致。通过计算机仿真，当题目中给定出任意数量的商人，随从，以及规定出任 意船的容量，都可以判断出“商人们能否安全渡河？ ”以及解决“如果能，那 么安全渡河

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

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

13、值范围，以及得到最优的渡河方案。由于水平有限，我们只能提出这个美好的想法，用某种方法能把在所有安 全状态集合和决策集合中，搜索出所有可能的解，从而从其中找出最优的解。六、模型的推广商人渡河”模型适合于解决很多问题，如传教士与野蛮人渡河”，“印度夫妻渡河”等。这些问题本质上都是相同或相似的，由此可见这个趣 味问题流传的广泛性。另外还有所谓“人狗鸡米过河”问题，也是颇有趣味 的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人 不在时，狗会吃鸡，鸡会吃米，问如何设计安全过河方案。我们完全可以仿 照商人渡河问题建立一个多步决策模型，将上述算法稍作修改，就可以得到 它的解。这里就不再赘述了。另外，用一定容积的若干油瓶倒出一定量的油 的问题也属此类问题。1数学建模案例分析白其峥主编北京：海洋出版社2数模竞赛赛题简析与论文点评：西安交大近年参赛论文选编赫孝良等选编西安: 西安交通大学岀版社卩百度百科文献访问日期4数学模型精品课程第四章