光明市的菜篮子工程

1、PAGE PAGE - 12 -数学建模论文 题 目：光明市的菜篮子工程姓 名： 时 间: 2012 / 6 / 26 光明市的菜篮子工程摘要 在各种假设的基础上，建立了解决蔬菜分配和运输问题的线性规划模型。由于变量较少，约束条件也为线性，目标函数也为一次，所以利用Lingo软件，对数据进行预处理和模型最优化求解，可以很快得求出最优化的分配和运输方案。 另外，我们在原始模型的基础上我们对模型进行了部分约束条件的修改与改进，并分析了其对总费用和订购运输计划的影响。在论文中，还对所建立的模型的优缺点和需要改进的地方进行了讨论，并进行了相关的经济效益和社会效益的分析。关键词：运输问题 弗洛伊德算法

2、线性规划 1问题的重述光明市共有三个蔬菜收购点，要在每天五点前，将三个收购点的蔬菜送往本市的八个菜市场，在已知常年情况下，A、B、C三个采购点每天的采购量和各菜市场的每天需求量及发生供应短缺时带来的损失，且假设从收购点至各菜市场蔬菜调运费用为1元，解决如下情况：要求为该市设计一个从各收购点至各菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失最小。若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案。为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点个供应多少最经济合理。2问题的分析3个收购点向8菜市场调运蔬菜，要求用于蔬

3、菜调运的运输费用及预期的短期损失最小，结合已知3个收购点每天收购量分别为200kg、170kg、160kg，可以利用线性规划的最决策问题进行思考。根据已知求出运输费用和预期短期损失最少的目标函数，以及相应的约束条件。对于第二问和第三问都是在第一问线性规划目标函数的基础上对约束条件进行一定的改变，而求解的新的优化问题。3模型的假设与符号的说明3.1 模型的假设（1）假设蔬菜在运送过程中不存在损坏。（2）假设不存在道路不通，无法运送的情况。（3） 假设各蔬菜市场的蔬菜只来源于A、B、C3个收购站，不包含外来送货状况。（4） 假设该市经济保持相对稳定，3个收购站每年的收购量相对稳定。（5） 假设蔬菜

4、价格一致，不存在恶意竞争。（6） 假设各收购站可作为中转站。（7） 不计算该市的新建市场，只考虑该题固定的8个菜市场。（8） 不考虑该市的新增路段，只在题中路段进行选择。3.2符号说明xij：第i个收购点向j市场供给的数量cij：第i个收购点向j 市场供给的单位运费ai：第i个收购点供应量bj：第j个市场需求量dj:第j个市场因供给量小于需求量的单位短缺损失4.问题分析、模型建立及求解4.1模型(a)的分析及建模4.1.1 模型分析目标函数总费用Z,包括两项: 蔬菜调运费Q，各市场供给量小于需求量的短缺损失PZ=P+Q其中:P= Q= 约束条件为 = 1 * GB3 3个收购点的蔬菜全部供给给

5、8个市场 （i=1，2，3） = 2 * GB3 3个收购点分别向每个市场供应的总量不超过每个市场的需求量（j=1,8）变量非负性限制（i=1，2，3，j=1,8）从而得出问题(a)的数学模型如下： min Z=+ s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）4.1.2模型求解(一) 为了求解模型，必须求出系数（），其中每一表示第i个收购点向j市场供给单位量蔬菜的运费，但因为从收购点至各菜市场单位量蔬菜单位路程的调运费用为1元/（100kg*100m），而蔬菜的单位量为100kg，单位距离为100m ，则可求出第i个收购点到第j市场每单位蔬菜的单位距离运费为1元

6、/（100m *100kg）*100m *100kg=1元。因而 在数值上等于第i个收购点到第j市场的距离值，从而等价于一个求最短路的问题，（1）标志距离：将图中15个点标号，分别为A,B,C,o,p,q,r,1,2,3,4,5,6,7,8.并由此构成15*15的权矩阵W15*15，其中Wij表示第I个点到第j个点的距离，若第I个点和第j个点不相邻，则wij=。（2）列出矩阵：对得到的W，使用弗洛依德算法，得到最短距离，也就是单位最小费用矩阵。从中抽取出第i（i=1,2,3）行和第j(j=8,.,15)列的子矩阵W，其中的值wij即对应为第i个收购站到第j个市场的单位最小费用。表1 单位最小运

