经典数学问题的建模巧用.ppt

《经典数学问题的建模巧用.ppt》由会员分享，可在线阅读，更多相关《经典数学问题的建模巧用.ppt（30页珍藏版）》请在三一办公上搜索。

1、经典数学问题的建模巧用,在这一章里，我们介绍一些利用数学知识或数学模型巧妙的解决一些经典的数学问题、数学游戏。这些问题有的看起来简单，却又不好下手，感觉有一种山重水复疑无路。然而采用合适的数学方法或数学工具后，突然有一种柳暗花明又一村的感觉。下面我们举几个这样的经典数学问题或数学游戏。,1 人、狼、羊、菜渡河问题 一个摆渡人希望用一条小船把一只狼，一头羊和一篮白菜从一条河的左岸渡到右岸去，而船小只能容纳人，狼，羊，菜中的两个，决不能在无人看守的情况下留下狼和羊在一起，也不允许羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过去？,解：采用试探法可以得到两种方法,方法:1.人、羊(去)-2.人(

2、回)-3.人、狼(去)-4.人、羊(回)-5.人、菜(去)-6.人(回)-7.人、羊(去),方法2:1.人、羊(去)-2.人(回)-3.人、菜(去)-4.人、羊(回)-5.人、狼(去)-6.人(回)-7.人、羊(去),然而对于这样的问题，如何采用数学的方法来获得最优解呢？这是我们要解决的问题。,图1 状态转移图,图2 用标号表示的连接图,2 商人过河问题,有3名商人各带一个仆人乘船渡河，小船只能容纳两个人，由他们自己划船。仆人们约定，在河的人一岸，一旦仆人的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手里。问商人们怎样才能安全渡河？,模型建立：,S=(0,0),(0,1),(0,2

3、),(0,3),(3,0),(3,1),(3,2),(1,1),(2,2),(3,3)（1）,图3 安全渡示意图,图4 状态转移图,图5 用标号表示的连接图,3 等分酒问题,现有一只装满8斤酒的瓶子和两只分别装5斤和3斤酒的空瓶，如何才能将这8斤酒分成两等份？,解：手工操作法：,设状态向量(a,b,c)，其中a代表可装8斤酒的瓶子，b代表可装5斤酒的瓶子，c代表可装3斤酒的瓶子。,该问题转化为如何将初始状态(8,0,0)达到目标状态(4,4,0).,其操作过程必须满足条件：任何两瓶之间操作必须满足其中一个瓶子清空为0或另一个装满。,下面是一个实现步骤：(8,0,0)-(3,5,0)-(3,2,

4、3)-(6,2,0)-(6,0,2)-(1,5,2)-(1,4,3)-(4,4,0)(共经7步操作),该方法是一种尝试方法。下面我们可以采用状态转移的方法，利用图论知识进行求解。,我们从初始状态(8,0,0)开始，依此推出新出现的状态，由新出现的状态再推出更新的状态，直到不能推出新状态为止。其中每个状态距离初始状态都有一个步长，新状态的后继状态的步数如果比同样的已有状态的步书更大则舍去。,图6 分酒问题的状态转移图,从图6容易看出，从(8,0,0)状态可以有两种方式实现平分酒。一种方式是采用上面的方式，通过7步实现。另一种方式是下面的方式，通过8步实现。当然采用上面的方式是最少步数的方式。实现

5、过程为：,(8,0,0)(3,5,0)(3,2,3)(6,2,0)(6,0,2)(1,5,2)1,4,3)(4,4,0),其与尝试得到的结果是一致的。,4、棋子颜色问题,在任意拿出黑白两种颜色的棋子共n个，随机排成一个圆圈。然后在两颗颜色相同的棋子中间放一颗黑色棋子，在两颗颜色不同的棋子中间放一颗白色棋子，放完后撤掉原来所放的棋子，再重复以上的过程，这样放下一圈后就拿走前次的一圈棋子，问这样重复进行下去各棋子的颜色会怎样变化呢？,分析与求解：,由于在两颗同色棋子中放一颗黑色棋子，两颗不同色的棋子中间放一颗白色棋子，故可将黑色棋子用1表示，白色棋子用-1表示。这是因为-1(-1)=1，11=1，

6、这代表两颗同色棋子中放一颗黑色棋子；1(-1)=-1，这代表两颗不同色的棋子中间放一颗白色棋子。,经过两步，最后全为1，即全变为黑色棋子。,Matlab程序:进行实验,%棋子颜色问题演示%1-黑子,-1-白子 n=4;%定义棋子数 times=6;%定义迭代次数 x0=zeros(1,n);x1=zeros(1,n);%定义数组 for i=1:n k=rand(1,1);if(k0.5)x0(i)=1;else x0(i)=-1;end end;%赋初值 x0,for i=1:times i for k=1:n-1 x1(k)=x0(k)*x0(k+1);end x1(n)=x0(n)*x0

7、(1);x1%显示各次结果 x0=x1;end,程序语句解释：1.zeros(m,n),产生一个mn的0矩阵，通常用于定义一个指定大小的矩阵.zeros(1,n)则产生一个全部为0的行向量。2.rand(m,n),产生一个mn的随机矩阵，每个元素都服从0,1上的均匀分布.rand(1,1)则产生一个服从0,1上的均匀分布的数字。,5、铺瓷砖问题,要用40块方形瓷砖铺下图7所示形状的地面，但当时市场上只有长方形瓷砖，每块大小等于方形的两块。一人买了20块长方形瓷砖，试着铺地面，结果弄来弄去始终无法铺好。试问是这人的功夫不到家还是这个问题根本无解呢？,图7 瓷砖待铺图,解答:,图8 标号的瓷砖待铺

8、图,如图8，将各方格依次填入0和1。其中0和1相间隔，0周围全为1，1周围全为0。则每块长方形瓷砖总是盖住左右相邻或上下相邻的一个0和1。对图中0和1进行记数，总共有19个1和21个0，故20块长方形砖不可能盖住40块方形砖。,6.某仓库要存放7种化学药品，其中有些药品彼此不能存放在一起，因为互相之间可能引起化学反应导致危险，所以必须把仓库分成若干区，各区之间相互隔离。用x1,x2,x3,x4,x5,x6,x7分别表示7种药品。已知不能放在一起的药品为：(x1,x2),(x1,x4),(x2,x3),(x2,x5),(x2,x7),(x3,x4),(x3,x6),(x4,x5),(x4,x7),(x5,x6),(x5,x7),(x6,x7)问至少应把仓库分成多少隔离区,才能确保安全？,分析与求解：,每种药品用一个顶点表示。当两种药品可以放在一起，则在图上对这两点进行连接。得到的图见图9。,图9 药品可放在一起的示意图,该问题转化为图7所示的图中，有哪些完全子图。从该图可以看出，完全子图有(x2,x4,x6)，(x1,x3,x5)，（x7）。或者划分为(x2,x4,x6)，(x1,x3,x7)，（x5）。因此要把仓库分为3个隔离区。,