《初等数学模型》PPT课件.ppt
《《初等数学模型》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《初等数学模型》PPT课件.ppt(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、初等数学模型vv1.1.商人安全过河模型商人安全过河模型商人安全过河模型商人安全过河模型vv2.2.人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型商人安全过河模型商人安全过河模型问题的提出问题的提出v三名商人各带一个随从乘船渡河,一只小船只三名商人各带一个随从乘船渡河,一只小船只能容纳两人,由他们自己划行。能容纳两人,由他们自己划行。v随从们密约,在河的任一岸,一旦随从的人数随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货。比商人多,就杀人越货。v如何乘船渡河的大权掌握在商人们手中,如何乘船渡河的大权掌握在商人们手中,v商人们怎样才能安全渡
2、河呢商人们怎样才能安全渡河呢?数模求解的意义数模求解的意义v 对于这类智力游戏,经过一番逻辑思索是可以找出对于这类智力游戏,经过一番逻辑思索是可以找出解决办法的。解决办法的。v这里用数学模型求解,这里用数学模型求解,一是为了给出建模的示例,一是为了给出建模的示例,二是因为这类模型可以解决相当广泛的一类问题,比逻二是因为这类模型可以解决相当广泛的一类问题,比逻辑思索的结果容易推广。辑思索的结果容易推广。问题分析:问题分析:v由于这个虚拟的问题己经理想化了,所以不必由于这个虚拟的问题己经理想化了,所以不必再作假设。再作假设。v安全渡河问题可以视为多步决策过程。每一步,安全渡河问题可以视为多步决策过
3、程。每一步,即船由此岸驶向彼岸或从彼岸驶回此岸,都要即船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员对船上的人员(商人、随从各几人商人、随从各几人)作出决策作出决策v在保证安全的前提下在保证安全的前提下(两岸的商人数都不比随从两岸的商人数都不比随从数少数少),在有限步内使人员全部过河。,在有限步内使人员全部过河。变量的确定变量的确定v用状态用状态(变量变量)表示某一岸的人员状况,决策表示某一岸的人员状况,决策(变量变量)表示船上的人员状况,可以找出状态随决策变化的表示船上的人员状况,可以找出状态随决策变化的规律。规律。v问题转化为在状态的允许变化范围内问题转化为在状态的允许变化范围内(即安
4、全渡河即安全渡河条件条件),确定每一步决策,达到渡河目标。,确定每一步决策,达到渡河目标。模型构成模型构成 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次渡船上商人数为次渡船上商人数
5、为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 k D(k=1,2,,n),使状
6、态使状态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次决次决策可取运
7、算后即可完成。策可取运算后即可完成。v 当当k为奇数时,为奇数时,dk表示从此岸到彼岸,当表示从此岸到彼岸,当k为为偶数时,表示从彼岸回到此岸。偶数时,表示从彼岸回到此岸。模型求解模型求解 v 根据根据(1)-(3)式编一段程序,用计算机求解上述多式编一段程序,用计算机求解上述多步决策问题是可行的。步决策问题是可行的。v对于商人和随从人数不大的简单状况,用图解法解对于商人和随从人数不大的简单状况,用图解法解这个模型更为方便。这个模型更为方便。v y(随从数)(随从数)3 (3,3)o x(商人数商人数)1 2 3 图1-3 安全渡河问题的图解法(共四种)图解法决策的步骤图解法决策的步骤v在在x
8、oy平面坐标系上画出图平面坐标系上画出图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
9、 2,d n,最终有,最终有s n+1=(0,0)。v将该结果翻译成渡河的方案。将该结果翻译成渡河的方案。评评 注注 v 这里介绍的模型是一种规格化的方法,使我们这里介绍的模型是一种规格化的方法,使我们可以用计算机求解,从而具有推广的意义。可以用计算机求解,从而具有推广的意义。v譬如当商人和随从人数增加或小船的容量加大譬如当商人和随从人数增加或小船的容量加大时,靠逻辑思考就困难了,而用这种模型则仍时,靠逻辑思考就困难了,而用这种模型则仍可方便地求解。可方便地求解。v另外,适当地设置状态和决策,并确定状态转另外,适当地设置状态和决策,并确定状态转移律,是有效地解决很广泛的一类问题的建模移律,是有
10、效地解决很广泛的一类问题的建模方法,在以后还可能要用到。方法,在以后还可能要用到。人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型 问题的提出问题的提出v一摆渡人一摆渡人F希望用一条小船把一只狼希望用一条小船把一只狼W,一头,一头羊羊G和一篮白菜和一篮白菜C从一条河的左岸渡到右岸去,从一条河的左岸渡到右岸去,而船小只能容纳而船小只能容纳F、W、G、C中的两个,决中的两个,决不能在无人看守的情况下,留下狼和羊在一不能在无人看守的情况下,留下狼和羊在一起,羊和白菜在一起,起,羊和白菜在一起,v应怎样渡河才能将狼、羊、白菜都运过去应怎样渡河才能将狼、羊、白菜都运过去?v 这是一个有趣的智力游戏问题,显然
11、可用这是一个有趣的智力游戏问题,显然可用递推方法解决,但我们把此问题化为状态转递推方法解决,但我们把此问题化为状态转移问题来解决。移问题来解决。状态向量的表示状态向量的表示 v将人、狼、羊、菜依次用一个四维向量表示,将人、狼、羊、菜依次用一个四维向量表示,当一物在左岸时,记相应的分量为当一物在左岸时,记相应的分量为1,否则记,否则记为为0,如,如A(1,0,1,0)表示人和羊在左岸,并称表示人和羊在左岸,并称为一个状态为一个状态v由问题中的限制条件,有些状态是允许的,由问题中的限制条件,有些状态是允许的,有的是不允许的。有的是不允许的。v凡系统可以允许存在的状态称为可取状态,如凡系统可以允许存
12、在的状态称为可取状态,如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
13、)(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 这样这样,一次渡河就是一个可取状态向量与一个可,一次渡河就是一
14、个可取状态向量与一个可取运载向量相加,可取状态经过加法运算后仍是可取运载向量相加,可取状态经过加法运算后仍是可取状态取状态,这种运算称为可取运算,这种运算称为可取运算。穷举法的数学模型穷举法的数学模型v 在上述规定下,问题转化为在上述规定下,问题转化为:从初始状态从初始状态 (1,1,1,1)经过多少次经过多少次(奇数次奇数次)可取运算才能转化为状态可取运算才能转化为状态(0,0,0,0)。v 如果一个状态是可取的就打如果一个状态是可取的就打,否则就打,否则就打,虽然,虽然可取但已重复就打可取但已重复就打,于是问题可用穷举法解答如,于是问题可用穷举法解答如下:下:(1,0,1,0)(0,1,0
15、,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
16、,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)(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 初等数学模型 初等 数学模型 PPT 课件
限制150内