陶欣

摘? 要：本文將現(xiàn)實中的混凝土攪拌站水泥運輸?shù)穆肪€最優(yōu)問題，轉(zhuǎn)換成合理的數(shù)學(xué)模型。一方面先將混凝土攪拌站和各工廠之間的道路連通情況轉(zhuǎn)化成求解最短路徑的圖論模型，另一方面通過對影響水泥運輸成本的各要素分析，確定了關(guān)于水泥運輸路程和載重的最優(yōu)化約束模型，然后根據(jù)混凝土攪拌站的日產(chǎn)能和各工地的日需求量確定約束條件。最后通過MATLAB軟件求解出關(guān)于水泥運輸和混凝土攪拌站類型選址的最優(yōu)方案。

關(guān)鍵詞：整數(shù)規(guī)劃;Dijkstra算法;最優(yōu)運輸;圖論

中圖分類號：TP273;TU642? ? ? 文獻標(biāo)識碼：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? 引? 言

隨著國家經(jīng)濟建設(shè)的快速發(fā)展，基礎(chǔ)工程的建設(shè)也在不斷推進。水泥混凝土作為其中應(yīng)用最廣泛的建筑材料，需求量日益增加。在道路運輸過程和方式中，會不可避免地存在一定的產(chǎn)能浪費。在“LP”（線性規(guī)劃：Linear Programming）的思路下建立合理的數(shù)學(xué)模型，找出正確的規(guī)劃路線，可以在最大程度上減少這一損失。針對混凝土攪拌站水泥運輸路線的最優(yōu)化問題，首先將水泥運輸路線轉(zhuǎn)化成求解最短路徑的圖論模型，接著通過對影響水泥運輸成本的各要素分析，確定關(guān)于運輸路程和載重的最優(yōu)化約束模型[1]。最后通過MATLAB軟件求解出關(guān)于水泥運輸和混凝土攪拌站類型選址的最優(yōu)方案。

1? 模型的建立

假設(shè)水泥運輸?shù)某杀局慌c運輸?shù)穆烦毯洼d重有關(guān)，每方載重的車輛運輸每公里的耗費相等，為a元，不考慮運輸車輛返回時的成本，混凝土攪拌站中生產(chǎn)的原料質(zhì)量相當(dāng)，價格相同。

1.1? 已知混凝土攪拌站的類型

在已知混凝土攪拌站類型的情況下，我們的目標(biāo)是要找出最優(yōu)的水泥運輸方案，所以先對混凝凝土攪拌站和各工廠之間的道路連通情況和距離數(shù)據(jù)做預(yù)處理，構(gòu)造出可以求解混凝土攪拌站到各工廠之間最短距離的圖論模型，為下文對模型的求解作出鋪墊。然后通過攪拌站到工廠的最短距離D和攪拌站運輸?shù)礁鞴S的水泥運輸量X，構(gòu)造最優(yōu)化的整數(shù)規(guī)劃模型：

在已知20個混凝土攪拌站的類型（1.日產(chǎn)能400方;2.日產(chǎn)能700方;3.日產(chǎn)能900方）和這92個工廠之間的水泥日需求量的情況下，根據(jù)混凝土攪拌站的日產(chǎn)能、確定模型的不等式滿足條件和各工地的日需求量來確定模型的等式約束條件，最后考慮到實際情況，水泥運輸量不能小于0，混凝土攪拌站的日產(chǎn)量一般為整數(shù)后，得到下式[2]：

1.2? 混凝土攪拌站產(chǎn)能類型不定

雖然混凝土攪拌站日產(chǎn)能類型不確定，但依舊只有三種規(guī)格日產(chǎn)能（400方/天，700方/天，900方/天）供我們選擇，所以我們的目標(biāo)是要在找出最優(yōu)的運輸方案的同時，盡量避免浪費產(chǎn)能。于是確定出關(guān)于混凝土攪拌站產(chǎn)能浪費的最優(yōu)化模型：

因為各工廠的日需求量沒有發(fā)生變化，所以關(guān)于等式的約束模型和上文沒有差別。由于混凝土攪拌站的建造規(guī)格有三種日產(chǎn)能供我們選擇，這時我們依然根據(jù)混凝土攪拌站的日產(chǎn)能來確定其不等式約束條件：

2? 模型的算法實現(xiàn)

首先，根據(jù)某市所給出的20個混凝土攪拌站和92個工廠之間的道路連通情況作出無向連通圖[3]并作為研究對象。根據(jù)所給的道路之間的距離信息，通過Dijkstra算法找到每個混凝土攪拌站到各個工廠之間的最短距離Dij。

2.1? 已知混凝土攪拌站產(chǎn)能類型求解

在已知混凝土攪拌站類型的情況下，直接根據(jù)最短距離Dij獲得目標(biāo)函數(shù)的系數(shù)矩陣，通過等式約束條件給出Aeq（等式約束矩陣），不等式約束條件給出Beq（不等式約束矩陣），通過實際情況給出變量的下界矩陣xm。最后通過MATLAB軟件中整數(shù)規(guī)劃函數(shù)intlinprog（）求解最優(yōu)化運輸方案（部分見表1），以及最優(yōu)方案在運輸過程中需耗費231755.29a元，全市混凝土生產(chǎn)中浪費1720方/天。（模型求解中的所有數(shù)據(jù)均來源于數(shù)模競賽題目：混凝土攪拌站設(shè)置與水泥運輸問題）。

2.2? 混凝土攪拌站產(chǎn)能類型不定求解

這里采用間接法，先運用混凝土運輸最優(yōu)模型，依然根據(jù)最短距離Dij獲得目標(biāo)函數(shù)的系數(shù)矩陣，通過等式約束條件給出Aeq（等式約束矩陣）。在確定Beq（不等式約束矩陣）時，由于供我們選擇的混凝土攪拌站的產(chǎn)能有三種，通過窮舉的算法可以實現(xiàn)，但是數(shù)據(jù)量太大，不易操作。所以這里我們直接假設(shè)每一個攪拌站的日產(chǎn)能均為其上線值900方/天進行求解。然后通過實際情況給出變量的下界矩陣xm。最后通過MATLAB軟件求解出在最優(yōu)化運輸方案的情況下，各混凝土攪拌站的實際輸出量（見表2）。

這時，我們再根據(jù)混凝土攪拌站的實際輸出量來確定應(yīng)該建造混凝土攪拌站的類型。只要混凝土攪拌站的實際輸出量小于其最接近的日產(chǎn)能（400方/天，700方/天，900方/天），就是混凝土攪拌站類型選址的最優(yōu)解。此時全市的混凝土攪拌站在生產(chǎn)水泥時的產(chǎn)能浪費為1950方/天，運輸過程中的共耗費115091.32a元。現(xiàn)在市面上C35的混凝土價格一般在400元/方，算其生產(chǎn)成本為300元/方。所以這種方案較之前混凝土攪拌站類型選址方案共節(jié)省116663.97a-69000元。

3? 結(jié)? 論

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

參考文獻：

[1] 盧曉珊.設(shè)施選址問題的數(shù)學(xué)模型與優(yōu)化算法研究 [D].北京：北京化工大學(xué)，2009.

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

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