商人过河数学模型.doc

商人过河数学模型 专业 信息与计算科学 班级 113010102 姓名 罗彪 学号 11301010229 1、 问题重述3名商人各带一名随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全过河呢？2、 问题分析 商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。3、 模型假设1.每个商人和随从都会划船；2.只有一条船，且每条船上最多只能乘坐两个人；3.所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；4.船在渡河的过程中不受外界环境的影响。4、 模型的建立与求解1. 模型建立第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)。2. 模型求解本模型使用MATLAB软件编程求解，运行结果如下 chouxiang输入商人数目:3输入仆人数目:3输入船的最大容量:2ans = 0 0 1 1 0 1 0 3 0 2 2 2 1 1 3 1 3 0 3 2 3 1 3 3Matlab程序function foot=chouxiang %程序开始需要知道商人数，仆人数，船的最大容量sr=input(输入商人数目:);pr=input(输入仆人数目:);c=input(输入船的最大容量:); if prsrsr=input(输入商人数目:);pr=input(输入仆人数目:);c=input(输入船的最大容量:); end %状态数组生成 zt=1; % 状态数组存放在矩阵“A”中,zt为插入新元素的行标初始为1for i=sr:-1:0 for j=pr:-1:0 if (i=j)&(sr-i)=(pr-j)|(i=0)|(i=sr) %(i=j)&(sr-i)=(pr-j)|(i=0)|(i=sr)为可以存在的状态的约束条件 A(zt,1:3)=i,j,1; % 表示此岸安全 A(zt+1,1:3)=i,j,0; zt=zt+2; end j=pr;end;end;%决策生成 jc=1; for i=0:c for j=0:c if (i+j0) % 满足条件 D=(u,v)|1=u+v(P(k)+v(k,pp) T(pp)=(P(k)+v(k,pp); lmd(pp)=k; end end end mi=min(T(a); if mi=inf break; else d=find(T=mi); d=d(1); P(d)=mi; T(d)=inf; k=d; S(d)=1; endendif lmd(y)=inf foot=can not reach; return;endfoot(1)=y;g=2; h=y;while(1) if h=x break; end foot(g)=lmd(h); g=g+1; h=lmd(h);end foot=A(foot,:);foot(:,3)=;5、 模型评价与推广1.模型的优点: 采用了较为成熟的数学理论建立模型，可行度比较高；模型的求解运用了强大的matlab软件，结果可信度高，便于推广；2. 模型的缺点: 没有找到商人数随从数及船的容量之间的数量关系；没有考虑到实际生活中，在安全渡河的前提下，商人过河的优先级应高于随从