Floyd與線性規劃在生產管理中的應用
——以“菜籃子工程”的優化設計為例

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

(安徽財經大學a.金融學院；b.統計與應用數學學院，安徽蚌埠 233000)

0 引言

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

1 數據來源與模型假設

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

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

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

2.1 研究思路

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

2.2 研究方法

2.2.1 求解最短路徑矩陣

Floyd算法是經典的動態規劃算法之一，也被稱為插點法，可以尋找給定加權圖中各頂點之間的最短路徑及距離[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.

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

2.2.3 最低總成本模型的構成

引入決策變量：

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

2.3 求解與分析

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

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

表2 中轉方案矩陣

注：標號1～8站點為產地，標號9～23為路口，標號24～58為銷售點.

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

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

表3 蔬菜供應方案表

注：WH表示產地，MARKET表示銷售點.

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

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

3.1 研究思路

本問題在求解政府短缺補償和運輸補貼最少的運輸方案的基礎上加緊了條件，銷售點需求量允許在特定范圍內短缺，目標仍為尋找政府支出最小的方案.最低總成本模型求解過程中已經給出了由運費補貼與短缺補償構成的成本矩陣，在此基礎上需要改動的地方有兩點：一是區分虛擬產地與實際產地，虛擬產地僅參與短缺補償的計算；二是線性規劃模型右端的需求限制，將等于需求量改為大于等于0.7倍原來的需求量即可[10].

3.2 構建需求限制條件下的線性規劃模型

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

3.3 求解與分析

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

表4 蔬菜供應方案表

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

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

4 結束語

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

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