商人过河问题数学建模
-
作业
1
、
2
：
商人过河
一、
问题重述
问题一：
< br>4
个商人带着
4
个随从过河，过
河的工具只有一艘小船，只能同
时载两个人过河，
包括划船的人
。
随从们密约
,
在河的任一岸
,
一旦随从的人数
比商人多
,
就杀人越货。
乘船渡河的方案由商人决定。
商人
们怎样才能安全过河
?
问题二：
假如
小船可以容
3
人，
请问最多可以有几名
商人各带一名随从安全
过河。
二、问题分析
问题可以看做一个多步
决策过程。
每一步由此岸到彼岸或彼岸到此岸船上的
人员在安全
的前提下
(
两岸的随从数不比商人多
)
,
经有限步使全体人员过河。
用状
态变
量表示某一岸的人员状况，
决策变量表示船上的人员情况，
可以
找出状态随
决策变化的规律。问题就转换为在状态的允许变化范围内（即安全渡河条件）
，
确定每一步的决策，达到安全渡河的目标。
< br>
三．问题假设
1.
过河途中不会出现不可抗力的自然因素。
2.
当随从人数大于商人数时，随从们不会改变杀人的计划。
3
．船的质量很好，在多次满载的情况下也能正常运作。
4.
随从会听从商人的调度。
四、模型构成
x(k)~
第
k
次渡河前此岸的商
人数
x(k),y(k)=0,1,2,3,4;
y(k)~
第
k
次渡河前此岸的随从数
k=1,2,
…
..
s(k)=[ x(k),
y(k)]~
过程的状态
S~
允许状态集合
< br>S={(x,y)
x=0,y=0,1,2,3,4;
x=4,y=0,1,2,3,4;x=y=1,2,3}
u(k)~
第
k
次渡船上的商人数
u(k), v(k)=0,1,2;
v(k)~
第
k
次渡船上的随从数
k=1,2
…
..
d(k)=( u(k),
v(k))~
过程的决策
D~
允许决策集合
< br>D={u,v
u+v=1,2,u,v=0,1,2}
状态因决策而改变
s(k+1)=s(k)+(-1)^k*d
(k)~
状态转移律
求
d(k)
D(k=1,2,
…
.n),
使
s(k)
S
并按转移律
s(k+1
)=s(k)+(-1)^k*d(k)
由（
4,4
）到达（
0,0
）
随从
y
商人
x
D
k
（
1
）
数学模型
：
S
k+1
=S
k
+
（
-1
）
k
x
k
x
k
'
4
（
2
）
y
k
y
k
'
4
（
3
）
x
k.
y
k
（
4
）
x
k
'
y
k
'
（
5
）
模型分析：
由（
2
）
（
3
）
（
5
）可得
4
< br>
x
k
化简得
< br>
4
y
k
x
k
y
k