数学建模简明教程.pptx

《数学建模简明教程.pptx》由会员分享，可在线阅读，更多相关《数学建模简明教程.pptx（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章 规划理论及模型规划理论及模型一、一、引言引言二、线性规划模型二、线性规划模型三、整数线性规划模型三、整数线性规划模型四、四、0-10-1整数规划模型整数规划模型 五、五、非线性规划模型非线性规划模型六、六、多目标规划模型多目标规划模型目录下页返回上页结束七、动态七、动态规划模型规划模型第1页/共112页一、引言一、引言目录下页返回上页结束 我们从2005年“高教社杯”全国大学生数模竞赛的B题“DVD在线租赁”问题的第二问和第三问 谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在运筹学中处于中心的地位.这类问题一般可以归结为数学规划模型.第

2、2页/共112页目录下页返回上页结束 规划模型的应用极其广泛，其作用已为越来 来越急速地渗透于工农业生产、商业活动、军事 行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常 见的一类数学模型.从92-06年全国大学生数模竞 越多的人所重视.随着计算机的逐渐普及，它越 赛试题的解题方法统计结果来看，规划模型共出 现了15次，占到了50%，也就是说每两道竞赛题 中就有一道涉及到利用规划理论来分析、求解.第3页/共112页目录下页返回上页结束二、线性规划模型二、线性规划模型二、线性规划模型二、线性规划模型 线性规划模型是所有规划模型中最基本、最例例

3、1（食谱问题）设有 n 种食物，各含 m 种营养素，第 j 种食物中第 i 中营养素的含量为 aij,n 种食物价格分别为c1,c2,cn，请确定食谱中n 种食物的数量x1,x2,xn，要求在食谱中 m 种营养素简单的一种.2.1 线性规划模型的标准形式线性规划模型的标准形式 的含量分别不低于b1,b2,bm 的情况下，使得总 的费用最低.第4页/共112页目录下页返回上页结束 首先根据食物数量及价格可写出食谱费用为 其次食谱中第 i 种营养素的含量为 因此上述问题可表述为：解解第5页/共112页目录下页返回上页结束 上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的

4、数学模型.它是指在一组线性的等式或不等式的约束条件下，第6页/共112页目录下页返回上页结束 线性规划模型的三种形式线性规划模型的三种形式线性规划模型的三种形式线性规划模型的三种形式 系数矩阵目标函数 价值向量 价值系数 决策变量右端向量非负约束自由变量 一般形式一般形式第7页/共112页目录下页返回上页结束 规范形式规范形式 标准形式标准形式 三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.第8页/共112页目录下页返回上页结束目标函数的转化 xoz-z第9页/共112页目录下页返回上页结束约束条

5、件和变量的转化 为了把一般形式的LP问题变换为规范形式，可用下述两个不等式约束去替代 我们必须消除等式约束和符号无限制变量.在一 般形式的LP中，一个等式约束第10页/共112页目录下页返回上页结束这样就把一般形式的LP变换为规范形式.变量 和 ，并设 对于一个无符号限制变量 ，引进两个非负第11页/共112页目录下页返回上页结束对于一个不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行.可引入一个剩余变量 ，必须消除其不等式约束和符号无限制变量.为了把一般形式的LPLP问题变换为标准形式，第12页/共112页目录下页返回上页结束 对于不等式约束 代替上述的不等式约束.这样

6、就把一般形式的LP变换为标准形式.可引入一个松弛变量，用第13页/共112页目录下页返回上页结束 针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也法单纯形方法及其相应的变化形式（两阶段2.2 线性规划模型的求解线性规划模型的求解 法，对偶单纯形法等）.是最核心的算法.它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判 断该可行解是否为最优解（或问题无界），若不 第14页/共112页目录下页返回上页结束是最优解，则根据相应规则，迭代到下一个更好的软件包有LINGO和LINDO.的可行解（极点），直到最优解（

7、或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献1.然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现 有的软件进行求解，此时通常并不要求线性规划 问题是标准形式.比较常用的求解线性规划模型 第15页/共112页目录下页返回上页结束运输问题运输问题例例2 2 设要从甲地调出物资20002000吨，从乙地调出物 资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？第1

