数学建模方法的应用.doc

数学建模方法的应用应用数学 *（广东惠州学院数学系*，广东惠州516007）（E-mail: *）摘要: 数学建模是培养学生应用数学能力, 培养学生的创造性的一种重要手段, 介绍了数学建模的基本概念, 并通过实例说明数学建模的过程。关键词：LP；IP；拉格朗日多项式插值把数学应用到任何一个实际问题中去, 都需要把这个问题的内在规律运用数字、图表、公式、符号表示出来, 经过数学的处理, 得出供人们作出分析预报、决策或者控制的定量结果, 这个过程就是人们常说的建立数学模型。一、线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(LinearProgramming 简记LP)则是数学规划的一个重要分支。自从1947 年 G. B.Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。例 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标x，y表示，距离单位：km)及水泥日用量d(t)由下表给出.目前有两个临时料场位于A（5，1），B（2，7），日储量各有20t.假设从料场到工地之间均有直线道路相连，试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小.模型 记工地的位置为，水泥日用量为；料场位置为，日储量为（j=1，2，分别表示A，B），从料场j向工地i的运送量为，这个优化问题的目标函数（总吨公里数）可表示为 （1）个工地的日用量必须满足，所以 ，i=1,2,.,6 （2）各料场的运送量不能超过日储量，所以 （3）问题归结为在约束（2），（3）及决策变量非负的条件下，使（1）式最小.决策变量只有，所以这是线性规划模型.二、整数规划规划中的变量（部分或全部）限制为整数时，称为整数规划（IP）。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。（一）整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：1、 变量全限制为整数时，称纯（完全）整数规划。2、变量部分限制为整数的，称混合整数规划。整数规划特点原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。例 求解如下IP模型： s.t. 且为整数.解 模型去掉整数限制后记作LP，其可行域为图中由点（0，0），（6，0），P（2.25，3.75），（0，5）围成的四边形，过P点的等值线（图中虚线）为，最优解在P点取得.图中小圆点为整数点，四边形中的小圆点才是IP的可行解.将P点舍入成整数或者找最靠近它的整数，都得不到IP的最优解.经在可行解中试探、比较得到下表: 表LP的最优解PP的舍入解靠近P的可行解IP最优解（2.25，3.75）z=41.25(2,4)不可行（2，3）z=34（0，5）z=40可见IP最优解不一定能从LP经过简单的“移动 ”得到.求解整数规划没有统一的有效方法，不同方法的效果与问题的性质有很大关系.三、非线性规划实例与定义如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。例 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金 A元，投资于第i(i = 1，.，n)个项目需花资金元，并预计可收益 元。试选择最佳投资方案。解 设投资决策变量为 ，i=1，.，n，则投资总额为，并且总的投资金额不能超过A，故有限制条件 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： s.t. 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 min f (x)s.t. （NP） 其中 称为模型（NP）的决策变量，f 称为目标函数，称为约束函数。另外，（i=1，.,p）称为等式约束，称为不等式的约束。对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。四、拉格朗日多项式插值1、插值多项式用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数 f (x)在区间a,b上n +1个不同点处的函数值，求一个至多n 次多项式 （1）使其在给定点处与 f (x)同值，即满足插值条件 （2） 称为插值多项式，称为插值节点，简称节点，a,b称为插值区间。从几何上看，n次多项式插值就是过n +1个点，作一条多项式曲线 近似曲线 y = f (x)。n次多项式（1）有n +1个待定系数，由插值条件（2）恰好给出n +1个方程 （3）记此方程组的系数矩阵为 A ，则 是范德蒙特(Vandermonde)行列式。当 互不相同时，此行列式值不为零。因此方程组（3）有唯一解。这表明，只要n +1个节点互不相同，满足插值要求（2）的插值多项式（1）是唯一的。插值多项式与被插函数之间的差 称为截断误差，又称为插值余项。当 f (x)充分光滑时， 其中。2、拉格朗日插值多项式实际上比较方便的作法不是解方程（3）求待定系数，而是先构造一组基函数是n 次多项式，满足 上式称为n次 Lagrange 插值多项式，由方程（3）解的唯一性，n +1个节点的n次Lagrange 插值多项式存在唯一。五、图与网络模型及方法图论起源于18 世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847 年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷 n 2n+2 C H 的同分异构物时，也发现了“树”。哈密尔顿于 1859 年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。例 对于图中所示的有向图，可以用邻接矩阵表示为 同样，对于网络中的权，也可以用类似邻接矩阵的n n 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。六、微分方程建模微分方程建模是数学建模的重要方法，因为许多实际问题的数学描述将导致求解微分方程的定解问题。把形形色色的实际问题化成微分方程的定解问题，大体上可以按以下几步：1. 根据实际要求确定要研究的量(自变量、未知函数、必要的参数等)并确定坐标系。2. 找出这些量所满足的基本规律(物理的、几何的、化学的或生物学的等等)。3. 运用这些规律列出方程和定解条件。列方程常见的方法有：（i）按规律直接列方程在数学、力学、物理、化学等学科中许多自然现象所满足的规律已为人们所熟悉，并直接由微分方程所描述。如牛顿第二定律、放射性物质的放射性规律等。我们常利用这些规律对某些实际问题列出微分方程。（ii）微元分析法与任意区域上取积分的方法自然界中也有许多现象所满足的规律是通过变量的微元之间的关系式来表达的。对于这类问题，我们不能直接列出自变量和未知函数及其变化率之间的关系式，而是通过微元分析法，利用已知的规律建立一些变量（自变量与未知函数）的微元之间的关系式，然后再通过取极限的方法得到微分方程，或等价地通过任意区域上取积分的方法来建立微分方程。（iii）模拟近似法在生物、经济等学科中，许多现象所满足的规律并不很清楚而且相当复杂，因而需要根据实际资料或大量的实验数据，提出各种假设。在一定的假设下，给出实际现象所满足的规律，然后利用适当的数学方法列出微分方程。在实际的微分方程建模过程中，也往往是上述方法的综合应用。不论应用哪种方法，通常要根据实际情况，作出一定的假设与简化，并要把模型的理论或计算结果与实际情况进行对照验证，以修改模型使之更准确地描述实际问题并进而达到预测预报的目的。卫星进入600km 高空轨道时，火箭必须的最低速度首先将问题理想化，假设：（i）卫星轨道是以地球中心为圆心的某个平面上的圆周，卫星在此轨道上以地球引力作为向心力绕地球作平面匀速圆周运动；（ii）地球是固定于空间中的一个均匀球体，其质量集中于球心；（iii）其它星球对卫星的引力忽略不计。建模与求解：设地球半径为 R ，质量为M ；卫星轨道半径为r ，卫星质量为m 。根据假设（ii）和（iii），卫星只受到地球的引力，由牛顿万有引力定律可知其引力大小为 （1）其中G 为引力常数。 为消去常数G ，把卫星放在地球表面，则由（1）式得 再代入（1）式，得 其中g = 9.81( )为重力加速度。根据假设（i），若卫星围绕地球作匀速圆周运动的速度为v，则其向心力为，因为卫星所受的地球引力就是它作匀速运动的向心力，故有 由此便推得卫星距地面为，必须的最低速度的数学模型为 取R = 6400km，r R = 600km，代入上式，得 v 7.6km/s即要把卫星送入离地面 600km 高的轨道，火箭的末速度最低应为7.6km/s。七、差分方程1、 差分方程简介规定t只取非负整数。记为变量 y在t点的取值，则称的一阶向前差分，简称差分，称的二阶差分。类似地，可以定义的n阶差分。由 的差分给出的方程称为的差分方程，其中含的最高阶差分的阶数称为该差分方程的阶。差分方程也可以写成不显含差分的形式。例如，二阶差分方程。满足一差分方程的序列称为差分方程的解。类似于微分方程情况，若解中含有的独立常数的个数等于差分方程的阶数时，称此解为该差分方程的通解。若解中不含任意常数，则称此解为满足某些初值条件的特解。称如下形式的差分方程 （1）为 n 阶常系数线性差分方程，其中 是常数，。其对应的齐次方程为 （2）容易证明，若序列方程（1）可用如下的代数方法求其通解：（I）先求解对应的特征方程 （3）（II）根据特征根的不同情况，求齐次方程（2）的通解。（i）若特征方程（3）有n 个互不相同的实根，则齐次方程（2）的通解为 （ii）若 是特征方程（3）的k 重根，通解中对应于 的项为为任意常数。（iii）若特征方程（3）有单重复根 = i ，通解中对应它们的项为（iv）若 = i是特征方程（3）的k 重复根，则通解对应于它们的项为（III）求非齐次方程（1）的一个特解为方程（2）的通解，则非齐次方程（1）的通解为。求非齐次方程（1）的特解一般要用到常数变易法，计算较繁。对特殊形式的b(t)也可使用待定系数法。例如，当次多项式时可以证明：若b不是特征根，则非齐次方程（1）有形如次多项式；若b是r重特征根，则方程（1）有形如的特解。进而可利用待定系数法求出，从而得到方程（1）的一个特解。例 求解两阶差分方程。解 对应齐次方程的特征方程为，其特征根为，对应齐次方程的通解为 原方程有形如at +b的特解。代入原方程求得，故原方程的通解为 八、对策论对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。零和对策（矩阵对策）零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。设局中人、的策略集分别为当局中人选定策略和局中人选定策略后，就形成了一个局势，可见这样的局势共有mn 个。对任一局势，记局中人的赢得值为，并称为局中人的赢得矩阵（或为局中人的支付矩阵）。由于假定对策为零和的，故局中人的赢得矩阵就是 A。当局中人、和策略集及局中人的赢得矩阵A 确定后，一个零和对策就给定了，零和对策又可称为矩阵对策并可简记成 例 设 有 一 矩 阵 对 策 ， 其 中 ， 从 A 中可以看出，若局中人希望获得最大赢利30，需采取策略，但此时若局中人采取策略，局中人非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人采取策略时，最坏的赢得结果分别为 min12,6,30,22 = 22 min14,2,18,10 = 2 min6,0,10,16 = 10其中最好的可能为。如果局中人采取策略，无论局中人采取什么策略，局中人的赢得均不会少于2。局中人采取各方案的最大损失为max12,14,6 = 14 ， max6,2,0 = 2，max30,18,10 = 30，和max22,10,16 =16。当局中人采取策略时，其损失不会超过2。注意到在赢得矩阵中，2 既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减少损失，称这样的局势为对策的一个稳定点或稳定解。九、目标规划 引言1线性规划的局限性只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。2实际决策中，衡量方案优劣考虑多个目标这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，LP 则无能为力。3目标规划（Goal Programming）美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在1961 年出版的管理模型及线性规划的工业应用一书中，首先提出的。求解思路（1）加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。（2）优先等级法将各目标按其重要程度不同的优先等级，转化为单目标模型。（3）有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。 目标规划的数学模型为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。例 某工厂生产 I，II 两种产品，已知有关数据见下表试求获利最大的生产方案。解 这是一个单目标的规划问题，用线性规划模型表述为：max最优决策方案为：元。但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如（i）根据市场信息，产品I 的销售量有下降的趋势，故考虑产品I 的产量不大于产品II。（ii）超过计划供应的原材料，需要高价采购，这就使成本增加。（iii）应尽可能充分利用设备，但不希望加班。（iv）应尽可能达到并超过计划利润指标56 元。这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。十、模糊数学模型1、基本概念1） 模糊集和隶属函数定义1 论域 X 到0,1闭区间上的任意映射 都确定 X 上的一个模糊集合A ，叫做A的隶属函数，叫做x 对模糊集A 的隶属度，记为： 使称为模糊集A 的过渡点，此点最具模糊性。显然，模糊集合A 完全由隶属函数来刻画，当时， A 退化为一