基于Floyd算法對蔬菜運送方案的最優(yōu)分析

王 妍 朱家明 王欣宇 張一鳴

（1.安徽財經大學統(tǒng)計與應用數學學院，安徽 蚌埠233030；2.安徽財經大學金融學院，安徽 蚌埠233030）

針對我國居民副食品短缺問題，農業(yè)部于1988年提出建設“菜籃子工程”。其中，蔬菜作為“菜籃子工程”中的主要產品，如何合理分配備受關注。對于一些中小城市，蔬菜種植采取以郊區(qū)和農區(qū)種植為主，結合政府補貼的方式來保障城區(qū)蔬菜的供應[1]。隨著信息與物流技術的日益完善，不斷優(yōu)化城市的蔬菜運輸方案，既能提高城區(qū)蔬菜供應的數量和質量，也能帶動郊區(qū)和農區(qū)菜農種植蔬菜的積極性。本文試圖利用Floyd算法對各蔬菜種植基地、銷售點最短距離進行求解，為提高城市蔬菜物流的綜合經濟效益提供理論基礎。

1.數據來源與模型假設

數據來源于2017年安徽財經大學暑期數學建模模擬題1中附件一：蔬菜種植基地日供應量；附件二：蔬菜銷售點日需求量及短缺補償；附件三：道路交通情況及距離；附件四：蔬菜銷售點對每種蔬菜的需求量。

JG市的人口近90萬，該市在郊區(qū)和農區(qū)建立了8個蔬菜種植基地，承擔全市居民的蔬菜供應任務，每天將蔬菜運送到市區(qū)的35個蔬菜銷售點。市區(qū)有15個主要交通路口，在蔬菜運送的過程中從蔬菜種植基地可以途徑這些交通路口再到達蔬菜銷售點。如果蔬菜銷售點的需求量不能滿足，則市政府要給予一定的短缺補償。同時，市政府還按照蔬菜種植基地供應蔬菜的數量以及路程，發(fā)放相應的運費補貼，以此提高蔬菜種植的積極性，運費補貼標準為0.04元/噸.公里。

針對研究問題，提出以下幾點假設：（1）假設運輸途中不存在蔬菜的損耗，且蔬菜只來源于8個基地，不考慮其他來源；（2）假設每一輛車只運往一個銷售點，到達該銷售點后即折返，不再前往下一個銷售點，且不算折返距離；（3）假設只考慮運輸補貼費用和短缺補償費用，不考慮裝卸費用等其他費用。

2.研究思路

為了便于直觀地反應各蔬菜種植基地、銷售站點和路口之間的距離關系，利用Graphviz繪圖軟件得到蔬菜運輸路線的平面圖。構造鄰接矩陣表示各基地、路口及銷售點的相對位置信息，利用圖論中的Floyd算法，使用MATLAB軟件求出各地點的最短距離，最后利用線性約束思想，通過LINGO軟件編程，求得結果。

3.Graphviz軟件中創(chuàng)建基地銷售點平面圖

根據附件三 （道路交通情況及距離）中的數據，為便于在平面圖上更好地顯示，首先將數據整合成統(tǒng)一形式，將8個蔬菜種植基地命名為Base1~Base8，15個交通路口命名為 Intersec1~Intersec15，35個銷售站點命名為Stand1~Stand35。

利用 Graphviz畫出平面圖，見圖 1（藍色點表示蔬菜種植基地，黃色點表示路口，紅色點表示蔬菜銷售點）。部分程序如下。

