数学建模商人过河问题#95;#95;论文 .docx

- - PAGE #- 组长：王鹏道110714 组员:任利伟110713、孙祎110706 小组成员负责情况： 王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结 任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立 孙祎：四、模型求解、五、模型的检验、拓展及延伸 商人过河问题 2014年11月24日 摘要 为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型, 并IL加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解, 获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。 关键词：多步决策计算机求解状态转移律图解法 一、 问题的提出 随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是 乘船渡河的方案山商人决定?商人们怎样才能安金过河？ 二、问题的关键 解决的关键集中在商人和随从的数量上，以及小船的容呈上.该问题就是考 虑过河步骤的安排和数鼠上。各个步骤对应的状态及决策的表示法也是关键。 三、问题的分析 在安全的前提下(两岸的随从数不比商人多)，经有限步使全体人员过河。山 于船上人数限制，这需要多步决策过程，必须考虑每…步船上的人员。动态规划 法正是求解多步决策的冇效方法。它耍求把解的问题一层一层?地分解成一?级一 级、规模逐步缩小的子问题。直到町以亡接求出其解的了问题为止。分解成所有 了?问题按层次关系构成?棵了?问题树.树根是原问题。原问题的解依赖问题 树中所有子问题的解。 四、模型假设 记第k次过河前-A岸的商人数为Xk, 随从数为Yk k=l, 2,??? Xk,Yk=O, b 2, 3,将二维向量Sk二(Xk, YJ定义为状态.把满足安全渡 河条件下的状态集合称为允许状态集合。记作S。则 S= ((Xk, Yk) I (Xk =0, Yk =0, 1,2,3), (Xk =3, YK =0, 1,2,3), (XK =YK =1) (XK =YK =2)} 记第k次过河船上的商人数为山 随从数为Vk 将二维向§Df(Uk,Vk)定义为决策?山小船的容量可知允许决策集合(记作 D)为 D= { (Un ,Vx) I Uk +Vk=1, 2} X (0, 1) ; (0, 2); (1, 0); (1, 1); (2, 0)} 五、模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题-层一 层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解 的子问题为止。分解成所有子问题按层次关系构成i棵子问题树?树根 是原问题。原问题的解依赖于子问题树屮所冇子问题的解。 用动态规划法分析三名商人的过河问题。可得如下的递归树: K=l (1,1)A (2,2) B(1J)K-2(1,0)A(3,2)B(0,l)相同情况(0J)A(3,2)B(0?l)K=3(0.2)A(3O)B(0?3)K=4(0,1)加3,1叽2) K=l (1,1) A (2,2) B(1J) K-2 (1,0) A(3,2)B(0,l) 相同情况 (0J) A(3,2)B(0?l) K=3 (0.2) A(3O)B(0?3) K=4 (0,1) 加3,1叽2) K=5 (2.0) K=6 (U) K=7 (2.0) K=8 1 (0,1) A(0,2)B(3J) doc^V豆丁  （注解:当K为奇数时，船在B岸;当K为偶数时,船在A岸。） 通过分析该递归树，知道求解关键在于正确地写出基木的状态转移关系式和 恰当的边界条件。 因为k为奇数时，船是从A岸驶向B岸，k为偶数时。船是由B岸驶回A岸。所以 状态Sk随决策以变化的规律是 Sk刃二Sk+(-1) k D》：，k-19 2, ???, 称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题： 每一步，船由A岸驶向B岸或B岸驶回人岸，都要对船上的人员(商人山，随从 叫各儿人)作出决策，在保证安全的前提下即两岸的商人数X,都不比随从数￡少， 用冇限步使人员全部过河?用状态(变量)表示某一椁的人员状况，决策(变量)5 表示船上的人员状况，可以找出状态9随决策D.变化的规律.这样安金过河问题 就转化为： 求决策DKeD(k=l,2,……，n),使得状态ses,按照状态转移律,由初始 状态S,= (3, 3),经有限步n到达状态S的=(0,0)。 Skh=Sk+(-1):U, 21,2, 3,其中Dk eD={(UK,VK) |Uk+Vk=1, 2), {其中 丘 (X：, Yk) I (Xk=0, Yk = 1, 2, 3)； (Xk=3, Yk=0, 1,2, 3); (XK=YK = 1, 2)}, Snn = (0, 0) 这就是三个商人的过河问题模盘。 六、模型求解： 穷举法：先建立编程的基本过程，然