8、6页/共112页目录下页返回上页结束1572521甲15375151乙DCBA表 1.1销地运费产地第17页/共112页目录下页返回上页结束解解乙甲DCBA第18页/共112页目录下页返回上页结束第19页/共112页目录下页返回上页结束一般的运输问题可以表述如下：运一个单位的产品到 已知，从在满足供需要求的条件下，使总运输费用最省.个发点要把某种物资从 ，调运给需要这种物资的 个收点.的运价为现在需要确定一个调运方案，即确到的运输量定由第20页/共112页目录下页返回上页结束数学模型：第21页/共112页目录下页返回上页结束 类似与将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包

9、括：即，则称该问题为平衡的运输问题.总产量总销量和总产量总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题.从而，我们的重点就是解决平衡运输问题的求解.若其中各产地的总产量等于各销地的总销量，第22页/共112页目录下页返回上页结束该方法将单纯形法与平衡的运输问题的特殊性质运输问题及其解法的进一步介绍参加文献2.显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解.但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，结合起来，很方便地实行了运输问题的求解.关于第23页/共112页目录下页返回上页结

10、束 对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运三、整数线性规划模型三、整数线性规划模型算量远大于同规模的线性规划问题.Gomory割规划问题的方法（见文献1）.此外，同线性规划模型一样，我们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.第24页/共112页目录下页返回上页结束如何求解整数线性规划模型.以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包例例3 有七种规格的包装箱要装到两节铁路平板车上去.包装箱的宽和高是一样的，

11、但厚度（t，以cm 计）及重量（w，以kg计）是不同的.表1给出了每种包装箱的厚度、重量以及数量.每节平板车有10.2 m 长的地方可用来装包装箱（像面包片那样），载重为40t.由于当地货运的限制，对于第25页/共112页目录下页返回上页结束C5,C6,C7 类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm.试把包装箱装到平板车上，使得浪费的空间最小.种类种类C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg2000 3000 10005004000 2000 1000n/件件8796648第26页/共112页

12、目录下页返回上页结束 为在第 节车上装载第 件包装箱的解解 令种包装箱需要)；数量(为第 下面我们建立该问题的整数线性规划模型.节车的载重量；为第为特殊限制().).装的件数；为第种包装箱的重量；为第 种包装箱的厚度；为第 节车的长度()；第27页/共112页目录下页返回上页结束1)约束条件约束条件两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：每节车可装的重量不超过车能够承受的重量：第28页/共112页目录下页返回上页结束对于C5,C6,C7类包装箱的总数的特别限制：2)目标函数目标函数浪费的空间最小，即包装箱的总厚度最大：第29页/共112页目录下页返回上页

13、结束3)整数线性规划模型整数线性规划模型第30页/共112页目录下页返回上页结束4)模型求解模型求解运用LINGO软件求解得到：5)最优解的分析说明最优解的分析说明优的装车方案，此时装箱的总长度为1019.7cm，两节车共装箱的总长度为2039.4cm.由上一步中的求解结果可以看出，即为最 但是，上述求解结果只是其中一种最优的装车方案，即此答案并不唯一.第31页/共112页目录下页返回上页结束 0-1整数规划是整数规划的特殊情形，它要求线性规划模型中的决策变量 xij 只能取值为0或1.单隐枚举法，该方法是一种基于判断条件（过滤 0-1整数规划模型的求解目前并没有非常好的四、四、0-10-1整

14、数规划模型整数规划模型 算法，对于变量比较少的情形，我们可以采取简条件）的穷举法.我们也可以利用LINGO和LINDO软件包来求解0-1整数规划模型.第32页/共112页目录下页返回上页结束例例4 4 有 n 个物品，编号为 1,2,n，第 i 件物品重 ai 千克，价值为 ci 元，现有一个载重量不超过大，应如何装载这些物品？a 千克的背包，为了使装入背包的物品总价值最用变量 xi 表示物品 i 是否装包，i=1,2,n，并令：解解第33页/共112页目录下页返回上页结束可得到背包问题的规划模型为：第34页/共112页目录下页返回上页结束例例5 5 有n 项任务，由 n 个人来完成，每个人只

