《《数学建模简明教程》ppt课件》由会员分享，可在线阅读，更多相关《《数学建模简明教程》ppt课件（112页珍藏版）》请在金锄头文库上搜索。
1、数学建模简明教程,国家精品课程,第一章 规划理论及模型,一、引言,二、线性规划模型,三、整数线性规划模型,四、0-1整数规划模型,五、非线性规划模型,六、多目标规划模型,七、动态规划模型,一、引言,我们从2005年“高教社杯”全国大学生数模竞,赛的B题“DVD在线租赁”问题的第二问和第三问,谈起.,其中第二个问题是一个如何来分配有限资源，,从而达到人们期望目标的优化分配数学模型. 它,在运筹学中处于中心的地位. 这类问题一般可以,归结为,数学规划模型.,规划模型的应用极其广泛，其作用已为越来,来越急速地渗透于工农业生产、商业活动、军事,行为核科学研究的各个方面，为社会节省的财富、,创造的价值无
2、法估量.,特别是在数模竞赛过程中，规划模型是最常,见的一类数学模型. 从92-06年全国大学生数模竞,越多的人所重视. 随着计算机的逐渐普及，它越,赛试题的解题方法统计结果来看，规划模型共出,现了15次，占到了50%，也就是说每两道竞赛题,中就有一道涉及到利用规划理论来分析、求解.,二、线性规划模型,线性规划模型是所有规划模型中最基本、最,例1 （食谱问题）设有 n 种食物，各含 m 种营养,素，第 j 种食物中第 i 中营养素的含量为 aij , n 种,食物价格分别为c1, c2, , cn，请确定食谱中n 种食,物的数量x1, x2, , xn，要求在食谱中 m 种营养素,简单的一种.,
3、2.1 线性规划模型的标准形式,的含量分别不低于b1, b2, , bm 的情况下，使得总,的费用最低.,首先根据食物数量及价格可写出食谱费用为,其次食谱中第 i 种营养素的含量为,因此上述问题可表述为：,解,上述食谱问题就是一个典型的线性规划问题，,寻求以线性函数的最大（小）值为目标的数学模型.,它是指在一组线性的等式或不等式的约束条件下，,线性规划模型的三种形式,系 数 矩 阵,目标函数 价值向量 价值系数 决策变量,右端向量, 一般形式, 规范形式, 标准形式,三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.,以下我们仅将一般形式化成规
4、范形式和标准形式.,目标函数的转化,约束条件和变量的转化,为了把一般形式的LP问题变换为规范形式，,可用下述两个不等式约束去替代,我们必须消除等式约束和符号无限制变量. 在一,般形式的LP中，一个等式约束,这样就把一般形式的LP变换为规范形式.,变量 和 ，并设,对于一个无符号限制变量 ，引进两个非负,对于一个不等式约束,代替上述的不等式约束.,对符号无限制变量的处理可按上述方法进行.,可引入一个剩余变量 ，,必须消除其不等式约束和符号无限制变量.,为了把一般形式的LP问题变换为标准形式，,对于不等式约束,代替上述的不等式约束.,这样就把一般形式的LP变换为标准形式.,针对标准形式的线性规划问
5、题，其解的理论,分析已经很完备，在此基础上也提出了很好的算,单纯形方法是线性规划问题的最为基础、也,法单纯形方法及其相应的变化形式（两阶段,2.2 线性规划模型的求解,法，对偶单纯形法等）.,是最核心的算法. 它是一个迭代算法，先从一个,特殊的可行解（极点）出发，通过判别条件去判,断该可行解是否为最优解（或问题无界），若不,是最优解，则根据相应规则，迭代到下一个更好,的软件包有LINGO和LINDO.,的可行解（极点），直到最优解（或问题无界）.,关于线性规划问题解的理论和单纯形法具体的求,解过程可参见文献1.,然后在实际应用中，特别是数学建模过程中，,遇到线性规划问题的求解，我们一般都是利用
6、现,有的软件进行求解，此时通常并不要求线性规划,问题是标准形式. 比较常用的求解线性规划模型,运输问题,例2 设要从甲地调出物资2000吨，从乙地调出物,资1100吨，分别供给A地1700吨、B地1100吨、C,假定运费与运量成正比. 在这种情况下，采用不,地200吨、D地100吨. 已知每吨运费如表1.1所示.,同的调拨计划，运费就可能不一样. 现在问：怎,样才能找出一个运费最省的调拨计划？,解,一般的运输问题可以表述如下：,在满足供需要求的条件下，使总运输费用最省.,数学模型：,类似与将一般的线性规划问题转化为其标准,否则，称为不平衡的运输问题，包括：,总产量总销量和总产量总销量.,形式，
7、我们总可以通过引入假想的销地或产地，,将不平衡的运输问题转化为平衡的运输问题. 从,而，我们的重点就是解决平衡运输问题的求解.,若其中各产地的总产量等于各销地的总销量，,该方法将单纯形法与平衡的运输问题的特殊性质,运输问题及其解法的进一步介绍参加文献2.,显然，运输问题是一个标准的线性规划问题，,因而当然可以运用单纯形方法求解.但由于平衡,的运输问题的特殊性质，它还可以用其它的一些,特殊方法求解，其中最常用的就是表上作业法，,结合起来，很方便地实行了运输问题的求解.关于,对于线性规划问题，如果要求其决策变量取,整数值，则称该问题为整数线性规划问题.,平面法和分支定界法是两种常用的求解整数线性,
8、对于整数线性规划问题的求解，其难度和运,三、整数线性规划模型,算量远大于同规模的线性规划问题. Gomory割,规划问题的方法（见文献1）. 此外，同线性规,划模型一样，我们也可以运用LINGO和LINDO软,件包来求解整数线性规划模型.,如何求解整数线性规划模型.,以1988年美国大学生数学建模竞赛B题为例，,说明整数线性规划模型的建立及用LINGO软件包,例3 有七种规格的包装箱要装到两节铁路平板车,上去. 包装箱的宽和高是一样的，但厚度（t，以,cm 计）及重量（w，以kg计）是不同的. 表1给出,了每种包装箱的厚度、重量以及数量. 每节平板,车有10.2 m 长的地方可用来装包装箱（像
9、面包片,那样），载重为40t. 由于当地货运的限制，对于,C5, C6, C7 类包装箱的总数有一个特别的限制：这,类箱子所占的空间（厚度）不能超过302.7cm. 试,把包装箱装到平板车上，使得浪费的空间最小.,下面我们建立该问题的整数线性规划模型.,1) 约束条件,两节车的装箱数不能超过需要装的件数，即：,每节车可装的长度不能超过车能提供的长度：,每节车可装的重量不超过车能够承受的重量：,对于C5, C6, C7类包装箱的总数的特别限制：,2) 目标函数,浪费的空间最小，即包装箱的总厚度最大：,3) 整数线性规划模型,4) 模型求解,运用LINGO软件求解得到：,5) 最优解的分析说明,优
10、的装车方案，此时装箱的总长度为1019.7cm，,两节车共装箱的总长度为2039.4cm.,但是，上述求解结果只是其中一种最优的装,车方案，即此答案并不唯一.,0-1整数规划是整数规划的特殊情形，它要求,线性规划模型中的决策变量 xij 只能取值为0或1.,单隐枚举法，该方法是一种基于判断条件（过滤,0-1整数规划模型的求解目前并没有非常好的,四、0-1整数规划模型,算法，对于变量比较少的情形，我们可以采取简,条件）的穷举法.,我们也可以利用LINGO和LINDO软件包来求,解0-1整数规划模型.,例4 有 n 个物品，编号为 1, 2, , n，第 i 件物品,重 ai 千克，价值为 ci
11、元，现有一个载重量不超过,大，应如何装载这些物品？,a 千克的背包，为了使装入背包的物品总价值最,用变量 xi 表示物品 i 是否装包，i =1, 2, , n，,并令：,解,可得到背包问题的规划模型为：,例5 有n 项任务，由 n 个人来完成，每个人只能,做一件， 第 i 个人完成第 j 项任务要 cij 小时，如,何合理安排时间才能使总用时最小？,引入状态变量 xij ，并令：,解,则总用时表达式为：,可得到指派问题的规划模型为：,上面介绍的指派问题称为指派问题的标准形,式，还有许多其它的诸如人数与任务数不等、及,但一般可以通过一些转化，将其变为标准形式.,某人可以完成多个任务，某人不可以
12、完成任务，,某任务必须由某人完成等特殊要求的指派问题.,对于标准形式的指派问题，我们可以利用匈,牙利算法实现求解. 它将指派问题中的系数构成,一个矩阵，利用矩阵上简单的行和列变换，结合,解的判定条件，实现求解（见文献2）.,DVD在线租赁第二个问题的求解,问题二的分析,尽量小，会员满意度最大.,经营成本和会员的满意度是被考虑的两个相互,制约的重要因素.在忽略邮寄成本的前提下，经营,成本主要体现为DVD的数量. 我们主要考虑在会员,向网站提供需求信息，且满足一定要求的前提下，,对给定数量DVD进行分配决策，使得DVD的数量,DVD，否则不进行租赁.,没有预定的DVD对其满意度的贡献为0.,假设按
13、照公历月份进行的租赁业务，即会员,无论两次租赁还是一次租赁，必须在当月内完成,DVD的租与还. 同时假设网站对其会员进行一次,租赁业务时，只能向其提供3张该会员已经预定的,经观察，可以认为在线订单中每个会员的预定,DVD的表示偏好程度的数字反映了会员对所预定,不同DVD的满意程度，且当会员租到其预定排序,为1，2，3的三张DVD时，满意度达到100%. 会员,利用层次分析法，对此满意指数的合理性进,行了简单分析.,进行求解.,该问题要求根据现有的100种DVD的数量和,当前需要处理的1000位会员的在线订单，制定分,配策略，使得会员达到最大的满意度. 因而我们,认为只需对这些DVD进行一次性分
14、配，使得会员,的总体满意度达到最大.为此考虑建立优化模型，,问题二的模型及求解,又根据假设，网站只向会员提供其预定的DVD，,进行分配. 故引入约束,进一步，对每个会员每次租赁只能获得3张其,预定的DVD或不能得到，有,在上述约束的前提下，我们追求会员的总体,会员的最大满意指数为10+9+827，1000个,为了更好地表示满意度，我们将目标转化为,满意指数和 达到最大，显然每个,会员最大的满意指数和为,用百分数表示的满意度为：,，,由此，可得问题二的0-1整数线性规划模型如下：,配方案（见表3）.,会员全都得到了3张预定的DVD.,根据所得的0-1整数线性规划模型，利用,LINGO软件进行求解
15、，我们得到了一组最优分,该组最优解其目标函数会员总体最大满意,度为91.56%，只有6人未成功租赁（如：前30,名会员中C0008被分配到DVD），其余994个,五、非线性规划模型,即非线性规划问题.,前面介绍了线性规划问题，即目标函数和约束条,件都是线性函数的规划问题，但在实际工作中，还,常常会遇到另一类更一般的规划问题，即目标函数,和约束条件中至少有一个是非线性函数的规划问题，,事实上，客观世界中的问题许多是非线性,的，给予线性大多是近似的，是在作了科学,的假设和简化后得到的. 为了利用线性的,知识，许多非线性问题常进行线性化处理.,但在实际问题中，有一些是不能进行线性化,处理的，否则将严
16、重影响模型对实际问题,近似的可依赖型.,由于非线性规划问题在计算上常是困难的，,理论上的讨论也不能像线性规划那样给出简洁,的结果形式和全面透彻的结论.这点又限制了非,线性规划的应用，所以，在数学建模时，要进,行认真的分析，对实际问题进行合理的假设、,简化，首先考虑用线性规划模型，若线性近似,误差较大时，则考虑用非线性规划.,非线性规划问题的标准形式为：,其中， 为 维欧式空间 中的向量，,中至少有一个是非线性函数.,非线性规划模型按约束条件可分为以下三类：, 等式约束非线性规划模型：, 无约束非线性规划模型：, 不等式约束非线性规划模型：,针对上述三类非线性规划模型，其常用求解的基,本思路可归纳如下：,（下降迭代法）寻找，该方法的基本步骤如下：,所以往往根据目标函数的特征采用搜索的方法,1) 无约束的非线性规划问题,止迭代，用 来近似问题的最优解，否则转至.,从 出发，沿方向 ,按某种方法确定步长 ,令 ，
