劉曉可

摘 要 本文根據(jù)JG市的蔬菜種植問題，采用線性規(guī)劃的理論和方法建立了簡單合理的運(yùn)輸方案來實(shí)現(xiàn)現(xiàn)階段的蔬菜供應(yīng)問題，建立模型時(shí)應(yīng)先運(yùn)用floyd算法求出各種植基地到每個(gè)銷售點(diǎn)的最短運(yùn)輸距離，然后用lingo軟件計(jì)算蔬菜短缺補(bǔ)償和運(yùn)費(fèi)最小的方案。緊接著根據(jù)題目要求對算法加以修改得出每個(gè)市場短缺量不超過需求量的30%的最優(yōu)方案，并求出了最佳的改進(jìn)方案。

關(guān)鍵詞 最短路問題 floyd算法 政府投入補(bǔ)貼

中圖分類號：S151.9 文獻(xiàn)標(biāo)識碼：A

2015年吉林省大學(xué)生數(shù)學(xué)建模競賽E題“菜籃子工程中的蔬菜種植問題”如下：JG在郊區(qū)和農(nóng)區(qū)建立了8個(gè)蔬菜種植基地，每天將蔬菜運(yùn)送到市區(qū)的35個(gè)蔬菜銷售點(diǎn)。市區(qū)有15個(gè)主要交通路口，在蔬菜運(yùn)送的過程中從蔬菜種植基地可以途徑這些交通路口再到達(dá)蔬菜銷售點(diǎn)。如果蔬菜銷售點(diǎn)的需求量不能滿足，則給予一定的短缺補(bǔ)償。同時(shí)市政府還按照蔬菜種植基地供應(yīng)蔬菜的數(shù)量以及路程，發(fā)放相應(yīng)的運(yùn)費(fèi)補(bǔ)貼，運(yùn)費(fèi)補(bǔ)貼標(biāo)準(zhǔn)為0.04元/（1噸·1公里）。

問題：針對下面兩個(gè)問題，分別建立數(shù)學(xué)模型，并制定蔬菜運(yùn)送方案。

（1）為JG市設(shè)計(jì)從蔬菜種植基地至各蔬菜銷售點(diǎn)的蔬菜運(yùn)送方案，使政府的短缺補(bǔ)償和運(yùn)費(fèi)補(bǔ)貼最少；

（2）制定蔬菜銷售點(diǎn)的短缺量一律不超過需求量的30%方案。

1模型假設(shè)

（1）蔬菜在運(yùn)輸途中無損耗；

（2）路口不是貨站不能把蔬菜拆分；

（3）銷售點(diǎn)及蔬菜種植基地都可以作為中轉(zhuǎn)點(diǎn)；

（4）并且只考慮短缺補(bǔ)償和運(yùn)費(fèi)補(bǔ)償，不考慮其它費(fèi)用。

2模型分析

首先要求解各個(gè)蔬菜種植基地到銷售點(diǎn)最短距離，運(yùn)用網(wǎng)絡(luò)各點(diǎn)之間的矩陣算法，即Floyd算法：從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是從i經(jīng)過若干個(gè)節(jié)點(diǎn)到j(luò)，2是直接從i到j(luò)。只要列出它的距離的鄰接矩陣，便能運(yùn)用MATLAB。

由于數(shù)據(jù)比較復(fù)雜，用普通的計(jì)算很困難，所以我們可以用MATLAB軟件來編程求解。

3模型求解

（1）采用標(biāo)號作業(yè)法，每次迭代產(chǎn)生一個(gè)永久標(biāo)號，從而得到最短路徑。

接下來可以運(yùn)用MALTAB語言，很快就可得到從各個(gè)蔬菜種植基地到35個(gè)銷售點(diǎn)的最短距離，從而可以求出最小的運(yùn)輸補(bǔ)償。

政府的補(bǔ)貼包括了蔬菜的短缺補(bǔ)償和交通補(bǔ)償，運(yùn)用之前得到的各個(gè)種植基點(diǎn)到銷售點(diǎn)的最短距離與運(yùn)費(fèi)補(bǔ)貼標(biāo)準(zhǔn)0.04元/（1噸.1公里）乘積與蔬菜的短缺補(bǔ)償相加，就能得到政府的補(bǔ)貼的費(fèi)用。

目標(biāo)函數(shù)為：M=∑（yg€Haxg））+0.04*（∑∑zig*xig）

根據(jù)每個(gè)基點(diǎn)蔬菜種植基點(diǎn)日供應(yīng)量（即由同一個(gè)基點(diǎn)運(yùn)往不同銷售點(diǎn)的總量）一定，已知各個(gè)銷售點(diǎn)需求量一定，而總供應(yīng)量卻滿足不了總需求量。

約束條件為：

∑xig≤xi；=1，2，3…8；

∑xig=xg=1，2，3…35；

xig≥0

用lingo求解，得到政府補(bǔ)貼最少為：42824.62元。

（2）若規(guī)定各蔬菜銷售點(diǎn)的短缺量一律不超過需求量的30%，則運(yùn)往各個(gè)銷售點(diǎn)蔬菜的量要大于等于需求量的70%。

目標(biāo)函數(shù)為：M=mg∑（yg€Haxg）+0.04*（∑∑zig*xig）；

約束條件為：

∑xig≥0.7xi ； i=1，2，3，…8；

∑xig=xg；g=1，2，3，…35；

xig≥0

用lingo求解，得到政府補(bǔ)貼最少為：50255.05元。

參考文獻(xiàn)

[1] Thomas H.Cormen，Charles E.Leiserson，等.Introduction to Algorithms（算法導(dǎo)論）[M].潘金貴等譯.機(jī)械工業(yè)出版社，2006：386.

[2] MATLAB技術(shù)大全.矩陣及其運(yùn)算[M].北京：人民郵電出版社，2013.

[3] 錢頌迪.運(yùn)籌學(xué)[M].北京：清華北大出版社，1999.