15、能做一件，第 i 个人完成第 j 项任务要 cij 小时，如何合理安排时间才能使总用时最小？引入状态变量 xij，并令：解解则总用时表达式为：第35页/共112页目录下页返回上页结束可得到指派问题的规划模型为：第36页/共112页目录下页返回上页结束 上面介绍的指派问题称为指派问题的标准形式，还有许多其它的诸如人数与任务数不等、及但一般可以通过一些转化，将其变为标准形式.某人可以完成多个任务，某人不可以完成任务，某任务必须由某人完成等特殊要求的指派问题.对于标准形式的指派问题，我们可以利用匈牙利算法实现求解.它将指派问题中的系数构成一个矩阵，利用矩阵上简单的行和列变换，结合 解的判定条件，实现

16、求解（见文献2）.第37页/共112页目录下页返回上页结束DVDDVD在线租赁第二个问题的求解在线租赁第二个问题的求解问题二的分析问题二的分析尽量小，会员满意度最大.经营成本和会员的满意度是被考虑的两个相互制约的重要因素.在忽略邮寄成本的前提下，经营成本主要体现为DVD的数量.我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量第38页/共112页目录下页返回上页结束DVD，否则不进行租赁.没有预定的DVD对其满意度的贡献为0.假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成DVD的租与还.同时假设网站对其

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

18、如下：我们定义.即不超过相应的现有数量个会员对第表示第令种DVD问题二的模型及求解问题二的模型及求解的满意指数矩阵.表示第 j 种DVD的现有数量.显然，对每种DVD,要求分配的总量第41页/共112页目录下页返回上页结束又根据假设，网站只向会员提供其预定的DVDDVD，进行分配.故引入约束进一步，对每个会员每次租赁只能获得3 3张其不为0时，才可能进行即只有当满意指数预定的DVD或不能得到，有第42页/共112页目录下页返回上页结束在上述约束的前提下，我们追求会员的总体会员的最大满意指数为10+9+827，1000个为了更好地表示满意度，我们将目标转化为满意指数和 达到最大，显然每个会员最大

19、的满意指数和为用百分数表示的满意度为：，第43页/共112页目录下页返回上页结束由此，可得问题二的0-1整数线性规划模型如下：第44页/共112页目录下页返回上页结束配方案（见表3）.会员全都得到了3张预定的DVD.根据所得的0-1整数线性规划模型，利用LINGO软件进行求解，我们得到了一组最优分该组最优解其目标函数会员总体最大满意度为91.56%，只有6人未成功租赁（如：前30名会员中C0008被分配到DVD），其余994个第45页/共112页目录下页返回上页结束五、非线性规划模型五、非线性规划模型五、非线性规划模型五、非线性规划模型即非线性规划问题.前面介绍了线性规划问题，即目标函数和约束

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

21、学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划.第48页/共112页目录下页返回上页结束非线性规划问题的标准形式为：非线性规划问题的标准形式为：其中，为 维欧式空间 中的向量，为目标函数，为约束条件.且中至少有一个是非线性函数.第49页/共112页目录下页返回上页结束非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类：等式约束非线性规划模型等式约束非线性规划模型：无约束非线性规划模型：第50页/共112页目录下页返回上页结束 不等式约束非线性规划模型：不等式约束非线性规划模型：针对上述三类

22、非线性规划模型，其常用求解的基本思路可归纳如下：第51页/共112页目录下页返回上页结束但求解 往往是很困难的.求出最优解 ，（下降迭代法）寻找，该方法的基本步骤如下：所以往往根据目标函数的特征采用搜索的方法1)无约束的非线性规划问题无约束的非线性规划问题若目标函数的形式简单，可以通过求解方程(表示函数的梯度）第52页/共112页目录下页返回上页结束止迭代，用 来近似问题的最优解，否则转至.从 出发，沿方向 ,按某种方法确定步长 ,令 ，然后置 ，返回适当选取初始点，令按某种规则确定处的搜索方向.使得：检验 是否满足停止迭代的条件，如是，则停第53页/共112页目录下页返回上页结束线性规划可以

23、用一维搜索方法求得最优解，一维搜最常用的搜索方法就是最速下降法.在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素.非线性规划只含一个变量，即一维非索方法主要有进退法和黄金分割法.二维的非线性规划也可以像解线性规划那样用图形求解.对于二维非线性规划，使用搜索方法是要用到梯度的概念，第54页/共112页目录下页返回上页结束约束问题求解.近的方法将非线性规划问题化为线性规划问题.2)2)只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无3)3)具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束

