基于“LP”的水泥運(yùn)輸問題研究

陶欣

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

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

中圖分類號(hào)：TP273;TU642? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

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

1? 模型的建立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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