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