实例1：人和狗的问题(续)
• 要求一旦推断出自己的狗生病了，当天立 即把狗枪毙，若不能确定就等一天，待第 二日能确定后再将自己的狗枪毙，以此类 推。第一天，第二天，第三天没有人打死 自己的狗，第四天响起一片枪声，问有多 少只狗生病了？
实例1：人和狗的问题(续)
• 如果是第K天响起一片枪声，情况 又如何？
• 其中：海盗绝顶聪明(任何一种情况大家都能想到)； • 海盗是凶残的(在相同利益情况下是没有人情味)； • 海盗是贪婪的(在条件允许下谁给的利益多就支持谁) 。
• 问老大如何分配可以使自己分得最多而不会被 扔到海里去？
实例2：海盗分金币(续)
• 如果把支持率改为大于50%，情况又如何？
例1(Hanoi塔问题) n个圆盘按从大到小的顺 序依次套在柱A上,规定每次只能从一根柱子上搬 动一个圆盘到另一根柱子上,且要求在搬动过程中 不允许大盘放到小盘上,而且只有A, B , C 三根柱子 可供使用.求将n个盘子从柱A移到柱C 上所需要搬 动圆盘的最小次数an .
d11
S={(x , y) x=0, y=0,1,2,3; xy=3, y=0,1,2,3; x=y=1,2} s1
d1
3
2
1
评注和思考
0
sn+1
1
2
3
x
规格化方法,易于推广 考虑4名商人各带一随从的情况
讨论：
商人过河问题的进一步思考： (1) 若船的情况不变，则2名商人2个随从如何安全渡 河？ (2) m名商人m个随从(m≥4)能否安全渡河？ (3) 一般地，m个商人n个随从，m>n能否安全渡河 ？若能，怎样渡河？在商人们安全过河问题中，若 商人和随从各四人，怎样才能安全过河呢？
数学建模
优化方法建模 及实例讨论
什么是优化？
Operations Research
Maxminimum Minimum
目
录
模型一：递推关系模型 模型二：一一对应模型 模型三：初等优化模型
模型一：递推关系
6
实例1：人和狗的问题
• 有 2017 个人站在一个圆柱环上，每人正下方 有1只狗。每个人不能看见自己的狗，但能看 见其他所有人的狗。现在已知一部分狗病了， 病是不会传染的，病狗的特征一眼就能识别出 来，这 2017 个人是绝顶聪明的(任何一种情况 大家都能想到)，可以通过别人的狗是否生病 来推断自己的狗生病与否。
16
如果字母串中第一个字母是b,则其余字母 可以有an1种选择,所以以 b开头的长为 n的字母 串有an1个, 同样, 以 c开头的长为 n的字母串有 an1 个.
于是得递推关系 an 2an 1 2an 2 , a1 3, a2 8
17
n3
• 简单递推关系数学模型求解
河
小船(至多2人) 3名商人 3名随 从
问题分析
多步决策过程
决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员 要求~在安全的前提下(两岸的随从数不比商人多),经有 限步使全体人员过河.
模型求解
• 穷举法 ~ 编程上机 • 图解法 状态s=(x,y) ~ 16个格 点 允许状态 ~ 10个 点 允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移. d1, ，d11给出安全渡河方 案
实例2：海盗分金币
• 有5个海盗，按凶狠程度排名老大、老二、 老三、老四、老五。 • 他们抢来了100个金币。现在老大提出一种 分配方案，然后大家投票，如果有不少于 50%的人支持，就按照他提出的方案分。 • 否则，将老大扔到海里去(下海即被鲨鱼吃 掉)，由老二来分，以此类推。
实例2：海盗分金币(续)
阿拉伯夫妻过河问题 有三对阿拉伯夫妻要过河，船最多可载两人。 约束条件是根据阿拉伯法律，任一女子不得在其丈 夫不在场的情况下单独与另外男子在一起，问此时 这三对夫妻能否过河?
商人安全过河问题
问题
随从们密约, 在河的任一 岸, 一旦随从的人数比商 人多, 就杀人越货. 但是乘船渡河的方案由商人决定 .商人们怎样才能安全过河?
实例2：完全覆盖问题(续)
• 问10×10棋盘是否存在完全覆盖？ • 如果剪去该棋盘左上角和右下角两个方格 以后，是否存在完全覆盖？ • 如果剪去该棋盘对角线上任意两个方格后 ，是否还存在完全覆盖？
实例2：完全覆盖问题(续)
实例3：孩子的年龄是多大
模型三：初等优化
28
人、狗、鸡、米过河问题 某人要带一条狗、一只鸡、一箩米过河，但小船 除需要人划外，最多只能载一物过河，而当人不在 场时，狗要咬鸡、鸡要吃米。问此人应如何过河?
于是,得递推关系an 2an 1 1,{an }的定解问题为 an 2an 1 1 a1 1
一元非齐次常系 数线性递推关系
15
例2 在信道上传输仅用a、b、c这3个字母组 成的长度为n的字母串, 规定有两个a 连续出现的 串不能传输,用an 表示这个信道允许传输长度为n 的字母串的个数,试建立序列{an }的递推关系. 解 长度为1的字母串有a , b, c , 所以 a1 3, 长度 为2且没有两个a相邻的字母串有 ab, ac, ba, bb, bc, ca, cb, cc , 所以 a2 8.下设 n 3. 如果字母串中第一个字母是a,那么第二个字 母只能是b或c,其余的字母可以有 an 2 种方式选择, 因此以a开头的长为 n的字母串有2 an 2 个.
3 2 3 3-2 3 解得 A , B 6 6 故,所求定解为
3 2 3 3-2 3 n an (1 3) (1 3)n 6 6
21
模型二：一一对应
22
实例1：女神救人
那是2012年12月。。。。。。
实例2：完全覆盖问题
• 设有一个棋盘，假定有一批外形完全一样 的扑克牌，每张牌恰好覆盖棋盘上相邻的 方格，若用一些牌覆盖棋盘，使得棋盘上 的所有方格都被牌覆盖，牌之间不交叠， 称之为棋盘的完全覆盖。
例1 求递推关系an 4an1 an 2 6an 3的通解.
解 特征方程为 x 3 4 x 2 x 6 0, 解得特征根 q1 1, q2 2, q3 3
所以通解为 an A( 1)n B 2n C 3n A, B , C为任意常数.
13
A
B
C
A
B
C
A
B
C
A
14

C
解 易知,a1 1, a2 3, 对于n 3,搬动圆盘 的算法如下:
第一步,将套在柱A的上面n - 1个盘移到柱 B上, 需搬动an1次; 第二步,将柱A上最大一个盘移到柱 C上,只需 搬动一次; 第三步,再从柱B上将n - 1个盘移到柱C 上,也 需an 1次.
19
例2 求定解 an 2an 1 2an 2 (n 3) a1 3, a2 8
解 特征方程为 x 2x 2 0
2
得特征根 q1 1 3, q2 1 3 所以,通解为 an A(1 3)n B (1 3)n
20
代入初值,得 A(1 3) B(1 3) 3 2 2 A (1 3) B (1 3) 8