Floyd與線性規(guī)劃在生產(chǎn)管理中的應(yīng)用
——以“菜籃子工程”的優(yōu)化設(shè)計為例

冮建偉，蔡欣悅，楊鵬輝，朱家明

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

0 引言

我國多年來農(nóng)副產(chǎn)品供不應(yīng)求，至2018年中國已經(jīng)是世界上最大的農(nóng)產(chǎn)品進口國，進口額占全球農(nóng)產(chǎn)品貿(mào)易的十分之一以上.為了緩解這種供不應(yīng)求的矛盾，農(nóng)業(yè)部在1988年就開始提出“菜籃子工程”[1].第一期的工程建立了中央與地方的水產(chǎn)、肉、蛋、奶和蔬菜生產(chǎn)基地及飼料加工、良種繁育等服務(wù)體系，用以保證居民一年四季都有正常的食品供應(yīng).“菜籃子工程”的主要產(chǎn)品是蔬菜，受到了各級政府的重視[2].至1995年，蔬菜種植人均占有量終于達到了世界人均水平.2000年11月在菜籃子產(chǎn)銷體制改革交流會上提出21世紀的“菜籃子工程”主要目標(biāo)任務(wù)：優(yōu)化產(chǎn)業(yè)結(jié)構(gòu)，提高產(chǎn)品質(zhì)量，增加農(nóng)民收入，實現(xiàn)與生態(tài)環(huán)境協(xié)調(diào)發(fā)展，農(nóng)歷提高居民生活質(zhì)量等.在一些中小城市，蔬菜種植是以農(nóng)區(qū)種植為主、郊區(qū)種植為輔，政府補貼保證城區(qū)蔬菜的供應(yīng)能夠滿足需求.如此方式，在提高城區(qū)蔬菜供應(yīng)數(shù)量的同時，還可以帶動郊區(qū)和農(nóng)區(qū)蔬菜種植的積極性[3].

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

數(shù)據(jù)來源于2018年安徽財經(jīng)大學(xué)暑期數(shù)學(xué)建模模擬題.JG市人口將近90萬，該市在農(nóng)區(qū)及郊區(qū)共擁有8個蔬菜種植基地，擔(dān)負起全市居民的蔬菜供應(yīng)的任務(wù)，每天需要將蔬菜運送到35個市區(qū)銷售點.連接產(chǎn)地與銷地的是15個主要的交通路口，蔬菜運輸?shù)能囕v需要途經(jīng)這些路口運往銷售點.政府會按照種植基地供應(yīng)蔬菜的數(shù)量和運輸路程，給予相應(yīng)的運費補貼，如果某一銷售點的需求量不能滿足，政府則要按照短缺量進行短缺補償，以此提高農(nóng)民種植蔬菜的積極性.運費的補貼為0.04元/(1噸每公里)，短缺補償因銷售點而異[4].

為了方便問題的研究與解決，做出如下的假設(shè)：⑴產(chǎn)地與銷地的產(chǎn)量和需求量是固定不變的；⑵不考慮質(zhì)量問題導(dǎo)致的供需不均衡，即所有的產(chǎn)品都是合格的；⑶路徑、路口、距離能夠在較長時期內(nèi)保持不變；⑷路途上沒有蔬菜的損耗.

2 求解政府短缺補償和運輸補貼最少的運輸方案

2.1 研究思路

為了將產(chǎn)量與銷量按照短缺補償和運輸補貼最低的要求匹配，首先要確定從任一產(chǎn)地到往任意銷地的最短運輸路徑和運輸距離，從而確定選擇的路徑和補貼費用[5].為了實現(xiàn)這一目的，根據(jù)圖論知識，可以利用Floyd算法或Dijkstra算法來求解，這里選用易于軟件實現(xiàn)的Floyd算法[6].然后以路徑長度確定運輸成本，建立產(chǎn)銷關(guān)系的線性規(guī)劃模型，基于單純形法的理論，利用Lingo軟件編程求解出最優(yōu)方案[7].

2.2 研究方法

2.2.1 求解最短路徑矩陣

Floyd算法是經(jīng)典的動態(tài)規(guī)劃算法之一，也被稱為插點法，可以尋找給定加權(quán)圖中各頂點之間的最短路徑及距離[8].Floyd算法基本思想如下：

于是有：D(0)[i][j]=min{D(-1)[i][j],D(-1)[i][0]+D(-1)[0][j]}

2.2.2 求出運輸成本矩陣

運輸成本為運費補貼與距離的乘積：S=D(v)×0.04.

由于供應(yīng)量總和小于需求量總和，即供不應(yīng)求，所以在建立模型時增加一個虛擬產(chǎn)地，產(chǎn)量假設(shè)為a9，達到供求平衡.虛擬產(chǎn)地與任一銷售點距離為0，它的發(fā)貨量即銷售點缺貨量，所以發(fā)貨成本為短缺補償[9].從而有：

2.2.3 最低總成本模型的構(gòu)成

引入決策變量：

產(chǎn)地i運往銷售點j的蔬菜量為xij，所產(chǎn)生的運費補貼成本或短缺補償為sij，從i地發(fā)出的蔬菜總量記為ai，銷售點j所需要的蔬菜量為dj.

2.3 求解與分析

首先，利用MATLAB編程分別求得距離矩陣表1、路徑矩陣表2，如下：

表1 最短路徑距離矩陣(僅列出7個銷售點)

表2 中轉(zhuǎn)方案矩陣

注：標(biāo)號1～8站點為產(chǎn)地，標(biāo)號9～23為路口，標(biāo)號24～58為銷售點.

