光明市的菜篮子工程

环游路径和单个路径（每次都从收购点出发）比较求解；第三问应该以增加量最合理为目标函数进行求解。

光明市的菜篮子工程

摘要

光明市菜篮子工程的开销主要由蔬菜调运费用和短缺损失两部分组成，要使开销最小，就要使这两部分的费用总和最小。因此路径的优化程度和各菜市场的分配情况对开销有重要影响。本题主要采用线性规划方法，使用MATLAB以及LINGO软件进行求解。首先，利用弗洛伊德算法找出菜市场、收购点各两点的最短距离，再利用蚁群算法找出从各收购点分别到8个菜市场的最优蔬菜调运路径，最后根据各小题的不同约束条件使用LINGO软件进行编程求解。

对于问题一，目标函数是蔬菜调运费用和短缺损失两部分的费用之和，约束条件是A、B、C三个收购点的收购量，利用LINGO软件编程求解可得蔬菜调用总费用为300元，短缺损失总费用为4110元，总费用为4410元。

对于问题二，目标函数是蔬菜调运费用和短缺损失两部分的费用之和，在问题一的基础上又增加了对各个菜市场运输量的约束，利用LINGO软件编程求解可得蔬菜调用总费用为8092元，短缺损失总费用为552元，总费用为8644元。

对于问题三，目标函数是蔬菜调运费用和短缺损失两部分的费用之和，在问题一的基础上又增加了对各个菜市场运输量的约束以及对A、B、C三个收购点增加供应的条件，利用LINGO软件编程求解可得蔬菜调用总费用为9095元，短缺损失总费用为0元，总费用为9095元。向A、B、C三个收购点分别增加0kg，135（100kg），10（100kg）。

关键词：运输问题；弗洛伊德算法；蚁群算法；线性规划

一、问题重述

光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C)设三个收购点，再有个收购点分别送到全市的8个菜市场，该市道路情况，各路段距离(单位：100m)及各收购点，菜市场①…⑧的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为200,170,160（单位：100kg），各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/（100kg.100m）.

① 6

5 6 11 3

8 10

⑧

4 A 7 8 7 8 ②

7 6

⑦ 图3.2 收购点、菜市场分布图

表3各菜市场的每天需求量及发生供应短缺时带来的损失

（a）为该市设计一个从收购点至各个菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失为最小；

（b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；（c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供应多少最经济合理。

二、问题分析

本题旨在解决如何减少菜篮子工程的开销，即蔬菜调运费用和短缺损失两部分的费用总和。蔬菜调运费用主要取决于蔬菜调运路径的选取，这是典型的旅行商问题，采用弗洛伊德算法和蚁群算法，用MATLAB软件编程求解即可得到最路径。短缺损失主要取决于调运到各菜市场的收购量。菜篮子工程的开销取决于这两部分，对两部分的方案进行线性规划，用LINGO软件进行求解即可得到最优分配方案。

三、基本假设

1、只考虑蔬菜调运费用和短缺损失费用，不考虑装卸等其他费用； 2、假设蔬菜在调运路途中没有损耗；

3、假设各菜市场蔬菜只来源于A、B、C三个收购站，而无其他来源； 4、假设各收购站供应蔬菜质量以及单位运价相同； 5、假设各收购站可以作为中转站。

四、符号说明

五、模型的建立

目标函数蔬菜运输和短缺损失的总费用Z包括两部分: 蔬菜调运费用P，短缺损失费用P。

Xij：第i个收购点向第j个菜市场运输蔬菜的数量（i=1,2,3;j=1,…,8）； Dij：调运路径中，第i个收购点到第j个菜市场的距离（i=1,2,3；j=1,…,8）； A：从收购点至各菜市场蔬菜调运费单价；则蔬菜调运总费用P为：

p=∑∑A*Xij*Dij

i=1

j=1

ai：第i个收购点的供应量（i=1,2,3）; bj:第j个菜市场的需求量（j=1,…,8） ;

B:第j个菜市场因供给小于需求量的单位短缺损失; 则短缺损失总费用为Q：

Q=∑B*(bj-∑Xij)

j=1

i=1

则蔬菜运输和短缺损失的总费用Z： Z=P+Q

