文档介绍：重庆大学
(商仆过河模型)
开课课程:数学模型
指导教师:黄光辉
小组成员:庄楚斌(20134760)自动化07班
张俊铭(20133227)材料加工01班
吴慧(20131966)数学01班
时间:2015年3月8日
一、问题提出
3名商人带3名随从乘一条小船过河,小船每次只能承载至多两人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就***,商人们如何才能安全渡河呢?
二、问题分析
商人与随从过河问题可以视为是一个多步决策的过程,通过多次优化,从而得到一个全局最优的决策方案。决策的每一步,即船从此岸到达彼岸,都要对船上的商人和仆人数做出决策。在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下,经有限步使所有人员到达彼岸。
三、模型假设
商人和随从都会划船,天气很好,无大风大浪,且船的质量很好,可以保证很多次安全的运载商人和随从。
四、模型建立
~第k次渡河前此岸的商人数,~第k次渡河前此岸的随从数
, =0,1,2,3; k=1,2,……
=(, , ck )~过程的状态,其中, , ck 分别表示对应时刻此
岸的商人,仆人数以及船的行进方向,其中c取值1表示即将向彼岸运行,为0表示即将向此岸运行
S ~ 允许状态集合,S={(x , y)| x=0, y=0,1,2,3; x=3 ,y=0,1,2,3; x=y=1,2}
~第k次渡船上的商人数
~第k次渡船上的随从数
=(, )~决策,D={(u , v)| ,, =0,1,2} ~允许决策集合
k=1,2,……
因为k为奇数时船从此岸驶向彼岸,k为偶数时船从彼岸驶向此岸,所以状态随决策的变化规律是
=+~状态转移律
求∈D(k=1,2, …n), 使∈S, 并按转移律由=(3,3,1)到达状态=(0,0,0(1))。
五、模型求解
本模型使用MATLAB软件编程, 通过穷举法获得所有可能的决策方案如下(完整matlab程序详见附录):
第一种: 第二种:
第三种: 第四种:
六、模型的推广
该商人、随从过河模型可以完美解决此类商仆过河的决策问题,并且该模型还可推广至解决m个商人和n个随从过河,以及小船的最大载重人数改变时的问题,只需适当地改变相关的语句即可轻松实现模型的转换。
如当商人数和随从数均为4,小船最大载重人数为2时,matlab程序运行的结果如下(程序改动详见附录):
推广过程只需要将其中的(x,y)(限定范围)改成相对应的情况即可,例如,商人基于仆人数都为4时允许状态集合,S={(x , y)| x=0, y=0,1,2,3,4; x=4 ,y=0,1,2,3,4; x=y=1,2,3}
总结
本程序相对于网上各种结构体,堆栈形式的程序来说简单很多,没有用到那些高级的函数,简单易懂,
核心要点:
(1)就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向,在后面判断是否有重复时非常重要,因为在船行进方向不同时,就算此岸人员分布一样也不是一种情况
(2)就是设置了m数组,以便于在后面的穷举过程中,记录每一步所采用的决策方案,以防止后面重复或者遗漏
(3)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说