数学模型课件(2007-03-07)

1、数 学 模 型么焕民哈尔滨师范大学信息科学系2008年3月7日需要阅读的参考书目1. 姜启源.数学模型(第三版).高等教育出版社.2003年2. 朱道元等. 数学建模案例精选. 科学出版社. 2003年3. 邹瑾 杨国安.开心数学.哈尔滨工业大学出版社.2003年4. 韩伯棠 吴祁宗 李金林.管理数学. 北京理工大学出版社5. 蓝伯雄 程佳惠 陈秉政.管理数学(下)-运筹学.清华大学出版社 6. 胡运权.运筹学教程(第二版). 清华大学出版社.2003年7. 朱德通. 运筹学. 上海人民出版社. 2001年8.线性代数或高等代数 9.数学分析10.常微分方程第一章 认识数学模型 提出三个简单的

2、实际问题【问题一】 已知甲桶放10000个蓝色的玻璃球，乙桶中放有10000个红色的玻璃球，任取甲桶中100个球放入乙桶中混合后再任取乙桶中的100个球放入甲桶中，如此重复三次。问甲桶中的红色球多还是乙桶中的蓝色球多？解:设甲桶中有x个红色球,乙桶中有y个蓝色球，由于两个桶中的蓝色球总数为10000个，则有 从而 【问题二】 能否将一张纸对折100次? 对折1次：2层= 21 对折2次：4层= 22 对折3次：8层= 23 对折100次: 2100假如普通纸每张厚度为0.05mm，又因为：210=10241000=103故 21001030 所以2100层纸厚度.051030mm =51022

3、 km计算结果为5万亿亿千米注意到: 地球到距太阳不过1.5亿千米！ 所以此问题的答案是否定的。 类似的，在日常生活中有许许多多的实际问题，有些好像与数学无关，但通过细致的观察分析与假设，都可以应用数学方法简捷和完美的解决。此乃数学模型的魅力。分析【问题三】数学与魔术-神奇的斐波那契数列1.洞从哪里来？ 如图，将两条长度分别为（8+5）与（2+1+2）的直角边剪裁成图A所示的四块几何图形，然后再重新拼接成图B，它仍是一个直角三角形，其边长分别是（5+2+1+5）和（3+2）,但是我们会惊奇的发现与图A相比,图B多出了一个洞,这个洞从哪里来？2122222221111133355585图A图B如

4、图，将图A中面积为1313=169的正方形裁剪成四块几何图形,然后重新拼接成图B，计算可知长方形的面积为821=168,比原来的正方形少了一个单位的面积，面积怎么会减少呢？ 55555588888888131313图A图B2. 面积怎么少了？出现“差错”的原因 以第二个问题为例，题中涉及到四个数据：5，8，13，21，正是斐波那契数列中的四项，斐波那契数列的特征是从第三项开始的每一项都是它的前两项的和： 1，1，2，3，5，8，13，21，34，58， 我们可以使用这个数列的其它任意相邻四项来试验这个过程，发现无论选取哪四项，都可以得出关于斐波那契数列的一个重要性质：这个数列任意一项的平方等于

5、它前后相邻两项之积加1或者减1。即：得到以下重要结论： 正方形的面积和长方形的面积不会相等，有时候正方形的面积比长方形的面积多一个单位，有时候正方形的面积比长方形的面积少一个单位。即正方形的面积，长方形的面积 知道了这个事实后，我们就可以随心所欲的构造类似第二个问题的几何趣味问题了。 如：用8，13，21，34来构造类似上述的问题，会得到同样类似的神奇结果。超级链接-广义斐波那契数列与黄金分割比上面提及的斐波那契数列是以1,1两数开始的,广义的斐波那契数列可以从任意两数开始.如用广义的斐波那契数列 2,2,4,6,10,16 ,做上述试验,就会多得或丢失4个单位的面积. 如果用 表示广义斐波那

6、契数列的相邻三项,以 表示“得”或“失”的数字，则成立 问题：把正方形按上述方法剪成四块，是否会拼成一个与它面积相等的长方形？此问题的求解：令方程组中的 等于零，再解之得到唯一的正解是： 其中 恰是著名的黄金分割比。通常用 来表示，它是一个无理数，其值是1.618033.；也就是说 ，唯一的每项平方等于前后相邻两项之积的斐波那契数列是： 要证明它的确是斐波那契数列，只要证明它等价于数列即可。（请自己证明这个结论并解释前面的第一个问题）超级链接-小知识 公元5-11世纪,是欧洲历史上的黑暗时期,天主教会成为欧洲社会的绝对势力,由于封建宗教的统治,使一般人笃信天国追求来世,从而淡漠世俗生活对自然不

7、感兴趣.教会宣扬天启真理并拥有解释这种真理的绝对权威,导致了理性的压抑.欧洲文明在整个中世纪处于凝滞状态.由于罗马人偏重于实用而没有发展抽象数学,这对罗马帝国崩溃后的欧洲数学也有一定的影响,终使黑暗时代的欧洲在数学领域毫无成就. 直到12世纪,由于受翻译,传播阿拉伯著作和希腊著作的刺激,欧洲数学才开始出现复苏的迹象.1100年左右,欧洲人通过贸易和旅游,同地中海地区和近东的阿拉伯人以及东罗马帝国的拜占庭人发生了接触,十字军为掠夺土地的东征,使欧洲人进入了阿拉伯世界,从此欧洲人从阿拉伯人和拜占庭人那里了解到希腊以及东方古典学术.中世纪欧洲数学历史上的黑暗时期 斐波那契欧洲数学走向复苏的号角 欧洲

