范文一:蔬菜运输问题的研究
西南交通大学峨眉校区2016年 全国大学生数学建模竞赛
题目 A题 蔬菜的运输问题
对蔬菜的运输问题的研究
本文针对蔬菜的运输问题进行分析,针对蔬菜运输时所需要注意的蔬菜供应量,需求量,运输距离,运输补贴,短缺补偿等约束性条件,运用lingo编程的方法解决如何进行蔬菜运输来分别使各类要求的支出最少的问题。
问题一中,要求如果不考虑短缺补偿,只考虑运费补贴最少,请为该市设计最优蔬菜运输方案。根据题目的意思,无论其中哪些销售点需求短缺,只要能使该使总体运输成本最少,即各个基地到各个销售点各自所运输的蔬菜吨数乘上运输的距离再乘上0.4所得之和最小,就能使运输补贴最少.我们将供货商和销售点需求分别编号a和b,数量是从1~8和1~35。从题中可以看出其约束条件,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地所生产的蔬菜数量;所有基地给Bj销售点提供的蔬菜数量要大于等于0,并且应该小于或等于该点的需求量。给定约束条件后使用LINGO做线性规划,写出约束条件,列出数据。最终得到各个基地分别运输到每个销售点的蔬菜数量(具体分配方案数据太多,在此不一一列举),并根据附件3中的各个基地到各个销售的的距离算出总运输距离35861.1公里,将其乘上0.4后即可得到总共需要支出的运费补贴1433.44元。
问题二中,增添了对短缺补缺的考虑,规定各蔬菜销售点的短缺量一律不超过需求量的30%,在同时考虑短缺补偿和运费补贴的情况下再次设计最有蔬菜方案。由题意即是要求总费用,具体步骤仍同问题一,需要变化的分别是总费用w的表达式和关于销售点需求的约束条件。w变为原运输补贴的公式再加上每个销售点每吨短缺蔬菜的数量乘上各个销售点不同的短缺补偿,短缺数量需要用各个销售点的需求减去所有基地供给给这个的销售点的蔬菜数量之和。而约束条件则是在上题的基础上增加一条:所有基地给Bj销售点提供的蔬菜数量要大于等于70%的需求量。在此基础上使用LINGO计算出结果,最终得到总支出为52035.1元。(具体分配方案数据太多在此不一一列举,详见下文求解部分或附件)。
问题三中,要求增加任意两个基地的生产数量,使得不存在短缺情况出现,然后视运费补贴最小的情况来确定哪两个基地分别增加多少的产量。由题意,我们首先设置一个0-1变量mi,当基地i要增加规模的时候,其值为1,否则为0.设第i个基地增加的生产量为li,然后确立其约束条件为:增加的蔬菜总量等于需求量减去原生产量,增加的生产量li乘上0-1变量mi等于增加的蔬菜总量,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地原生产的蔬菜数量加上新增的总量;所有基地给Bj销售点提供的蔬菜数量要等于该点的需求量;mi∈{0,1};
所有的mi之和要等于2.使用LINGO计算出结果,得到最优解是基地二和基地六共增
产90.1吨。
本文最大特色是使用LINGO进行线性规划得到最优解,并使用0-1变量来更方便的解出方案。灵敏度的分析也增加了方案的更多弹性,使其更加方便。
关键词:0-1变量规划、lingo,线性规划
一、问题的提出
某市在郊区建立了8个蔬菜基地,每天需要将全部的蔬菜运输到市区的35个蔬菜销售点进行销售。如果蔬菜销售点的需求量不能满足,则市政府要给予一定的短缺补偿。同时市政府还按照蔬菜基地供应蔬菜的数量以及路程,发放相应的运费补贴,运费补贴标准为0.4元/(1吨.1公里)。
相关数据“蔬菜基地日供应量”、“蔬菜销售点日需求量及短缺补偿”、“基地与销售点之间的运输距离”见表。
(1)如果不考虑短缺补偿,只考虑运费补贴最少,请为该市设计最优蔬菜运输方案。
(2)若规定各蔬菜销售点的短缺量一律不超过需求量的30%,且考虑短缺补偿和运费补贴,请为该市重新设计蔬菜运输方案。
(3)为满足市民的蔬菜供应,该市决定选择其中2个基地扩大蔬菜生产面积。试建立数学模型,确定基地选择方案及相应的新增蔬菜量,并重新设计蔬菜运输方案,使运费补贴最少。
二、基本假设
1、假设:每天每个基地给予每个销售点的蔬菜数量相同,不存在特殊原因使其变化;
2、假设:每个销售点蔬菜来源仅来自生产基地,生产基地的蔬菜会仅运输并全部运输到销售点;
3、假设:销售点得到的数量总和等于生产总和; 4、假设:每个基地和每个销售点相互独立;
5、假设:八个基地和三十五个销售点被一视同仁,不存在特殊情况;
6、假设:所有运输的蔬菜都可以在每日规定的时间内从不同的蔬菜基地送达指定的销售点;忽略运输路上其他的损耗;
7、假设:每个基地的生产蔬菜数量不会变化,每个基地对于蔬菜的需求也不会发生变化;
三、符号说明
符号
意义
第i个基地供应的蔬菜数量
单位 吨
备注
ai bj
第j个销售点需求的蔬菜数量 吨
Cij
i
基地i与销售点j之间的运输
距离
第i个蔬菜基地的序号
第j个销售点的序号 每吨蔬菜每公里的运费补贴
公里 元/(1吨*1公里)
吨 元/吨
吨
i∈{x≤x≤8且x∈n*} j∈{x≤x≤35且x∈n*}
j
s s=0.4
xij dj li
从基地i运往销售点j蔬菜量 第j个销售点短缺可获得的短
缺补贴
第三问中第i个基地增加的蔬
菜数量
mi
第i个基地是否增加了数量,是
为1,否为0
四、问题分析
对于问题一,如果不考虑短缺补偿,只考虑运费补贴最少,为该市设计最优蔬菜运输方案。因为不需要考虑短缺补偿,所以我们只需要关注运费补贴最少,而运费补贴为0.4乘以公里数乘以运输重量,所以我们只需要求得所有的和最少的情况。我们需要设置280(8×35)个未知量,再用lingo软件求解即可。
对于问题二,规定各蔬菜销售点的短缺量一律不超过需求量的30%,且需要同时考虑短缺补偿和运费补贴,然后据此为该市重新设计蔬菜运输方案。根据题目要求,首先我们给约束条件在问题一的约束条件基础上增加一条:所有基地给Bj销售点提供的蔬菜数量要大于等于70%的需求量。将最后的总费用分为两个方面,一是运输补贴,二是短缺补贴,相加之后列出表达式。使用LINGO进行线性规划,建立数学模型并计算出分配方案。
对于问题三,要求增加任意两个基地的生产数量,使得不存在短缺情况出现,计算最小的运费补贴。由题意,我们首先设置一个0-1变量mi,当基地i要增加规模的时候,其值为1,否则为0.设第i个基地增加的生产量为li,然后改变其约束条件为:增加的蔬菜总量等于需求量减去原生产量,增加的生产量li乘上0-1变量mi等于增加的蔬菜总量,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地原生产的蔬菜数量加上新增的总量;所有基地给Bj销售点提供的蔬菜数量要等于该点的需求量;mi∈{0,1};所有的mi之和要等于2.在此基础上使用LINGO
进行线性规划,建立数学模型并计算出分配方案。
五、模型建立与求解
5.1问题一的分析与求解 5.1.1问题一的分析
本文旨在针对题目要求,不需要关心需求短缺的问题,只需设计出使运费补贴最小的分配方案。我们主要应考虑的有3个相关因素:每个基地的蔬菜数量,每个销售点的销售需求,以及每个基地到每个销售点之间的距离。在三个相关因素的影响下还存在着两个约束条件,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地所生产的蔬菜数量,以及所有蔬菜生产基地给Bj销售点提供的蔬菜数量要大于等于0,并且应该小于或等于该点的需求量。根据这个目标,三个相关因素和两个约束条件,我们需要使用LINGO进行线性规划。 5.1.2问题一模型的建立
由题目要求,我们可知本题最终要求的是最小运费补贴,而从基地i运送到j销售点的运费补贴为s?Cij?xij,从而我们可以得到第一问的目标函数为:
mins∑∑Cij?xij(1)
i=1j=1
835
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
∑x
j=18
35
ij
=ai(2)
另外,每个销售点收到的蔬菜量应该小于等于其需求量,所以有:
∑x
i=1
ij
≤bi(3)
综合(1)(2)(3)式我们可以得到最终模型为:
mins∑∑Cij?xij
i=1j=1
835
?35
?∑xij=ai,i=1,2,...,8j=1??8s..t?∑xij≤bi,j=1,2,...,35 ?i=1???xij>0
5.1.3问题一模型的求解
根据5.1.2得到的模型,我们运用lingo软件进行求解(程序及输出结果见附录),我们得到并整理分配方案如下表:(无数字代表0)
销售点1
基地1
基地2
基地3
基地4
基地5
基地6
基地7 6.5
基地8
5.1.4 问题一结果的分析及验证
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行。缺点是可以发现销售点10,11,12,18,19,22,23,24,31没有得到蔬菜供应,这就是不考虑短缺补偿所带来的问题。其灵敏度分析见附录。
5.2问题二的分析与求解
5.2.1问题二的分析
本文旨在针对题目要求,在满足运费补贴与短缺补贴之和最小的情况下,设计出合理的分配方案。我们主要应考虑的有4个相关因素:每个基地的蔬菜数量,每个销售点的销售需求,以及每个基地到每个销售点之间的距离,以及不同销售点短缺时每短缺一吨蔬菜可获得短缺补贴。在四个相关因素的影响下还存在着两个约束条件,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地所生产的蔬菜数量,以及所有蔬菜生产基地给Bj销售点提供的蔬菜数量要大于等于该点需求量的70%,并且应该小于或等于该点的需求量。根据这个目标,四个相关因素和两个约束条件,我们需要使用LINGO进行线性规划。
5.2.2问题二模型的建立
由题目要求,我们可知本题最终要求的是最小总支出费用,而从基地i运送到j销售点的运费补贴为s?Cij?xij,短缺补贴则为目标函数为:
∑((b-∑x)*d),从而我们可以得到第二问的
j
ij
j
j=1
i=1
358
min(s∑∑Cij?xij+∑((bj-∑xij)*dj))(4)
i=1j=1
j=1
i=1
835358
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
∑x
j=18
35
ij
=ai(5)
另外,每个销售点收到的蔬菜量应该小于等于其需求量,且大于等于其需求量的70%,所以有:
(0.7*bj)≤∑xij≤bi(6)
i=1
综合(4)(5)(6)式我们可以得到最终模型为:
min(s∑∑Cij?xij+∑((bj-∑xij)*dj))
i=1j=1
j=1
i=1
835358
?35
?∑xij=ai,i=1,2,...,8j=1?8?s..t?(0.7*bj)≤∑xij≤bi,j=1,2,...,35 ?i=1???xij>0
5.2.3问题二模型的求解
根据5.2.2得到的模型,我们运用lingo软件进行求解(程序及输出结果见附录),我们得到并整理分配方案如下表:(无数字代表0)
5.2.4 问题二结果的分析及验证
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行,最终所得的结果即是最小的支出费用。但是发现蔬菜基地6和7有多余的蔬菜没有供应到销售点去,造成了浪费,这也是这种运输办法的缺点之一。 5.3问题三的分析与求解
5.3.1问题三的分析
本文旨在针对题目要求,在增加两个基地的产量使满足不存在短缺的情况下,设计出合理的分配方案。我们主要应考虑的有4个相关因素:哪两个基地需要增加产量;每个基地的新的蔬菜数量,每个销售点的销售需求,以及每个基地到每个销售点之间的距离。在四个相关因素的影响下还存在着六个约束条件:增加的蔬菜总量等于需求量减去原生产量,增加的生产量li乘上0-1变量mi等于增加的蔬菜总量,所有销售点从第Ai基地获得的蔬菜数量应该等于该基地原生产的蔬菜数量加上新增的总量;所有基地给Bj销售点提供的蔬菜数量要等于该点的需求量;mi∈{0,1};所有的mi之和要等于2.根据这个目标,四个相关因素和六个约束条件,我们需要使用LINGO进行线性规划。
5.3.2问题三模型的建立
由题目要求,我们可知本题最终要求的是最小运费补贴,而从基地i运送到j销售点的运费补贴为s?Cij?xij,从而我们可以得到第三问的目标函数为:
8
35
mins∑∑Cij?xij(7)
i=1j=1
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
∑x
j=1
35
ij
=ai+li*mi(8)
另外,每个销售点收到的蔬菜量应该等于其需求量,所以有:
∑(x
i=1
8
ij
+(li*mi))=bi(9)
又因我们对mi的假设,可以得:
mi∈{0,1}(10)
∑m
i=1
8
i
=2(11)
35
8
新加的产量量应该等于原需求量减去原总产量:
∑l*m=∑b-∑a
i
i
j
i=1
j=1
i=18
35
8
i
(12)
综合(7)(8)(9)(10)(11)(12)式我们可以得到最终模型为:
mins∑∑Cij?xij
i=1j=1
?35
?∑xij=ai+li*mi,i=1,2,...,8=1?j8
?∑(x+(l*m))=b,j=1,2,...,35
iii
?i=1ij
?m∈{0,1},i=1,2,...,8s..t?8i
?∑mi=2?i=1
?xij>0
358?8
?∑li*mi=∑bj-∑ai
j=1i=1?i=1
5.3.3问题三模型的求解
根据5.3.2得到的模型,我们运用lingo软件进行求解(程序及输出结果
5.3.4 问题三结果的分析及验证
对该结果进行灵敏度分析:
Righthand Side Ranges
Row Current Allowable Allowable RHS Increase Decrease 2 40.00000 6.300000 5.700000 3 45.00000 29.40000 INFINITY 4 30.00000 0.2000000 9.400000 5 38.00000 0.2000000 8.000000 6 29.00000 10.20000 INFINITY 7 35.00000 50.50000 INFINITY 8 25.00000 5.700000 4.500000 9 28.00000 5.500000 5.000000
由表可知,基地2和基地6弹性较大,可选范围比较大,因此我们仅使m2和
m6值等于1,最终结果为使基地二和基地6总增产90.1吨(需求与原提供量之差)即可。
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行,最终所得的结果即是最小的支出费用。
六、模型的评价与推广
6.1 模型的评价
(1)模型的优点
本模型的优点在于:1.采用LINGO软件做最优解得到方案,可以帮忙节约在运输过程中的不必要的运输成本,做到运输距离最小,运输补贴最低。得到最合适的方案。
2.采用0-1变量来求解第三问,是计算变得简单明了而又易于操作。 3.灵敏度的分析使得本文中的部分数据具有弹性,更方便实际操作。
(2)模型的缺点 本模型的缺点在于
(1) 假设使得每个销售点的需求是永恒不变,而且生产总量也不会变化,这有些不太现实,运输成本理论和现实会存在一定的差距,也会导致浮动。
(2) 数据较多,所以录入数据的过程较为冗长,给解决问题带来了一定的影响。
6.2 模型的推广
本模型是用于在以运输成本为基本考虑点的情况下,计算方案使得从不同仓库运输到不同销售点如何使得运输成本最低的问题,因此本文对于不同地方的电厂给某地区不同地方运送电力也有着一定的参考价值和帮助。
七、参考文献
[1]姜启源等.数学模型(第四版).北京:高等教育出版社,2003年8月 [2]谢金星.优化模型与LINGO/LINGO软件。北京:清华大学出版社,2005.07 [3] 司守奎,孙玺箐.数学建模算法与应用.北京:国防工业出版社,2012.
八、附录
8.1 附录清单
附录1:求解问题一的LINGO程序 附录2:问题一的灵敏度分析 附录3:求解问题二的LINGO程序 附录4:问题二的灵敏度分析 附录5:求解问题三的LINGO程序 附录6:问题三的灵敏度分析 8.2 附录正文
附录1:求解问题一的LINGO程序
model: sets:
vendors/1..8/:a; demand/1..35/:b;
links(vendors,demand):x,c; endsets data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7;
c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29
26 29 32 37 44 41 48 54 46 52
35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37
50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36
67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10
52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21
26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38
7 22 31 44 41 26 18 25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65
38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
s=0.4; enddata
min=s*@sum(links(i,j):c(i,j)*x(i,j));
@for(vendors(i):@sum(demand(j):x(i,j))=a(i)); @for(demand(j):@sum(vendors(i):x(i,j))<=b(j));>=b(j));>
附录2:问题一的灵敏度分析
附录3:求解问题二的LINGO程序 model: sets:
vendors/1..8/:a;
demand/1..35/:b;
links(vendors,demand):c,x; shorts/1..35/:d; endsets data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7;
c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29 26 29 32 37 44 41 48 54 46 52 35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37 50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36 67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10 52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21 26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38 7 22 31 44 41 26 18 25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65 38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
d=710 700 580 600 570 480 500 610 440 705 610 630 590 490 570 460 530 640 665 650 580 680 685 560 660 430 540 620 630 680 695 690 560 520 500;
enddata
min=@sum(links(i,j):0.4*c(i,j)*x(i,j))+@sum(demand(j):(b(j)-@sum(vendors(i):x(i,j)))*d(j));
@for(vendors(i):@sum(demand(j):x(i,j))=a(i)); @for(demand(j):@sum(vendors(i):x(i,j))<>
@for(demand(j):b(j)-@sum(vendors(i):x(i,j))<=0.3*b(j));>=0.3*b(j));>
附录5:求解问题三的LINGO程序
model: sets:
vendors/1..8/:a; demand/1..35/:b;
links(vendors,demand):x,c; increase/1..8/:l; changes/1..8/:m; endsets data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7; c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29 26 29 32 37 44 41
48 54 46 52
35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37
50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36
67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34
28 19 10
52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21
26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38
7 22 31 44 41 26 18 25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65
38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
s=0.4; enddata
min=s*@sum(links(i,j):c(i,j)*x(i,j)); @bin(m(i));
@for(@sum(m(i))=2);
@for(@sum(l(i)*m(i))=@sum(b(j))-@sum(a(i))); @for(@sum(a(i)+l(i)*m(i))=b(j));
@for(@sum(demand(j):x(i,j))=a(i)+l(i)*m(i)); end
附录6:问题三的灵敏度分析
Row Current Allowable Allowable
RHS Increase Decrease 2 40.00000 6.300000 5.700000 3 45.00000 29.40000 INFINITY 4 30.00000 0.2000000 9.400000 5 38.00000 0.2000000 8.000000 6 29.00000 10.20000 INFINITY 7 35.00000 50.50000 INFINITY 8 25.00000 5.700000 4.500000 9 28.00000 5.500000 5.000000
范文二:蔬菜运输问题--数学建模
蔬菜运输问题
摘要
本文运用floyd 算法求出各蔬菜采购点到每个菜市场的最短运输距离,然后用lingo 软件计算蔬菜调运费用及预期短缺损失最小的调运方案,紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案,并求出了最佳的供应改进方案。求解各采购点到菜市场的最短距离,在图论里面关于最短路问题比较常用的是Dijkstra 算法,Dijkstra 算法提供了从网络图中某一点到其他点的最短距离。
关键词
最短路问题 floyd 算法 运输问题
一、问题重述
F 市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况,分别在花市(A ),城乡路口(B )和下塘街(C )设三个收购点,再由各收购点分送到全市的8个菜市场,该市道路情况,各路段距离(单位:100m )及各收购点,菜市场① ⑧的具体位置见图1,按常年情况,A,B,C 三个收购点每天收购量分别为200,170和160(单位:100 kg), 各菜市场的每天需求量及发生供应短缺时带来的损失(元/100kg)见表1. 设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).
① 7 ②
4 8 7 B ⑥ 7
6 3 ④ 6 6
C
⑦ 图1
(a)为该市设计一个从收购点至个菜市场的定点供应方案,使用于蔬菜调运及预期的短缺损失为最小;
(b)若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案 (c)为满足城市居民的蔬菜供应,光明市的领导规划增加蔬菜种植面积,试问增产的蔬菜每天应分别向A,B,C 三个采购点供应多少最经济合理。
二、问题分析
求总的运费最低,可以先求出各采购点到菜市场的最小运费,由于单位重量运费与距离成正比,题目所给的图1里包含了部分菜市场、中转点以及收购点之间的距离,(a )题可以用求最短路的方法求出各采购点到菜市场的最短路径,乘上单位重量单位距离费用就是单位重量各运输线路的费用,然后用线性方法即可解得相应的最小调运费用及预期短缺损失。
第二问规定各菜市场短缺量一律不超过需求量的20%,只需要在上题基础上加上新的限制条件,即可得出新的调运方案。
第三问可以在第二问的基础上用灵敏度分析进行求解,也可以建立新的线性问题进行求解。
三、模型假设
1、各个菜市场、中转点以及收购点都可以作为中转点;
2、各个菜市场、中转点以及收购点都可以的最大容纳量为610吨; 3、假设只考虑运输费用和短缺费用,不考虑装卸等其它费用; 4、假设运输的蔬菜路途中没有损耗; 5、忽略从种菜场地到收购点的运输费用。
四、符号说明
A 收购点分送到全市的8个菜市场的供应量分别为a1,b1,c1,d1,e1,f1,g1,h1, B 收购点分送到全市的8个菜市场的供应量分别为a2,b2,c2,d2,e2,f2,g2,h2, C 收购点分送到全市的8个菜市场的供应量分别为a3,b3,c3,d3,e3,f3,g3,h3, 8个菜市场的短缺损失量分别为a,b,c,d,e,f,g,h(单位均为100kg) 。
五、模型的建立与求解
按照问题的分析,首先就要求解各采购点到菜市场的最短距离,在图论里面关于最短路问题比较常用的是Dijkstra 算法,Dijkstra 算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。但由于它遍历计算的节点很多,所以效率较低,实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra 算法对各点分别计算,就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法,即Floyd
算法。
Floyd 算法的基本是:从任意节点i 到任意节点j 的最短路径不外乎2种可能,1是直接从i 到j ,2是从i 经过若干个节点k 到j 。i 到j 的最短距离不外乎存在经过i 与j 之间的k 和不经过k 两种可能,所以可以令k=1,2,3,... ,n(n是城市的数目) ,在检查d(i,j)与d(i,k)+d(k,j)的值;在此d(i,k)与d(k,j)分别是目前为止所知道的i 到k 与k 到j 的最短距离。因此d(i,k)+d(k,j)就是i 到j 经过k 的最短距离。所以,若有d(i,j)>d(i,k)+d(k,j),就表示从i 出发经过k 再到j 的距离要比原来的i 到j 距离短,自然把i 到j 的d(i,j)重写为d(i,k)+d(k,j),每当一个k 查完了,d(i,j)就是目前的i 到j 的最短距离。重复这一过程,最后当查完所有的k 时,d(i,j)里面存放的就是i 到j 之间的最短距离了。对于上面的问题,只要能列出它的距离的邻接矩阵,如表2所示。便能用floyd 法进行计算了。
表2 各点的邻接矩阵图
首先对图1中的4个纯中转点进行编号,为(9)~(12),并标注在图1中,A 、B 、C 的编号分别为1、14、15,其余点在矩阵中的编号如表1第一行所示。
由于数据比较复杂,用普通的计算很困难,所以我们可以用MATLAB 软件来编程求解。
算法思路:采用标号作业法, 每次迭代产生一个永久标号, 从而生长一颗以V 0为根的最短路树, 在这颗树上每个顶点与根节点之间的路径皆为最短路径。当然此问题也需要表2的各点邻接矩阵。
M 程序如下:
function [min,path]=dijkstra(w,start,terminal) n=size(w,1); label(start)=0; f(start)=start; for i=1:n
if i~=start
label(i)=inf; end , end
s(1)=start; u=start; while length(s)
for j=1:length(s) if i==s(j) ins=1; end , end if ins==0 v=i;
if label(v)>(label(u)+w(u,v))
label(v)=(label(u)+w(u,v)); f(v)=u; end , end , end v1=0;
k=inf; for i=1:n ins=0;
for j=1:length(s) if i==s(j) ins=1; end , end if ins==0 v=i;
if k>label(v)
k=label(v); v1=v; end , end , end
s(length(s)+1)=v1; u=v1; end
min=label(terminal); path(1)=terminal; i=1;
while path(i)~=start
path(i+1)=f(path(i)); i=i+1 ; end
path(i)=start; L=length(path); path=path(L:-1:1);
图2 Dijkstra算法的MATLAB 运行图
如图2,红色框内的是Dijkstra 算法的脚本程序,蓝色框内的试运行结果,根据程序显示s 点到j 点的最短路就是4百米。在程序中显示所走的路线为path=1 2,对应点即为直接从A 点到达①点。但是由于运用dijkstra 编程每次都要修改起始点和终点,所以在大部分情况下效率都不高。 由于dijkstra 算法较为复杂,所以可用Floyd 算法用于求最短路径。Floyd 算法思路本质很简单,即用三个for 循环的嵌套,代码思路如下: for ( int i = 0; i < 节点个数;="" ++i="" )="">
for ( int j = 0; j < 节点个数;="" ++j="" )="">
for ( int k = 0; k < 节点个数;="" ++k="" )="">
if ( Dis[i][k] + Dis[k][j] < dis[i][j]="" )="">
// 找到更短路径
Dis[i][j] = Dis[i][k] + Dis[k][j]; } } } }
但是这里我们要注意循环的嵌套顺序,如果把检查所有节点X 放在最内层,那么结果将是不正确的,因为这样便过早的把i 到j 的最短路径确定下来了,所以正确的应该是这样的:
for ( k = 0; k < 节点个数;="" ++k="" )="">
for ( i = 0; i < 节点个数;="" ++i="" )="">
for ( j = 0; j < 节点个数;="" ++j="" )="">
if ( Dis[i][k] + Dis[k][j] < dis[i][j]="" )="">
% 找到更短路径
Dis[i][j] = Dis[i][k] + Dis[k][j]; } } }. }
那么接下来的问题就是,我们如何找出最短路径. 这里需要借助一个辅助数组Path ,它是这样使用的:Path(AB)的值如果为P ,则表示A 节点到B 节点的最短路径是A->...->P->B。这样一来,假设我们要找A->B的最短路径,那么就依次查找,假设Path(AB)的值为P ,那么接着查找Path(AP),假设Path(AP)的值为L ,那么接着查找Path(AL),假设Path(AL)的值为A ,则查找结束,最短路径为A->L->P->B。那么,如何填充Path 的值呢?很简单,当我们发现Dis(AX) + Dis(XB) < dis(ab)成立时,就要把最短路径改为a-="">...->X->...->B,而此时,Path(XB)的值是已知的,所以,Path(AB) = Path(XB)。Floyd 算法直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n 个矩阵D(1), D(2), ?, D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径。d(i,j) : i到j 的距离; path(i,j): i到j 的路径上i 的后继点; 输入带权邻接矩阵a(i,j)。赋初值,对所有i,j, d(i,j) a(i,j) , path(i,j) j,k=l。然后更新d(i,j) , path(i,j)对所有i,j, 若d(i,k)+d(k,j)<>
d(i,j)=d(i,k)+d(k,j) , path(i,j)path(i,k) , k =k+1。重复上述步骤直到k=n+1。
接下来就是代入具体的数据了,这里的图以及邻接矩阵依旧是修改后的图1及表2。
Floyd 算法的MATLAB 代码如下: M 程序
function [D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n
if D(i,j)~=inf path(i,j)=j; end , end , end for k=1:n for i=1:n for j=1:n
if D(i,k)+D(k,j)
min1=D(start,terminal); m(1)=start; i=1;
path1=[ ];
while path(m(i),terminal)~=terminal
k=i+1; m(k)=path(m(i),terminal); i=i+1; end
m(i+1)=terminal; path1=m; end 脚本程序的代码如下: a=[
0 4 8 8 inf inf 6 inf inf 7 inf 4 inf inf inf 4 0 7 inf inf inf 5 inf inf inf inf inf inf inf inf 8 7 0 inf inf inf inf inf inf 3 inf inf inf 7 inf 8 inf inf 0 inf 5 inf inf inf 5 inf 4 6 7 inf inf inf inf inf 0 inf inf inf inf inf inf inf 5 inf inf inf inf inf 5 inf 0 inf inf inf inf 6 7 3 inf 6 6 5 inf inf inf inf 0 inf inf inf 7 5 inf inf inf inf inf inf inf inf inf inf 0 11 inf 10 inf inf inf 5 inf inf inf inf inf inf inf 11 0 inf inf inf 6 inf 10 7 inf 3 5 inf inf inf inf inf 0 inf inf inf 6 inf inf inf inf inf inf 6 7 10 inf inf 0 inf inf inf 8 4 inf inf 4 inf 7 5 inf inf inf inf 0 inf inf inf inf inf inf 6 5 3 inf inf 6 inf inf inf 0 11 inf inf inf 7 7 inf inf inf inf inf 6 inf inf 11 0 inf inf inf inf inf inf 6 inf 5 10 inf 8 inf inf inf 0];
[D, path]=floyd(a)
运行结果如下:
图3 返回矩阵D
图4 返回矩阵path
D(i,j)表示i 到j 的最短距离; path(i,j)表示i 与j 之间的最短路径上顶点i 的后继点。根据图3、图4的结果可以很快的知道各点到各个点之间的最短路径,A 、①、②??(12)、B 、C 对应1到15这15个网点。例如要找A 点到⑦点的最短路,就是从path 矩阵寻找。A 到⑦,即为1到8,首先找到矩阵中点(1,8)为数字12;再从12出发,找到点(12,8)数字为6;再从6出发,找到点(6,8)为数字15;最后从15出发,找到点(15,8)为数字8。所以最优路线即为从1-12-6-15-8,即从A 到(11),(11)到⑤,⑤到C ,再从C 到⑦,是从A 点到⑦点的最短路,其长度可以直接从图3中按(1,8)找得,为22。
于是很用以得到图3中红色框内的部分分别就是从A 、B 、C 到各菜市场的最短距离,整理出表3所示的每一百公斤蔬菜从各收购点到各菜市场的运输费用。
表3 每一百公斤蔬菜从各收购点到各菜市场的运输费用(元)
由于每天三个收购点的总供应量为200+170+160=530(100kg )
每天8个菜市场的总需求量为75+60+80+70+100+55+90+80=610(100kg ) 所以每天的短缺损失量为610-530=80(100kg )
(一)
对于(a )问题,可以建立以下lindo 程序下的线性规划模型:
min
4a1+8b1+8c1+19d1+11e1+6f1+22g1+20h1+14a2+7b2+7c2+16d2+12e2+16f2+23g2+17h2+ 20a3+19b3+11c3+14d3+6e3+15f3+5g3+10h3+10a+8b+5c+10d+10e+8f+5g+8h st 1) a1+b1+c1+d1+e1+f1+g1+h1=200 2)a2+b2+c2+d2+e2+f2+g2+h2=170 3)a3+b3+c3+d3+e3+f3+g3+h3=160 4)a+b+c+d+e+f+g+h=80 5)a1+a2+a3+a=75 6)b1+b2+b3+b=60 7)c1+c2+c3+c=80 8)d1+d2+d3+d=70 9)e1+e2+e3+e=100 10)f1+f2+f3+f=55 11)g1+g2+g3+g=90 12)h1+h2+h3+h=80 End
根据附录1里面的运行结果,我们可以得出各收购点到各菜市场的蔬菜调运量,表4,其最小的蔬菜调运费用及预期短缺损失共为4610元。
由于有些收购点到菜市场的最短距离不是直接到达,而是经过其他中转站、
菜市场,甚至其他收购点的,因此还要根据图4查出具体的调运线路如下:
P (A ,1)=A-1,运送量为75百公斤;
P (A ,3)=A-3,运送量为40百公斤;
P (A ,5)=A-(11)-5,运送量为30百公斤;
P (A ,6)=A-6,运送量为55百公斤;
P (B ,2)=B-2,运送量为60百公斤;
P (B ,3)=B-3,运送量为40百公斤;
P (B ,4)=B-(12)-4,运送量为70百公斤;
P (C ,5)=C-5,运送量为70百公斤;
P (C ,7)=C-7,运送量为90百公斤;
注:P (i,j )为i 到j 的最短路径
因此,按点与点来表示,调运方案还可以这样:
表5 点对点的调运方案
需要。
(二)
显然上一模型得出的结果中⑧菜市场完全没有得到供应,现实生活中是不允许的,那么接下来就解答第二个问题:若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案。同样的可以用线性模型来求解,于是建立以下lindo 程序下的线性规划模型:
min
4a1+8b1+8c1+19d1+11e1+6f1+22g1+20h1+14a2+7b2+7c2+16d2+12e2+16f2+23g2+17h2+ 20a3+19b3+11c3+14d3+6e3+15f3+5g3+10h3+10a+8b+5c+10d+10e+8f+5g+8h
st 1) a1+b1+c1+d1+e1+f1+g1+h1=200
2)a2+b2+c2+d2+e2+f2+g2+h2=170
3)a3+b3+c3+d3+e3+f3+g3+h3=160
4)a+b+c+d+e+f+g+h=80
5)a1+a2+a3+a=75
6)b1+b2+b3+b=60
7)c1+c2+c3+c=80
8)d1+d2+d3+d=70
9)e1+e2+e3+e=100
10)f1+f2+f3+f=55
11)g1+g2+g3+g=90
12)h1+h2+h3+h=80
13)a<>
14)b<>
15)c<>
16)d<>
17)e<>
18)f<>
19)g<>
20)h<>
End
根据附录2里面的运行结果,我们可以得出各收购点到各菜市场的蔬菜调运量,表6,其最小的蔬菜调运费用及预期短缺损失共为4806元。
同样,根据图4查出具体的调运线路如下:
P (A ,1)=A-1,运送量为75百公斤;
P (A ,2)=A-2,运送量为10百公斤;
P (A ,5)=A-(11)-5,运送量为60百公斤;
P (A ,6)=A-6,运送量为65百公斤;
P (B ,2)=B-2,运送量为50百公斤;
P (B ,3)=B-3,运送量为64百公斤;
P (B ,4)=B-(12)-4,运送量为56百公斤;
P (C ,5)=C-5,运送量为24百公斤;
P (C ,7)=C-7,运送量为72百公斤;
P (C ,8)=C-8,运送量为64百公斤。
因此,按点与点来表示,调运方案如下
(三)
要满足城市居民的蔬菜供应同时又要符合经济,就必须是理想的收购量总和等于需求总和,从表7得知,目前的最优运输线路中没有一个收购点是同时作为其他运输线的中转站的,因此,只需把新增加的蔬菜按最优方案加到原来的基础上,而不需要把原来的收购量做减少,可以建立以下lindo 程序下的线性规划模型:
min 4a1+8b1+8c1+19d1+11e1+6f1+22g1+20h1+14a2+7b2+7c2+16d2+12e2+16f2+23g2+ 17h2+20a3+19b3+11c3+14d3+6e3+15f3+5g3+10h3
st
1)a1+a2+a3=75
2)b1+b2+b3=60
3)c1+c2+c3=80
4)d1+d2+d3=70
5)e1+e2+e3=100
6)f1+f2+f3=55
7)g1+g2+g3=90
8)h1+h2+h3=80
9) a1+b1+c1+d1+e1+f1+g1+h1>200
10)a2+b2+c2+d2+e2+f2+g2+h2>170
11)a3+b3+c3+d3+e3+f3+g3+h3>160
end 从附录3的运算结果可以得知,增加的80百公斤手工量只需全部分给C 收购点,然后重新分配,如表8所示,这时满足了题目要求,同时,蔬菜调运费用及预期短缺损失也是最低的,共4770元。
六、模型的检验与改进
本文所涉及的最短路问题以及运输供求平衡问题都没有使用常规的图上作业法,而是把算法的思路转化为计算机程序,节省了求解的时间同时也提高了模型的准确度,而且具有较强的可复制性。
当然在设计最少运费(最短路)的时候,可以尝试把它与接下来的运输问题用“供求平衡”的方法结合在一起求解,即不用先求出各采购点到菜市场的最短路径,直接按必须供应部分和选择性供应部分用动态规划的方法求解以验证,由于手工的运算量大,在此不作赘述。
而第三问的增加供应分配方案,可以从附录2的灵敏度分析中得知改变任何一个的供应量都接改变最终的结果(因为ROW1、2、3的ALLOWABLE INCREASE和ALLOWABLE DECREASE都为零),研究影子价格的意义就不大了。
综上所述,本文中所涉及的方法和模型都是合适的。
七、模型的推广
本文的解题思路以及所涉及的方法和模型都是准确而且可复制性强的,在解决各种最小费用、最短路线、产销平衡、运输问题时都有较强的参考意义,适当的运用计算机程序解决复杂的计算问题有利于数学应用的推广。
八、参考文献
【1】《运筹学》教材编写组,运筹学,清华大学出版社,2011
九、附录
1、lindo 运算结果1(含灵敏度分析)
LP OPTIMUM FOUND AT STEP 1
OBJECTIVE FUNCTION VALUE
1) 4610.000
VARIABLE VALUE REDUCED COST
A1 75.000000 0.000000
B1 0.000000 0.000000
C1 40.000000 0.000000
D1 0.000000 2.000000
E1 30.000000 0.000000
F1 55.000000 0.000000
G1 0.000000 12.000000
H1 0.000000 5.000000
A2 0.000000 11.000000
B2 60.000000 0.000000
C2 40.000000 0.000000
D2 70.000000 0.000000
E2 0.000000 2.000000
F2 0.000000 11.000000
G2 0.000000 14.000000
H2 0.000000 3.000000
A3 0.000000 21.000000
B3 0.000000 16.000000
C3 0.000000 8.000000
D3 0.000000 2.000000
E3 70.000000 0.000000
F3 0.000000 14.000000
G3 90.000000 0.000000
H3 0.000000 0.000000
A 0.000000 13.000000
B 0.000000 7.000000
C 0.000000 4.000000
D 0.000000 0.000000
E 0.000000 6.000000
F 0.000000 9.000000
G 0.000000 2.000000
H 80.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
1) 0.000000 -15.000000
2) 0.000000 -14.000000
3) 0.000000 -10.000000
4) 0.000000 -8.000000
5) 0.000000 11.000000
6) 0.000000 7.000000
7) 0.000000 7.000000
8) 0.000000 -2.000000
9) 0.000000 4.000000
10) 0.000000 9.000000
11) 0.000000 5.000000
12) 0.000000 0.000000
NO. ITERATIONS= 1
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE A1 4.000000 11.000000 INFINITY B1 8.000000 INFINITY 0.000000 C1 8.000000 0.000000 2.000000 D1 19.000000 INFINITY 2.000000 E1 11.000000 2.000000 0.000000 F1 6.000000 9.000000 INFINITY G1 22.000000 INFINITY 12.000000 H1 20.000000 INFINITY 5.000000 A2 14.000000 INFINITY 11.000000 B2 7.000000 0.000000 INFINITY C2 7.000000 2.000000 0.000000 D2 16.000000 0.000000 2.000000 E2 12.000000 INFINITY 2.000000 F2 16.000000 INFINITY 11.000000 G2 23.000000 INFINITY 14.000000 H2 17.000000 INFINITY 3.000000 A3 20.000000 INFINITY 21.000000 B3 19.000000 INFINITY 16.000000 C3 11.000000 INFINITY 8.000000 D3 14.000000 INFINITY 2.000000 E3 6.000000 0.000000 2.000000 F3 15.000000 INFINITY 14.000000 G3 5.000000 2.000000 INFINITY H3 10.000000 INFINITY 0.000000
A 10.000000 INFINITY 13.000000
B 8.000000 INFINITY 7.000000
C 5.000000 INFINITY 4.000000
D 10.000000 2.000000 0.000000 E 10.000000 INFINITY 6.000000 F 8.000000 INFINITY 9.000000 G 5.000000 INFINITY 2.000000 H 8.000000 0.000000 INFINITY
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 1 200.000000 0.000000 0.000000 2 170.000000 0.000000 0.000000
3 160.000000 0.000000 0.000000 4 80.000000 0.000000 0.000000 5 75.000000 0.000000 0.000000 6 60.000000 0.000000 0.000000 7 80.000000 0.000000 0.000000 8 70.000000 0.000000 0.000000 9 100.000000 0.000000 0.000000 10 55.000000 0.000000 0.000000 11 90.000000 0.000000 0.000000 12 80.000000 0.000000 0.000000
2、lindo 运算结果2(含灵敏度分析)
LP OPTIMUM FOUND AT STEP 20
OBJECTIVE FUNCTION VALUE
1) 4806.000
VARIABLE VALUE REDUCED COST
A1 75.000000 0.000000
B1 10.000000 0.000000
C1 0.000000 0.000000
D1 0.000000 2.000000
E1 60.000000 0.000000
F1 55.000000 0.000000
G1 0.000000 12.000000
H1 0.000000 5.000000
A2 0.000000 11.000000
B2 50.000000 0.000000
C2 64.000000 0.000000
D2 56.000000 0.000000
E2 0.000000 2.000000
F2 0.000000 11.000000
G2 0.000000 14.000000
H2 0.000000 3.000000
A3 0.000000 21.000000
B3 0.000000 16.000000
C3 0.000000 8.000000
D3 0.000000 2.000000
E3 24.000000 0.000000
F3 0.000000 14.000000
G3 72.000000 0.000000
H3 64.000000 0.000000
A 0.000000 7.000000
B 0.000000 1.000000
C 16.000000 0.000000
D 14.000000 0.000000
E 16.000000 0.000000
F 0.000000 3.000000
G 18.000000 0.000000
H 16.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
1) 0.000000 0.000000
2) 0.000000 1.000000
3) 0.000000 5.000000
4) 0.000000 1.000000
5) 0.000000 -4.000000
6) 0.000000 -8.000000
7) 0.000000 -8.000000
8) 0.000000 -17.000000
9) 0.000000 -11.000000
10) 0.000000 -6.000000
11) 0.000000 -10.000000
12) 0.000000 -15.000000
13) 15.000000 0.000000
14) 12.000000 0.000000
15) 0.000000 2.000000
16) 0.000000 6.000000
17) 4.000000 0.000000
18) 11.000000 0.000000
19) 0.000000 4.000000
20) 0.000000 6.000000
NO. ITERATIONS= 20
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE A1 4.000000 7.000000 INFINITY B1 8.000000 0.000000 2.000000 C1 8.000000 INFINITY 0.000000 D1 19.000000 INFINITY 2.000000
F1 6.000000 3.000000 INFINITY G1 22.000000 INFINITY 12.000000 H1 20.000000 INFINITY 5.000000 A2 14.000000 INFINITY 11.000000 B2 7.000000 2.000000 0.000000 C2 7.000000 0.000000 2.000000 D2 16.000000 2.000000 6.000000 E2 12.000000 INFINITY 2.000000 F2 16.000000 INFINITY 11.000000 G2 23.000000 INFINITY 14.000000 H2 17.000000 INFINITY 3.000000 A3 20.000000 INFINITY 21.000000 B3 19.000000 INFINITY 16.000000 C3 11.000000 INFINITY 8.000000 D3 14.000000 INFINITY 2.000000 E3 6.000000 2.000000 3.000000 F3 15.000000 INFINITY 14.000000 G3 5.000000 12.000000 4.000000 H3 10.000000 3.000000 6.000000
A 10.000000 INFINITY 7.000000
B 8.000000 INFINITY 1.000000
C 5.000000 2.000000 INFINITY
D 10.000000 6.000000 INFINITY E 10.000000 1.000000 2.000000 F 8.000000 INFINITY 3.000000 G 5.000000 4.000000 INFINITY H 8.000000 6.000000 INFINITY
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 1 200.000000 0.000000 0.000000 2 170.000000 0.000000 0.000000 3 160.000000 0.000000 0.000000 4 80.000000 0.000000 0.000000 5 75.000000 0.000000 0.000000 6 60.000000 0.000000 0.000000 7 80.000000 0.000000 0.000000 8 70.000000 0.000000 0.000000 9 100.000000 0.000000 0.000000 10 55.000000 0.000000 0.000000 11 90.000000 0.000000 0.000000 12 80.000000 0.000000 0.000000
14 12.000000 INFINITY 12.000000 15 16.000000 10.000000 4.000000 16 14.000000 10.000000 4.000000 17 20.000000 INFINITY 4.000000 18 11.000000 INFINITY 11.000000 19 18.000000 16.000000 4.000000 20 16.000000 16.000000 4.000000
3、lindo 运算结果3
LP OPTIMUM FOUND AT STEP 14
OBJECTIVE FUNCTION VALUE
1) 4770.000
VARIABLE VALUE REDUCED COST
A1 75.000000 0.000000
B1 40.000000 0.000000
C1 0.000000 0.000000
D1 0.000000 2.000000
E1 30.000000 0.000000
F1 55.000000 0.000000
G1 0.000000 12.000000
H1 0.000000 5.000000
A2 0.000000 11.000000
B2 20.000000 0.000000
C2 80.000000 0.000000
D2 70.000000 0.000000
E2 0.000000 2.000000
F2 0.000000 11.000000
G2 0.000000 14.000000
H2 0.000000 3.000000
A3 0.000000 21.000000
B3 0.000000 16.000000
C3 0.000000 8.000000
D3 0.000000 2.000000
E3 70.000000 0.000000
F3 0.000000 14.000000
G3 90.000000 0.000000
H3 80.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
1) 0.000000 1.000000
2) 0.000000 -3.000000
3) 0.000000 -3.000000
4) 0.000000 -12.000000
5) 0.000000 -6.000000
6) 0.000000 -1.000000
7) 0.000000 -5.000000
8) 0.000000 -10.000000
9) 0.000000 -5.000000
10) 0.000000 -4.000000
11) 80.000000 0.000000
NO. ITERATIONS= 14
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE A1 4.000000 11.000000 INFINITY B1 8.000000 0.000000 2.000000 C1 8.000000 INFINITY 0.000000 D1 19.000000 INFINITY 2.000000 E1 11.000000 2.000000 2.000000 F1 6.000000 11.000000 INFINITY G1 22.000000 INFINITY 12.000000 H1 20.000000 INFINITY 5.000000 A2 14.000000 INFINITY 11.000000 B2 7.000000 2.000000 0.000000 C2 7.000000 0.000000 INFINITY D2 16.000000 2.000000 INFINITY E2 12.000000 INFINITY 2.000000 F2 16.000000 INFINITY 11.000000 G2 23.000000 INFINITY 14.000000 H2 17.000000 INFINITY 3.000000 A3 20.000000 INFINITY 21.000000 B3 19.000000 INFINITY 16.000000 C3 11.000000 INFINITY 8.000000 D3 14.000000 INFINITY 2.000000 E3 6.000000 2.000000 3.000000 F3 15.000000 INFINITY 14.000000 G3 5.000000 12.000000 INFINITY
H3 10.000000 3.000000 INFINITY
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 1 75.000000 30.000000 70.000000 2 60.000000 30.000000 40.000000 3 80.000000 20.000000 40.000000 4 70.000000 20.000000 40.000000 5 100.000000 INFINITY 70.000000 6 55.000000 30.000000 55.000000 7 90.000000 INFINITY 80.000000 8 80.000000 INFINITY 80.000000 9 200.000000 70.000000 30.000000 10 170.000000 40.000000 20.000000 11 160.000000 80.000000 INFINITY
范文三:数学模型课程设计-蔬菜的运输问题
攀枝花学院
学生课程设计(论文)
题 目: 蔬菜的运输问题 学生姓名:
学 号:
所在院(系): 数学与计算机学院 专 业: 信息与计算科学 班 级: 2015级信本 指 导 教 师:
2017年 6 月 29 日
攀枝花学院教务处制
攀枝花学院本科学生课程设计任务书 题 目 蔬菜的运输问题
1、课程设计的目的
针对蔬菜的运输问题进行分析,针对蔬菜运输时所需要注意的蔬菜供应量,需求量,运输距离,运输补贴,短缺补偿等约束性条件,运用lingo编程的方法解决如何进行蔬菜运输来分别使各类要求的支出最少的问题。
2、课程设计的内容和要求(包括原始数据、技术要求、工作要求等)
1只要能使该使总体运输成本最少,即各个基地到各个销售点各自所运输的蔬菜吨数乘上运输的距离再乘上0.4所得之和最小,就能使运输补贴最少
2增添了对短缺补缺的考虑,规定各蔬菜销售点的短缺量一律不超过需求量的30%,在同时考虑短缺补偿和运费补贴的情况下再次设计最有蔬菜方案
3要求增加任意两个基地的生产数量,使得不存在短缺情况出现,然后视运费补贴最小的情况来确定哪两个基地分别增加多少的产量。
3、主要参考文献
[1] 姜启源等.数学模型(第四版).北京:高等教育出版社,2003年8月 [2] 谢金星.优化模型与LINGO/LINGO软件。北京:清华大学出版社,2005.07 [3] 司守奎,孙玺箐.数学建模算法与应用.北京:国防工业出版社,2012. 4、课程设计工作进度计划
序号 时间(天) 内容安排 备注
1 2 课程题目确定,了解matlab
2 2 查找资料,编写论文
3 3 数学模型建立求解,验证
4 3 整理内容,修改格式
总计 10
指导教师(签字) 日期 年 月 日
教研室意见:
年 月 日 学生(签字):
接受任务时间: 2014 年 12 月 8 日
课程设计(论文)指导教师成绩评定表 题目名称 技术革新的推广问题
分得评分项目 评价内涵 值 分
遵守各项纪律,工作刻苦努力,具有良好的科学工01 学习态度 6 工作态度。 作 通过实验、试验、查阅文献、深入生产实践等渠表02 科学实践、调研 7 道获取与课程设计有关的材料。 现 按期圆满完成规定的任务,工作量饱满。 03 课题工作量 7 20%
能运用所学知识和技能去发现与解决实际问题,
能正确处理实验数据,能对课题进行理论分析,04 综合运用知识的能力 10
得出有价值的结论。
能独立查阅相关文献和从事其他调研;能提出并
较好地论述课题的实施方案;有收集、加工各种05 应用文献的能力 5 能信息及获取新知识的能力。 力 能正确设计实验方案,独立进行装置安装、调试、设计(实验)能力,方案水操作等实验工作,数据正确、可靠;研究思路清06 5 的设计能力 晰、完整。 平
具有较强的数据运算与处理能力;能运用计算机35% 07 计算及计算机应用能力 5 进行资料搜集、加工、处理和辅助设计等。
对计算或实验结果的分析
具有较强的数据收集、分析、处理、综合的能力。 08 能力(综合分析能力、技10
术经济分析能力)
插图(或图纸)质量、篇符合本专业相关规范或规定要求;规范化符合本成09 幅、设计(论文)规范化5 文件第五条要求。 果 程度
质综述简练完整,有见解;立论正确,论述充分,10 设计说明书(论文)质量 30 结论严谨合理;实验正确,分析处理科学。 量
45% 对前人工作有改进或突破,或有独特见解。 11 创新 10
成绩
指
导
教
师 评 语
指导教师签名: 年 月 日
摘 要
本文针对蔬菜的运输问题进行分析,针对蔬菜运输时所需要注意的蔬菜供应量,需求量,运输距离,运输补贴,短缺补偿等约束性条件,运用lingo编程的方法解决如何进行蔬菜运输来分别使各类要求的支出最少的问题。
问题一中,要求如果不考虑短缺补偿,只考虑运费补贴最少,请为该市设计
b最优蔬菜运输方案。我们将供货商和销售点需求分别编号和,数量是从1~8a
和1~35。从题中可以看出其约束条件,所有销售点从第基地获得的蔬菜数量Ai
应该等于该基地所生产的蔬菜数量;所有基地给销售点提供的蔬菜数量要大Bj
于等于0,并且应该小于或等于该点的需求量。
问题二中,增添了对短缺补缺的考虑,规定各蔬菜销售点的短缺量一律不超过需求量的30%,在同时考虑短缺补偿和运费补贴的情况下再次设计最有蔬菜方案。由题意即是要求总费用,具体步骤仍同问题一,需要变化的分别是总费用w的表达式和关于销售点需求的约束条件。变为原运输补贴的公式再加上每个销w
售点每吨短缺蔬菜的数量乘上各个销售点不同的短缺补偿,短缺数量需要用各个销售点的需求减去所有基地供给给这个的销售点的蔬菜数量之和。
问题三中,要求增加任意两个基地的生产数量,使得不存在短缺情况出现,然后视运费补贴最小的情况来确定哪两个基地分别增加多少的产量。由题意,我
i们首先设置一个0-1变量m,当基地要增加规模的时候,其值为1,否则为0.设i
i第l个基地增加的生产量为,然后确立其约束条件为:增加的蔬菜总量等于需i
lm求量减去原生产量,增加的生产量乘上0-1变量等于增加的蔬菜总量,所有ii
A销售点从第基地获得的蔬菜数量应该等于该基地原生产的蔬菜数量加上新增i
m,0,1B的总量;所有基地给销售点提供的蔬菜数量要等于该点的需求量;;,,ji
m所有的之和要等于2.使用LINGO计算出结果,得到最优解是基地二和基地六共增i
产90.1吨。
关键字:0-1变量规划、lingo,线性规划
I
目 录
摘 要..............................................................................................1
一、问题分析 ......................................................................................1
二、模型假设 ......................................................错误~未定义书签。
三、符号说明 ......................................................错误~未定义书签。
四、模型建立 ......................................................错误~未定义书签。
模型一 ............................................................错误~未定义书签。
模型二 ............................................................错误~未定义书签。
模型三 ............................................................错误~未定义书签。
五 模型检验 ........................................................错误~未定义书签。
六 参考文献 ........................................................错误~未定义书签。
七 附录................................................................................................6
II
一 问题分析
某市在郊区建立了8个蔬菜基地,每天需要将全部的蔬菜运输到市区的35个蔬菜销售点进行销售。如果蔬菜销售点的需求量不能满足,则市政府要给予一定的短缺补偿。同时市政府还按照蔬菜基地供应蔬菜的数量以及路程,发放相应的运费补贴,运费补贴标准为0.4元/(1吨.1公里)。
相关数据“蔬菜基地日供应量”、“蔬菜销售点日需求量及短缺补偿”、“基地与销售点之间的运输距离”见表。
(1)如果不考虑短缺补偿,只考虑运费补贴最少,请为该市设计最优蔬菜运输方案。
(2)若规定各蔬菜销售点的短缺量一律不超过需求量的30%,且考虑短缺补偿和运费补贴,请为该市重新设计蔬菜运输方案。
(3)为满足市民的蔬菜供应,该市决定选择其中2个基地扩大蔬菜生产面积。试建立数学模型,确定基地选择方案及相应的新增蔬菜量,并重新设计蔬菜运输方案,使运费补贴最少。
二、模型假设
1、假设:每天每个基地给予每个销售点的蔬菜数量相同,不存在特殊原因使其变化;
2、假设:每个销售点蔬菜来源仅来自生产基地,生产基地的蔬菜会仅运输并全部运输到销售点;
3、假设:销售点得到的数量总和等于生产总和;
4、假设:每个基地和每个销售点相互独立;
5、假设:八个基地和三十五个销售点被一视同仁,不存在特殊情况; 6、假设:所有运输的蔬菜都可以在每日规定的时间内从不同的蔬菜基地送达指定的销售点;忽略运输路上其他的损耗;
7、假设:每个基地的生产蔬菜数量不会变化,每个基地对于蔬菜的需求也不
1
发生变化;
三、符号说明
符号 意义 单位 备注 a i第个基地供应的蔬菜数量 吨 i
个销售点需求的蔬菜数量 第jb 吨 j
i 基地与销售点之间的运输Cj公里 ij
距离
*ii 第个蔬菜基地的序号 ixxxn,,,,18且 ,,
* j第个销售点的序号 j jxxxn,,,,135且 ,,
s,0.4 每吨蔬菜每公里的运费补贴 元/(1吨 s
*1公里)
ij从基地运往销售点蔬菜量 x 吨 ij
j个销售点短缺可获得的短第d元/吨 j
缺补贴
i第三问中第个基地增加的蔬吨 l i菜数量
i第个基地是否增加了数量,是
mi为1,否为0
2
四、模型建立
问题一模型的建立
i由题目要求,我们可知本题最终要求的是最小运费补贴,而从基地运送到销售点的j运费补贴为,从而我们可以得到第一问的目标函数为: sCx,,ijij
835
(1) minsCx,,,ijij,,ij11
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于
供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
35
(2) xa,,iji,j1
另外,每个销售点收到的蔬菜量应该小于等于其需求量,所以有:
8
(3) xb,,iji,i1
综合(1)(2)(3)式我们可以得到最终模型为:
835
minsCx, ,,ijij,,ij11
35,xai,,,1,2,...,8,iji,j,1,8,st.. ,xbj,,,1,2,...,35,iji,i,1
,x,0,ij,
问题二模型的建立
ij由题目要求,我们可知本题最终要求的是最小总支出费用,而从基地运送到销售点
3
358
的运费补贴为,短缺补贴则为,从而我们可以得到第二(()*)bxd,sCx,,,,ijijjijj,,ji11
问的目标函数为:
835358
(4)min((()*))sCxbxd,,,,,,,ijijjijj,,,,ijji1111
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于
供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
35
(5) xa,,iji,j1
另外,每个销售点收到的蔬菜量应该小于等于其需求量,且大于等于其需求量的70%,
所以有:
8
(6) (0.7*)bxb,,,jiji,i1
综合(4)(5)(6)式我们可以得到最终模型为:
835358
min((()*))sCxbxd,,,,,,,ijijjijj,,,,ijji1111
35,xai,,,1,2,...,8,iji,j,1,8,st..,(0.7*),1,2,...,35bxbj,,,,jiji,i,1
,x,0,ij,
问题三模型的建立
ij由题目要求,我们可知本题最终要求的是最小运费补贴,而从基地运送到销售点的
sCx,,运费补贴为,从而我们可以得到第三问的目标函数为: ijij
835
minsCx, (7),,ijij,,ij11
4
显然,我们可以知道从每个基地运出去的运输总量应该是等于各自的供应量。如果小于
供应量,那就还会给另外需要补偿的销售点运输。由此,我们得到:
35
(8) xalm,,*,ijiii,j1
另外,每个销售点收到的蔬菜量应该等于其需求量,所以有:
8
(9) ((*))xlmb,,,ijiii,i1
又因我们对的假设,可以得: mi
(10) m,0,1,,i
8
(11) m,2,i,i1
新加的产量量应该等于原需求量减去原总产量:
8358
lmba*,, (12) ,,,iiji,,,iji111
)(8)(9)(10)(11)(12)式我们可以得到最终模型为: 综合(7
835
minsCx, ,,ijij,,ij1135,,,,xalmi*,1,2,...,8,ijiii,1j,,8,((*)),1,2,...,35xlmbj,,,,ijiii,i,1,mi,,0,1,1,2,...,8,,ist..,8
,m,2,i,i1,x,0,ij8358,lmba*,,,,,,iiji111iji,,,,
5
五、模型验证
问题一模型的求解
我们运用lingo软件进行求解(程序及输出结果见附录),我们得到并整理分
配方案如下表:(无数字代表0)
基地1 基地2 基地3 基地4 基地5 基地6 基地7 基地8
6.5 销售点1
0.7 4.5 5 销售点2
12 销售点3
14.3 销售点4
13 销售点5
11 销售点6
14 销售点7
9.5 销售点8
10 销售点9
销售点10
销售点11
销售点12
0.7 7.8 销售点13
12 销售点14
11.6 销售点15
12.5 销售点16
2.4 销售点17
销售点18
销售点19
6
10 销售点20
5.5 4.8 销售点21
销售点22
销售点23
销售点24
9.6 销售点25
10.7 4.3 销售点26
7.2 销售点27
8.9 销售点28
10.3 销售点29
9 销售点30
销售点31
8 销售点32
11.4 销售点33
8 4.1 销售点34
10.7 销售点 36
7
问题一结果的分析及验证
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行。缺点是可以发现销售点10,11,12,18,19,22,23,24,31没有得到蔬菜供应,这就是不考虑短缺补偿所带来的问题。其灵敏度分析见附录。
问题二模型的求解
我们运用lingo软件进行求解(程序及输出结果见附录),我们得到并整理分配方案如下表:(无数字代表0)
最优解为52035.1元。
8
基地1 基地2 基地3 基地4 基地5 基地6 基地7 基地8
6.5 销售点1
4.01 6.19 销售点2
销售点3 8(4
10.01 销售点4
9.1 销售点5
7.7 销售点6
9.8 销售点7
1.96 4.69 销售点8
7 销售点9
8.4 销售点10
1.64 5.71 销售点11
4.9 销售点12
5.95 销售点13
8.4 销售点14
8.12 销售点15
8.75 销售点16
9.52 销售点17
4.67 1.63 销售点18
5.11 销售点19
7 销售点20
8.89 销售点21
2.26 3.9 销售点22
6.7 销售点23
8.75 销售点24
6.72 销售点25
7.24 3.26 销售点26
5.04 销售点27
6.23 销售点28
9
7.21 销售点29
9 销售点30
7.70 销售点31
8 销售点32
7.98 销售点33
6.6 1.87 销售点34
7.49 销售点35
问题二结果的分析及验证
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行,最终所得的结果即是最小的支出费用。但是发现蔬菜基地6和7有多余的蔬菜没有供应到销售点去,造成了浪费,这也是这种运输办法的缺点之一。
问题三模型的求解
我们运用lingo软件进行求解(程序及输出结果见附录),我们得到并整理分配方案如下表:
10
基地1 基地2 基地3 基地4 基地5 基地6 基地7 基地8
销售点1 0 0 0 0 0 0 6.5 0 销售点2 0 0 0 0 0 5.7 4.5 0 销售点3 0 0 0 0 0 0 0 12 销售点4 14.3 0 0 0 0 0 0 0 销售点5 13 0 0 0 0 0 0 0 销售点6 0 0 0 0 0 0 0 11 销售点7 0 0 0 0 0 0 14 0 销售点8 0 0 0 0 0 9.5 0 0 销售点9 0 0 0 0 0 10 0 0 销售点10 0 0 0 0 0 8.4 0 0 销售点11 0 0 0 0 0 5.5 0 5 销售点12 7 0 0 0 0 0 0 0 销售点13 0 8.5 0 0 0 0 0 0 销售点14 5.7 6.3 0 0 0 0 0 0 销售点15 0 11.6 0 0 0 0 0 0 销售点16 0 12.5 0 0 0 0 0 0 销售点17 0 13.6 0 0 0 0 0 0 销售点18 0 0 0 0 0 9 9 0 销售点19 0 0 0 0 0 7.3 0 0 销售点20 0 0 0 0 0 10 0 0 销售点21 0 0 0 0 0 12.7 0 0 销售点22 0 0 0 0 0 7.4 0 0 销售点23 0 6.7 0 0 0 0 0 0
11
销售点24 0 0 4.5 8 0 0 0 0
销售点25 0 0.2 9.4 0 0 0 0 0
销售点26 0 15 0 0 0 0 0 0
销售点27 0 0 7.2 0 0 0 0 0
销售点28 0 0 8.9 0 0 0 0 0
销售点29 0 0 0 10.3 0 0 0 0
销售点30 0 0 0 9 0 0 0 0
销售点31 0 0 0 0 7.7 0 0 0
销售点32 0 0 0 0 8 0 0 0
销售点33 0 0 0 0 11.4 0 0 0
销售点34 0 0 0 0 12.1 0 0 0
销售点35 0 0 0 10.7 0 0 0 0
问题三结果的分析及验证
对该结果进行灵敏度分析:
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 40.00000 6.300000 5.700000
3 45.00000 29.40000 INFINITY
4 30.00000 0.2000000 9.400000
5 38.00000 0.2000000 8.000000
6 29.00000 10.20000 INFINITY
7 35.00000 50.50000 INFINITY
8 25.00000 5.700000 4.500000
9 28.00000 5.500000 5.00000
12
由表可知,基地2和基地6弹性较大,可选范围比较大,因此我们仅使和m2
值等于1,最终结果为使基地二和基地6总增产90.1吨(需求与原提供量之m6
差)即可。
对于表中所有的数据均满足我们对于约束条件的要求,所以在我们的假设成立的情况下,我们可以认为一定程度上,该数据正确,该分配方案可行,最终所得的结果即是最小的支出费用。
六 参考文献
[1] 姜启源等.数学模型(第四版).北京:高等教育出版社,2003年8月 [2] 谢金星.优化模型与LINGO/LINGO软件。北京:清华大学出版社,2005.07 [3] 司守奎,孙玺箐.数学建模算法与应用.北京:国防工业出版社,2012.
七、附录
附录清单
附录1:求解问题一的LINGO程序
附录2:问题一的灵敏度分析
附录3:求解问题二的LINGO程序
附录4:问题二的灵敏度分析
附录5:求解问题三的LINGO程序
附录6:问题三的灵敏度分析
13
附录正文
附录1:求解问题一的LINGO程序
model:
sets:
vendors/1..8/:a;
demand/1..35/:b;
links(vendors,demand):x,c;
endsets
data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7;
c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29 26 29 32 37 44 41 48 54 46 52
35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37
50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36
67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10
52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21
26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38
7 22 31 44 41 26 18 25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65
14
38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
s=0.4;
enddata
min=s*@sum(links(i,j):c(i,j)*x(i,j));
@for(vendors(i):@sum(demand(j):x(i,j))=a(i));
@for(demand(j):@sum(vendors(i):x(i,j))<=b(j));>=b(j));>
End
附录2:问题一的灵敏度分析
Row Current RHS Allowable Allowable
RHS INCREASE DECREASE
2 40.00000 7.800000 0.7000000
3 45.00000 11.20000 2.400000
4 30.00000 10.70000 2.400000
5 38.00000 2.400000 5.500000
6 29.00000 2.400000 5.500000
7 35.00000 2.400000 4.800000
8 25.00000 0.7000000 4.500000
9 28.00000 0.7000000 4.800000
10 6.500000 4.500000 0.7000000
11 10.20000 4.800000 0.7000000
12 12.00000 4.800000 0.7000000
13 14.30000 0.7000000 7.800000
15
14 13.00000 0.7000000 7.800000
15 11.00000 4.800000 0.7000000
16 14.00000 4.500000 0.7000000
17 9.500000 4.800000 2.400000
18 10.00000 4.800000 2.400000
19 8.400000 INFINITY 8.400000
20 10.50000 INFINITY 10.50000
21 7.000000 INFINITY 7.000000
22 8.500000 2.400000 7.800000
23 12.00000 0.7000000 7.800000
24 11.60000 2.400000 11.20000
25 12.50000 2.400000 11.20000
26 13.60000 INFINITY 11.20000
27 9.000000 INFINITY 9.000000
28 7.300000 INFINITY 7.300000
29 10.00000 4.800000 2.400000
30 12.70000 INFINITY 2.400000
31 7.400000 INFINITY 7.400000
32 6.700000 INFINITY 6.700000
33 12.50000 INFINITY 12.50000
34 9.600000 2.400000 9.600000
35 15.00000 2.400000 10.70000
36 7.200000 2.400000 7.200000
37 8.900000 2.400000 8.900000
38 10.30000 5.500000 2.400000
39 9.000000 5.500000 2.400000
16
40 7.700000 INFINITY 7.700000
41 8.000000 5.500000 2.400000
42 11.40000 5.500000 2.400000
43 12.10000 5.500000 2.400000
44 10.70000 5.500000 2.400000
附录3:求解问题二的LINGO程序
model:
sets:
vendors/1..8/:a;
demand/1..35/:b;
links(vendors,demand):c,x;
shorts/1..35/:d;
endsets
data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7;
c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29 26 29 32 37 44 41 48 54 46 52 35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33 39 31 37 50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42 48 40 36 67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10 52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21 26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38 7 22 31 44 41 26 18
17
25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65 38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
d=710 700 580 600 570 480 500 610 440 705 610 630 590 490 570 460 530 640 665 650 580 680 685 560 660 430 540 620 630 680 695 690 560 520 500;
enddata
min=@sum(links(i,j):0.4*c(i,j)*x(i,j))+@sum(demand(j):(b(j)-@sum(ve
ndors(i):x(i,j)))*d(j));
@for(vendors(i):@sum(demand(j):x(i,j))=a(i));
@for(demand(j):@sum(vendors(i):x(i,j))<=b(j));>=b(j));>
@for(demand(j):b(j)-@sum(vendors(i):x(i,j))<=0.3*b(j));>=0.3*b(j));>
end
附录4:问题二的灵敏度分析
Row Current RHS Allowable Allowable
RHS INCREASE DECREASE
2 40.00000 1.240000 0.9800000
3 45.00000 1.240000 0.9800000
4 30.00000 1.240000 0.9800000
5 38.00000 1.240000 0.9800000
6 29.00000 1.240000 0.9800000
7 35.00000 1.240000 0.9800000
8 25.00000 1.240000 0.9800000
9 28.00000 1.240000 0.9800000
10 6.500000 0.9800000 1.240000
11 10.20000 0.9800000 1.240000
12 12.00000 INFINITY 3.600000
13 14.30000 INFINITY 4.290000
14 13.00000 INFINITY 3.900000
18
15 11.00000 INFINITY 3.300000
16 14.00000 INFINITY 4.200000
17 9.500000 INFINITY 2.850000
18 10.00000 INFINITY 3.000000
19 8.400000 0.9800000 1.240000
20 10.50000 INFINITY 3.150000
21 7.000000 INFINITY 2.100000
22 8.500000 INFINITY 2.550000
23 12.00000 INFINITY 3.600000
24 11.60000 INFINITY 3.480000
25 12.50000 INFINITY 3.750000
26 13.60000 INFINITY 4.08000
27 9.000000 INFINITY 2.700000
28 7.300000 INFINITY 2.190000
29 10.00000 INFINITY 3.000000
30 12.70000 INFINITY 3.810000
31 7.400000 INFINITY 1.240000
32 6.700000 0.9800000 1.240000
33 12.50000 INFINITY 3.750000
34 9.600000 INFINITY 2.880000
35 15.00000 INFINITY 4.500000
36 7.200000 INFINITY 2.160000
37 8.900000 INFINITY 2.670000
38 10.30000 INFINITY 3.090000
39 9.000000 0.9800000 1.240000
40 7.700000 0.9800000 1.240000
41 8.000000 0.9800000 1.240000
42 11.40000 INFINITY 3.420000
19
43 12.10000 INFINITY 3.630000
44 10.70000 INFINITY 3.210000
45 -4.550000 INFINITY 1.950000
46 -7.140000 INFINITY 3.060000
47 -8.400000 1.240000 0.9800000
48 -10.01000 1.240000 0.9800000
49 -9.100000 1.240000 0.9800000
50 -7.700000 1.240000 0.9800000
51 -9.800000 1.240000 0.9800000
52 -6.650000 1.240000 0.9800000
53 -7.000000 1.240000 0.9800000
54 -5.880000 INFINITY 2.52000
55 -7.350000 1.240000 0.9800000
56 -4.900000 1.240000 0.9800000
57 -5.950000 1.240000 0.9800000
58 -8.400000 1.240000 0.9800000
59 -8.120000 1.240000 0.9800000
60 -8.750000 1.240000 0.9800000
61 -9.520000 1.240000 0.9800000
62 -6.300000 1.240000 0.9800000
63 -5.110000 1.240000 0.9800000
64 -7.000000 1.240000 0.9800000
65 -8.890000 1.240000 0.9800000
66 -5.180000 INFINITY 0.9800000
67 -4.690000 INFINITY 2.010000
68 -8.750000 1.240000 0.9800000
69 -6.720000 1.240000 0.9800000
70 -10.50000 1.240000 0.9800000
71 -5.040000 1.240000 0.9800000
20
72 -6.230000 1.240000 0.9800000
73 -7.210000 1.240000 0.9800000
74 -6.300000 INFINITY 2.700000
75 -5.390000 INFINITY 2.310000
76 -5.600000 INFINITY 2.400000
77 -7.980000 1.240000 0.9800000
78 -8.470000 1.240000 0.9800000
79 -7.490000 1.240000 0.980000
附录5:求解问题三的LINGO程序
Model
sets:
vendors/1..8/:a;
demand/1..35/:b;
links(vendors,demand):x,c;
increase/1..8/:l;
changes/1..8/:m;
endsets
data:
a=40 45 30 38 29 35 25 28;
b=6.5 10.2 12 14.3 13 11 14 9.5 10 8.4 10.5 7 8.5 12 11.6 12.5 13.6 9 7.3 10 12.7 7.4 6.7 12.5 9.6 15 7.2 8.9 10.3 9 7.7 8 11.4 12.1 10.7; c=42 27 18 13 17 25 33 41 38 42 37 30 24 16 20 25 28 39 44 40 41 37 33 35 29 26 29 32 37 44 41
48 54 46 52
35 20 11 24 21 18 26 34 31 29 29 24 13 9 5 10 13 24 29 32 26 22 18 20 14 11 14 17 22 29 26 33
39 31 37
50 35 26 39 36 33 41 48 46 38 38 33 28 24 20 19 22 33 38 41 35 31 27 21 15 14 11 12 17 28 35 42
21
48 40 36
67 52 43 56 53 50 57 55 54 45 45 46 45 41 37 32 35 40 37 40 34 30 32 26 28 32 31 25 20 18 24 34 28 19 10
52 40 40 53 53 43 41 39 32 32 35 42 45 41 37 32 29 30 24 18 16 20 24 33 36 39 42 39 35 24 17 9 3 12 21
26 14 14 27 28 21 15 13 6 17 27 34 24 16 20 25 27 22 16 8 14 18 22 35 29 26 29 32 37 31 24 17 23 29 38
7 22 31 44 41 26 18 25 27 30 39 46 41 33 37 42 45 35 38 41 46 45 44 52 46 43 46 49 54 58 51 50 56 56 65
38 23 15 28 29 22 30 38 31 39 35 36 25 17 21 26 29 38 41 33 39 38 34 36 30 27 30 33 38 45 42 42 48 47 53;
s=0.4;
enddata
min=s*@sum(links(i,j):c(i,j)*x(i,j));
@bin(m(i));
@for(@sum(m(i))=2);
@for(@sum(l(i)*m(i))=@sum(b(j))-@sum(a(i)));
@for(@sum(a(i)+l(i)*m(i))=b(j));
@for(@sum(demand(j):x(i,j))=a(i)+l(i)*m(i));
end
附录6:问题三的灵敏度分析
Row Current Allowable Allowable
RHS Increase Decrease
2 40.00000 6.300000 5.700000
3 45.00000 29.40000 INFINITY
4 30.00000 0.2000000 9.400000
5 38.00000 0.2000000 8.000000
22
6 29.00000 10.20000 INFINITY
7 35.00000 50.50000 INFINITY
8 25.00000 5.700000 4.500000
9 28.00000 5.500000 5.000000
23
要求:
1、 正文小四号字体,行距1.5倍;
2、 正文中的公式必须亲自用公式编辑器编写;
3、 摘要、目录的页码形式为I、II等,正文的页码形式为1、2
等;
4、 注意论文排版,要求规范整洁,具体可参看教材的排版; 5、 上交前需验收,验收不合格则拒收;
6、 星期四交打印版和对应的电子版。电子版上交要求:word的命
名方式:姓名—学号—题目,发送到邮箱:lee77105@163.com
1
范文四:蔬菜的运输方式
蔬菜的运输方式 上商蔬菜SHANGHAIVEGETABLES20吡(2j:37—38 藏加工'
,一?1|'F'f,|一
善
霉??尊餐:=蛩《一管譬:蚤:;誊.警
I一蛰每-蚤-期毒:鸯.誓?每.譬誊
'i霉燕褰宴疃?麓
所谓蔬菜运输就是指采用各种工具和设备,通 过多种方式使蔬菜商品在区域之间实现位置移动的 过程.它是蔬菜商品在流通过程中形成物流的媒
蔬菜的运输业越 舟,也是蔬菜商品化生产的继续.
发达,越能促进蔬菜基地的商品化生产,加速蔬菜商 品的流通,扩大流量,活跃蔬菜经济,对于蔬菜周年 生产和均衡供应都有重要意义.蔬菜空间移动的基 本要求是"及时,准确,安全,经济".蔬菜运输应考 虑流通区域间的交通运输条件,选择适宜的运输工 具及运输形式,力求用最少的时间,走最短的路,花 最低的成本,以最有效的商品保护,安全及时地将蔬 菜商品运达目的地.目前,世界上发达国家的商品
运输供应"的办法.在美 蔬菜大多采取"适地生产,
国,商品蔬菜主要产地集中在加里福尼亚,亚利桑 那,佛罗里达和德克萨斯等州,由于运输业发达,短 时间内就可将蔬菜运抵全国各地.在日本,蔬菜生 产集中在爱知,千叶,长野,静冈,广岛,高知等县,其 商品蔬菜量占全国的60%,一天之内就能将蔬菜运 达全国各地.近十几年来,我国的蔬菜运输业也有
很大的发展,现正迅猛的速度向前推进. 紊后,在提高畜禽重量,成活率等方面都获得了良好 的效果.国内现已建成用于饮料添加剂的年产100T 大蒜索油剂及IO00T大蒜索粉剂的工业化生产装 置.当前国内大蒜作为农产品,还未得到充分的开 发利用,绝大多数大蒜都用于鲜食.困此,加快大蒜 加工产业化势在必行.
5医药制品
每吨鲜太蒜中可提炼出精油6,5kg,每1大蒜 精油售价为3OO元.大蒜精油是一种抗菌杀菌的药 物,对多种球菌和大肠杆菌,伤寒杆菌,痢疾杆菌,百 日咳菌及霉菌,病毒,阿米巴虫,晓虫等都有良好的 抑制和杀灭作用.此外,大蒜精油还有降低胆固醇, 三酸甘油酯和脂蛋白的功能,可以制成片剂,口服液 或葡萄糖滴注液临床使用,蒜精口服液日常食用也 可增强人体的抗病能力.
目前,我国的蔬菜运输通常有公路运输,海洋运 输,内河运输,铁路运输,航空运输和联运等.各种运 输方式都有自身的优缺点,如公路运输方便,成本低, 但振动大,速度慢,运载力小,效率低.海洋运输运载 量大,成本低,但易受地理条件限制,且航行受季节影 响较大.内河运输成本低,运载量大,行驶平稳,振动 损伤少,但速度较慢.铁路运输运载量大,速度快,安 全,准时,不受季节影响,但没有铁路的地方,不能直 接运达.航空运输优点是不受地形条件限制,运行速 度快,蔬菜在运途中损伤少,但运量少,运费高.所谓 联运,是指蔬菜商品从产地到目的地的运输全过程使 用同一运输凭证,采用两种或两种咀上不同运输工具 的相互衔接的运送过程.如铁路,公路联运,水陆联
运,江海联运等.国外普遍应用的联运方式是:把适 用公路运输的拖车装于火车的平板车上或轮船内,到 达终点站或港口时,把拖车卸下来,挂在牵引车后面. 进行短距离的公路运输,直达目的地.联运可以充分 利用运输能力,促进各种运输方式协作,简化托运手 续,缩短途中滞留时间,节省运费.
在采用各种交通工具运送蔬菜时,有的采用散 装运输.即蔬菜商品不进行包装,基本上是自然状 态装人运输工具直接运输,它具有装卸方便的优点, 但易造成机械损伤,是一种落后的运输方法.有的 采用集装箱运输.即使用集装箱为装卸容器,将蔬 菜商品装进各种规格不同的集装箱内,直接送到目 的地卸货.这种运输方法可节省包装材料和费用, 同时集装葙能反复使用,减少搬运次数,商品损伤 少,便于机械化装卸,简化运输手续,有利于联运的 发展.
随着我国综合国力的增强,大市场,太流通的进 一
步完善,交通,装载设备的不断现代化,我国的蔬 菜运输业必将与发达国家接轨,实现现代化. ……j{{…i…{I{?i'{it{'…i{i{'I…i{{'{…一{,…? ?
国外动态?
尽J本蝓鲜潼褰产晶
批发市场(一》
方志权
(上海市蔬菜工作领导小组办公室2O?62) 日本鲜活农产品批发市场主要分为两种类型: 一
类是中央批发市场,分布在20万人口上的城 市,大多是都,道,府,县(相当于省会)城市,市场开 办者必须是地方公共团体,并需经农林水产大臣许 一
37—
范文五:蔬菜运输方式的选择
第7题 蔬菜运输方式的选择
某公司欲将一批易坏蔬菜从A地运往B地,共有汽车、火车、直升飞机三种运输工具可供选择,三种运输工具的主要参考数据如下:
运输工具 途中速度 途中费用 装卸时间 装卸费用
(千米/小时) (元/千米) (小时) (元)
汽车 50 8 2 1000
火车 100 4 4 2000
飞机 200 16 2 1000 若这批蔬菜在运输过程中的损耗为300元/小时,问采用哪种运输方式比较好,即运输过程中的费用与损耗之和最小。
分析:商品的运输过程是增加成本的过程,要想在商品的营销中获利最高,必然尽可能降低其成本。对于本问题而言,若采用飞机运输可以减少途中时间,即减少蔬菜损耗,但租用运输工具的费用较高;若采用火车运输,途中费用比较节约,但装卸不便;而采用汽车运输将增加途中的时间,因此作出运输方式的决策,主要是在减少途中费用和时间上找到合理的结合点,尽可能减少总支出,控制成本的提高。
解:设A、B两地间距离为s千米,则采用三种运输工具的费用和时间可用下表给出:
运输工具 途中费用(元) 途中时间(小时)
汽车 8s,1000
火车 4s,2000
飞机 16s,1000
分别用c、c、c 表示用汽车、火车、飞机运输时的123
总支出,则有:
由c 、c 、c 的表达式及s,0可知:123
c,c恒成立; 13
所以可以有以下结论:
230千米时,采用汽车运输较合理。
米时,采用火车、汽车均可。
230千米时,采用火车运输比较合理。
回顾:由上面解决问题的过程可知,因为c1,c3 不成立,所以采用直升飞机运输不可能成为最合理的运输方式,事实上,飞机运输的优势体现在速度上,即由于减少途中时间而减少损耗,下面探讨当蔬菜损耗率为多少时,直升飞机运输可能成为最佳的运输方式。
设损耗率为x元/小时,则
要使直升飞机运输成为最好的运输工具,只需满足:
即
所以可以有如下结论成立
不小于170千米时,当损耗率达到多少可以采用直升飞机运输与 AB两地间距离有关,其关系式由( 3)式给出。
练习7
1(某公司准备将一批货物用直升飞机从甲地运到乙地,在运输过程中,有两种装卸方式可供选择,即内部装卸和外部装卸。其中采用内部装卸方式可以增加途中速度,减少途中时间,但装卸时间增加;而采用外部装卸方式恰好相反,可以节约装卸时间,下面是两种方式下的参数:
装卸方式 平均速度 装货时间 卸货时间
(千米/小时) (小时) (小时)
请讨论如何对运输方式进行决策。
2(某地打算建造一座总跨度为l米的桥梁,现在准备就造几个桥墩问题进行决策。在决策过程中,主要考虑以下两个因素:(1)建造桥墩的费用,(2)造桥所需钢材的费用,其中,若桥墩数减少,随着两桥墩间跨度的增大,造单位长度的桥梁所需钢材将增加。如果假设任意两个桥墩间的距离相等,造一个桥墩的费用为p 元,桥梁所用钢材的单价为c(元,千克),桥梁的钢材用量与两桥墩间距离(桥孔长)成正比例关系,比例系数为K,即若桥孔长为X米,则钢材需用量为KX(千克,米)。请你作出正确的决策。
3(某运输公司欲将一批易坏物品从甲地运往乙地,其中有三种方式可供选择,其主要参考数据如下:
运输方式 装卸时间 装卸费用 运输速度 途中费用
(小时) (元) (千米,小时) (元,公里)
火车 4 400 100 4
汽车 2 200 50 6
直升飞机 2 200 200 8
若这批物品的损耗为 300元,小时,甲乙两地间距离为2000公里,请问:
(1)哪种运输方式比较合理;
(2)若物品损耗率不变,当甲、乙两地间距离为多少时火车是最好的运输方式;
(3)若甲、乙两地相距200公里,损耗率达到多少时,直升飞机运
输最好.
练习7
则有: 若T,T12
所以,当甲、乙两地间距离大于196公里时,应采用内部装卸方式运输,当两地间距离为196公里左右时,两种方式均可,否则,采用外部运输方式。
2(设n为桥孔数,桥孔长为x米,则桥墩数为(n-1)个,且等式
造桥墩的费用为p(n-1)元
钢材的费用=钢材用量×钢材单价
=(Kx?l)?c
所以造桥总费用
T,p(n-1)+Klc? x
3((1)分别用c,c,c表示火车、汽车、飞机运输的123
总费用,则有:
所以,采用火车运输最经济。
(2)设甲、乙两地间距离x公里,则
若火车运输最合理,只需满足c,c且c,c。1213
由c,c 得x,160(公里) 12
由c,c得x,320(公里) 13
所以当甲、乙两地间距离大于320公里时,火车运输最好。
(3)设损耗率为K元/小时,则
由c,c得K,650 13