商仆过河问题——数学建模.doc

word
word
1 / 20
word
商仆过河问题
*学院 **班 *** ********** **号
2014年12月4日
word
word
2 / 20
word
摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进展求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。
关键词：多步决策 计算机求解 状态转移律 图解法 MATLAB程序
一、问题的提出
S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？
二、问题的关键
解决的关键集中在商人和随从的数量上，以与小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态与决策的表示法也是关键。
三、问题的分析
在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
四、 模型假设
记第k次过河前A岸的商人数为XK，随从数为YKk=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)}
记第k次过河船上的商人数为UK，随从数为VK
将二维向量DK=(UK ,VK)定义为决策．由小船的容量可知允许决策集合〔记作D)为 D={(UK ,VK)|UK +VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}
word
word
3 / 20
word
五、模型建立：
动态规划是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
用动态规划法分析三名商人的过河问题。可得如下的递归树：
word
word
4 / 20
word
K=1
A(3,2)B(0,1)
A(3,2)B()
K=2
A〔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=4
K=5
(0,1)
(2,0)
A(1,1)B(2,2)
K=6
A(2,2)B(1,1)
K=7
=
A(0,2)B(3,1)
K=8
(0,1)
word
word
5 / 20
word
〔转下页〕
word
word
6 / 20
word
A(0,3)B(3,0)
K=9
(0,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=10
K=11
〔注解：当K为奇数时，船在B岸；当K为偶数时，船在A岸。〕
通过分析该递归树，知道求解关键在于正确地写出根本的状态转移关系式和恰当的边界条件。
word
word
7 / 20
word
因为k为奇数时，船是从A岸驶向B岸，k为偶数时。船是由B岸驶回A岸。所以状态SK随决策DK变化的规律是
SK+1=SK+(-1)K DK，k=l，2，⋯，
称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题：
每一步，船由A岸驶向B岸或B岸驶回A岸，都要对船上的人员(商人UK，随从VK各几人)作出决策，在保证安全的前提下即两岸的商人数XK都不比随从数YK少，用有限步使人员全部过河．用状态(变量)SK表示某一岸的人员状况，决策(变