haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 小学数学小学数学

建模论文

发布时间:2013-11-05 11:40:37  

商人过河问题

学号: 姓名:

摘要

1、问题提出

三名商人各带一个随从乘船渡河,一只小船只能容纳二人,由他们自己划行。随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?

2、模型假设

安全渡河问题可以视为一个多步决策过程。每一步,即船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员(商人、随从各几人)作出决策,在保证安全的前提下(两岸的随从数都不比商人数多),在有限步内使全部人员过河。用状态(变量)表示某一岸的人员状况,可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件),确定每一步的决策,达到渡河的目标。

3、模型建立

记第k次渡河前此岸的商人数为xk,随从数为yk,k=1,2,…,xk,yk=0,1,2,3。将二维向量sk=(xk,yk)定义为状态。安全渡河条件下的状

态集合称为允许状态集合,记作S

S={(x,y)| x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2} (1-1) 或 S={(0,0)(0,1)(0,2)(0,3)(1,1)(2,2)(3,3)(3,0)(3,1)(3,2)} 不难验证,S对此岸和彼岸都是安全的。

记第k次渡船上的商人数为uk,随从数为vk。将二维向量dk=(uk,vk)定义为决策。允许决策集合记作D,由小船的容量可知

D={(u,v)|1?u+v?2,u,v=0,1,2} (1-2)

因为k为奇数时船从此岸驶向彼岸,k为偶数时船从彼岸驶回此岸,所以状态sk随决策dk变化的规律是

sk?1=sk+(?1)kdk (1-3)

上式称为状态转移律。这样,制定安全渡河方案归结为如下的多步决策模型:

求决策dk?D(k=1,2,…,n),使状态sk?S按照转移律(3),由初始状态s1=

(3,3)经有限步n到达状态sn?1=(0,0)

4、模型求解

根据(1)~(3)式编一段程序,用计算机求解上述多步决策问题。Matlab编程如下:

clear all

clc

n=3;m=3;h=2; %n为商人数,m为随从数,h为每次过河的最多人数 m0=0;n0=0; %初始状态及数据

tic %运行出结果所需的时间

LS=0; %允许的状态集合S与个数LS

LD=0; %允许的决策集合D与个数LD

for i=0:n

for j=0:m

if i>=j&n-i>=m-j|i==n|i==0

LS=LS+1;S(LS,:)=[i j];

end

if i+j>0&i+j<=h&(i>=j|i==0)

LD=LD+1;D(LD,:)=[i j];

end

end

end

%用搜索法找出符合条件的渡河方案

N=15;

Q1=inf*ones(2*N,2*N); %无穷乘以一个所有元素都为1(2乘以N阶)的矩阵 Q2=inf*ones(2*N,2*N);

t=1;

le=1;

q=[m n];

f0=0; %判断循环终止标记

while f0~=1&t<N %搜索可行的策略

k=1;

sa=[];

sb=[];

for i0=1:le %第n次允许的策略集逐次搜索

s0=q(i0,:);

if f0==1

break

end

for i=1:LD %由s0搜索D后得到允许的状态

s1=s0+(-1)^t*D(i,:);

if s1==[m0,n0]

sa=[m0,n0];

sb=D(i,:);

f0=1;

break

end

for j=2:LS-1 %搜索对比S后允许的状态 if s1==S(j,:)

if k==1

sa(k,:)=s1;

sb(k,:)=D(i,:);

k=k+1;

break

end

if k>1 %对重复状态进行删除处理 f1=0;

for ii=1:k-1

if s1==sa(ii,:)

f1=1;

break

end

end

end

if f1==0

sa(k,:)=s1;

sb(k,:)=D(i,:);

k=k+1;

break

end

end

end

end

end

q=sa;

le=size(q,1);

Q1(1:le,t*2-1:t*2)=q;

Q2(1:le,t*2-1:t*2)=sb;

t=t+1;

end

%在可行方案集合中逆向搜寻唯一方案

tr=t-1;saa1=sa;

SA=zeros(tr,2);SB=zeros(tr,2);

for k=tr:-1:2

k1=k-1;f0=0;

sbb=Q2(:,k*2-1:k*2);

saa=Q1(:,k1*2-1:k1*2);

for i=1:2*N

saa2=saa1-(-1)^k*sbb(i,:); for j=1:2*N

if saa2==saa(j,:) saa1=saa2;

sbb1=sbb(i,:); f0=1;

break

end

end

if f0==1

break

end

end

SA(k1,:)=saa1;

SB(k,:)=sbb1;

end

SA(tr,:)=[m0 n0];

SB(1,:)=[m,n]-SA(1,:);

disp '初始状态:'

X0=[m,n]

disp '状态为:'

SA

disp '决策为:'

SB

toc

运行结果为:

初始状态:

X0 =

3 3

状态为:

SA =

3 1

3 2

3 0

3 1

1 1

2 2

0 2

0 3

0 1

0 2

0 0

决策为:

SB =

0 2

0 1

0 2

0 1

2 0

1 1

2 0

0 1

0 2

0 1

0 2

Elapsed time is 0.060993 seconds.

5、结果分析

运行结果与预期结果相同。

通过自己的笔算检验,迭代过程见附录A。

此处只解决3个商人和3个随从过河的状态,若当商人和随从数增加或小船的容量加大时,靠逻辑思考就困难了,而用这种模型则仍然可以求解。由于本人能力有限,此处就不再加以分析。

参考文献

[1] 姜启源 谢金星 叶俊《数学模型》(第四版)北京 高等教育出版社 2011.12.3

附录A

通过笔算检验,迭代过程如下:

s=(3,3) 1

1???(?1)s2s1?1s1d1?(3,3)?(0,2)?(3,1)

2???(?1)s3s2?1s2d2?(3,1)?(0,1)?(3,2)

3??(?1)s4s3d3?(3,2)?(0,2)?(3,0)

4??(?1)s5s4d4?(3,0)?(0,1)?(3,1)

s?s6

75?(?1)d5?(3,1)?(2,0)?(1,1) 5s?s

s?s96?(?1)6d6?(1,1)?(1,1)?(2,.2) 7??(?1)s8s7d7?(2,2)?(2,0)?(0,2) 8?(?1)d8?(0,2)?(0,1)?(0,3) 8

s10?s9?(?1)9d9?(0,3)?(0,2)?(0,1)

10??(?1)s11s10d10?(0,1)?(0,1)?(0,2)

s11??(?1)sd11?(0,2)?(0,2)?(0,0) 1211

所求决策为: dk= 0 2

0 1 0 2 0 1 2 0 1 1 2 0 0 1 0 2 0 1 0 2

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com