钢管定购与运输

《钢管定购与运输》由会员分享，可在线阅读，更多相关《钢管定购与运输（70页珍藏版）》请在金锄头文库上搜索。

1、钢管定购与运输,南京邮电大学数理学院 杨振华,问题,要铺设一条 的输送天然气的 主管道, 如图一所示。经筛选后可以生产这种 主管道钢管的钢厂有 。图中粗线表 示铁路，单细线表示公路，双细线表示要铺 设的管道(假设沿管道或者原来有公路，或者 建有施工公路)，圆圈表示火车站，每段铁 路、公路和管道旁的阿拉伯数字表示里程(单 位km)。为方便计，1km主管道钢管称为1单 位钢管。,一个钢厂如果承担制造这种钢管，至少需要 生产500个单位。钢厂 在指定期限内能生产 该钢管的最大数量为 个单位，钢管出厂销价 1单位钢管为 万元，如下表：,1单位钢管的铁路运价如下表： 1000km以上每增加1至100km

2、运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部 分按整公里计算）。 钢管可由铁路公路运往铺设地点(不只是运到点 , 而是管道全线)。,（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,图一,图二,建模思路,(1)将A1到A15的51

3、71公里分成5171段，每一段设置一个变量，取值为1到7，即供应钢管的钢厂的标号。显然从任何一个钢厂到铺设的任何一段的费用是固定的。从而可以求出最优解。 问题 复杂度大，即使不考虑产量约束，也要考虑75171种情况，计算机无法计算出。 钢厂是否一定按照整数产量供应？即使整数产量，铺设的也未必是两个整数之间。,(2)考虑到钢管运送到Aj之后再铺设时，已经与从何处运来没有关系，我们可以将任何一点Aj向左(右)铺设的钢管分成7段，即同一个钢厂的钢管合并为一个区间。这样，每个节点Aj对应7个区间,一共98个区间(A1不考虑)。如果将98个区间决定出来，生产和运输的方案也确定。据此可建立数学模型。 问题

4、 复杂度依然大，用计算机很难求解。,(3)根据上面的思路，钢管运送到Aj之后再铺设时，已经与从何处运来没有关系，可以将任何一个钢厂到节点的运输量作为变量，再设出节点向左右铺设的长度，总的方案即确定。据此可建立数学模型。 两部分费用： 一是将钢管由厂Si运到Aj,设Si到Aj的单位费用为qij ,运量为xij , 则总费用为 ,(xi1=0)。,二是到达Aj的钢管再由公路送到管线，设Aj向左 运yj公里，向右运zj公里，相应的费用为,其中yj,yj分别表示yj的整数与小数部分。 注意：此处不能将费用简单地处理为m(m+1)/2的 形式，如果铺设距离是小数，该式不成立。,模型,最小费用路径,要求出

5、qij（单位钢管由Si生产并运至Aj的费 用），必须求最小费用路径。我们可以求出 铁路网任意两点的最短路，折算成公路，再 和公路网合并，即可求出最小费用路径。 下面的表给出qij的取值。,优化模型的求解,上面的优化模型形式复杂，较难求解。不过可以从以下几个方面把模型化为已知的优化问题： （1）设xij,yj,zj都是整数，目标函数就成为它们的二次函数。,（2）将集合 分为两部分，分别进行求解。这样可将原问题化为128个二次规划问题，从而找出最优解。,可以发现，S1,S2,S3已经达到满负荷生产，S4产量为零，S5,S6为部分生产.唯一有问题的是S7的产量不符合约束条件。,（3）上面（2）的处理

6、方法还是过于复杂。我们可以先将约束集合 扩大为 ，求出最优解。用SAS软件求解得各钢厂的产量为： 800, 800, 1000, 0, 1190.5, 1135.5, 245 (费用：1275351.55),（4）为满足原来的约束条件，我们只需将S7的约束分为两种情况求解。 若S7产量为零，则最优解对应的费用为1278631.55, (800, 800,1000, 0,1190.5,1380.5) 若S7产量在500,3000内，则最优解对应的费用为1279660.55。 因此，我们得出结论S7产量为零，而且可以写出最优解。,问题： 我们是在存在最优整数解的假设下用计算机求出了最优解。然而得出

7、的解不是整数,这是一个矛盾。能否证明最优解中必存在整数解？并进而在此条件下给出一个最优解？ 能否证明最优解中S4与S7的产量为零，以及前三个钢厂的产量达到满负荷？ 能否求出精确的最优解？如果用计算机求解得到的精度不高，会给灵敏度分析带来困难。,最优解中必存在整数解(证明思路),考虑98个区间的模型。我们来说明存在98个 区间的端点均为整数的最优解。否则，假设 与非整数区间对应的钢厂均已达到产量的上 限或下限(如果有区间对应钢厂的产量未达 限，证明稍简单)。考虑将某一非整区间对应 钢厂 在其端点x12附近交给产量给相邻区 间对应钢厂 ，费用增量为 ，(注意可取得小一些，保证在x12附近这两 个钢

8、厂的单价均不发生变化)。钢厂 必然还 对应另外的非整区间，将 的产量调整给,其相邻区间对应钢厂,如此下去必然会出现钢厂的 一个循环,不妨设为 ,其费用的总的增 量为 若括号内的数不为零，由于可正可负，总可以 取合适的,使得总费用减少,与最优解矛盾.因此 括号内数字为零。 选取合适的，必然可以使非整数端点的数目减 少一个。 由于区间的总数是有限的，最终可以使所有的端 点均为整数。,误差分析,虽然在最优解中必存在整数解，但用SAS软 件求出的解却不是整数。 (1)xij不是整数 计算机求出的最优解中存在许多xij不是整数， 这一部分不影响目标函数的取值因为在将目 标函数简化为二次函数时，和这些变量