24、，再将约束问题化为无约束问题，用线性逼第55页/共112页规划问题可用拉格朗日方法求解.下面介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线性第56页/共112页目录下页返回上页结束客户的速度.例例7 7 （石油最优储存方法）有一石油运输公（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间.但要求存储的石油能满足客户的要求.为简化问题，假设只经营两种油，各种符号表示的意义如表4 4所示.其中供给率指石油公司供给第57页/共112页目录下页返回上页结束表表4 4 各种符号表示意义表各种符号表示意义表第第i种油的存储量种油的存储量第第i种油的价格种

25、油的价格第第i种油的供给率种油的供给率第第i种油的每单位的存储费用种油的每单位的存储费用第第i种油的每单位的存储空间种油的每单位的存储空间总存储公式总存储公式第58页/共112页目录下页返回上页结束由历史数据得到的经验公式为 :且提供数据如表5 5所示：第59页/共112页目录下页返回上页结束表5 数据表已知总存储空间石油的石油的种类种类1930.5022450.24第60页/共112页目录下页返回上页结束代入数据后得到的模型为：拉格朗日函数的形式为：模型求解：第61页/共112页目录下页返回上页结束即即:对 求各个变量的偏导数，并令它们等于零，得:第62页/共112页目录下页返回上页结束 解

26、这个线性方程组得：解这个线性方程组得：从而可得最小值是12.71.间由24变为25时，最优值会由12.71变为表示当约束条件右边的值增大一个单位后，相应目标函数值的增加值。比如说：如总存储空第63页/共112页目录下页返回上页结束六、多目标规划模型六、多目标规划模型六、多目标规划模型六、多目标规划模型 许多实际问题中，衡量一个方案的好坏标准往往不止一个.例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产计划的例子.第64页/共112页目录下页返回上页结束能耗不得超过160t标准煤其它数据如下表：布料布料生产数量生产数

27、量（m/h）利润利润（元（元/m）最大销售量最大销售量（m/周）周）能耗能耗（t/km）A14004000.150.1540000400001.21.2A25105100.130.1351000510001.31.3A33603600.200.2030000300001.41.4问每周应生产三种布料各多少m，才能使该厂的利润最高，而能源消耗最少？，该厂两班生产，每周生产时间为80h，例例8 8 （生产计划问题）某厂生产三种布料第65页/共112页目录下页返回上页结束解解 设该厂每周生产布料 的小时数为 ，总利润为 （元），总能耗为（t标准煤），其中 ，则上述问题的数学模型为第66页/共112页

28、目录下页返回上页结束其中，.有显然这是一个多目标线性规划问题.一般的多目 标规划问题都可写成如下的形式：第67页/共112页目录下页返回上页结束从而得到满意解的方法.主要区别在于：目标函数不止一个，而是p 个（）.问题的可行集或容许集，称为可行解或容 称为多目标规划许解.多目标规划问题与前面讲的规划问题的多目标规划问题的解法大致可分为两类：直接解法和间接解法.到目前为止，常用的多为间接解法，即根据问题的实际背景和特征，设法将多目标优化问题转化为单目标优化问题，第68页/共112页目录下页返回上页结束一个目标为主要目标，例如 ，而把其余目1)主要目标法主要目标法线性规划问题：多目标优化问题中，若

29、能从p 个目标中，确定标作为次要目标，并根据实际情况，确定适当的界限值，这样就可以把次要目标作为约束来处理，而将多目标优化问题转化为求解如下的线性或非第69页/共112页目录下页返回上页结束其中界限值取为 ，则目标优化问题的弱有效解或有效解.令此非线性规划问题得最优解必为原问题的弱有效解.因此，用主要目标法求得的解必是多第70页/共112页目录下页返回上页结束排一个次序，假设 最重要，次之，再次之，最后一个目标 .先求出以第一个目标 为目标函数，而原2)2)分层序列法把多目标规划问题中的p 个目标按其重要程度问题中的约束条件不变的问题 ：第71页/共112页目录下页返回上页结束的最优解 及最优

