当商人和随从数都不多的情况下，用图 解法解此模型更为方便。
03.05.2020
A
5
建模实例
在xoy坐标系上画出方格，方格点上的 坐标同时也表示状态
s = ( x , y ). 允许状态集是沿方格线移动1或2格，k 为奇数时向左、下方移动，k为偶数时 向右、上方移动。 要确定一系列的dk使由s1=(3,3)经过那 些点最终移至原点（0，0）
S={(x,y) | x=0,3;y=0,1,2,3或x=2,y=0,1,2或x=1;y=0,1}
03.05.2020
A
3
建模实例
记第k次渡船上的商人数为uk ,随从数为vk 将二维向量dk=(uk,vk)定义为决策,允许决 策集合记作D,由小船的容量可知
D={（u,v）| u + v = 1 , 2 }
用状态变量表示某一岸的人员状况，决策变量表示 船上的人员状况，可以找出状态随决策变化的规律。 问题转化为在状态的充许变化范围内，确定每一步 的决策模实例
模型的生成过成： 记第k次渡河前此岸的商人数为xk,随从数为yk, k=1,2,……，xk , yk =0,1,2,3， 将二维向量sk=(xk,yk)定义为状态,安全渡河 条件下的状态集称为允许状态集合，记作S， 不难写出
建模实例
商人怎样安全过河？
三名商人各带一个随从乘船渡河，一只小 船只能容纳二人，由他们自已划行，随从 们密约，在河的一岸，一旦随从的人数比 商人多，就杀人越货，但是如何乘船渡河 大权掌握在商人手中，商人们怎样才能安 全渡河呢？
03.05.2020
A
1
建模实例
安全渡河问题可以视为一个多步决策过程。每一步 即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船 上的人员作出决策，在有限步内使人员全部过河.
03.05.2020
A
6
建模实例
03.05.2020
A
7
建模实例
03.05.2020
A
8
建模实例
评注
这里介绍的模型是一种规格化的方法， 使我们可以用计算机求解，从而具有广 泛意义.譬如当商人和随从人数增加或小 船容量加大时，靠逻辑思考就困难了， 而这种模型则仍可方便地求解
03.05.2020
A
9
谢谢
03.05.2020
A
10
因为k为奇数时船由此岸驶向彼岸， k为偶数时船由彼岸驶回此岸，所以 状态sk 随决策dk变化的规律是：
sk+1 = sk + (-1) k d k
03.05.2020
A
4
建模实例
求 决 策 dk∈D (k=1,2,……n) ， 使 状 态 sk∈S ， 按 照 转 移 规 律 ， 由 初 始 状 态 s1=(3,3)经有限n步后到达状态sn+1=(0,0). 模型求解