8、黑暗时期过后,第一位有影响的数学家就是斐波那契（L.Fibonacci1170-1250）他早年就随其父在北非师从阿拉伯人学习算学，后又游历地中海沿岸诸国，回意大利后写成算经，亦作算盘书。 这部很有名的著作主要是一些源自古代中国、印度和希腊的数学问题的汇集,内容涉及整数和分数算法，开方法，二次和三次方程和不定方程，特别是书中系统地介绍了印度-阿拉伯数码，对改变欧洲数学的面貌产生了很大的影响. 1228年的算经修订版载有著名的兔子问题： 某人在一处有围墙的地方养了一对兔子，假定这对兔子每月生一对小兔，而小兔出生后两个月就能生育。问从这对兔子开始一年内能繁殖成多少对兔子。 对这个问题的回答导致了著

9、名的菲波那契数列的产生。算经可以看作是欧洲数学在经历了漫长的黑夜之后走向复苏的号角。超级链接-斐波那契数列： 【小知识】Lionardo Fibonacci（约11701250）数列 据记载,历史上首先是由19世纪法国数学家吕卡将级数Un：1，1，2，3，5，8，13，21，34，.命名为斐波那契级数，它是一种特殊的线性递归数列，un+2=un+un+1，n=1,2,3 在许多数学分支中都有极其广泛的应用。以下就是一个有趣的斐波那契级数问题。斐波那契兔子的问题 某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。 该

10、问题记载于公元前13世纪意大利数学家斐波那契的名著算盘书（1202）1228年的修订本中，并在原书中对此作了分析：第一个月是最初的一对兔子生下一对兔子，围墙内共有两对兔子。第二个月仍是最初的一对兔子生下一对兔子，共有3对兔子。到第三个月除最初的兔子新生一对兔子外，第一个月生的兔子也开始生兔子，因此共有5对兔子。 继续推下去，第12个月时最终共有对377对兔子。 书中还提出:每个月的兔子总数可由前两个月的兔子数相加而得。 1.1 什么是数学模型 一、有关的几个概念 1.原型：指人们在现实世界里关心,研究或从事生产,管理的实际对象. 2.模型：为了某个特定的目的,将原型的某一部分信息简缩,提炼而构

11、造的原型的替代品. 3.原型与模型的关系：原型是模型的前提与基础，模型是原型的提炼与升华。原型有各个方面和各个层次的特征，而模型只要求反映与某些目的有关的那些方面和层次。二、什么是数学模型 数学模型 对现实世界上的一个特殊对象，为了一个特定目的，根据特有的内在规律，做出一些必要的假设，运用适当的数学工具，得到的一个数学结构。或者 对于现实世界中的具体问题，往往不能以现成的数学形式出现，需要我们抽象，再将其尽可能地简化，通过假设变量和参数运用一些数学方法建立变量和参数间的数学关系，这样抽象出来的数学问题就是-数学模型。 通过数学方法对模型进行分析求解，最后再解释和验证所得的解，进而为解决现实问题

12、提供数据支持和理论指导，这个过程称为数学建模。三、建立数学模型的全过程 数学模型 现实对象的解答 模型的解答 现实对象的信息 四、模型的分类 1、按应用领域分（或学科）：人口模型，交通模型、环境模型，城镇模型、规划模型、生态模型、水资源模型等；2、按建模的数学方法（数学分支分）：初等数学模型，几何模型，微分方程模型，概率、图论模型；3、按表现特征分：确定性模型与随机性模型；静态模型与动态模型；线性模型与非线性模型；离散模型与连续模型；4、按建模的目的分：描述模型，分析模型，预报模型，优化模型，决策模型，控制模型等.5、按对模型的了解分：白箱模型，灰箱模型，黑箱模型等。 五、历史上成功的建立数学

13、模型的例子 阅读 说到数学模型的建立或数学建模，似乎是一个新东西、新名词，其实是古已有之的。一个最典型也最成功的数学建模的例子是行星运动规律的发现。开普勒根据他的老师第谷近30年天文观测的大量数据，用了10年时间总结出行星运动的三个规律，但当时还只是经验的规律，只有确认这些规律，找到它们内在的根据，才能有效地加以运用。牛顿提出与距离平方成反比的万有引力公式，利用运动三大定律证明了开普勒的结论，严格推导出行星运动的三大定律，成功地解释并预测了行星运动规律，也证明了他建立的数学模型的正确性。这是数学建模取得光辉成功的一个著名的例子。1.2 椅子在不平坦地面上的稳定问题 这个问题来源于日常生活中许多

14、人常遇到的极其普遍但可能没有引起足够注意的现象，即任意一把放在不很平坦的地面上的多于三条腿的椅子，通常是不稳定的，但只要将椅子适当地移动位置,它便能放稳。这种现象表面上看与数学模型关系不大,其实我们完全可以运用数学方法来具体地解释这种现象。 三点可以确定一个平面，因而一把多于三条腿的椅子无论怎样放置，对于相对比较平坦的地面来讲，总可以保证有三条腿同时着地，因而只需再使其余的椅腿也能完全着地即可。 一、问题的提出问题椅子能在不平的地面上放稳吗？1.椅子四条腿一样长，椅脚与地面接触处可视为一个点，四脚的连线呈正方形；2.地面高度是连续变化的，沿任何方向都不会出现间断（没有像台阶那样的情况），即地面