30、值 ，再求问题 ：的最优解 及最优值 ，即 ，其中：为问题的可行域.第72页/共112页目录下页返回上页结束再求解问题 ：得最优解 及最优值 ，如此继续下去，直到求出第p 个问题 ：原多目标规划问题在分层序列意义下得最优解，为其最优值.得最优解 及最优值 ，则 就是第73页/共112页目录下页返回上页结束P,其最优解是唯一的，则问题 的最优解也是唯一的，且 。因此常将分层序列法修改如下：选取一组适当的小正数成为宽容值，把上述的问题 修改如下：再按上述方法依次求解各问题 .容易看出，在使用分层序列法时，若对某个问题.第74页/共112页目录下页返回上页结束3）线性加权求和法）线性加权求和法程度给

31、以适当的权系数 ，且 ，然后用 作为新的目标得最优解 ，取 作为多目标规划函数，成为评价（目标）函数，再求解问题对多目标规划问题中的p p个目标按期重要问题的解.第75页/共112页目录下页返回上页结束优解必是原多目标规划问题的有效解或弱有效解.例例9 求解引言中求解引言中DVDDVD在线租赁的第三个问题在线租赁的第三个问题.性规划模型以及利用主要目标法求解该模型.在一定条件下，用线性加权求和法求得的最下面以引言中20052005年全国大学生数模竞赛 “DVDDVD在线租赁”问题第三问为例，介绍多目标线第76页/共112页目录下页返回上页结束得会员的满意度最大.问题三的分析此问是在现有的在线订

32、单基础上，满足一个月内95%的会员得到他预订的DVD，我们进行购买量预算和分配决策，使得会员的满意度最大.预算购买量的目的是在尽可能地减少DVD购买量的前提下，满足要求，进行合理分配使第77页/共112页在一个月内进行分配，因而存在部分DVD的两次员的第二次租赁.我们假设会员得到他想看的DVD就是指：会员租赁到了他预定的DVD中的三张；且假设会员每次租赁前都需要提交新的在线订单.此问中要求被租赁，但因为是处理同一份订单，因而存在会第78页/共112页目录下页返回上页结束了 张DVD的作用.基于这个假设，为了最小化购买量，我们在允许当前某些会员无法被满足租赁要求，让其等待，利用部分会员还回的DV

33、D对其进行租赁.根据问题一，我们认为，一个月中每张DVD有0.6的概率被租赁两次，0.4的概率被租赁一次.即在二次租赁的情况下，每张DVD相当于发挥第79页/共112页目录下页返回上页结束由此，在问题二建立的0-1整数规划模型的求，考虑DVD可能的两次分配，进一步追求DVD基础上，满足95%的会员得到他想看DVD的要进行求解.总的购买数量最小.建立双目标整数规划模型第80页/共112页目录下页返回上页结束设 表示第j种DVD需要的购买量.对每种DVD，问题三的模型问题三的模型要求分配的总量不超过相应的现有数量的1.61.6倍.即:为了让95%的会员可以得到他想看的3张DVD，即:第81页/共1

34、12页目录下页返回上页结束我们希望购买我们希望购买DVDDVD的总数量最小，即的总数量最小，即 :由此，可以得到问题三的双目标整数线性规划模型如下：第82页/共112页目录下页返回上页结束第83页/共112页目录下页返回上页结束总体满意度水平 （即最小的满意度）将其满意度的目标转换为约束，如下：问题三的求解与检验 对于该双目标整数线性规划模型，我们引入第84页/共112页目录下页返回上页结束第85页/共112页目录下页返回上页结束利用Lingo软件，调整总体满意度水平 进行求解。实际计算中，如果要求 为整约束进行计算。求得解 后，对其进行取整。当 时，我们解得DVD总的最小购买量 ，其中第j种

35、DVD需要的购买量 如下表：数，无法求得可行解，因而我们取消了其整数 第86页/共112页表表6 6 6 6 当当 时最小购买量的时最小购买量的 值值目录下页返回上页结束DVDDVD编号编号D01D01D02D02D03D03D04D04D05D05D06D06D07D07D08D08D09D09D10D10最少购买量最少购买量1414212117172424121217171919212122221414DVDDVD编号编号D11D11D12D12D13D13D14D14D15D15D16D16D17D17D18D18D19D19D20D20最少购买量最少购买量181818181717171

