数学建模(优化方法建模)

《数学建模(优化方法建模)》由会员分享，可在线阅读，更多相关《数学建模(优化方法建模)（33页珍藏版）》请在金锄头文库上搜索。

1、数学建模数学建模优化方法建模优化方法建模 及实例讨论及实例讨论什么是优化？什么是优化？Operations ResearchMaxminimum Minimum目目 录录 模型一：递推关系模型模型一：递推关系模型 模型二：一一对应模型模型二：一一对应模型 模型三：初等优化模型模型三：初等优化模型6模型一：递推关系模型一：递推关系实例实例1 1：人和狗的问题：人和狗的问题 有有 2017 个人站在一个圆柱环上，每人正下方个人站在一个圆柱环上，每人正下方有有1只狗。每个人不能看见自己的狗，但能看只狗。每个人不能看见自己的狗，但能看见其他所有人的狗。现在已知一部分狗病了，见其他所有人的狗。现在已知一

2、部分狗病了，病是不会传染的，病狗的特征一眼就能识别出病是不会传染的，病狗的特征一眼就能识别出来，这来，这 2017 个人是绝顶聪明的个人是绝顶聪明的(任何一种情况任何一种情况大家都能想到大家都能想到)，可以通过别人的狗是否生病，可以通过别人的狗是否生病来推断自己的狗生病与否。来推断自己的狗生病与否。实例实例1 1：人和狗的问题：人和狗的问题( (续续) ) 要求一旦推断出自己的狗生病了，当天立要求一旦推断出自己的狗生病了，当天立即把狗枪毙，若不能确定就等一天，待第即把狗枪毙，若不能确定就等一天，待第二日能确定后再将自己的狗枪毙，以此类二日能确定后再将自己的狗枪毙，以此类推。第一天，第二天，第三

3、天没有人打死推。第一天，第二天，第三天没有人打死自己的狗，第四天响起一片枪声，问有多自己的狗，第四天响起一片枪声，问有多少只狗生病了？少只狗生病了？实例实例1 1：人和狗的问题：人和狗的问题( (续续) ) 如果是第如果是第K天响起一片枪声，情况天响起一片枪声，情况又如何？又如何？实例实例2：海盗分金币：海盗分金币 有有5 5个海盗，按凶狠程度排名老大、老二、个海盗，按凶狠程度排名老大、老二、 老三、老四、老五。老三、老四、老五。 他们抢来了他们抢来了100100个金币。现在老大提出一种个金币。现在老大提出一种 分配方案，然后大家投票，如果有不少于分配方案，然后大家投票，如果有不少于 50%5

4、0%的人支持，就按照他提出的方案分。的人支持，就按照他提出的方案分。 否则，将老大扔到海里去否则，将老大扔到海里去( (下海即被鲨鱼吃下海即被鲨鱼吃 掉掉) )，由老二来分，以此类推。，由老二来分，以此类推。实例实例2：海盗分金：海盗分金币币( (续续) ) 其中：海盗绝顶聪明其中：海盗绝顶聪明( (任何一种情况大家都能想到任何一种情况大家都能想到) )； 海盗是凶残的海盗是凶残的( (在相同利益情况下是没有人情味在相同利益情况下是没有人情味) )； 海盗是贪婪的海盗是贪婪的( (在条件允许下谁给的利益多就支持谁在条件允许下谁给的利益多就支持谁) ) 。 问老大如何分配可以使自己分得最多而不会

5、被问老大如何分配可以使自己分得最多而不会被 扔到海里去？扔到海里去？实例实例2：海盗分金：海盗分金币币( (续续) ) 如果把支持率改为大于如果把支持率改为大于50%，情况又如何？，情况又如何？,nnAA B CnACa个个圆圆盘盘按按从从大大到到小小的的顺顺序序依依次次套套在在柱柱 上上, ,规规定定每每次次只只能能从从一一根根柱柱子子上上搬搬动动一一个个圆圆盘盘到到另另一一根根柱柱子子上上, ,且且要要求求在在搬搬动动过过程程中中不不允允许许大大盘盘放放到到小小盘盘上上, ,而而且且只只有有三三根根柱柱子子可可供供使使用用. .求求将将 个个盘盘子子从从柱柱 移移到到柱柱 上上所所需需要要