15、可视为数学上的连续曲面；3.对于椅脚的间距和椅腿的长度而言，地面是相对平坦的，使椅子的任何位置至少有三只脚同时着地。模型假设ABCDtABCDOx模型构成椅脚连线为正方形ABCD(如右图)。t 椅子绕中心点O旋转角度f(t)A,C两脚与地面距离之和g(t)B,D两脚与地面距离之和 f(t), g(t) 0模型构成由假设1，f 和 g都是连续函数由假设3，椅子在任何位置至少有三只脚同时着地：对任意t ，f(t)和g(t)中至少有一个为0。当t=0时,不妨设g(t)=0,f(t)0,原题归结为证明如下的数学命题：已知f(t)和g(t)是t的连续函数,对任意t, f(t) g(t)=0,且g(0)=

16、0,f(0)0。则存在t0，使f(t0)= g(t0)=0模型求解OxABCDABCDt最后，因为f(t) g(t)=0，所以f(t0)= g(t0)=0。将椅子逆时针旋转 则对角线AC与BD的位置互换。 可知 令h(t)= f(t)-g(t),则h(0)0和h( ) 0，由f和g的连续性知h也是连续函数.根据连续函数的基本性质,必存在t0 (0t00为比例常数)三 模型的假设 假设某种细菌的个数按照指数方式增长, 如下表所示天数细菌个数5936102190 求:开始时细菌的个数可能是多少? 若继续以现在的速度增长下去, 假定细菌无死亡, 那么60天后细菌的个数大概是多少?四 模型的求解 (1

17、) 建立数学模型 为了计算出t时细菌的个数, 我们将时间间隔0,t分成几等份由于细菌的繁殖过程可视为连续变化的,在很短的一段时间内数量的变化很小,繁殖的速度可以近似地看作不变. 即假设在每一个小时间段(i-1)t/n, it/n(i=1,2,n)内细菌的繁殖速度不变, 且在各小段时间内只繁殖一次.因此在第一段时间0,t/n内,细菌繁殖的数量为kA0t/n,第一段时间末细菌的数量为A0(1+kt/n); 第二段时间末细菌的数量为A0(1+kt/n)2 ;依此类推,到最后一段时间末细菌的数量为 由此可知,当时间间隔分得越细(即n越大)时, 这个值越接近精确值,如果对时间间隔无限细分(即n ),则可

18、求得其精确值. 所以, 经过时间t后细菌的总数是:设细菌总数为y, 即模型为(2)细菌繁殖服从生长函数由题目所个数据得解此方程组,得:即: 开始时细菌个数为400个,按此速度增长下去,则60天后细菌个数为第三章 线性规划模型 如何来分配有限的资源, 从而达到人们期望目标的数学模型,又称为分配模型. 它在运筹学中处于中心地位. 最优分配问题, 一般可以归结为数学规划问题, 其中最简单,最常用的一类模型就是线性规划模型. 线性规划(Linear Programming,简记为LP)是数学规划中提出较早, 在理论和算法上也比较成熟的一个分支. 而数学规划则是运筹学的一个重要分支,它起源于工业生产组织

19、管理的决策问题, 广泛应用于最优化设计,工农业生产,国防建设,交通运输, 决策管理与规划等领域. LP问题不仅在实际中有广泛应用,而且运筹学的其他分支里的许多问题也可以化归为线性规划问题来处理. 运筹学经过半个多世纪的发展, 现在已经形成了一个相当庞大的学科, 其内容相当丰富,主要包括: (Linear Programming) (Nonlinear Programming) (Integer Programming) (Multiobjective Programming) (Dynamic Programming) (Games Theory) (Decision Theory) (Inv

20、entory Theory) (Queuing Theory)(Graph Theory) (Forecast Theory)第一节 线性规划(LP)问题 3.1 几个实例 【例1】生产安排问题 某工厂利用三台设备，生产三种不同的产品。各种产品每生产一件在各台设备上所需要的加工时间(分钟)各台设备每天的生产能力(每天的工作时间)以及每件产品的单位利润如下表。 问怎样安排生产才能使每天获得的利润最大？ 假如每天生产B1，B2，B3三种产品数量分别为x1,x2,x3件，每天的利润为 之为决策变量.由于每台设备可提供的可以使用的资源是有限的,不能超过它的最大生产能力，所以变量应满足条件： 再考虑到每

21、种产品的产品都不可能是负值,即xj0,(j=1,2,3)每天的总利润最大是我们追求的目标,所以称 为目标函数, 而变量 的值是我们需要确定的, 故称 (3.1.2) (3.1.1) 综上所述，这个生产安排问题可归结为： 求变量 满足以下约束条件 使目标函数 的值最大。(3.1.3) 上述问题的数学模型简记为其中max是maximize的缩写,中文意思是”求的最大值”,s.t.是subjuct to的缩写, 中文意思是”受约束于”或”约束条件”.(3.1.4) 由于在问题(3.1.4)中, 目标函数 S=f(x1,x2,x3) 是变量x1,x2,x3的线性函数, 约束条件是x1,x2,x3的线性

22、不等式,所以我们把问题(3.1.4)称为线性规划问题.一般的拟订生产计划问题 设有m种资源: A1,A2,Am, 拟生产n种产品:B1,B2,.,Bn. 用aij表示生产一个单位第j种产品所需要的第i种资源的数量,用bi表示第i种资源的使用限额,用cj表示销售一个单位的第j种产品获得的利润,用xj表示第j种产品的生产数量, 则x=(x1,x2,xn)T就代表一个生产计划, 我们的问题是: 要设法安排一个生产计划,使该厂可获得最大的总利润.解: 在这个问题中, 决策变量为x1,x2,xn. 设总利润为Z, 则目标函数为(3.1.5) 因而拟订一个最优的生产计划问题可以归结为以下的LP问题:一般的

