初等数学方法建模 第二章初等数学方法建模 现实世界中有很多问题,它的机理较简单,用静态线性或逻辑的方法即可建立模型,使用初等的数学方 法,即可求解,我们称之为初等数学模型。本章主要介绍有关自然数,比例关系,状态转移,及量刚分析 等建模例子,这些问题的巧妙的分析处理方法,可使读者达到举一反三,开拓思路,提高分析,解决实际问 题的能力。 第一节有关自然数的几个模型 1.1鸽笼原理 鸽笼原理又称为抽屉原理,把N个苹果放入n(n<N)个抽屉里,则必有一个抽屉中至少有2个苹果 问题1:如果有N个人,其中每个人至多认识这群人中的m(n<N)个人(不包括自己),则至少有两 个人所认识的人数相等。 分析:我们按认识人的个数,将N个人分为0,1,2…,n类,其中k(0≤k≤m)类,表示认识k个人,这 样形成n+1个“鸽笼”。若n<N-1,则N个人分成不超过N-1类,必有两人属于一类,也即有 两个人所认识的人数相等:若n=N-1,此时注意到0类和N类必有一个为空集,所以不空的“鸽笼” 至多为N-1个,也有结论成立 问题2:在一个边长为1的正三角形内最多能找到几个点,而使这些点彼此间的距离大于0.5 分析:边长为1的正三角形△ABC,分别以A,B,C为中心,0.5为半径圆弧,将三角形分为四个部 分(如图1-1),则四部分中任一部分内两点距离都小于0.5,由鸽笼原理知道,在三角形内最多能找四 个点,使彼此间距离大于0.5,且确实可找到如A,B,C及三角形中心四个点 问题3:能否在8×8的方格表ABCD的各个空格中,分别填写1,2,3这三个数中的任一个,使得每行
初等数学方法建模 1 第二章 初等数学方法建模 现实世界中有很多问题，它的机理较简单，用静态,线性或逻辑的方法即可建立模型，使用初等的数学方 法，即可求解，我们称之为初等数学模型。本章主要介绍有关自然数，比例关系，状态转移，及量刚分析 等建模例子，这些问题的巧妙的分析处理方法，可使读者达到举一反三，开拓思路，提高分析, 解决实际问 题的能力。 第一节 有关自然数的几个模型 1.1 鸽笼原理 鸽笼原理又称为抽屉原理，把 N 个苹果放入 n(n N) 个抽屉里，则必有一个抽屉中至少有 2 个苹果。 问题 1：如果有 N 个人，其中每个人至多认识这群人中的 n(n N) 个人（不包括自己），则至少有两 个人所认识的人数相等。 分析：我们按认识人的个数，将 N 个人分为 0,1,2 ,n 类，其中 k(0 k n) 类，表示认识 k 个人，这 样形成 n+1 个“鸽笼”。若 n N −1 ，则 N 个人分成不超过 N −1 类，必有两人属于一类，也即有 两个人所认识的人数相等；若 n = N −1 ，此时注意到 0 类和 N 类必有一个为空集，所以不空的“鸽笼” 至多为 N −1 个，也有结论成立 问题 2：在一个边长为 1 的正三角形内最多能找到几个点，而使这些点彼此间的距离大于 0.5. 分析：边长为 1 的正三角形 ABC ，分别以 A, B,C 为中心， 0.5 为半径圆弧，将三角形分为四个部 分（如图 1-1 ），则四部分中任一部分内两点距离都小于 0.5 ，由鸽笼原理知道，在三角形内最多能找四 个点，使彼此间距离大于 0.5 ，且确实可找到如 A, B,C 及三角形中心四个点。 图 1—1 问题 3：能否在 88 的方格表 ABCD 的各个空格中，分别填写 1,2,3 这三个数中的任一个，使得每行
初等数学方法建模 每列及对角线AC,BD的各个数的和都不相同?为什么? 分析:若从考虑填法的种类入手,情况太复杂:这里我们注意到,方格表中行,列及对角线的总数为18 个;而用1,2,3填入表格,每行,列及对角线都是8个数,8个数的和最小为8,最大为24,共有24-8+1=17 种:利用鸽笼原理,18个“鸽”放入17个“鸽笼”,必有两个在一个“鸽笼”,也即必有两个和相同。所以 题目中的要求,无法实现。 思考题:在一个边长为1的正三角形内,若要彼此间距离大于,最多能找到几个点? 12“奇偶校验”方法 所谓“奇偶校验”,即是如果两个数都是奇数或偶数,则称这两个数具有相同的奇偶性:若一个数是 奇数,另一个数是偶数,则称具有相反的奇偶性。在组合问题中,经常使用“奇偶校验”考虑配对问题 问题1(棋盘问题):假设你有一张普通的国际象棋盘,一组对角上的两个方格被切掉,这样棋盘上只 剩下62个方格(如图1—2)。若你还有31块骨牌,每块骨牌的大小为1×2方格。试说明用互不重叠的骨牌 完全覆盖住这张残缺的棋盘是不可能的 分析:关键是对图1—2的棋盘进行黑白着色,使得相邻的两个方格有不同的颜色:用一块骨牌覆盖两 个方格,必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格,白格个数,分别为30和32:因此 不同能用31块骨牌盖住这张残缺的棋盘。用奇偶校验法,我们可以把黑色方格看成奇数方格,白色方格看 成偶数方格;因为奇偶个数不同,所以不能进行奇偶配对,故题中要求的作法是不可能实现的 团团 图1-2 图1-3 问题2(菱形十二面体上的H路径问题):沿一菱形十二面体各棱行走,要寻找一条这样的路径它通过 各顶点恰好一次,该问题被称为 Hamilton路径问题 分析:我们注意到菱形十二面体每个顶点的度或者为3或者为4,所谓顶点的度是指通过这一顶点的棱 数,如图1-3:且每3度顶点刚好与3个4度顶点相连,而每个4度顶点刚好与4个3度顶点相连。因此 一个 Hamilton路径必是3度与4度顶点交错,故若存在 Hamilton路径,则3度顶点个数,与4度顶点个数 要么相等,要么相差l。用奇偶校验法3度顶点为奇数顶点,4度顶点为偶数顶点,奇偶配对,最多只能余 1个:而事实上菱形十二面体中,有3度顶点8个,4度顶点6个;可得结论,菱形十二面体中不存在 Hamilton 路径 思考题:1、设一所监狱有64间囚室,其排列类似8×8棋盘,看守长告诉关押在一个角落里的囚犯, 只要他能够不重复地通过每间囚室到达对角的囚室(所有相邻囚室间都有门相通),他将获释, 问囚犯能否获得自由? 2、某班有49个学生,坐成7行7列,每个坐位的前后左右的坐位叫做它的邻座,要让49个
初等数学方法建模 2 每列及对角线 AC, BD 的各个数的和都不相同？为什么？ 分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为 18 个；而用 1,2,3 填入表格，每行,列及对角线都是 8 个数， 8 个数的和最小为 8 ，最大为 24 ，共有 24−8+1=17 种；利用鸽笼原理， 18 个“鸽”放入 17 个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以 题目中的要求，无法实现。 思考题：在一个边长为 1 的正三角形内，若要彼此间距离大于 n 1 ，最多能找到几个点？ 1.2 “奇偶校验”方法 所谓 “奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是 奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。 问题 1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只 剩下 62 个方格（如图 1—2）。若你还有 31 块骨牌，每块骨牌的大小为 1 2 方格。试说明用互不重叠的骨牌 完全覆盖住这张残缺的棋盘是不可能的。 分析：关键是对图 1—2 的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两 个方格，必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为 30 和 32 ；因此 不同能用 31 块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看 成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。 问题 2（菱形十二面体上的 H 路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过 各顶点恰好一次，该问题被称为 Hamilton 路径问题。 分析：我们注意到菱形十二面体每个顶点的度或者为 3 或者为 4 ，所谓顶点的度是指通过这一顶点的棱 数，如图 1—3；且每 3 度顶点刚好与 3 个 4 度顶点相连，而每个 4 度顶点刚好与 4 个 3 度 顶点相连。因此 一个 Hamilton 路径必是 3 度与 4 度顶点交错，故若存在 Hamilton 路径，则 3 度顶点个数，与 4 度顶点个数 要么相等，要么相差 1 。用奇偶校验法 3 度顶点为奇数顶点， 4 度顶点为偶数顶点，奇偶配对，最多只能余 1 个；而事实上菱形十二面体中，有 3 度顶点 8 个， 4 度顶点 6 个；可得结论，菱形十二面体中不存在 Hamilton 路径. 思考题：1、设一所监狱有 64 间囚室，其排列类似 88 棋盘，看守长告诉关押在一个角落里的囚犯， 只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他将获释， 问囚犯能否获得自由？ 2、某班有 49 个学生，坐成 7 行 7 列，每个坐位的前后左右的坐位叫做它的邻座，要让 49 个 图 1-2 图 1-3
初等数学方法建模 学生都换到他的邻座上去,问是否有这种调换位置的方案? 1.3自然数的因子个数与狱吏问题 令d(m)为自然数n的因子个数,则d(n)有的为奇数,有的为偶数,见下表 9 d(n) 6244 我们发现这样一个规律,当且仅当n为完全平方数时,d(n)为奇数;这是因为n的因子是成对出现的 也即n=ab;只有n为完全平方数,才会出现n=a2的情形,d(n)才为奇数 下面我们利用上述结论研究一个有趣的问题 狱吏问题:某王国对囚犯进行大赦,让一狱吏n次通过一排锁着的n间牢房,每通过一次按所定规则 转动门锁,每转动一次,原来锁着的被打开,原来打开的被锁上:通过n次后,门锁开着的,牢房中的犯人 放出,否则犯人不得获释。转动门锁的规则是这样的,第一次通过牢房,要转动每一把门锁,即把全部锁 打开;第二次通过牢房时,从第二间开始转动,每隔一间转动一次:第k次通过牢房,从第k间开始转动 每隔k-1间转动一次:问通过n次后,那些牢房的锁仍然是打开的? 问题分析:牢房的锁最后是打开的,则该牢房的锁要被转动奇数次;如果把n间牢房用1,2,…,n编号, 则第k间牢房被转动的次数,取决于k是否为1.2.…,n整除,也即k的因子个数,利用自然数因子个数定 理,我们得到结论:只有编号为完全平方数的牢房门仍是开着的。 1.4相识问题 问题:在6人的集会上,总会有3人互相认识或互相不认识。 分析:设6人为A1,A2…,A;下面分二种情形,1A1至多只和两个人相识,不妨设A1不认识A2,A3,A4 若A2,A34互相都认识,则结论成立,若A2,A3,4中有两人不认识,则加上A,有三人互不相识2.A1 至少和三人相识,不妨设A1认识A2,A3,A4;若A2,A3,A4互不相识结论成立,若A2,A3,A有两人相识, 加上A1则有三人互相认识。这样,我们就证明了结论成立这个问题的讨论,我们也可以采用几何模似的 方法,如图1-4 图1-4 在平面上画出六个点,表示6个人,两点间存在连线,表示两人相识;只需说明,图中必有三点组成 三角形(有三人相识),或有三点之间设有一条连线(三人互不相识)即可
初等数学方法建模 3 学生都换到他的邻座上去，问是否有这种调换位置的方案？ 1.3 自然数的因子个数与狱吏问题 令 d (n) 为自然数 n 的因子个数，则 d (n) 有的为奇数，有的为偶数，见下表: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 我们发现这样一个规律，当且仅当 n 为完全平方数时, d (n) 为奇数；这是因为 n 的因子是成对出现的, 也即 n = ab ; 只有 n 为完全平方数, 才会出现 2 n = a 的情形， d (n) 才为奇数。 下面我们利用上述结论研究一个有趣的问题. 狱吏问题：某王国对囚犯进行大赦，让一狱吏 n 次通过一排锁着的 n 间牢房，每通过一次按所定规则 转动门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过 n 次后，门锁开着的，牢房中的犯人 放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁 打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第 k 次通过牢房，从第 k 间开始转动， 每隔 k-1 间转动一次；问通过 n 次后，那些牢房的锁仍然是打开的？ 问题分析： 牢房的锁最后是打开的，则该牢房的锁要被转动奇数次；如果把 n 间牢房用 1,2, ,n 编号， 则第 k 间牢房被转动的次数，取决于 k 是否为 1,2, ,n 整除，也即 k 的因子个数，利用自然数因子个数定 理，我们得到结论：只有编号为完全平方数的牢房门仍是开着的。 1．4 相识问题 问题：在 6 人的集会上，总会有 3 人互相认识或互相不认识。 分析：设 6 人为 1 2 6 A , A , , A ;下面分二种情形，1. A1 至多只和两个人相识，不妨设 A1 不认识 2 3 4 A , A , A ； 若 2 3 4 A , A , A 互相都认识，则结论成立，若 2 3 4 A , A , A 中有两人不认识，则加上 A1 ，有三人互不相识. 2．A1 至少和三人相识，不妨设 A1 认识 2 3 4 A , A , A ；若 2 3 4 A , A , A 互不相识结论成立，若 2 3 4 A , A , A 有两人相识， 加上 A1 则有三人互相认识 。这样，我们就证明了结论成立,这个问题的讨论，我们也可以采用几何模似的 方法，如图 1—4 在平面上画出六个点，表示 6 个人，两点间存在连线，表示两人相识；只需说明，图中必有三点组成 三角形（有三人相识），或有三点之间设有一条连线（三人互不相识）即可， 图 1-4
初等数学方法建模 思考题 1.9个人的集会中一定有3个人互相认识或4个人互相不认识 2.14个人的集会中一定有3个人互相认识或者5个人互相不认识 3.17个科学家中,每个科学家都和其他科学家通信,他们之间讨论3个题目,且任意两个科学家之间只讨 论1个题目,证明其中至少有3名科学家,他们互相通信中讨论的是同一题 第二节状态转移问题 本节介绍两种状态转移问题,解决这种问题的方法,有状态转移法,图解法及用图的邻接距阵等。 2.1人、狗、鸡、米问题 人、狗、鸡、米均要过河,船上除1人划船外,最多还能运载一物,而人不在场时,狗要吃鸡,鸡要 吃米,问人,狗、鸡、米应如和过河? 分析:假设人、狗、鸡、米要从河的南岸到河的北岸,由题意,在过河的过程中 两岸的状态要满足一定条件,所以该问题为有条件的状态转移问题 1.允许状态集合 我们用(wx,y,z),w,xy,z=0或1,表示南岸的状态,例如(1,1,1,1)表示它们都在南岸,(0,1, 1,0)表示狗,鸡在南岸,人,米在北岸;很显然有些状态是允许的,有些状态是不允许的,用穷举法可 列出全部10个允许状态向量 (1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0) (0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0.,0)(0,1,0,1) 我们将上述10个可取状态向量组成的集合记为S,称S为允许状态集合 2、状态转移方程 对于一次过河,可以看成一次状态转移,我们用向量来表示决策,例(1,0,0,1)表示人,米过河 令D为允许决策集合 D={(1,x,y,z):x+y+z=0或1} 另外,我们注意到过河有两种,奇数次的为从南岸到北岸,而偶数次的为北岸回到南岸,因此得到下 述转移方程, S4+(-1)dk Sk=(Wk,xk,yk,k)表示第k次状态,dk∈D为决策向量 410 140 图2-1
初等数学方法建模 4 思考题： 1． 9 个人的集会中一定有 3 个人互相认识或 4 个人互相不认识 2． 14 个人的集会中一定有 3 个人互相认识或者 5 个人互相不认识 3． 17 个科学家中,每个科学家都和其他科学家通信，他们之间讨论 3 个题目，且任意两个科学家之间只讨 论 1 个题目，证明其中至少有 3 名科学家，他们互相通信中讨论的是同一题目 第二节 状态转移问题 本节介绍两种状态转移问题，解决这种问题的方法,有状态转移法，图解法及用图的邻接距阵等。 2．1 人、狗、鸡、米问题 人、狗、鸡、米均要过河，船上除 1 人划船外，最多还能运载一物，而人不在场时，狗要吃鸡，鸡要 吃米，问人，狗、鸡、米应如和过河？ 分析：假设人、狗、鸡、米要从河的南岸到河的北岸，由题意，在过河的过程中， 两岸的状态要满足一定条件，所以该问题为有条件的状态转移问题。 1. 允许状态集合 我们用（w, x, y, z），w, x, y, z=0 或 1，表示南岸的状态，例如（1，1，1，1）表示它们都在南岸，（0，1， 1，0）表示狗，鸡在南岸，人，米在北岸；很显然有些状态是允许的，有些状态是不允许的，用穷举法可 列出全部 10 个允许状态向量， (1, 1, 1, 1) (1, 1, 1, 0) (1, 1, 0, 1) (1, 0, 1, 1) (1, 0, 1, 0) (0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (0, 1, 0, 1) 我们将上述 10 个可取状态向量组成的集合记为 S，称 S 为允许状态集合 2、状态转移方程 对于一次过河，可以看成一次状态转移，我们用向量来表示决策，例（1，0，0，1）表示人，米过河。 令 D 为允许决策集合， D={ (1, x, y, z) : x+y+z=0 或 1} 另外，我们注意到过河有两种，奇数次的为从南岸到北岸，而偶数次的为北岸回到南岸，因此得到下 述转移方程， k k Sk+1 = Sk + (−1) d ------------------------(2.1) ( , , , ) k k k k k S = w x y z 表示第 k 次状态， dk D 为决策向量. 图 2-1
初等数学方法建模 2.人、狗、鸡、米过河问题,即要找到d1,d2…,dm∈D,S0,S1,…,Sn∈SS=(0,0.0,0) Sn=(1,1,1,1)且满足(2.1)式。 下面用状态转移图求解 将10个允许状态用10个点表示,并且仅当某个允许状态经过一个允许决策仍为允许状态,则这两个允许 状态间存在连线,而构成一个图,如图2—1,在其中寻找一条从(1,1,1,1)到(0,0,0,0)的路径 这样的路径就是一个解,可得下述路径图, 乳1 (1息11 414)(11 u111,1 41 (1,11 由图2-2,有两个解都是经过7次运算完成,均为最优解 2商人过河问题 三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的任一岸的 随从人数多于商人,他们就可能抢劫财物。但如何乘船渡河由商人决定,试给出一个商人安全渡河的方案 首先介绍图论中的一个定理 G是一个图,V(G)为G的顶点集,E(G)为G的边集。设G中有n个顶点v1,V2…,v; A=(an)∞为G的邻接距阵,其中 vv,∈E(G) 0 V, EE(G) 1,2 定理1:设A(G)为图G的邻接距阵,则G中从顶点v到顶点v,长度为k的道路的条数为A中的行 j列元素 证:对k用数学归纳法 k=1时,显然结论成立;假设k时,定理成立,考虑k+1的情形 记A的行j列元素为a1≥2,因为A·A=A",所以 all+=aa. ta 而从v到v长k+1的道路无非是从v经k步到某顶v1≤l≤n,再从v,走一步到v;由归纳 假设从v到v长为k的道路共计a条,而从v到v,长为1的道路为an条,所以长为k+1的从v经k 步到v再一步到v的道路共有aa条,故从T经k+1步到v的路径共有a=∑qa条 下面分析及求解
初等数学方法建模 5 2. 人、狗、鸡、米过河问题，即要找到 d1 , d2 , ,dm−1 D ， S0 , S1 , ,Sm S (0,0,0,0) S0 = = (1,1,1,1) Sm 且满足（2.1）式。 下面用状态转移图求解 将 10 个允许状态用 10 个点表示，并且仅当某个允许状态经过一个允许决策仍为允许状态，则这两个允许 状态间存在连线，而构成一个图, 如图 2—1 , 在其中寻找一条从（1，1，1，1）到（0，0，0，0）的路径， 这样的路径就是一个解, 可得下述路径图, 由图 2—2，有两个解都是经过 7 次运算完成，均为最优解 2．2 商人过河问题 三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，若在河的任一岸的 随从人数多于商人，他们就可能抢劫财物。但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。 首先介绍图论中的一个定理 G 是一个图，V（G）为 G 的顶点集，E(G)为 G 的边集。 设 G 中有 n 个顶点 n v ,v , ,v 1 2 ; A = aij nn ( ) 为 G 的邻接距阵，其中 = 0 ( ) 1 ( ) v v E G v v E G a i j i j ij i, j = 1, 2, ,n 定理 1：设 A(G) 为图 G 的邻接距阵，则 G 中从顶点 i v 到顶点 j v ，长度为 k 的道路的条数为 k A 中的 i 行 j 列元素. 证： 对 k 用数学归纳法 k =1 时，显然结论成立; 假设 k 时，定理成立， 考虑 k +1 的情形. 记 l A 的 i 行 j 列元素为 2 ( ) a l l ij , 因为 +1 = l l A A A , 所以 nj l j in l j i l i l aij = a a +a a + +a a ( +1) 1 1 2 2 (2.2) 而从 i v 到 j v 长 k +1 的道路无非是从 i v 经 k 步到某顶 vl 1 l n ,再从 l v 走一步到 j v ；由归纳 假设从 i v 到 l v 长为 k 的道路共计 k il a 条，而从 l v 到 j v 长为 1 的道路为 lj a 条，所以长为 k +1 的从 i v 经 k 步到 l v 再一步到 j v 的道路共有 lj k ail a ( ) 条，故从 i v 经 k +1 步到 j v 的路径共有 = + = n l lj k il k aij a a 1 ( 1) ( ) 条. 下面分析及求解 图 2-2
初等数学方法建模 假设渡河是从南岸到北岸,(m,n)表示南岸有m个商人,n个随从,全部的允许状态共有10个 v1=(3,3) (3,2)v3=(3,1)v4=(30) (2, v6=(1,1)v7=(0,3)vs=(0,2)v=(0.1)Vo=(00) 以V=句,v2…v10}为顶点集,考虑到奇数次渡河及偶数次渡河的不同,我们建立两个邻接距阵 , A2 0 A 00000 0001 00111 00000 00110 其中4=00010 A2=10000 A3=00011 00000 00000 00001 00000 00000 其中A表示从南岸到北岸渡河的图的邻接距阵,B=A表示从北岸到南岸渡河的图的邻接距阵。 由定理1、我们应考虑最小的k,st(AB)A中1行10列的元素不为0,此时2k+1即为最少的 渡河次数,而矩阵(AB)A中1行10列的元素为最佳的路径数目。 经过计算K=5时,(AB)A的第1行10列元素为2,所以需11次渡河,有两条最佳路径 最后我们用图解法求解 前面我们已求出问题的10种允许状态,允许决策向量集合D={1):a+v=1,2状态转移方程为 S1=S4+(-1)dk,如图2-3,标出10种允许状态,找出从S1经由允许状态到原点的路径,该路径还 要满足奇数次向左,向下;偶数次向右,向上 duo d6/ d g 图2-3 由图2一3可得这样的过河策略,共分11次决策
初等数学方法建模 6 假设渡河是从南岸到北岸，（m，n）表示南岸有 m 个商人，n 个随从，全部的允许状态共有 10 个 (3,3) (3,2) (3,1) (3,0) (2,2) v1 = v2 = v3 = v4 = v5 = (1,1) (0,3) (0,2) (0,1) (0,0) v6 = v7 = v8 = v9 = v10 = 以 V = v1 ,v2 , v10 为顶点集，考虑到奇数次渡河及偶数次渡河的不同，我们建立两个邻接距阵 T B A A A A A = = 3 1 2 0 其中 = = = 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 A1 A2 A3 其中 A 表示从南岸到北岸渡河的图的邻接距阵， T B = A 表示从北岸到南岸渡河的图的邻接距阵。 由定理 1、我们应考虑最小的 k ， s t AB A k ( ) 中 1 行 10 列的元素不为 0，此时 2k +1 即为最少的 渡河次数，而矩阵 AB A k ( ) 中 1 行 10 列的元素为最佳的路径数目。 经过计算 K=5 时, AB A 5 ( ) 的第 1 行 10 列元素为 2，所以需 11 次渡河，有两条最佳路径. 最后我们用图解法求解： 前面我们已求出问题的 10 种允许状态，允许决策向量集合 D = (u,v):u + v =1, 2,状态转移方程为 k k Sk+1 = Sk + (−1) d , 如图 2—3，标出 10 种允许状态，找出从 1 s 经由允许状态到原点的路径，该路径还 要满足奇数次向左，向下；偶数次向右, 向上. 由图 2—3 可得这样的过河策略，共分 11 次决策 图 2--3
初等数学方法建模 去一商一 回一商 去二随 回一随 去二商 (3.3) (2,2) (3,2) (3,0) (3.1) (1,1) 回一商一随 去二商 (2,2) (0.2) (0,3) (0.1) (0.2) (0.0) 思考题:1、在商人过河中若有4名商人,各带一随从能否过河 2、夫妻过河问题:有3对夫妻过河,船最多能载2人,条件是任一女子不能在其丈夫不在的情况 下与其他男子在一起,如何安排三对夫妻过河?若船最多能载3人,5对夫妻能否过河? 3、量纲分析法 量纲分析是20世纪初提出的,在物理领域中建立数学模型的一种方法,它是在经验和实验的基础上,利 用物理定律的量纲齐次原则,确定各物理量之间的关系 3.1量纲齐次原则与Pi定理 许多物理量是有量纲的,有些物理量的量纲是基本的,另一些物理量的量纲则可以由基本量纲根据其 定义或某些物理定律推导出来。例如在动力学中,把长度l,质量m和时间t的量纲作为基本量纲,记为 =L.[m]=M,团=T;而速度v,力f的量纲可表示为]=Lr-,[门=MT 在国际单位制中,有7个基本量:长度、质量、时间、电流、温度、光强度和物质的量,它们的量纲 分别为L、M、T、I、O、J、和N;称为基本量纲。任一个物理量q的量纲都可以表成基本量纲的幂次之 ]=LMr1°eN/ 量纲齐次性原则:用数学公式表示一个物理定律时,等式两端必须保持量纲一致。 量纲分析就是在保证量纲一致的原则下,分析和探求物理量之间关系;先看一个具体的例子,再给出 量纲分析的一般方法 例3-1:单摆运动,质量为m的小球系在长度为l的线的一端,线的另一端固定,小球偏离平衡位置 后,在重力mg作用下做往复摆动,忽略阻力,求摆动周期的表达式。 解:在这个问题中有关的物理量有1,m,l,g设它们之间有关系式 t=/ '/28 (3.1) 其中a,a2,a3为待定常数,入为无量纲的比例系数,取(3.1)式的量纲表达式有 ]=[m}"￠[g}整理得:T=M“L-T2 由量纲齐次原则应有 a2+
初等数学方法建模 7 思考题：1、在商人过河中若有 4 名商人，各带一随从能否过河？ 2、夫妻过河问题：有 3 对夫妻过河，船最多能载 2 人，条件是任一女子不能在其丈夫不在的情况 下与其他男子在一起，如何安排三对夫妻过河？若船最多能载 3 人，5 对夫妻能否过河？ 3、量纲分析法 量纲分析是 20 世纪初提出的, 在物理领域中建立数学模型的一种方法，它是在经验和实验的基础上, 利 用物理定律的量纲齐次原则，确定各物理量之间的关系。 3.1 量纲齐次原则与 Pi 定理 许多物理量是有量纲的，有些物理量的量纲是基本的，另一些物理量的量纲则可以由基本量纲根据其 定义或某些物理定律推导出来。例如在动力学中，把长度 l , 质量 m 和时间 t 的量纲作为基本量纲，记为 l = L, m = M, t = T ; 而速度 v，力f 的量纲可表示为 1 2 , − − v = LT f = MLT . 在国际单位制中，有 7 个基本量：长度、质量、时间、电流、温度、光强度和物质的量，它们的量纲 分别为 L、M、T、I、 、J、和 N；称为基本量纲。任一个物理量 q 的量纲都可以表成基本量纲的幂次之 积， q = L M T I N J 量纲齐次性原则：用数学公式表示一个物理定律时，等式两端必须保持量纲一致。 量纲分析就是在保证量纲一致的原则下，分析和探求物理量之间关系；先看一个具体的例子，再给出 量纲分析的一般方法。 例 3—1： 单摆运动，质量为 m 的小球系在长度为 l 的线的一端，线的另一端固定，小球偏离平衡位置 后，在重力 mg 作用下做往复摆动，忽略阻力，求摆动周期 t 的表达式。 解：在这个问题中有关的物理量有 t,m,l, g 设它们之间有关系式 1 2 3 1 t = m l g ---------------（3.1） 其中 2 3 , , 为待定常数，入为无量纲的比例系数，取（3．1）式的量纲表达式有 1 2 3 t = m l g 整理得： 1 2 +3 −23 T = M L T --------------（3.2） 由量纲齐次原则应有 − = + = = 2 1 0 0 3 2 3 1 ---------------（3.3） 去一商一随 （3，3） （2，2） 回一商 （3，2） 去二随 （3，0） 回一随 （3，1） 去二商 （1，1） 回一商一随 （2，2） 去二商 （0，2） 回一随 （0，3） 去二随 （0，1） 回一随 （0，2） 去二随 （0，0）
初等数学方法建模 解得:a1=0,a2 ,代入(3.1)得t=λ (34) (34)式与单摆的周期公式是一致的 下面我们给出用于量纲分析建模的 Buckingham pi定理, 定理:设n个物理量x1,x2,…,xn之间存在一个函数关系 f(x1,x2…xn)=0 (3.5) x]…{xn]为基本量纲,m≤n。x的量纲可表示为 i=1,2 矩阵A=(an)m称为量纲距阵,若Rmnk4=r,则(3.5)式与下式等价, F(兀1 其中F为一个未定的函数关系,丌为无量纲量,且丌,可表示为 13.6) i=1 而B)=(BB2)…B)为线性齐次方程组AB=0的基本解向量 利用Pi定理建模,关键是确定与该问题相关的几个基本量纲的无量纲量丌1丌2……丌n 作为量纲分析法的应用,下面我们介绍航船阻力的建模 3.2航船的阻力 长吃水深度h的船以速度ν航行,若不考虑风的影响,航船受到的阻力∫除依赖于船的诸变量 1、h、v以外,还与水的参数—一密度P,粘性系数μ,以及重力加速度g有关 我们利用pi定理分析f和上述物理之间的关系 1.航船问题中涉及的物理量及其量纲为 F=LN []=L [=L Iv]=LT [川=L-MT 1 8=lt
初等数学方法建模 8 解得： , 2 1 , 2 1 0 , 1 = 2 = 3 = − 代入（3．1）得 g l t = -------（3.4） （3.4）式与单摆的周期公式是一致的 下面我们给出用于量纲分析建模的 Buckingham Pi 定理， 定理：设 n 个物理量 n x , x , , x 1 2 之间存在一个函数关系 f (x1 , x2 , , xn ) = 0 --------------（3.5） m x x 1 为基本量纲， m n 。 1 x 的量纲可表示为 x x i n ij j m j i [ ] [ ] 1, 2, , 1 = = = 矩阵 A = ij nm ( ) 称为量纲距阵，若 RankA = r, 则（3.5）式与下式等价， F( 1 2 n−r ) = 0 其中 F 为一个未定的函数关系， s 为无量纲量，且 s 可表示为 ( ) 1 s i i n i s x = = -----------(3.6) 而 ( ) ( ) ( ) 2 ( ) 1 ( ) s n s s s = 为线性齐次方程组 = 0 T A 的基本解向量. 利用 Pi 定理建模，关键是确定与该问题相关的几个基本量纲的无量纲量 1 2 n−r , 作为量纲分析法的应用，下面我们介绍航船阻力的建模. 3．2 航船的阻力， 长 l 吃水深度 h 的船以速度 v 航行，若不考虑风的影响，航船受到的阻力 f 除依赖于船的诸变量 l、h、v 以外，还与水的参数——密度 P，粘性系数 , 以及重力加速度 g 有关。 我们利用 pi 定理分析 f 和上述物理之间的关系 1． 航船问题中涉及的物理量及其量纲为 = = = = = = = − − − − − − 2 1 1 3 1 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] g LT L MT L M v LT h L l L f LMT
初等数学方法建模 我们要寻求的关系式为 p(, l,h,v,P, u,g)=0 (3.7) 这些物理量中涉及到的基本量纲为L、M、T 2.写出量纲距阵 A=1000110M 200-10-1-2|T rank A= 3 3.解齐次线性方程组AB=0,可得n-rnkA=4个基本解向量 BD=(0、1、-1、0、0、0、0) B2)=(0、0、-20、0) B3=(0、0、11-10)7 B(+=(1、-20、-2、-10、0)7 由(36)式,可给出4个无量量纲 兀1=h (3.8) - 由Pi定理,(3.7)等价于下列方程 d(x1,x2,x3,丌4)=0 -----(3.9) 这里Φ是未定的函数 由(3.8),(3.9)可得阻力f的显式表达式, ∫=Pv2pv(x1,2r3) (3.10) 其中W是由(3.9)可得到的未知的函数关系,在力学上 称为 Froude数,记为F,bp称为 Reynold数,记为Re,因此(310)又可写为f=12y2pv(%,Fr,Re) (3.11) 4.下面我们利用物理模拟进一步确定航船在水中的阻力 设:f、l、h、ν、g和f1、h、v'、p、山、g分别表示模型和原型中的各物理量, 由(3.1)有 f=lvy( f=lv'p'y( I'v'p √g wp /vp 当无量纲量 (3.12)
初等数学方法建模 9 我们要寻求的关系式为 ( f ,l,h,v, , , g) = 0 ---------------（3.7） 这些物理量中涉及到的基本量纲为 L、M、T 2． 写出量纲距阵 T M L A T − − − − − − = 2 0 0 1 0 1 2 1 0 0 0 1 1 0 1 1 1 1 3 1 1 rank A = 3 3． 解齐次线性方程组 = 0 T A , 可得 n − rank A = 4 个基本解向量 = − − − = − = − = − T T T T （、 、、 、 、、） （ 、、、、、 、） 、、、 、、、 、、 、、、、 1 2 0 2 1 0 0 0 1 0 1 1 1 0 (0 1 0 2 0 0 1) (0 1 1 0 0 0 0) (4) (3) (2) (1) 由（3.6）式，可给出 4 个无量量纲 = = = = − − − − − − 2 2 1 4 1 3 2 2 1 1 fl v lv lv g lh - -------------------（3.8） 由 Pi 定理，（3.7）等价于下列方程 ( 1 , 2 , 3 , 4 ) = 0 -------------------（3.9） 这里 是未定的函数 由（3.８）,（３.９）可得阻力 f 的显式表达式， ( , , ) 1 2 3 2 2 f = l v -------------------（3.10） 其中 是由（３.９）可得到的未知的函数关系,在力学上, lg v 称为 Froude 数，记为 Fr ; lv 称为 Reynold 数，记为 Re , 因此（3.10）又可写为 ( , ,Re) 2 2 f l v h Fr = l ------------------（3.11） 4. 下面我们利用物理模拟进一步确定航船在水中的阻力。 设: f、l、h、v、、、g 和 f 、l 、h 、v 、 、 、g 分别表示模型和原型中的各物理量, 由(3.11)有 , ) lg ( , 2 2 v lv h l f = l v , ) l g ( , 2 2 = v l v h l f l v 当无量纲量 = = = v v lv l v h l h l lg l g -------------------（3.12）
初等数学方法建模 成立时,可得 ----(3.13) 则此时由模型船的阻力∫,及其它的1、v、p、V、y、p’;可确定原型船的阻力f 下面我们讨论一下(312)成立的条件如果在实验中采用跟实际同样的水质,则p'=p,’=p又 g=g / 故可得: hr' v'-vry' (3.14) 要使得(3.14)成立,必有l=}′,h=h’:也即模型船与原型船一样大,这显然排除了物理模拟的可 行性。若考虑选用不同的水质,s·t'≠,仍设p'=p则(3.12)式化为 (3.15) 由(315可得2=() 若按1:20的比例,H=0·011’,显然无法找到如此小的粘性系数的液体 实际上的一种近似处理方法是,在一定条件下Re数的影响很小,这样可近似得到, f≈l2y2pv( h√g 类似地分析,只要 h h1 V/即有 (3.16) 由(3.16)式就容易确定原型船的阻力∫ 3.3无量纲化抛射问题 面我们通过一个例子,介绍如何使用无量纲化方法简化模型 抛射问题:在某星球表面以初速度v竖直向上发射火箭,记星球半径为r,星球表面重力加速度为g 忽略阻力,讨论发射高度x随时间T的变化规律 模型建立:设x轴竖直向上,t=0时x=0,火箭和星球质量分别记为m1和m2,由牛顿第二定律 和万有引力定律可得
初等数学方法建模 10 成立时 , 可得 = 2 lv l v f f --------------------（3.13） 则此时由模型船的阻力 f ，及其它的 l、v、、l 、v 、 ；可确定原型船的阻力 f . 下面,我们讨论一下(3.12)成立的条件,如果在实验中采用跟实际同样的水质,则 p = p, = ; 又 g = g 故可得 ： l l v v l l v v h l h l = = = ---------------------------（3.14） 要使得(3.14)成立 , 必有 l = l , h = h ；也即模型船与原型船一样大，这显然排除了物理模拟的可 行性。若考虑选用不同的水质， st , 仍设 = 则(3.12)式化为 = = = l l v v l l v v h l h l ---------------------（3.15） 由(3.15)可得 2 3 = l l , 若按 1：20 的比例， = 0 011 ，显然无法找到如此小的粘性系数的液体 实际上的一种近似处理方法是，在一定条件下 Re 数的影响很小，这样可近似得到， ) lg ( , 2 2 v h l f l v 类似地分析，只要 l l v v h l h l = = 即有 3 = l l f f ----------------（3.16） 由（3.16）式就容易确定原型船的阻力 f 3.3 无量纲化 抛射问题 下面我们通过一个例子,介绍如何使用无量纲化方法简化模型。 抛射问题：在某星球表面以初速度 v 竖直向上发射火箭，记星球半径为 r ，星球表面重力加速度为 g ， 忽略阻力，讨论发射高度 x 随时间 T 的变化规律. 模型建立：设 x 轴竖直向上， t = 0 时 x = 0 ，火箭和星球质量分别记为 m1 和 m2 ，由牛顿第二定律 和万有引力定律可得: