天然气管道订购与运输摘要本文就使西气东输二线工程制定钢管的订购和运输方案总费用最小模型先 针对特殊情况,即铺设管道呈一条线的情行，计算出钢管从钢厂经单位运费最小 路径运输到施工节点的运输费用矩阵 ,建立了钢管订购和运输问题的带有 01 整数约束的二次规划模型 ,从而找到了钢管订购和运输的最优方案，并利用Lingo软件编程求出最小费用为1278632万元。通过灵敏度分析得出钢厂S的销6价变化对目标函数影响最大，钢厂S产量上限的变化对目标函数影响最大，且S11的产量上限每增加一个单位，目标函数就减少1 3 2万元.对于铺设管道成树形图的一般情形，我们将树形图转化为有向图，建立了与 铺设管道为一条线时类似的数学模型,经计算得最小费用为1406631万元。 关键字：钢管订购与运输，0-1 规划，二次规划模型,灵敏度分析,有向图一、问题的提出要铺设一条从A到A的天然气管道，经筛选可以生产我们所需要的钢管的1 15钢厂有S到S。由于生产能力的不同，每个钢厂在指定期限内能生产的钢管最 17大数量如表所示。一个钢厂若要承担制造这种钢管要求我们至少订购 500个单位 钢管(1km主管道钢管称为1单位钢管)不同钢厂出售1单位钢管的价格如表 所示。钢管订购后可经铁路，公路运输到要铺设的管道全线。试建立数学模型， 制定钢管的订购及运输计划，使总费用最小。在所建立模型的基础上分析哪个钢 厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限 的变化对购运计划和总费用的影响最大，给出相应的数字结果并就更一般的情 形(即所要铺设的管道成树形:铁路，公路，管道构成网络)给出一种解决办法， 建立模型，给出结果。二、符号说明2.1模型一、二的符号说明S :第i个钢厂(i = 1,2,异)；iA :第j个施工节点(j = 1,2,.,15);js :钢厂S在指定期限内能生产该种钢管的最大数量;iia ：一单位钢管从厂 S 运到施工节点 A 的最小运费； ij i jp :钢厂S出售一单位钢管的价格；iix :钢厂 S 运往施工节点 A 的钢管单位数；ij i jm :全部钢厂运往施工节点 A 的钢管总量； jjd :施工节点 A 到 A 的路程;jjj+ll :从施工节点 A 向左铺设的长度； jjr :从施工节点 A 向右铺设的长度； jjQ :该项工程所需的总费用。2。2模型三的符号说明S :第i个钢厂(i二1,2,异)；iA :第j个施工节点(j = 1,2-.,15)；js :钢厂S在指定期限内能生产该种钢管的最大数量;iia ：一单位钢管从厂 S 运到施工节点 A 的最小运费; ijijp :钢厂S出售一单位钢管的价格； iix ：钢厂 S 运往施工节点 A 的钢管单位数；ijijm ：全部钢厂运往施工节点 A 的钢管总量； jjd ：施工节点 A 到 A 的路程；jkjkr ：从施工节点 A 向右铺设的长度；jjz :运抵A的所有钢管沿A T A铺设的里程数；jkjjkd(A ):树中 A 的度数；jjd-(A ):树中A的入度；jjd + (A ):树中A的出度；jjQ ：该项工程所需的总费用。三、模型假设1、不考虑火车运载和汽车运载的装卸费用； 2、沿铺设管道边或者原来有公路,或者建有施工公路，可以运送所需钢管；3、管道衔接紧密，即要铺设的管道线路总长为钢管总长；4、不考虑其他外界因素对总费用的影响；5、在指定期间内钢管的价格不变，且指定期限即为该工程花费的总时间；6、将一单位管道所在地看成一个需求点，向一单位管道运输钢管即为向一个点 运输钢管.四、问题的分析对于本模型的求解，我们可以把总费用分成三部分考虑:钢管订购费用、钢管 从钢厂经单位运费最小路运至结点的运输费用、钢管在施工线路上铺设费用。 4.1、 对钢管购买费用函数的分析钢管在各个厂订购的费用是于x p，故购买钢管所花费的总费用是ij ij=2京 15 x p。ij ii=1 j=24。2、对公路和铁路运费函数的分析 由于公路运费函数是运输里程的线性函数，具有可加性。铁路运费函数是运 输里程的分段函数，铁路和公路组成的混合交通网的费用函数具有不可加性。所 以,不能直接利用 Dijkstra 和 Floyd 等最短路算法来求最小购运费用矩阵。因 此，在求解这个问题时，关键是要找到从钢厂到结点的路径，从本题图中可以看到从钢厂直接到结点A没有路径可走，到A和A分别有两条路径可走，到其他1714路径只有一条路径可走。而本题并不复杂，故可用笔算方法分别算出由钢厂S经 i单位运费最小路运至结点 A 的运输费用。对于有两条路径可选的情况，分别计j算出运费并取其最小值即可.4.3、 对钢管铺设过程中运费函数的分析在A至A路段，由于钢管必须经过A才能到达A，因此可不考虑A，在A1 2 2 1 1 2至 A 的路段任取一点 u （长度为一公里），我们需要确定的是通过哪个结点运至 15u 点使得总运费（包括钢管购买费用、公路铁路运输费用和铺设过程运输费用）最小。结合分析2中得到的数据表格：若u e （A , A ），若j丰3,4，那么u通过A j j+ij或A 两点，费用最小。若j二3,4，那么u分别通过A , A铺设u点会更合适，即 j+13 5从每个结点A （除了 A , A ）向两边运输最优.j14五、模型的建立与求解5.1问题一的模型建立与求解5.1.1 模型建立计算4.2中的钢厂S经单位运费最小路径运至结点A的运输费用，得到从Siji到A的最小运费矩阵A（a ），最小运费矩阵如下表jijaijA2A3A5A6A7A8A9A10A11A12A13A14A15SI160.3140 o 23820 o 53.121.264 o 29296106121.2128142S2205.3190.211195.588.171.2114.2142146156171。2178192S3220.3200 o 2121105.598 o 186 o 248.2828696111.2118132S4250.3235 o 2156140 o 5133.1116.284.262516176 o 28397S5245 o 3225 o 2146130.5123 d111.279 o 257335171.27387S6255 o 3235.2156140 o 5133。1121.284.262514526.21128S7265 o 3245 o 2166150.5143.1131o299.277665638.2262表一：最小运费矩阵列表在模型的分析中我们已经得到了购买钢管的总费用迟x p，钢管从钢厂运ij ij=2到结点的总费用工艺x p，由于在每个结点处向两边同时铺设，向左边每铺设 ij ii=1 j=2一千米卸下一单位钢管，故在该结点向左边铺设钢管的总费用是0.051 G +1 ）,jj同理向右边铺设钢 管的总费用是0.05r G + r），所以铺设管道的总费 用即jj目标函数为0.05迟1 (1 +1 )+ r G + r ” ,L j j j jj=2min Q =i=1 j=2xpij i+工工x a +0.05国ij iji=1 j =2j =21 (1 +1 )+ r (1 + r )1jjjj 1）总量，即在每个结点向左铺设的路程 1 与向右铺设的路程 r 的和应该等于该结点处钢 jj2）1 + r = i xj jiji=1在结点A向左铺设的路程1加上在结点A向右铺设的路程r应该等于A到jjjTj-1A的路程m，即j-1j1 + r = m (j 丰 15) jj -1j（3）由于结点A，A都不向右铺设，故结点A向右铺设的量r应该等于结点A到A1152212的路程104,结点A向右铺设的量r应该等于0,即1515r = 104 ， r = 0（4）215每个钢厂S提供的钢管量兰x必须大于等于500个单位且不超过钢厂的最大产 iijj=2量s或者是0，即i500 1L x s 或者迟 x = 0 (*)ij iijj=2j=2此处可采用01整数规划，即设ci1,从钢厂S购钢管i0,不从钢厂S购钢管i则表达式*可改为500c 国 x s - ciij i ij=2所以该题所建立的数学模型是：5）目标函数min Q =i =1 j=2xpij i+i7 i15x a +0.05iij ij6）i=1 j=2j=2l + r =工 x (i = 1,2,7.j 2,3 *15) j jji1l + r m (j 主 15)jj+ijs.t r 104, r 0 215500ci 艺 x s - cij i i j2c 0,1i5.1.2 模型求解以上得到的模型属于有 01 规划的二次规划模型，我们利用 Lingo 软件求 解得到最优解为 1278632 万元.并且得到订购和调运方案，如表二S1S2S3S4S5S6S7A2017900000179A3028913808100508A5335321980519001084A6200000000200A7265000000265A8030000000300A9006640000664A10000035100351A11000041500415A120000086086A13000003330333A14000006210621A15000001650165订购量800800100001366120505171表二：订购和调运方案5A12AllA10图一：路线图1具体调运方案：A1不向任何厂订购；A2向S2订购179单位钢管，路线为:S2fifdfbfaA2.A3向S2订购289单位钢管，路线为：S2fifdf