graph test{

//基地著色藍

base1[color=blue, style=filled];

base2[color=blue, style=filled];

base3[color=blue, style=filled];

//站點著色紅

stand1[color=red, style=filled];

stand2[color=red, style=filled];

stand3[color=red, style=filled];

//路口著色黃

intersec1[color=yellow, style=filled];

intersec2[color=yellow, style=filled];

intersec3[color=yellow, style=filled];

base1——stand4[lebel="14"];

base1——stand14[lebel="16"];

base1——intersec3[lebel="16"];

圖1 蔬菜運輸平面圖

4.模型的建立與求解

4.1 模型Ⅰ：最短距離模型

4.1.1 Floyd算法簡介

A0為鄰接矩陣，遞推產生一個矩陣序列A0，A1，…，AK，…An，其中 AK(i,j)表示頂點 Vi到 Vj的路徑上所經過的頂點序號不大于K的最短路徑的長度。迭代公式為：

當k=n時，An即是各頂點之間的最短路長度。

4.1 .2模型的求解

由于種植基地、路口和銷售站一共為58個基點，根據Floyd算法，建立58×58的網絡權矩陣，其中D[i][j]表示蔬菜種植基地到銷售點之間的最短距離。

利用MATLAB[2]對相關數據進行迭代，得到種植基地與銷售站的最小距離矩陣，具體數據詳見表1，bi表示蔬菜種植基地，ij表示蔬菜銷售點。

表1 種植基地與銷售點之間的最小距離（單位：km）

4.2 模型Ⅱ：線性規(guī)劃模型

4.2.1 建模準備

下表2表示各種植基地每日的蔬菜供應量，表3表示各蔬菜銷售點的日需求量和短缺補償。

表2 蔬菜種植基地的日供應量（噸/天）

表3 蔬菜銷售點日需求量（噸/天）和短缺補償（元/噸.天）

根據表2和表3中的數據，我們可以直觀地看出，日供應總量ΣT=270（噸/天）小于日需求總量ΣM=360.1（噸/天），所以可以利用線性規(guī)劃問題來求解。在問題一中分為兩個約束條件，下面對兩個約束條件分別進行求解。

（1）短缺補償和運費補貼最小。

設在蔬菜運輸中總的費用為F，政府運輸費用補貼為 F1，短缺補償為 F2，F(xiàn)＝F1＋F2，其中，F(xiàn)1滿足：

b,i分別表示生產基地與銷售站，Xbi表示生產基地到銷售點的距離，Xbi表示各生產基地對銷售點的蔬菜供給量，C表示每噸每公里運費補貼標準。

上式中的1i表示每個銷售點每噸每天的短缺補償，Mi表示銷售點i的蔬菜日需求量。

約束條件有：基地b對銷售點的日供應量不大于基地b的日產量；基地對銷售點i的日供應量不大于銷售點i的日需求量；基地b對銷售點i的日供應量不小于0。

建立線性規(guī)劃模型[3]如下：

上式中Sb表示基地b的日產量。

代入已知數值，用LINGO求解[4]得到結果，鑒于文章篇幅，僅給出部分結果，見表4所示。

表4 蔬菜配送方案I（單位：噸）

代入短缺補償和運費補貼的數值，我們可以計算得出，目標函數最小費用為42836.28元。

（2）短缺量不超過需求量的30%。

在此約束條件下，目標函數沒有發(fā)生變化，建立線性規(guī)劃模型[5]如下：

利用LINGO進行計算，得到計算結果如表5所示。由于文章篇幅限制，下表僅為部分結果。

LINGO編程程序如下：

model:

sets:

jd/1..8/:supply;

xsd/1..35/:need,compensation;

links(jd,xsd):d,x;

endsets

data:

c=0.04;

supply=40,45,30,38,29,35,25,28;

need=6.5,10.2,12,14.3,13,11,14,9.5,10,8.4

,10.5,7,8.5,12,11.6,12.5,13.6,9,7.3,10,12.7

,7.4,6.7,12.5,9.6,15,7.2,8.9,10.3,9,7.7,8,

11.4 ,12.1,10.7;

compensation=710,700,580,600,570,480,500,

610,440,705,610,630,590,490,570,460,530,

640,665,650,580,680,685,560,660,430,540,

620,630,680,695,690,560,520,500;

@ole('C:UsersSTUDesktopjieguo1_2.xlsx',x)=x;

enddata

min=c*@sum(links:d*x)+@sum(xsd(j):(need(j)-

@sum(jd(i):x(i,j)))*compensation(j));

@for(jd(i):@sum(xsd(j):x(i,j))=supply(i));

@for(xsd(j):@sum(jd(i):x(i,j))<=need(j));

@for(xsd(j):need(j)-@sum(jd(i):x(i,j))<=0.3*need(j));

End

表5 蔬菜配送方案 II（單位：噸）

代入短缺補償和運費補貼的數值，我們可以計算得出，目標函數最小費用為50478.69元。

5.結論

本文針對具有現(xiàn)實意義的 “菜籃子工程”中蔬菜配送方案設計問題，運用MATLAB軟件和LINGO軟件編程，操作簡單，效果較好。綜合改進的Floyd算法，按照每一步求解需要靈活選取數據，循序漸進，逐步完善，加快了迭代速度，大大減少運行時間，較好地解決了任意兩點間最短距離問題。線性規(guī)劃模型操作簡便，使用靈活，運用范圍較大，便于推廣。

[1]王一鳴,韓曙.“菜籃子工程”政策的理論與實踐[J].上海財稅,1994(6):7-10.

[2]周炳生.Floyd算法的一個通用程序及在圖論中的應用[J].杭州應用工程技術學院學報,1999(3):1-9.

[3]閔欣.線性規(guī)劃在利潤最大化和成本最小化問題中的應用[J].黑龍江科技信息,2013(21):125-126.

[4]張銀靈.Lingo軟件在運輸問題中的應用研究[J].中國商界(下半月),2010(10):205.

[5]姜啟源,謝金星,葉俊.數學模型:第 3版[M].北京:高等教育出版社,2007.