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