文档介绍：节螂重庆大学螈芆蚄(商仆过河模型)膁开课课程:数学模型薈指导教师:黄光辉莇小组成员:庄楚斌()自动化07班螃张俊铭()材料加工01班薀吴慧()数学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)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说是个巨大的进步,这得益于其中while函数的使用,回溯思想的建立,以及每次找到成功的路线之后,在将路线输出之后,以未成功的方式继续穷举,向下运行到找到第二条成功路线以及更多的方案到所有的可能进程都被检验为止。衿芈螅膁羁莆膄袂肂附录蝿Matlab源代码蚃1、三个商人三个随从蚂%——商人过河MATLAB程序,3商人,3仆人衿%本程序相对于网上各种结构体,堆栈形式的程序来说简单很多,没有用到那些高级的函数,简单易懂袇%核心要点(1)就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向,在后面判断是否有重复时非常重要,因为在船行进方向不同时,就算此岸人员分布一样也不是一种情况莇%核心要点(2)就是设置了m数组,以便于在后面的穷举过程中,记录每一步所采用的决策方案,以防止后面重复或者遗漏莃%核心要点(3)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说是个巨大的进步袁艿z=zeros(30,3);%z为由(a,b,c)的列向量组成的3行30列数组,初始化为0矩阵,a,b,c代表此刻此岸的商人,仆人数量以及船的运行状态,c=1表示即将向彼岸运行螆m=zeros(1,20);%m为一维行向量,初始化为1矩阵,用于在后面的程序中判断第k次选择的乘船方案膃d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1];%共有5种可以选择的乘船方案,最后面一列全为1,即用于在后面表示使得z(k,3)的取值保持随着k的奇偶性保持着0-1变换.