商人过河matlab程序以及解析.doc

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