钢管的订购和运输

1钢管的订购和运输摘要本文研究了在特定的铁路与公路交通网络情况下，结合工厂与铺设地点的供需限制，对钢管的订购与运输方案进行最优化的问题。通过建立非线性规划的数学模型，设计最小运费算法，得到了相对最优的订购和运输方案与最小总花费，并探究了各工厂的钢管销价与产量上限对订购和运输方案与最小总花费的影响程度。对于问题一，我们对图一的点进行标号，构造关联矩阵，以各点之间的单位钢管运费作为赋权图，运用floyd算法计算得到各工厂到节点的运费最小路径，将工厂沿此路径运输到的钢管数量作为变量，构造了一个非线性规划模型，通过lingo求解得到最小总花费为：（万元）。对于问题二，我们针对每个工厂的销价和生产上限分别上调和下调5%、10%来探究其对总花费和购运计划的影响。我们发现：（1）的销价变化对总费用的影响最大；（2）的销价变化对购运计划的影响最大；（3）工厂生产上限对总费用和购运计划的影响最大。对于问题三，我们按照问题一中的算法得到新的各工厂到节点的运费最小路径，由于加入了新的节点，管道的铺设变成了网状结构，所以我们在问题一模型的基础上增加了新的变量，设计了新的约束条件，通过lingo求解出这个非线性规划模型，得到最小总花费为：（万元）。关键词：floyd算法非线性规划1、问题重述1.1问题背景要铺设一条1521AAA的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有721,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位，钢管出厂销价1单位钢管为ip万元，2如下表：i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。31.2问题提出（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二4（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。2、模型假设及符号说明2.1模型假设（1）钢管在运输和铺设途中没有损耗。（2）所有钢管均由提供。（3）钢管铁路转公路时没有额外费用。2.2符号说明工厂的的生产总量工厂到的总运量工厂到的运输单位数量钢管的价格工厂的生产单价往方向运的钢管数量往方向运的钢管数量运输的总费用生产钢管的总费用运输的总费用铺设管道的总费用到的距离工厂的产量上限0，1变量，表示工厂是否生产到的距离矩阵53、问题一的分析建模与求解3.1问题一的分析本题的要求是制定一个采购和运输计划，使总费用最小，这是一个最优化问题。工厂生产钢管运输到各个节点，再从各个节点处向左右两边铺设管道。在这个问题中，把各个工厂生产运输到各节点的钢管数量作为一个变量。当各工厂运输到各节点钢管数量一定时，各节点的钢管数量就为一个确定值，又由于节点之间里程确定，则铺设方案此时也同时确定。由此可见，将各工厂运输到各节点的钢管数量作为变量对解决这个问题是可行的。3.2模型的建立总费用包含三部分：采购的总费用、运输到节点的总运费、从运往铺设地点的总费用。工厂的总生产量是其运输到各个节点钢管数量的总和，即，则采购的总费用为，即工厂运输钢管到节点的运费为，则各工厂运输到节点的总运费在铺设管道的过程中，对于各个节点，其可以往左铺设也可以往右铺设，铺设时每隔一公里卸下一单位管道，则对于这一段路内，由处往右运输，由处往左运输，则铺设管道的总费用为目标是：限制条件：①铺设总里程的限制：②工厂生产量的限制：6③之间道路的距离限制：④节点的钢管数量限制：⑤初始值限制：;;;;;;⑥其它限制：由图中易知，各工厂要运钢管到必然要经过，为了使费用最低，则可令各工厂运输到节点的钢管数量为0，即段铺设的钢管完全由于提供，于是有以下限制：；。综上所述，对应此问题的非线性规划模型为：目标函数：限制条件：，，，3.3模型的求解3.3.1求单位钢管运输到节点费用最少的路径我们首先把图中各点标号，构造出该图的关联矩阵，按照以下规则构造：两地无直接到达的路径两地可通过铁路直接到达两地可通过公路直接到达把1单位钢管从运到的运输价格作为到的“等效距离”，将此等效距离作为该图的赋权图，运用弗洛伊德算法得到到的等效最短路径，即运输成本最7小的路径，由此得到到的运输单位数量钢管的单价矩阵。如下是具体算法描述：①Floyd算法介绍权矩阵：对于任意一个包含n个点的路线图，将所有点从1到n依次编号，运用一个n*n的矩阵，可以将路线图中所包含的两点间是否有道路直接连接和有道路连接的两点之间的道路里程记录下来。权矩阵)(nnA构建方法为：对于图中任意两点iv和jv，若i与j间有道路相连通（设iv、jv间道路距离为),(jipath），则),()(jijipathA，若i=j,则0)(jiA，若iv与jv间无道路相连通，则)(jiA。构建示例如下：0971290670812680)44(A最短路径通用算法（Floyd算法）：基本思想：初始化)(nnD，令jDji),(，从权矩阵)(nnA出发构建三重循环，对于任意两点iv和jv，依次对两点间插入点kv（nk....3,2,1），若),(),(),(jijkkiAAA，则令),(),(),(jkkijiAAA，且kDji),(。最终),(jiD记录点iv和点jv间的最短路径，),(jiA记录点iv和点jv间最短路径所对应的总长度。②最小运费算法（Floyd算法改进）由于图中两点间的路径既可能存在公路，又可能存在铁路，且铁路运营的计费方式为分段函数，在这里我们要构建四个矩阵)()()()(,,,nnnnnnnnREDC来实现，各矩阵的用途与构建方式如下：:)(nnC用于记录两点间铁路里程，在构建过程中，若点iv和点jv间无铁路4v73v691v122v88直接相连则),(jiC，若点iv=jv，则0),(jiC；:)(nnD用于记录两点间公路里程，在构建过程中，若点iv和点jv间无公路直接相连则),(jiD，若点iv=jv，则0),(jiD；:)(nnE用于记录两点间路径所所对应的运费，在构建过程中，通过已有的)(nnC和)(nnD通过公路和铁路的计费准则得出；)(nnR:用于记录两点间的路径，构建过程中，令jRji),(。算法叙述：从计费矩阵)(nnE出发构建三重循环，对于iv和点jv，依次对两点间插入点kv（nk....3,2,1）。对于插入点kv进行判断，若iv和点kv之间无公路或铁路连接或kv和点jv之间无公路或铁路连接，则跳出当前循环，若iv、kv和jv之间有道路连接，则先通过中间变量LC和LD分别对iv、kv和jv之间铁路和公路的总里程进行记录。记录方式如下：令0,0LDLC若),(kiC，则),(kiCLCLC；),(jkC，则),(jkCLCLC；若),(kiD，则),(kiDLDLD；),(jkD，则),(jkDLDLD；根据铁路和公路的计费准则计算iv、kv和jv之间铁路和公路的费用之和S，若),(jiES，则SEji),(，且令),(),(),(jkkijiCCC，,),(),(),(jkkijiDDDkjiR),(。按照上述算法，用matlab求解得出到的运输成本最小路径，部分路线如图二、图三所示(完整成本最小路径矩阵见附录)。93.3.2求解规划问题该问题为一个非线性规问题，目标函数和限制条件如下目标函数：限制条件：10，，，3.4结果分析利用lingo进行求解得到最小总费用为：1278632在总费用最小情况下各工厂的生产情况：工厂产量80080010000132012510从以上数据可以看到，总费用最小的时候与不提供钢管，原因在于模型中在设置限制条件时有个生产量下限（500单位钢管），这两个工厂因为没有达到该下限所以不提供钢管。各个节点向左右两边铺设钢管的数量：节点向左运向右运节点向左运向右运005051591047532130226282270145468075116069.5199134184.515.5286335189.57616501251754、问题二的求解4.1工厂销价的影响：4.1.1工厂销价对总花费的影响我们在问题一的模型基础上，先对各个工厂的销价上调5％和10％，比较变化后的总花费相对于原先总花费的相对变化率。由lingo计算改变销价后的最小花费如下表：销价变化原始价格11上调5%128503128483128638127863128509128484127863127863下调5%127223127243127088127863126112126566127566上调10%129143129103129413127863128836128964127863下调10%126583126623126313127588125672125066127166其对应的相对原始价格之差：单价变化上调5%64062077506466210下调5%-640-620-7750-1751-1297-297上调10%128012401550097311010下调10%-1280-1240-1550-275-2191-2797-697总影响（绝对值之和）38403720465027555615816994由以上数据可以看出，当销价上调5%和10%时，销价的调整对总费用影响程度最大；当销价下调5%时，对总费用影响程度最大；当销价下调10%时，对总费用影响程度最大。综合来看其影响程度，知的销价变化对总费用的影响程度最大。从实际情况来看，的销价在7个工厂中是最低的，而且其供应量又较大，所以显然其销价的改变对总费用影响程度较大，说明我们计算得到的结论是合理的，从而间接证明了我们模型的正确性。4.1.2工厂销价对购运计划的影响当工厂的销价改变时，会影响这个工厂的需求量，即会引起各个工厂生产量变化。记改变销价后工厂生产量为，令，当我们改变各个工厂销价时，只需比较的大小即可，值大的对