数学模型——钢管订购和运输.doc

钢管订购和运输一、 问题提出要铺设一条 的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有S1,S2,.,S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si 在指定期限内能生产该钢管的最大数量为si 个单位，钢管出厂销价1单位钢管为pi 万元，如下表：I1234567si80080010002000200020003000Pi1601551551601551501601单位钢管的铁路运价如下表：里程300301350351400401500451500运价（万元）2023262932里程（km）5016006017007018008019009011000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点A1,A2,.,A15 ，而是管道全线）。（1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2） 请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。二、 模型假设1. 只考虑订购费用和运输费用，不考虑装卸等其他费用。2. 要铺设的管道侧有公路，可运输所需钢管。3. 钢管单价与订购量、订购次数、订购日期无关。4. 订购假话是指对每个厂商的订货数量；运输方案是指具有如下属性的一批记录：管道区间、供应厂商、具体运输路线。5. 将每一单位的管道所在地看成一个需求点，向以单位管道的所在地运输钢管即向一个点运输钢管。6. 钢管在运送和使用中没有损耗。三、 符号说明符号说明m钢厂数n管网中的结点数r要铺设的单位管道总数d公路上一单位钢管的每公里运费（0.1万元）W订购钢管、运输的总费用（单位：万元）Si第i个钢厂si第i个钢厂最大生产钢管数Ai管道线上第i个节点Yj运送到Aj向Aj-1铺设的管道数Zj运送到Aj向Aj+1铺设的管道数pi第i个钢厂每单位钢管的售价cij一个单位钢管从钢厂Si到管网节点Aj的最小运价tjk管网上相邻节点Aj与Ak之间的边长AjAk（里程数）Tj等于AjAj+1路段的总长度（即钢管数）eih表示钢厂Si到编号为h这一段的最低费用（包括订购费用和运输费用）zihsi到Aj的总钢管运量四、 问题分析l 对于问题I的分析整个铺设管道的工程看似错综复杂，其实可以分为三个部分：（1） 各个工厂（Si）生产一定数量的钢管；（2） 把钢管从工厂（Si）运送到铺设管道的关节点（Ai）；（3） 从关节点（Ai）将管道运输至铺设地点；其中：（1） 购买钢管的费用只与向各钢厂订购刚钢管的数量有关，与运输路线无关，只需求出最终各工厂生产多少单位钢管并乘以相应单价即可（后面需考虑每个工厂最小生产数量及最大生产数量）；（2） 我们需要求出个钢厂到各个火车站的最短里程（这里涉及最短路径的求解，我们可以使用Dijkstra算法或Floyd算法进行求解，在题目简单的情况下我们也可以口算求解，在这里我们使用Floyd算法进行最短路径的求解），再根据铁路运价得到每单位钢管由钢厂到火车站的最低运价。用类似方法也可以的得到火车站到个管网节点的最低运价，将这两者结合起来即可得到每单位钢管从某钢厂到某铺设点运输单位钢管的最少运输费用cij。（3） 从关节点（Ai）将管道运输至铺设地点，每个关节点须向Aj-1和Aj+1两个方向运输和铺设。将这三部分的费用做加和即得到第一问中所求的最小总费用。l 对于问题II的分析通过问题一里面Lingo编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。l 对于问题III的分析利用同问题I同样的方法，从而可求出某钢厂到某某铺设点运输单位钢管的最少运输费用。五、 模型建立与求解1) 模型建立问题I模型：如上文分析所述，我们采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，具体数据如下表：表1 单位钢管从运输到的最小费用(包括生产)（单位：万元）目标函数是总费用W , 它包含三项: 钢管出厂总价Q , 运输费P , 及铺设费T. 即W = Q + P + T其中 ， ， 铺设费T可以如下来确定：开始从左右两个方向铺设，与单位长钢管的费用为 + ，于是最小费用可表示为： 约束条件为:生产能力的限制: ， 运到的总钢管数: ， 与之间的钢管: ， 变量非负性限制:, 其它限制：Z15=0， Y2=104故问题一的模型为：s.t. ， ， ， =0 , =104 ， =0, =0或1 (i=1,.,7) d=0.05; 2) 数值求解1. 根据模型计算得出，工厂4没有运出货物，需要被淘汰2. 工厂7得出的结果大于0小于500需要求在1的条件下求没有工厂7，和有工厂7且的结果较，的出来的较小的成本，即为最优解。经计算没有工厂4和7的结果是最优的结果为1279977.万元初始求解lingo代码为：MODEL:Title 钢管;sets:supply/1.7/: s,p; ! 工厂，s表示工厂最大生产量，p表示售价;demand/1.14/: a,tt,ww; ! 公路,y表示公路点收到的钢管辆，a表示公路段长度，tt（i）表示从第i+1公路点向左运输的量，ww（i）表示从第i公路点向有运输的iang;link(supply,demand):c,t,w,x; !x表示第i工厂到第j公路点的运输量，但是x无法求出，SB Lingo说我变量太多不能求了，就没求x，t（i）表示第i+1公路点向左运输量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, 410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257, 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178, 425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,2000,2000,2000,3000;p= 160,155,155,160,155,150,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因该是第i工厂到所有公路点的运输量小于工厂的最大生产量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工厂运到第j公路点的钢管（向左运输的） = 第j公路点向做运输的量;FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 换成向右的;FOR( demand(j): tt(j) = a(j) ); !每个公路点向左的运输量小于左端公路长度;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 从右端点运来的 + 从左端点运来的 = 该段长度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);end没有工厂4和没有工厂7的代码：MODEL:Title 钢管;sets:supply/1.5/: s,p; ! 工厂，s表示工厂最大生产量，p表示售价;demand/1.14/: a,tt,ww; ! 公路,y表示公路点收到的钢管辆，a表示公路段长度，tt（i）表示从第i+1公路点向左运输的量，ww（i）表示从第i公路点向有运输的iang;link(supply,demand):c,t,w,x; !x表示第i工厂到第j公路点的运输量，但是x无法求出，SB Lingo说我变量太多不能求了，就没求x，t（i）表示第i+1公路点向左运输量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, !410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257,; 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178; !425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,!2000,;2000,2000;!,3000;p= 160,155,155,!160,;155,150;!,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因该是第i工厂到所有公路点的运输量小于工厂的最大生产量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工厂运到第j公路点的钢管（向左运输的） = 第j公路点向做运输的量;FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 换成向右的;FOR( demand(j): tt(j) = a(j) ); !每个公路点向左的运输量小于左端公路长度;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 从右端点运来的 + 从左端点运来的 = 该段长度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);End结果为：1279977.万元没有工厂4且工厂7的生产量大于500代码：MODEL:Title 钢管;sets:supply/1.6/: s,p; ! 工厂，s表示工厂最大生产量，p表示售价;demand/1.14/: a,tt,ww; ! 公路,y表示公路点收到的钢管辆，a表示公路段长度，tt（i）表示从第i+1公路点向左运输的量，ww（i）表示从第i公路点向有运输的iang;link(supply,demand):c,t,w,x; !x表示第i工厂到第j公路点的运输量，但是x无法求出，SB Lingo说我变量太多不能求了，就没求x，t（i）表示第i+1公路点向左运输量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, !410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257,; 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178, 425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,!2000,;2000,2000,3000;p= 160,155,155,!160,;155,150,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因该是第i工厂到所有公路点的运输量小于工厂的最大生产量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工厂运到第j公路点的钢管（向左运输的） = 第j公路点向做运输的量;FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 换成向右的;FOR( demand(j): tt(j) = 500;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 从右端点运来的 + 从左端点运来的 = 该段长度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);end结果为： 281006.万元最终lingo显示结果为： Local optimal solution found. Objective value: 1279977. Infeasibilities: 0.2842171E-13 Total solver iterations: 89 Model Title: 钢管 Variable Value Reduced Cost S( 1) 800.0000 0.000000 S( 2) 800.0000 0.000000 S( 3) 1000.000 0.000000 S( 4) 2000.000 0.000000 S( 5) 2000.000 0.000000 P( 1) 160.0000 0.000000 P( 2) 155.0000 0.000000 P( 3) 155.0000 0.000000 P( 4) 155.0000 0.000000 P( 5) 150.0000 0.000000 A( 1) 104.0000 0.000000 A( 2) 301.0000 0.000000 A( 3) 750.0000 0.000000 A( 4) 606.0000 0.000000 A( 5) 194.0000 0.000000 A( 6) 205.0000 0.000000 A( 7) 201.0000 0.000000 A( 8) 680.0000 0.000000 A( 9) 480.0000 0.000000 A( 10) 300.0000 0.000000 A( 11) 220.0000 0.000000 A( 12) 210.0000 0.000000 A( 13) 420.0000 0.000000 A( 14) 500.0000 0.000000 TT( 1) 104.0000 0.000000 TT( 2) 226.0000 0.000000 TT( 3) 468.0000 0.000000 TT( 4) 606.0000 0.000000 TT( 5) 184.5000 0.000000 TT( 6) 190.0000 0.000000 TT( 7) 99.50000 0.000000 TT( 8) 530.0000 0.000000 TT( 9) 321.0000 0.000000 TT( 10) 270.0000 0.000000 TT( 11) 75.00000 0.000000 TT( 12) 199.0000 0.000000 TT( 13) 286.0000 0.000000 TT( 14) 165.0000 0.000000 WW( 1) 75.00000 0.000000 WW( 2) 282.0000 0.000000 WW( 3) 0.000000 0.000000 WW( 4) 9.500000 0.000000 WW( 5) 15.00000 0.000000 WW( 6) 101.5000 0.000000 WW( 7) 150.0000 0.000000 WW( 8) 159.0000 0.000000 WW( 9) 30.00000 0.000000 WW( 10) 145.0000 0.000000 WW( 11) 11.00000 0.000000 WW( 12) 134.0000 0.000000 WW( 13) 335.0000 0.000000 WW( 14) 0.000000 0.000000 C( 1, 1) 320.3000 0.000000 C( 1, 2) 300.2000 0.000000 C( 1, 3) 258.6000 0.000000 C( 1, 4) 198.0000 0.000000 C( 1, 5) 180.5000 0.000000 C( 1, 6) 163.0000 0.000000 C( 1, 7) 181.2000 0.000000 C( 1, 8) 224.2000 0.000000 C( 1, 9) 252.0000 0.000000 C( 1, 10) 256.0000 0.000000 C( 1, 11) 266.0000 0.000000 C( 1, 12) 281.2000 0.000000 C( 1, 13) 288.0000 0.000000 C( 1, 14) 302.0000 0.000000 C( 2, 1) 360.3000 0.000000 C( 2, 2) 345.2000 0.000000 C( 2, 3) 326.6000 0.000000 C( 2, 4) 266.0000 0.000000 C( 2, 5) 250.5000 0.000000 C( 2, 6) 241.0000 0.000000 C( 2, 7) 266.2000 0.000000 C( 2, 8) 269.2000 0.000000 C( 2, 9) 297.0000 0.000000 C( 2, 10) 301.0000 0.000000 C( 2, 11) 311.0000 0.000000 C( 2, 12) 326.2000 0.000000 C( 2, 13) 333.0000 0.000000 C( 2, 14) 347.0000 0.000000 C( 3, 1) 375.3000 0.000000 C( 3, 2) 355.2000 0.000000 C( 3, 3) 336.6000 0.000000 C( 3, 4) 276.0000 0.000000 C( 3, 5) 260.5000 0.000000 C( 3, 6) 251.0000 0.000000 C( 3, 7) 241.2000 0.000000 C( 3, 8) 203.2000 0.000000 C( 3, 9) 237.0000 0.000000 C( 3, 10) 241.0000 0.000000 C( 3, 11) 251.0000 0.000000 C( 3, 12) 266.2000 0.000000 C( 3, 13) 273.0000 0.000000 C( 3, 14) 287.0000 0.000000 C( 4, 1) 400.3000 0.000000 C( 4, 2) 380.2000 0.000000 C( 4, 3) 361.6000 0.000000 C( 4, 4) 301.0000 0.000000 C( 4, 5) 285.5000 0.000000 C( 4, 6) 276.0000 0.000000 C( 4, 7) 266.2000 0.000000 C( 4, 8) 234.2000 0.000000 C( 4, 9) 212.0000 0.000000 C( 4, 10) 188.0000 0.000000 C( 4, 11) 206.0000 0.000000 C( 4, 12) 226.2000 0.000000 C( 4, 13) 228.0000 0.000000 C( 4, 14) 242.0000 0.000000 C( 5, 1) 405.3000 0.000000 C( 5, 2) 385.2000 0.000000 C( 5, 3) 366.6000 0.000000 C( 5, 4) 306.0000 0.000000 C( 5, 5) 290.5000 0.000000 C( 5, 6) 281.0000 0.000000 C( 5, 7) 271.2000 0.000000 C( 5, 8) 234.2000 0.000000 C( 5, 9) 212.0000 0.000000 C( 5, 10) 201.0000 0.000000 C( 5, 11) 195.0000 0.000000 C( 5, 12) 176.2000 0.000000 C( 5, 13) 161.0000 0.000000 C( 5, 14) 178.0000 0.000000 T( 1, 1) 0.000000 28.00000 T( 1, 2) 0.000000 23.00000 T( 1, 3