第八章逻辑模型.ppt
《第八章逻辑模型.ppt》由会员分享,可在线阅读,更多相关《第八章逻辑模型.ppt(94页珍藏版)》请在三一文库上搜索。
1、第八章 逻辑模型,数学建模基地,8 逻辑模型,欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论,从而建立了完整的欧几里得几何学,这一辉煌成果至今仍然是人类的宝贵财富。 本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发,运用逻辑推理方法或者导出满足这些基本属性的解来,或者证明在原有观念下问题不可能有解,从而从根本上改变人们对这一问题的看法,例1 在每一次人数不少于6人的聚会中必可找出这样的3人,他们或者彼此均认识或者彼此均不认识 。,利用图的方法来描述该问题。将人看成顶点,两人彼此都认识用实线连,否则虚线。,证明:
2、,问题转化为在一个6阶图中必存在实线三角形或虚线三角形。,请大家一起画图证明,1,2,3,4,任取一顶点,不妨1,考察23、24和34,23、24和34只能是虚线 ,否则得证,但这样三角形234的三边均为虚线,拉姆齐问题也可这样叙述: 6阶2色完全图中必含有3阶单色完全图。,其他类似可推出的结果 :,命题8.1 任一6阶2色完全图中至少含有两个3阶单色完全图。,证明:前面证明必存在3阶单色完全图,不妨设123 为红色完全图,15、25、35中至少有两条黑色、故15 与25中至少有一条是黑色,14、24、34至少应有两条黑色,不妨设 14 、24 黑色,所以存在第二个3阶单色完全图。,命题8.2
3、 7阶2色完全图至少含有4个3阶单色安全图。,命题8.3 18阶2色完全图中必含有4阶单色完全图。,对拉姆齐问题的认识不能仅仅停留在例11.1的水平上。利用逻辑推理方法,实际上还可获得一大批结果。命题11.2和命题11.3的证明留给大家自己去完成。,例2 17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题,则其中必可找出3位学者,他们之间讨论的是同一方向的课题。,证明: 采用反证法,设 ,其中p、q互素,则有 p2=2q2。因为2|p2,故2|p。记p=2p1,可得4p12=2q2 ,即 2p12=q2 ,故又有2|q,与p、q 互素矛盾。,例3 证明 是无理
4、数。,同样方法可以证明:若m是大于1的素数,n是大于1的整数则 必为无理数。,例4 拟用40块方形瓷砖铺设如下图所示的地面,但商店只有长方形瓷砖,其大小为方形的两块。问购买20块长方形瓷砖后,是否可能不裁开而直接铺好地面?,解 将图11.4中的(a) (b)黑白相间染色。,显然,如长方形瓷砖不裁开,只能用来复盖相邻的两格,故复盖的两格必为一白一黑。 下图(a)中共有21个黑格和19个白格,故不可能直接铺好,下图(b)中黑白格各为20个,大家很容易找到直接铺设的方法。,证明: 显然有4|mn,故m、n中至少有一个为偶数,不妨 设n为偶数,将棋盘按列黑白相间染色,如下图 (a ) 所示,由于n为偶
5、数,黑、白列的数目相同,故黑白 格数相同,设各为2k个。,板块可以有许多种拼凑法,但容易看出,每一板块放 置的方向(称之为定向)只有八种可能的选择,如下 图(b)所示。,容易看出,不论按什么方向放置板块,每一板块均盖住 奇数个黑格(1格或3格),故盖住棋盘的板块必有偶数 个,从而,mn的棋盘必能被8整除。,例6 拟将一批尺寸为124的的商品装入尺寸为666的正方体包装箱中,问是否存在一种装法,使装入的该商品正好充满包装箱。,解 将正方体剖分成27个222的小正方体,并 按下图所示黑白相间地染色。,再将每一222的小正方体剖分成111的小正方体。 易见,27个222的正方体中,有14个是黑的,1
6、3个是白的(或13黑14白),故经两次剖分,共计有112个111的黑色小正方体和104个111的白色小正方体。 虽然包装箱的体积恰好是商品体积的27倍,但容易看到,不论将商品放置在何处,它都将占据4个黑色和4个白色的111小正方体的位置,故商品不可能充满包装箱。,德国著名的艺术家Albrecht Drer(1471-1521)于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里,我们仅研究铜币右上角的数字问题,所谓的魔方是指由1n2这n2个正整数按一定规则排列成的一个n行n列的正方形 。n称为此魔方的阶 。,Drer
7、魔方:4阶,每一行之和为34,每一列之和为34,对角线(或反对角线)之和是34,每个小方块中的数字之和是34,四个角上的数字加起来也是34,什么是Drer魔方,多么奇妙的魔方!,铜币铸造时间:1514年,构造魔方是一个古老的数学游戏,起初它还和神灵联系在一起,带有深厚的迷信色彩。传说三千二百多年前(公元前2200年),因治水出名皇帝大禹就构造了三阶魔方(被人们称“洛书”),至今还有人把它当作符咒用于某些迷信活动,大约在十五世纪时,魔方传到了西方,著名的科尼利厄斯阿格里帕(1486-1535)先后构造出了39阶的魔方 。,如何构造魔方,奇数(不妨n=5)阶的情况,1,2,3,4,5,6,7,8,
8、9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,魔方数量随阶数n增长的速度实在是太惊人了!,同阶魔方的个数,允许构成魔方的数取任意实数,允许取实数,n阶魔方A、B,任意实数、,A+B是n阶魔方,具有指定性质的魔方全体构成一个线性空间,问题已发生了实质性变化,注:刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底,松驰问题的讨论,1在第一行中共有4种取法,为保持上述性质的成立,第二行中的1还有两种取法。当第二行的1也取定后,第三行与第四行的1就完全定位了,故一共可作出8个不同的最简方阵,称之为基本魔方并记之为Q1, ,Q8,仍以4阶方阵
9、为例。 令R为行和,C为列和,D为对角线和,S为小方块和 定义0-方:R=C=D=S=0 定义1-方:R=C=D=S=4,R=C=D=S=1的方阵构成的线性空间具有什么样的性质?,类似于构造n维欧氏空间的标准基,利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。,显然, Drer空间(简称D空间)中任何一个元素都可以用Q1,Q2,Q8来线性表示,但它们能否构成D空间的一组基呢?,等号两边对应元素相比较,得r1=r2=r7=0, 所以 是线性无关,是D空间的最小生成集。,令D 即解方程组:,=,解得 D=,研究Albrecht Drer铸造的铜币,D空间的子空间和D空间的扩展,(1)要求
10、数字方的所有数都相等 这是集合G=rE,rR, G是以G=E为基的一维向量空间,进一步讨论,(4)仅要求行和与列和相等 得到10维向量空间 基向量B=Q1,Q2,Q7,N1,N2,N3 其中Q1,Q2,Q7是D的基,而,(5)对数字没任何要求 所有44数字方组成16维向量空间M 基向量MB的元素应是标准基(即仅有一个 元素为1,其余元素均为0的阵)。,Botsch(1976年)证明了对于1与16之间的每一个数K,都存在K维的44方的向量空间,由上可知,有下式成立 : (向量空间) (维数) 0 1 5 7 8 10 16,什么是拼方问题,在H.E.Dudeney所写的Cantebury难题一书
11、中有一个正方形的图案,这个正方形图案是由一个小长方形和若干个边长各异的小正方形组成的。小长方形的长为 ,宽为 ,要求求出所有正方形的边长和拼接方法。这种拼接过程称为拼方,而这种类型的问题称为拼方问题。,受上一问题的启示,加拿大数学家W.T.Tutte, A.Stone等人考虑了如下问题:,怎样的长方形可以剖分成若干个边长各异的小正方形? 正方形能否剖分成边长各异的小正方形?,称具有上述性质的长方形为完美长方形,正方形为完美正方形。,Z.Moron的完美长方形很接近完美正方形,Tutte等人用来分析Moron给出例子的 奇特方法:,用点表示水平边,用边表示小正方形。边长即小正方形之边长,方向规定
12、由上到下。于是一个剖分好的完美长方形被十分巧妙地转化成了一个有向图网络,见下图,除表示上、下两底边的顶点以外,其余顶点处指入边边长之和应等于指出边边长之和,由上面说明:假如我们把得到的有向图网络看作电网络,则所述性质恰好就是电学中的基尔霍夫定律。,若将每边看成一个单位电阻,在给出正极A与负极F之间的电势差后(相当于给出长方形的高),即可求出每条边上的电流强度(等于两顶点间的电势差),而这些数恰好就是小正方形的边长。,此外还可看出,解应当是唯一的,因为在给定A、F间的电势差后,各边上的电流强度是唯一确定的。,分析Moron给出的完美长方形,取高为32,则相应电网络中的电流强度xi(i=1,9)应
13、满足: 其解为: (x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,15,4,7,8,1,14,10,9), 恰为相应小正方形的边长。此外,由x1+x2=33可知,长方形的宽应为33。,可以不管长方形的剖分,直接根据图的各种情况利用计算机来搜查,前面分析是在对完美长方形作了剖分的前提下作出的,不知道剖分情况怎么办?,有向图只有三条边的图见图1。 由x1= x3可知不存在3阶完美长方形。,由四条边组成的有向图可以有两种形式, 见图2中的(a)、(b),它们均不可能对 应完美长方形。,逐阶寻查下去可发现,完美长方形对应的电网络必有以下性质,根据这两条性质,可以发现完美长方形的最小阶
14、数为9,进而可作出各种9阶、10阶、11阶完美长方形。,当然,随着阶数增大,计算量将按指数增长,因为相应电网络的数目是按指数增长的。,Tutte等人将他们用人工方法得到的完美长方形列成了一个表,其中包括有二百多个完美长方形。1960年,人们用电子计算机求得了9至15阶的全部完美长方形,可其中没有一个是完美正方形!,是否存在完美正方形?,当求得的完美长方形的长恰好等于宽的十分巧合的情况下,我们才能得到一个正方形的剖分。由于计算量过大,在计算机上寻查并未获得成功,最早作出的正方形的剖分是基于非常复杂的图形并用对称性人工凑出来的,它具有69阶。后来又作出了39阶和38阶的完美正方形。接着Tutte等
15、人利用他们获得的完美长方形表又拼凑出一个26阶的完美正方形,它是由一个边长为231的正方形和两个完美长方形拼合而成的,如图所示。,在此之前,人们对图论还没有多少研究。Tutte等人在引入网络图方法后,十分自然地将兴趣转向了对图论的研究,并因此而获得了许多具有重大意义的开创性结果,直接促进了图论的发展。,对一个完美长方形也可用垂直线代替水平线,用类似方法作出另一个有向图。所以对一个确定的完美长方形,我们可以获得的两个不同的有向图。,添加,添加,前面我们已经看到,由几个完美长方形可以拼出一个新的完美长方形。相应地,新网络图与原有的完美长方形的网络之间存在着十分密切的联系。应当看到这种拼合而成的完美
16、长方形是比较特殊的,它们与那些非拼合而成的(基本)完美长方形有着重大的区别,这些区别必然会在图论中反映出来。例如,考察由两个完美长方形拼接成的完美长方形,可以导出下述定义:, 8.2 合作对策模型,在上一章我们已经看到,从事某一活动的各方如能通力合作,常常可以获得更大的总收益(或受到更小的总损失)。本节主要讨论在这种合作中应当如何分配收益(或分摊损失),这一问题如果处理不当,合作显然是无法实现的。先让我们来分析一个具体实例,分析 本问题中三城镇处理污水可以有五种方案: (1)每城镇各建一个处理厂(单干)。 (2)城1,城2合建一个,城3单独建一个(1、2城合作建于城2处)。 (3)城2,城3合
17、建一个,城1单独建一个(2、3城合作建于城3处)。 (4)城3,城1合建一个,城2单独建一个(1、3城合作建于城3处)。 (5)三城合建一个污水处理厂(建于城3处),容易计算:,以三城合作总投资为最少,费用怎么分摊呢?,建厂费用按三城污水量之比5:3:5分摊,管道是为城1、城2建的,应由两城协商分摊。,同意城3意见,由城2城3的管道费用可按污水量之比5:3:5分摊,但城1城2的管道费用应由城1承担。,分摊方案有道理,但得作一番 “可行性论证”,,城1的“可行性论证”:,联合建厂费 : (万元) 城1负担 : (万元) 城1城2管道费: (万元) 全部由城1负担 城2城3管道费: (万元) 城1
18、负担 : (万元) 城1的总负担 :约为2457万元,城1自己建厂费用 :2300万元,合作后城1费用增加!,差点做了冤大头!,怎样找出一个合理的分摊原则,以保证合作的实现呢?,N人合作对策模型,设有一个n人的集合I=1,2,n,其元素是某一合作的可能参加者。,(1)对于每一子集S I,对应地可以确定一个实数V(S),此数的实际意义为如果S中的人参加此项合作,则此合作的总获利数为V(S),十分明显,V(S)是定义于I的一切子集上的一个集合函数。根据本问题的实际背景,还应要求V(S)满足以下性质:,(2)定义合作结果V(S)的分配为 ,其中 表示第i人在这种合作下分配到的获利。显然,不同的合作应
19、有不同的分配,问题归结为找出一个合理的分配原则 来, 被称为合作对策,1953年Shapley采用逻辑建模方法研究了这一问题。首先,他归纳出了几条合理分配原则 应当满足的基本性质(用公理形式表示),进而证明满足这些基本性质的合作对策 是唯一存在的,从而妥善地解决了问题。,是否存在合理分配原则,Shapley提出了以下公理: 设V是I上的特征函数, 是合作对策,则有,公理1,合作获利对每人的分配与此人的标号无关。,公理2,,即每人分配数的总和等于总获利数。,公理3,若对所有包含的i的子集S有: V(S-i)=V(S), =0。,即若第i人在他参加的任一合作中均不 作出任何贡献,则他不应从合作中获
20、利,公理4,若此n个人同时进行两项互不影响的合作,则两项合作的分配也应互不影响,每人的分配额即两项合作单独进行时应分配数的和。,利用上述公理可以证明满足公理14的 是唯一存在的(证明略),存在 的公式吗,Shapley指出, 可按下列公式给出:,(8.1) i=1,n,可视为i在合作 S中所作的贡献,W(|S|)可看作这 种贡献的权因子,合作的获利真的不少于他单干时的获利吗,对每一iI,有,求证:,证明:,|S|=K时,包含i的子集S共有 个,即 个,故 = 1/n,从而,又根据性质,有,故有,城1究竟应当承担多少费用,首先不难看出 : S1=1,1,2,1,3,1,2,3 计算出与(11.1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 逻辑 模型
链接地址:https://www.31doc.com/p-3164981.html