问题（a）的模型

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）3个收购点分别向每个市场供应的总量不超过每个市场的需求量 ∑xij≤bj（j=1,…,8）

i=13

（3）变量非负性限制xij≥0（i=1，2，3；j=1,…,8）综合以上结论，得出问题(a)的数学模型如下： Obj1: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

s.t.

∑x

j=1

∑x

i=1

≤b（jj=1,…,8）

xij≥0（i=1，2，3，j=1,…,8）

问题（b）的模型

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）每个菜市场短缺量不超过需求量的20% bj-∑Xij

i=13

(3)变量非负性限制xij≥0（i=1，2，3；j=1,…,8）综合以上结论，得出问题(b)的数学模型如下： Obj2: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

3883

s.t.

∑x

j=1

bj-∑Xij

i=1

xij≥0（i=1，2，3，j=1,…,8）

问题（c）

Ci:增产的蔬菜向第i个收购点供应的数量（i=1,2,3）

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）3个收购点分别向每个市场供应的总量不少于每个市场的需求量 ∑xij>=bj（j=1,…,8）

i=13

（3）变量非负性限制xij≥0（i=1，2，3；j=1,…,8）

综合以上结论，得出问题(c)的数学模型如下： Obj3: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

3883

s.t.

∑x

j=13

∑x

i=1

>=bj（j=1,…,8）

xij≥0（i=1，2，3，j=1,…,8）

六、模型的求解

（一）、模型求解算法： 1.弗洛伊德算法

1.1弗洛伊德算法简述

对于任何集合V中的任意一个顶点vk，顶点vi到顶点vj的最短路经过顶点vk

或者不经过顶点vk。比较dij与dik+dkj的值。若dij>dik+dkj，则令dij=dik+dkj，保持dij是当前收索的顶点vi到顶点vj的最短距离。重复这一过程，最后当收索完所有顶点vk时，dij就是顶点vi到顶点vj的最短距离。 1.2弗洛伊德算法的基本步骤

令dij是顶点vi到顶点vj的最短距离，wij是顶点vi到vj的权。Floyd算法的步骤是：

步骤1：输入图G的权矩阵W。对所有i，j，有dij=wij，k=1。步骤2：更新dij。对所有i,j,若dik+dkj

步骤3：若dii

2.蚁群算法

2.1蚁群算法简述

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。仿生学家研究发现, 蚂蚁个体之间通过一种称之为信息素( pheromone)的物质进行信息传递, 而且其他蚂蚁能够感知这种物质, 并借以指导自己的前进方向,因此, 由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象, 即走过某一路径的蚂蚁越多, 则后来者选择该路径的概率就越大, 最终, 总能够找到从实物源到蚁巢之间的最短路径。根据这个有趣的现象, 20世纪90年代, M. Dorigo等提出了蚁群算法( an t colony algor ithm) , 并将其应用于求解TSP, 取得了较好的结果。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性, 证明它是一种很有发展前景的方法。图1形象说明了蚁群寻找最优路径的过程。30只蚂蚁从A 点出发, 要到达E点, 有两条路径可走, ACDE 和AHDE, 其中BHD 长为2, BCD长为1, t= 0时刻, 蚂蚁在节点B随机选择路线, 而在t= 1时刻, 因为BCD 较BHD

短, 故在BCD上留下的信息素浓度大, 所以在c)中, 更多的蚂蚁选择较短的路径, 留下的信息素会更多, 从而吸引更多的蚂蚁选择此路径, 最终所有蚂蚁都选择较短的那条路径。

图1 蚁群寻找最优路径的过程 2.2蚁群算法模型

设m表示蚁群中蚂蚁的数量, n 表示城市的数量,dij = dj i ( i, j = 1,2,..., n ), 表示城市i和城市j之间的距离, τij (t)表示t时刻在dij上残留的信息量, η

= 1 /dij,

α,β是自定义可调整的参数,用于调节τij和ηij的关系,pkij表示第k只蚂蚁选择边dij的概率,Jk表示第k只蚂蚁还未访问过的城市,各条路径上信息量都为0。每只蚂蚁将按照

