商人过河模型问题的求解
-
《数学建模实验》课程考试试题
----
商人安全过河数学建模与求解
一．问题提出：
4
< br>名商人带
4
名随从乘一条小船过河，小船每次自能承载至
多两人。随从们
密约
,
在河的任一岸
,
一旦随从的人数比商人多
,
就杀人越
货
.
乘船渡河的方案
由商人决定，商人
们如何才能安全渡河呢？
二．模型假设：
商人和随从都会划船
，天气很好，无大风大浪，且船的质量很好，可以保证
很多次安全的运载商人和随从。<
/p>
三．问题分析：
商随过河问题可以视为一个多步决策过程，
通过多次优化，
最后获取一个全
局最优的决策方案。
对于每一步，
即船由此岸驶向彼岸或由彼岸驶向此岸，
都要
对船上
的人员作出决策，
在保证两岸的商人数不少于随从数的前提下，
在有限步
内使全部人员过河。
用状态变量表示某一岸的人员状况
，
决策变量表示船上的人
员状况，
可以
找出状态随决策变化的规律，
问题转化为在状态的允许变化范围内
(
即安全渡河条件
)
，确定每一步的
决策，达到安全渡河的目标。
四．模型构成：
x
< br>k
~
第
k
次渡河前此岸的商人数，
y
k
~
第
k
次渡河前此岸的随从数
x
k
,
y
k
=0,1,2,3,4;
k
=1,2,
…
…
S
k
=(
x
k
,
y
k
)~
过程的状
态
,
S ~
允许状态集合，
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
次渡船上的商人数
v
k
~
第
k
次渡船上的随从数
d
k
=(
u
k
,
v
k
)~
决策，
D={(
u ,
v
)
|
1
u
v
2
,
u
k
,
v
k
=0,1,2}
~
允许决策集合
k
< br>=1,2,
…
…
因为
k<
/p>
为奇数时船从此岸驶向彼岸，
k
为偶数时
船从彼岸驶向此岸，
所以状态
S
k
随决策
d
k
的变化规律是
S
k
1
=<
/p>
S
k
+
(
1
)
k
d
k
~
状态转移律
求
d
k
∈
D(
k
=1,2,
…
n),
使
S
k
∈
S,
并按转移律由
S
1
=(4,4)
到达状态
S
n
1
=(0,0)
。
五．模型求解：
1.
图解法：
对于人数不多的情况，可以利用图解法来求解。
在
xoy
平面坐标系上画出如图所
示的方格，方格点表示状态
s=(x,y)
，允许状
态集合
S
是圆点标出的
1
3
个格子点，允许决策
d
k
是沿方格线移动
1
格或
2
格，
k
为
奇数
时向左、下方移动，
k
为偶数时向右、上方移动。要确定一系列
的
d
k
使由
S
1
=
(4,4)
经过那些圆点最终移动到原点
(0,0)
。
< br>
由初始状态
(4,4)
到原点
(0,0)
，无论怎样走，都要经过
(
2,2)
，但是无论怎样变
化人数，也只能到达此点后不能继续
走下去，只能循环走
(
由
d7
状态无法不重复
循环地走下去
)
，达不到最终的目标
(0,0)
，因此该问题无解。<
/p>
y
4
d1
3
d
d2
d1
d6
7
d2
2
d5
d4
d3
1
0
1
2
3
4
x
2.
穷举法：
根据分析可以通过编程上机求解，所用的
c
程序如下所示：<
/p>
#include
#define N 30
int
x[N],y[N],u[6],v[6],k;
/*
x,y
：状态值，分别表示此岸商人、随从数
*/
/*u,v
：决策值，分别表示船上商人、随从数
*/
/* k
：决策步数；
k
的奇偶性标志着船在河的此岸或彼岸
*/
next(int k,int
i)/*
计算下一状态
*/
{
if(k%2) /* k+1
为偶数，船从此岸到彼岸
*/
1