6、搬搬动动圆圆(Han(Han盘盘的的最最小小oioi次次塔塔) )例例1 1数数问问题题. .ABC 13ABCABCABC141nBnCa 第第三三步步, ,再再从从柱柱 上上将将 -1-1个个盘盘移移到到柱柱 上上, ,也也需需次次. .11121,211 nnnnnaaaaaa 于于是是, ,得得递递推推关关系系的的定定解解问问题题为为一元非齐次常系一元非齐次常系 数线性递推关系数线性递推关系121,3,3aan 解解 易易知知, , 对对于于, ,搬搬动动圆圆盘盘的的算算法法如如下下: :1nAnBa 第第一一步步, ,将将套套在在柱柱 的的上上面面 -1-1个个盘盘移移到到柱柱 上上

7、, ,需需搬搬动动次次; ;AC 第第二二步步, ,将将柱柱 上上最最大大一一个个盘盘移移到到柱柱 上上, ,只只需需搬搬动动一一次次; ;15nnabcnaana在在信信道道上上传传输输仅仅用用 、 、 这这3 3个个字字母母组组成成的的长长度度为为 的的字字母母串串, ,规规定定有有两两个个 连连续续出出现现的的串串不不能能传传输输, ,用用表表示示这这个个信信道道允允许许传传输输长长度度为为的的字字母母串串的的个个数数, ,试试建建例例2 2 立立序序列列的的递递推推关关系系. .12, , ,3,8.3.a b caaab ac ba bb bc cacb ccan 解解 长长度度为为

8、1 1的的字字母母串串有有所所以以长长度度为为2 2且且没没有有两两个个 相相邻邻的的字字母母串串有有所所以以下下设设222nnabcaana 如如果果字字母母串串中中第第一一个个字字母母是是 , ,那那么么第第二二个个字字母母只只能能是是 或或 , ,其其余余的的字字母母可可以以有有种种方方式式选选择择, ,因因此此以以 开开头头的的长长为为 的的字字母母串串有有个个. .16121222, 33, 8 nnnaaanaa 于于是是得得递递推推关关系系111nnnbabnacna 如如果果字字母母串串中中第第一一个个字字母母是是 , ,则则其其余余字字母母可可以以有有种种选选择择, ,所所以

9、以以以 开开头头的的长长为为 的的字字母母串串有有个个, , 同同样样, , 以以 开开头头的的长长为为 的的字字母母串串有有个个. .17 简单递推关系数学模型求解简单递推关系数学模型求解12346nnnnaaaa 求求例例1 1递递推推关关系系的的通通解解. .32460,xxx解解 特特征征方方程程为为1231, 2, 3qqq 解解得得特特征征根根 ( 1)23,nnn naABCA B C所所以以通通解解为为为为任任意意常常数数. .19121222 (3)3, 8 nnnaaanaa 例例求求定定解解2 2 1213, 13qq得得特特征征根根 (13)(13)nn naAB所所以

10、以, ,通通解解为为2220xx解解 特特征征方方程程为为2022(13)(13)3(13)(13)8ABAB 代代入入初初值值, ,得得32 33-2 3(13)(13)66nn na 故故, ,所所求求定定解解为为 32 33-2 3, 66AB 解解得得 2122模型二：一一对应模型二：一一对应实例实例1 1：女神救人：女神救人那是那是2012年年12月。月。实例实例2 2：完全覆盖问题：完全覆盖问题 设有一个棋盘，假定有一批外形完全一样设有一个棋盘，假定有一批外形完全一样的扑克牌，每张牌恰好覆盖棋盘上相邻的的扑克牌，每张牌恰好覆盖棋盘上相邻的方格，若用一些牌覆盖棋盘，使得棋盘上方格，若