23、拟订生产计划问题(3.1.6) 【例2】运输问题 运输问题是线性规划模型中最早被研究的一类问题, 早在1939年,苏联数学家 .B.康托洛维奇写了生产组织与计划中的数学方法一书, 在该书中就提出了这一类问题的数学模型和求解方法. 【例2】运输问题 设有两个砖厂A1,A2,其产量别为23万块与27万块。它们生产的砖供应三个工地B1,B2,B3,其需要量分别为17万块,18万块和15万块。从各个生产地点到各个工地的运价如教材中P3-表1.2. 问应如何调运，才能总运费最省？ 求解 设 表示由砖厂 运往工地 砖的数量（单位:万块) 例如 表示由砖厂 运往工地 砖的数量等. 由题意 运往三工地 的总数

24、分别是23、27,得： 由于三工地 需求量分别是17、18、15得：因此，调运必须满足下列约束条件： (3.1.8) (3.1.7) (3.1.9) 满足这个约束条件的调运方案很多，我们希望在这些方案中找到一个运费最少的方案，即求一组变量的值，使它满足约束条件 并使以下目标函数的值最小（即总运费最少）(3.1.10) 上述问题的数学模型简记为运输问题的一般形式例: 假设某种物质有m个产地, 有n个销地. 第i个产地的产量为ai,i=1,2,m;第j个销地的需要量为bj,j=1,2,n.其中由产地i到销地j的距离已知为dij.问应如何分配该种物质,使既能满足各地的需要, 又使所花费的运输总吨公里

25、数最少?(3.1.11) 解: 用xij表示产地i供给销地j的物质数量, 设s为运输的总吨公里数, 则上述问题的数学模型为运输问题的一般形式【例3】食谱问题 例: 一饲养场饲养供实验用的动物, 已知动物生长对饲料中的三种营养成份-蛋白质,矿物质和维生素特别敏感. 每个动物每天至少需要蛋白质70g, 矿物质3g, 维生素10mg.该饲养场现有五种饲料, 每种饲料10kg的成本如下: 单位:元饲料A1A2A3A4A5成本27435每一千克饲料中所含的营养成分如下表:饲料蛋白质/g矿物质/g维生素/mgA10.300.100.05A22.000.050.10A31.000.020.02A40.600

26、.200.20A51.800.050.08 我们希望确定既能满足动物需求, 又使总成本为最低的饲料配方. 试建立相应的数学模型. 解: 设动物每天食用的混合饲料中所含的第j种饲料Aj 的数量为xj(kg), 混合饲料的总成本为y, 则上述问题的数学模型为一般的食谱问题可叙述如下: 假定有n种食品, 每种食品中含有m种营养成分. 用aij表示一个单位的第j种食品中含有第i种营养的数量, 用bi表示每人每天对第i种营养的最低需要量, cj表示第j种食品的单价, Xj表示所用的第j种食品的数量. 问应怎样选配食品,才能保证在满足m种营养成分的条件下, 使食品的总成本y最低? (3.1.12) (3.

27、1.13) 【例4】下料问题 某工厂有一批长度为300cm的钢管(数量充分多),要把它们截成长度为45cm、80cm和95cm的管料,并要求其根数成的比按5:3:2来配套生产某种零件，问采用怎样的方案进行锯割,可使得到的三种管料既能配套又能使残料最少？ 解：首先，我们用下表列出可能的各种截法：截法12345678910长度45cm80cm95cm600410401320211202130121012003残料304025535201503015求解 设 表示按照第j种截法锯割的钢管的根数，那么截出的长45cm管料的根数为截出的长80cm管料的根数为截出的长95cm管料的根数为此时，残料的长度为

28、于是，我们要解决的问题归结为下列数学形式：求满足以上条件的 使得取最小值。 不难看出，上面这些问题虽然各式各样，但它们的数学模型却有相同的数学形式，即：求一个线性函数的最大值（或最小值），而这个线性函数的变量是非负的，满足一组线性等式或不等式。我们把具有这种模型的问题称为线性规划问题。 所以线性规划问题的数学模型的一般形式为 求 （或 ） 它的变量满足(3.1.14) (3.1.15) 3.2 线性规划问题的基本概念 线性规划问题的数学模型有许多种，目标函数有求最小值的，有求最大值的；约束条件有的是“”形式的，也有“”或“”形式的。我们希望能把各种不同形式的线性规划问题的数学模型化为一种统一的

29、标准形式，这样只要对标准形式找出一种解法，就可以解决其余不同形式的线性规划问题了。 (一) 线性规划问题的标准形式 规定下列形式的线性规划问题为标准形式：(3.1.17) (3.1.16) 其中 均为常数，且 此标准形式可以写成矩阵的形式：求其中 (3.1.19) (3.1.18) (二) 怎样把线性规划问题的非标准形式化为标准形式1、如果目标函数是求 则只需要令 便有 把求得的 的值反号,便可得到原问题的最小值。 2、如果第个约束条件为则引入松弛变量 上式便可化为 3、如果第 个约束条件为 则引入剩余变量 上式化为 注意：松弛变量和剩余变量所以它们在目标函数中的系数为0。都不是决策变量,4、

30、如果第 个约束条件为等式，但有某个常数 则在第个等式的两边同时乘以化为 (此时 )5、如果某个决策变量 没有非负约束，则令 且 代入约束方程与目标函数则全部都有非负限制了。【例1】把下面的线性规划问题化为标准形式原问题标准形式【例2】把下面的LP问题化为标准形式为了把不等式约束变为等式约束,引入松弛变量(3.1.20) 则问题(3.1.20)可转化为(3.1.21) 【例3】把下面的LP问题化为标准形式由于本题中x3没有非负限制,是自由变量,故引入松弛变量令为了使上述约束条件中的不等式变为方程, 再引入松弛变量则上述线性规划问题就可以转化成标准形式了.和剩余变量一. 凸集和极点3.3 线性规划

