王 妍 朱家明 王欣宇 張一鳴

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

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

1.數(shù)據(jù)來源與模型假設(shè)

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

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

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

2.研究思路

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

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

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

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

graph test{

//基地著色藍(lán)

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 蔬菜運(yùn)輸平面圖

4.模型的建立與求解

4.1 模型Ⅰ：最短距離模型

4.1.1 Floyd算法簡介

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

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

4.1 .2模型的求解

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

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

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

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

4.2.1 建模準(zhǔn)備

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

表2 蔬菜種植基地的日供應(yīng)量（噸/天）

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

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

（1）短缺補(bǔ)償和運(yùn)費補(bǔ)貼最小。

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

b,i分別表示生產(chǎn)基地與銷售站，Xbi表示生產(chǎn)基地到銷售點的距離，Xbi表示各生產(chǎn)基地對銷售點的蔬菜供給量，C表示每噸每公里運(yùn)費補(bǔ)貼標(biāo)準(zhǔn)。

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

約束條件有：基地b對銷售點的日供應(yīng)量不大于基地b的日產(chǎn)量；基地對銷售點i的日供應(yīng)量不大于銷售點i的日需求量；基地b對銷售點i的日供應(yīng)量不小于0。

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

上式中Sb表示基地b的日產(chǎn)量。

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

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

代入短缺補(bǔ)償和運(yùn)費補(bǔ)貼的數(shù)值，我們可以計算得出，目標(biāo)函數(shù)最小費用為42836.28元。

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

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

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

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（單位：噸）

代入短缺補(bǔ)償和運(yùn)費補(bǔ)貼的數(shù)值，我們可以計算得出，目標(biāo)函數(shù)最小費用為50478.69元。

5.結(jié)論

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

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

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

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

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

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