792被浏览169,282分享邀请回答19725 条评论分享收藏感谢收起1314 条评论分享收藏感谢收起当前位置： >>
数学模型课件()
数 学 模 型么焕民哈尔滨师范大学数学科学学院日数学从诞生之日起，就与人类社会、生活、 文化、哲学、艺术、科技等密切相连，不仅成为 “科学之王”，而且还是美的使者。幻方是奇怪的迷宫！ 圆周率是无穷的歌谣！ 黄金分割是奇美的图画！ 分形是怪异的曲线！ 莫比乌斯圈是梦幻的摇滚！ 几何是神奇的彩笔！ 代数是美妙的遐思！第一章 认识数学模型提出三个简单的实际问题【问题一】 已知甲桶放10000个蓝色的玻璃球,乙桶中放有 10000个红色的玻璃球,任取甲桶中100个球放入乙桶中混合 后再任取乙桶中的100个球放入甲桶中,如此重复三次.问甲 桶中的红色球多还是乙桶中的蓝色球多？ 解:设甲桶中有x个红色球,乙桶中有y个蓝色球，由于两 个桶中的蓝色球总数为10000个，则有10000? x ? y ? 10000从而得到x? y【问题二】能否将一张纸对折100次?对折1次：2层= 21 对折2次：4层= 22 对折3次：8层= 23 …… 对折100次: 2100 计算结果为：5万亿亿千米！ 提示: 地球到太阳的距离不过1.5 亿千米！！！ 所以此问题的答案在理论上讲是可以的，但是实际上是 做不到的。类似的，在日常生活中有许许多多的实际问题， 有些好像与数学无关，但通过细致的观察分析与假设，都可 以应用数学方法简捷和完美的解决。此乃数学模型的魅力。设普通纸每张厚度为 0.05mm，因为 210==103 故
所以 2100层纸厚度＞ 0.05×1030mm =5×1022 km【问题三】神奇的数学是魔术师的障眼法3-1 洞从哪里来？将两条长度分别为 8+5 与 2+1+2 的直角边剪裁成图A 所示的四块几何图形，然后再重新拼接成图B，它仍是一个直 角三角形，其边长分别是（5+2+1+5）和（3+2）。 我们发现与图A相比，图B多出了一个洞，这个洞是从哪 里来的？．8． ．． ． ． ．． ． ． ．2152213212 55． ． ． ． ． ． ． ． ．．3 5 32121125图A图B 多出了一个洞！3-2面积怎么少了？如图，将图A中面积为13×13=169的正方形裁剪成四块几何图 形,然后重新拼接成图B，计算可知长方形的面积为8×21=168, 比原来的正方形少了一个单位的面积。． ．13．558．5 ．8 8． ．813．5．58．888．5 ．图A．．图B．13．图A的面积= 13×13=169图B的面积= 8×21=168出现“差错”的原 因以第二个问题为例，题中涉及到四个数据：5，8，13， 21，正是斐波那契数列中的四项，斐波那契数列的特征是 从第三项开始的每一项都是它的前两项的和： 1，1，2，3，5，8，13，21，34，58，?? 我们可以使用这个数列的其它任意相邻四项来试验这 个过程，发现无论选取哪四项，都可以得出关于斐波那契 数列的一个重要性质：这个数列任意一项的平方等于它前 后相邻两项之积加1或者减1。即：f2 n? f n?1 ? f n?1 ? 1得到以下重要结论：正方形的面积和长方形的面积不会相等，有时候正方形的 面积比长方形的面积多一个单位，有时候正方形的面积比长方 形的面积少一个单位，即f n2正方形的面积， f n?1 ? f n?1长方形的面积知道了这个事实后，我们就可以随心所欲的构造类似第二个问题的几何趣味问题了。如：用8，13，21，34来构造类似上述的问题，会得到同 样类似的神奇结果。美妙的花朵----广义斐波那契数列前面提及的斐波那契数列是以1,1两数开始的,广义的斐波 那契数列可以从任意两数开始.如用广义的斐波那契数列 2,2,4,6,10,16 ,?? 做上述试验,就会多得或丢失4个单位的面积. 如果用 a, b, c 表示广义斐波那契数列的相邻三项,以 x 表示 “得”或“失”的数字，则成立?a ? b ? c ? 2 ?b ? ac ? x问题思考：把正方形按上述方法剪成四块，是否会拼成一个与 它面积相等的长方形？此问题的求解：b 1? 5 令方程组中的 x 等于零，解之得到唯一的正解是 ? a 21? 5 其中 恰是著名的黄金分割比（常数）. 通常用 ?来表示， 2 它是一个无理数，其值是1.618033……；即，每项平方等于其相邻的前后两项之积的斐波那契数列是：1，?，? 2，?3，? 4， ?要证明它的确是斐波那契数列，只要证明它等价于数列1, ?, ? ? 1,2? ? 1,3? ? 1,?即可。（请自己证明这个结论并解释前面的第一个问题）知识链接：中世纪欧洲――数学历史上的黑暗时期；斐波那契――欧洲数 学走向复苏的号角公元5-11世纪, 是欧洲历史上的黑暗时期, 天主教会成为欧洲社会的绝对 势力,由于封建宗教的统治,使一般人笃信天国追求来世,从而淡漠世俗生活对自 然不感兴趣.教会宣扬天启真理并拥有解释这种真理的绝对权威, 导致了理性的 压抑.欧洲文明在整个中世纪处于凝滞状态. 由于罗马人偏重于实用而没有发展 抽象数学,这对罗马帝国崩溃后的欧洲数学也有一定的影响, 终使黑暗时代的欧洲在数学领域毫无成就.直到12世纪, 由于受翻译,传播阿拉伯著作和希腊著作的刺激, 欧洲数学才 开始出现复苏的迹象. 公元1100年左右,欧洲人通过贸易和旅游,同地中海地区 和近东的阿拉伯人以及东罗马帝国的拜占庭人发生了接触,十字军为掠夺土地而 东征, 使欧洲人进入了阿拉伯世界, 从此欧洲人从阿拉伯人和拜占庭人那里了解 到希腊以及东方古典学术.中世纪欧洲――数学历史上的黑暗时期；斐波那契――欧洲数 学走向复苏的号角欧洲黑暗时期过后，第一位有影响的数学家就是L.Fibonacci（），他早年就随其父在北非师从阿拉伯人学习算学，后来又游历地中海沿岸诸国，回到意大利后写成《算经》，亦称作《算盘书》。 这部很有名的著作主要是一些源自古代中国、印度和希腊的数学问题的汇集，内容涉及整数和分数算法、开方法、二次和三次方程和不定方程，特别是书中系统地介绍了印度-阿拉伯数码，对改变 欧洲数学的面貌产生了很大的影响.中世纪欧洲――数学历史上的黑暗时期；斐波那契――欧洲数 学走向复苏的号角在1228年的《算经》修订版载有著名的《兔子问题》： 某人养了一对兔子，假定这对兔子每月生一对小兔，而小兔出生 后两个月就能生育。问从这对兔子开始一年内能繁殖成多少对兔子。对这个问题的回答导致了著名的菲波那契数列的产生。因此《算经》可 以看作是欧洲数学在经历了漫长的黑夜之后走向复苏的号角。神奇的关系式：5 ?1 2 1 ? ? 1.? ? 1 ? 1 2 5 ?1 1? 1??1.1 什么是数学模型一、有关的几个概念1.原型：指人们在现实世界里关心,研究或从事生产,管 理的实际对象。 2.模型：为了某个特定的目的,将原型的某一部分信息简 缩,提炼而构造的原型的替代品。 3.原型与模型的关系：原型是模型的前提与基础，模型 是原型的提炼与升华。 原型有各个方面和各个层次的特征，而模型只要求反 映与某些目的有关的那些方面和层次。二、什么是数学模型所谓数学模型是指对某种事物系统的特征和数量关系，借助数学 语言而建立的符号系统。 广义上讲，数学模型是指凡是以响应的客观原型作为背景加以一 级抽象或多级抽象的数学概念、数学式子、数学理论等都叫数学模型； 狭义上讲，数学模型是指那些反映特定问题或特定事物的数学符 号系统。（我们所指的数学模型是指狭义上的数学模型） 数学模型不是原型的复制品，而是为了一定的目的对原型所作的 一种抽象模拟，它用数学算式、数学符号、程序、图表等刻画客观事 物的本质属性与内在关系，是对现实世界的抽象、简化而有本质的描 述，它源于现实，又高于现实。 数学模型能解释事物的各种形态，预测将来的形态；或者能为控 制某一事物的发展提供最优化策略，都是为了达到解决实际问题的目 的。三、建立数学模型的全过程现实对象的信息数学模型现实对象的解答模型的解答四、建立数学模型解决实际问题的思维方法不符合实际实际 问题简化、假设 抽象数学 问题有无现 成方法无有数学、数值求解检验发展新方法解释、设计、预测、控制符 合 实 际五、模型的分类1、按应用领域分：人口模型、交通模型、环境模型，城镇模型、 规划模型、生态模型、水资源模型等； 2、按建模的数学方法分：初等数学模型、几何模型、微分方程模型、差分方程模型、随机模型、图论模型、组合最优化模型、层次模型、最优控制模型和规划模型等； 3、按表现特征分：确定性模型与随机性模型、静态模型与动态模型、线性模型与非线性模型、离散模型与连续模型；4、按建模的目的分：描述模型、分析模型、预报模型、优化 模型、决策模型、控制模型等；5、按对模型的了解分：白箱模型、灰箱模型、黑箱模型等；6、按人们对原型的认识过程分：描述性模型和解释性模型。例：分类5的具体解释（1）白箱模型对系统相当了解，利用系统的机理方程建立起来的 数学模型，通常采用机理建模。（2）黑箱模型对系统并不了解，利用实验得到的输入输出数据来 构建系统的等价模型，通常采用统计建模。 （3）灰箱模型 介于白箱模型和黑箱模型之间的模型。例：分类6的具体解释（1）描述性数学模型采用归纳法，从特殊到一般，从分析具体事物归纳 出描述事物的数学模型的方法； （2）解释性数学模型 采用演绎法，从一般到特殊，从一般的公理系统出发，借助于数序推理的方法给出公理系统正确解释的一种数学模型方法。六、历史上成功的建立数学模型的例子说到数学模型的建立或数学建模，似乎是一个新东西、新 名词，其实是古已有之的。一个最典型也最成功的数学建模的 例子是行星运动规律的发现。开普勒根据他的老师第谷近30年 天文观测的大量数据，用了10年时间总结出行星运动的三个规 律，但当时还只是经验的规律，只有确认这些规律，找到它们 内在的根据，才能有效地加以运用。牛顿提出与距离平方成反 比的万有引力公式，利用运动三大定律证明了开普勒的结论， 严格推导出行星运动的三大定律，成功地解释并预测了行星运 动规律，也证明了他建立的数学模型的正确性。 这是数学建模取得光辉成功的一个著名的例子。构造模型示例一：九宫图口诀九宫图：出自西汉（公元前206-公元25）学者戴德编纂《大戴礼》 口诀一：九宫者，法以灵龟，二四为肩，六八为足，左三右七， 戴九履一，五居中央。 ----《数术记遗》南北朝（420-589）甄鸾口诀二：九子斜列，上下对易，左右相更，四维挺出。----南宋（）杨辉（台州府地方官，数学家和数学教育家）九子斜列 1 2 3 6 9 5 8 4 7上下对易 9 2 3 6 1 5 8 4 7左右相更 9 2 7 6 1 5 8 4 3四维挺出2 7 69 5 14 3 8 幻和=15知识链接： 河图洛书―古老而悠久的中华文化宝殿中的璀璨明珠河图洛书是我们祖先创造出来的两个简单的数字图，是中华文化 的总源头，对中国及世界文化的发展有着深刻的影响。长期以来，人 们为它的神话般的传说、高深的奥义、丰富的内容和简洁的形式万分 惊讶，对它与中国的思想文化、社会科学、自然科学的密切联系更是 迷惑不解。 河图洛书产生于四千五百多年以前，那时人类尚处于无文字时代 人类的认识水平还十分低，很难想象那时就有人能够制造出如此高深 莫测的图书。翻遍各种古典著作，根本找不到这位?创始人?。 《易经》是中华文明源泉之根源，《易经》之根源来自于被称为 天书的《河图》《洛书》这两幅上古之图。因相隔年限久远，使后人 对‘河洛’的传说与理解说法太多，难有公认定义，由此被人们称之 为 天书。 对河图洛书的起源，在我国的各种古籍中仅有龙马载河图和神龟 背洛书等两个传说。知识链接：河图洛书―古老而悠久的中华文化宝殿中的璀璨明珠一、龙马载河图相传远古时期的孟津河边，一天河水忽然大涨，波浪滔天，水 中有一巨兽，似龙非龙，似马非马，浪里飞腾。当时的伏羲黄帝与 众臣听到有人报告，立即去河边观看，只见河中洪涛巨浪，波浪中 一巨兽踏水如登平地，大体象马却身有鱼鳞，高八九尺，有两翼， 形体象骆驼，身上负有由花点构成的图案，黄帝命人走近河边，将 图案记录下来，刚刚记下，怪兽即没而不见。 伏羲皇帝认真研究了这副图发现它正是由十种花点组成，这十 种花点代表1-10这10个数，两种花点构成一组，布局在东西南北中 五个位Z上，每组花点所表示的数，其差均是5。这种和谐统一、 四方对称的特征，黄帝越研究越感到奇妙无比，后来他就依此画八 卦，建甲历，定时辰，治理国家。 由于此幅图是在孟津河中发现的，故称此图为河图。知识链接：河图洛书―古老而悠久的中华文化宝殿中的璀璨明珠二、神龟背洛图公元前23世纪，大禹与治水士兵正在在黄河支流洛水河边现察洛河水情，商议治理黄河大计，突然发现河中浮现出一个大乌龟，只见 它身形庞大，甲背平圆，行走水面，上下翻腾。近处仔细观看，他们 惊奇地发现甲上载有9种花点的图案，9种花点数正好是1～9个数，各 数的位Z排列也相当奇巧，纵横六线及两条对角线上三数之和都为15 既均衡对称，又深奥有趣，奇偶数交替变化，似有旋转运动之妙。 据《史记．夏本纪》记载，大禹治水以神龟背上的九宫为据，应用到测量、气象、地理与交通运输之中，从而治理黄河，大获成功， 受到黄河两岸人们的拥戴。由于神龟所背图是在黄河支流洛水中发现且图中内容如书一样深 奥，故人们称此为洛书，古称龟书。知识链接：河图洛书―古老而悠久的中华文化宝殿中的璀璨明珠传说在出于洛水的神龟甲壳上有此图象，结构是：载九履一，左三右七，二四为肩， 六八为足，以五居中。五方白圈皆阳数，四 隅黑点为阴数，前人指出洛书数字本太一下 九宫而来，以四十五数演星斗之象。九宫八 风图配合八风，八卦，中央一宫，即洛书的 中宫，乃周围八宫的核心。古人观测天象，认为北极星(太乙)之位恒居北方，可以作为中 心以定位的标准。九宫是据北斗斗柄所指，从天体中找出九个方位上最明亮的星为标志，便于配合斗柄以辨方定位，发现九星的方位 及数目，即洛书的方位和数目。知识链接：河图洛书―古老而悠久的中华文化宝殿中的璀璨明珠 神龟背洛图：1.2 椅子在不平坦地面上的稳定问题一、问题的提出这个问题来源于日常生活中许多人常遇到的极其普遍但可能 没有引起足够注意的现象，即任意一把放在不很平坦的地面上的 多于三条腿的椅子，通常是不稳定的，但只要将椅子适当地移动 位置，它便能放稳。 三点可以确定一个平面，因而一把多于三条腿的椅子无论怎 样放置，对于相对比较平坦的地面来讲，总可以保证有三条腿同 时着地，因而只需再使其余的椅腿也能完全着地即可。问题模 型 假 设椅子能在不平的地面上放稳吗？1. 椅子四条腿一样长，椅脚与地面接触处可视为一个点，四脚的 连线呈正方形； 2. 地面高度是连续变化的，沿任何方向都不会出现间断（没有像 台阶那样的情况），即地面可视为数学上的连续曲面；3. 对于椅脚的间距和椅腿的长度而言，地面是相对平坦的，使椅 子的任何位置至少有三只脚同时着地。模 型 构 成椅脚连线为正方形ABCD(如右图)。t ~椅子绕中心点O旋转角度 f(t)~A,C两脚与地面距离之和 g(t)~B,D两脚与地面距离之和 f(t), g(t) ? 0C‘ B‘ CB t OA‘A x D‘D模型构成由假设1，f 和 g都是连续函数，由假设3，B B‘ C O C‘ t A‘椅子在任何位置至少有三只脚同时着地： 对任意t，f(t)和g(t)中至少有一个为0。当t=0时, 不妨设g(t)=0, f(t)&0, 原题归结 为证明如下的数学命题：A xD‘已知f(t)和g(t)是t的连续函数,对任意t, f(t)?g(t)=0, 且 g(0)=0, f(0)&0。则存在t0，使f(t0)= g(t0)=0。D模型 求解? g ?0? ? 0 f ?0? ＞ 0 可知 g ? ? ＞0 ? ??2? ? f(t)-g(t),则h(0)&0和h( 2将椅子逆时针旋转 2 , 则对角线AC与BD的位置互换。?? ? f? ??0 ?2??令h(t)= ) &0，由f和g的连续性知h也 ? 是连续函数. 根据连续函数的基本性质, 必存在t0 (0&t0& ), 成立 2 h(t0)=0，即f(t0)= g(t0)。 最后，因为f(t) ?g(t)=0，所以f(t0)= g(t0)=0。本 节 点 评“椅子问题”的解决抓住了问题的本质，在合理的假设 下 (椅子中心不动，对角线看成坐标轴)，将椅子转动与坐标 轴旋转联系起来, 将椅腿与地面的距离用旋转角度t的函数 表示，由三点确定一平面得到f(t)?g(t)=0，再根据闭区 间上连续函数介值定理，使这个问题解决得巧妙而又简单。 满足介值定理条件的关键是：利用了对称性。1.3 商人们怎样安全过河问题随从们密约, 在河的任一岸,河 流一旦随从的人数比商人多就杀人越货。有利条件：乘船渡河的方案由商人决 定.商人们怎样才能安全过河?小船(至多2人)? ? ? 3名商人问题分析-----多步决策过程? ? ? 3名随从决策: 每一步(此岸到彼岸或彼岸到此岸)船上的人员。 要求: 在安全的前提下(两岸的随从数不比商人多),经有限步使 全体人员过河。模型构成xk~第k次渡河前此岸的商人数 xk, yk=0,1,2,3; yk~第k次渡河前此岸的随从数 k=1,2,?,n sk=(xk , yk)~过程的状态 S--允许状态集合 S={(x , y)? x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2} uk~第k次渡船上的商人数 uk, vk=0,1,2;vk~第k次渡船上的随从数 k=1,2,?,n D={(u , v)? u+v=1, 2} ~允许决策集合 dk=(uk , vk)~决策状态转移律： sk+1=sk +(-1)k dk 多步决策问题 求dk?D(k=1,2, ?,n), 使sk?S按状态转 移律由s1=(3,3)到达sn+1=(0,0).模型求解S={(x , y)? x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2} D={(u , v)? u+v=1, 2} 状态s=(x,y) ，16个格点;允许状态S: 10个点 允许决策D ~ 移动1或2格; 3 y 图解法s1d1k奇,左下移; k偶,右上移。d1, ?,d11 : 安全渡河方案21评注和思考 规格化方法, 易于推广。d110sn+1123x思考：考虑4名商人各带一随从的情况。1.4 数学模型特点与建模能力培养数学模型有以下特点：1、模型的逼真性和可行性 越逼真的模型就越复杂，应用起来费用 越高，常与取得的效益不成正比。所以建模时需在逼真性与可行性 折衷，在费用与效益之间选择。 2、模型的渐进性 稍微复杂的数学模型通常不是一次成功的,是反复迭代，越来越完善。3、模型的强建性 已建好模型,当观测数据(信息)有微小改变时, 模型结构和参数只有微小变化,一般也应导致模型求解的结果发生 微小的变化。1.4 数学模型特点与建模能力培养4、模型的可转移性 模型是现实对象抽象化产物，它可能与其 它领域其它事物有共性。常常好多领域不同事物却共有几乎相同 数学模型。 5、模型的非预制性 大千世界变化莫测,各种事物千姿百态， 不能要求把各种模型做成预制品供我们建模时使用,我们遇到的 要解决的问题往往事先没有答案，这一特性往往给我们惊喜.即 再建立新的模型的过程中有时会伴随着新的数学方法,新数学概 念产生。 6、模型的条理性 从建模角度考虑问题,使人对现实对象分析 更全面深入,更具有条理性。有时即使建模失败，往往对解决研 究问题有利的。1.4 数学模型特点与建模能力培养7、模型的技艺性 建模目前与其说使一门技术,不如说是一种 艺术,是技艺很强的技巧.经验,想象力,洞察力,判断力以及直 觉灵感起的作用往往比数学知识更大.人的知识是有限的,想象 力是无限的。 8、模型的局限性 建模过程有把现实对象简 化、近似、假设 过程，当模型应用到实际，那些被忽略简化因素必须考虑。于 是结论往往是相对的、近似的。人的认识能力受科学技术、数 学本身发展水平限制，还有不少实际问题没有建立出实用(有 价值)的数学模型，如中医诊断,人与电脑对局下围棋等。数学建模的方法与步骤?一、对数学模型的要求1. 准确：一个数学模型要有足够的精确度，能较准确的反 映实际问题本质的性质和关系。 2. 简练：数学模型要尽可能的简单，便于处理。模型必须 作简化，不作简化，模型十分复杂难以求解甚至难以建立 模型，即非实际问题本质的关系要省略，以免模型太复杂。 3. 正确：构造数学模型的理论要正确，依据要充分，推理 要合法。要充分利用科学规律来建立有关的模型。数学建模的方法与步骤二、数学建模的方法1. 机理分析法:根据人们对现实对象的了解和已有的知识、经 验等,分析研究对象中各变量之间的因果关系,找出反映其内部 机理的规律. 2. 测试分析法:当我们对研究对象的机理不清楚的时候,可以把 研究对象视为一个?黑箱?系统。对系统的输入输出进行观测， 并以这些实测数据为基础进行统计分析来建立模型。 3.综合分析法:对于某些实际问题，将上述两种建模方法结合 起来使用。例如用机理分析法确定模型结构，再用测试分析法 确定其中的参数。数学建模的方法与步骤三、数学建模的一般步骤 1、形成问题 2、假设与简化 3、模型构成与求解 4、模型的检验与评价 5、模型的改进 还可以归纳为: 八步建模法(参考教材)四、八步建模法1. 提出问题 2. 量的分析 4. 模型建立 6. 模型分析 8. 模型应用3. 模型假设5. 模型求解 7. 模型检验提高建模能力具体如何做?? 学好数学各门专业课，基础课 ? 大量阅读思考别人做过的模型? 亲自动手实践，认真做若干个实际题目? 善于用数学语言表述现实世界大量需要解决的问题 ? 有较坚实的理论基础和广博专业知识? 有丰富的想象力和敏锐的洞察力第二章 初等模型§2.1 双层玻璃的功效【问题的提出】 位于北方寒冷地区的建筑物里，通常把单层玻璃 窗改建成中间制造成真空的双层玻璃窗，这样可以有 效地阻止热量向室外的扩散带来的损失，问题是当建 筑物室内外的热传递处于一个热力学平衡状态时，双 层玻璃窗究竟能比单层玻璃窗阻止多少热量的损失？ 两层玻璃窗之间的距离控制在多少为好？为什么双层 玻璃的功效大于同样多材料制成的单层玻璃？【模型的假设】（1）热量的传播过程只有传导没有对流。即窗户的密封性能很 好，两层玻璃之间的空气是不流动的。 （2）室内温度和室外温度保持不变，热传导过程已处于稳定状 态.即沿热传导方向,单位时间内通过单位面积的热量是常数。 （3）玻璃材料均匀，热传导系数是常数。 （如图所示）【符号说明】T1 T2 d l Ta Tb k Q――――室内温度 ――――室外温度 ――――单层玻璃厚度――――两层玻璃之间的空气厚度――――内层玻璃的外侧温度 ――――外层玻璃的内侧温度 ――――热传导系数 ――――热量损失【模型的建立与求解】运用物理学中的热传导方程模型遵从的物理定律:厚度为d的均匀 介质，两侧温度差为Δ T，则单位时间由温度高的一侧向温度低的一 侧通过单位面积的热量Q ，与Δ T成正比，与d 成反比，即?T Q?k d1.双层玻璃的热量流失k为热传导系数(1)记双层窗内窗玻璃的外侧温度为 Ta ,外层玻璃的内侧温度为 Tb 玻璃的热传导系数为 k1 ,空气的热传导系数为 k2 ,由(1)式单位时间 单位面积的热量传导（热量流失）模型方程为T1 ? Ta T ?T T ?T ? k 2 a b ? k1 b 2 d l d Tb ? T2 T1 ? Ta 由 Q ? k1 及 Q ? k1 可得 d d Q ? k1(2)Ta ? Tb Q?d , 将(2)式中的 再代入 Q ? k 2 Ta ? Tb ? ?T1 ? T2 ? ? 2 l k1Ta , Tb 消去, 变形可得 k1 ?T1 ? T2 ? k1 l Q? , s?h , h? d ?s ? 2? k2 d2.单层玻璃的热量流失(3)对于厚度为2d的单层玻璃窗户,容易写出其热量流失为T1 ? T2 Q? ? k1 2d3.单层玻璃窗和双层玻璃窗热量流失比较 由 (3)、(4) 得(4)Q 2 ? Q? s ? 2(5)显然 Q? Q?已知不流通、干燥空气的热传导系数 k2 常用玻璃的热传导系数 k1 于是? 4 ?10?3 ? 8 ?10?3 ?J / cm? s ? 度?? 2.5 ?10?4 ?J / cm? s ? 度?k1 ? 16 ～ 32 k2 k1 ? 16 k2在分析双层玻璃窗比单层玻璃窗可减少多少热量损失时，我们做最 保守的估计，即取Q 1 l 由（3），（5）式可得： ? ,h? Q? 8h ? 1 d【模型的讨论】Q/Q’ 0.06 0.03 0.02 O 2?比值Q/Q’反映了双层玻璃窗在减少热量损 失上的功效，它只与h=l/d有关.下图给出 了 Q/Q’～h的曲线?4通常取h=4,则Q/Q’≈3%.?6 h这说明: 从理论上讲双层玻璃比用同样多材料制成的单层玻璃要节 约热量约97%！? 若将双层玻璃该为三层玻璃，结果会怎样？ ? 若单层玻璃的厚度也是d，结果又会如何？2.2 选购手机SIM卡模型【问题的提出】某公司新推出A、B两种新型手机SIM卡，资费情况如下：若要在A、B两种SIM卡中二选一，问你将选择哪一种？A卡月租费少，B卡免费通话时间长，直观的感觉是：若每 月通话业务多时用B卡好，业务少则用A卡，那么这个划分 的标准是多少？即此“临界值”应当是多少？模型的假设与建立设通话时间为t分钟，消费的话费为f(t)，则对于A、B两种SIM 卡来说，分别有： ?98, 0 ? t ? 60 ? A : f ?t ? ? ? ?98 ? 0.38 ? ? t ? 60 ? , t ? 60 ??168, 0 ? t ? 500 ? B : f ?t ? ? ? ?168 ? 0.38 ? ? t ? 500 ? , t ? 500 ?比较A、B的表达式，讨论究竟通话 时间超过多少分钟时B比A合算： （如图所示）?结 论通过上图直观的看出，Q点就是这个划分的标准是多少？ 也即起“临界值”，应当求出Q的坐标。 具体求法为： 令 0.38(t-60)+98=168，求得 t=244.21。 上述结果说明: 当每月使用手机时间不超过244分钟（约4小时）时,应选用A卡否则应选用B卡。2.3 高跟鞋问题与黄金分割中世纪德国数学家、天文学家开普勒曾经指出：?在几何学 中有两件瑰宝：一是毕达哥拉斯定理，另一个是黄金分割率?.趣味实用的高跟鞋问题模型，是“黄金分割”方法的具体应用。公元前600年至公元600年间，活动与在希腊半岛、意大利半岛、马 其顿与色雷斯地区、爱琴海区域、小亚西亚以及非洲北部的数学家们创 造的希腊数学，是数学史上辉煌的一页，其中生于靠近小亚西亚西部海 岸萨摹斯岛的希腊论证数学的祖师之一毕达哥拉斯（约公元前580～前 500），曾在今意大利东南沿海的克洛托内建立了一个秘密会社，即今 天所称的毕达哥拉斯学派，该学派的一个著名成就是正多面体作图问 题，其中就包括正五边形的作图与“黄金分割”问题。如右图所示，正五边形ABCDE。存在下面的重要结论：每条对角线都被交点分成两条不 相等的线段，使该对角线的整体与较 长部分之比等于较长部分与较短部分 之比， 这就是所谓的“黄金分割”。 经验表明：当人的下肢部分长与身高总长度的比为0.618 时是最美的。 如果某人的下肢部分长与身高总长度的比与0.618相差较 大，则可以通过穿适当高度的高跟鞋来调节，从而达到美的标 准。问题的求解：设某人身高为 h M，下肢长为 h1 M，选择的高跟鞋的鞋 跟高度为M，则由已知条件可得: x ? h1 ? 0.618 x?h 0.618h ? h1 x? 不难解得 即当高跟鞋的鞋跟高度是人身 0.382 体下肢部分的长与身高总长度的比恰为0.618是最美的。 例如：某女身高168厘米，下肢长102厘米，则高跟鞋的鞋跟 高 度大约是4.7748厘米。若身高153厘米,下肢长92厘米，则高 跟 鞋的鞋跟高度大约是6.6厘米.黄金分割的应用1、人体结构比例中的黄金分割：（1）正常身高的人的人体肚脐上下的部分之比为0.618:1 或接近这个比。 （2）上肢的黄金点在肘关节。 （3）肚脐以下部分的黄金点在膝盖，肚脐以上部分的黄金 点在咽喉。黄金分割的应用2、有经验的优秀舞台报幕员一般常常站在舞台的0.618 处，给人优雅、和谐的感觉。 3、如果是一根琴弦，则在琴弦的0.618处弹奏时，可以 获得最悦耳的声音。4、埃及基沙的第一座金字塔，高146米，与底边长230米 之比为0.637，所以该金字塔看上去气势磅礴，雄伟壮丽5、世界最高建筑，多伦多电视塔的楼阁和法国埃菲尔铁 塔的平台，都落座在整个塔身高度的黄金分割处，使得 这些建筑物有龙盘虎踞之势。相关的信息（1）1680年意大利―――法国学者卡西尼给出了重要的 关系式：（2）1730年法国棣莫弗给出通项公式：相关的信息（3）19世纪另一法国数学家比内证明了此表达式。现又 称之为比内公式。 那么该数列与黄金分割有何关系呢？事实上：（4）19世纪初另一位法国数学家比内首先证明这一表 达式，现在称为之为比内公式。1963年美国还创刊《斐 波那契季刊》来专门研究斐波那契数列。2.4 哥尼斯堡七桥问题一、问题的提出相传在十八世纪德国的哥尼斯堡城市中，有一条美丽的 布勒格尔河，河中心有两座岛屿A，B，南北两岸是繁华的商 业区，在河的两岸与两座小岛之间修建了七座桥（图），哥 尼斯堡的市民们热衷一个有趣的游戏：能否从四块陆地的某一处出发，通过每座桥恰好一次，再回到出发地点？二、图论方法在数学模型中的运用现实世界中许多现象都体现着事物与事物之间的某 种联系，如球队之间的比赛，两座城市之间的，在数学 中通常把中的城市、球队等抽象成点，而把铁路、公路 线或进行过比赛用连接两个点的直线表示，这就形成了 所谓的图形。 图论是有着完整体系与内容的独立的数学分支，运 用图论原理解决现实生活中的实际问题早已被证明是行 之有效的方法。同时，图论方法也是建立离散模型的重 要方法。三 相关的图论知识定义1 一个图是一个有序二元组G＝{V(G),E(G)},其中V(G)＝{Vi}为顶 点集，E(G)＝{ek}为边集，V＝V(G)中的元素Vi称为顶点,E＝E(G)中的 元素ek叫做边。当V、E为有限集合时，G称为有限图，否则G称为无限图。 定义2 称G＝{V(G),E(G),?G }为一个有向图，其中V（G）≠Φ 是顶点集 合,V（G）的元素称为顶点，E(G)是边的集合,E(G)的元素称为 边, V(G)∩E(G)＝Φ ; ?G :E(G)→V(G)×V(G)称为关联函数， 当?G e ? uv ,称边e与顶点相关联,又称顶点u与v相邻,u是e的尾,v是e 的头.??定义3 若G的每条边头尾不分，即有 ?G?e? ? uv ? vu,则称G为无向图。四 哥尼斯堡七桥问题的求解1736年,29岁的欧拉（Euler）发表了图论的首篇论文,严 格证明了七桥问题无解.欧拉把A岛、B岛、南岸、北岸等四块 陆地抽象成四个点A,B,C,D,连接两块陆地的桥为边(用直线段 或曲线弧表示),便形成了以下数学中抽象的图。?CA ?B ?? D不难看出，该图是一个无向图, 可以看成是七桥问题的数 学模型，因此七桥问题可以用图论的知识阐述如下： 从此图中某个顶点出发，遍历每条边恰好一次，最 后能否还回到原来的顶点处（出发点）？ 定义1 如果与某个顶点相关联的边的条数为偶数，则称 这个顶点为偶点。 定义2 如果与某个顶点相关联的边的条数为奇数，则称 这个顶点为奇点。 显然图中A、B、C、D四个顶点均为奇点（与任何一 个点相关联的边的条数非3即5），因此无论从哪个顶点 出发，必然是先?去?后?返?，且最后必须以?去? 结束才能保证每条边恰好遍历一次，但是遗憾的是，这 是无法做到的,由此证明了七桥问题无解。2.5 万有引力定律的发现一 问题的提出万有引力定律的发现是伟大的物理学家,数学家牛顿（）在 力学上的重大贡献之一,牛顿在研究力学的过程中建立了微积分理论,又成 功地在开普勒行星运动三定律的基础上运用微积分理论推导了万有引力定 律, 这一创造性成就可以看作是历史上最著名的数学模型之一.二 历史背景15世纪下半叶开始,欧洲商品经济的繁荣促进了航海业的发展.当时远 洋航船的方位全靠星球的位Z来确定, 人们对天文观测数据的精度要求也 越来越高.在这种强大的社会需要推动下,许多科学家投入到了天文观测与 研究之中.在获得的大量实际观测数据面前,一直处于天文学统治地位的? 地心说?开始动摇了.波兰天文学家哥白尼()在天文观测的基 础 上,冲破宗教统治和?地心说?的束缚,提出了?日心说?,这是天文学乃 至整 个科学的一大革命.但是由于当时历史条件和科学水平的限制,哥白尼的理 论还有不少缺陷,例如:他认为行星围绕太阳的运动轨迹是圆形等等.德国天文学家第古?布拉赫观测行星运动,积累了20多年的资料,而作为他 的助手,开普勒(,德国天文学家,数学家)运用数学工具分析研究这 些资料，发现哥白尼的理论与观测结果并不一致. 例如: 火星的实际位置与按照哥白尼理论计算出的位置相差8弧分。在深入分析 的基础上于1609年归纳出著名的开普勒行星运动三定律, 即： 开普勒第一定律：行星围绕太阳以椭圆轨道运动，太阳位于轨道的一个焦点.开普勒第二定律：太阳到行星的半径向量在相等时间内扫过相等的面积.开普勒第三定律：行星运行周期的平方与其椭圆运行轨道长半轴的三次方成正比.在开普勒等人研究工作的基础上,17,18世纪许多科学家致力于行星沿椭圆 轨道运行时受力状况的研究.从开普勒定律可以看出, 行星运行速度是变化的,而 在当时尚没有计算变速运动的动力学方法. 英国物理学家胡克() 和荷兰物理学家惠更斯()等人虽然都取得了一些成果,但是综未得 到有关引力的定律.牛顿认为一切运动都有其力学原因,行星运动也 不例外,行星运动一定也受力的作用.这力来自何方? 开普勒三定律揭示了行星的运动规律,是一个什么样 的力使行星的运动表现出这种运动规律?这便导出了 万有引力的数学模型.为了寻找行星运动周期与轨道尺寸的关系,牛顿 将当时已发现的六大行星运行周期和其运行椭圆轨 道的长半轴列成以下表格，并总结出第三, 四列周 期T的平方与长半轴A的三次方值几乎相等。万有引力定律的验证行星 水星 金星 地球 火星 木星 土星 周期 T 0.241 0.615 1.000 1.881 11.862 29.457 长半轴 a 0.387 0.723 1.000 1.524 5.203 9.535T20.2 1.000 3. 867.715a30.9 1.000 3.5 867.978三 模型假设开普勒三定律和牛顿第二定律是导出万有引力定律的基 础,所以需要将它们作为这个模型的基本假设. 根据加速度的定义,它是位置函 数的二阶导数, 也是速度函数的一 阶导数.为方便起见, 采用极坐标 系(r, ? ),向径r表示行星的位置. 取太阳(椭圆的一个焦点)为原点, 则行星位置为r,如图所示:u?rur??行星? O(太阳) ?图:极坐标系中的行星轨道这样上述基本假设的数学形式为:1. 根据开普勒第一定律, 对某颗确定的行星, 其运动轨道为一个焦点在 太阳位置的椭圆, 其运行的轨迹极坐标方程为p r? 1 ? e cos ?b2 p? ab2 ? a 2 1 ? e2??(1)式中a为椭圆长半轴,b为短半轴,e为离心率.1 2 r ?? ? A 2. 单位时间内向径r扫过的面积是常数A,即 2 式中 ? ?表示 ? 对时间 t 的导数;3. 行星运行周期T满足(2)T 2 ? ?a 3其中? 是绝对常数(即与任何一颗行星都无关)4. 行星运行时受的作用力 f 等于行星加速度r’’和质量m的乘积, 即f ? mr??四 模型建立首先, 基向量选为?u r ? cos ?i ? sin ?j ? ?u? ? ? sin ?i ? cos ?j如图所示, r可以表示为r=rur因为(1)?u? ? ? sin ? ?? ?i ? cos? ?? ?j ? ? ? ? u? r ? ? ?u? ? ? cos? ?? ?i ? sin ? ?? ?j ? ?? ? ? u r(2)所以u ?r? ? r ?u r ? ru? ? r ? ? u r ? r? ? ? r ? r?? ? r ?? ? r? ? 2 u r ? ?r? ?? ? 2r ?? ??u? ???(3)由假设(2),可得 ? ? ?2A ? 4 Ar ? , ? ?? ? r2 r3将其代入(3)式右端第二项, 可知 r? ?? ? 2r ?? ? ? 0 从而(3)式变为r?? ? r?? ? r? ?2 ur由假设(1)并利用 ? ? ???(4)2A , 可得 2 r 2 Ae 4 A2 e 4 A2 ? p ? r ? r? ? sin ? , r ?? ? cos? ? 2 p pr pr3 2A ? ? 2 代入(4)式, 可得 将 (5)式及 ? r ? 4 A2 (6) r?? ? ur 2 pr(5)将(6)式(并考虑到 r? ru r)代入假设(4)中,有(7)4 A2 m r f ?? r0 , r0 ? 2 pr r这里r0是单位向径. (7)式表明, 行星运行时太阳对其的作用力f的方向与向径方 向r0相反, 即f在太阳----行星的连线方向, 指向太阳; f的大小与太阳----行星间 的距离的平方成反比. 为了完成万有引力定律的推导,只需进一步证明(7)式中的 (显然A和p不是绝对常数).A2 p是绝对常数因为A是单位时间内向径扫过的面积, 行星(无论哪一个行星)运行一个周期 T, 向径扫过的面积恰是以 a, b 为长, 短半轴的椭圆面积, 所以TA ? ?ab(8)b2 , b2 ? a 2 1 ? e2 由假设(1)中的 p ? a?? 和假设(3)中的 TA ? ?abA2 ? 2 ??和?均为绝对常数?。将上式代入(7)中，有 ? 容易算出 p ?? 4? 2 m f ?? r0 2 ?r平方r2成反比以外, 余下的因子 我们熟知的形式(9)这表明, 太阳对行星的作用力f的大小除了与行星质量m成正比,与相互距离的4? 2f ? ?k4? 2Mm r0 相比较, 应该有 2 r?就只与太阳本身有关了. 将这个结果与?? kM ?k为万有引力常量， 为太阳的质量? M2.6 细菌的繁殖一 问题的提出已知某时刻某种细菌的数量,预测在任意时刻t这种细 菌的数量. 建立细菌繁殖的数学模型.二 量的分析由实验可知, 某种细菌繁殖的速度V在培养基充足等 条件满足时, 与当时已有的数量A0成正比. 即V=kA0(k&0为比例常数)三 模型的假设假设某种细菌的个数按照指数方式增长, 如下表所示 天数5 10细菌个数936 2190求:开始时细菌的个数可能是多少? 若继续以现在的速度增 长下去, 假定细菌无死亡, 那么60天后细菌的个数大概是多 少?四 模型的求解(1) 建立数学模型为了计算出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 ;……; 依此类推, 到最后一段时间末细菌的数量为t? ? A0 ?1 ? k ? n? ?n由此可知, 当时间间隔分得越细(即n越大)时, 这个值 越接近精确值, 如果对时间间隔无限细分(即n ∞), 则可 求得其精确值. 所以, 经过时间t后细菌的总数是:t? ? ? kt ? lim?1 ? k ? ? ? A0 lim?1 ? ? n ?? n ?? n? n? ? ?? kt 1 ? ? 令 ? , n ?? , x ?? ? ? n x ?nn??? 1 ? A0 lim ??1 ? ? x ?? ?? x ? ?x ktx? ? ? ?kt? ? 1? ? ? A0 ?lim?1 ? ? ? ? A0 e kt ? x ??? x ? ? ? ? y ? A0ekt 设细菌总数为y, 即模型为(2)细菌繁殖服从生长函数y ? A0ekt由题目所个数据得?936 ? A0 e5 k ? ? ?2190? A0 e10 k ?解此方程组,得: A0 ? 400, k ? 0.17 即: 开始时细菌个数为400个,按此速度增长下去,则 60天后细菌个数为y?60? ? 400e60?0.17 ? ?个?第三章 线性规划模型如何来分配有限的资源, 从而达到人们期望目标的数学模 型, 又称为分配模型. 它在运筹学中处于中心地位. 最优分配 问题, 一般可以归结为数学规划问题, 其中最简单,最常用的一 类模型就是线性规划模型. 线性规划(Linear Programming,简记为LP)是数学规划 中提出较早, 在理论和算法上也比较成熟的一个分支. 而数学 规划则是运筹学的一个重要分支,它起源于工业生产组织管理 的决策问题, 广泛应用于最优化设计,工农业生产,国防建设,交 通运输, 决策管理与规划等领域. LP问题不仅在实际中有广泛应用,而且运筹学的其他分支 里的许多问题也可以化归为线性规划问题来处理.运筹学经过半个多世纪的发展, 现在已经形成了 一个相当庞大的学科, 其内容相当丰富,主要包括:?线性规划 (Linear Programming) ? (Nonlinear Programming) ?非线性规划 ?整数规划 (Integer Programming) ? ?多目标规划 (Multiobjective Programming) ?动态规划 (Dynamic Programming) ? ? 运筹学?对策论 (Games Theory) ?决策论 (Decision Theory) ? ?存储论 (Inventory Theory) ? (Queuing Theory) ?排队论 ?图论 (Graph Theory) ? ?预测论 (Forecast Theory) ?第一节 线性规划(LP)问题3.1 几个实例【例1】生产安排问题某工厂利用三台设备，生产三种 不同的产品。各种产品每生产一件在 各台设备上所需要的加工时间(分钟) 各台设备每天的生产能力(每天的工 作时间)以及每件产品的单位利润如 下表。 问怎样安排生产才能使每天获得 的利润最大？假如每天生产B1，B2，B3三种产品数量分别为 x1,x2,x3件，每天的利润为每天的总利润最大是我们追求的目标,所以称 S ? f ?x1 , x2 , x3 ? 为目标函数, 而变量 x1 , x2 , x3 的值是我们需要确定的, 故称 之为决策变量.由于每台设备可提供的可以使用的资源是有S ? 2x1 ? x2 ? 1.5x3 ? f ?x1 , x2 , x3 ?(3.1.1)限的,不能超过它的最大生产能力，所以变量应满足条件：?2 x1 ? x2 ? x3 ? 420 ? ? 2 x3 ? 450 ?3 x1 ?2 x ? x ? 2 x ? 430 3 ? 1 2(3.1.2)再考虑到每种产品的产品都不可能是负值,即xj≥0,(j=1,2,3)综上所述，这个生产安排问题可归结为： 求变量 x j ? j ? 1,2,3? 满足以下约束条件?2 x1 ? x 2 ? x3 ? 420 ?3x ? 2 x ? 450 ? 1 3 ? ?2 x1 ? x 2 ? 2 x3 ? 430 ? x j ? 0? j ? 1,2,3? ?(3.1.3)使目标函数 S ? 2x1 ? x2 ? 1.5x3 的值最大。上述问题的数学模型简记为max S ? 2 x1 ? x2 ? 1.5 x3 ?2 x1 ? x2 ? x3 ? 420 ?3 x ? 2 x ? 450 ? 1 3 (3.1.4) s.t.? ?2 x1 ? x2 ? 2 x3 ? 430 ? x j ? 0? j ? 1,2,3? ? 其中max是maximize的缩写,中文意思是”求…的最大 值”,s.t.是subjuct to的缩写, 中文意思是”受约束于”或” 约束条件”. 由于在问题(3.1.4)中, 目标函数 S=f(x1,x2,x3) 是变量 x1,x2,x3的线性函数, 约束条件是x1,x2,x3的线性不等式,所以 我们把问题(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, 则 n 目标函数为Z ? ?cj xjj ?1(3.1.5)一般的拟订生产计划问题因而拟订一个最优的生产计划问题可以归结为以下的LP问题:max Z ? ? c j x jj ?1n?n ?? aij x j ? bi , i ? 1,2,?, m s.t.? j ?1 ? x ? 0, j ? 1,2,?, n ? j(3.1.6)【例2】运输问题运输问题是线性规划模型中最早被研究的 一类问题, 早在1939年,苏联数学家?.B.康托洛维奇写了《生产组织与计划中的数学方法》 一书, 在该书中就提出了这一类问题的数学模 型和求解方法.【例2】运输问题设有两个砖厂A1,A2,其产量别为23万块与27万块。它们 生产的砖供应三个工地B1,B2,B3,其需要量分别为17万块,18 万块和15万块。从各个生产地点到各个工地的运价如教材中P3-表1.2. 问应如何调运，才能总运费最省？求解设 xij表示由砖厂 Ai 运往工地 B j 砖的数量（单位:万块)?i ? 1, 2; j ? 1, 2,3? 例如x13 表示由砖厂 A1 运往工地 B3 砖的数量等.由题意 A1 , A2 运往三工地B1 , B2 , B3 的总数分别是23、27,得：(3.1.7)由于三工地 B1 , B2 , B3 需求量分别是17、18、15得： (3.1.8) 因此，调运必须满足下列约束条件：(3.1.9)满足这个约束条件的调运方案很多，我们希望在这 些方案中找到一个运费最少的方案，即求一组变量的值， 使它满足约束条件(3.1.10)并使以下目标函数的值最小（即总运费最少）S ? 50x11 ? 60x12 ? 70x13 ? 60x21 ? 110x22 ? 160x23上述问题的数学模型简记为min S ? 50x11 ? 60x12 ? 70x13 ? 60x21 ? 110x22 ? 160x23 ? x11 ? x12 ? x13 ? 23 ? x ? x ? x ? 27 ? 21 22 23 ? x11 ? x21 ? 17 ? s.t.? ? x12 ? x22 ? 18 ? x13 ? x23 ? 15 ? ? xij ? 0, i ? 1,2; j ? 1,2,3 ?运输问题的一般形式例: 假设某种物质有m个产地, 有n个销地. 第i个产地 的产量为ai,i=1,2,…,m;第j个销地的需要量为 bj,j=1,2,…,n.其中? a ? ?bi ?1 i j ?1mnj(3.1.11)由产地i到销地j的距离已知为dij.问应如何分配该种物质,使 解: 用xij表示产地i供给销地j的物质数量, 设s为运输的总 既能满足各地的需要, 又使所花费的运输总吨公里数最少?吨 公里数, 则上述问题的数学模型为运输问题的一般形式min s ? ?? dij xiji ?1 j ?1 m n?m ? ?? xij ? b j , j ? 1,2, ? , n?满足各销地的需要量 ? i ?1 ?n s.t.?? xij ? ai , i ? 1,2, ? , m?各产地的运出量不超过 产量? ? j ?1 ? x ? 0, i ? 1,2, ? , j ? 1,2, ? , n ? ij ?【例3】食谱问题一饲养场饲养供实验用的动物, 已知动物生长对饲料 中的三种营养成份--蛋白质, 矿物质和维生素特别敏感. 每个动物每天至少需要蛋白质70g, 矿物质3g, 维生素 10mg. 该饲养场现有五种饲料, 每种饲料10kg的成本如下:单位:元饲料 成本A1 2A2 7A3 4A4 3A5 5每一千克饲料中所含的营养成分如下表:饲料 A1 A2 A3 A4 蛋白质/g 0.30 2.00 1.00 0.60 矿物质/g 0.10 0.05 0.02 0.20 维生素/mg 0.05 0.10 0.02 0.20A51.800.050.08我们希望确定既能满足动物需求, 又使总成本为最低的 饲料配方. 试建立相应的数学模型.解: 设动物每天食用的混合饲料中所含的第j种饲料Aj 的数量为xj(kg), 混合饲料的总成本为y, 则上述问题的数学模型为1 min y ? ?2 x1 ? 7 x2 ? 4 x3 ? 3 x4 ? 5 x5 ? 10 ?0.30x1 ? 2 x2 ? x3 ? 0.6 x4 ? 1.8 x5 ? 70 ?0.1x ? 0.05x ? 0.02x ? 0.2 x ? 0.05x ? 3 ? 1 2 3 4 5 s.t.? ?0.05x1 ? 0.1x2 ? 0.02x3 ? 0.2 x4 ? 0.08x5 ? 10 ? x j ? 0, j ? 1,2, ? ,5 ?一般的食谱问题可叙述如下:假定有n种食品, 每种食品中含有m种营养成分. 用aij 表示一个单位的第j种食品中含有第i种营养的数量, 用bi 表示每人每天对第i种营养的最低需要量, cj表示第j种食 品的单价, Xj表示所用的第j种食品的数量. 问应怎样选配 食品,才能保证在满足m种营养成分的条件下, 使食品的总 成本y最低? n min y ? ? c j x j (3.1.12)j ?1? n ?? aij x j ? bi , i ? 1,2, ?, m s.t.? j ?1 ? x ? 0, j ? 1,2, ?, n ? j(3.1.13)【例4】下料问题某工厂有一批长度为300cm的钢管(数量充分多),要把它 们截成长度为45cm、80cm和95cm的管料,并要求其根数成 的比按5:3:2来配套生产某种零件，问采用怎样的方案进行锯 割,可使得到的三种管料既能配套又能使残料最少？解：首先，我们用下表列出可能的各种截法：截法长 度45cm 80cm 95cm16 0 0 3024 1 0 4034 0 1 2543 2 0 552 1 1 3562 0 2 2071 3 0 1581 2 1 090 1 2 30100 0 3 15残料设 x j ? j ? 1,2,?,10? 表示按照第j种截法锯割 的钢管的根数，那么截出的长45cm管料的根数 6 x1 ? 4 x2 ? 4 x3 ? 3x4 ? 2 x5 ? 2 x6 ? x7 ? x8 为 截出的长80cm管料的根数为x2 ? 2 x4 ? x5 ? 3x7 ? 2 x8 ? x9求解截出的长95cm管料的根数为x3 ? x5 ? 2x6 ? x8 ? 2x9 ? 3x10此时，残料的长度为30x1 ? 40x2 ? 25x3 ? 5x4 ? 35x5 ? 20x6 ? 15x7 ? 30x9 ? 15x10于是，我们要解决的问题归结为下列数学形式：6x1 ? 4x2 ? 4x3 ? 3x4 ? 2x5 ? 2x6 ? x7 ? x8 ? 5ax2 ? 2 x4 ? x5 ? 3x7 ? 2 x8 ? x9 ? 3ax j ? 0 ? j ? 1,2,?,10?x3 ? x5 ? 2 x6 ? x8 ? 2 x9 ? 3x10 ? 2a求满足以上条件的 x j 使得f ? 30x1 ? 40x2 ? 25x3 ? 5x4 ? 35x5 ? 20x6 ? 15x7 ? 30x9 ? 15x10取最小值。不难看出，上面这些问题虽然各式各样，但 它 们的数学模型却有相同的数学形式，即：求一个线 性函数的最大值（或最小值），而这个线性函数的 变量是非负的，满足一组线性等式或不等式。我们 把具有这种模型的问题称为线性规划问题。所以线性规划问题的数学模型的一般形式为(3.1.14) min max ?c j x j求 （或 它的变量满足 ）j ?1 n? n ? ? aij x j ? bi 或 ? bi 或 ? bi ?i ? 1,2,?, m? (3.1.15) ? j ?1 ? x j ? 0 ? j ? 1,2,?, n ? ???3.2 线性规划问题的基本概念线性规划问题的数学模型有许多种，目标函 数有求最小值的，有求最大值的；约束条件有的是 “≤”形式的，也有“≥”或“＝”形式的。我们 希望能 把各种不同形式的线性规划问题的数学模型化为 一 种统一的标准形式，这样只要对标准形式找出一 种 解法，就可以解决其余不同形式的线性规划问题(一) 线性规划问题的标准形式规定下列形式的线性规划问题为标准形式：max S ? c1 x1 ? c2 x2 ? ? ? cn xn? a11 x1 ? a12 x2 ? ? ? a1n xn ? b1 ? a x ? a x ??? a x ? b 22 2 2n n 2 ? 21 1 ? ? ? ? ? s.t.? ?a x ? a x ? ? ? a x ? b m2 2 mn n m ? m1 1 ? j ? 1,2,?, n ? ? xj ? 0 ?(3.1.16)(3.1.17)其中 c j , aij , bi 均为常数，且 bi ? 0 ?i ? 1,2,?, j ? 1,2,?, n?此标准形式可以写成矩阵的形式：求 max S ? CX ?AX ? b s.t.? ?x ? 0(3.1.18)(3.1.19)其中 C ? ?c1 , c2 , ?, cn ?? a11 a12 ? ? a21 a22 A?? ? ? ? ?a ? m1 am 2 ? a1n ? ? b1 ? ? ? ? ? a2 n ? ? b2 ? ? b?? ? ? ? ? ? ? ? ? ? amn ? ? bm ??0? ? x1 ? ? ? ? ? ? x2 ? 0 ? ? 0 ? X?? ? ??? ? ? ? ? ? ?0? ?x ? ? ? ? n?(二) 怎样把线性规划问题的非标准形式化为标准形式1、如果目标函数是求 min S ? CX 则只需要令 S ? ? ? S便有 max S ? ? ?CX把求得的 S ?的值反号,便可得到原问题的最小值。 2、如果第 r 个约束条件为ar1 x1 ? ar 2 x2 ? ? ? arn xn ? br则引入松弛变量 xn?r ? 0 ?r ? 1,2,?, m?上式便可化为ar1 x1 ? ar 2 x2 ? ? ? arn xn ? xn?r ? br3、如果第 k 个约束条件为ak1 x1 ? ak 2 x2 ? ? ? akn xn ? bk则引入剩余变量 xn?k ? 0 ?k ? 1,2,?, m? 上式化为 ak1 x1 ? ak 2 x2 ? ? ? akn xn ? xn?k ? bk 注意：松弛变量 xn? r和剩余变量xn?k 都不是决策变量, 所以它们在目标函数中的系数为0。 4、如果第 i 个约束条件为等式，但有某个常数 bi ? 0 则在第 i 个等式的两边同时乘以 ? 1 化为? ai1 x1 ? ai 2 x2 ? ? ? ain xn ? ?bi (此时 ? bi ? 0)5、如果某个决策变量 x j 没有非负约束，则令? ? x j ? 0, x j ? 0? ? x j ? x j ?x j 且代入约束方程与目标函数则全部都有非负限制了。【例1】把下面的线性规划问题化为标准形式原问题min S ? 2 x1 ? 3x2 ? x3? x1 ? x 2 ? 2 x3 ? 8 ? 2 x ? x ? 3 x ? 20 ? 2 3 s.t.? 1 ? ? x1 ? x 2 ? 2 x3 ? ?2 ? x1 ? 0, x 2 ? 0, x3 无非负限制 ?? ? max S ? ? ?2 x1 ? 3x2 ? ( x3 ? x3 )? x ? x ? 2( x ? ? x ? ) ? x ? 8 2 3 3 4 ? 1 ? 2 x1 ? x 2 ? 3( x3? ? x3 ? ) ? x5 ? 20 s.t.? ? ? ? x1 ? x 2 ? 2( x3 ? x3 ) ? 2 ? ? ? x1 , x 2 , x3 , x3 , x 4 , x5 ? 0 ?标准形式【例2】把下面的LP问题化为标准形式maxW ? 5 x1 ? 8 x2 ?3 x1 ? 2 x2 ? 6 (3.1.20) ? s.t.? x1 ? x2 ? 1 ?x , x ? 0 ? 1 2 为了把不等式约束变为等式约束,引入松弛变量 x3 , x4 ? 0则问题(3.1.20)可转化为 max W ? 5 x1 ? 8 x2?3 x1 ? 2 x2 ? x3 ? 6 ? s.t.? x1 ? x2 ? x4 ? 1 ?x , x , x , x ? 0 ? 1 2 3 4(3.1.21)【例3】把下面的LP问题化为标准形式min Z ? x1 ? 2 x2 ? x3 ? x1 ? x2 ? x3 ? 9 ?x ? x ? x ? 3 ? 1 2 3 s.t.? ?2 x1 ? x2 ? x3 ? 1 ? x1 ? 0, x2 ? 0 ?max Z ? ? ? x1 ? 2 x2 ? x4 ? x5 ? x1 ? x2 ? x4 ? x5 ? x6 ? 9 ?x ? x ? x ? x ? x ? 3 ? 1 2 4 5 7 s.t.? ?2 x1 ? x2 ? x4 ? x5 ? 1 ? x1 , x2 , x4 , x5 , x6 , x7 ? 0 ?由于本题中x3没有非负限制,是自由变量,故引入松弛变量x4 , x5 ? 0 令 x3 ? x4 ? x5 为了使上述约束条件中的不等式变为方程, 再引入松弛 和剩余变 x7 , x6 ? 0, x7 ? 0 变量 x6 量则上述线性规划问题就可以转化成标准形式了.3.3 线性规划问题的基本理论一. 凸集和极点直观的看, 三角形, 矩形, 圆, 球体等都是凸的. 都有 这样的几何特性, 即连接形体中任意两点的线段都在该形 体之中. 因此,我们可以这样来定义凸集.1. 凸集定义1 设集S ?Rn, 如果对任意点x, y ? S ,0 ? ? 的任何 ? ,都有 ?x ? 1 ? ? y ? S , 则S称为凸集.???1例1 满足LP问题约束条件 Ax ? b, x ? 0 所有一切x所成的集R是一个凸集.证明. 因为?x, y ? RAx ? b, x ? 0; Ay ? b, y ? 0 所以 ?? ? ?0,1? 有且 ?x ? ?1 ? ? ?y ? 0 即A??x ? ?1 ? ? ?y ? ? ?Ax ? ?1 ? ? ?Ay ? ?b ? ?1 ? ? ?b ? b?x ? ?1 ? ? ?y ? R证毕.x ? ?x1, x2 ,?, xn ? 称为可行点或可行解, 所有可行点T定义2.满足LP问题约束条件Ax ? b, x ? 0 的点构成的集合R称为可行集或约束集,记为 R ? x Ax ? b, x ? 0??2. 极点与基本可行解定义3 设集S ? En为凸集, x∈S, 对于x, 若不存在两个不 S的一个极点或顶点. 同的点y,z∈S,使 x ? ?y ? ?1 ? ? ?z,0 ? ? ? 1 ,则称x为凸集例如: 三角形的顶点, 圆周上的任意一点均为极点.对于定义2中的算式 Ax ? b, x ? 0 ,设 A ? ?aij ?m?nx ? ?x1, x2 ,?, xn ? , b ? ?b1, b2 ,?, bm ? , 其中m ? n, b ? 0.T TA的秩为m, 即r(A)=m. 则可从A的n列中选 出m列,使它们线性无关, 为了书写方便, 不妨设A 的前m列线性无关, 即设a j ? ?a1 j , a2 j ,?, amj ? , j ? 1,2,?, m.T是线性无关的, 令 B ? ?a1, a2 ,?, am ?T则B是可逆的. 因此方程组 BxB ? b有唯一解x B ? B?1b, T 其中xB是一个m维的列矢量， B ? ?x1, x2 ,?, xm ? x? xB ? 令x ? ? ?，我们便得到Ax ? b的一个解， ?0? ? ? 它的前m个分量等于x B的相应分量，而后面的 n ? m个分量均为零。? xB ? 我们称B为基或基底，称上述的 x ? ? ?为 ?0? ? ? 约束方程组Ax ? b关于基底B的基本解，而与 B的第i列相应的分量xi ?i ? 1,2, ? , m ?称为基本变量 .例2. 考察线性规划问题解: 若令x1=x2=0, 则可得x3=9, max W ? 10x1 ? 11x2 x4=8,x5=1,即x=(0,0,9,8,1)T 显然x是一个可行解. 由于?1? ?0? ?0? ? ? ? ? ? ? a3 ? ? 0 ?, a4 ? ? 1 ?, a5 ? ? 0 ? ?0? ?0? ?1? ? ? ? ? ? ??3 x1 ? 4 x2 ? x3 ? 9 ?5 x ? 2 x ? x4 ? 8 ? 1 2 s.t.? ? x5 ? 1 ? x1 ? 2 x2 ? xi ? 0, i ? 1,2, ? ,5 ?是线性无关的, 故这个可行解x关于基底B=(a3,a4,a5)又是基 本解. 而且是非退化的, 所以x是一个非退化的基本可行解. 其 中x1,x2是非基变量, x3,x4,x5是基变量.下面的定理说明了极点与基本可行解之间的关系.定理1 设A ? ?aij ?m?n , x ? ? x1 , x2 , ? , xn ? ,Tb ? ?b1 , b2 , ? , bm ? , m ? n, 则点x 为凸集TR ? ?x Ax ? b, x ? 0? 的一个极点的充要条件是 : x 为 Ax ? b, x ? 0 的一个基本可 行解。证明: (1)必要性即设x为R的一个极点, 则x是Ax=b, x≥0的一个基 本可行解.设x有k个分量大于零, 不妨设其前k个分量xi&0, i=1,2,…,k, 用ai表示A的第i列, 于是?xai ?1ki i?b我们来证明a1,a2,…,ak是线性无关的, 因而 x=(x1,x2,..,xk,0,…,0)T 就是一个基本可行解.用反证法. 设a1,a2,…,ak是线性无关, 则必有k个 不全为零的数y1,y2,…,yk, 使T?yai ?1ki i?0令y ? ? y1 , y2 , ?, yk ,0,? ,0 ? , 则有Ay ? 0. 因为xi ? 0, i ? 1,2, ?, k，故可选取足够小的数? ? 0，使得 x ? ? y ? 0, x ? ? y ? 0，且A?x ? ? y ? ? b, A?x ? ? y ? ? b1 1 又x ? ?x ? ? y ? ? ?x ? ? y ?，即点x可以表示R中的 2 2 两个不同点的凸组合， 这与x是R的极点矛盾，所 以a1 , a2 , ? , ak 线性无关, 于是 x是一个基本可行解。(2)充分性 设x=(x1,x2,…,xk,0,…,0)T是Ax=b, x≥0 的一个基本可行解, 即当x是一可行解,且a1,a2,…,ak线性无 关时,点x一定R的一个极点.用反证法. 设x不是R的一个极点, 则必有R中的两个不同的点y,z,使得x=sy+(1-s)z,(0&s&1)即xj=syj+(1-s)zj,j=1,2,…,n. 因当j=k+1,k+2,…,n时, xj=0,故上式成为0=syj+(1-s)zj,j=k+1,k+2,…,n又因为yj≥ 0,zj≥0,0&s&1,所以有yj=zj=0, j=k+1,k+2,…,n 由于y,z属于R, 所以Ay=b,Az=b, 因此有y1a1+y2a2+…+ykak=b, z1a1+z2a2+…+zkak=b两式相减得(y1-z1)a1+(y2-z2)a2+…+(yk-zk)ak=0 因为y≠z,所以yj-zj不全为零,于是a1,a2,…,ak线性相关,这与假设矛盾,所以x是R的一个极点.(证毕)3.3 线性规划问题的基本理论当一个可行解x又是基本解时, 称它为基本可行解. 若一个基本解中, 至少有一个基本变量xi为零时, 则称它为退化的基本解. 因此, 一个基本可行解x是一个至多有m个正xi的可行解, 而另一个非退化的基本可行解x是一 个恰有m个正xi的可行解.m 由于从n列中选取m个线性无关的列的取法至多只有C n种,所以一个m阶n维的LP问题, 其基本可行解的个数也不 m 会超过 C n 个。3.4 LP模型的几何解释和图解法对只有两个变量的线性规划问题，我们可以在直角坐标 平面上，用图解法求解此类线性规划问题。虽然在实际应用 中，我们很少遇到这样简单的问题，但通过两个变量线性规 划问题的图解法，我们能更直观地理解后面的线性规划问题 的基本理论。解题步骤：（1）画出可行解域以两个约束变量为坐标轴画直角坐标系,第一象限的点满足非 负约束条件, 所以一般只画出第一象限部分, 将两个约束条件对应 的半平面画出, 得到图中的阴影部分, 它是满足约束条件的所有点 所组成的集合,称为可行解域,简称可行域.（2）画出等值线目标函数Z=c1x1+c2x2+…+cnxn在坐标平面上, 表示以Z为参数的一族平行线, 其中任一条直线上含于可行域 内的点有相同的目标函数值Z, 故这些直线称为等值线. （3）求最优解 等值线在上方的表示Z值大, 我们一般希望找到一个使 Z值尽可能的大且与可行域有交的直线. 由于最优解是在可 行域构成的凸集中的极点处,所以我们不必研究可行域内的 每一点的情况,只须求可行域的顶点及其对应的目标函数值.3.4 LP模型的几何解释和图解法为了在讨论LP问题的解法时有一个直观背景,我们来说明它 的几何意义,并给出二维LP问题的一种解法--图解法.例1. 考虑如下的LP问题:max Z ? x1 ? 3 x2 ? x1 ? x2 ? 2 s.t.? ? x1 , x2 ? 0解. 约束条件x1,x2≥0表示可行解集R在第一象限之内, 而 约束条件x1+x2≤2说明R位于直线x1+x2=2的下方, 所 以可行集R为图中的三角形OAB.例1的图形:x2 2B 1 R O A x1+3x2=6 3 6 x1+3x2=3 x1+3x2=0 x1令Z=0,3,6,…,作出目标函数Z的等值线x1+3x2=0, x1+3x2=3, x1+3x2=6,…,等等, 这是一族平行线,容易 看出:Z0值越大, 等值线x1+3x2=Z0离开原点就越远.因此,求解上述问题可以转化为:在上述平行线族中, 找出一条,使它与可行解集R相交, 而它又离开原点最远, 即Z0的值最大.由图形可见: 过B点的等值线x1+3x2=6即为所求, 这 时Z0=6. 而B点的坐标x1=0, x2=2既满足约束条件, 又使 目标函数Z=x1+3x2取得最大值Z=6. 所以, 该问题的最优解为x*=(0,2)T,最优值为Z*=6. 结论: 由本例可以看出, LP问题的可行解集R是一个三 角形(一般为一个凸多边形), 其最优值必在R的一个顶点 (也叫极点)上达到.例2. 求解如下的LP问题min Z ? 2 x1 ? x2 ?3 x1 ? 4 x2 ? 12 ? s.t.?3 x1 ? 5 x2 ? 30 ?x , x ? 0 ? 1 2解. 用图解法求解(三个步骤). 1. 画出该问题的可行解区域R(四边形ABCD), 如下图所示.例2 示意图x2 2x1+x2=8 2x1+x2=20D2x1+x2=4 A 2x1+x2=2 ORB 2x1+x2=3 C 3x1+4x2=12 x1 3x1+5x2=302. 令Z=2,3,4,8,20,…,作出目标函数Z=2x1+x2的等 值线(上图中红色的直线).3. 从图中看出: 经过A点的等值线L: 2x1+x2=3与可行 域R相交, 且A点又使目标函数达到最小值, 所以该问题的 最优解为x*=(0,3)T, 最优值为Z*=3.图解法小结:1. 画出所要求解的LP问题的可行域R. 2. 令Z=c1,c2,c3,…,作出线性规划问题目标函 数Z=f(x1,x2)的等值线Z=ci ,i=1,2,3,…. 3. 通过观察等值线在可行域R上的变化趋势, 确 定使目标函数Z=f(x1,x2)取得最小(大)值的可 行点x*, 即为所求的LP问题的最优解.max Z ? 60x1 ? 80x2例3.求解如下的LP问题x2(1)画图86 4 2? ? ? ?R(2)分析求解 由图可以看出, 此问题的可行域R是一 个无界区域,当Z由小变大时,等值线沿其正 法线方向向右上方无限地移动下去. (3)结论 由于目标函数值没有 上界,故此问题无解. 我们 x1 称这种情况为无界解或没 有有限最优解.? x1 ? 2 x2 ? 6 ? s.t.?2 x1 ? x2 ? 8 ?x , x ? 0 ? 1 2O????2 4 6 8小结: LP问题解的几种情况（1）若LP问题有可行解, 则可行域是一个凸多边形(或凸多面体), 这个 凸凸多边形(或凸多面体)可能是有界的, 也可能是无界的.（2）若LP问题有最优解, 则最优解可能是唯一的, 也可能有无穷多个. 如果解是唯一的, 那么这个最优解一定可以在该凸多边形的某个顶点 上达到; 如果最优解有无穷多个, 那么这些最优解一定充满凸多边形的 一条边界(包括此边界的两个端点). 总之,如果LP问题有最优解,那么 最优解一定可以在可行域的顶点上达到. （3）若LP问题有可行解, 但没有最优解, 那么可行域是无界的. （4）若LP问题没有可行解, 那么可行域是空的,也没有最优解.第一次课堂测试用图解法求解下面的LP问题: (1) max Z ? 8 x1 ? 5 x2 (2) max Z ? 16x1 ? 7 x2?3x1 ? 8 x2 ? 60 ? s.t.?5 x1 ? 2 x2 ? 40 ?x , x ? 0 ? 1 2? x1 ? 2 x2 ? 4 ?2 x ? x ? 6 ? 1 2 s.t.? ? x1 ? x2 ? 8 ? x1 , x2 ? 0 ?要求: (1)画图(2)分析作答参考答案(1) max Z ? 8 x1 ? 5 x2解: 绘图如下x220 15?3x1 ? 8 x2 ? 60 ? s.t.?5 x1 ? 2 x2 ? 40 ?x , x ? 0 ? 1 2分析求解: 从图中可以看出,最优 解在B点达到, 其坐标为: B(100/17,90/17),对应 的最大利润为1250/17.10 5C? ? ? ?R5x1+2x2≤40B53x1+8x2≤60A 1015 20O????x1Z=8x1+5x2参考答案(2) max Z ? 16x1 ? 7 x2解: 绘图如下x28 64? x1 ? 2 x2 ? 4 ?2 x ? x ? 6 ? s.t.? 1 2 ? x1 ? x2 ? 8 ? x1 , x2 ? 0 ? 分析求解:从图中可以看出,可行 解集是空集,于是没有最优 解.2? ? ? ?x1+x2≥82x1+x2≤6O?? ???2 4 6 8 10x1+2x2≤4x13.5 整数线性规划所谓整数线性规划是指：一个线性规划问题，除了要满足约束条件外还要求最优解的每个分量都取整数。 求解整数线性规划的方法： （1）分支定界法； （2）分解算法； （3）平面法； （4）松弛方法； （5）群论方法等。用分支定界法求解整数线性规划问题分支定界法属于穷举法，当整数线性规划问题 相 应的线性规划问题的可行解域有界时，则整数线性规 划问题的可行解的数目一定的有限的。 我们可以把全部可行解求出后比较它们的目标函 数值，得到最优解。但当问题较大这样穷举显然不切 实际。分支定界法在穷举的过程中缩小了穷举的范围 大大减少了计算量，是比较适用的方法。 具体例子详见教材下册P21―【例1.10】3.6 线性规划的对偶理论每一个线性规划问题都伴随着另一个线性规划问题,两 者关系密切,互为对偶;其中一个称为原问题, 另一个称为对 偶问题. 研究对偶问题之间存在的客观联系及其性质, 便成 为线性规划问题的对偶理论. 这种问题的特点是:解原问题的同时也得到了其对偶问 题的解. 对偶问题的解在实际中有重要的应用背景, 它能够提供很有价值的经济和管理信息. 因此, 研究对偶理论问题在经济管理领域中具有重要的意义.一 线性规划的对偶问题的提出例1 胜利家具厂生产桌子和椅子两种家具.桌子售价50元/个 椅子售价30元/个,生产桌子和椅子需要木工和油漆工两个工种 生产一个桌子需要木工4小时,油漆工2小时. 生产一个椅子需要 木工3小时,油漆工1小时.该厂每月可用木工工时为120小时,油 漆工工时为50小时.问该厂如何组织生产才能使每月的销售收入 最大? 解: 该问题的标准形式为max Z ? 50x1 ? 30x2 ?4 x1 ? 3 x2 ? 120 ? s.t.?2 x1 ? x2 ? 50 ?x , x ? 0 ? 1 21. 对偶问题的提出: 对例1来讲,考虑更换角度后的另 外一种经营问题,将得到与上述模型密切相关的以下LP模型.如果某企业家有一批待加工的订单, 有意利用该家具厂的 木工和油漆工资源来加工产品. 需要与家具厂谈判付给该厂每 个工时的价格.如果该企业家已对家具厂的经营状况有详细的了 解,那么他将如何构造一个数学模型来研究如何才能既让家具厂 觉得有利可图而肯把资源出租给他,同时又使自己所付的租金最 少?2. 对偶问题模型的构造显然,该企业家的目标是使所付的租金最少.如果设y1为付给每个木 工工时的租金,y2为付给每个油漆工工时的租金,则所付租金最小的目标 可以表示为min f ( y1 , y2 ) ? 120y1 ? 50y2其中系数120和50分别表示家具厂可供租用的木工和油漆工的工时数量.3. 对偶问题模型的约束条件由于该企业家支付的租金不能太低,否则家具厂的管理者会 觉得无利可图而不肯将工时租给他.因此他付的租金应不低于 家 (1) 支付相当于生产一个桌子的木工和油漆工的工时的租金应该不 具厂利用这些资源所能得到的利益,因此有以下的约束条件:低于生产一个桌子的收入,即4 y1 ? 2 y2 ? 50(2) 支付相当于生产一个椅子的木工和油漆工的工时的租金应该不 低于生产一个椅子的收入,即 3 y1 ? y2 ? 30 上述两个不等式可以解释为: 生产一个桌子(椅子)的木工工时×木工工时租金＋生产一个桌子(椅子) 的油漆工工时×油漆工工时租金≥一个桌子(椅子)的销售收入(3)再加上付给每种工时的租金应大于零: y1&0,y2&0, 于是我们就得到了关于家具厂的另外一个线性规划问题:min S ? 120y1 ? 50 y2 ?4 y1 ? 2 y2 ? 50 ? s.t.?3 y1 ? y2 ? 30 ?y , y ? 0 ? 1 2仔细观察, 看看它们之间 的联系是否很密切呢? 原来的问题:max Z ? 50x1 ? 30x2 ?4 x1 ? 3 x2 ? 120 ? s.t.?2 x1 ? x2 ? 50 ?x , x ? 0 ? 1 2二 对偶线性规划问题的种类（1）对称形式的对偶规划 （2）非对称形式的对偶规划对称形式的对偶规划问题原问题max S ? c1 x1 ? c2 x2 ? ? ? cn xn ?a11 x1 ? a12 x2 ? ? ? a1n xn ? b1 ? ?a21 x1 ? a22 x2 ? ? ? a2 n xn ? b2 ? s.t.? ???? ?a x ? a x ? ? ? a x ? b mn n m ? m1 1 m 2 2 ? x j ? 0? j ? 1,2,?, n ? ?对偶问题 min Z ? b1 y1 ? b2 y2 ? ? ? bm ym?a11 y1 ? a21 y2 ? ? ? am1 ym ? c1 ? ?a12 y1 ? a22 y2 ? ? ? am 2 ym ? c2 ? s.t.? ???? ?a y ? a y ? ? ? a y ? c mn m n ? 1n 1 2 n 2 ? y j ? 0? j ? 1,2,?, m ? ?对称形式的对偶线性规划问题的矩阵表示原问题max S ? C X?YA ? C ?AX ? b s.t.? s.t.? ?Y ? 0 ?X ? 0 其中 C ? ?c1, c2 ?, cn ?, X ? ?x1, x2 ,?, xn ?T , Y ? ? y1, y2 ,?, ym ?T对偶 问题min Z ? Yb? a11 ? ? a21 A?? ? ? ?a ? m1a12 a22 ? am 2? a1n ? ? b1 ? ? ? ? ? a2 n ? ? b2 ? ?, b ? ? ? ? ? ? ? ? ? ?b ? ? amn ? ? ? m?三 如何将原问题转化为对偶问题原问题1 目标函数求max S 2 目标函数中的系数ci 3 约束条件中的右端常数项bj 4 约束条件的系数矩阵A 5 约束条件有m个 6 决策变量有n个 7 约束条件为?≥0”(”≤0” ,=0)对偶问题目标函数求min Z 约束条件中的右端项ci 目标函数中的系数bj 约束条件的系数矩阵AT 对偶变量有m个 约束条件有n个 对偶变量?≤0”(”≥0”,无限制)8 决策变量?≥0” (”≤0”,无限制) 约束条件为?≥0”(”≤0”,”=0”)原问题max Z ? c1 x1 ? c2 x2 ? ? ? cn xn ?a11 x1 ? a12 x2 ? ? ? a1n xn ? b1 ?a x ? a x ? ? ? a x ? b 2n n 2 ? 21 1 22 2 ? s.t.? ?? ?a x ? a x ? ? ? a x ? b mn n m ? m1 1 m 2 2 ? xi ? 0?i ? 1,2,?, n ? ?对偶问题min W ? b1 y1 ? b2 y2 ? ? ? bm ym ?a11 y1 ? a21 y2 ? ? ? am1 ym ? c1 ?a y ? a y ? ? ? a y ? c m2 m 2 ? 12 1 22 2 ? s.t.? ?? ?a y ? a y ? ? ? a y ? c mn m n ? 1n 1 2 n 2 ? yi ? 0?i ? 1,2,?, m ? ?或者max Z ? cx ?Ax ? b s.t.? ?x ? 0min W ? yb ?yA ? c s.t.? ?y ? 0例: 写出下列LP问题的对偶问题max S ? 2 x1 ? 4 x2 ? 3 x3 ? x1 ? x2 ? x3 ? 10 ?? x ? 4 x ? 3 x ? ?5 ? 1 2 3 s.t.? ?3 x1 ? 2 x2 ? 5 x3 ? 8 ? x1 ? 0, x2 ? 0 ?min Z ? 10 y1 ? 5 y2 ? 8 y3 ? y1 ? y2 ? 3 y3 ? 2 ?? y ? 4 y ? 2 y ? 4 ? 1 2 3 s.t.? ?2 y1 ? 3 y2 ? 5 y3 ? ?3 ? y1 ? 0, y3 ? 0 ?竞赛题赏析:两辆铁路平板车的装货问题――1988年美国数模竞赛(MCM)(B题)有七种规格的包装箱要装到两辆平板车上,包装箱的宽和高是一 样的但厚度t(以厘米计)及重量w(以公斤计)是不同的. 下表给出了 每种包装箱的厚度,重量以及数量. 每辆平板车有10.2米长的地方可 用来装包装箱(象面包片那样),载重量为40吨. 由于地区货运的限制, 对C5,C6,C7类包装箱的总数有一个特别的限制:这三类箱子所占的总 空间(厚度)不能超过302.7厘米.包装箱类型C1 48.7 8C2 52.0 7C3 61.3 9C4 72.0 500 6C5 48.7 6C6 52.0 4C7 64.0 8T(厘米) W(公斤) 数量000010.2m问题要求：设计一种装车方案,使剩余的空间最小。(一) 问题的假设1. 包装箱不能分割成较小的部分; 2. 所有的数据均是精确值,无任何测量误差; 3. 给出的解,均可进行装卸.(二) 模型的建立容易计算出所有包装箱的总厚度为27.495米,事实上有总厚度=48.7×8+52.0×7+61.3×9+72.0×6+48.7×6 +52.0×4+64.0×8=27.495(米)而两辆铁路平板车总共有20.4米(10.2×2) 长的地方,所 以不可能把包装箱全部装运上车。 以xij表示装到第j(j=1,2)辆铁路平板车上的第i种包装箱Ci 的个数(1≤i≤7); xij是本问题里的决策变量。符号说明:Ni --- 表示类型为Ci的包装箱的总件数； Wi--- 表示类型为Ci的包装箱的每件重量； ti --- 表示类型为Ci的包装箱每件厚度； S --- 表示剩余的空间。 我们的目的是使装车剩下的空间最小。为此构造模型如下：7 7 ? ? ? ? min S ? ?1020? ? ti xi1 ? ? ?1020? ? ti xi 2 ? i ?1 i ?1 ? ? ? ?? 2040? ? ti ? xi1 ? xi 2 ?i ?17约 束 条 件 为7 ? t i xi1 ? 1020 平板车1的长度限制 i ?1 7 ? t i xi 2 ? 1020 平板车 2的长度限制 i ?1 7 ? wi xi1 ? 40000 平板车1的载重量限制 i ?1 7 ? wi xi 2 ? 40000 平板车 2的载重量限制 i ?1??????? ? ?Ci 类包装箱的件数限制 ? xi1 ? xi 2 ? N i t 5 ? x51 ? x52 ? ? t 6 ? x 61 ? x 62 ? ? t 7 ? x 71 ? x72 ? ? 302.7xij ? 0且为整数此ILP模型还可以写成以下形式：7 7 7 ? ? ? ? min S ? ?1020? ? ti xi1 ? ? ?1020? ? ti xi 2 ? ? 2040? ? ti ?xi1 ? xi 2 ? i ?1 i ?1 i ?1 ? ? ? ?7 ? ? t x ? 1020 ? j ? 1, 2 ?? 厚度约束 i ij i ?1 ? ?7 ?i?1wi xij ? 40000? j ? 1, 2 ?? 重量约束 ? ?2 ? s.t.? ? xij ? xi1 ? xi 2 ? N i ?i ? 1, 2, ? ,7 ?? 数量约束 j ?1 ? 7 ? ? t x ? 302.7? j ? 1, 2 ?? 特殊约束 ?i ?5 i ij ? x ? 0且为整数? j ? 1, 2; i ? 1, 2, ? ,7 ? ? ij ?对上述整数线性规划问题(ILP)用分枝定界法可求得30个不同 的解如下(没有利用的空间为0.6cm) 平板车1 1 2 2 2 2 3 5 9 5 4 3 1 3 5 3 2 3 6 0 0 1 7 0 0 0 1 4 4 4 2 4 5 5 4 4 4 平板车2 3 4 0 4 4 3 5 3 5 0 1 0 6 3 3 2 7 0 0 0箱 子 类 型44 411 095 913 123 212 200 044 466 704 053 510 121 100 043 3 307 7 654 0 433 5 331 2 130 1 100 0 045 5 570 0 145 9 533 1 302 1 203 2 200 0 0续前表 平板车1 1 2 6 5 5 3 0 4 0 4 5 3 5 5 2 1 2 6 2 2 3 7 0 0 0 1 5 5 5 2 1 2 2 3 3 3 平板车2 3 9 5 9 4 1 3 1 5 1 2 1 6 1 1 0 7 0 0 0箱 子 类 型33 342 149 931 113 330 100 055 535 650 035 520 003 200 032 2 207 6 594 4 413 3 332 2 220 1 200 0 056 6 670 1 205 5 553 3 301 1 113 2 100 0 0续前表 平板车1 平板车2125 430 445 353 263 370 016 622 339 541 350 160 070 0箱 子 类 型2 211 1 0 0 0 065 4 7 7 6 644 4 9 6 9 633 3 0 4 0 433 3 0 0 0 012 3 2 0 3 100 0 0 0 0 077 7 8 8 8 812 3 0 0 1 155 5 0 3 0 333 3 6 2 6 200 0 3 3 3 321 0 1 3 0 200 0 0 0 0 005640208232310(三) 模型的分析现在我们分析求得的解是否最优？考虑C5、 C6、C7三种类型的箱子， 它们有如下特别的限制：t5 ?x51 ? x52 ? ? t6 ?x61 ? x62 ? ? t7 ?x71 ? x72 ? ? 302.7C5、 C6、C7类箱子的件数限制为xi1+xi2≤Ni (i = 5 ，6，7 ), 记x5 ? x51 ? x52 , x6 ? x61 ? x62 , x7 ? x71 ? x72并把已知的 ti 与 Ni (5≤ i ≤7 )代入，我们有?48.7 x5 ? 52x6 ? 64x7 ? 302.7 ?0 ? x ? 6 5 ? ? ILP : ?0 ? x6 ? 4 ?0 ? x ? 8 7 ? ? x5 , x6 , x7为整数 ?这个问题的解共有315个，其中使z=48.7x5+52x6+64x7的 值介于[292.2，302.7]之间的解有以下6个:x53 4 0 5 1 6x63 2 2 1 1 0x70 0 3 0 3 0Z=48.7x5+52x6 +64x7302.1cm 298.8cm 296.0cm 295.5cm 292.7cm 292.2cm可以看出: 对类型为C5、C6、C7三种类型的包装箱,在所占空间厚度不 能超过302.7厘米的限制下, 两辆平板车最多只能装运302.1厘米宽度的包 装箱. 此时C5类型和C6类型的包装箱各装3只，不装C7类型的包装箱。由4?t Ni ?1 ii? 48.7 ? x1 ? 52.0 ? x2 ? 61.3x3 ? 72.0 x4 ? 48.7 ? 8 ? 52.0 ? 7 ? 61.3 ? 9 ? 72.0 ? 6 ? 1737 3?cm? .即：两辆平板车装运C1、C2、C3 、C4四种类型的包装箱的空间厚度 为1737.3厘米，从而总的装运空间的厚度为 302.1+9.4(厘米) 因此，装运时的剩余空间至少为 =0.6 (厘米) 这说明我们求得的30个解均为最优解。如果我们进一步要求这两辆平板车装运包装箱后，使得剩 余空间相同，此时的解如下：C1 C2 C3 C 4 C5 C6 C70 8 0 8 7 0 6 1 9 0 9 0 0 6 0 6 0 3 0 3 2 1 3 0 0 0 0 0平板车第一辆 第二辆 第一辆 第二辆厚度重量00 00 00 00注意到: 最优解不装运C7类箱子。如果再进一步要求每一种类型的包装箱都必须装运一部分，从前面各表 中数据可以看出，此时两辆平板车装运的C1―C7类型包装箱的数量应 该是8,7,9,6,1,1,3.此时装完两辆平板车后，剩余的空间至少为+(cm)3.7 动态规划模型? ?线性规划问题 ?静态的优化问题 ?非线性规划问题 ? ? 优化问题 ? ?整数规划问题 ? ? ?动态的优化问题： 多阶段决策问题 ?3.7 动态规划模型动态规划( Dynamic Programming )是用来解决多 阶段决策过程最优化问题的一种行之有效的方法。1951 年美国数学家贝尔曼(R.Bellman)等人根据一类多阶段决 策问题的特点，提出了解决这类问题的“最优化原理”， 并 研究了许多数学模型，成功地解决了生产管理、工程技术 等方面的实际问题，建立了运筹学理论中的一个新分支― ―动态规划，1957年贝尔曼发表了动态规划方面的首部 专著《动态规划》。动态规划方法在工程技术、经济管 理、工业生产和军事科学等领域均有着极为广泛的应用。动态规划问题的研究种类1.最优路径问题 3.投资决策问题 5.排序问题 2.资源分配问题 4.生产计划与库存问题 6.货物装载问题7.生产过程中的最优控制问题动态规划问题的特点动态规划不象线性规划或非线性规划有一个标准的表达式,而是不同的具体问题就有相应不同的、具体的数学表达式，从而动态规划没有统一的处理格式，它必须依据问题本身的特性, 利用灵活的数学技巧来解决，因而属于灵活、动态的数学方法动态规划模型的种类动态规划模型的种类很多，可根据决策过程的时间参数 是离散的还是连续的，过程的演变是确定性的还是随机性的, 分为离散确定型、离散随机型、连续确定型和连续随机型四 种，其中离散确定型是最基本的动态规划模型。一、动态规划模型的基本概念1. 多阶段决策问题所谓多阶段决策问题，是指这样的一类特殊的活动过程，它们可 以按照时间和空间依次划分为若干个相互联系的阶段，在每一个阶段 中，都需要做出一定的决策（备选方案），全部过程的决策集形成一 个决策序列，这种考虑整个决策过程中各个阶段决策的全体又称为一 个策略，这类问题就是多阶段决策问题.2. 动态规划问题的基本概念(1) 阶段 (2) 状态 (3)决策 (4)策略 (5)状态转移方程 (6) 指标函数二、动态规划方法的基本思想动态规划方法的产生基于贝尔曼(R.Bellman)等人在50年代提出 的最优化原理:“对于一个过程的最优策略来说，无论其出发初始状态及初始决策怎样,由其先前所有决策所形成的状态，其后的剩余决策序列必构成最优策略”.三、动态规划的求解的两种方法(1) 逆序递推法 (2) 顺序递推法四 算例――最短路线问题如图所示，某人从A出发，要把一批物资沿图中的边送至E点 其中Bi,Ci,Di(i=1,2,3)代表九个小镇，所标数字代表不同道路的 长度(单位:千米)。问应选择哪条行走路线，可以使总行程最短？B1 4 8 8 7 C1 5 2 3 D1 5 D2 8 1 D3A8 3B2 2 4 7 84B391 C2 2 4 6 5 C3 5E解: 用d(sk,uk) 表示由点sk出发，采用决策uk到达下一阶段点sk+1 时的两点间的距离,fk(sk)表示从第k段状态点sk出发,采用最优策略到 该过程终止时的最短距离。即: fk(sk)=min{d(sk,uk)}采用逆序递推算法的求解过程如下：（1）从k=4开始，状态变量s4可以取三个值D1，D2，D3，因为由D1， D2，D3到E各有一条路，故容易求得f4(D1), f4(D2), f4(D3)。 （2）当k=3时，状态变量s3可以取三个值C1，C2，C3，这是一个经过 中途点D1，D2，D3到达终点的两步决策问题，具体求解步骤如下：（a）从C1出发，共有三个选择，即C1 D1，C1 D2 ，C1 有 ?d3 C1, D1 ? f 4 D1 ? ?2 ? 5?? ? ? ? ? ? ? ? f3 ?C1 ? ? min ?d3 ?C1, D2 ? ? f 4 ?D2 ?? ? min ?3 ? 8 ? ? 6 ? ? ?5 ? 1 ? d3 ?C1, D3 ? ? f 4 ?D3 ?? ? ? ?D3 E。D3 ，且故从C1出发到终点E的最短距离为6，最短子路线为C1（b）从C2出发，也有三个选择，即C2 D1，C2 D2 ，C2D3 ，且?d3 ?C2 , D1 ? ? f 4 ?D1 ? ? ?1 ? 5 ? ? ? ? ? f3 ?C2 ? ? min ?d3 ?C2 , D2 ? ? f 4 ?D2 ?? ? min ?2 ? 8? ? 5 ? ? ?4 ? 1 ? d3 ?C2 , D3 ? ? f 4 ?D3 ? ? ? ? ?故从C2出发到终点E的最短距离为5，最短子路线为C2D3E。 D3 ，且（c）从C3出发，也有三个选择，即C3 D1，C3 D2 ，C3?d3 ?C3 , D1 ? ? f 4 ?D1 ? ? ?6 ? 5? ? ? ? ? f3 ?C3 ? ? min ?d3 ?C3 , D2 ? ? f 4 ?D2 ?? ? min ?5 ? 8 ? ? 6 ? ? ?5 ? 1 ? d3 ?C3 , D3 ? ? f 4 ?D3 ?? ? ? ?D3故从C3出发到终点E的最短距离为6，最短子路线为C3E。（2）当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), f3(C3)为基础，再分别加上B1，B2，B3与C1，C2，C3 之间的相应距离，并加以比较，从而求出此阶段的最短路线。 具体求解步骤如下： （a）从B1出发，共有三个选择，即B1 C1，B1 C2 ，B1?d 2 ?B1, C1 ? ? f3 ?C1 ? ? ?8 ? 6 ? ? ? ? ? f 2 ?B1 ? ? min ?d 2 ?B1, C2 ? ? f3 ?C2 ?? ? min ?7 ? 5? ? 12 ? ? ? ?8 ? 6 ? d 2 B1, C3 ? ? f3 ?C3 ?? ? ? ?C3 ，且有故从B1出发到终点E的最短距离为12，最短子路线为B1 C2D3E。（b）从B2出发，也有三个选择，即B2 C1，B2 C2 ，B2C3 ，且有?d 2 ?B2 , C1 ? ? f3 ?C1 ? ? ?4 ? 6? ? ? ? ? f 2 ?B2 ? ? min ?d 2 ?B2 , C2 ? ? f3 ?C2 ?? ? min ?2 ? 5 ? ? 7 ? ? ? ?4 ? 6? d 2 B2 , C3 ? ? f3 ?C3 ? ? ? ? ?故从B2出发到终点E的最短距离为7，最短子路线为B2 C2D3 E。（c）从B3出发，也有三个选择，即B3 C1，B3 C2 ，B3?d 2 ?B3 , C1 ? ? f3 ?C1 ? ? ?7 ? 6? ? ? ? ? f 2 ?B3 ? ? min ?d 2 ?B3 , C2 ? ? f3 ?C2 ?? ? min ?8 ? 5 ? ? 13 ? ? ? ?9 ? 6 ? d 2 B3 , C3 ? ? f3 ?C3 ?? ? ? ?C3 ，且有故从B3出发到终点E的最短距离为13，最短子路线为B3 C2D3E。（3）当k=1时，状态变量s1只有一个取值，即出发点A，且?d 2 ?A, B1 ? ? f 2 ?B1 ? ? ?4 ? 12? ? ? ? ? f1 ? A? ? min ?d 2 ?A, B2 ? ? f 2 ?B2 ?? ? min ?8 ? 7 ? ? 15 ? ? ? ?3 ? 13? d 2 A, B3 ? ? f 2 ?B3 ? ? ? ? ?即从城市A出发，到终点E的最短距离为15，最短 子路线为 A B3 C2 D3 E。数学建模问题欣赏: 城镇道路扫雪模型――1990年美国数模竞赛(MCM)(B题)如图所示，实线表示美国马里兰州威克米尔市需要清除积雪的双向行车道路, 虚线是州高速公路。雪后，两辆扫雪车分别从地图中★号标出的两点以西约４英 里处出发清扫道路上的积雪。扫雪车可以通过高速公路进入市内道路，假定扫雪 过程中扫雪车不会损坏或停止，并且道路交叉处不需要另外附加的扫雪程序。试 为两车找出有效的路径。本题目是该城市道路局局长Kirk Banks工程师从该城实际扫雪工作中提出来的.城镇道路扫雪模型求解方法一----运用“中国邮递员问题”原理求解此问题(一) 模型的分析 我们的目的是要寻求一个有效的办法用两台扫雪车清除威克米尔市内 道路(不包括州高速公路)的积雪. 其有效解法应该具有以下特点:1. 扫完全部路面所花的时间尽量少; 2. 扫雪完毕后,两车应尽快回到出发点; 3. 两车工作时间大致相同.如果扫雪车没有重复走某一条路, 或者扫雪车重复走的路径和最小 我们就可以认为扫雪所花的时间最少.为了使交通尽快畅通,通常应该把 所花的时间少放在最重要的地位来考虑。必要时还要考虑首先清除威克 米尔市内道路交通图中的主要干线道路上的积雪问题，这时需要解决确 定哪些路线是主干线的问题。(二) 模型的假设1. 扫雪过程中没有下雪, 所有市内道路都有积雪需要清除.2. 两辆扫雪车性能相同，都能正常工作； 3. 两辆扫雪车司机驾驶技术相同，扫雪时车速相同；4. 在所有交叉路口, 包括市内道路与高速公路的接口, 扫雪车可以不减速地拐弯； 5. 两辆扫雪车出发的时间相同; 6. 每条路面的积雪范围、厚度相同。(三) 模型的建立1. 双行道问题★ 假定每条道路均有两条方向相反的行车道.此时将地图中每个交叉路口(包括市内与高速公路的交叉口)看成点,每条市内道路看成边, 它的长度看成该边对应的权,这样我们就得到了网络N=(V,E,W).★ 由于每条公路均是双行道,这样的网络N是一个欧拉有向图,每点的入次和出次相同.利用弗莱里算法可以求得N的欧拉环游.如果只有 一辆扫雪车，这就是“中国邮递员问题”。现在有两辆扫雪车,为了 使工作过程最优，两辆扫雪车应扫过几乎同样长的道路。★ 为此，我们把网络N分为两个子网络N1和N2，使得N1和N2均连通且N1和N2两子网络的权应尽可能相等。问题：把网络N分为两个子网络N1和N2,使得N1和N2均连通且N1 和N2两子网络的权应尽可能相等。 此问题的求解把网络N分成两个连通的子网络，分别算出两个子网络中所有边的总长度，由 于N的总边长已知，在总长度较大的子网络中减去一些与另一子网络相连的边，添 加到总长较小的子网络中.（参见下图）如果扫雪车在市内道路交叉路口或市内道路与高速公路交叉处可 以掉头，即扫雪车到达城市边缘可以不经高速公路而重新进入市区， 则可用上述方法求解。 如果忽略扫雪车在高速公路上的行车时间，则可同上述情况一样 求解；否则，我们要将高速公路看成上述网络的若干条新边，然后用 上述方法求解。2. 单行道问题近代喷气扫雪车已经问世，它靠喷射热气流来清除积雪，因此这 种扫雪车在双行道一边行驶时，就可以很容易的清除整条路面上的积 雪，无需再沿道路的另一边重新行驶。 求这种情况下的最优解问题称为单行道问题。对这类问题，与双行道问题一样,我们可以将它对应一个网络N， 并将N分成两个子网络N1和N2，要求N1和N2两子网络的边总长度相 等, 这样利用求解 “中国邮递员问题” 的算法可以分别求得N1和N2的 欧拉环游，得到我们要求的近似解。城镇道路扫雪模型求解方法二（1）粘贴丝线等分全城首先划分城市为南区与北区（或东区与西区），使两区分别连通， 且路的总长相等。具体操作时可把地图放大，用丝线沿街道曲线粘贴 再撕下丝线，测其总长；把北城（或东城）的街道粘贴丝线，使所用丝线是全城所用之半，且使粘线各街道与未粘线各街道分别连通，设粘线者为G1，其余为G2，甲车在G1上，乙车在G2上；然后在G1与G2 上分别执行Edmonds和Johnson解中国邮递员问题的算法。如果街道要求右侧通行，则分别在G1与G2上执行Fleury算法，即可找到甲乙两车的扫雪回路，执行Fleury算法时，认为每条街对应 等长共端的两条边。（参见下图所示）威克米尔市城区街道标识图（2）添加虚拟街道等分全城1 2 3 4 5 6 是6个死胡同，扫雪时，这6条街道必然要通过2次，所以可以各添加一条等长共端的虚拟街道；又设在高速公路上的各街口按顺 时针顺序依次1,2,3,…,26。假设高速公路不需要扫雪,在高速公路上的行驶速度足 够快，因此可以假设在城区街道对应的图G上，两个扫雪车在一个顶上，相邻近的 在高速公路上的路口在G的一个顶上. 例如：1与25在G的一个顶上，记成 (1,25)。其它路口结合情形为：(2,3), (4,5), (6,7), (8,9), (10,11), (12,13), (14,15), (16,17), (18,19), (20,21) , (22,23), (24,25)这样添加虚拟街道并且高速公路上“路口组合”后，G上无桥，是2-边连通图， 可采用算法把G分成G1与G2，且G1与G2分别连通(1,25)是公共顶，即两个扫雪车 既在G1上又在G2上。用Ed}