31、问题的基本概念 直观的看, 三角形, 矩形, 圆, 球体等, 其形体都是凸的都有这样的几何特性, 即连接形体中任意两点的线段都在该形体之中. 因此, 我们可以这样来定义凸集. 定义1 设集SEn, 如果对任意点的任何,都有, 则S称为凸集.1. 凸集例1 满足LP问题约束条件的一切x所成的集R是一个凸集.证明. 因为有所以有且即证毕.定义2. 满足LP问题约束条件的点称为可行点或可行解, 所有可行点构成的集合R称为可行集或约束集,记为2. 极点与基本可行解定义3 设集SEn为凸集, xS, 对于x, 若找不到两个不同的点y,zS,使,则称x为凸集S的一个极点或顶点.例如: 三角形的顶点, 圆周

32、上的任意一点均为极点.对于定义2中的算式,设 A的秩为m, 即r(A)=m. 则可从A的n列中选出m列,使它们线性无关, 为了书写方便, 不妨设A的前m列线性无关, 即设是线性无关的, 令则B是可逆的.因此方程组例2. 考察线性规划问题解: 若令x1=x2=0, 则可得x3=9,x4=8,x5=1,即x=(0,0,9,8,1)T显然x是一个可行解. 由于是线性无关的, 故这个可行解x关于基底B=(a3,a4,a5)又是基本解. 而且是非退化的, 所以x是一个非退化的基本可行解. 其中x1,x2是非基变量, x3,x4,x5是基变量.下面的定理说明了极点与基本可行解之间的关系.证明: (1)必要

33、性 即设x为R的一个极点, 则x是Ax=b, x0的一个基本可行解. 设x有k个分量大于零, 不妨设其前k个分量xi0,i=1,2,k, 用ai表示A的第i列, 于是 我们来证明a1,a2,ak是线性无关的, 因而x=(x1,x2,.,xk,0,0)T 就是一个基本可行解.用反证法. 设a1,a2,ak是线性无关, 则必有k个不全为零的数y1,y2,yk, 使用反证法. 设不是R的一个极点, 则必有R中的两个不同的点y,z,使得x=sy+(1-s)z,(0s1)即xj=syj+(1-s)zj,j=1,2,n.因当j=k+1,k+2,n时, xj=0,故上式成为 0=syj+(1-s)zj,j=

34、k+1,k+2,n又因为yj 0,zj0,0s0,y20, 于是我们就得到了关于家具厂的另外一个线性规划问题:原来的问题:仔细观察, 看看它们之间的联系是否很密切呢?二 对偶线性规划问题的种类（1）对称形式的对偶规划（2）非对称形式的对偶规划对称形式的对偶规划问题原问题对偶问题对称形式的对偶线性规划问题的矩阵表示原问题对偶问题其中三 如何将原问题转化为对偶问题原问题对偶问题1 目标函数求max S目标函数求min Z2 目标函数中的系数ci约束条件中的右端项ci3 约束条件中的右端常数项bj目标函数中的系数bj4 约束条件的系数矩阵A约束条件的系数矩阵AT5约束条件有m个对偶变量有m个6决策变

35、量有n个约束条件有n个7约束条件为”0”(”0” ,=0)对偶变量”0”(”0”,无限制)8决策变量”0” (”0”,无限制)约束条件为”0”(”0”,”=0”)原问题(P)为对偶问题(P)为或者例 写出下列LP问题的对偶问题 竞赛题赏析: 两辆铁路平板车的装货问题 1988年美国数模竞赛(MCM)(B题) 有七种规格的包装箱要装到两辆平板车上,包装箱的宽和高是一样的但厚度t(以厘米计)及重量w(以公斤计)是不同的. 下表给出了每种包装箱的厚度,重量以及数量. 每辆平板车有10.2米长的地方可用来装包装箱(象面包片那样),载重量为40吨. 由于地区货运的限制, 对C5,C6,C7类包装箱的总数

36、有一个特别的限制:这三类箱子所占的总空间(厚度)不能超过302.7厘米.包装箱类型C1C2C3C4C5C6C7T(厘米)48.752.061.372.048.752.064.0W(公斤)200030001000500400020001000数量879664810.2m问题要求：(一) 问题的假设1. 包装箱不能分割成较小的部分;2. 所有的数据均是精确值,无任何测量误差;3. 给出的解,均可进行装卸.(二) 模型的建立容易计算出所有包装箱的总厚度为27.495米,事实上有设计一种装车方案,使剩余的空间最小。 以xij表示装到第j(j=1,2)辆铁路平板车上的第i种包装箱Ci的个数(1i7);

37、xij是本问题里的决策变量。总厚度=48.78+52.07+61.39+72.06+48.76 +52.04+64.08=27.495(米) 而两辆铁路平板车总共有20.4米(10.22) 长的地方,所以不可能把包装箱全部装运上车。符号说明:Ni - 表示类型为Ci的包装箱的总件数；Wi- 表示类型为Ci的包装箱的每件重量； ti - 表示类型为Ci的包装箱每件厚度； S - 表示剩余的空间。我们的目的是使装车剩下的空间最小。为此构造模型如下：约束条件为此ILP模型还可以写成以下形式：对上述整数线性规划问题(ILP)用分枝定界法可求得30个不同的解如下(没有利用的空间为0.6cm)平板车1平板

