商人过河数学模型
专业信息与计算科学
班级 113010102 姓名罗彪
学号 ***********
一、问题重述
3名商人各带一名随从乘船渡河，一只小船只能容纳二人，由他们自己划行。
随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。
但是如何乘船渡河的大权掌握在商人们手中。
商人们怎样才能安全过河呢？
二、问题分析
商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。
对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。
用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。
三、模型假设
1.每个商人和随从都会划船；
2.只有一条船，且每条船上最多只能乘坐两个人；
3.所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；
4.船在渡河的过程中不受外界环境的影响。
四、模型的建立与求解 1.模型建立
k x ~第k 次渡河前此岸的商人数，k y ~第k 次渡河前此岸的随从数
k x , k y =0,1,2,3; k =1,2,… …
k S =(k x , k y , c k )~过程的状态，
其中k x , k y , c k 分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中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 u ~第k 次渡船上的商人数 k v ~第k 次渡船上的随从数
k d =(k u , k v )~决策，D={(u , v )| 21≤+≤v u ,k u , k v =0,1,2} ~允许决策集合
k =1,2,… …
因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态
k S 随决策k d 的变化规律是
1+k S =k S +k )1(-k d ~状态转移律
求k d ∈D(k =1,2, …n), 使k S ∈S, 并按转移律由1S =(3,3,1)到达状态
1+n S =(0,0,0(1))。
2.模型求解
本模型使用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('输入船的最大容量:');
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+j>0) % 满足条件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]; %表示从彼岸到此岸
jc=jc+2;
end
end
j=0;
end
%将状态数组生成抽象矩阵
k=(1/2)*size(A,1);
CX=zeros(2*k,2*k);
a=size(d,1);
for i=1:2*k
for j=1:a
c=A(i,:)+d(j,:) ;
x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ;
v(i,x)=1; % x为空不会改变v的值
end
end
%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);
if size(aa,1)==m
break;
end
for j=1:size(a,1)
pp=a(j,1);
if v(k,pp)~=0
if T(pp)>(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;
end
end
if lmd(y)==inf
foot='can not reach';
return;
end
foot(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)=[];
五、模型评价与推广
1.模型的优点: 采用了较为成熟的数学理论建立模型，可行度比较高；
模型的求解运用了强大的matlab软件，结果可信度高，便于推广；
2.模型的缺点: 没有找到商人数﹑随从数及船的容量之间的数量关系；没有考虑
到实际生活中，在安全渡河的前提下，商人过河的优先级应高于随从。
3.该商人、随从过河模型可以完美解决此类商仆过河的决策问题，并且该模型还可推广至解决m个商人和n个随从过河，以及小船的最大载重人数改变时的问题，只需适当地改变相关的语句即可轻松实现模型的转换。