11、用一些牌覆盖棋盘，使得棋盘上的所有方格都被牌覆盖，牌之间不交叠，的所有方格都被牌覆盖，牌之间不交叠，称之为棋盘的完全覆盖。称之为棋盘的完全覆盖。实例实例2 2：完全覆盖问题：完全覆盖问题( (续续) ) 问问1010棋盘是否存在完全覆盖？棋盘是否存在完全覆盖？ 如果剪去该棋盘左上角和右下角两个方格如果剪去该棋盘左上角和右下角两个方格以后，是否存在完全覆盖？以后，是否存在完全覆盖？ 如果剪去该棋盘对角线上任意两个方格后如果剪去该棋盘对角线上任意两个方格后，是否还存在完全覆盖？，是否还存在完全覆盖？实例实例2 2：完全覆盖问题：完全覆盖问题( (续续) )实例实例3：孩子的年龄是多大：孩子的年龄是

12、多大28模型三：初等优化模型三：初等优化人、狗、鸡、米过河问题人、狗、鸡、米过河问题某人要带一条狗、一只鸡、一箩米过河，但小船某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河场时，狗要咬鸡、鸡要吃米。问此人应如何过河?阿拉伯夫妻过河问题阿拉伯夫妻过河问题有三对阿拉伯夫妻要过河，船最多可载两人。有三对阿拉伯夫妻要过河，船最多可载两人。约束条件是根据阿拉伯法律，任一女子不得在其丈约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下单独与另外男子在一起，问此时夫不在场的

13、情况下单独与另外男子在一起，问此时这三对夫妻能否过河这三对夫妻能否过河? ? 商人安全过河问题商人安全过河问题问题问题 3名商人名商人 3名随名随 从从随从们密约随从们密约, , 在河的任一在河的任一 岸岸, , 一旦随从的人数比商一旦随从的人数比商 人多人多, , 就杀人越货就杀人越货. .但是乘船渡河的方案由商人决定但是乘船渡河的方案由商人决定 . .商人们怎样才能安全过河商人们怎样才能安全过河?问题分析问题分析多步决策过程多步决策过程决策决策 每一步每一步( (此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸) )船上的人员船上的人员要求要求在安全的前提下在安全的前提下( (两岸的随从数不比

14、商人多两岸的随从数不比商人多),),经有经有 限步使全体人员过河限步使全体人员过河. .河河小船小船(至多至多2人人)模型求解模型求解xy3322110 穷举法穷举法 编程上机编程上机 图解法图解法状态状态s=(x,y) 16个格个格 点点 10个个 点点允许决策允许决策 移动移动1或或2格格; k奇奇,左下移左下移; k偶偶,右上移右上移.s1sn+1d1, ，d11给出安全渡河方给出安全渡河方 案案评注和思考评注和思考规格化方法规格化方法, ,易于推广易于推广考虑考虑4名商人各带一随从的情况名商人各带一随从的情况d1d11允许状态允许状态S=(x , y) x=0, y=0,1,2,3;x=3, y=0,1,2,3; x=y=1,2讨论：讨论：商人过河问题的进一步思考：商人过河问题的进一步思考：(1) 若船的情况不变，则若船的情况不变，则2名商人名商人2个随从如何安全渡个随从如何安全渡河？河？(2) m名商人名商人m个随从个随从(m4)能否安全渡河？能否安全渡河？(3) 一般地，一般地，m个商人个商人n个随从，个随从，mn能否安全渡河能否安全渡河？若能，怎样渡河？在商人们安全过河问题中，若？若能，怎样渡河？在商人们安全过河问题中，若商人和随从各四人，怎样才能安全过河呢？商人和随从各四人，怎样才能安全过河呢？