第5讲_非线性规划分解.ppt

钢管订购及运输优化模型 2000年“网易杯”全国大学生数学建模竞赛B题 优化模型竞赛题 一、问题重述 要铺设一条输送天然气的主管道A1→A2→…→A15，能生产这种钢管的厂家一共有:S1,S2,…S7 。厂家与管道间的交通网络已知。假设沿管道或者原来有公路，或者建有施工公路。 为方便计算，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si 个单位，钢厂1单位钢管的出厂销价为pi万元，如下表： I 1 2 3 4 5 6 7 SI 800 800 1000 2000 2000 2000 3000 Pi 160 155 155 160 155 150 160 1单位钢管的铁路运价如下表，1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到主管道结点A1,A2,…, A15 ,而是管道全线）。 里程（km） ≤300 301~350 351~400 401~450 451~500 运价（万元） 20 23 26 29 32 里程（km） 501~600 601~700 701~800 801~900 901~1000 运价（万元） 37 44 50 55 60 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。 （2）请就（１）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图（２）的情形给出模型和结果。 需解决的问题： 图1 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图一 二、模型假设 1.沿铺设的主管道以有公路或者有施工公路。 2.在主管道上，每公里卸1单位的钢管。 3.公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算） 4.在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用。 5.在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制。 6.假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管的运价增加5万元。 三、符号说明 四、模型的分析、建立、求解 先看总费用：总费用由三部分组成： 1) 钢管的订购费。 支付钢厂订购钢管的费用。因为钢厂生产单位钢管的出厂销价为常量，所以在运费相同的情况下，应从销价低的钢厂订购钢管。 1. 模型的分析与决策变量的设置 根据题目要求，要制定一个主管道钢管的订购和运输计划，使总费用最小。 2) 把钢管从钢厂运到主管道结点所需的运费。 要注意运输过程中既有铁路，也有公路。 3) 从结点Ai向两边铺设管道的费用。 要注意每个结点分别向左右铺设多少？ 再看订购和运输计划： 所谓订购计划：就是向每个钢厂订购多少钢管。 所谓运输计划：就是将每个钢厂订购的钢管运输到 那些节点？运多少？ 故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管。 故可设：向第i个钢厂订购xi单位钢管，第i个钢厂 运往第j个节点xij单位的钢管 。 故变量xi可以不要，少用7个变量！ 另外，要决定每个结点分别向左右铺设多少？ 第二方案：也可以考虑在Aj左右各设一个变量！ 2.求单位钢管从钢厂运到运输点的最小费用 方法：将图一转换为一个以单位钢管的运输费 用为权的赋权图，再求最短路的权。 由于运输过程中既有铁路，也有公路，且铁路的运费还是分段函数，与全程运输总距离