38、车21234567123456742533004443030429120045051304253310454302041912104605120415332046430104091220470511040533304743000374310050532303705210509112036431105153220箱子类型续前表平板车1平板车2123456712345673605220519111035431205253210350523052911003443130535320032913005505030319131056050203091320570501027432006053130264

39、3210615312025432206253110箱子类型续前表平板车1平板车21234567123456725053306291000244323063531001643310715302015433207253010144333073530000790020800631007640008032330069003081063000664010813232005640208232310箱子类型(三) 模型的分析 现在我们分析求得的解是否最优？考虑C5、 C6、C7三种类型的箱子，它们有如下特别的限制：C5、 C6、C7类箱子的件数限制为xi1+xi2Ni (i = 5 ，6，7 ), 记并把已

40、知的ti与Ni (5 i 7 )代入，我们有这个问题的解共有315个，其中使z=48.7x5+52x6+64x7的值介于292.2，302.7之间的解有以下6个:x5x6x7Z=48.7x5+52x6 +64 x7330302.1cm420298.8cm023296.0cm510295.5cm113292.7cm600292.2cm 可以看出: 对类型为C5、C6、C7三种类型的包装箱,在所占空间厚度不能超过302.7厘米的限制下,两辆平板车最多只能装运302.1厘米宽度的包装箱.此时C5类型和C6类型的包装箱各装3只，不装C7类型的包装箱。由 即：两辆平板车装运C1、C2、C3 、C4四种类

41、型的包装箱的空间厚度为1737.3厘米，从而总的装运空间的厚度为 302.1+1737.3=2039.4(厘米)因此，装运时的剩余空间至少为 2040-2039.4=0.6 (厘米) 这说明我们求得的30个解均为最优解。如果我们进一步要求这两辆平板车装运包装箱后，使得剩余空间相同，此时的解如下：平板车厚度重量C1C2C3C4C5C6C7第一辆1019.7340000790020第二辆1019.7330008006310第一辆1019.7330000690030第二辆1019.7340008106300注意到: 最优解不装运C7类箱子。如果再进一步要求每一种类型的包装箱都必须装运一部分，从前面各

42、表中数据可以看出，此时两辆平板车装运的C1C7类型包装箱的数量应该是8,7,9,6,1,1,3.此时装完两辆平板车后，剩余的空间至少为 2040-(292.7+1737.3)=10(cm)3.7 动态规划模型 动态规划( Dynamic Programming )是用来解决多阶段决策过程最优化问题的一种行之有效的方法。1951年美国数学家贝尔曼(R.Bellman)等人根据一类多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并研究了许多数学模型，成功地解决了生产管理、工程技术等方面的实际问题，建立了运筹学理论中的一个新分支动态规划，1957年贝尔曼发表了动态规划方面的首部专著动态规划

43、。动态规划方法在工程技术、经济管理、工业生产和军事科学等领域均有着极为广泛的应用。3.7 动态规划模型动态规划问题的研究种类 1.最优路径问题 2.资源分配问题 3.投资决策问题 4.生产计划与库存问题 5.排序问题 6.货物装载问题 7.生产过程中的最优控制问题 动态规划问题的特点 动态规划不象线性规划或非线性规划有一个标准的表达式,而是不同的具体问题就有相应不同的、具体的数学表达式，从而动态规划没有统一的处理格式，它必须依据问题本身的特性,利用灵活的数学技巧来解决，因而属于灵活、动态的数学方法动态规划模型的种类 动态规划模型的种类很多，可根据决策过程的时间参数是离散的还是连续的，过程的演变

44、是确定性的还是随机性的,分为离散确定型、离散随机型、连续确定型和连续随机型四种，其中离散确定型是最基本的动态规划模型。一、动态规划模型的基本概念 1. 多阶段决策问题 所谓多阶段决策问题，是指这样的一类特殊的活动过程，它们可以按照时间和空间依次划分为若干个相互联系的阶段，在每一个阶段中，都需要做出一定的决策（备选方案），全部过程的决策集形成一个决策序列，这种考虑整个决策过程中各个阶段决策的全体又称为一个策略，这类问题就是多阶段决策问题 3. 动态规划问题的基本概念 (1) 阶段 (2) 状态 (3)决策 (4)策略 (5)状态转移方程 (6) 指标函数 二、动态规划方法的基本思想 动态规划方法

45、的产生基于贝尔曼(R.Bellman)等人在50年代提出的最优化原理:“对于一个过程的最优策略来说，无论出发其初始状态及初始决策怎样,由其先前所有决策所形成的状态，其后的剩余决策序列必构成最优策略。三、动态规划的求解方法动态规划的求解有两种方法:(1) 逆序递推法 (2) 顺序递推法四 算例最短路线问题 如图所示，某人从A出发，要把一批物资沿图中的边送至E点其中Bi,Ci,Di(i=1,2,3)代表九个小镇，所标数字代表不同道路的长度(单位:千米)。问应选择哪条行走路线，可以使总行程最短？AB1B2B3C3C2C1D1D2D3E483888897442223551465517解:用d(sk,u

46、k) 表示由点sk出发，采用决策uk到达下一阶段点sk+1时的两点间的距离,fk(sk)表示从第k段状态点sk出发,采用最优策略到过程终止时的最短距离。 采用逆序递推算法的求解过程如下：（1）从k=4开始，状态变量s4可以取三个值D1，D2，D3，因为由D1，D2，D3到E各有一条路，故容易求得f4(D1)。（2）当k=3时，状态变量s3可以取三个值C1，C2，C3，这是一个经过中途点D1，D2，D3到达终点的两步决策问题，具体求解步骤如下：（a）从C1出发，共有三个选择，即C1 D1，C1 D2 ，C1 D3 ，且有故从C1出发到终点E的最短距离为6，最短子路线为C1 D3 E。（b）从C2

