- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数学建模商人过河问题__论文
组长:王鹏道 110714
组员:任利伟110713、孙祎110706
小组成员负责情况:
王鹏道:选择论文题目、设计论文版面字体、分配成员任务、总结
任利伟:一、问题提出、关键、分析。二、模型假设、三、模型建立
孙祎:四、模型求解、五、模型的检验、拓展及延伸
2014年11月24日
摘 要
为了求解3个商人和3个随从的过河问题,用数学分析方法,建立数学模型,并且加以求解,展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解,获得过河问题的完整求解过程;有效地求解类似多步决策问题的作用。
关键词:多步决策 计算机求解 状态转移律 图解法
问题的提出
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?
问题的关键
解决的关键集中在商人和随从的数量上,以及小船的容量上,该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。
三、 问题的分析
在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制,这需要多步决策过程,必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树.树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
四、 模型假设
记第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为奇数时,船在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表示船上的人员状况,可以找出状态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)
这就是三个商人的过河问题模型。
模型求解:
穷举法:先建立编程的基本过程,然后考虑模型,再编写程序
然后就可以得出结果了
主程序流程图
图解法:状态s=(x,y) 16个格点
允许状态 10个●点
允许决策 移动1或2格; k奇,左下移;右下移
总共需要11步
七、模型的检验
用2名商人和2名随从的过河问题的解决思路,检验3名商人和3名随从的过河问题。
八、 模型的拓展和延伸
通过三名商人和三名随从的过河问题的解决方案,可以进一步计算四名商人和四名随从的过河问题,通过计算机编程可以设计m名商人和n名随从的过河问题。这需要用多步决策
九、总结
这是通过数学分析的方法解决实用问题,经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程,解决商人过河问题。然后扩
您可能关注的文档
- 插花知识与技能.ppt
- 摄影协会炫彩杯活动策划书.doc
- 提高直排式真空预压密闭真空管网连接合格率.ppt
- 携带式电源项目创业计划.ppt
- 摄影论文论纪实摄影的人文关怀.doc
- 摇摇棒的制作与调试生产实习报告.doc
- 摄影的技术美与艺术美(孙佳慧).ppt
- 搅拌站安全知识讲座讲义.doc
- 摇臂加工工艺规程及夹具设计.doc
- 摇钱树垭煤矿井下安全避险“六大系统”专项设计.doc
- 低空物流无人机应用中的物流配送网络布局与优化报告.docx
- 2025年新能源汽车换电技术专利分析报告[001].docx
- 金融科技合规风险防控策略研究:2025年案例分析与应对措施.docx
- 新能源电动冷藏配送在冷链物流网络中的冷链物流信息化平台建设报告.docx
- 2025年化工行业安全生产管理现状与安全风险防控体系构建策略报告.docx
- 美妆电商全渠道运营策略研究报告.docx
- XX企业2025年数字化转型与产业链协同创新研究报告.docx
- 资质认证某行业企业资质证明书(8篇).docx
- 《血液透析血管通路并发症的药物干预与临床观察》教学研究课题报告.docx
- 钢铁企业2025年绿色生产技术革新与节能降耗效果案例分析报告.docx
文档评论(0)