商人过河matlab程序以及解析

重庆大学

（商仆过河模型）

开课课程：数学模型 指导教师：黄光辉

小组成员：庄楚斌（20134760）自动化07班

张俊铭（20133227）材料加工01班 吴慧（20131966）数学01班

时间：2015年3月8日

一、问题提出

3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？

二、问题分析

商人与随从过河问题可以视为是一个多步决策的过程，通过多次

优化，从而得到一个全局最优的决策方案。决策的每一步，即船从此岸到达彼岸，都要对船上的商人和仆人数做出决策。在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下，经有限步使所有人员到达彼岸。

三、模型假设

商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，

可以保证很多次安全的运载商人和随从。

四、模型建立

xk~第k次渡河前此岸的商人数，yk~第k次渡河前此岸的随从数

xk, yk=0,1,2,3; k=1,2,… …

Sk=(xk, yk, ck )~过程的状态，其中xk, yk, ck 分别表示对应时刻此

岸的商人，仆人数以及船的行进方向，其中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次渡船上的商人数 vk~第k次渡船上的随从数

dk=(uk, vk)~决策，D={(u , v)| 1?u?v?2,uk, vk=0,1,2} ~允许决策集

合

k=1,2,… …

因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶向此岸，所以状态Sk随决策dk的变化规律是

Sk?1=Sk+(?1)kdk~状态转移律

求dk∈D(k=1,2, …n), 使Sk∈S, 并按转移律由S1=(3,3,1)到达状态Sn?1=(0,0,0(1))。

五、模型求解

本模型使用MATLAB软件编程， 通过穷举法获得所有可能的决策方案如下(完整matlab程序详见附录):

第一种： 第二种：

第三种： 第四种：

六、模型的推广

该商人、随从过河模型可以完美解决此类商仆过河的决策问题，并且该模型还可推广至解决m个商人和n个随从过河，以及小船的最大载重人数改变时的问题，只需适当地改变相关的语句即可轻松实现模型的转换。

如当商人数和随从数均为4，小船最大载重人数为2时，matlab程序运行的结果如下(程序改动详见附录):

推广过程只需要将其中的 (x,y)（限定范围）改成相对应的情况即可，例如，商人基于仆人数都为4时允许状态集合，S={(x , y)| x=0, y=0,1,2,3,4; x=4 ,y=0,1,2,3,4; x=y=1,2,3}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库商人过河matlab程序以及解析在线全文阅读。