二次规划及钢管运输问题模型剖析new.ppt

二次规划与2000年B题--钢管订购与运输模型剖析;若数学规划模型中目标函数或约束条件中有一个或多个是变量的非线性函数，则这样的规划模型叫做非线性规划模型。和此模型相比，前面我们介绍的多是线性问题。 非线性规划的求解相对线性问题要复杂的多，对非线性规划而言，不同的问题有不同的求解方法。 非线性问题规划中有一类较简单的问题----二次规划，许多实际问题的数学模型会归结为二次规划。此处，简单介绍它的解法。;一般的非线性规划模型;二次规划模型;凸二次规划的若干特殊结论;定理：对凸（二次）规划问题，K-T点即是最优解点，即K-T条件是最优解存在的充分必要条件。;二次规划的K-T条件;若令;等式约束二次规划的解法;定理：设Q是半正定矩阵，则x是上述问题的全局最优解， 是相应乘子向量的充要条件是：x， 是线性方程组的解;不等式约束二次规划的求解方法;目录;题目来源;题目;15;16;17;题目重述;基本假设;问题分析;题目求解方法;最简单最直观的想法就是分“两步走”。 第一步：求出各钢厂到各铺设结点的单位最小运费； 这部分包括铁路运费和公路运费，通过合理的方式可将铁路运费转换成公路运费（具体后面说明），再利用求最短路的方法求出我们需要的单位最小运费。 第二步：沿着铺设管道从各结点到各施工地的单位最小运费。 如果这两个运费都能算出，我们就可以将待铺设的主管道全线按照 1公里作为一个单位分割成 5171个点 （对于问题三，可以将树形图分割成 5903个点）。这样问题就变成了一个理想的运输问题，根据我们所学的知识，求解是不难的。;初始思路的考虑不周或未尽之处; 对于每一段待铺设的管线 中的任一铺设点 p而言，从某一钢厂 将钢管运到 p点无外乎有通过 和通过 两种可能，显然，这两种走法的运费是不同的。为此要计算 到 p点的费用，还应该比较这两种走法的大小，对于每一段管线都会有一个平衡点，即两种走法运价相同的点，在该平衡点的两侧应该分别采用两种走法。而且对于同一段管线，这种运价的平衡点又会因运出钢厂的不同而异，因此绝不可以将运到枢纽点 （铺设???点）和运到具体的铺设点割裂开来考虑。;如果假设已经找到了较好的运费、销价的转换方法，问题的模型就可以给出了。;这种模型与普通运输问题模型的区别在于约束条件（2），因为题目给出要求是一个钢厂如果承担制造这种钢管，则至少需要生产 500个单位。而普通的运输问题相应的条件则是;法二：二次规划方法;其它模型; 模型求解;出厂销价、铁路运费向公路运费的转换;转换方法二：;特殊约束条件的处理;根据这种思想，运用二次规划软件得到的最优解中;题目要求中第二问;35;第三问和第一问的区别在于：主管道由直线变为树形图。;37