商人过河数学模型.docVIP

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