基于“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元?，F在市面上C35的混凝土價格一般在400元/方，算其生產成本為300元/方。所以這種方案較之前混凝土攪拌站類型選址方案共節省116663.97a-69000元。

3? 結? 論

求解最短路徑的圖論模型和關于“LP”的最優化模型是解決最優物流運輸方案和物流基站選址的重要模型。模型在構建上簡單實用且易于求解，一方面其可以給城市規劃選址前期提供一定的指導，另一方面可以幫助物流企業在后期運營時大大節省成本[3]。筆者利用建立的圖論模型和整數規劃模型提供的最優的運輸路線和最佳的類型選址方案，體現了本文研究的實用價值和現實意義。

參考文獻：

[1] 盧曉珊.設施選址問題的數學模型與優化算法研究 [D].北京：北京化工大學，2009.

[2] 徐芹.基于Lingo下的線性規劃問題——以土地規劃問題為例 [J].伊犁師范學院學報（自然科學版），2016，10（1）：21-23.

[3] 李捷承.聚類算法在物流配送中心選址問題中的研究與應用 [D].沈陽：中國科學院大學（中國科學院沈陽計算技術研究所），2018.