计算所得的概率,从( 1)式可以看出, 蚂蚁选择路径的概率随着τij增大而增加, 随着dij的增大而减小。并根据程序产生的随机数,决定下一步的方向, 直到完成周游路径。每当所有蚂蚁完成一次循环后,按照

τij ( t+ 1) = ( 1- ρ)* τij( t) + ∆τij （ 2 ）对路径信息量进行更新,

∆τij=∑∆τij

k=1m

式中的

（ 3 ）

k∆τij

表示第k只蚂蚁在本次循环中在dij上留下的信息量, 其中

⎧Q

dij

⎪L，若蚂蚁k在循环中经过k

∆τij=⎨k

⎪0，k未从d经过

ij⎩

公式中Q是一常数, 表示每只蚂蚁周游一遍留下的信息素总量。当每只蚂蚁都完成一次上述操作时,就称该算法进行了一次周游( Iteration)。循环以上步骤, 直到周游次数达到指定次数或在一定时间内没有新的更优解出现。

2.3算法实现

2.3.1蚁群算法程序的步骤：

1）初始化问题的集合规模N，蚂蚁的数量m，并将m只蚂蚁放到N个城市（过孔）上； 2）程序执行需要循环NC=NC+1次； 3）执行循环时蚂蚁的个数K=K+1;

4）对其中第K只蚂蚁，根据公式（1）选择城市（过孔）J,并继续进行前进； 5）把蚂蚁选择的城市（过孔)j加入到第K只蚂蚁的表tabu中，并修改表Allowed； 6）对于第K只蚂蚁如果没有行走完所有n个城市(过孔)，则转到第四步，若所有城市（过孔）均已走完，则继续往下执行；

7）如果蚂蚁数K小于蚂蚁总数m，则转到第三步，直到m只蚂蚁都走完N个城市，继续往下执行；

8）由式（2）、式（3）随时更新蚂蚁行走时的信息量，且找出m只蚂蚁中，所走路径最短的值，并保存；

9）若循环的总次数没有达到最大的循环次数，则继续转到第二步进行执行，若满足结束条件循环将结束，同时输出结果数据。

程序流程图如下：

（二）模型求解

为了求解模型，必须求出Dij，Dij表示调运路径中，第i个收购点到第j个菜市场的距离。因为从收购点至各菜市场单位量蔬菜单位路程的调运费用为1元/（100kg*100m），而蔬菜的单位量为100kg，单位距离为100m ，则可求出第i个收购点到第j市场每单位蔬菜的单位距离运费为1元/（100m *100kg）*100m *100kg=1元。因而 Dij在数值上等于第i个收购点调运蔬菜到第j菜市场的费用的值，从而等价于一个求最短路的问题。

分别为A,B,C,1,2,3,4,5,6,7,8,9,10,11,12.并由此构成15*15（1）将图中15个点标号，

的权矩阵W15*15，其中Wij表示第I个点到第j个点的距离，若第I个点和第j个点不相邻，则wij= 。

（2）对得到的W，使用弗洛依德算法，得到最短距离。

表1 三个收购点分别到菜市场的最短距离

（3）使用蚁群算法分别求出从收购点A、B、C出发调运蔬菜的最短路径 1）路径A

A--1--2--9--3--5--12--4--12--8--7--11--6

2) 路径B

B--3--5--12--4--12--8--7--11--6--1--2

3) 路径C

C--7--8--12--4--12--5--3--9--2--1--5

⑦

图1 路径A

图2 路径B

⑦

图3 路径C

问题（a）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表2 各收购点向各菜市场供应量分配表

表3各菜市场蔬菜短缺量及损失

由以上两表可知总费用为：4100+300=4410（元）

问题（b）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表4 各收购点向各菜市场供应量分配表

表5各菜市场蔬菜短缺量及损失

由以上两表可知总费用为：8092+552=8644（元）

问题（c）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表6 各收购点向各菜市场供应量分配表

表7各菜市场蔬菜短缺量及损失

表 8增产蔬菜向收购点供应表

由以上两表可知总费用为：9095+0=9095（元）

七、模型的分析与评价

1.模型的优点：

（1）所建立的模型简洁明了，便于使用数学工具,如Lingo,MATLAB,降低了编程求解的难度，缩短了运行时间，提高了工作效率。

