第三章初等数学模型

初等数学模型v 1. 商人安全过河模型商人安全过河模型v 2. 人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型商人安全过河模型商人安全过河模型问题的提出v 三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。v 随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。v 如何乘船渡河的大权掌握在商人们手中，v 商人们怎样才能安全渡河呢 ?数模求解的意义v 对于这类智力游戏，经过一番逻辑思索是可以找出解决办法的。v 这里用数学模型求解， 一是为了给出建模的示例， 二是因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推广。问题分析：v 由于这个虚拟的问题己经理想化了，所以不必再作假设。v 安全渡河问题可以视为多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员 (商人、随从各几人 )作出决策v 在保证安全的前提下 (两岸的商人数都不比随从数少 )，在有限步内使人员全部过河。变量的确定v 用状态 (变量 )表示某一岸的人员状况，决策 (变量 )表示船上的人员状况，可以找出状态随决策变化的规律。v 问题转化为在状态的允许变化范围内 (即安全渡河条件 )，确定每一步决策，达到渡河目标。模型构成 v 记第 k次渡河前此岸的商人数 为 xk， 随从 数为 yk，k=l， 2， ， xk,yk=0， 1， 2， 3。v 将二维向量 sk=(xk,yk)定义为状态v 安全渡河条件下的状态集合称为允许状态集合 ，记作 S。 不难写出S= (x,y)|x=0, y= 0， 1， 2， 3;x=3, y=0， 1， 2， 3;x=y=1， 2 (1)状态 sk随决策 d k变化的规律v 记第 k次渡船上商人数为 u k， 随从数 为 v kv 将二维向量 dk=(uk,vk)定义为决策 .允许决策集合记作 D， 由小船的容量可知D= (u， u)|u+v=l， 2 (2)v 因为 k为奇数时船从此岸驶向彼岸， k为偶数时船由彼岸驶回此岸，所以状态 sk随决策 d k变化的规律是s k+1= s k +(-1)kd k (3)(3)式称状态转移律。商人安全过河的数学模型（ 多步决策模型） :v 求决策 d kD(k=1， 2， ,n) ，使状态 s k S按照转移律 (3):s k+1= s k +(-1)kd k由初始状态 s 1=(3,3)经有限步 n到达状态 s n+1=(0,0)。由状态 (3， 3)经 n(奇数 )步决策转移到 (0， 0)的转移过程v 具体转移步骤如下 :(0， 1) (3， 2) (0， 2) (3， 1) (3， 3) + (-1)1 (1， 1) (2 ， 2) (1， 0) (2， 3) (2， 0) (1， 3) v 再将 (3， 2)， (3， 1)， (2， 2)分别与决策向量进行运算。如此下去，不难验证，经过 11次决策可取运算后即可完成。v 当 k为奇数时， dk表示从此岸到彼岸，当 k为偶数时，表示从彼岸回到此岸。模型求解 v 根据 (1)-(3)式编一段程序，用计算机求解上述多步决策问题是可行的。v 对于商人和随从人数不大的简单状况，用图解法解这个模型更为方便。v y（随从数） 3 (3,3) o x (商人数 ) 1 2 3 图 1-3 安全渡河问题的图解法（共四种）图解法决策的步骤v 在 xoy平面坐标系上画出图 1-3那样的方格，方格点表示状态 s=(x,y)。v 允许状态集合 S是圆点标出的 10个格子点。v 允许决策 d是沿方格线移动 1或 2格， k为奇数时向左、下方移动， k为偶数时向右、上方移动。v 要确定一系列 的 d k使由 s 1=(3， 3)经过那些圆点最终移至原点 (0， 0)。课堂 (后 )数模练习v 试在图 1-3中给出一种移动方案，即经过决策d 1,d 2， ， d n， 最终 有 s n+1=(0， 0)。v 将该结果翻译成渡河的方案。评 注 v 这里介绍的模型是一种规格化的方法，使我们可以用计算机求解，从而具有推广的意义。v 譬如当商人和随从人数增加或小船的容量加大时，靠逻辑思考就困难了，而用这种模型则仍可方便地求解。v 另外，适当地设置状态和决策，并确定状态转移律，是有效地解决很广泛的一类问题的建模方法，在以后还可能要用到。人、狼、羊、菜渡河模型问题的提出v 一摆渡人 F希望用一条小船把一只狼 W， 一头羊 G和一篮白菜 C从一条河的左岸渡到右岸去，而船小只能容纳 F、 W、 G、 C中的两个，决不能在无人看守的情况下，留下狼和羊在一起，羊和白菜在一起，v 应怎样渡河才能将狼、羊、白菜都运过去 ?v 这是一个有趣的智力游戏问题，显然可用递推方法解决，但我们把此问题化为状态转移问题来解决。状态向量的表示 v 将人、狼、羊、菜依次用一个四维向量表示，当一物在左岸时，记相应的分量为 1，否则记为 0，如 A(1,0,1,0)表示人和羊在左岸，并称为一个状态v 由问题中的限制条件，有些状态是允许的，有的是不允许的。v 凡系统可以允许存在的状态称为可取状态， 如A1(1,0,1,0)是可取状态，但 A2(0,0,1,1)是一个不可取状态，v 此外，把每运载一次也用一个四维向量来表示，如 B1(1,1,0,0)表示人和狼在船上，而羊和白菜不在船上，这是可取的运载，因为船可载两物，而 B2(1,0,1,1)则是不可取运载v 利用穷举法可得到问题的解 穷举法 求解v (1)可取 (允许 )状态 A共有 10个(1， 1， 1， 1) (0， 0， 0， 0)(1， 1, 1， 0) (0， 0， 0， 1) (1， 1， 0， 1) (0， 0， 1， 0) (1， 0， 1， 1) (0， 1， 0， 0)(1， 0， 1， 0) (0， 1， 0， 1) 右边 5个正好是左边 5个的相反状态 。可取运载与可取运算 v (2)可取运载 B 共有 4个 (1， 1， 0， 0) (1， 0， 1， 0)(1， 0， 0， 1) (1， 0， 0， 0)v (3)可取运算 :规定 A与 B相加时对每一分量按二进制法则进行 :0十 0= 0， 1十 0=1， 0十 1=1， 1十 1= 0。v 这样 ，一次渡河就是一个可取状态向量与一个可取运载向量相加，可取状态经过加法运算后仍是可取状态 ，这种运算称为可取运算 。穷举法的数学模型v 在上述规定下，问题转化为 :从初始状态 (1， 1， 1， 1)经过多少次 (奇数次 )可取运算才能转化为状态 (0， 0， 0， 0)。v 如果一个状态是可取的就打 ，否则就打 ，虽然可取但已重复就打 ，于是问题可用穷举法解答如下：(1， 0， 1， 0) (0， 1， 0， 1) 1) (1， 1， 1， 1) 十 (1， 1， 0， 0) (0 ， 0， 1， 1) (1， 0， 0， 1) (0， 1， 1， 0) (1， 0， 0， 0) (0， 1， 1， 1) (1， 0， 1， 0) (1， 1， 1， 1) 2) (0， 1， 0， 1) 十 (1， 1， 0， 0) (1 ， 0， 0， 1) (1， 0， 0， 1) (1， 1， 0， 0) (1， 0， 0， 0) (1， 1， 0， 1) (1， 0， 1， 0) (0， 1， 1， 1) 3) (1， 1， 0， 1) 十 (1， 1， 0， 0) (0 ， 0， 0， 1) (1， 0， 0， 1) (0， 1， 0， 1) (1， 0， 0， 0) (0， 1， 0， 1) (1， 0， 1， 0) (1， 0， 1， 1) 4)1 (0， 0， 0， 1) 十 (1， 1， 0， 0) (1 ， 1， 0， 1) (1， 0， 0， 1) (1， 0， 0， 0) (1， 0， 0， 0) (1， 0， 0， 1) (1， 0， 1， 0) (1， 1， 1， 0) 4)2 (0， 1， 0， 0) 十 (1， 1， 0， 0) (1 ， 0， 0， 0) (1， 0， 0， 1) (1， 1， 0， 1) (1， 0， 0， 0) (1， 1， 0， 0) (1， 0， 1， 0) (0， 0， 0， 1) 5)1 (1， 0， 1， 1) 十 (1， 1， 0， 0) (0 ， 1， 1， 1) (1， 0， 0， 1) (0， 0， 1， 0) (1， 0， 0， 0) (0， 0， 1， 1) (1， 0， 1， 0) (0， 1， 0， 0) 5)2 (1， 1， 1， 0) 十 (1， 1， 0， 0) (0 ， 0， 1， 0) (1， 0， 0， 1) (0， 1， 1， 1) (1， 0， 0， 0) (0， 1， 1， 0) (1， 0， 1， 0) (1， 0， 0， 0) 6) (0， 0， 1， 0) 十 (1， 1， 0， 0) (1 ， 1， 1， 0) (1， 0， 0， 1) (1， 0， 1， 1) (1， 0， 0， 0) (1， 0， 1， 0) (1， 0， 1， 0) (0， 0， 0， 0) 7) (1， 0， 1， 0) 十 (1， 1， 0， 0) (0 ， 1， 1， 0) (1， 0， 0， 1) (0， 0， 1， 1) (1， 0， 0， 0) (0， 0， 1， 0) v 第 7步 已经出现 (0， 0， 0， 0)状态，说明经过 7次运载即可，其过程为：去 (人，羊 )回 (人 ) 去 (人，狼 (或菜 ) 回 (人，羊 )去 (人，菜 (或狼 ) 回 (人 )去 (人，羊 )评 注v 用这种方法的优点易于在计算机上实现。由此可把一个数学游戏问题转化成为一个在计算机上计算的数学问题 (即建模 )。v 可以看出，当状态向量维数增加，约束条件复杂时，这种方法更能方便求解，当所有的转移过程出现循环时，则问题无解。图论法求解v 在研究状态域位置发生变更的问题中，常常构造有向图来解决。v 首先对两岸上允许的组合加以分类，比如用 (FWG|C)表示 F、 W和 G在左岸上， 而 C在右岸上， “O“意味着在相应的岸上均无。v 将每一状态 (允许出现情况 )用一个点表示，若某次船从左岸划往右岸时，使状态 u变为v,就作一条从 u到 v的弧 (有向边 )，由此构造了一个有向图 (图 5-12)。得到该问题的数学模型。 有向图的图数学模型(FWGC|O) (FWG|C) (FWC|G) (FGC|W) (FG|WC)(WC|FG) (W|FGC) (G|FWC) (C|FWG) (O|FWGC)图 1v 注意到船是在两岸间往返的 ;该问题数学模型：在图 1中找一个从初始状态 (FWGC|O)到(O|FWGC)的弧的序列。无向图的模拟求解法v 仍将每一允许状态用一个点表示，两种状态的两顶点有边相连当且仅当两种状