第一章 规划理论及模型.ppt

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 线性规划模型的求解,法，对偶单纯形法等）.,是最核心的算法。它是一个迭代算法，先从一个,特殊的可行解（极点）出发，通过判别条件去判,断该可行解是否为最优解（或问题无界），若不,是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献1.,然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标

6、准形式. 比较常用的求解线性规划模型的软件包有LINGO和LINDO.,运输问题,例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 长的地方可用来装包装箱（像面包片,那样），载重为40t. 由于当地

9、货运的限制，对于,C5, C6, C7 类包装箱的总数有一个特别的限制：这,类箱子所占的空间（厚度）不能超过302.7cm. 试,把包装箱装到平板车上，使得浪费的空间最小.,下面我们建立该问题的整数线性规划模型。,1) 约束条件,两节车的装箱数不能超过需要装的件数，即：,每节车可装的长度不能超过车能提供的长度：,每节车可装的重量不超过车能够承受的重量：,对于C5, C6, C7类包装箱的总数的特别限制：,2) 目标函数,浪费的空间最小，即包装箱的总厚度最大：,3) 整数线性规划模型,4) 模型求解,运用LINGO软件求解得到：,5) 最优解的分析说明,优的装车方案，此时装箱的总长度为1019.

10、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的租与还. 同时假设网站对其会员进

13、行一次租赁业务时，只能向其提供3张该会员已经预定的DVD，否则不进行租赁.,经观察，可以认为在线订单中每个会员的预定DVD的表示偏好程度的数字反映了会员对所预定不同DVD的满意程度，且当会员租到其预定排序为1，2，3的三张DVD时，满意度达到100% .会员没有预定的DVD对其满意度的贡献为0 .,利用层次分析法，对此满意指数的合理性进,行了简单分析.,该问题要求根据现有的100种DVD的数量和当前需要处理的1000位会员的在线订单，制定分配策略，使得会员达到最大的满意度. 因而我们认为只需对这些DVD进行一次性分配，使得会员的总体满意度达到最大. 为此考虑建立优化模型，进行求解.,问题二的模

14、型及求解,经营成本和会员的满意度是被考虑的两个相互制约的重要因素. 在忽略邮寄成本的前提下，经营成本主要体现为DVD的数量. 我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量尽量小，会员满意度最大.,由此，可得问题二的0-1整数线性规划模型如下：,根据所得的0-1整数线性规划模型，利用LINGO软件进行求解，我们得到了一组最优 分配方案.,该组最优解其目标函数会员总体最大满意度为91.56%，只有6人未成功租赁（如：前30名会员中C0008被分配到DVD），其余994个会员全都得到了3张预定的DVD .,五、非线性规划模型,前面介绍了

15、线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，其中目标函数和约束条件至少有一个是非线性函数的规划问题，即非线性规划问题.,事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型.,由于非线性规划问题在计算上常是困难的，理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论. 这点又限制了非线性规划的应用，所以，在数学建模时，要进行认真的

16、分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划.,非线性规划问题的标准形式为：,非线性规划模型按约束条件可分为以下三类：, 等式约束非线性规划模型：, 无约束非线性规划模型：, 不等式约束非线性规划模型：,1) 无约束的非线性规划问题.,针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下：,( 表示函数的梯度）求出最优解 ，,但求解 往往是很困难的.,若目标函数,的形式简单，可以通过求解方程,（下降迭代法）寻找，该方法的基本步骤如下：,所以往往根据目标函数的特征采用搜索的方法,检验 是否满足停止迭代的条件，如是，则停 止迭代，用

17、来近似问题的最优解，否则转至.,从 出发，沿方向 ，按某种方法确定步长 ，使得：,令 ，然后置 ，返回,在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素. 非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，一,维搜索方法主要有进退法和黄金分割法. 二维的非线性规划也可以像解线性规划那样用图形求解. 对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.,2) 只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解.,3) 具有不等式约束的非线性规划问题解起来很复杂

18、，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线性规划问题.,下面介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解.,例7 （石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间.但要求存储的石油能满足客户的要求.为简化问题，假设只经营两种油，各种符号表示的意义如表4所示.其中供给率指石油公司供给客户的速度.,表4 各种符号表示意义表,由历史数据得到的经验公式为 :,且提供数据如表5所示：,表5 数据表,已知总存储空间,代入数据后得到的模型为：,模型求解：

