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].