47、出发，也有三个选择，即C2 D1，C2 D2 ，C2 D3 ，且故从C2出发到终点E的最短距离为5，最短子路线为C2 D3 E。（c）从C3出发，也有三个选择，即C3 D1，C3 D2 ，C3 D3 ，且故从C3出发到终点E的最短距离为6，最短子路线为C3 D3 E。（3）当k=2时，状态变量s2可以取三个值B1，B2，B3，这是一个经过中途点C1，C2，C3和D1，D2，D3才能到达终点的三步决策问题，由于第三段中各点C1，C2，C3到终点E的最短距离f3(C1), f3(C2), f3(C3)均已求得，所以若要继续求从B1，B2，B3到点E的最短距离，只需以f3(C1), f3(C2),

48、f3(C3)为基础，再分别加上B1，B2，B3与C1，C2，C3之间的相应距离，并加以比较，从而求出此阶段的最短路线。 具体求解步骤如下：（a）从B1出发，共有三个选择，即B1 C1，B1 C2 ，B1 C3 ，且有故从B1出发到终点E的最短距离为12，最短子路线为B1 C2 D3 E。（b）从B2出发，也有三个选择，即B2 C1，B2 C2 ，B2 C3 ，且有故从B2出发到终点E的最短距离为7，最短子路线为B2 C2 D3 E。（c）从B3出发，也有三个选择，即B3 C1，B3 C2 ，B3 C3 ，且有故从B3出发到终点E的最短距离为13，最短子路线为B3 C2 D3 E。（3）当k=1

49、时，状态变量s1只有一个取值，即出发点A，且即从城市A出发，到终点E的最短距离为15，最短子路线为 A B3 C2 D3 E。数学建模问题欣赏:城镇道路扫雪模型 1990年美国数模竞赛(MCM)(B题) 如图所示，实线表示美国马里兰州威克米尔市需要清除积雪的双向行车道路，虚线是州高速公路。雪后，两辆扫雪车分别从地图中号标出的两点以西约英里处出发清扫道路上的积雪。扫雪车可以通过高速公路进入市内道路，假定扫雪过程中扫雪车不会损坏或停止，并且道路交叉处不需要另外附加的扫雪程序。试为两车找出有效的路径。本题目是该城市道路局局长Kirk Banks工程师从该城实际扫雪工作中提出来的.一 相关的图论知识

50、一个图是一个有序二元组G=V(G),E(G), 其中V(G)=Vi为顶点集, E(G)=ek为边集,V=V(G)中的元素Vj称为顶,E=E(G)中的元素ek叫做边. 当V,E为有限集合时,G称为有限图,否则称为无限图.记W=V0b1V1b2Vk-1bkVk, 其中biE(G), i=1,2,3, ,k,VjV(G), j=1,2,3, ,k。若与相关联，称W是图G的一路,k为路长，V0为起点，Vk为终点。 各边相异的路叫做行迹；各顶点相异的路叫做轨道；起点与终点重合的路，叫做回路；起点与终点重合的轨道，叫做圈。 图中包含每条边的行迹叫做Euler行迹；闭的Euler行迹叫做Euler回路；含E

51、uler回路的图叫做Euler图。中国邮递员问题 某邮递员负责某地区的送信投报任务，他每天从邮局取出邮件，投递到所管辖的不同地点，然后再返回到邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望他选择一条尽可能短的路线。这个问题是我国数学家管梅谷先生1962年首先提出来的，因此被称为 “中国邮递员问题”。 在一个网络N=(V,E,W)中,经过它的每条边的链称为欧拉(Euler)链, 经过N中每一条边至少一次的闭链称为N的环游,经过N中每一条边恰好一次的环游称为欧拉环游.显然中国邮递员问题就是在具有非负权的网络中找出一条权最小的环游，这种环游称为最优环游。 若N有欧拉环游,则它的每一条

52、欧拉环游具有相同的权,它也必然是最优环游.对有欧拉环游的网络,我们可以采用弗莱里(Fleury)算法求得N的最优环游。弗莱里(Fleury)算法1. 任意选取N的一个顶点v0,置Z= v02. 假设链Z=v0e1v1e2v2eivi已选定,从Ee1, e2, ei中按下述方法选取ei+1:(1) ei+1和vi相关联;(2) ei+1尽量不选Gi(是G中去掉边e1, e2, ei而得到的图)的割边(即去掉此边后,图Gi变为不连通),除非没有非割边可选择.(3) 设ei+1的另一关联点为vi+1。若Ee1, e2, ei，重复步骤(2)；否则v1e1v2e2ei+1vi+1即为N的一条欧拉环游。

53、若N没有欧拉环游,此时最优环游通过的某些边将超过一次.例如图(a)中的xuywvzwyxuwvxzyx是最优环游,此时四条边ux,xy,yw和wv都被这环游通过二次.xyvuwz图(a)11222223564最优环游: xuywvzwyxuwvxzyx对于非Euler图，1973年Edmonds和Johnson给出下面算法: 设G是连通加权图，边权为m(e)。（1）求V0=v|vV(G),d(v)=1(mod2)。（2）对每对顶u，v V0 ，求d(u,v)（ d(u,v)是u与v的距离，可用Dijkstra算法求得）。（3）构作完全加权图K |V0| ，以V0为顶集，以d(u,v)为边uv的