19、拉格朗日函数的形式为：,即:,对 求各个变量的偏导数，并令它们等于零，得:,解这个线性方程组得：,从而可得最小值是12.71 .,表示当约束条件右边的值增大一个单位后，相应目标函数值的增加值。比如说：如总存储空间由24变为25时，最优值会由12.71变为,六、多目标规划模型,在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产计划的例子.,能耗不得超过160t标准煤其它数据如下表：,问每周应生产三种布料各多少m，才能使该厂,的利润最高，而能源消耗最少？,，该厂两

20、班生产，每周生产时间为80h，,例8 （生产计划问题）某厂生产三种布料,（t标准煤），其中 ，,则上述问题的数学模型为,其中， ， .,有,显然这是一个多目标线性规划问题. 一般的多目标规划问题都可写成如下的形式：,多目标规划问题的解法大致可分为两类：直接解法和间接解法. 到目前为止，常用的多为间接解法，即根据问题的实际背景和特征，设法将多目标优化问题转化为单目标优化问题，从而得到满意解的方法.,许解.多目标规划问题与前面讲的规划问题的主要区别在于：目标函数不止一个，而是p个（ ）.,称为多目标规划问题的可行集或容许集， 称为可行解或容,在多目标优化问题中，若能从p个目标中，确定一个目标为主要

21、目标，例如 ，,主要目标法,而把其余目标作为次要目标，并根据实际情况，确定适当的界限值，这样就可以把次要目标作为约束来处理，而将多目标优化问题转化为求解如下的线性或非线性规划问题：,把多目标规划问题中的p个目标按其重要程度排一个次序，假设 最重要， 次之，,令 ，其中界限值取为 ，,再次之，L，最后一个目标 .,先求出以第一个目标 为目标函数而原问题,则此非线性规划问题得最优解必为原问题的弱有效解.因此，用主要目标法求得的解必是多目标优化问题的弱有效解或有效解.,2）分层序列法,变的问题 ：,的最优解 及最优值 ，再求问题 ：,的最优解 及最优值 ，即 ，,其中：,为问题 的可行域.,再求解问

22、题 ：,得最优解 及最优值 ，L，如此继续下去，,直到求出第p个问题 ：,得最优解 及最优值 ，则 就是,原多目标规划问题在分层序列意义下得最优解，,为其最优值.,，其最优解是唯一的，则问题 的最优解,也是唯一的，且 。因此常将分层,序列法修改如下：选取一组适当的小正数,，成为宽容值，把上述的问题 修改如下：,再按上述方法依次求解各问题 .,容易看出，在使用分层序列法时，若对某个问题p,.,对多目标规划问题中的p个目标按期重要程度给以适当的权系数 ，且,，然后用 作为新的目,得最优解 ，取 作为多目标规划问题的解.,3）线性加权求和法,标函数，成为评价（目标）函数，再求解问题,在一定条件下，用

23、线性加权求和法求得的最优解必是原多目标规划问题的有效解或弱有效解.,例9求解引言中DVD在线租赁的第三个问题.,下面以引言中2005年全国大学生数模竞赛 “DVD在线租赁”问题第三问为例，介绍多目标线性规划模型以及利用主要目标法求解该模型.,此问是在现有的在线订单基础上，为满足一个月内95%的会员得到他想看的DVD，我们进行购买量预算和分配决策，使得会员的满意度最大. 预算购买量的目的是在尽可能地减少DVD购买量的前提下，满足要求，进行合理分配使得会员的满意度最大.,问题三的分析,我们假设会员得到他想看的DVD就是指：会员租赁到了他预定的DVD中的三张；且假设会员每次租赁前都需要提交新的在线订

24、单. 此问中要求在一个月内进行分配，因而存在部分DVD的两,次被租赁，但因为是处理同一份订单，因而存在会员的第二次租赁.,基于这个假设，为了最小化购买量，我们在允许当前某些会员无法被满足租赁要求，让其等待，利用部分会员还回的DVD对其进行租赁.,根据问题一，我们认为，一个月中每张DVD有0.6的概率被租赁两次，0.4的概率被租赁一次.即在二次租赁的情况下，每张DVD相当于发挥了 张DVD的作用.,由此，在问题二建立的0-1整数规划模型的,求，考虑DVD可能的两次分配，进一步追求DVD,基础上，满足95%的会员得到他想看DVD的要,进行求解.,总的购买数量最小. 建立双目标整数规划模型,设 表示