（2）从社会效益和经济效益对问题进行了分析，也表现出现实生活中政府在寻求两者之间的平衡中做出的努力。 2.模型的缺点：

以上模型均只考虑在降低运输费用和短缺费用的目标下的优化方案，并未涉及到市场上蔬菜供过于求和收购点蔬菜积压而导致的存储费用等，而使所建立的模型不能很好地符合实际情况。此外，本题对最短路径进行求解时，所求的结果与蚁群算法的参数有关，所设参数并非最优参数，而是相比较之下的较优解，因此所求方案不一定是最好的，该问题使用贪婪算法求解较好。

参考文献

[1]张宏达,郑全第.基于蚁群算法的TSP的仿真与研究 [J].航空计算技术，2005,12（4）:103-106

[2]姜启源，邢文训，谢金星，杨顶辉.大学数学实验[M].北京：清华大学出版社，2005 [3]徐红梅，陈义保，刘加光，王燕涛.蚁群算法中参数设置的研究[J].山东理工大学学报（自然科学版）,2008(1):7-11

[4]姜昌华，胡幼华.一种求解旅行商问题的高效混合遗传算法[J].计算机工程与应用，2004,40（22）：67-70

[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005

[6]党林立，孙晓群.数学建模简明教程[M].西安：西安电子科技大学出版社，2009 [7]王海英，黄强，李传涛，褚宝增.图论算法及其MATLAB实现[M].北京：北京航空航天大学出版社，2010

附录

1.弗洛伊德算法MATLAB程序 %floyd.m

function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n

for j=1:n R(i,j)=j; end end R

for k=1:n for i=1:n

for j=1:n

if D(i,k)+D(k,j)

R end

2. 蚁群算法部分MATLAB程序

function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%========================================================== %% 主要符号说明

%% D 完全图的赋权邻接矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%==========================================================

n=size(D,1);

Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵

Tabu=zeros(m,n); %存储并记录路径的生成

NC=1; %迭代计数器，记录迭代次数 R_best=zeros(NC_max,n); %各代最佳路线

L_best=inf.*ones(NC_max,1); %各代最佳路线的长度 L_ave=zeros(NC_max,1); %各代路线的平均长度

while NC

Randpos=[Randpos,randperm(n)]; end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:n %所在城市不计算 for i=1:m

visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问 J=zeros(1,(n-j+1)); %待访问的城市

P=J; %待访问城市的选择概率分布 Jc=1; for k=1:n

if length(find(visited==k))==0 %开始时置0 J(Jc)=k;

Jc=Jc+1; %访问的城市个数自加1 end end

%下面计算待选城市的概率分布 for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P); %cumsum，元素累加即求和

Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线 to_visit=J(Select(1)); Tabu(i,j)=to_visit; end end

if NC>=2

Tabu(1,:)=R_best(NC-1,:); end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1); %开始距离为0，m*1的列向量 for i=1:m R=Tabu(i,:); for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离 end

L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离 end

L_best(NC)=min(L); %最佳距离取最小 pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线

L_ave(NC)=mean(L); %此轮迭代后的平均距离 NC=NC+1 %迭代继续

%%第五步：更新信息素

Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵 for i=1:m for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); %此次循环在路径（i，j）上的信息素增量 end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); %此次循环在整个路径上的信息素增量 end

Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素 %%第六步：禁忌表清零

Tabu=zeros(m,n); %%直到最大迭代次数 end

%%第七步：输出结果

Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真） Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径 Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离

环游路径和单个路径（每次都从收购点出发）比较求解；第三问应该以增加量最合理为目标函数进行求解。

光明市的菜篮子工程

摘要

关键词：运输问题；弗洛伊德算法；蚁群算法；线性规划

一、问题重述

① 6

5 6 11 3

8 10

⑧

4 A 7 8 7 8 ②

7 6

⑦ 图3.2 收购点、菜市场分布图

表3各菜市场的每天需求量及发生供应短缺时带来的损失

（a）为该市设计一个从收购点至各个菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失为最小；

二、问题分析

三、基本假设

1、只考虑蔬菜调运费用和短缺损失费用，不考虑装卸等其他费用； 2、假设蔬菜在调运路途中没有损耗；

四、符号说明

