线性规划解工厂选址问题.docx
《线性规划解工厂选址问题.docx》由会员分享,可在线阅读,更多相关《线性规划解工厂选址问题.docx(17页珍藏版)》请在冰点文库上搜索。
线性规划解工厂选址问题
线性规划解工厂选址问题
摘要
本文讨论了工厂选址最优化问题,建立了整型规划模型,并且运用了重力法,在MATLAB及lingo中编程求解工厂选址的位置。
在资源稀缺的市场竞争时代,如何优化资源配置是每个生产公司在日益激烈的市场竞争中求生存、促发展的有效途径和理智选择,求解结果可以给公司一个合理的选择
针对问题一,首先利用MATLAB中的绘图工具箱,令月份为自变量,公司的月需求量为因变量。
将其进行拟合,可以看出利用linearfitting进行拟合,拟合效果最好,如图1,图2,图3。
可以求出月需求量关于月份的函数,将预测的结果进行误差分析,得到表1,精确度非常高,将12月带入方程中即可得出预测值,程序见附录一。
针对问题二,本文利用lingo软件中的整型规划求最优解。
将模型简化成0—1整数规划。
利用LINGO进行LP优化求解得到成本最小值,并用以确定各个厂的生产规模。
为了方便建模,我们忽略了交叉工资弹性和运输竞争。
生产成本=月总工资+货物量的运输成本。
求出各厂的生产量,与各厂大概人数。
工厂规模利用工厂人数表示,可以得到表2的结果。
针对问题三,根据第二问的0-1变量,确定出各个工厂所供应的城市。
在需求点(各个城市的坐标)、运输量及线性运输费率不变的前提下,我们将运输成本作为唯一决策因素。
于是对该静态选址问题建立模型。
通过MATLAB,利用重心法为各个工厂确定最优选址,对运输路径进行优化。
得到其运输成本最优解。
本文模型能很好的预测每个工厂的生产量,并且可以为工厂选址提供一定的参考。
本模型不考虑工厂储备以及运输过程中的运输竞争,假设每一地每月的最大值为工厂规模确定的依据,在实际中会有一定的偏差。
关键词:
线性拟合,0—1整数规划[1],重力算法[2]
一、问题的重述
1.1研究背景
在资源稀缺的市场竞争时代,如何优化资源配置是每个生产公司在日益激烈的市场竞争中求生存、促发展的有效途径和理智选择。
本案例是根据其上一年11月向各城市供应的需求量,来预测下一年对各城市的供应量。
并且新厂还要根据对各城市的供应量来扩大生产规模。
其生产规模则可选择一个生产量最大的城市来算出其生产规模。
事实表明经营方向,产品构成和服务水平基本相同的企业能够获得更大的利润。
地址选择要以便利顾客为首要原则,同时考虑各个地方的工资水平及运输费用,将选址问题进行建模,可以得到一个合理的解决方案。
1.2问题的提出
本文将要解决以下几个问题:
问题一:
请根据所给数据预测每地当年12月各地区的产品需求量。
问题二:
根据所给工资标准及运输价格等条件确定各加工厂的生产规模。
问题三:
如果允许重新设定新厂位置,请根据相关条件为新厂选址并给做出评价。
二、问题的分析
对本文提出的新厂选址相关的3个问题,我们逐一做如下分析:
问题一的分析:
我们将18个城市一年11月的需求量利用MATLAB进行曲线拟合,经过试验可以知道利用线性拟合可以得到最好的拟合曲线,利用每一条曲线的函数,将自变量等于12代入,可以得到12月份的预测值。
问题二的分析:
根据所给工资标准及运输价格等条件确定各加工厂的生产规模,生产规模应该是指工厂的人数,根据所给的运输路程和基本工资,结合其约束条件的规划模型,可以运用规划优化模型进行求解。
由于案例提供了各城市的月需求量、各工厂到各城市的距离和工资标准,我们可以建立以生产量和加班时间为决策变量;通过决策变量来表示工厂的人数,构建工资和运输成本最低的目标函数;再根据附件数据可以找出一个约束条件:
工厂对每个城市的供应量不能超过它的生产量加上存储量,再通过国家对每月加班时间的要求和我们的合理假设(每个城市只由一个工厂提供产品)再得到两个约束,在目标函数和约束条件都合乎逻辑的情况下,建立规划模型。
问题三的分析:
在问题二中我们得到了一个优化后的结果,即:
每个工厂所供应的城市。
在需求点(各个城市的坐标)、运输量及线性运输费率不变的前提下,我们将运输成本作为唯一决策因素。
于是对该静态选址问题建立模型。
通过MATLAB,利用重心法为各个工厂确定最优选址,对运输路径进行优化。
得到最短运输距离,从而使使运输成本降低。
三、模型假设
针对本文提出的问题,我们做了如下模型假设:
1.题中所给数据真实可靠
2.加班不超过36小时,每天工作8小时,每月按30天计算
3.不考虑节假日,天气情况,运输竞争的影响
4.假定每年的生产量不受仓库容量影响
5.运输成本之受距离影响
6.任一厂每个人加班情况相同
四、符号说明
本文常用符号见下表,其它符号见文中说明.
符号
符号说明
单位
五、建模与求解
5.1问题一的建模与求解
问题一要求根据各地1月至11月的产品需求量,预测12月的产品需求量。
我们小组最初采用了灰色预测模型,发现拟合效果存在较大误差,后来又改用cftool工具箱进行了傅里叶级数拟合,拟合效果更符合,预测性较好。
5.1.2产品需求预测模型的建立
运用MATLAB中的cftool工具箱进行拟合预测,采用线性拟合:
y=a*(sin(x-pi))+b*((x-10).^2)+c,进行曲线拟合,最终得到拟合效果更好的函数图像与模型。
以下以郑州、南京、杭州三个城市为例,得到模型预测方程与曲线拟合效果:
图一郑州的拟合曲线
函数表达式Y=4.688*10^4*(sin(x-pi))-76.41*(x-10).^2)+4.02*10^5
图2南京的拟合曲线
Y=3.341*10^4*(sin(x-pi))-1983*(x-10).^2)+4.776*10^5
图3杭州的拟合曲线
Y=7.057*10^4*(sin(x-pi))-1101*(x-10).^2)+4.284*10^5
依据题目要求,根据所给数据(见附录二)预测当年12月各地区的产品需求量,已求得各地的产品需求量模型,预测结果如下:
表112个月的预测值
地名
1
2
3
4
5
6
7
8
9
10
11
12
天津
300600
487900
415300
480900
476100
440900
415300
424600
382200
379000
358800
382200
太原
246400
580900
417100
553500
477300
316000
417100
417300
311100
361200
377000
311100
石家庄
328500
473400
455400
486800
481200
336700
455400
503200
427900
474000
352100
427900
济南
361200
391300
568300
408300
471800
336000
568300
552000
369800
448400
388100
369800
郑州
311700
403000
488600
452600
517200
335700
488600
552000
377000
379000
453100
377000
西安
314500
424600
436300
427900
474000
392100
436300
379000
480900
476100
440900
480900
上海
345800
417300
487800
369800
448400
388100
487800
394100
336700
436300
379000
336700
南京
353500
503200
492400
388000
437400
442400
492400
397600
435300
455400
557200
435300
合肥
377000
552000
492600
397600
435300
390700
492600
398800
424600
568300
474000
424600
武汉
382200
379000
507800
358800
425800
398400
507800
428500
385800
417300
369800
385800
重庆
505000
394100
527500
428500
457200
422700
527500
314500
353500
503200
388000
353500
杭州
368300
414400
397200
457100
512000
373800
397200
345800
394100
468500
457200
394100
长沙
327500
429800
270800
403400
453100
369700
270800
353500
414400
457100
512000
414400
南昌
311100
361200
200700
411500
463800
383200
200700
417300
345800
417300
369800
345800
贵阳
369600
415100
181700
430500
475400
425800
181700
503200
353500
503200
388000
353500
福州
417500
409800
226500
493600
453800
334500
226500
425800
377000
572000
397600
377000
广州
524900
404100
262500
433800
420100
427100
262500
463800
382200
379000
318800
382200
南宁
417400
447100
369300
444700
410500
397600
369300
430500
209800
353500
403200
209800
任取三个数进行误差分析,可以看出预测结果的真实性。
表2误差分析表
实际值
220000
353500
368300
预测值
188680
320308
293766
误差
-14%
-9%
-20%
可以看出,模型的预测结果比较真实
5.1.3模型的求解和分析
1.模型求解
运用MATLAB进行编程运算预测12月各地的产品需求量,程序如下:
a = 4.688e+04
b = -76.41
c = 4.02e+05
x=[1;2;3;4;5;6;7;8;9;10;11;12]
y = a*(sin(x-pi)) + b*((x-10).^2) + c;
plot(x,y)
5.1.4模型检验(或误差分析或仿真)
由上面拟合曲线可以看出效果很好,R方很接近于1,任意抽取一个数据,如将太原的x=3带入模型方程,求得的预测值与实际值基本吻合,可以看出模型拟合优度很好。
5.2问题二的建模与求解
本题要求根据所给工资标准及运输价格等条件确定各加工厂的生产规模。
由于案例提供了各城市的月需求量、各工厂到各城市的距离和工资标准,在忽略交叉工资弹性和运输竞争的情况下,我们可以建立以生产量和加班时间为决策变量。
通过决策变量来表示厂的人数,构建工资和运输成本最低的目标函数;再通过国家对每月加班时间的要求和我们的合理假设(每个城市只由一个工厂提供产品)再得到两个约束,在目标函数和约束条件都合乎逻辑的情况下,建立线性规划模型,并用LINGO进行优化。
5.2.2线性规划--工厂规模模型的建立
利用lingo软件中的整型规划求最优解。
将模型简化成0—1整数规划。
利用LINGO进行LP优化求解得到成本最小值,并用以确定各个厂的生产规模。
5.2.3模型的求解和分析
1.模型求解
通过计算,可以得到5月份各个城市的需求量总和最大。
设:
每个厂的五月份的产量为:
;
每个厂五月份的加班时间为:
各个工厂的人数:
;
各个工厂的总工资:
;
各个工厂的总运输成本:
;
我们建立模型如下:
目标函数:
约束条件:
工厂对每个城市的供应量不能超过它的生产量:
i工厂提供j城市产品为1,否则为0:
利用lingo软件解线性方程的功能对模型进行求解,可以得到如下数据
X11768324.
T10.000000
X21738720.
T236.00000
X3415240.0
T30.000000
X41169440.
T40.000000
X5439480.0
T50.000000
X6896920.0
T60.000000
2.结果分析
从上面的结果可以看出:
各个厂五月份的生产量:
x1=1768324;x2=1738720;x3=41524;x4=1169440;x5=439480;x6=896920;
需要加班的工厂:
t2=36;
各个工厂的人数规模:
R1=73680;R2=62997;R3=17301;R4=48726;R5=18311;R6=37371;
产品提供情况:
1号工厂提供天津、太原、石家庄、济南的产品;
2号工厂提供合肥、武汉、重庆、长沙的产品;
3号工厂提供上海、广州的产品;
4号工厂提供南京、杭州、福州的产品;
5号工厂提供郑州、西安的产品;
6号工厂提供南昌、贵阳、南宁的产品。
由于对最大生产容量不考虑的原因,所以各厂生产x1至x6,结果合理可行。
各个工厂的人数最大的有6、7万多人,其余均小于5万人,而二厂即使正常工作时间的生产量供应不足,也可以通过加班增产。
5.3问题三的建模与求解
通过第二问各厂对指定城市的供应,我们采用0-1变量法确定制定城市,则使得重新建厂时,在需求点(各个城市的坐标)、运输量及线性运输费率不变的前提下,我们将运输成本作为唯一决策因素。
利用重心法可得到最优解,将求解得到的值带入计算,可以使得运输成本有明显降低。
5.3.1数据的预处理
首先根据网上资料得到18个城市的经纬度坐标如下:
天津(39.095963,117.180176)太原(37.872685,112.549438)
石家庄(38.056742,114.510498)济南(36.668419,116.982422)
郑州(34.759666,113.620605)西安(34.252676,108.94043)
上海(31.231592,121.464844)南京(32.045333,118.806152)
合肥(31.821565,117.224121)武汉(30.581179,114.32373)
重庆(29.573457,106.54541)杭州(30.278044,120.168457)
长沙(28.207609,112.939453)南昌(28.690588,115.839844)
贵阳(26.667096,106.633301)福州(26.086388,119.300537)
广州(23.14036,113.269043)南宁(22.816694,108.363647)
5.3.2重心法新厂设址模型的建立
通过第二问各厂对指定城市的供应,我们采用0-1变量法确定制定城市,则使得重新建厂时,在需求点(各个城市的坐标)、运输量及线性运输费率不变的前提下,我们将运输成本作为唯一决策因素。
利用重心法可得到最优解,将求解得到的值带入计算,运输成本有明显降低。
5.3.3模型的求解和分析
1.模型求解
根据第二问的0-1变量,确定出各个工厂所供应的城市。
在需求点(各个城市的坐标)、运输量及线性运输费率不变的前提下,我们将运输成本作为唯一决策因素。
于是对该静态选址问题建立模型。
通过MATLAB,利用重心法为各个工厂确定最优选址,对运输路径进行优化。
得到其运输成本最优解。
2.结果分析
利用MATLAB进行分析可以得出每一地到重心的距离如表3所示。
厂编号
1
2
3
4
5
6
距离
82.221
81.503
83.473
82,382
77.657
90.154
六、模型的推广与评价
6.1模型的优点
针对问题1:
能在一定的误差范围内预测出工厂需求量。
针对问题2:
能够准确地判断出工厂的生产规模以及加班情况
针对问题3:
可以为工厂的选址做出合理的评估,可以找到最优方案
6.2模型的缺点
针对问题1:
容易受极端数据的影响
针对问题2:
实际生活中要考虑每月剩余产品的累加不超过库存量以及没人的加班情况不尽相同
针对问题3:
不能精确求出每厂的经纬度坐标
6.3模型的推广
利用数据拟合可以很好处理一些比较繁杂的数据,并且起能很好反映出结果,因此问题一采用此解法比较合理。
优化模型便是求最优解,而第二题便是要求最小成本的基础下来设定工厂规模,而0-1变量也能使问题简便化,使问题不会那么繁琐。
本题当中所涉及的采购模型考虑到的影响因素、约束条件还不够多。
因此结果可能有些偏差。
故对大型工厂相对误差较大,但适合小型的工厂预测和小型工厂规模优化。
参考文献
【1】司守奎,数学建模方法与应用[M].国防工业出版社,2015.4.
【2】赵静,数学建模与数学实验[m].高等教育出版社,2014.8
附录
1.附录清单
附录一:
求解问题一的Matlab程序
附录二:
求解问题二的lingo程序
附录三:
求解问题三的Matlab程序
2.附录内容
附录一:
求解问题一的Matlab程序
y = a*(sin(x-pi)) + b*((x-10).^2) + c;
plot(x,y)
clc,clear
y1=[1 2 3 4 5 6 7 8 9 10 11]';
x0=[209800353500503200388000437400442400492400397600435300455400557200]';
cftool;
附录二:
求解问题二的Matlab程序
min=(x1*100/((240+t1)*10))*(1900+1.5*1900*t1/240)+(x2*100/((240+t2)*10))*(1740+1.5*1740*t1/240)+(x3*100/((240+t3)*10))*(1710+1.5*1710*t3/240)+(x4*100/((240+t4)*10))*(1800+1.5*1800*t4/240)+(x5*100/((240+t5)*10))*(1840+1.5*1840*t5/240)+(x6*100/((240+t6)*10))*(1650+1.5*1650*t6/240)+58548000*(307*y11+559*y21+930*y31+1520*y41+1562*y51+1400*y61)+69708000*(255*y12+570*y22+591*y32+1238*y42+1400*y52+1337*y62)+60384000*(116*y13+470*y23+695*y33+1313*y43+1415*y53+1306*y63)+68196000*(178*y14+283*y24+730*y34+1289*y44+1287*y54+1122*y64)+66240000*(392.5*y15+257*y25+358*y35+945*y45+104.4*y55+979*y65)+57708000*(678*y16+696*y26+213*y36+802*y46+109.9*y56+119.6*y66)+58536000*(850*y17+565*y27+104.4*y37+128.9*y47+987*y57+641*y67)+66864000*(637*y18+287*y28+769*y38+107.1*y48+834*y58+618*y68)+68196000*(622*y19+254*y29+634*y39+932*y49+786*y59+689*y69)+60936000*(745*y1A+45*y2A+426*y3A+621*y4A+575*y5A+540*y6A)+638000000*(119.2*y1B+107.7*y2B+525*y3B+382*y4B+863*y5B+114.3*y6B)+61440000*(845*y1C+559*y2C+941*y3C+111.7*y4C+823*y5C+479*y6C)+61440000*(102.7*y1D+7..34*y2D+551*y3D+383*y4D+319*y5D+489*y6D)+55656000*(936*y1E+605*y2E+682*y3E+680*y4E+413*y5E+264*y6E)+60384000*(114.7*y1F+125.1*y2F+775*y3F+266*y4F+726*y5F+108.1*y6F)+68640000*(127*y1G+825*y2G+112.2*y3G+100.9*y4G+564*y5G+196*y6G)+62988000*(160.8*y1H+128*y2H+109.5*y3H+610*y4H+271*y5H+581*y6H)+53652000*(173.1*y1I+146.87*y2I+112.8*y3I+963*y4I+632*y5I+102.4*y6I);
585480*y11+697080*y12+603804*y13+681960*y14+662400*y15+577080*y16+585360*y17+668640*y18+681960*y19+609360*y1A+633000*y1B+614400*y1C+614400*y1D+556560*y1E+603840*y1F+686400*y1G+629880*y1H+536520*y1I<=x1;
585480*y21+697080*y22+603804*y23+681960*y24+662400*y25+577080*y26+585360*y27+668640*y28+681960*y29+609360*y2A+633000*y2B+614400*y2C+614400*y2D+556560*y2E+603840*y2F+686400*y2G+629880*y2H+536520*y2I<=x2;
585480*y31+697080*y32+603804*y33+681960*y34+662400*y35+577080*y36+585360*y37+668640*y38+681960*y39+609360*y3A+633000*y3B+614400*y3C+614400*y3D+556560*y3E+603840*