例2 商人怎样安全过河?
三名商人各带一个随从乘船渡河,一只小 船只能容纳二人,由他们自已划行,随从们密约,在河的一岸,一旦随从的人数比商人多,就杀人越货,但是如何乘船渡河大权掌握在商人手中,商人们怎样才能安全渡河呢?
这里是要用数学方法求解,一是为了给出建模的示例,二是因为这类模型可以解决相当广泛的一类问题,比逻辑思索的结果容易推广.
由于问题已经理想化了,所以不必再作假设.安全渡河问题可以视为一个多步决策过程.每一步即船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员作出决策,在保证安全的前题下,在有限步内使人员全部过河,
用状态变量表示某一岸的人员状况,决策变量表示船上的人员状况,可以找出状态随决策变化的规律.问题转化为在状态的充许变化范围内,确定每一步的决策,达到渡河的目标
模型的过成：
记第k次渡河前此岸的商人数为xk随从数为yk,k=1,2,……,xk ,yk =0,1,2,3,将二维向量sk=(xk,yk)定义为状态,
安全渡河条件下的状态集称为允许状态集合,记作S,不难写出
S={（x,y）|x=0,y=0,1,2,3; x=y=1,2} - (1)
记第k次渡船上的商人数为uk ,随从数为vk ,将二维向量dk = (uk,vk)定义为决策,允许决集合记作D,由小船的容量可知
D={（u,v）| u + v = 1 ,2 }- (2)
因为k为奇数时船由此岸驶向彼岸,k为奇数时船由彼岸驶回此岸,所以状态sk 随决策dk变化的规律是：
sk+1 = sk + (-1) k d k - (3)
(3)式称状态转移律,这样,制定安全渡河方案归结为如下的多步决策问题：
求决策dk∈D (k=1,2,……n),使状态sk∈S按照转移规律（3）,由初始状态s1=(3,3)经有限n步后到达状态sn+1=(0,0).
根据（1）~（3）式通过计算机编写一段程序来求解多步决策问题是可行的,不过当商人和随从数都不多的情况下还可以用图解法解此模型更为方便.