五、模型的建立

目标函数蔬菜运输和短缺损失的总费用Z包括两部分: 蔬菜调运费用P，短缺损失费用P。

p=∑∑A*Xij*Dij

i=1

j=1

ai：第i个收购点的供应量（i=1,2,3）; bj:第j个菜市场的需求量（j=1,…,8） ;

B:第j个菜市场因供给小于需求量的单位短缺损失; 则短缺损失总费用为Q：

Q=∑B*(bj-∑Xij)

j=1

i=1

则蔬菜运输和短缺损失的总费用Z： Z=P+Q

问题（a）的模型

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）3个收购点分别向每个市场供应的总量不超过每个市场的需求量 ∑xij≤bj（j=1,…,8）

i=13

（3）变量非负性限制xij≥0（i=1，2，3；j=1,…,8）综合以上结论，得出问题(a)的数学模型如下： Obj1: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

s.t.

∑x

j=1

∑x

i=1

≤b（jj=1,…,8）

xij≥0（i=1，2，3，j=1,…,8）

问题（b）的模型

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）每个菜市场短缺量不超过需求量的20% bj-∑Xij

i=13

(3)变量非负性限制xij≥0（i=1，2，3；j=1,…,8）综合以上结论，得出问题(b)的数学模型如下： Obj2: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

3883

s.t.

∑x

j=1

bj-∑Xij

i=1

xij≥0（i=1，2，3，j=1,…,8）

问题（c）

Ci:增产的蔬菜向第i个收购点供应的数量（i=1,2,3）

（1）3个收购点的蔬菜全部供给8个市场 ∑xij

j=18

（2）3个收购点分别向每个市场供应的总量不少于每个市场的需求量 ∑xij>=bj（j=1,…,8）

i=13

（3）变量非负性限制xij≥0（i=1，2，3；j=1,…,8）

综合以上结论，得出问题(c)的数学模型如下： Obj3: min

Z=∑∑A*Xij*Dij+∑B*(bj-∑Xij)

i=1

j=1

i=1

3883

s.t.

∑x

j=13

∑x

i=1

>=bj（j=1,…,8）

xij≥0（i=1，2，3，j=1,…,8）

六、模型的求解

（一）、模型求解算法： 1.弗洛伊德算法

1.1弗洛伊德算法简述

对于任何集合V中的任意一个顶点vk，顶点vi到顶点vj的最短路经过顶点vk

令dij是顶点vi到顶点vj的最短距离，wij是顶点vi到vj的权。Floyd算法的步骤是：

步骤1：输入图G的权矩阵W。对所有i，j，有dij=wij，k=1。步骤2：更新dij。对所有i,j,若dik+dkj

步骤3：若dii

2.蚁群算法

2.1蚁群算法简述

图1 蚁群寻找最优路径的过程 2.2蚁群算法模型

设m表示蚁群中蚂蚁的数量, n 表示城市的数量,dij = dj i ( i, j = 1,2,..., n ), 表示城市i和城市j之间的距离, τij (t)表示t时刻在dij上残留的信息量, η

= 1 /dij,

τij ( t+ 1) = ( 1- ρ)* τij( t) + ∆τij （ 2 ）对路径信息量进行更新,

∆τij=∑∆τij

k=1m

式中的

（ 3 ）

k∆τij

表示第k只蚂蚁在本次循环中在dij上留下的信息量, 其中

⎧Q

dij

⎪L，若蚂蚁k在循环中经过k

∆τij=⎨k

⎪0，k未从d经过

ij⎩

2.3算法实现

2.3.1蚁群算法程序的步骤：

1）初始化问题的集合规模N，蚂蚁的数量m，并将m只蚂蚁放到N个城市（过孔）上； 2）程序执行需要循环NC=NC+1次； 3）执行循环时蚂蚁的个数K=K+1;

7）如果蚂蚁数K小于蚂蚁总数m，则转到第三步，直到m只蚂蚁都走完N个城市，继续往下执行；

8）由式（2）、式（3）随时更新蚂蚁行走时的信息量，且找出m只蚂蚁中，所走路径最短的值，并保存；

9）若循环的总次数没有达到最大的循环次数，则继续转到第二步进行执行，若满足结束条件循环将结束，同时输出结果数据。

