商人过河数学模型

《商人过河数学模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档商人过河数学模型专业信息与计算科学班级113010102姓名罗彪学号11301010229实用文档一、问题重述3名商人各带一名随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全过河呢？二、问题分析商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步

2、内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。三、模型假设1.每个商人和随从都会划船；实用文档2.只有一条船，且每条船上最多只能乘坐两个人；3.所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；4.船在渡河的过程中不受外界环境的影响。一、模型的建立与求解1.模型建立~第k次渡河前此岸的商人数，~第k次渡河前此岸的随从数,=0,1,2,3;k=1,2,……=(,,ck

3、)~过程的状态，其中,,ck分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中c取值1表示即将向彼岸运行，为0表示即将向此岸运行S~允许状态集合，S={(x,y)

4、x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}~第k次渡船上的商人数~第k次渡船上的随从数=(,)~决策，D={(u,v)

5、,,=0,1,2}~允许决策集合k=1,2,……因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是=+~状态转移律求∈D(k=1,2,…n),使∈S,并按转移律由=(3,3,1

6、)到达状态实用文档=(0,0,0(1))。1.模型求解本模型使用MATLAB软件编程求解，运行结果如下>>chouxiang输入商人数目:3输入仆人数目:3输入船的最大容量:2ans=001101030222113130323133Matlab程序functionfoot=chouxiang%程序开始需要知道商人数，仆人数，船的最大容量实用文档sr=input('输入商人数目:');pr=input('输入仆人数目:');c=input('输入船的最大容量:');ifpr>srsr=input('输入商人数目:');pr=in

7、put('输入仆人数目:');c=input('输入船的最大容量:');end%状态数组生成zt=1;%状态数组存放在矩阵“A”中,zt为插入新元素的行标初始为1fori=sr:-1:0forj=pr:-1:0if((i>=j)&((sr-i)>=(pr-j)))

8、((i==0)

9、(i==sr))%(i>=j)&((sr-i)>=(pr-j)))

10、((i==0)

11、(i==sr))为可以存在的状态的约束条件A(zt,1:3)=[i,j,1];%表示此岸安全A(zt+1,1:3)=[i,j,0];zt=zt+2;endj=pr;e

12、nd;end;%决策生成jc=1;fori=0:c实用文档forj=0:cif(i+j<=c)&(i+j>0)%满足条件D={(u,v)

13、1<=u+v<=c,u,v=0,1,2}d(jc,1:3)=[i,j1];%表示从此岸到彼岸d(jc+1,1:3)=[-i,-j,-1];%表示从彼岸到此岸jc=jc+2;endendj=0;end%将状态数组生成抽象矩阵k=(1/2)*size(A,1);CX=zeros(2*k,2*k);a=size(d,1);fori=1:2*kforj=1:ac=A(i,:)+d(j,:);x=fi

14、nd((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3)));v(i,x)=1;%x为空不会改变v的值endend%dijstra方法x=1;y=size(A,1);实用文档m=size(v,1);T=zeros(m,1);T=T.^-1;lmd=T;P=T;S=zeros(m,1);S(x)=1;P(x)=0;lmd(x)=0;k=x;while(1)a=find(S==0);aa=find(S==1);ifsize(aa,1)==mbreak;endforj=1:size(a,1)pp=

15、a(j,1);ifv(k,pp)~=0ifT(pp)>(P(k)+v(k,pp))T(pp)=(P(k)+v(k,pp));lmd(pp)=k;endendendmi=min(T(a));ifmi==infbreak;else实用文档d=find(T==mi);d=d(1);