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

商仆过河问题
作者:*学院**班*** ********** **号
2014年12月4日
摘要:为了求解3个商人和3个随从的过河问题,用数学分析方法,建立数学模型,并且加以求解,展示动态规划思想的应用步骤。最后利用计算机编程进行求解,获得过河问题的完整求解过程;有效地求解类似多步决策问题的作用。
关键词:多步决策计算机求解状态转移律图解法 MATLAB程序
一、问题的提出
S个商人各带一个随从乘船过河,一只小船只能容纳K人,由他们自己划船。商人们窃听到随从们密谋,在河的任意一岸上,只要随从的人数比商人多,就杀掉商人。但是如何乘船渡河的决策权在商人手中,商人们如何安排渡河计划确保自身安全?
二、问题的关键
解决的关键集中在商人和随从的数量上,以及小船的容量上,该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。
三、问题的分析
在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制,这需要多步决策过程,必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。。原问题的解依赖于子问题树中所有子问题的解。
四、模型假设
记第k次过河前A岸的商人数为XK,随从数为YK 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)}
记第k次过河船上的商人数为UK,随从数为VK
将二维向量DK=(UK ,VK)(记作D)为 D={(UK ,VK)|UK +VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}
五、模型建立:
动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。。原问题的解依赖于子问题树中所有子问题的解。
用动态规划法分析三名商人的过河问题。可得如下的递归树:
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)
(转下页)
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岸。)
通过分析该递归树,知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。
因为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表示某一岸的人员状况,决策(变量)DK表示船上的人员状况,:
求决策DK∈D(k=1,2,……,n),使得状态SK∈S,按照状态转移律,由初始状态S1=(3,3),经有限步n到达状态SK+1=(O,O)。
模型建立:
SK+1=SK+(-1)KDK,k=l,2,3,其中DK ∈D={(UK ,VK)|UK +VK=l,2},{其中SK ∈(XK ,YK)|(XK=0,YK =1,2,3);(XK =3,YK=0,1,2,3);(XK =YK =1,2)},Sn+1 =(0,0)
这就是三个商人的过河问题模型。
六、模型求解:
穷举