9、相关 的项没有改变。,(2)yj与zj不是整数 用计算机求出的yj与zj有一部分不是整数： y6=184.5,y7=189.5,z5=9.5,z6=15.5 这里的小数部分会影响目标函数的取值。 考虑A5A6这一段，由S1从A6进入铺设右边184.5公里的费用应为(184*185/2+185*0.5)*0.1, 但是在编程时忽略了“不足1公里按1公里计算”这一条件,铺设费用计算为0.1*184.5*185.5/2. 减小了0.0125. 一共有4个0.5公里出现了上述的误差。 实际的最优函数值应为1278361.6,上面两个结论以及前三个钢厂满负荷生产的证明比较复杂。 在数学建模中给出问题的一

10、些理论结果是很有价值的.在建模竞赛中给出一些理论证明对于获奖也是有利的 竞赛中即使仅给出不完善的证明也是有利的. 下面引入新的模型来证明并讨论原问题。,积分模型,记铺设管道A1A15上任一点到A1的距离为x,令fi(x)为钢厂Si生产并运输单位钢管至x处的最小费用。若xAj Aj+1易知 fi(x)=min(qij+0.1(x-aj+1), qi,j+1+0.1(aj+1-x+1) 根据qij的取值，我们可以给出fi(x)的具体表达式和图形. 下图就是这7个函数的图形（实际上是众多的水平线段，看起来象斜线段）,注：到达Aj的钢管的铺设费用，只与铺设的长度有关，可以将同一钢厂的钢管铺为一个区间，

11、因此Ei可以表示为 并且可以证明存在一组最优解使得区间端点为整数。,设 为Si生产运输钢管的集合，由于 为单价，其相应的总费用为 ，我们 得到原问题的数学模型2：,模型2的初步结论,在单价图上,我们尽量找下方的函数使得目标函数最小。根据观察,我们可以初步得到下面的结论： (1)在区间0,2600上，f1,f2,f3的取值要小于其它的函数，因此S1,S2,S3应满负荷生产。 (这三个厂的最高产量为8008001000),(2)在区间3300,5171(近似)上，除去最右端的一小段，最小的函数是f5,f6，因此这一段由S5,S6提供钢管。 由于在区间2600,3550(近似)上，这两个函数相等，存

12、在最优解，使得这两个厂都不是满负荷生产。 (3)f4下方的厂家可以提供足够的产量，因此 S4 的产量为零。 (4)在区间0,4950上(近似)，f6f7,因此由S6提供钢管比由S7提供节省，因此S7 的产量为零.,松弛模型,为讨论方便，我们给出下面的模型3,该模型放宽了模型2的约束条件，从而扩大了可行域.显然如果该模型的最优解在模型2 的可行域内，则它必是模型2的最优解；反之，模型2的最优解必是模型3的可行解。 记 为模型3的一个最优解。,差价控制定理,在Aj与Aj+1之间任一点 处，Sm与Sn的钢管单价之差 一定位于两厂在Aj的差价j与两厂 在Aj1的差价j1之间。 其中： 该定理的只需用

13、的表达式直接证明。,的图形,定理1,证明思路：由于 ,根据 差价控制定理,在0,5171上有 . 若 ,可以将S4的钢管改由S5提供（注意 到模型3中S5的产量无上限），总费用降低。 从题目中的路线图以及生产价格也可看出上述 结论。,的图形,定理2,证明思路：根据差价控制定理，在区间0,4671上 有 ，再由 的表达式，可以证明 在4671,4826(长度345)上 也有 。 另一方面，可以计算得到， 若 ，则 ，从而 因此可以将S7的钢管改由S6提供，总费用降低。,定理3,s1+s2+s3=2600,在区间0,2600， min(f5, f6)max(f1,f2, f3), 若S1,S2,S

14、3中有一个不是满负荷生产,则在区间0,2600中必然有一段由S5或S6生产.显然不是最优的.,问题:以上的定理是针对模型3(松弛模型,S5,S6的产量没有限制)得到的,那么对模型2(S5,S6的产量有限制,结论是否还成立呢?),模型3模型2?,问题:前面的定理是针对模型3(松弛模型,S5,S6的产量没有限制)得到的,那么对模型2(S5,S6的产量有限制,结论是否还成立呢?),为了解决上述问题,我们只要说明模型3有一个最优解满足模型2的约束.其依据是下面的引理:,对最优化问题minf(x)|xD1与minf(x)|xD2, (D1D2),若minf(x)|xD2的最优解集为T2,且T2D1f,则

15、minf(x)|xD1的最优解集为T2D1,模型的进一步简化,观察单价图可以发现，在3300右边有一点，在这一点的右方最小函数是f5或f6,(不再考虑f7),可以求出该点坐标为3325。我们再将模型3分解为以下的两个模型(下面记J=1,2,3,5,6)。 模型4,模型5 模型4的最优解与模型5的最优解的并集如果是模 型3的可行解，则必是其最优解；反之，模型3的 最优解在3325左右的部分分别是模型4和模型5 的可行解。,模型5的最优解,由于在模型5的 时，f5,f6均小于f1,f2,f3， 因此模型5的最优解可以简单得到。 (长度415) (长度1205) (长度226)中的 部分可任意置于 和 中。,模型4的讨论,在0,2541，f5f6；在2541,3325，f5=f6，因此在讨论模型4时不妨假设 ，此时对于模型4，很容易得到下面的结论：,s1+s2+s3=2600,在区间0,2600(观察下一页的图形)，f5f1, f5f2, f5f3,若S1,S2,S3中有一个不是满负荷生产,则在区间0,2600中必然有一段由S5生产.显然不是最优的.,小结,我们已经证明了下面的结论:,对模型4,存在一满足最优解,对模型5,存在一满足最