第三章 经典数学问题的建模巧用课件.ppt

《第三章 经典数学问题的建模巧用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模与实验第三章经典数学问题的建模巧用人狼羊菜渡河问题状态转移问题一个摆渡人希望用一条小船把一只狼、一头羊和一篮白菜从一条河的左岸渡到右岸去，而船小只能容纳人、狼、羊、菜中的两个，决不能在无人看守的情况下留下狼和羊在一起，也不允许羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过河？人狼羊菜渡河问题问题分析这是一个多步决策问题，我们采用状态变量表示此岸人、狼、羊、菜的状况，决策变量为每次运载的东西。问题转化为在状态允许的范围内，确定每一步的决策，达到安全渡河的目的。模型建立与求解我们用作为状态变量，表示人、狼、羊、菜在此岸的状态。表示

2、在彼岸。表示在此岸，人狼羊菜渡河问题◆则所有的安全状态集合S为◆可供决策的变量集合D为◆定义S与D的运算为模2运算：如（1，1，1，0）+（1，1，0，0）=（0，0，1，0）状态变量决策变量新的状态变量（1，0，0，0）=（0，1，1，0）×（1，1，0，0）=（0，0，1，0）（1，1，1，0）+（1，0，1，0）=（0，1，0，0）（1，0，0，1）=（0，1，1，1）×人狼羊菜渡河问题状态转移举例状态决策变量状态人狼羊菜渡河问题◆由此可得10个安全状态之间的转移关系图标号人在此岸人在彼岸标号1（1，1，1，1）（0，0，0，0）6

3、2（1，1，1，0）（0，0，0，1）73（1，1，0，1）（0，0，1，0）84（1，0，1，1）（0，1，0，0）95（1，0，1，0）（0，1，0，1）10用标号表示的连接图人狼羊菜渡河问题11037482956从连接图可看出，状态1到状态6的最短路线为路线1：1-10-3-7-4-8-5-6路线2：1-10-3-9-2-8-5-6人狼羊菜渡河问题课堂练习商人过河问题有3名商人各带一名仆人乘船渡河，小船只能容纳两个人，由他们自己划船。仆人们约定，在河的一岸，一旦仆人的人数比商人多，就杀人越货。但如何乘船的大权掌握在商人们手里。问商人

4、们怎样才能安全渡河？数学巧用棋子颜色问题任意拿出黑白两种颜色的棋子共n个，随机排成一圆圈。然后在两颜色相同的棋子中间放一颗黑色棋子，在两颗颜色不同的棋子中间放一颗白色棋子，放完后撤掉原来的棋子，再重复以上过程。问这样重复进行下去棋子的颜色会发生怎样的变化？棋子颜色问题模型分析（-1）×（-1）=1，1×（-1）=-1，运算结果与颜色相同的棋子中间放一颗黑色棋子，颜色不同的棋子中间放一颗白色棋子的规则正好相符。如果用1表示黑色棋子，用-1表示白色棋子。因为故可设棋子数为n,为初始状态，其中则状态变化过程如下n=3n=2两步以后棋子全为黑色三

5、步以后回到前面状态棋子颜色问题n=4棋子颜色问题经过4步棋子全为黑子n=5棋子颜色问题棋子既不循环也不全为黑子当棋子数为结论棋子颜色问题时，至多经全变为黑子。当棋子数不为次操作，就可以时，一般不能全变为黑子。1.设棋子数为16，经过16步操作，看棋子是否全变为黑色。2.设棋子数为7，经过10步操作，看棋子颜色如何。编程练习棋子颜色问题MATLAB程序棋子颜色问题clcclearalln=16;%棋子数times=16;%迭代次数x0=zeros(1,n);%产生1×n全零阵x1=zeros(1,n);fori=1:nk=rand(1,1)

6、;%产生1个服从[0，1]上均匀分布的随机数if(k>0.5)x0(i)=1;elsex0(i)=-1;endend棋子颜色问题x0%初始棋子颜色构造完毕fori=1:timesi%显示迭代次数fork=1:n-1x1(k)=x0(k)*x0(k+1);endx1(n)=x0(n)*x0(1);x1%显示第i次迭代结果x0=x1;%初始状态更新end铺瓷砖问题要用40块方形瓷砖铺下图所示的地面，当时市场上只有长方形瓷砖，每块大小等于方形的两块。有人买了20快长方形瓷砖，试着铺地面，结果弄来弄去始终无法铺好。试问是这人的功夫不到家还是这个问

7、题根本无解呢？铺瓷砖问题解：将相邻的方块，一个画上阴影，一个保留空白，则共有21个阴影方块和19个空白方块。因为一块长方形砖一次只能覆盖一个阴影方块和一个空白方块，故多余的两块阴影方块无法覆盖，本问题本身无解。课堂练习跑步问题有人在任何一个5min时间区内跑不到500m，问此人10min有没有可能恰好跑完1000m？答案：不可能。为什么？若问题改为有人2min时间区内跑不到200m，问此人10min有没有可能恰好跑完1000m？答案又如何？建模提示：设S(t)表示t（min)（t∈[0,5]）跑完的路程。构造f(t)=s(t+5)-s(t

8、)-500,利用闭区间上连续函数的性质设S(t)表示t（min)跑完的路程。构造f(t)=s(t+2)-s(t)-200,则f(0)=s(2)-s(0)-200（s(0)=0)f(2)=s(4