数学建模简明教程（第一章pptppt课件

单击此处编辑母版标题样式 单击此处编辑母版副标题样式 *1 数学建模简明教程 国家精品课课程 第一章 规规划理论论及模型 一、引言 二、线性规划模型 三、整数线性规划模型 四、0-1整数规划模型 五、非线性规划模型 六、多目标规划模型 目录下页返回上页结束 七、动态规划模型 一、引言 目录下页返回上页结束 我们从2005年“高教社杯”全国大学生数模竞 赛的B题“DVD在线租赁”问题的第二问和第三问 谈起. 其中第二个问题是一个如何来分配有限资源， 从而达到人们期望目标的优化分配数学模型. 它 在运筹学中处于中心的地位. 这类问题一般可以 归结为数学规划模型. 目录下页返回上页结束 规划模型的应用极其广泛，其作用已为越来 来越急速地渗透于工农业生产、商业活动、军事 行为核科学研究的各个方面，为社会节省的财富、 创造的价值无法估量. 特别是在数模竞赛过程中，规划模型是最常 见的一类数学模型. 从92-06年全国大学生数模竞 越多的人所重视. 随着计算机的逐渐普及，它越 赛试题的解题方法统计结果来看，规划模型共出 现了15次，占到了50%，也就是说每两道竞赛题 中就有一道涉及到利用规划理论来分析、求解. 目录下页返回上页结束 二、线性规划模型 线性规划模型是所有规划模型中最基本、最 例1 （食谱问题）设有 n 种食物，各含 m 种营养 素，第 j 种食物中第 i 中营养素的含量为 aij , n 种 食物价格分别为c1, c2, , cn，请确定食谱中n 种食 物的数量x1, x2, , xn，要求在食谱中 m 种营养素 简单的一种. 2.1 线性规划模型的标准形式 的含量分别不低于b1, b2, , bm 的情况下，使得总 的费用最低. 目录下页返回上页结束 线性规划模型的三种形式 系 数 矩 阵 目标函数 价值向量 价值系数 决策变量 右端向量 非负约束 自由变量 一般形式 目录下页返回上页结束 规范形式 标准形式 三种形式的LP问题全都是等价的，即一种 形式的LP可以简单的变换为另一种形式的LP， 且它们有相同的解. 以下我们仅将一般形式化成规范形式和标准 形式. 目录下页返回上页结束 目标函数的转化 xo z -z 目录下页返回上页结束 约束条件和变量的转化 为了把一般形式的LP问题变换为规范形式， 可用下述两个不等式约束去替代 我们必须消除等式约束和符号无限制变量. 在一 般形式的LP中，一个等式约束 目录下页返回上页结束 这样就把一般形式的LP变换为规范形式. 变量 和 ，并设 对于一个无符号限制变量 ，引进两个非负 目录下页返回上页结束 对于一个不等式约束 代替上述的不等式约束. 对符号无限制变量的处理可按上述方法进行. 可引入一个剩余变量 ， 必须消除其不等式约束和符号无限制变量. 为了把一般形式的LP问题变换为标准形式， 目录下页返回上页结束 对于不等式约束 代替上述的不等式约束. 这样就把一般形式的LP变换为标准形式. 可引入一个松弛变量，用 目录下页返回上页结束 针对标准形式的线性规划问题，其解的理论 分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也 法单纯形方法及其相应的变化形式（两阶段 2.2 线性规划模型的求解 法，对偶单纯形法等）. 是最核心的算法. 它是一个迭代算法，先从一个 特殊的可行解（极点）出发，通过判别条件去判 断该可行解是否为最优解（或问题无界），若不 目录下页返回上页结束 是最优解，则根据相应规则，迭代到下一个更好 的软件包有LINGO和LINDO. 的可行解（极点），直到最优解（或问题无界）. 关于线性规划问题解的理论和单纯形法具体的求 解过程可参见文献1. 然后在实际应用中，特别是数学建模过程中， 遇到线性规划问题的求解，我们一般都是利用现 有的软件进行求解，此时通常并不要求线性规划 问题是标准形式. 比较常用的求解线性规划模型 目录下页返回上页结束 运输问题 例2 设要从甲地调出物资2000吨，从乙地调出物 资1100吨，分别供给A地1700吨、B地1100吨、C 假定运费与运量成正比. 在这种情况下，采用不 地200吨、D地100吨. 已知每吨运费如表1.1所示. 同的调拨计划，运费就可能不一样. 现在问：怎 样才能找出一个运费最省的调拨计划？ 目录下页返回上页结束 1572521甲 15375151乙 DCBA 表 1.1 销 地 运 费 产 地 目录下页返回上页结束 解 乙 甲 D C B A 目录下页返回上页结束 目录下页返回上页结束 一般的运输问题可以表述如下： 运一个单单位的产产品到 已知 ，从 在满满足供需要求的条件下，使总总运输费输费 用最省. 个发发点要把某种物资资从 ， 调调运给给需要这这种物资资的 个收点 . . 的运价为为现在需要确定一个调运方案，即确 到的运输输量定由 目录下页返回上页结束 数学模型： 目录下页返回上页结束 类似与将一般的线性规划问题转化为其标准 否则，称为不平衡的运输问题，包括： 即，则称该问题为平衡的运输问题. 总产量总销量和总产量总销量. 形式，我们总可以通过引入假想的销地或产地， 将不平衡的运输问题转化为平衡的运输问题. 从 而，我们的重点就是解决平衡运输问题的求解. 若其中各产地的总产量等于各销地的总销量， 目录下页返回上页结束 该方法将单纯形法与平衡的运输问题的特殊性质 运输问题及其解法的进一步介绍参加文献2. 显然，运输问题是一个标准的线性规划问题， 因而当然可以运用单纯形方法求解.但由于平衡 的运输问题的特殊性质，它还可以用其它的一些 特殊方法求解，其中最常用的就是表上作业法， 结合起来，很方便地实行了运输问题的求解.关于 目录下页返回上页结束 对于线性规划问题，如果要求其决策变量取 整数值，则称该问题为整数线性规划问题. 平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运 三、整数线性规划模型 算量远大于同规模的线性规划问题. Gomory割 规划问题的方法（见文献1）. 此外，同线性规 划模型一样，我们也可以运用LINGO和LINDO软 件包来求解整数线性规划模型. 目录下页返回上页结束 如何求解整数线性规划模型. 以1988年美国大学生数学建模竞赛B题为例， 说明整数线性规划模型的建立及用LINGO软件包 例3 有七种规格的包装箱要装到两节铁路平板车 上去. 包装箱的宽和高是一样的，但厚度（t，以 cm 计）及重量（w，以kg计）是不同的. 表1给出 了每种包装箱的厚度、重量以及数量. 每节平板 车有10.2 m 长的地方可用来装包装箱（像面包片 那样），载重为40t. 由于当地货运的限制，对于 目录下页返回上页结束 C5, C6, C7 类包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过302.7cm. 试 把包装箱装到平板车上，使得浪费的空间最小. 种类类 C1C2C3C4C5C6 C7 t/cm48.753.061.372.048.752.064.0 w/kg2000 3000 10005004000 2000 1000 n/件8796648 目录下页返回上页结束 为在第 节车上装载第 件包装箱的 解 令 种包装箱需要)；数量(为为第 下面我们建立该问题的整数线性规划模型. 节车节车 的载载重量；为为第为为特殊限制(). 装的件数；为为第种包装箱的重量； 为为第 种 包装箱的厚度；为为第 节车节车 的长长度()； 目录下页返回上页结束 1) 约束条件 两节车的装箱数不能超过需要装的件数，即： 每节车可装的长度不能超过车能提供的长度： 每节车可装的重量不超过车能够承受的重量： 目录下页返回上页结束 对于C5, C6, C7类包装箱的总数的特别限制： 2) 目标函数 浪费的空间最小，即包装箱的总厚度最大： 目录下页返回上页结束 3) 整数线性规划模型 目录下页返回上页结束 4) 模型求解 运用LINGO软件求解得到： 5) 最优解的分析说明 优的装车方案，此时装箱的总长度为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 元，现有一个载重量不超过 大，应如何装载这些物品？ a 千克的背包，为了使装入背包的物品总价值最 用变量 xi 表示物品 i 是否装包，i =1, 2, , n， 并令： 解 目录下页返回上页结束 可得到背包问题的规划模型为： 目录下页返回上页结束 例5 有n 项任务，由 n 个人来完成，每个人只能 做一件， 第 i 个人完成第 j 项任务要 cij 小时，如 何合理安排时间才能使总用时最小？ 引入状态变量 xij ，并令：解 则总用时表达式为： 目录下页返回上页结束 可得到指派问题的规划模型为： 目录下页返回上页结束 上面介绍的指派问题称为指派问题的标准形 式，还有许多其它的诸如人数与任务数不等、及 但一般可以通过一些转化，将其变为标准形式. 某人可以完成多个任务，某人不可以完成任务， 某任务必须由某人完成等特殊要求的指派问题. 对于标准形式的指派问题，我们可以利用匈 牙利算法实现求解. 它将指派问题中的系数构成 一个矩阵，利用矩阵上简单的行和列变换，结合 解的判定条件，实现求解（见文献2）. 目录下页返回上页结束 DVD在线租赁第二个问题的求解 问题二的分析 尽量小，会员满意度最大. 经营成本和会员的满意度是被考虑的两个相互 制约的重要因素.在忽略邮寄成本的前提下，经营 成本主要体现为DVD的数量. 我们主要考虑在会员 向网站提供需求信息，且满足一定要求的前提下， 对给定数量DVD进行分配决策，使得DVD的数量 目录下页返回上页结束 DVD，否则不进行租赁. 没有预定的DVD对其满意度的贡献为0. 假设按照公历月份进行的租赁业务，即会员 无论两次租赁还是一次租赁，必须在当月内完成 DVD的租与还. 同时假设网站对其会员进行一次 租赁业务时，只能向其提供3张该会员已经预定的 经观察，可以认为在线订单中每个会员的预定 DVD的表示偏好程度的数字反映了会员对所预定 不同DVD的满意程度，且当会员租到其预定排序 为1，2，3的三张DVD时，满意度达到100%. 会员 目录下页返回上页结束 利用层次分析法，对此满意指数的合理性进 行了简单分析. 进行求解. 该问题要求根据现有的100种DVD的数量和 当前需要处理的1000位会员的在线订单，制定分 配策略，使得会员达到最大的满意度. 因而我们 认为只需对这些DVD进行一次性分配，使得会员 的总体满意度达到最大.为此考虑建立优化模型， 目录下页返回上页结束 如下：我们们定义义 . 即不超过相应的现有数量 个会员对员对 第表示第令种DVD 问题二的模型及求解 的满满意指数矩阵阵.表示第 j 种DVD 的现现有数量. 显显然，对对每种DVD,要求分配的总量 目录下页返回上页结束 又根据假设设，网站只向会员员提供其预预定的DVD， 进进行分配. 故引入约约束 进进一步，对对每个会员员每次租赁赁只能获获得3张张其 不为0时，才可能进行即只有当满意指数 预定的DVD或不能得到，有 目录下页返回上页结束 在上述约约束的前提下，我们们追求会员员的总总体 会员员的最大满满意指数为为10+9+827，1000个 为为了更好地表示满满意度，我们们将目标转标转 化为为 满意指数和 达到最大，显然每个 会员最大的满意指数和为 用百分数表示的满意度为： ， 目录下页返回上页结束 由此，可得问题二的0-1整数线性规划模型如下： 目录下页返回上页结束 配方案（见表3）. 会员全都得到了3张预定的DVD. 根据所得的0-1整数线性规划模型，利用 LINGO软件进行求解，我们得到了一组最优分 该组最优解其目标函数会员总体最大满意 度为91.56%，只有6人未成功租赁（如：前30 名会员中C0008被分配到DVD），其余994个 目录下页返回上页结束 五、非线性规划模型 即非线性规划问题. 前面介绍绍了线线性规规划问题问题 ，即目标标函数和约约束条 件都是线线性函数的规规划问题问题 ，但在实际实际 工作中，还还 常常会遇到另一类类更一般的规规划问题问题 ，即目标标函数 和约约束条件中至少有一个是非线线性函数的规规划问题问题， 目录下页返回上页结束 事实实上，客观观世界中的问题许问题许 多是非线线性 的，给给予线线性大多是近似的，是在作了科学 的假设设和简简化后得到的. 为为了利用线线性的 知识识，许许多非线线性问题问题 常进进行线线性化处处理. 但在实际问题实际问题 中，有一些是不能进进行线线性化 处处理的，否则则将严严重影响模型对实际问题对实际问题 近似的可依赖型. 目录下页返回上页结束 由于非线线性规规划问题问题 在计计算上常是困难难的 ， 理论论上的讨论讨论 也不能像线线性规规划那样给样给 出简洁简洁 的结结果形式和全面透彻彻的结论结论 .这这点又限制了非 线线性规规划的应应用，所以，在数学建模时时，要进进 行认认真的分析，对实际问题进对实际问题进 行合理的假设设、 简简化，首先考虑虑用线线性规规划模型，若线线性近似 误差较大时，则考虑用非线性规划. 目录下页返回上页结束 非线性规划问题的标准形式为： 其中， 为为 维维欧式空间间 中的向量， 为为目标标函数，为约为约 束条件. 且 中至少有一个是非线线性函数. 目录下页返回上页结束 非线性规划模型按约束条件可分为以下三类： 等式约束非线性规划模型： 无约束非线性规划模型： 目录下页返回上页结束 不等式约束非线性规划模型： 针对上述三类非线性规划模型，其常用求解的基 本思路可归纳如下： 目录下页返回上页结束 但求解 往往是很困难的. 求出最优优解 ， （下降迭代法）寻寻找，该该方法的基本步骤骤如下： 所以往往根据目标函数的特征采用搜索的方法 1) 无约束的非线性规划问题 若目标标函数的形式简单简单 ，可以通过过 求解方程( 表示函数的梯度） 目录下页返回上页结束 止迭代，用 来近似问题问题 的最优优解，否则转则转 至 . 从 出发发，沿方向 ,按某种方法确定步长长 , 令 ，然后置 ，返回 适当选选取初始点，令 按某种规则规则 确定处处的搜索方向. 使得： 检验检验 是否满满足停止迭代的条件，如是，则则停 目录下页返回上页结束 线性规划可以用一维搜索方法求得最优解，一维搜 最常用的搜索方法就是最速下降法. 在下降迭代算法中，搜索方向起着关键键的作 用，而当搜索方向确定后，步长长又是决定算法好坏 的重要因素. 非线线性规规划只含一个变变量，即一维维非 索方法主要有进进退法和黄金分割法. 二维维的非线线性 规规划也可以像解线线性规规划那样样用图图形求解. 对对于二 维维非线线性规规划，使用搜索方法是要用到梯度的概念， 目录下页返回上页结束 约束问题求解. 近的方法将非线性规划问题化为线性规划问题. 2) 只有等式约约束的非线线性规规划问题问题 通常可用消 元法、拉格朗日乘子法或反函数法，将其化为为无 3) 具有不等式约约束的非线线性规规划问题问题 解起来很 复杂杂，求解这这一类问题类问题 ，通常将不等式化为为等式 约约束，再将约约束问题问题 化为为无约约束问题问题 ，用线线性逼 规划问题可用拉格朗日方法求解. 下面介绍绍一个简单简单 的非线线性规规划问题问题 的例 子，其中的一些约约束条件是等式，这类这类 非线线性 目录下页返回上页结束 客户的速度. 例7 （石油最优储优储 存方法）有一石油运输输公 司，为为了减少开支，希望作了节节省石油的存储储 空间间.但要求存储储的石油能满满足客户户的要求.为为 简简化问题问题 ，假设设只经营经营 两种油，各种符号表示 的意义义如表4所示.其中供给给率指石油公司供给给 目录下页返回上页结束 表4 各种符号表示意义表 第i种油的存储储量 第i种油的价格 第i种油的供给给率 第i种油的每单单位的存储费储费 用 第i种油的每单单位的存储储空间间 总总存储储公式 目录下页返回上页结束 由历史数据得到的经验公式为 : 且提供数据如表5所示： 目录下页返回上页结束 表5 数据表 已知总总存储储空间间 石油的 种类类 1930.502 2450.24 目录下页返回上页结束 代入数据后得到的模型为： 拉格朗日函数的形式为： 模型求解： 目录下页返回上页结束 即: 对对 求各个变变量的偏导导数，并令它们们 等于零，得: 目录下页返回上页结束 解这个线性方程组得： 从而可得最小值值是12.71. 间间由24变为变为 25时时，最优值优值 会由12.71变为变为 表示当约约束条件右边边的值值增大一个单单位后，相 应应目标标函数值值的增加值值。比如说说：如总总存储储空 目录下页返回上页结束 六、多目标规划模型 许许多实际问题实际问题 中，衡量一个方案的好坏标标准 往往不止一个. 例如设计设计 一个导弹导弹 ，既要射程 最远远，又要燃料最省，还还要精度最高. 这这一类类 问题统问题统 称为为多目标标最优优化问题问题 或多目标规标规 划问 题. 我们先来看一个生产计划的例子. 目录下页返回上页结束 能耗不得超过160t标准煤其它数据如下表： 布料 生产产数量 （m/h） 利润润 （元/m） 最大销销售量 （m/周） 能耗 （t/km） A1 4000.15400001.2 A2 5100.13510001.3 A3 3600.20300001.4 问每周应生产三种布料各多少m，才能使该厂 的利润最高，而能源消耗最少？ ，该厂两班生产，每周生产时间为80h， 例8 （生产计划问题）某厂生产三种布料 目录下页返回上页结束 解 设该厂每周生产布料 的小时数为 ，总利润为 （元），总能耗为 （t标准煤），其中 ， 则上述问题的数学模型为 目录下页返回上页结束 其中， ， . 有 显然这是一个多目标线性规划问题. 一般的多目 标规划问题都可写成如下的形式： 目录下页返回上页结束 从而得到满意解的方法. 主要区别在于：目标函数不止一个，而是p 个 （ ） . 问题问题 的可行集或容许许集， 称为为可行解或容 称为多目标规划 许许解. 多目标规标规 划问题问题 与前面讲讲的规规划问题问题 的 多目标规标规 划问题问题 的解法大致可分为为两类类：直 接解法和间间接解法. 到目前为为止，常用的多为为 间接解法，即根据问题问题 的实际实际 背景和特征，设设 法将多目标优标优 化问题转问题转 化为单为单 目标优标优 化问题问题 ， 目录下页返回上页结束 一个目标为主要目标，例如 ，而把其余目 1)主要目标法 线性规划问题： 多目标优标优 化问题问题 中，若能从p 个目标标中，确定 标标作为为次要目标标，并根据实际实际 情况，确定适当的 界限值值，这样这样 就可以把次要目标标作为约为约 束来处处理， 而将多目标优标优 化问题转问题转 化为为求解如下的线线性或非 目录下页返回上页结束 其中界限值取为 ，则 目标优化问题的弱有效解或有效解. 令 此非线线性规规划问题问题 得最优优解必为为原问题问题 的弱 有效解. 因此，用主要目标标法求得的解必是多 目录下页返回上页结束 排一个次序，假设 最重要， 次之， 再次之，最后一个目标 . 先求出以第一个目标 为目标函数，而原 2) 分层序列法 把多目标规标规 划问题问题 中的p 个目标标按其重要程度 问题中的约束条件不变的问题 ： 目录下页返回上页结束 的最优解 及最优值 ，再求问题 ： 的最优解 及最优值 ，即 ， 其中：为问题 的可行域. 目录下页返回上页结束 再求解问题 ： 得最优解 及最优值 ，如此继续下去， 直到求出第p 个问题 ： 原多目标规划问题在分层序列意义下得最优解， 为其最优值. 得最优解 及最优值 ，则 就是 目录下页返回上页结束 P, 其最优解是唯一的，则问题 的最优解 也是唯一的，且 。因此常将分层 序列法修改如下：选取一组适当的小正数 成为宽容值，把上述的问题 修改如下： 再按上述方法依次求解各问题 . 容易看出，在使用分层序列法时，若对某个问题 . 目录下页返回上页结束 3）线性加权求和法 程度给以适当的权系数 ，且 ，然后用 作为新的目标 得最优解 ，取 作为多目标规划 函数，成为评价（目标）函数，再求解问题 对对多目标规标规 划问题问题 中的p个目标标按期重要 问题问题 的解. 目录下页返回上页结束 优解必是原多目标规划问题的有效解或弱有效解. 例9 求解引言中DVD在线线租赁赁的第三个问题问题 . 性规规划模型以及利用主要目标标法求解该该模型. 在一定条件下，用线线性加权权求和法求得的最 下面以引言中2005年全国大学生数模竞赛竞赛 “DVD在线线租赁赁”问题问题 第三问为问为 例，介绍绍多目标线标线 目录下页返回上页结束 得会员的满意度最大. 问题三的分析 此问问是在现现有的在线订单线订单 基础础上，满满足一个 月内95%的会员员得到他预订预订 的DVD，我们进们进 行 购买购买 量预预算和分配决策，使得会员员的满满意度最 大.预预算购买购买 量的目的是在尽可能地减少DVD 购买购买 量的前提下，满满足要求，进进行合理分配使 在一个月内进行分配，因而存在部分DVD的两次 员的第二次租赁. 我们们假设设会员员得到他想看的DVD就是指：会员员 租赁赁到了他预预定的DVD中的三张张；且假设设会员员每 次租赁赁前都需要提交新的在线订单线订单 . 此问问中要求 被租赁赁，但因为为是处处理同一份订单订单 ，因而存在会 目录下页返回上页结束 了 张DVD的作用. 基于这这个假设设，为为了最小化购买购买 量，我们们在 允许许当前某些会员员无法被满满足租赁赁要求，让让其 等待，利用部分会员还员还 回的DVD对对其进进行租赁赁. 根据问题问题 一，我们认为们认为 ，一个月中每张张DVD 有0.6的概率被租赁赁两次，0.4的概率被租赁赁一次. 即在二次租赁赁的情况下，每张张DVD相当于发挥发挥 目录下页返回上页结束 由此，在问题二建立的0-1整数规划模型的 求，考虑DVD可能的两次分配，进一步追求DVD 基础上，满足95%的会员得到他想看DVD的要 进行求解. 总的购买数量最小. 建立双目标整数规划模型 目录下页返回上页结束 设 表示第j种DVD需要的购买量.对每种DVD， 问题三的模型 要求分配的总量不超过相应的现有数量的1.6倍.即: 为了让95%的会员可以得到他想看的3张DVD，即: 目录下页返回上页结束 我们希望购买DVD的总数量最小，即 : 由此，可以得到问题三的双目标整数线性规划 模型如下： 目录下页返回上页结束 目录下页返回上页结束 总体满意度水平 （即最小的满意度） 将其满意度的目标转换为约束，如下： 问题问题 三的求解与检验检验 对对于该该双目标标整数线线性规规划模型，我们们引入 目录下页返回上页结束 目录下页返回上页结束 利用Lingo软件，调整总体满意度水平 进行 求解。实际计算中，如果要求 为整 约束进行计算。求得解 后，对其 进行取整。当 时，我们解得DVD总的最小 购买量 ，其中第j种DVD需要的购买 量 如下表： 数，无法求得可行解，因而我们们取消了其整数 表6 当 时最小购买量的 值 目录下页返回上页结束 DVD编编号D01D02D03D04D05D06D07D08D09D10 最少购买购买 量 14211724121719212214 DVD编编号D11D12D13D14D15D16D17D18D19D20 最少购买购买 量 18181717172418161823 DVD编编号D21D22D23D24D25D26D27D28D29D30 最少购买购买 量 20182214181715121624 DVD编编号D31D32D33D34D35D36D37D38D39D40 最少购买购买 量 19222019222213171717 DVD编编号D41D42D43D44D45D46D47D48D49D50 最少购买购买 量 32201621221620152020 目录下页返回上页结束 续上表 DVD编编号D51D52D53D54D55D56D57D58D59D60 最少购买购买 量24171917191819172021 DVD编编号D61D62D63D64D65D66D67D68D69D70 最少购买购买 量16191920171917212019 DVD编编号D71D72D73D74D75D76D77D78D79D80 最少购买购买 量21221520151412171917 DVD编编号D81D82D83D84D85D86D87D88D89D90 最少购买购买 量18101412211322151317 DVD编编号D91D92D93D94D95D96D97D98D99D100 最少购买购买 量24171514251522201122 目录下页返回上页结束 我们利用规划模型求得每种DVD的购买量后， 需要对其进行可行性校验，测试此结果是否可以 且具有尽可能大的总体满意度. 满足一个月内比例为95%的会员得到他想看DVD， 目录下页返回上页结束 校验方法： （一）根据订单订单 和求得的DVD购买购买 数量，利用问题问题 二的规规划模型进进行第一次分配，对对分配情况：租 赁赁的会员员，DVD的分配情况，剩余的各种DVD 数量作记录记录 ；同时时将已租赁赁的会员员在满满意指数 矩阵阵的指数全变为变为 0，即不考虑对虑对 其进进行第二次 分配. 第一次未分配到DVD的会员进行第二次分配； （二）随机从第一次得到DVD的会员员中抽取60%， 将这这部分人所还还回的DVD与第一次分配余下的 DVD合在一起，作为为第二次分配时时各种DVD的 现现有量.然后，利用问题问题 二的0-1线线性规规划模型对对 目录下页返回上页结束 （三）统计出经过两次分配后，得到DVD的会员 使得到DVD的会员大于95%，则认为模型三是合 种算法进行多次随机模拟，若大多数情况下可以 的比例，若大于95%，则此次分配成功.利用这 理的. 目录下页返回上页结束 校验结果： 因为每次检验需时约1小时，我们只对问题三 表7 7次模拟结果每次的观看比例列表 验证验证 次 数 1234567 观观看比 例 95.8 96.6 93.4 95.3 95.9 96.1 95.7 观看比例大于95%）.下面给出7次模拟得到的观 求得的结果进行了7次模拟，其中6次符合要求（ 看比例（表7）： 目录下页返回上页结束 七、动态规划模型 过程中的最优控制问题. 动态规划所研究的对象是多阶段对策问题， 是在20世纪50年代初期由美国数学家R.Bellman等 人提出的一类规划模型. 动态规划是现代管理领域 的一种重要的决策方法，其主要应用有最优路径 问题、资源分配问题、投资决策问题、生产计划 与库存问题、排序问题、货物装载问题以及生产 目录下页返回上页结束 理多阶段决策问题的最优化原理. 效益的总和达到最优. 多阶段决策问题是指一类活动过程，它可分 为若干个相互联系的阶段，在每个阶段都需要做 出决策，这个决策不仅决定这一阶段的效益，而 定以后，就得到一个决策序列，称为策略. 多阶 段决策问题就是求一个策略，使各阶段的效益的 下面我们通过讲解一个最短路问题来引出处 且决定下一阶段的初始状态，每个阶段的决策确 目录下页返回上页结束 例10 有一辆辆汽车车要把货货物从A城运到E城，而 可供选择选择 ，选选取怎样样的路线线才能使路程最短 ？ 从A城到E城必须经过一些城市，整段路程可以 分为若干个阶段，而每个阶段又有若干个城市 假定从A城到E城的所有路线如下图所示： 目录下页返回上页结束 图1 从A城到E城的路线 5 61 3 2 7 4 2 4 1 4 6 途中的数字表示两城之间的距离（以10千米为 其中 B1,B2,C1,C2,D1,D2是可供选择的城市， 单位）. 目录下页返回上页结束 很明显，前面各阶段的决策如何选择，直接影响着 段选择选择 一个决策，使由它们们决定的总总路程最短. 显然，这是一个多阶段决策问题：从A到E可以分为 4个阶段. 从A点出发到B1或B2为第一阶段，这时有 两个选择：走到B1或者走到B2. 若我们选择走到B1 的决策，则B1就是下一个阶段的起点. 在下一阶段， 我们从B1出发，有一个可供选择的决策集合C1 ,C2， 其余各阶段的行进路线，我们的目的就是在各个阶 目录下页返回上页结束 动态规划的基本概念. 阶段的终点又是第k+1阶段的起点，记为Sk， 下面我们来求此问题的最短路线，并以此来 说明处理多阶段决策问题的最优化原理.先引入 令k表示由某点至终点之间的阶段数.例如从A 到E可以分为4个阶段，从B1到E是5个阶段；第k 个阶阶段时时所选择