刘晓可

摘 要 本文根据JG市的蔬菜种植问题，采用线性规划的理论和方法建立了简单合理的运输方案来实现现阶段的蔬菜供应问题，建立模型时应先运用floyd算法求出各种植基地到每个销售点的最短运输距离，然后用lingo软件计算蔬菜短缺补偿和运费最小的方案。紧接着根据题目要求对算法加以修改得出每个市场短缺量不超过需求量的30%的最优方案，并求出了最佳的改进方案。

关键词 最短路问题 floyd算法 政府投入补贴

中图分类号：S151.9 文献标识码：A

2015年吉林省大学生数学建模竞赛E题“菜篮子工程中的蔬菜种植问题”如下：JG在郊区和农区建立了8个蔬菜种植基地，每天将蔬菜运送到市区的35个蔬菜销售点。市区有15个主要交通路口，在蔬菜运送的过程中从蔬菜种植基地可以途径这些交通路口再到达蔬菜销售点。如果蔬菜销售点的需求量不能满足，则给予一定的短缺补偿。同时市政府还按照蔬菜种植基地供应蔬菜的数量以及路程，发放相应的运费补贴，运费补贴标准为0.04元/（1吨·1公里）。

问题：针对下面两个问题，分别建立数学模型，并制定蔬菜运送方案。

（1）为JG市设计从蔬菜种植基地至各蔬菜销售点的蔬菜运送方案，使政府的短缺补偿和运费补贴最少；

（2）制定蔬菜销售点的短缺量一律不超过需求量的30%方案。

1模型假设

（1）蔬菜在运输途中无损耗；

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

（3）销售点及蔬菜种植基地都可以作为中转点；

（4）并且只考虑短缺补偿和运费补偿，不考虑其它费用。

2模型分析

首先要求解各个蔬菜种植基地到销售点最短距离，运用网络各点之间的矩阵算法，即Floyd算法：从任意节点i到任意节点j的最短路径不外乎2种可能，1是从i经过若干个节点到j，2是直接从i到j。只要列出它的距离的邻接矩阵，便能运用MATLAB。

由于数据比较复杂，用普通的计算很困难，所以我们可以用MATLAB软件来编程求解。

3模型求解

（1）采用标号作业法，每次迭代产生一个永久标号，从而得到最短路径。

接下来可以运用MALTAB语言，很快就可得到从各个蔬菜种植基地到35个销售点的最短距离，从而可以求出最小的运输补偿。

政府的补贴包括了蔬菜的短缺补偿和交通补偿，运用之前得到的各个种植基点到销售点的最短距离与运费补贴标准0.04元/（1吨.1公里）乘积与蔬菜的短缺补偿相加，就能得到政府的补贴的费用。

目标函数为：M=∑（yg€Haxg））+0.04*（∑∑zig*xig）

根据每个基点蔬菜种植基点日供应量（即由同一个基点运往不同销售点的总量）一定，已知各个销售点需求量一定，而总供应量却满足不了总需求量。

约束条件为：

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

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

xig≥0

用lingo求解，得到政府补贴最少为：42824.62元。

（2）若规定各蔬菜销售点的短缺量一律不超过需求量的30%，则运往各个销售点蔬菜的量要大于等于需求量的70%。

目标函数为：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求解，得到政府补贴最少为：50255.05元。

参考文献

[1] Thomas H.Cormen，Charles E.Leiserson，等.Introduction to Algorithms（算法导论）[M].潘金贵等译.机械工业出版社，2006：386.

[2] MATLAB技术大全.矩阵及其运算[M].北京：人民邮电出版社，2013.

[3] 钱颂迪.运筹学[M].北京：清华北大出版社，1999.