54、权。（4）求M中权之和最小的完备对集M。（5）求M中边的端点之间的在G中的最短轨。（6）在（5）中求得的每条最短轨上每条边填加一条等权的所谓“倍边”（即共端点共权的边）。（7）在（6）中得的图G上求Euler回路即为中国邮递员问题的解用d(v)表示与顶v关联的边的条数，称d(v)为v的次数，容易证明例题 在图1所示的图上求中国邮递员问题的解。（1）V0=v1,v2,v3,v4 （2）d(v1,v2)=4 d(v1,v3)=5 d(v1,v4)=2 d(v2,v3)=3 d(v2,v4)=5 d(v3,v4)=3 （3）K |V0|如图2所示（4）K |V0|中的最小权对集为M=v1v4,v2v

55、3见图2中实线v1v4，v2v3。（5）M中的边之端点间G中的最短轨为 P(v1,v4)=v1u1v4, P(v2,v3)=v2u4v3（6）构作G如图3所示（7）求得G上的一条Euler回路C， C即为所求。（此C 不是唯一的Euler回路） C=v1u1v4u3u4v2v1u1u3v2u4u3u5v3u4u1v4u6u5u2u6u1v1u1u2u3u4u5u6v1v2v3v411111112222225334433255v1v2v3v4图1图2图3v1v2u4v3v4u1u6u5u2u3城镇道路扫雪模型求解方法一 运用“中国邮递员问题”原理求解此问题 我们的目的是要寻求一个有效的办法用两台

56、扫雪车清除威克米尔市内道路(不包括州高速公路)的积雪.这个问题的有效解法应该具有以下特点: 1. 扫完全部路面所花的时间尽量少; 2. 扫雪完毕后,两车应尽快回到出发点; 3. 两车工作时间大致相同. 如果扫雪车没有重复走某一条路,或者扫雪车重复走的路径和最小我们就可以认为扫雪所花的时间最少。为了使交通尽快畅通,通常应该把所花的时间少放在最重要的地位来考虑。必要时还要考虑首先清除威克米尔市内道路交通图中的主要干线道路上的积雪问题，这时需要解决确定哪些路线是主干线的问题。 (一) 模型的分析1. 扫雪过程中没有下雪，所有市内道路都有积雪需要清除；2. 两辆扫雪车性能相同，都能正常工作；3. 两辆

57、扫雪车司机驾驶技术相同，扫雪时车速相同；4. 在所有交叉路口，包括市内道路与高速公路的接口，扫雪 车可以不减速地拐弯；5. 两辆扫雪车出发的时间相同;6. 每条路面的积雪范围、厚度相同。(二) 模型的假设(三) 模型的建立1. 双行道问题假定每条道路均有两条方向相反的行车道.此时将地图中每个交叉路口(包括市内与高速公路的交叉口)看成点,每条市内道路看成边,它的长度看成该边对应的权,这样我们就得到了网络N=(V,E,W).由于每条公路均是双行道,这样的网络N是一个欧拉有向图,每点的入次和出次相同.利用弗莱里算法可以求得N的欧拉环游.如果只有一辆扫雪车，这就是“中国邮递员问题”。现在有两辆扫雪车,

58、为了使工作过程最优，两辆扫雪车应扫过几乎同样长的道路。为此，我们把网络N分为两个子网络N1和N2，使得N1和N2均连通且N1和N2两子网络的权应尽可能相等。 把网络N分成两个连通的子网络，分别算出两个子网络中所有边的总长度，由于N的总边长已知，在总长度较大的子网络中减去一些与另一子网络相连的边，添加到总长较小的子网络中.（参见下图）问题：把网络N分为两个子网络N1和N2,使得N1和N2均连通且N1和N2两子网络的权应尽可能相等。此问题的求解2. 单行道问题 近代喷气扫雪车已经问世，它靠喷射热气流来清除积雪，因此这种扫雪车在双行道一边行驶时，就可以很容易的清除整条路面上的积雪，无需再沿道路的另一

59、边重新行驶。 求这种情况下的最优解问题称为单行道问题。 对这类问题，与双行道问题一样,我们可以将它对应一个网络N，并将N分成两个子网络N1和N2，要求N1和N2两子网络的边总长度相等, 这样利用求解 “中国邮递员问题” 的算法可以分别求得N1和N2的欧拉环游，得到我们要求的近似解。 如果扫雪车在市内道路交叉路口或市内道路与高速公路交叉处可以掉头，即扫雪车到达城市边缘可以不经高速公路而重新进入市区，则可用上述方法求解。 如果忽略扫雪车在高速公路上的行车时间，则可同上述情况一样求解；否则，我们要将高速公路看成上述网络的若干条新边，然后用上述方法求解。城镇道路扫雪模型求解方法二 首先划分城市为南区与

60、北区（或东区与西区），使两区分别连通，且路的总长相等。具体操作时可把地图放大，用丝线沿街道曲线粘贴再撕下丝线，测其总长；把北城（或东城）的街道粘贴丝线，使所用丝线是全城所用之半，且使粘线各街道与未粘线各街道分别连通，设粘线者为G1，其余为G2，甲车在G1上，乙车在G2上；然后在G1与G2上分别执行Edmonds和Johnson解中国邮递员问题的算法。 如果街道要求右侧通行，则分别在G1与G2上执行Fleury算法，即可找到甲乙两车的扫雪回路，执行Fleury算法时，认为每条街对应等长共端的两条边。（参见下图所示）（1）粘贴丝线等分全城威克米尔市城区街道标识图（2）添加虚拟街道等分全城12345