光明市的菜篮子工程.doc

环游路径和单个路径（每次都从收购点出发）比较求解；第三问应该以增加量最合理为目标函数进行求解。光明市的菜篮子工程摘要光明市菜篮子工程的开销主要由蔬菜调运费用和短缺损失两部分组成，要使开销最小，就要使这两部分的费用总和最小。因此路径的优化程度和各菜市场的分配情况对开销有重要影响。本题主要采用线性规划方法，使用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）。关键词：运输问题 ；弗洛伊德算法；蚁群算法；线性规划 一、问题重述5748A564773648571165710687536610511BC光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C)设三个收购点，再有个收购点分别送到全市的8个菜市场，该市道路情况，各路段距离(单位：100m)及各收购点，菜市场的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为200,170,160（单位：100kg），各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/（100kg.100m）.图3.2 收购点、菜市场分布图菜市场每天需求（100kg）短缺损失（元/100kg） 7510608805701010010558905808表3各菜市场的每天需求量及发生供应短缺时带来的损失（a）为该市设计一个从收购点至各个菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失为最小； （b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案； （c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供应多少最经济合理。2、 问题分析本题旨在解决如何减少菜篮子工程的开销，即蔬菜调运费用和短缺损失两部分的费用总和。蔬菜调运费用主要取决于蔬菜调运路径的选取，这是典型的旅行商问题，采用弗洛伊德算法和蚁群算法，用MATLAB软件编程求解即可得到最路径。短缺损失主要取决于调运到各菜市场的收购量。菜篮子工程的开销取决于这两部分，对两部分的方案进行线性规划，用LINGO软件进行求解即可得到最优分配方案。3、 基本假设1、只考虑蔬菜调运费用和短缺损失费用，不考虑装卸等其他费用；2、假设蔬菜在调运路途中没有损耗；3、假设各菜市场蔬菜只来源于A、B、C三个收购站，而无其他来源；4、假设各收购站供应蔬菜质量以及单位运价相同；5、假设各收购站可以作为中转站。四、符号说明Xij第i个收购点向第j个菜市场运输蔬菜的数量Dij调运路径中，第i个收购点到第j个菜市场的距离A从收购点至各菜市场蔬菜调运费单价P蔬菜调运总费用ai第i个收购点的供应量bj第j个菜市场的需求量B第j个菜市场因供给小于需求量的单位短缺损失Q短缺损失总费用Z蔬菜运输和短缺损失的总费用Ci增产的蔬菜向第i个收购点供应的数量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为：ai：第i个收购点的供应量（i=1,2,3）;bj:第j个菜市场的需求量（j=1,8）;B:第j个菜市场因供给小于需求量的单位短缺损失;则短缺损失总费用为Q： 则蔬菜运输和短缺损失的总费用Z： Z=P+Q问题（a）的模型（1）3个收购点的蔬菜全部供给8个市场 （i=1，2，3）（2）3个收购点分别向每个市场供应的总量不超过每个市场的需求量 （j=1,8）（3） 变量非负性限制（i=1，2，3；j=1,8） 综合以上结论，得出问题(a)的数学模型如下：Obj1: minZ=s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）问题（b）的模型（1）3个收购点的蔬菜全部供给8个市场 （i=1，2，3）（2）每个菜市场短缺量不超过需求量的20% （j=1,8） (3)变量非负性限制（i=1，2，3；j=1,8） 综合以上结论，得出问题(b)的数学模型如下：Obj2: minZ=s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）问题（c）Ci:增产的蔬菜向第i个收购点供应的数量（i=1,2,3）（1）3个收购点的蔬菜全部供给8个市场 （i=1，2，3）（2）3个收购点分别向每个市场供应的总量不少于每个市场的需求量 （j=1,8）（3）变量非负性限制（i=1，2，3；j=1,8） 综合以上结论，得出问题(c)的数学模型如下：Obj3: minZ=s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）6、 模型的求解（一）、模型求解算法：1.弗洛伊德算法1.1弗洛伊德算法简述对于任何集合V中的任意一个顶点vk，顶点vi到顶点vj的最短路经过顶点vk或者不经过顶点vk。比较dij与dik+dkj的值。若dijdik+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+dkjdij，则令dij=dik+dkj。步骤3：若dii0，则存在一条含有顶点vi的负回路，停止；或者k=n停止，否则转到步骤2。 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上残留的信息量, ij = 1 /dij,是自定义可调整的参数,用于调节ij和ij的关系,pkij表示第k只蚂蚁选择边dij的概率,Jk表示第k只蚂蚁还未访问过的城市,各条路径上信息量都为0。每只蚂蚁将按照 计算所得的概率,从( 1)式可以看出, 蚂蚁选择路径的概率随着ij增大而增加, 随着dij的增大而减小。并根据程序产生的随机数,决定下一步的方向, 直到完成周游路径。每当所有蚂蚁完成一次循环后,按照 ij ( t+ 1) = ( 1- )* ij( t) + ij （ 2 ）对路径信息量进行更新, （ 3 ） 式中的表示第k只蚂蚁在本次循环中在dij上留下的信息量, 其中公式中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菜市场的费用的值，从而等价于一个求最短路的问题。（1） 将图中15个点标号，分别为A,B,C,1,2,3,4,5,6,7,8,9,10,11,12.并由此构成15*15的权矩阵W15*15，其中Wij表示第I个点到第j个点的距离，若第I个点和第j个点不相邻，则wij=。（2） 对得到的W，使用弗洛依德算法，得到最短距离。 12345678A488191162220B14771612162317C20191114615510表1 三个收购点分别到菜市场的最短距离（3） 使用蚁群算法分别求出从收购点A、B、C出发调运蔬菜的最短路径1） 路径A A-1-2-9-3-5-12-4-12-8-7-11-62) 路径B B-3-5-12-4-12-8-7-11-6-1-23) 路径C C-7-8-12-4-12-5-3-9-2-1-55748A564773648571165710687536610511BC图1 路径A5748A564773648571165710687536610511BC图2 路径B5748A564773648571165710687536610511BC 图3 路径C问题（a）的求解根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。12345678A750000000B00000000C00000000蔬菜调用总费用：300元表2 各收购点向各菜市场供应量分配表123456780608070100559080短缺损失总费用：4110元表3各菜市场蔬菜短缺量及损失由以上两表可知总费用为：4100+300=4410（元）问题（b）的求解根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。12345678A1024830002000B00345680000C00000247264蔬菜调用总费用：8092元表4 各收购点向各菜市场供应量分配表12345678012161420111816短缺损失总费用：552元表5各菜市场蔬菜短缺量及损失由以上两表可知总费用为：8092+552=8644（元）问题（c）的求解根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。12345678A7560000000B0080701005500C0000009080蔬菜调用总费用：9095元表6 各收购点向各菜市场供应量分配表1234567800000000短缺损失总费用：0元表7各菜市场蔬菜短缺量及损失C1C2C3013510 表 8增产蔬菜向收购点供应表由以上两表可知总费用为：9095+0=9095（元）7、 模型的分析与评价1.模型的优点：（1）所建立的模型简洁明了，便于使用数学工具,如Lingo,MATLAB,降低了编程求解的难度，缩短了运行时间，提高了工作效率。（2）从社会效益和经济效益对问题进行了分析，也表现出现实生活中政府在寻求两者之间的平衡中做出的努力。2.模型的缺点：以上模型均只考虑在降低运输费用和短缺费用的目标下的优化方案，并未涉及到市场上蔬菜供过于求和收购点蔬菜积压而导致的存储费用等，而使所建立的模型不能很好地符合实际情况。此外，本题对最短路径进行求解时，所求的结果与蚁群算法的参数有关，所设参数并非最优参数，而是相比较之下的较优解，因此所求方案不一定是最好的，该问题使用贪婪算法求解较好。参考文献1张宏达,郑全第.基于蚁群算法的TSP的仿真与研究 J.航空计算技术，2005,12（4）:103-1062姜启源，邢文训，谢金星，杨顶辉.大学数学实验M.北京：清华大学出版社，20053徐红梅，陈义保，刘加光，王燕涛.蚁群算法中参数设置的研究J.山东理工大学学报（自然科学版）,2008(1):7-114姜昌华，胡幼华.一种求解旅行商问题的高效混合遗传算法J.计算机工程与应用，2004,40（22）：67-705段海滨.蚁群算法原理及其应用M.北京：科学出版社，20056党林立，孙晓群.数学建模简明教程M.西安：西安电子科技大学出版社，20097王海英，黄强，李传涛，褚宝增.图论算法及其MATLAB实现M.北京：北京航空航天大学出版社，2010附录1. 弗洛伊德算法MATLAB程序%floyd.mfunctionD,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendRfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D Rend2. 蚁群算法部分MATLAB程序 functionR_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=rand); %若计算的概率大于原来的就选择这条路线to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_b