36、7171724241818161618182323DVDDVD编号编号D21D21D22D22D23D23D24D24D25D25D26D26D27D27D28D28D29D29D30D30最少购买量最少购买量2020181822221414181817171515121216162424DVDDVD编号编号D31D31D32D32D33D33D34D34D35D35D36D36D37D37D38D38D39D39D40D40最少购买量最少购买量1919222220201919222222221313171717171717DVDDVD编号编号D41D41D42D42D43D43D44D44D

37、45D45D46D46D47D47D48D48D49D49D50D50最少购买量最少购买量3232202016162121222216162020151520202020第87页/共112页目录下页返回上页结束 续上表续上表DVDDVD编号编号D51D51D52D52D53D53D54D54D55D55D56D56D57D57D58D58D59D59D60D60最少购买量最少购买量2424171719191717191918181919171720202121DVDDVD编号编号D61D61D62D62D63D63D64D64D65D65D66D66D67D67D68D68D69D69D70D

38、70最少购买量最少购买量1616191919192020171719191717212120201919DVDDVD编号编号D71D71D72D72D73D73D74D74D75D75D76D76D77D77D78D78D79D79D80D80最少购买量最少购买量2121222215152020151514141212171719191717DVDDVD编号编号D81D81D82D82D83D83D84D84D85D85D86D86D87D87D88D88D89D89D90D90最少购买量最少购买量1818101014141212212113132222151513131717DVDDVD编号

39、编号D91D91D92D92D93D93D94D94D95D95D96D96D97D97D98D98D99D99D100D100最少购买量最少购买量2424171715151414252515152222202011112222第88页/共112页目录下页返回上页结束 我们利用规划模型求得每种DVD的购买量后，需要对其进行可行性校验，测试此结果是否可以且具有尽可能大的总体满意度.满足一个月内比例为95%的会员得到他想看DVD，第89页/共112页目录下页返回上页结束校验方法：校验方法：校验方法：校验方法：（一）（一）根据订单和求得的根据订单和求得的DVD购买数量，利用问题购买数量，利用问题二的

40、规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0 0，即不考虑对其进行第二次分配.第90页/共112页第一次未分配到DVD的会员进行第二次分配；（二）随机从第一次得到DVD的会员中抽取60%，将这部分人所还回的DVD与第一次分配余下的DVD合在一起，作为第二次分配时各种DVD的现有量.然后，利用问题二的0-1线性规划模型对第91页/共112页目录下页返回上页结束 （三）（三）统计出经过两次分配后，得到DVD的会员使得到DVD的会员大于95%，则认为模型三是合种算法进行多次随机模拟，若大多数情况下可以的比

41、例，若大于95%，则此次分配成功.利用这理的.第92页/共112页目录下页返回上页结束校验结果：校验结果：校验结果：校验结果：因为每次检验需时约1 1小时，我们只对问题三表7 7次模拟结果每次的观看比例列表验证次数验证次数1234567观看比例观看比例 95.8 96.6 93.4 95.3 95.9 96.1 95.7观看比例大于95%）.下面给出7 7次模拟得到的观求得的结果进行了7次模拟，其中6次符合要求（看比例（表7）：第93页/共112页目录下页返回上页结束七、动态规划模型七、动态规划模型过程中的最优控制问题.动态规划所研究的对象是多阶段对策问题，是在20世纪50年代初期由美国数学家

42、R.Bellman等人提出的一类规划模型.动态规划是现代管理领域的一种重要的决策方法，其主要应用有最优路径问题、资源分配问题、投资决策问题、生产计划与库存问题、排序问题、货物装载问题以及生产第94页/共112页目录下页返回上页结束理多阶段决策问题的最优化原理.效益的总和达到最优.多阶段决策问题是指一类活动过程，它可分为若干个相互联系的阶段，在每个阶段都需要做出决策，这个决策不仅决定这一阶段的效益，而定以后，就得到一个决策序列，称为策略.多阶段决策问题就是求一个策略，使各阶段的效益的下面我们通过讲解一个最短路问题来引出处且决定下一阶段的初始状态，每个阶段的决策确第95页/共112页目录下页返回上

