《光明市的菜篮子工程》由会员分享，可在线阅读，更多相关《光明市的菜篮子工程（17页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上环游路径和单个路径（每次都从收购点出发）比较求解；第三问应该以增加量最合理为目标函数进行求解。光明市的菜篮子工程摘要光明市菜篮子工程的开销主要由蔬菜调运费用和短缺损失两部分组成，要使开销最小，就要使这两部分的费用总和最小。因此路径的优化程度和各菜市场的分配情况对开销有重要影响。本题主要采用线性规划方法，使用MATLAB以及LINGO软件进行求解。首先，利用弗洛伊德算法找出菜市场、收购点各两点的最短距离，再利用蚁群算法找出从各收购点分别到8个菜市场的最优蔬菜调运路径，最后根据各小题的不同约束条件使用LINGO软件进行编程求解。对于问题一，目标函数是蔬菜调运费用和短缺损失
2、两部分的费用之和，约束条件是A、B、C三个收购点的收购量，利用LINGO软件编程求解可得蔬菜调用总费用为300元，短缺损失总费用为4110元，总费用为4410元。对于问题二，目标函数是蔬菜调运费用和短缺损失两部分的费用之和，在问题一的基础上又增加了对各个菜市场运输量的约束，利用LINGO软件编程求解可得蔬菜调用总费用为8092元，短缺损失总费用为552元，总费用为8644元。对于问题三，目标函数是蔬菜调运费用和短缺损失两部分的费用之和，在问题一的基础上又增加了对各个菜市场运输量的约束以及对A、B、C三个收购点增加供应的条件，利用LINGO软件编程求解可得蔬菜调用总费用为9095元，短缺损失总费
3、用为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），各菜市场的每天需
4、求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/（100kg.100m）.图3.2 收购点、菜市场分布图菜市场每天需求（100kg）短缺损失（元/100kg） 7510608805701010010558905808表3各菜市场的每天需求量及发生供应短缺时带来的损失（a）为该市设计一个从收购点至各个菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失为最小； （b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案； （c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供
5、应多少最经济合理。二、 问题分析本题旨在解决如何减少菜篮子工程的开销，即蔬菜调运费用和短缺损失两部分的费用总和。蔬菜调运费用主要取决于蔬菜调运路径的选取，这是典型的旅行商问题，采用弗洛伊德算法和蚁群算法，用MATLAB软件编程求解即可得到最路径。短缺损失主要取决于调运到各菜市场的收购量。菜篮子工程的开销取决于这两部分，对两部分的方案进行线性规划，用LINGO软件进行求解即可得到最优分配方案。三、 基本假设1、只考虑蔬菜调运费用和短缺损失费用，不考虑装卸等其他费用；2、假设蔬菜在调运路途中没有损耗；3、假设各菜市场蔬菜只来源于A、B、C三个收购站，而无其他来源；4、假设各收购站供应蔬菜质量以及单
6、位运价相同；5、假设各收购站可以作为中转站。四、符号说明Xij第i个收购点向第j个菜市场运输蔬菜的数量Dij调运路径中，第i个收购点到第j个菜市场的距离A从收购点至各菜市场蔬菜调运费单价P蔬菜调运总费用ai第i个收购点的供应量bj第j个菜市场的需求量B第j个菜市场因供给小于需求量的单位短缺损失Q短缺损失总费用Z蔬菜运输和短缺损失的总费用Ci增产的蔬菜向第i个收购点供应的数量五、 模型的建立目标函数蔬菜运输和短缺损失的总费用Z包括两部分: 蔬菜调运费用P，短缺损失费用P。Xij：第i个收购点向第j个菜市场运输蔬菜的数量（i=1,2,3;j=1,8）；Dij：调运路径中，第i个收购点到第j个菜市场
7、的距离（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
8、） （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）变量非负性限
9、制（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）六、 模型的求解（一）、模型求解算法：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弗洛伊德算法的基本步骤令di
10、j是顶点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)的物质进行信息传递, 而且其他蚂
11、蚁能够感知这种物质, 并借以指导自己的前进方向,因此, 由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象, 即走过某一路径的蚂蚁越多, 则后来者选择该路径的概率就越大, 最终, 总能够找到从实物源到蚁巢之间的最短路径。根据这个有趣的现象, 20世纪90年代, M. Dorigo等提出了蚁群算法( an t colony algor ithm) , 并将其应用于求解TSP, 取得了较好的结果。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性, 证明它是一种很有发展前景的方法。图1形象说明了蚁群寻找最优路径的过程。30只蚂蚁从A 点出发, 要到达E点, 有
12、两条路径可走, 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,
13、是自定义可调整的参数,用于调节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中，并修改
