次规划和钢管运输问题模型剖析.ppt

Hu JunfengHu JunfengHu JunfengHu Junfeng 二次规划与2000年B题-钢管 订购与运输模型剖析 韩会磊 2011/07/13 1 Hu JunfengHu JunfengHu JunfengHu Junfeng 若数学规划模型中目标函数或约束条件中有一个或 多个是变量的非线性函数，则这样的规划模型叫做 非线性规划模型。和此模型相比，前面我们介绍的 多是线性问题。 非线性规划的求解相对线性问题要复杂的多，对非 线性规划而言，不同的问题有不同的求解方法。 非线性问题规划中有一类较简单的问题-二次规划 ，许多实际问题的数学模型会归结为二次规划。此 处，简单介绍它的解法。 第一部分：二次规划模型 2 Hu JunfengHu JunfengHu JunfengHu Junfeng 一般的非线性规划模型 其中，均为的函数。 是其中使得 有定义的一个开集。 若约束条件都不存在，就是无约束模型。 若目标和约束满足下面条件，问题就称为二次规划。 3 Hu JunfengHu JunfengHu JunfengHu Junfeng 二次规划模型 其中，是一个对称矩阵， 此问题为一般的二次规划模型。 4 Hu JunfengHu JunfengHu JunfengHu Junfeng 凸二次规划的若干特殊结论 若模型（2）求最小值时，Q是半正定（正定）矩阵 ，则此二次规划为凸（严格凸）二次规划。（若为 最大化问题，则需Q负定或半负定） 众所周知，一般非线性规划问题，求得的往往是局 部最优解，而全局最优解并不一定存在，而且即使 存在的话，也多半不唯一，但如果问题是凸二次规 划的话，结果则不同。 凸二次规划有如下结论（不加证明的给出）： 5 Hu JunfengHu JunfengHu JunfengHu Junfeng 定理：对凸（二次）规划问题，K-T点即是最优解点， 即K-T条件是最优解存在的充分必要条件。 定理：对严格凸（二次）规划问题，全局极小点（如果 存在）是唯一的。 定理：对凸（二次）规划问题，任何局部极小点都是全 局极小点，且极小点的集合为凸集。 6 Hu JunfengHu JunfengHu JunfengHu Junfeng 二次规划的K-T条件 设x*是上述二次规划问题的解，则由非线性规划的 K-T条件结论得二次规划对应的K-T条件： 存在Lagrange乘子 使得 K-T条件是一般非线性规划局部最优解存在的 必要条件 7 若令 则K-T条件可以写成 8 Hu JunfengHu JunfengHu JunfengHu Junfeng 等式约束二次规划的解法 其中，是一个对称矩阵，x,q为n维列向量， 考虑等式约束二次规划： 且rank(A)=m，即A列满秩。 由以上命题和K-T条件，易得以下结论： 9 Hu JunfengHu JunfengHu JunfengHu Junfeng 定理：设Q是半正定矩阵，则x是上述问题的全局最 优解， 是相应乘子向量的充要条件是：x， 是线 性方程组的解 定理表明，求解等式约束二次规划问题可转化为求 解线性方程组问题。 线性方程组的解法很多，常用的比如消去法等 10 Hu JunfengHu JunfengHu JunfengHu Junfeng 不等式约束二次规划的求解方法 对于一般的包含不等式约束的凸二次规划，求解的 方法有很多，比如Lemke方法、Wolfe方法、序列二 次规划法、有效集法（又称积极集法）等，近年来 ，有效集法在中等规模实际问题的求解中使用较广 泛。 11 Hu JunfengHu JunfengHu JunfengHu Junfeng 目录 题目来源 题目 题目重述 基本假设 问题分析 题目求解的思路 题目求解方法 第二部分：2000年B题剖析 12 Hu JunfengHu JunfengHu JunfengHu Junfeng 题目来源 2000年全国数模竞赛B题 命题的主要思路是结合当时的大事西气东输 给出的，但为了适应数模要求在三天完成，时间 较短的特点，对问题做了适当简化。 13 Hu JunfengHu JunfengHu JunfengHu Junfeng 题目 14 Hu JunfengHu JunfengHu JunfengHu Junfeng 15 16 17 Hu JunfengHu JunfengHu JunfengHu Junfeng 题目重述 要求：简洁的表述清楚题目要求，一般不要毫无改动 的照抄原题（此处略掉） 18 Hu JunfengHu JunfengHu JunfengHu Junfeng 基本假设 要求：根据题目要求，提出符合常规的假设或为了方 便解题提出的一些简化问题的假设。 例（此题假设） 1. 钢管运输过程中若用火车则直接把钢管运到公路与铁路交接 处,即下了火车不上火车； 2. 假设运输单位可提供足够的火车与汽车； 3. 费用计算时按钢管数量算，不考虑其他计费方法及因素。 4. 运费中不足整公里部分按整公里计。 5. 假设向每个钢管厂都订购钢管。 6. 设km主管道钢管为单位钢管。 7.路中铺设的钢管只允许由其相邻站点提供。 8.不计各个环节中的装卸费用 。 19 Hu JunfengHu JunfengHu JunfengHu Junfeng 问题分析 本题要铺设一条 的天然气管道，使得总费用最小。 可以这样考虑问题：先把钢厂生产的钢管运到各个站点 再往两边运送，再计算出总的费用使之最小。 首先应该想到的是运输问题模型，但由于铁路、公路运费的不 同还有钢管出厂销价的差别，这不是一个简单的运输问题。 20 Hu JunfengHu JunfengHu JunfengHu Junfeng 题目求解方法 法一：运输问题方法 这是多数同学首先想到的方法。 最简单的运输问题模型就是线性规划中的标准运输问题，用单 纯形法求解此类特殊问题的具体实现就是表上作业法，这个方 法我们已经在运筹学课上学习过了，多数同学都不会陌生。 运输问题模型中最重要的就是运输单位物品的运价，此题中 的运费包括两部分：由钢厂 到各个管道结点 的运费和由各管道结点运到各施工处的费用。 21 Hu JunfengHu JunfengHu JunfengHu Junfeng 最简单最直观的想法就是分“两步走”。 第一步：求出各钢厂到各铺设结点的单位最小运费； 这部分包括铁路运费和公路运费，通过合理的方式可将铁路运 费转换成公路运费（具体后面说明），再利用求最短路的方法 求出我们需要的单位最小运费。 第二步：沿着铺设管道从各结点到各施工地的单位最小运费。 如果这两个运费都能算出，我们就可以将待铺设的主管道全线 按照 1公里作为一个单位分割成 5171个点 （对于问题三，可 以将树形图分割成 5903个点）。这样问题就变成了一个理想 的运输问题，根据我们所学的知识，求解是不难的。 简单的初始思路 22 Hu JunfengHu JunfengHu JunfengHu Junfeng 初始思路的考虑不周或未尽之处 1. 我们对各钢厂的出厂销价未做考虑，即我们已经默认各钢 厂的出厂销价是相同的或此销价的不同不影响钢管的订购 和运输，但这是不符合题意的； 2. 铁路和公路的运费转换未明确； 3. 我们把各钢厂的出厂销价、钢厂到铺设结点的最小运费和 铺设结点到各施工处的最小费用分离开来考虑，实际上它 们是不能完全分开的。 23 Hu JunfengHu JunfengHu JunfengHu Junfeng 对于每一段待铺设的管线 中的任一铺设点 p而言 ，从某一钢厂 将钢管运到 p点无外乎有通过 和通过 两 种可能，显然，这两种走法的运费是不同的。为此要计算 到 p点的费用，还应该比较这两种走法的大小，对于每一段管线都 会有一个平衡点，即两种走法运价相同的点，在该平衡点的两侧 应该分别采用两种走法。而且对于同一段管线，这种运价的平衡 点又会因运出钢厂的不同而异，因此绝不可以将运到枢纽点 （铺 设结点）和运到具体的铺设点割裂开来考虑。 注 由此注解我们很容易知道，前面看似是三个方面的不足实际上 可归结为两点：1，那就是钢管的出厂销价、铁路运费与公路 运费需统一；2，结点到施工处的最小运价通过钢厂运送到结 点的运量 与钢厂到结点的最小运价发生关系，它们是不可 分离的，是密切相关的。24 Hu JunfengHu JunfengHu JunfengHu Junfeng 如果假设已经找到了较好的运费、销价的转换方法，问题的模 型就可以给出了。 方法一的数学模型 25 Hu JunfengHu JunfengHu JunfengHu Junfeng 这种模型与普通运输问题模型的区别在于约束条件（2），因 为题目给出要求是一个钢厂如果承担制造这种钢管，则至少需 要生产 500个单位。而普通的运输问题相应的条件则是 模型说明 此模型的最大优点是其目标函数为线性函数，处理 起 来 比 较 简 单，而且这种模型对题目的第一问和第三问的情况都适用 它的最大缺点是规模太大，决策变量太多，一般的求解线性规 划的软件会因为变量太大而无法工作。为此，在后续的求解中 要采取各种手段，尽可能减少决策变量数。（如，先期比较运 费将 S4从供应商中删除，根据图形特点将供需点归类等手段 ），但这种分析手段只能针对本题的具体情况而不具有一般性 ，而且，采用这种方法将很难证明所得的结果一定是最优的。 26 Hu JunfengHu JunfengHu JunfengHu Junfeng 法二：二次规划方法 此处含订 购费用 由Aj向左，需运输的钢管量： Zj+Zj-1+Zj-2+1(边运输边放下) 27 Hu JunfengHu JunfengHu JunfengHu Junfeng 其它模型 以上，我们介绍了两种最普遍使用的模型，求解此 问题的方法很多，获奖论文中也涉及各种不同的做 法，但多数做法都可大致归为这两种之一，比如其 中的最小费用网络流模型或者二分图的模型就其本 质来讲就属于第一种。 28 Hu JunfengHu JunfengHu JunfengHu Junfeng 模型求解 1.统一在一起的运费 模型一和模型二的求解难点都是类似的，主要有如 下两点： 2.约束条件2的处理 下面依次解决。 29 Hu JunfengHu JunfengHu JunfengHu Junfeng 出厂销价、铁路运费向公路运费的转换 转换方法一： 30 Hu JunfengHu JunfengHu JunfengHu Junfeng 转换方法二： 31 Hu JunfengHu JunfengHu JunfengHu Junfeng 特殊约束条件的处理 32 根据这种思想，运用二次规划软件得到的最优解中 于是将S4从供应名单中删除，再将第7家工厂的供货量改为 0和 不小于500两种情况重做。相比之下，取 0的情况总费用较小， 从而也应把 S7删去，得到问题的最优解为 33 Hu JunfengHu JunfengHu JunfengHu Junfeng 题目要求中第二问 问题中的第二问就是灵敏度分析的内容，可以使用软件结合 适当的讨论，不难作出。 34 Hu JunfengHu