43、页结束例10 有一辆汽车要把货物从A城运到E城，而可供选择，选取怎样的路线才能使路程最短？从A城到E城必须经过一些城市，整段路程可以分为若干个阶段，而每个阶段又有若干个城市假定从A城到E城的所有路线如下图所示：第96页/共112页目录下页返回上页结束图1 从A城到E城的路线561327424146途中的数字表示两城之间的距离（以10千米为其中 B1,B2,C1,C2,D1,D2是可供选择的城市，单位）.第97页/共112页目录下页返回上页结束很明显，前面各阶段的决策如何选择，直接影响着段选择一个决策，使由它们决定的总路程最短.显然，这是一个多阶段决策问题：从A A到E E可以分为4个阶段.从A

44、点出发到B1或B2为第一阶段，这时有两个选择：走到B1或者走到B2.若我们选择走到B1的决策，则B1就是下一个阶段的起点.在下一阶段，我们从B1出发，有一个可供选择的决策集合C1,C2，其余各阶段的行进路线，我们的目的就是在各个阶第98页/共112页目录下页返回上页结束动态规划的基本概念.阶段的终点又是第k+1阶段的起点，记为Sk，下面我们来求此问题的最短路线，并以此来说明处理多阶段决策问题的最优化原理.先引入令k表示由某点至终点之间的阶段数.例如从A到E可以分为4个阶段，从B1到E是5个阶段；第k第99页/共112页个阶段时所选择的一个决策；在各个阶段上选择令xk(sk)为决策变量，它表示当

45、处于状态时还有态全体可用状态集合来描述.例如：S2=B1,B2；称为状态变量或状态.某个阶段的所有可能状的决策组成的总体称为一个策略.第100页/共112页目录下页返回上页结束由 至终点的最短距离；令 表示 点到 有定义，表示由D1至E的最短距离，故 ，同理 .当 时，若从C1点的距离.现在我们采用逆序递推法从最后一个阶段开 出发则有两个选择，一是至D1,一是至 D2，所以：始计算并逐步推移至A点(也可采用顺序递推法).令 表示现在处在状态 还有k个阶段时，第101页/共112页目录下页返回上页结束最短路线是 ，.依次递推，我们能够得到 ，因此最优路线是 ，这种方法就是动态规划方法.这说明由C

46、1C1出发至终点E E的最短距离是4 4，其第102页/共112页动态规划的递推关系是依据最优化原理推导出来的：一个过程的最优策略应具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必由上例我们可得到动态规划原理的一般模型：第103页/共112页目录下页返回上页结束所给最优策略的前i阶段的策略构成这前i步问题的一个最优策略.上原有的约束条件)来形成一个前 i 步问题，那么须构成最优策略，同时，对于多阶段决策问题的最优策略，如果用它的前i i步策略产生的情况(加第104页/共112页目录下页返回上页结束下面我们利用最优化原理解决一个生产与库

47、存的四个季度的订货量分别为600600件、700700件、500500件了使费用最小，每一季度应生产多少最好？例例11 某厂计划今年全年生产某种产品A，已收到管理问题.和1200件.产品A的生产费用与产品数量的平方成正 比，比例系数为0.005，存在仓库里的产品要花费一定的储存费用，每件产品储存费用为每季度1元，为第105页/共112页目录下页返回上页结束用Ak 表示每个季度的订货量，由已知可得由题目已知，两个阶段之间的产品数量关系，解解 将每个季度视为一个阶段.可得状态转移方程：取第k季度初具有的产品数为状态变量sk，第 k 季度需要生产的产品数xk为决策变量，第106页/共112页目录下页

48、返回上页结束的订单，所以有约束条件：用 表示从状态 出发，采用最优策阶段效益即是费用，所以：略到第四季度结束时的最小费用，可得到动态规划模型：由于订货量的限制，每季度至少要完成相应第107页/共112页目录下页返回上页结束从最后一阶段 开始，此时：当 时，得极小值，即：第三阶段 时：下面用逆序递推方法求解：第108页/共112页目录下页返回上页结束对 求导后并令其为零得：第二阶段 时，用同样的方法可得：第一阶段 时，注意到 ，可得到驻点：即在此点可取极小值，所以：同样用第三阶段时的方法得：第109页/共112页目录下页返回上页结束所以各季度的库存量和最优策略分别为：最小费用为11800元.则总费用为12700元，多用了900元.若每季度都按订货量生产，即第110页/共112页再见目录下页返回上页结束第111页/共112页感谢您的观看。第112页/共112页