25、第j种DVD需要的购买量.对每种DVD，,问题三的模型,要求分配的总量不超过相应的现有数量的1.6倍. 即:,为了让95%的会员可以得到他想看的3张DVD，即:,我们希望购买DVD的总数量最小，即 :,由此，可以得到问题三的双目标整数线性规划 模型如下：,对于该双目标整数线性规划模型，我们引入总体满意度水平 （即最小的满意度）,将其满意度的目标转换为约束，如下：,问题三的求解与检验,利用Lingo软件，调整总体满意度水平 进行,求解。实际计算中，如果要求 为整,数，无法求得可行解，因而我们取消了其整数 约束进行计算。求得解 后，对其,进行取整。当 时，我们解得DVD总的最小,购买量 ，其中第j

26、种DVD需要的购买,量 如下表：,表6 当 时最小购买量的 值,续上表,我们利用规划模型求得每种DVD的购买量后，,需要对其进行可行性校验，测试此结果是否可以,且具有尽可能大的总体满意度.,满足一个月内比例为95%的会员得到他想看DVD，,校验方法：,（一）根据订单和求得的DVD购买数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配.,（二）随机从第一次得到DVD的会员中抽取60%，将这部分人所还回的DVD与第一次分配余下的DVD合在一起，作为第二次分配时各种

27、DVD的现有量.然后，利用问题二的0-1线性规划模型对第一次未分配到DVD的会员进行第二次分配；,（三）统计出经过两次分配后，得到DVD的会,得到DVD的会员大于95%，则认为模型三是合理的.,种算法进行多次随机模拟，若大多数情况下可以使,员的比例，若大于95%，则此次分配成功.利用这,校验结果：,因为每次检验需时约1小时，我们只对问题三,表7 7次模拟结果每次的观看比例列表,观看比例大于95%）.下面给出7次模拟得到的观,求得的结果进行了7次模拟，其中6次符合要求（,看比例（表7）：,七、动态规划模型,过程中的最优控制问题.,动态规划所研究的对象是多阶段对策问题，,是在20世纪50年代初期由

28、美国数学家R.Bellman等,人提出的一类规划模型. 动态规划是现代管理领域,的一种重要的决策方法，其主要应用有最优路径,问题、资源分配问题、投资决策问题、生产计划,与库存问题、排序问题、货物装载问题以及生产,理多阶段决策问题的最优化原理.,效益的总和达到最优.,多阶段决策问题是指一类活动过程，它可分,为若干个相互联系的阶段，在每个阶段都需要做,出决策，这个决策不仅决定这一阶段的效益，而,定以后，就得到一个决策序列，称为策略. 多阶,段决策问题就是求一个策略，使各阶段的效益的,下面我们通过讲解一个最短路问题来引出处,且决定下一阶段的初始状态，每个阶段的决策确,例10 有一辆汽车要把货物从A城

29、运到E城，而,可供选择，选取怎样的路线才能使路程最短？,从A城到E城必须经过一些城市，整段路程可以,分为若干个阶段，而每个阶段又有若干个城市,假定从A城到E城的所有路线如下图所示：,图1 从A城到E城的路线,其中 B1,B2,C1,C2,D1,D2是可供选择的城市，途中的数字表示两城之间的距离（以10千米为单位）.,显然，这是一个多阶段决策问题：从A到E可以分为4个阶段. 从A点出发到B1或B2为第一阶段，这时有两个选择：走到B1或者走到B2. 若我们选择走到B1的决策，则B1就是下一个阶段的起点. 在下一阶段，我们从B1出发，有一个可供选择的决策集合C1,C2 ，很明显，前面各阶段的决策如何选择，,直接影响着其余各阶段的行进路线，我们的目的就是在各个阶段选择一个决策，使由它们决定的总路程最短.,下面我们来求此问题的最短路线，并以此来说明处理多阶段决策问题的最优化原理.先引入动态规划的基本概念.,令k表示由某点至终点之间的阶段数.例如从 A到E可以分为4个阶段，从B1到E是5个阶段；第k阶段的终点又是第k+1阶段的起点，记为Sk，,个阶段时所选择的一个决策；在各个阶段上 选择的决策组成的总体称为一个策略.,令xk(sk)为决策变量，它表示当处于状态时还有,称为状态变量或状态.某个阶段的所有可能状 态全体可用状态集合来描述.例如：S2=B