7、费12345678A488191162220B14771612162317C20191114615510(3) 结合上述分析，根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解，解如表2。表2 各收购点向市场供应量分配表12345678A75000705500B06080300000C00003009040 总计费用：4610（元）已知各市场每单位短缺损失（表3）表3 各市场每单位短缺损失（元/100kg） 市场1234 5 678短缺损失10851010858(二) 比较表1中每个收购点到市场的单位蔬菜的运价cij和表3 每个市场的单位蔬菜短缺的损失价格dj，若ci

8、jdj,即运费大于短缺损失，则不运，否则增加宏观经济的损失。由此，我们得出表512345678A可运运或不运可运B可运C可运运或不运而表2 中B3 ,B4,A5,C8的路线上发生了运输往来，不利于整个宏观经济值增加。 (1)考虑到如C收购点到8市场的单位量蔬菜的运输费用大于8市场单位量蔬菜的短缺损失等情况，模型2修改模型1的 = 6 * GB3 假设，为允许3个收购点分别向每个市场供应的总量可超过每个市场的需求量。即改变约束条件2，此时模型为min Z=+s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）根据建立的上述模型，利用LINGO软件，输入目标函数和约束条件，

9、求解模型（b）的最优解。表6 各收购点向市场供应量分配表 1234567806080300000C00001000600 总计费用：4460（元）比较表2和表6，从第二个模型所求得分配方式中可以看到A5,C8两条不合理的运输路线已被取消，同时最终的运费也有所下降，下降了150元。(2)仍然考虑到如C收购点到8市场的单位量蔬菜的运输费用大于8市场单位量蔬菜的短缺损失等情况，在模型1的基础上，对模型1 的 = 6 * GB3 假设做出了另一种修改，为允许每个收购点的蔬菜可以只运部分。即改变约束条件1，可得模型min Z=+s.t. （i=1，2，3）（j=1,7） （i=

10、1，2，3，j=1,7） 根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。表7 各收购点向市场供应量分配表12345678A7500005500 B060000000 C0000100000 总计费用：3840（元）(3) 比较表2与表7，从第三个模型所求得分配方式中可以看到B3,B4,A5,C8四条不合理路线都被取消，同时总运费减少了545元。(三)在市场经济下，模型c，随着市场的调节，最终A只愿供应12000千克，B只愿供应6000千克，C只愿供应10000千克，大大小于各收购点常年的每天收购量20000千克，17000千克，16000千克。4.2模型(b)的

11、分析及建模4.2.1模型分析按题中问题(b)规定各菜市场短缺量一律不超过需求量的20%的条件，我们对需求量的约束条件进行了修改。min Z=+ s.t. （i=1，2，3） （j=1,8） （j=1,8） （i=1，2，3，j=1,8）4.2.2模型求解(1)根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。表8 各收购点向市场供应量分配表12345678A751000605500B05064560000C00002407264 总计费用：4806（元）(2)比较表2和表8，主要是对3，4，7，8市场的供应量作出了调整。其中的主要原因是对于3，4，7，8市场，从收购

12、点到其的单位量蔬菜的运输费用大于该市场单位量蔬菜的短缺损失，所以，当加入各菜市场短缺量一律不超过需求量的20%的约束条件后，为了保证4，8市场的需求，在考虑到3，7市场相对其他市场运输代价较高的情况下，在这四个市场之间做出平衡供给量的调整。4.3模型(c)的分析及建模4.3.1模型分析为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，即模型为min Z=+s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8） t0（i=1，2，3）4.3.2模型求解 (1)根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。表9 各收购点向市场供应量分

13、配表12345678A754000305500B02080700000C00007009080 总计费用：4770（元）各收购点增加的蔬菜收购量如下表：ABCt0080(2)比较表2和表9，对于4，8市场做了比较大的调整，主要是因为从收购点到其的单位量蔬菜的运输费用大大高于这两个市场单位量蔬菜的短缺损失，供应这两个市场并不能获得收益，反而会受到较大损失。在市场机制的主导下，无法满足这两个市场的需求量。但是，光明市的领导为保证城市居民的蔬菜供应，规划增加蔬菜种植面积，提高收购点的蔬菜收购量，在承担一定损失的情况下，满足了这两个市场的蔬菜需求。5 模型评价(1)以上各模型的优点： = 1 * GB

