数学建模培训规划理论及模型.ppt

下 回 停 一、引言 二、线性规划模型 三、整数线性规划模型 第一讲 规划理论及模型 四、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 的情况下，使得总 总的费用最低. 首先根据食物数量及价格可写出食谱费用为 其次食谱中第 i 种营养素的含量为 因此上述问题可表述为： 解 上述食谱问题就是一个典型的线性规划问题， 寻求以线性函数的最大（小）值为目标的数学模 型. 它是指在一组线性的等式或不等式的约束条件下， 线性规划模型的三种形 式 一般形式 目标函数 价值向量 价值系数 决策变量 右端向量 系 数 矩 阵 非负约束 自由变量 规范形式 标准形式 三种形式的LP问题全都是等价的，即一种 形式的LP可以简单的变换为另一种形式的LP， 且它们有相同的解 . 以下我们仅将一般形式化成规范形式和标准 形式. 目标函数的转化 xo z -z 约束条件和变量的转化 为了把一般形式的LP问题变换为规范形式 ，我们必须消除等式约束和符号无限制变量.在 一般形式的LP中，一个等式约束 可用下述两个不等式约束去替代 这样就把一般形式的LP变换为规范形式. 对于一个无符号限制变量 ，引进两个非负 变量 和 ，并设 为了把一般形式的LP问题变换为标准 形式，必须消除其不等式约束和符号无限 制变量. 对于一个不等式约束 代替上述的不等式约束. 对符号无限制变量的处理可按上述方法进行. 可引入一个剩余变量 ，用 对于不等式约束 代替上述的不等式约束 这样就把一般形式的LP变换为标准形式 . 可引入一个松弛变量，用 针对标准形式的线性规划问题，其解的理论 分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也 法单纯形方法及其相应的变化形式（两阶段 2.2 线性规划模型的求解 法，对偶单纯形法等）. 是最核心的算法。它是一个迭代算法，先从一个 特殊的可行解（极点）出发，通过判别条件去判 断该可行解是否为最优解（或问题无界），若不 是最优解，则根据相应规则，迭代到下一个更好 的可行解（极点），直到最优解（或问题无界）. 关于线性规划问题解的理论和单纯形法具体的求 解过程可参见文献1. 然后在实际应用中，特别是数学建模过程中， 遇到线性规划问题的求解，我们一般都是利用现 有的软件进行求解，此时通常并不要求线性规划 问题是标准形式. 比较常用的求解线性规划模型 的软件包有LINGO和LINDO. 运输问题 例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.2m 长的地方可用来装包装箱（像面包片 那样），载重为40t. 由于当地货运的限制，对于 C5, C6, C7 类包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过302.7cm. 试 把包装箱装到平板车上，使得浪费的空间最小. 种类 C1C2C3C4C5C6 C7 t/cm48.753.061.372.048.752.064.0 w/kg 2000 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的租与还. 同时假设网站对其会员进行一次 租赁业务时，只能向其提供3张该会员已经预定的 DVD，否则不进行租赁. 经观察，可以认为在线订单中每个会员的预 定DVD的表示偏好程度的数字反映了会员对所预 定不同DVD的满意程度，且当会员租到其预定排 序为1，2，3的三张DVD时，满意度达到100% . 会员没有预定的DVD对其满意度的贡献为0 . 利用层次分析法，对此满意指数的合理性进 行了简单分析. 该问题要求根据现有的100种DVD的数量和 当前需要处理的1000位会员的在线订单，制定 分配策略，使得会员达到最大的满意度. 因而我 们认为只需对这些DVD进行一次性分配，使得会 员的总体满意度达到最大. 为此考虑建立优化模 型，进行求解. 问题二的模型及求解 经营成本和会员的满意度是被考虑的两个相 互制约的重要因素. 在忽略邮寄成本的前提下， 经营成本主要体现为DVD的数量. 我们主要考虑 在会员向网站提