《数学建模》课程教学资源（PPT课件讲稿）第五章 离散模型

第五章离散模型 数学建模

第五章 离散模型

离散模型是将实际问题直接抽象成离散的数、符号 或图形,然后以离散数学为主要研究工具来解决的数学 e模型。连续模型进行离散化所得到的数学模型不在此讨 论 数学建模

离散模型是 将实际问题直接抽象成离散的数、符号 或图形，然后以离散数学为主要研究工具来解决的数学 模型。连续模型进行离散化所得到的数学模型不在此讨 论

过河问题 e问题有三名商人各带一名随从要乘一条小船过河, 这条船每次最多只能容纳两个人,并且由于某种原因, 商人们总是提防着随从们,预感到一旦在任何地方只要 随从人数多于商人数,就会对商人构成危害。但是由于 商人们控制着如何乘船的指挥权,所以商人们就可以制 定一个过河方案,以确保商人们的安全。试求出这个方 案。 数学建模

一、过河问题 问题 有三名商人各带一名随从要乘一条小船过河， 这条船每次最多只能容纳两个人，并且由于某种原因， 商人们总是提防着随从们，预感到一旦在任何地方只要 随从人数多于商人数，就会对商人构成危害。但是由于 商人们控制着如何乘船的指挥权，所以商人们就可以制 定一个过河方案，以确保商人们的安全。试求出这个方 案

建模 设在渡河过程中,此岸的商人个数为x,随从个数为 y以(x,y)表示此岸的状态向量,即 E=(x, 2)x, y=0,1,2, 31 在E中有一部分对商人是安全的,称为容许状态集 记为S.即有 =(3)y=0123(0.y)y=0.23 (x, y)x=y=1, 2) 数学建模

建模 设在渡河过程中，此岸的商人个数为 随从个数为 以 表示此岸的状态向量，即 x, y, ( x y, ) E x y x y = = ( , , 0,1,2,3 . )  在 中有一部分对商人是安全的，称为容许状态集合， 记为 即有 E S, ( ) ( ) ( )  3, 0,1,2,3; 0, 0,1,2,3, , 1,2 . S y y y y x y x y = = = = =

在上图中,实点即表示为容许状态的集合 乘船的方案称为决策,仍然用向量x,y)来表示, 即x名商人和ν名随从同坐一条船.在这些决策中,有 数学建模

x y o 1 2 3 1 2 在上图中, 实点即表示为容许状态的集合. 乘船的方案称为决策，仍然用向量 来表示， 即 名商人和 名随从同坐一条船. 在这些决策中, 有 ( x y, ) x y

是符合条件的,称为容许决策。容许决策的全体组成集 合构成容许决策的集合,记为D e在这个问题中,容许决策的集合为 D={(xy)≤x+y≤2 小船从此岸到彼岸的一次航行,会使两岸的状态发生 一次变化,此称为状态的转移。用 s1(x,y)2s2(x,y),s3(x,y) 数学建模

D x y x y =  +  ( , 1 2 . )  是符合条件的，称为容许决策。容许决策的全体组成集 合构成容许决策的集合，记为 D. 在这个问题中，容许决策的集合为 小船从此岸到彼岸的一次航行，会使两岸的状态发生 一次变化，此称为状态的转移。用 s x y s x y s x y 1 2 3 ( , , , , , , ) ( ) ( )

表示状态的转移。其中S∈S(i=12,3…)用d1(xy) e表示在状态S下的决策。当为奇数时,表示从此岸到 e彼岸,当i为偶数时,表示从彼岸到此岸。所以 +(-1)d 公式(1)称为状态转移公式。 所以,该问题转变成寻找一系列的决策d,∈D,使状 态S∈S(=12,3…)按()由初始状态经过有限次的 转移达到 数学建模

表示状态的转移。其中 用 表示在状态 下的决策。当 为奇数时，表示从此岸到 彼岸，当 为偶数时，表示从彼岸到此岸。所以 s S i i  = , 1,2,3, ( ) d x y i ( , ) i s i i 1 ( 1 . ) i i i i s s d + = + − ⑴ 公式⑴称为状态转移公式。 所以，该问题转变成寻找一系列的决策 使状 态 按⑴由初始状态经过有限次的 转移达到 , i d D  s S i i  = , 1,2,3, ( ) . n s

解模 建立坐标系统,并在坐标平面上建立的刻度单位。做 网格线,网格线上的每一个交点代表一个状态(用实点 表示)。黄色曲线弧表示向彼岸渡人,绿色曲线弧表示 从彼岸返回。容许决策d,表现为y 从一个实点向另一个实点的转移。 当i为奇数时,容许决策表现的是2 向下及向左的移动,当为偶数时1 容许决策表现的是向上及向右的移d 数学建模 >

建立坐标系统，并在坐标平面上建立的刻度单位。做 网格线，网格线上的每一个交点代表一个状态（用实点 表示）。黄色曲线弧表示向彼岸渡人，绿色曲线弧表示 从彼岸返回。容许决策 表现为 从一个实点向另一个实点的转移。 当 为奇数时，容许决策表现的是 向下及向左的移动，当 为偶数时 容许决策表现的是向上及向右的移 i d i i 解模 s1 (3,3) x y o 1 2 3 1 2

动 e整个状态的转移用下面的表格来表示。 数学建模

动。 整个状态的转移用下面的表格来表示

°序号状态决策「序号状态决策 (3)(.2) (22)(2.0) 1-2-3—4-5-6 (31)(0.)8(02)(01) (32)(02)9(03)(02) (01)10(0)(0.) (31)(20)1(0.2)(0.2) (1)(.1)12(00 数学建模

序号 状态 决策 序号 状态 决策 1 7 2 8 3 9 4 10 5 11 6 12 (3,3) (0,2) (0,1) (3,2) (3,1) (0,2) (3,0) (0,1) (3,1) (2,0) (1,1) (1,1) (2,2) (2,0) (0,2) (0,1) (0,3) (0,2) (0,1) (0,1) (0,2) (0,2) (0,0)