商人安全过河-中学数学建模方法

三名商人各带一名随从乘船渡河，一只小船只能容纳两人，且由他们自己划行.随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货.但是如果乘船渡河的大权掌握在商人们手中，商人们怎样渡河才能安全呢[1]？

对于这类智力游戏，经过一番逻辑思索是可以找出解决办法的.这里用数学模型求解，一是为了给出建模的示例，二是因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推广.

由于这个虚拟的问题已经理想化了，所以不必再作假设.安全渡河问题可以视为一个多步决策过程.每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员（商人、随从各几人）作出决策，在保证安全的前提（两岸的随从人数都不比商人人数多）下，在有限步内使全部人员过河.用状态（变量）表示某一岸的人员状况，决策（变量）表示船上的人员状况，可以找出状态随决策变化的规律，此时问题转化为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到渡河的目标.

【模型构建】

记第k次渡河前此岸的商人人数为xk，随从人数为yk(k=1，2，…)，xk，yk=0，1，2，3.将二维向量sk=(x k，yk )定义为状态.安全渡河条件下的状态集合称为允许状态集合，记作S.

不难验证，S对此岸和彼岸都是安全的.

记第k次渡河时，船上的商人人数为uk，随从人数为vk.将二维向量dk=(uk，vk)定义为决策.允许决策集合记作D，由小船的容量可知

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

（4.1.3）式称为状态转移律.这样，制订安全渡河方案可归结为如下的多步决策模型：

求决策kd D∈(k=1，2，…，n)，使状态ks S∈按照转移律（4.1.3），由初始状态s1=(3，3)经n步到达最终状态sn+1=(0，0).

【模型求解】

解法1　本题商人和随从人数不大，用图解法可以很方便地解这个模型.

在xOy平面坐标系上画出图4.1.1所示的方格，方格点表示状态s=(x，y).允许状态集合S是用圆点标出的10个格子点.允许决策dk是沿方格线移动1或2格，k为奇数时向左、下方移动，k为偶数时向右、上方移动.要确定一系列的dk，使由s1=(3，3)经过哪些圆点最终移至原点(0，0).

图4.1.1　安全渡河问题的图解法(www.xing528.com)

图4.1.1给出了一种移动方案，经过决策d1，d2，…，d11，最终有s12=(0，0).这个结果很容易翻译成渡河的方案.

解法2　根据（4.1.1）～（4.1.3）式编一段程序，用计算机求解上述多步决策问题是可行的.一个穷举模拟算法的MATLAB代码如下：

主函数脚本duhe:

function d=duhe(p)

%p和q分别为此岸和对岸的状态向量

%s1和s2分别为划过去和划回来的决策向量

%d为决策矩阵

模拟划过去过程的子函数go:

模拟返回过程的子函数back:

在MATLAB中运行d=duhe([3 3])，即可得到本问题的决策向量.

此问题中的决定因素包含商人和随从人数以及船容量，不妨将其分别设为n1，n2，n3，此类问题记为Q(n1，n2，n3)，请读者尝试用上述方法研究一下Q(4，4，2)，Q(4，4，3)，Q(4，3，2)，…，考察一下有没有什么规律[4]？该问题的第三种解法见第八章第二节.

评注：这里介绍的是一种规格化的方法，所建立的多步决策模型可以用计算机求解，从而具有推广的意义.譬如当商人和随从人数增加或小船的容量加大时，靠逻辑思考就困难了，而用这种模型则可方便地求解.