14、3 所建立的模型简洁明了，便于使用数学工具。如Lingo,降低了编程求解的难度，缩短了运行时间，提高了工作效率。对同一个问题从不同的角度进行了考虑，建立了多个模型，并进行了结果的比较分析，既结合题目要求，又考虑了实际意义。 = 3 * GB3 从社会效益和经济效益对问题进行了分析，也表现出现实生活中政府在寻求两者之间的平衡中做出的努力。(2)不足之处：以上模型均只考虑在降低运输费用和短缺费用的目标下的优化方案，并未涉及到市场上蔬菜供过于求和收购点蔬菜积压而导致的存储费用等，而使所建立的模型不能很好地符合实际情况,还有待改进。参考文献1姜启源，谢金星，叶俊 .数学建模M,北京：高等教育出版社，2

15、004.2谢金星 ,薛毅.优化建模与LINDO/LINGO软件M，北京：清华大学出版社，2005.7.3胡运权.运筹学基础及应用M,北京:高等教育出版社,2008.6.附录部分1.数据预处理部分：求最小费用的LINGO的文件如下：model:SETS:NODES/A,B,C,o,p,q,r,1,2,3,4,5,6,7,8/;ROADS(NODES, NODES)/A,o A,p A,1 A,2 A,3 A,6 B,o B,r B,2 B,3 C,q C,5 C,7 C,8 o,2 o,3 p,3 p,5 p,6 q,5 q,6 q,7 r,3 r,4 r,5 r,8 1,2 1,6 3,5 7

16、,8/:W0;LINK(NODES, NODES): W, D;NNN(Nodes,nodes,nodes):U; ENDSETS DATA:BIG=1000;W0=7 4 4 8 8 6 6 11 7 7 8 6 5 10 3 5 4 7 5 6 7 10 6 5 3 6 7 5 5 11;TEXT(FinalCost.txt)=writefor(nodes(i)|i#le#3: writefor(nodes(j)|j#ge#8 #and# j#le#15: format(D(i,j),5.0f) );ENDDATACALC:FOR(LINK(i,j)|IN(ROADS,i,j): W(i,

17、j) = W0(i, j); W(j,i) = W0(i,j); ); FOR(LINK(i,j)|i#eq#j: W(i,j) = 0 ); FOR(LINK(i,j)|i#ne#j #and# #not#IN(ROADS,i,j) #and# #not#IN(ROADS,j,i): W(i,j) = BIG;W(j,i) = BIG; ); FOR(NNN(i,j,k)|k#eq#1: U(i,j,k) = W(i,j) );For(nodes(k)|k#lt#size(nodes): FOR(LINK(i,j): U(i,j,k+1) = if(U(i,j,k) #le# U(i,k,k

18、)+U(k,j,k), U(i,j,k), U(i,k,k)+U(k,j,k);FOR(NNN(i,j,k)|k#eq#size(nodes): D(i,j) = if(U(i,j,k) #le# U(i,k,k)+U(k,j,k), U(i,j,k), U(i,k,k)+U(k,j,k) ); ENDCALCEnd求得最短路部分结果如下：Variable ValueD( A, B) 13.00000D( A, C) 17.00000D( A, O) 7.000000D( A, P) 4.000000D( A, Q) 13.00000D( A, R) 14.00000D( A, 1) 4.000000D( A, 2) 8.000000D( A, 3) 8.000000D( A, 4) 19.00000D( A, 5) 11.00000D( A, 6) 6.000000D( A, 7) 22.00000D( A, 8) 20.000002模型主体LINGO程序如下（只取其中一个，其他类同）：MODEL:SETS:SUPPLY/A,B,C/:S;NEED/1.8/:B,P;LINK(Supply, need): C, X;ENDSETSDATA:S=200 170 160;B=75 60 80 70 100 55 90 80;P=10 8 5 10 10 8 5 8;C