表1中的數(shù)據(jù)表示的是任意兩地之間的最短距離，與之對應(yīng)的就是表2中的中轉(zhuǎn)方法，其中標(biāo)號5與標(biāo)號24對應(yīng)的數(shù)據(jù)56，表示想要從標(biāo)號5的地點到達標(biāo)號24的地點首先要到達標(biāo)號56的地點，然后再以標(biāo)號56為起點查閱該表確定下一個目的地.

將距離矩陣乘以運費補貼得到運費矩陣后，加入虛擬產(chǎn)地以及其發(fā)貨成本，利用Lingo編程求解得如下結(jié)果：

表3 蔬菜供應(yīng)方案表

注：WH表示產(chǎn)地，MARKET表示銷售點.

表3中列出了在政府總的支出條件下所有產(chǎn)地到各個銷售點的運輸數(shù)量，此時政府總共花費42836.28元.實際生產(chǎn)經(jīng)營中，產(chǎn)品的短缺導(dǎo)致喪失銷售機會，造成顧客長期或暫時的流失，而不顧成本的購進貨物又會增加運費負擔(dān)提高銷售成本，在這對矛盾的關(guān)系下，通過確定產(chǎn)品短缺費用和銷售成本，以總成本最小(總利潤最大)為目標(biāo)，利用線性規(guī)劃的方法統(tǒng)籌考量，往往能得到滿意的結(jié)果.

3 求解各銷售點短缺量不超30%的條件下的最優(yōu)運輸方案

3.1 研究思路

本問題在求解政府短缺補償和運輸補貼最少的運輸方案的基礎(chǔ)上加緊了條件，銷售點需求量允許在特定范圍內(nèi)短缺，目標(biāo)仍為尋找政府支出最小的方案.最低總成本模型求解過程中已經(jīng)給出了由運費補貼與短缺補償構(gòu)成的成本矩陣，在此基礎(chǔ)上需要改動的地方有兩點：一是區(qū)分虛擬產(chǎn)地與實際產(chǎn)地，虛擬產(chǎn)地僅參與短缺補償?shù)挠嬎悖欢蔷€性規(guī)劃模型右端的需求限制，將等于需求量改為大于等于0.7倍原來的需求量即可[10].

3.2 構(gòu)建需求限制條件下的線性規(guī)劃模型

由于在最低總成本模型的構(gòu)建過程中，對銷售點需求的滿足程度不作任何限制，而本問題要求各銷售點實際收到的貨物達到需求量的70%以上，為了便于處理虛擬發(fā)貨與實際發(fā)貨的問題，這里區(qū)分開虛擬產(chǎn)地與實際產(chǎn)地：包括虛擬產(chǎn)地在內(nèi)的9個產(chǎn)地發(fā)貨總量等于35個銷售點的收貨量，供需平衡以方便構(gòu)建線性規(guī)劃模型；8個實際產(chǎn)地到達35個銷售點的運輸量要大于各銷售點的需求下限，作為模型的約束條件之一.所以約束條件如下：

3.3 求解與分析

根據(jù)上述研究方法在Lingo中編程求解，整理結(jié)果得到表4：

表4 蔬菜供應(yīng)方案表

注：COLLECTION1～8為8個蔬菜生產(chǎn)地，COLLECTION9為增添的虛假產(chǎn)地，MARKET1～35為蔬菜銷售地.

由表4所示，添加需求量的限制條件后，政府補貼提高到了50480.94元.此時每個銷售點至少滿足70%需求量，銷售點1、10、12、23、30、31、32需求量全部滿足.對于蔬菜這種生存必需品， 供給量不能完全由市場主導(dǎo)，需要保障居民的最低需求得到滿足，所以經(jīng)過改進后的模型在實際中擁有更廣泛的應(yīng)用.

4 結(jié)束語

蔬菜作為農(nóng)業(yè)經(jīng)濟作物之一，其產(chǎn)業(yè)的外部性、弱質(zhì)性和多功能性，決定了對其施行補貼政策的必要性和重要性.城鎮(zhèn)化在加速發(fā)展、收入水平大幅提高，蔬菜的價格和糧食價格整體成為經(jīng)濟系統(tǒng)的定價基礎(chǔ)，與此同時，隨之產(chǎn)生了“菜貴傷民，菜賤傷農(nóng)”的社會問題[11].

為了實現(xiàn)蔬菜行業(yè)蔬菜產(chǎn)業(yè)的可持續(xù)發(fā)展和發(fā)展現(xiàn)代化農(nóng)業(yè)等多個目標(biāo)需求，我國自1988年開始“菜籃子工程”對蔬菜產(chǎn)業(yè)進行補貼， 以提高人口密集區(qū)蔬菜的供應(yīng)質(zhì)量和數(shù)量，同時帶動周邊農(nóng)業(yè)發(fā)展.文中應(yīng)用Floyd算法求出了8個產(chǎn)地銷往35個銷售點的最短路徑，從而使政府在路途補貼上支出最少，與此類似的，該模型可推廣到其他許多生產(chǎn)經(jīng)營領(lǐng)域.政府通過減少運費補貼、短缺補償?shù)却胧┩顿Y建立蔬菜存儲基地以及蔬菜生產(chǎn)基地，建立并完善蔬菜運輸網(wǎng)絡(luò)及物流配送體系，從而減少政府財政資金壓力，并進一步增加“菜籃子工程”試點區(qū)域，保障現(xiàn)階段蔬菜產(chǎn)業(yè)補貼政策四大目標(biāo)的實現(xiàn)[12].