商人过河

《商人过河》由会员分享，可在线阅读，更多相关《商人过河（8页珍藏版）》请在装配图网上搜索。

1、数学建模题 目： 商人安全过河问题 学 院： 数理与信息工程学院 专 业： 数学与应用数学 组 员： 指导老师： 评 分： 摘 要本文通过MATLAB编程来解决商人安全过河问题。运用编程来计算分析，动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题。针对此问题，为了求解3个商人和3个随从的过河问题，用数学分析方法，建立多步决策数学模型，并且加以求解。首先通过图解法求解3个商人和3个随从的过河问题，引进状态、允许状态集合、状态转移等，通过多步决策将初始状态到最终状态来解决问题。总之，问题转化为多步决策模型通过计算机、图解法解决了问题过河需要

2、经过11此来回。关键词：多步决策；计算机求解；状态转移律；图解法；MATLAB程序1 问题重述三名商人各带一个随从过河，一只小船只能容纳两个人，随从们约定，只要在河的任何一岸，一旦随从人数多于商人人数就杀人越货，但是商人们知道了他们的约定，并且如何过河的大权掌握在商人们手中，商人们该采取怎样的策略才能安全过河呢？S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？2 模型假设1.假设记第k次过河前A岸的商人数为XK，随从数为YK，

3、 k=1，2， XK ,YK=0,1,2,3，将二维向量SK=(XK,YK)定义为状态把满足安全渡河条件下的状态集合称为允许状态集合。记作S。则S=(XK,YK)|(XK=0,YK=0,1,2,3),(XK =3,YK =0,1,2,3),(XK =YK=1)(XK=YK=2)2.假设记第k次过河船上的商人数为UK，随从数为VK将二维向量DK=(UK ,VK)定义为决策。由小船的容量可知允许决策集合（记作D)为 D=(UK ,VK)|UK+VK=1,2=(0,1);(0,2);(1,0);(1,1);(2,0)3 模型的建立与求解3.1 问题一3.1.1 问题分解在安全的前提下(两岸的随从数不

4、比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树树根是原问题。原问题的解依赖于子问题树中所有子问题的解。解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。3.1.2 模型的建立动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以

5、直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树树根是原问题。原问题的解依赖于子问题树中所有子问题的解。用动态规划法分析三名商人的过河问题。可得如下的递归树：）K=1A(3,2)B(0,1)A(3,2)B(0.1)K=2A（3,1）B(0,2)(0,1)A（2,2）B(1,1)（0，2）A(3,0)B(0,3)(1,1)(2,0)（3,3）（1,1）(1,0)相同情况K=3(0,2)A(3,1)B(0,2)K=4K=5(0,1)(2,0)A(1,1)B(2,2)K=6A(2,2)B(1,1)K=7=A(0,2)B(3,1)K=8(0,1)A(0,3)B(3,0)K=9(0,

6、2)A(0,1)B(3,2)A(1,1)B(2,2)A(0,2)B(3,1)(1,0)(0,1)A(0,0)B(3,3)K=10K=11（注解：当K为奇数时，船在B岸；当K为偶数时，船在A岸。）通过分析该递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。因为k为奇数时，船是从A岸驶向B岸，k为偶数时。船是由B岸驶回A岸。所以状态SK随决策DK变化的规律是SK+1=SK+(-1)K DK，k=l,2,， 称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题：每一步，船由A岸驶向B岸或B岸驶回A岸，都要对船上的人员(商人UK，随从VK各几人)作出决策，在保证安全的前

7、提下即两岸的商人数XK都不比随从数YK少，用有限步使人员全部过河用状态(变量)SK表示某一岸的人员状况，决策(变量) DK表示船上的人员状况，可以找出状态SK随决策DK变化的规律这样安全过河问题就转化为：求决策DKD(k=1,2,n)，使得状态SKS，按照状态转移律，由初始状态S1=(3,3)，经有限步n到达状态SK+1=(0,0)。模型建立：SK+1=SK+-1K DK，k=l,2,其中DKDk=1,2,n=UK ,VKUK+VK=1,2，其中SK XK ,YKXK=0，YK =1，2，3；XK =3，YK=0,1,2,3;XK=YK=1,2, Sn+1 =(0,0) 这就是三个商人的过河问

8、题模型。3.1.3模型求解：穷举法：计算机编程（见附录）先建立编程的基本过程，然后考虑模型，再编写程序。然后就可以得出结果了。 开始变量赋值初始化判断是否完全过河选择一种可行方案，进行过河或返回，得到新的状态否判断是不是允许状态集合中的状态，并且还没在已经考虑的状态中是否还有其他状态否结束是是是主程序流程图图解法：状态s=(x,y) 16个格点允许状态 10个点允许决策 移动1或2格; k奇,左下移;k偶,右上移.xy3322110S1sn+1d1d11总共需要11步可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一

9、列。4 模型的检验用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。5 模型的拓展和延伸通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m名商人和n名随从的过河问题。6 总结这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题。学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世

10、界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。7 参考文献1傅清祥数据结构与算法王晓东北京：电子工业出版社 19982姜启瑟数学建模(第二版)北京：高等教育出版社，20003运筹学教材编写组运筹学(修订版)北京：清华大学出版社。2001附录：商仆过河的MATLAB程序及运行截屏:clear;clcn=3;%输入商人数目;nn=3;%输入仆人数目;nnn=2;%输入船的最大容量;% 决策生成 jc=1; % 决策向量存放在矩阵“d”中，jc为插入新元素的行标初始为1 for i=0:nnn for j=0:nnn if (i+j0) % 满足条件 D

11、=(u,v)|1=u+v=j)&(n-i)=(nn-j)|(i=0)|(i=n) % (i=j)&(n-i)=(nn-j)|(i=0)|(i=n)为可以存在的状态的约束条件 A(kx,1:3)=i,j,1; % 生成状态数组集合D A(kx+1,1:3)=i,j,0; kx=kx+2; end end j=nn;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 jc运行截屏：- 8 -