基于“LP”的水泥运输问题研究

陶欣

摘  要：本文将现实中的混凝土搅拌站水泥运输的路线最优问题，转换成合理的数学模型。一方面先将混凝土搅拌站和各工厂之间的道路连通情况转化成求解最短路径的图论模型，另一方面通过对影响水泥运输成本的各要素分析，确定了关于水泥运输路程和载重的最优化约束模型，然后根据混凝土搅拌站的日产能和各工地的日需求量確定约束条件。最后通过MATLAB软件求解出关于水泥运输和混凝土搅拌站类型选址的最优方案。

关键词：整数规划;Dijkstra算法;最优运输;图论

中图分类号：TP273;TU642      文献标识码：A 文章编号：2096-4706（2019）01-0162-02

Study on Cement Transportation Problem Based on “LP”

TAO Xin

（Zhejiang Wanli University，Ningbo  315000，China）

Abstract：In this paper，the optimal route of cement transportation in concrete mixing station is transformed into a reasonable mathematical model.On the one hand，concrete mixing station and first path connected between each factory into a graph theory model for solving the shortest path，on the other hand，through to the various influence factor analysis of cement transportation cost，determines the optimization constraints on cement transport distance and load model，and then according to the capacity of concrete mixing station and the site daily demand constraint conditions were determined.At last，the optimal selection scheme of concrete transportation and concrete mixing station was solved by MATLAB software.

Keywords：integer programming;Dijkstra algorithm;optimal transportation;graph theory

0  引  言

随着国家经济建设的快速发展，基础工程的建设也在不断推进。水泥混凝土作为其中应用最广泛的建筑材料，需求量日益增加。在道路运输过程和方式中，会不可避免地存在一定的产能浪费。在“LP”（线性规划：Linear Programming）的思路下建立合理的数学模型，找出正确的规划路线，可以在最大程度上减少这一损失。针对混凝土搅拌站水泥运输路线的最优化问题，首先将水泥运输路线转化成求解最短路径的图论模型，接着通过对影响水泥运输成本的各要素分析，确定关于运输路程和载重的最优化约束模型[1]。最后通过MATLAB软件求解出关于水泥运输和混凝土搅拌站类型选址的最优方案。

1  模型的建立

假设水泥运输的成本只与运输的路程和载重有关，每方载重的车辆运输每公里的耗费相等，为a元，不考虑运输车辆返回时的成本，混凝土搅拌站中生产的原料质量相当，价格相同。

1.1  已知混凝土搅拌站的类型

在已知混凝土搅拌站类型的情况下，我们的目标是要找出最优的水泥运输方案，所以先对混凝凝土搅拌站和各工厂之间的道路连通情况和距离数据做预处理，构造出可以求解混凝土搅拌站到各工厂之间最短距离的图论模型，为下文对模型的求解作出铺垫。然后通过搅拌站到工厂的最短距离D和搅拌站运输到各工厂的水泥运输量X，构造最优化的整数规划模型：

在已知20个混凝土搅拌站的类型（1.日产能400方;2.日产能700方;3.日产能900方）和这92个工厂之间的水泥日需求量的情况下，根据混凝土搅拌站的日产能、确定模型的不等式满足条件和各工地的日需求量来确定模型的等式约束条件，最后考虑到实际情况，水泥运输量不能小于0，混凝土搅拌站的日产量一般为整数后，得到下式[2]：

1.2  混凝土搅拌站产能类型不定

虽然混凝土搅拌站日产能类型不确定，但依旧只有三种规格日产能（400方/天，700方/天，900方/天）供我们选择，所以我们的目标是要在找出最优的运输方案的同时，尽量避免浪费产能。于是确定出关于混凝土搅拌站产能浪费的最优化模型：

因为各工厂的日需求量没有发生变化，所以关于等式的约束模型和上文没有差别。由于混凝土搅拌站的建造规格有三种日产能供我们选择，这时我们依然根据混凝土搅拌站的日产能来确定其不等式约束条件：

2  模型的算法实现

首先，根据某市所给出的20个混凝土搅拌站和92个工厂之间的道路连通情况作出无向连通图[3]并作为研究对象。根据所给的道路之间的距离信息，通过Dijkstra算法找到每个混凝土搅拌站到各个工厂之间的最短距离Dij。

2.1  已知混凝土搅拌站产能类型求解

在已知混凝土搅拌站类型的情况下，直接根据最短距离Dij获得目标函数的系数矩阵，通过等式约束条件给出Aeq（等式约束矩阵），不等式约束条件给出Beq（不等式約束矩阵），通过实际情况给出变量的下界矩阵xm。最后通过MATLAB软件中整数规划函数intlinprog（）求解最优化运输方案（部分见表1），以及最优方案在运输过程中需耗费231755.29a元，全市混凝土生产中浪费1720方/天。（模型求解中的所有数据均来源于数模竞赛题目：混凝土搅拌站设置与水泥运输问题）。

2.2  混凝土搅拌站产能类型不定求解

这里采用间接法，先运用混凝土运输最优模型，依然根据最短距离Dij获得目标函数的系数矩阵，通过等式约束条件给出Aeq（等式约束矩阵）。在确定Beq（不等式约束矩阵）时，由于供我们选择的混凝土搅拌站的产能有三种，通过穷举的算法可以实现，但是数据量太大，不易操作。所以这里我们直接假设每一个搅拌站的日产能均为其上线值900方/天进行求解。然后通过实际情况给出变量的下界矩阵xm。最后通过MATLAB软件求解出在最优化运输方案的情况下，各混凝土搅拌站的实际输出量（见表2）。

这时，我们再根据混凝土搅拌站的实际输出量来确定应该建造混凝土搅拌站的类型。只要混凝土搅拌站的实际输出量小于其最接近的日产能（400方/天，700方/天，900方/天），就是混凝土搅拌站类型选址的最优解。此时全市的混凝土搅拌站在生产水泥时的产能浪费为1950方/天，运输过程中的共耗费115091.32a元。现在市面上C35的混凝土价格一般在400元/方，算其生产成本为300元/方。所以这种方案较之前混凝土搅拌站类型选址方案共节省116663.97a-69000元。

3  结  论

求解最短路径的图论模型和关于“LP”的最优化模型是解决最优物流运输方案和物流基站选址的重要模型。模型在构建上简单实用且易于求解，一方面其可以给城市规划选址前期提供一定的指导，另一方面可以帮助物流企业在后期运营时大大节省成本[3]。笔者利用建立的图论模型和整数规划模型提供的最优的运输路线和最佳的类型选址方案，体现了本文研究的实用价值和现实意义。

参考文献：

[1] 卢晓珊.设施选址问题的数学模型与优化算法研究 [D].北京：北京化工大学，2009.

[2] 徐芹.基于Lingo下的线性规划问题——以土地规划问题为例 [J].伊犁师范学院学报（自然科学版），2016，10（1）：21-23.

[3] 李捷承.聚类算法在物流配送中心选址问题中的研究与应用 [D].沈阳：中国科学院大学（中国科学院沈阳计算技术研究所），2018.