程序流程图如下：

（二）模型求解

分别为A,B,C,1,2,3,4,5,6,7,8,9,10,11,12.并由此构成15*15（1）将图中15个点标号，

的权矩阵W15*15，其中Wij表示第I个点到第j个点的距离，若第I个点和第j个点不相邻，则wij= 。

（2）对得到的W，使用弗洛依德算法，得到最短距离。

表1 三个收购点分别到菜市场的最短距离

（3）使用蚁群算法分别求出从收购点A、B、C出发调运蔬菜的最短路径 1）路径A

A--1--2--9--3--5--12--4--12--8--7--11--6

2) 路径B

B--3--5--12--4--12--8--7--11--6--1--2

3) 路径C

C--7--8--12--4--12--5--3--9--2--1--5

⑦

图1 路径A

图2 路径B

⑦

图3 路径C

问题（a）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表2 各收购点向各菜市场供应量分配表

表3各菜市场蔬菜短缺量及损失

由以上两表可知总费用为：4100+300=4410（元）

问题（b）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表4 各收购点向各菜市场供应量分配表

表5各菜市场蔬菜短缺量及损失

由以上两表可知总费用为：8092+552=8644（元）

问题（c）的求解

根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。

表6 各收购点向各菜市场供应量分配表

表7各菜市场蔬菜短缺量及损失

表 8增产蔬菜向收购点供应表

由以上两表可知总费用为：9095+0=9095（元）

七、模型的分析与评价

1.模型的优点：

（1）所建立的模型简洁明了，便于使用数学工具,如Lingo,MATLAB,降低了编程求解的难度，缩短了运行时间，提高了工作效率。

（2）从社会效益和经济效益对问题进行了分析，也表现出现实生活中政府在寻求两者之间的平衡中做出的努力。 2.模型的缺点：

参考文献

[1]张宏达,郑全第.基于蚁群算法的TSP的仿真与研究 [J].航空计算技术，2005,12（4）:103-106

[4]姜昌华，胡幼华.一种求解旅行商问题的高效混合遗传算法[J].计算机工程与应用，2004,40（22）：67-70

[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005

附录

1.弗洛伊德算法MATLAB程序 %floyd.m

function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n

for j=1:n R(i,j)=j; end end R

for k=1:n for i=1:n

for j=1:n

if D(i,k)+D(k,j)

R end

2. 蚁群算法部分MATLAB程序

function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%========================================================== %% 主要符号说明

%% D 完全图的赋权邻接矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%==========================================================

n=size(D,1);

Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵

Tabu=zeros(m,n); %存储并记录路径的生成

NC=1; %迭代计数器，记录迭代次数 R_best=zeros(NC_max,n); %各代最佳路线

L_best=inf.*ones(NC_max,1); %各代最佳路线的长度 L_ave=zeros(NC_max,1); %各代路线的平均长度

while NC

Randpos=[Randpos,randperm(n)]; end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:n %所在城市不计算 for i=1:m

visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问 J=zeros(1,(n-j+1)); %待访问的城市

P=J; %待访问城市的选择概率分布 Jc=1; for k=1:n

if length(find(visited==k))==0 %开始时置0 J(Jc)=k;

Jc=Jc+1; %访问的城市个数自加1 end end

%下面计算待选城市的概率分布 for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P); %cumsum，元素累加即求和

Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线 to_visit=J(Select(1)); Tabu(i,j)=to_visit; end end

if NC>=2

Tabu(1,:)=R_best(NC-1,:); end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1); %开始距离为0，m*1的列向量 for i=1:m R=Tabu(i,:); for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离 end

L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离 end

L_best(NC)=min(L); %最佳距离取最小 pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线

L_ave(NC)=mean(L); %此轮迭代后的平均距离 NC=NC+1 %迭代继续

%%第五步：更新信息素

Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵 for i=1:m for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); %此次循环在路径（i，j）上的信息素增量 end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); %此次循环在整个路径上的信息素增量 end

Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素 %%第六步：禁忌表清零

Tabu=zeros(m,n); %%直到最大迭代次数 end

%%第七步：输出结果

Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真） Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径 Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离

光明市的菜篮子工程

相关文章