Flody算法求最短路径 N 2问求出种植基地种植量 供求是否相等？ Y 对短缺损失进行约N Y 设计算法使短缺损失和运输费用最蔬菜种类是否有要求？ Y 问3设计各个基地种植计划 问（1）规划设计使短缺损失和运输费用最问（2）在问（1）上增加约束条件使短缺损失和运输费用最小 设计方案使使短缺损失和运输费用最小 设计方案使使短缺损失和运输费用最小 第四问提出改进方法 图2-1 算法思路流程图
三、基本假设
1、各个路口以及蔬菜销售点都可以作为中转点
2、不考虑每个蔬菜种植基地到各个蔬菜销售最大云货量的限制
3、假设蔬菜种植基地直达某个销售地点，即销售点之间没有卸货的情况 4、假设运输的蔬菜路途中没有损耗
5、假设只考虑运输费用和短缺费用，不考虑装卸等其它费用 6、假设各蔬菜种植基地供应蔬菜同质且单位运价相同
四、符号说明
4
符号 意义
x(i,j) (i=1,2,?8;j=1,2,?,35) 第i个基地到第j个销售点之间的距离 y(i,j) (i=1,2,?8;j=1,2,?,35) 第i个基地到第j个销售点之间的运货量 P 运输总费用 Q 短缺补助总费用 R 政府总补助费用
b(j) 第j个销售点蔬菜的需求量
d(i) 第i个蔬菜种植基地的产量 c 每吨每公里的补贴费用
? 蔬菜种植基地和销售基地与配送中心的单位费用 tin 第i个销售点到第n个设备中心的运量 mjk 表示送往第j个销售点k种蔬菜的运量
snj 第n个配送中心到第j个销售点的运量
五、模型的建立与求解
5.1、模型的准备
首先针对题目给出的数据，利用matlab编程绘制出蔬菜种植基地、交通路口、销售点之间的连通图，如图5-1所示：
图5-1 路线图
如图5-1所示，图中一共有58个节点（其中包括8个蔬菜种植基地，15个路口以及35个销售基地），对图中的8个蔬菜种植基地进行编号为v1~v8;15个路口进行编号为v9~v23;35销售点编号为v24~v59。
由于蔬菜的运输过程具有无向性，所以我们首先可以考虑用经典的floyd算法求出蔬菜种植基地到销售点的最短距离，再利用线性规划来解决题目中的问
5
题。首先根据附录中的数据对图中的58个节点建立邻接矩阵A，便于利用floyd算法求出最短路径。
?v11v12?v1p??v?v?v21222p? A??????????vv?v?pp??p1p2?(58?58)其中，p?58；vij代表第i个蔬菜种植基地到第j个销售点的距离，后面用符号x(i,j)表示。
5.2、问题一模型的建立和与求解
5.2.1建立Floyd算法求蔬菜种植基地到销售点的距离
Floyd算法亦称为插点法，是一种用于寻找给定加权图中顶点间路径最短的算法。Floyd算法基本思想为：首先设置一个n?n矩阵A(k)，其中对角线元素全为0，其他ak[i][j]表示顶点i到j的路径值，k代表运算步骤，当k=0时：
A(0)[i][j]?arcs[i][j] 得出的矩阵称为临接矩阵，以后逐步的尝试在原路径的两顶点上增加其他顶点作为中心顶点，如果增加中间顶点后，新的路径比原来路径减小了，则用新的路径代替旧路径，并修改矩阵元素，否则不变。
小面是具体步骤：
（1）让所有边加入中间点1，取A[i][j]与A[i][1]?A[1][j]中较小的值后
A[i][j]的新值，完成后得到A(1)；
（2）让所有边加入中间点2，把A[i][j]与A[i][2]?A[2][j]中较小的值作为A(2)，依次类推得到A(3),A(4),?,A(n)，其中循坏到第n个得到的A(n)即为我们所
求的结果，A(n)[i][j]表示顶点i与j之间的最短距离。
因此可以描述为：（arcs[i][j]为邻接矩阵）
A(o)[i][j]?arcs[i][j]
A(k)[i][j]?min{A(k?1)[i][j],A(k?1)[i][k],A(k?1)[k][j]} (k=1,2,?,n) 其中：k?1,2,?,n；arcs[i][j]为邻接矩阵。 定义一个n阶方正矩阵序列：
D(?1),D(0),?,D(n?1)
其中D(?1)[i][j]?G.arcs[i][j]；
D(k)[i][j]?min{D(k?1)[i][j],D(k?1)[i][k]?D(k?1)[k][j]} (k=0,2,?,n-1) D(0)[i][j]是从顶点vi到vj，中间顶点是v0的最短路径的长度；
D(k)[i][j]是从顶点vi到vj，中间顶点的符号不大于k的最短路径长度； D(n?1[)i][j是从顶点vi到vj最短路径长度； ]按上述步骤规定，根据图5-1建立58?58的网络权矩阵为：
6
?d11d12?d1p??d?d?d21222p? D[i][j]??????????dd?d??p1p2pp??其中：p?58，D[i][j]为第i个蔬菜种植基地到第j个销售点之间的最短距离。
下面来确定网络权矩阵：
W?(wij)其中:
n?n
wii=lij，当（vi,vj）属于E时，lij为弧（vi,vj）的权 wii=0，i=1,2,3……n
（inf为无穷大，n为网络结点个数） wij=inf,当（vi,vj）不属于E时。
因为上述网络有58个结点，故网络的权矩阵均为58阶矩阵。在给出网络最
短路线的Froyd算法：
（1）d1=w.(w为所给网络的n阶权矩阵) （2）dk=(dkij)n?n,k=2,3,…,p.
其中：
dkij=min[d(k?1)ij,d(k?1)is?d(k?1)sj] i,j=1,2,…,n.
下面来确定计算次数。当wij?0时，p由下式确定：p?ln(n-1)/ln2，这样的dp就确定了网络各点间的最短距离。此处n=15,解出p?3.3669故只需要取p=4即可，即算到d4即可。 5.2.2模型的求解
通过matlab编程求得每个蔬菜种植基地到各个销售点的最短距离x(i,j)如表5-1所示,具体路线如图5-1的红色线部分。
销售点1 销售点2 销售点3 销售点4 销售点5 销售点6 销售点7 销售点8 销售点9 销售点10 销售点11 销售点12 销售点13 销售点14
表5-1 每个蔬菜种植基地到各个销售点的距离表 种植种植种植种植种植基种植基种植基基地1 基地2 基地3 基地4 地5 地6 地7 47 48 61 68 52 26 7 35 36 51 64 51 31 14 26 27 42 59 50 30 14 13 14 29 46 46 43 27 17 18 33 50 50 40 28 33 34 49 56 43 23 21 41 41 50 57 41 15 18 49 39 48 55 39 13 25 50 40 49 54 32 6 27 40 29 38 45 32 17 30 37 29 38 45 35 27 34 30 24 33 46 42 34 41 20 13 28 45 45 43 36 12 9 24 41 41 39 32 7
种植基地8 32 23 15 28 29 22 30 38 39 39 35 42 37 33
销售点15 销售点16 销售点17 销售点18 销售点19 销售点20 销售点21 销售点22 销售点23 销售点24 销售点25 销售点26 销售点27 销售点28 销售点29 销售点30 销售点31 销售点32 销售点33 销售点34 销售点35 16 21 24 35 40 43 37 33 29 31 25 22 25 28 33 40 37 44 50 42 48 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21 35 30 27 22 16 8 14 18 22 35 34 37 40 37 42 31 24 17 23 29 38 36 41 44 35 38 41 46 45 44 51 45 42 45 48 53 58 51 50 56 56 65 37 42 45 38 41 51 49 48 47 52 46 43 46 49 54 61 54 56 62 59 68 得到每个蔬菜种植基地到各个销售点的最短距离之后，只要知道每个蔬菜种植基地把蔬菜送往销售点的重量，便可以求得运输的总费用。
将八个蔬菜种植基地分别编号为A,B,C,D,E,F,G,H 统计附录数据可得5-2表：
表5-2 总生产量和需求量对照表 蔬菜总生产量 270 吨 销售点需求量 360 吨 由表可以看出：蔬菜总生产量<销售点需求量,该问题属于产量大于销售量，因此可以利用线性规划来求解，用LINGO软件得出结果。
设目标函数总费用Z来表示,总费用包括两部分: 蔬菜调运费P，各市场供给量小于需求量的短缺损失Q，即：Z=P+Q；根据题意，他们分别可以用公式表示为：
1）蔬菜总运输费用P可以表示为：
835P???c?x(i,j)y(i,j)
i?1j?1其中，i?1,2,?,8;j?1,2,?,35；x(i,j)为第i个基地到第j个销售点之间
的距离，c表每吨每公里的运费补贴
2）市场j的短缺量为：
b(j)??y(i,j)；
i?18其中，i?1,2,?,8;j?1,2,?,35；b(j)代表第j个蔬菜市场每天对蔬菜的
8