《初等数学模型》PPT课件

《《初等数学模型》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、初等数学模型1.商人安全过河模型2.人、狼、羊、菜渡河模型商人安全过河模型问题的提出三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢?数模求解的意义对于这类智力游戏，经过一番逻辑思索是可以找出解决办法的。这里用数学模型求解，一是为了给出建模的示例，二是因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推广。问题分析：由于这个虚拟的问题己经理想化了，所以不必再作假设。安全渡河问题可以视为多

2、步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人、随从各几人)作出决策在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。变量的确定用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步决策，达到渡河目标。模型构成记第k次渡河前此岸的商人数为xk，随从数为yk，k=l，2，…，xk,yk=0，1，2，3。将二维向量sk=(xk,yk)定义为状态安全渡河条件下的状态集合称为允许状态

3、集合，记作S。不难写出S=｛(x,y)

4、x=0,y=0，1，2，3;x=3,y=0，1，2，3;x=y=1，2｝(1)状态sk随决策dk变化的规律记第k次渡船上商人数为uk，随从数为vk将二维向量dk=(uk,vk)定义为决策.允许决策集合记作D，由小船的容量可知D=｛(u，u)

5、u+v=l，2｝(2)因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶回此岸，所以状态sk随决策dk变化的规律是sk+1=sk+(-1)kdk(3)(3)式称状态转移律。商人安全过河的数学模型（多步决策模型）:求决策dkD(k=1，2，…,n)，使状态

6、skS按照转移律(3):sk+1=sk+(-1)kdk由初始状态s1=(3,3)经有限步n到达状态sn+1=(0,0)。由状态(3，3)经n(奇数)步决策转移到(0，0)的转移过程具体转移步骤如下:(0，1)(3，2)√(0，2)(3，1)√(3，3)+(-1)1(1，1)→(2，2)√(1，0)(2，3)×(2，0)(1，3)×再将(3，2)，(3，1)，(2，2)分别与决策向量进行运算。如此下去，不难验证，经过11次决策可取运算后即可完成。当k为奇数时，dk表示从此岸到彼岸，当k为偶数时，表示从彼岸回到此岸。模型求解根据(1)-

7、(3)式编一段程序，用计算机求解上述多步决策问题是可行的。对于商人和随从人数不大的简单状况，用图解法解这个模型更为方便。y（随从数）3(3,3)ox(商人数)123图1-3安全渡河问题的图解法（共四种）图解法决策的步骤在xoy平面坐标系上画出图1-3那样的方格，方格点表示状态s=(x,y)。允许状态集合S是圆点标出的10个格子点。允许决策d是沿方格线移动1或2格，k为奇数时向左、下方移动，k为偶数时向右、上方移动。要确定一系列的dk使由s1=(3，3)经过那些圆点最终移至原点(0，0)。课堂(后)数模练习试在图1-3中给出一种移动方案，

8、即经过决策d1,d2，…，dn，最终有sn+1=(0，0)。将该结果翻译成渡河的方案。评注这里介绍的模型是一种规格化的方法，使我们可以用计算机求解，从而具有推广的意义。譬如当商人和随从人数增加或小船的容量加大时，靠逻辑思考就困难了，而用这种模型则仍可方便地求解。另外，适当地设置状态和决策，并确定状态转移律，是有效地解决很广泛的一类问题的建模方法，在以后还可能要用到。人、狼、羊、菜渡河模型问题的提出一摆渡人F希望用一条小船把一只狼W，一头羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，决不能在无人看守的情况

9、下，留下狼和羊在一起，羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过去?这是一个有趣的智力游戏问题，显然可用递推方法解决，但我们把此问题化为状态转移问题来解决。状态向量的表示将人、狼、羊、菜依次用一个四维向量表示，当一物在左岸时，记相应的分量为1，否则记为0，如A(1,0,1,0)表示人和羊在左岸，并称为一个状态由问题中的限制条件，有些状态是允许的，有的是不允许的。凡系统可以允许存在的状态称为可取状态，如A1(1,0,1,0)是可取状态，但A2(0,0,1,1)是一个不可取状态，此外，把每运载一次也用一个四维向量来表示，如B1(1,

10、1,0,0)表示人和狼在船上，而羊和白菜不在船上，这是可取的运载，因为船可载两物，而B2(1,0,1,1)则是不可取运载利用穷举法可得到问题的解穷举法求解(1)可取(允许)状态A共有10个(1，1，1，1)