16757数学模型课件北邮12.pdf

商人过河商人过河商人过河

设有三名商人，各带一个随从，欲乘一小船渡河，小船只能容纳两人，须由

他们自己划行。随从们密约，在河的任何一岸，一旦随从的人数比商人多，就杀

人越货。而如何乘船渡河的大权掌握在商人们的手中。商人们怎样才能安全渡河

呢？

因这已经是一个相当清晰的理想化问题，所以直接讨论其模型描述以及模型

求解。这里将其描述为一个动态决策问题：

记第k次渡河前此岸的商人数为，随从数为,k=1,…,n。将二维向量xkyk

s(x,y)kkk定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作

S,S{(x,y)|x0,y0,1,2,3;x3,y0,1,2,3;xy1,2}。

记第k次渡船上的商人数为uk，随从数为,k=1,…,n。将二维向量vk

d(u,v)定义为决策。考虑小船载人数的限制，d(u,v)应满足

kkkkkk

uv1或2，u,v为非负整数，而称D{(u,v)|uv1,2;u,v为非负整数为非负整数}

kkkk

为允许决策集合。

因为k为奇数时，船从此岸驶向彼岸；k为偶数时，船从彼岸驶回此岸，所

sdss(1)dk

以状态随决策的变化规律是kkk1kk（状态转移规律）。

求决策dD,k1nk，使状态sSk按照状态转移规律，由初始状态

s(3,3)1经有限步n到达状态sn11(0,0)。

接下来讨论模型的求解，设ssssss是某个可行的渡河方案所

12ijnn1

对应的状态序列，若存在某i,j(1ijn)，且同为奇数或同为偶数，满足

ss，则称ssssss所对应的渡河方案是可约的。这时

ij12ijnn1

ssssss也是某个可行的渡河方案所对应的状态序列。显然，一个有

12ij1nn1

效的渡河方案应当是不可约的。

设渡河已进行到第k步，s(x,y)kkk为当前的状态，记

Sk(1)s|1ik,i为奇数i，Sk(2)s|1ik,i为偶数i，为保证构造的渡河

方案不可约，则当前的决策d(u,v)除了应满足：

kkk

1）dD，且当k为奇数时，ux,vy，当k为偶数时，

kkkkk

u3x,v3y

kkkk；

还须满足：

2）当k为奇数时，sSkk(2)；当k为偶数时，sSkk(1)。

通过作图，可以得到两种不可约的渡河方案，如下图：

思考题：思考题：

（1）四名商人各带一名随从的情况（小船同前）。

（2）n名商人各带n名随从的情况（小船同前）。

商人过河商人过河商人过河

设有三名商人，各带一个随从，欲乘一小船渡河，小船只能容纳两人，须由

他们自己划行。随从们密约，在河的任何一岸，一旦随从的人数比商人多，就杀

人越货。而如何乘船渡河的大权掌握在商人们的手中。商人们怎样才能安全渡河

呢？

因这已经是一个相当清晰的理想化问题，所以直接讨论其模型描述以及模型

求解。这里将其描述为一个动态决策问题：

记第k次渡河前此岸的商人数为，随从数为,k=1,…,n。将二维向量xkyk

s(x,y)kkk定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作

S,S{(x,y)|x0,y0,1,2,3;x3,y0,1,2,