必威体育精装版商人过河matlab程序以及解析.pdfVIP

精品文档 重庆大学 （商仆过河模型） 开课课程：数学模型 指导教师：黄光辉 小组成员：庄楚斌（ 自动化 07 班 张俊铭（材料加工 01 班 吴慧（数学 01 班 时间： 2015 年 3 月 8 日 精品文档 精品文档 一、问题提出 3 名商人带 3 名随从乘一条小船过河，小船每次只能承载至多两 人。随从们密约 , 在河的任一 岸 , 一旦随从的人数比商人多 , 就杀人越货 . 乘船渡河的方案 由商人决定，商人们如何才能 安全渡河呢？ 二、问题分析 商人与随从过河问题可以视为是一个多步决策的过程，通过多次 优化，从而得到一个全局最优的决策方案。决策的每一步，即船从此 岸到达彼岸， 都要对船上的商人和仆人数做出决策。 在保证河的任一 岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下， 经有限步使所有人员到达彼岸。 三、模型假设 商人和随从都会划船， 天气很好，无大风大浪， 且船的质量很好， 可以保证很多次安全的运载商人和随从。 四、模型建立 xk ~第k次渡河前此岸的商人数， y k ~第 k次渡河前此岸的随从数 x k , yk =0,1,2,3; k=1,2,… … S =( x , y , c )~过程的状态，其中 x , y , c 分别表示对应时刻此 k k k k k k k 精品文档 精品文档 岸的商人， 仆人数以及船的行进方向， 其中 c取值 1表示即将向彼岸运 行，为 0表示即将向此岸运行 S ~ 允许状态集合， S={(x , y)| x=0, y=0,1,2,3; x=3 ,y=0,1,2,3; x=y=1,2} uk ~第k次渡船上的商人数 v k ~第k次渡船上的随从数 d k =( u k , v k )~决策， D={( u , v)| 1 u v 2 , uk , v k =0,1,2} ~允许决策集 合 k=1,2,… … 因为 k为奇数时船从此岸驶向彼岸， k为偶数时船从彼岸驶向此岸， 所以状态 S 随决策 d 的变化规律是 k k Sk 1 = Sk + ( 1) k dk ~状态转移律 求 d ∈D(k=1,2, …n), 使 S ∈S, 并按转移律由 S =(3,3,1)到达状态 S k k 1 n 1 =(0,0,0(1)) 。 精品文档 精品文档 五、模型求解 本模型使用 MATLAB软件编程， 通过穷举法获得所有可能的决策方案 如下 ( 完整 matlab 程序详见附录 ): 第一种： 第二种： 第三种： 第四种： 精品文档 精品文档 六、模型的推广 该商人、随从过河模型可以完美解决此类商仆过河的决策问题， 并且该模型还可推广至解决 m 个商人和 n 个随从过河，以及小船的 最大载重人数改变时的问题， 只需适当地改变相关的语句即可轻松实 现模型的转换。 如当商人数和随从数均为 4 ，小船最大载重人数为 2 时， matlab 程序运行的结果如下 (程序改动详见附录 ): 推广过程只