文档介绍：(商仆过河模型)
开课课程:数学模型指导教师:黄光辉
小组成员:庄楚斌(20134760)自动化07班张俊铭(20133227)材料加工01班吴慧(20131966)数学01班
时间:2015年3月8日
一、问题提出
小船(至多2人)
3名商人带3名随从乘一条小船过河,小船每次只能承载至多两人。随从们密约,在河的任一岸,一旦随从的人数比商人多,
AAA 3名商人 XXX 3名随从
就***,商人们如何才能安全渡河呢?
二、问题分析
商人与随从过河问题可以视为是一个多步决策的过程,通过多次优化,从而得到一个全局敁优的决策方案。决策的每一步,即船从此岸到达彼岸,都要对船上的商人和仆人数做出决策。在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下, 经有限步使所有人员到达彼岸。
三、模型假设
商人和随从都会划船,天气很好,无大风大浪,且船的质量很好, 可以保证很多次安全的运载商人和随从。
四、模型建立
〜第A;次渡河前此岸的商人数,〜第A:次渡河前此岸的随从数
Xk, y々=0,l,2,3;/c=l,2,
Sk =(xk, >7, Q)〜过程的状态,其中xA.,h,Q分别表7F对应时刻此库的商人,仆人数以及船的行进方向,其中C取值1表示即将向彼岸运行, 为0表示即将向此岸运行
S 〜允许状态集合,S={(x, y) | x=0, j=04,2,3; x=3^=0,l,23; x=j=l,2}
Uk〜第A:次渡船上的商人数
V,〜笫々次渡船上的随从数
dk=、uk,人)〜决策,D={(M,V)| 1<m + v<2, ukJ h =0,1,2}〜允许决策集合
众=1,2,
因为k为奇数时船从此岸驶向彼岸,k为偶数时船从彼岸驶向此岸, 所以状态随决策< 的变化规律是
5a+1 = 5, + (-1)a么〜状态转移律
求AED(*=1,2, •••!!),使久ES,并按转移律由S,=(3,3,l)到达状态s,,+1 =(0,0,0⑴)。
五、模型求解
本模型使用MATLAB软件编程,通过穷举法获得所有可能的决策方案
如下(完整mat lab程序详见附录): 第一种: 第二种:
essfully found!
每一次的此岸人员分布:
:商人
仆人
第1次
3
3
第2次
2
2
第3次
3
2
第4次
3
0
第5次
3
1
第6次
1
1
第7次
2
2
第8次
0
9
第9次
0
3
第10次
0
1
第11次
1
1
第12次
0
0
第三种:第四种:
esstu丄丄y tound:
每一次的此岸人员分布:
商人
仆人
第1次
3
3
第2次
3
1
第3次
3
9
第4次
3
0
第5次
3
1
第6次
1
1
第7次
‘?
9
第8次
0
9
第9次
0
3
第10次
0
1
第11次
1
1
第12次
0
0
esstu丄丄y found!
每一次的此岸人员分布:
商人
仆人
第1次
3
3
第2次
3
1
第3次
3
9
第4次
3
0
第5次