对商仆过河问题数学建模论文.docx

数
学
建
模
题目:商仆过河问题
组员:

班级:
指导老师:
目录
摘要………………………………………………………3
问题的提出…………………………………………..3
问题的分析…………………………………………..4
模型的假设…………………………………………..5
模型的建立与解.………………………………....5
模型的符号…………………………………………..6
模型的解……………………………………………….6
模型的图解…………………………………….……..8
关于C语言的程序算法…………………..…..10
模型的优缺点…………………………………..14
参考文献……….…………………………………15

摘要:
本文针对商人安全渡河问题,采用多步决策的过程建立数学模型,求解得到了在随从没杀人越货的情况下的渡河方案。
对于本题而言,在3(15)对商仆、船最大容量为2(8)人的情况下,首先定义了渡河前此岸的状态,并设安全渡河条件下的状态集合定义为允许状态集合,接着得到渡河方案的允许决策集合,然后得到状态随从渡河方案变化的规律。利用c软件编译运行程序得到了一种商人安全渡河的方案,并输出了允许的状态向量和允许的决策向量。
关键词:船载量、允许状态向量、允许决策向量
问题的提出
仆人们密约,在河的任何一边,只要仆人的数量超过商人的数量,仆人就会联合起来将商人杀死并抢夺其财物,三名商人各带一个随从乘船渡河,一只小船只能容纳两人,由他们自己划行。在河的任意一岸,一旦随从的人数比商人多,。商人们怎样才能安全渡河呢?同时,推广到十五名商人带十五名随从又如何?
问题的分析
安全渡河问题可以看成一个多步决策过程,船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员(商人随从各几人)作出决策。
状态向量:用二维坐标向量表示(商,仆):0<=H<=3(11), 0<=S<=3(11),
例如:(3,3,)(5,0)(6,4)等均成立
允许向量:由题意可知,仆人数少于商人数被选定为允许向量。
运载向量:利用二维向量(m,n)表示船只上的商仆数量。
可行的运载向量:满足二维向量(m,n),0<=n<=m<=3(15)。
枚举所有可能的算法:(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)(8,0)(1,1)(2,2)(3,3)(4,4)(2,1)(3,2)(4,3)
可取用状态向量:利用穷举法表示状态,利用递归算法进行模型的建立与运算
运载向量:使用二维向量进行表示(商,仆):0<=商<=3(11),0<=仆<=3(11)
该模型使用逻辑运算法则进行数学模型的建立
模型的假设
每个商人和他的随从均会划船
只有一条船,且船只的承载数量为8人
船在划行的状况下不受任何的外力干扰
(4)不存在任意几人不能同时坐船的情况
模型的建立与解
由题目可知,3(15)对商仆过河,船载量为2(8)人,现记第K次渡河前的商人数为Xk,仆人数为Yk,k=1,2,…,(2)8,再记一组二维向量Ak=(Xk,Yk),Ak为给定时的状态量,可记做C的表达式为:
C={(x,y)|x=0,y=0,1,…,(3)15=y=0,1,…,(3)15=y=0,1,…,(3)15
再记第K次渡河时船上的商人数为uk,仆人数为vk,记二维向量Bk=(uk,vk),可知小船此时的运载为D,D的表达式为;
D ={(u,v)|1<=u+v<=2(8),u,v=0,1,…,2(8)}
由上题目中的题意可知第K+1次时的情况为E :
E=Ak+(-1)^k*Dk最终直到3(15)对商仆全部过河时完成问题
模型的符号
A 表示起始状态下商仆所在一岸
B 表示末状态商仆所在一岸
S 表示商仆的对数
K 表示船最多的载人数
C 渡河时的一侧岸边的商仆数
D 小船运载的商仆数量
E 第k次渡河是的商仆数量
Ak 河岸一边的商人数
Bk 河岸一边的仆人数
Ck 河岸另一边的商人数
Dk 河岸另一边的仆人数
模型的解
利用程序框图来解决过河问题
根据题意状态转移必须满足以下规则;
(1). Z从1变0或0变1交替进行。
(2).Z从1变为0即从河的此岸到彼岸,此案的人数减少1或2;即(m,n,1) →(u,v,0)时,两岸的人数满足m>=n且u>=v,且m+n-1=u+v 或m+n-2=u+v。
(3) Z从0变为1时,即从河的彼岸到此案,则此案的人数增加1或2;即(u,v,0) →(m,n,1)时,两岸的人数满足m>=n , u>=v ,m+n+1=u+v或m+n+2=u+v。