木材运输问题数学建模论文.docx
《木材运输问题数学建模论文.docx》由会员分享，可在线阅读，更多相关《木材运输问题数学建模论文.docx（14页珍藏版）》请在冰点文库上搜索。
木材运输问题数学建模论文
B题木材运输问题
摘要
木材运输问题是木材物流系统优化决策的一个重要问题，科学合理地进行木材运输方案的制定对提高木材物流效率，降低物流成本具有直接的影响。
在本题中，我们通过建立线性规划模型和用遗传模型（运输问题），使木材运输总费用最小。
针对木材运输总费用最小的问题，我们建立线性规划模型，使用lingo软件对该模型进行求解。
由于木材在实际运输过程中按其发货地和目的地之间的距离运输条件及运输路线的通达情况，存在2种基本的运输形式:
一是直接从供材点运送到需材点，称为直达运输;二是木材经过物流配送中心等物流结点贮存中转后才运达需材点，称为中转运输；由这2种运输构成的问题为混合运输问题。
最终对该模型求解，所得的最小费用为131461元。
同时，对于这个问题，我们也建立了遗传模型，使用遗传算法的方法，运用matlab软件对这个模型进行求解。
最终得出最小费用为110704元。
建立这两种模型，我们可以通过这两个模型进行对比，以便我们选出最优的方案来解决费用最小的问题，从而延伸到实际生活中，解决实际问题。
通过对比，建立遗传模型比建立规划模型更好，因此最优费用为110704元。
对于以上模型，还是有很多的不足之处，需要对这些模型进行修改。
关键词：
线性规划模型lingo软件遗传模型总费用最小
一、问题重述
1.1问题背景
木材运输问题是木材物流系统优化决策的一个重要问题科学合理地进行木材运输方案的制定对提高木材物流效率，降低物流成本具有直接影响，更重要的是能为客户提供优质高效的物流服务。
由于森林资源分布客户分布供需状况道路网络和自然条件等特点决定了木材运输问题的复杂性和动态性。
1.2问题介绍
以2个采育场［永安林业（集团）股份有限公司福溪采育场和半村采育场］4月份木材生产供应及其下游企业需求的基本数据为基础进行分析。
这2个采育场主要生产杉木、松木和其它杂木，这些木材主要以原木（含有多种等级）和薪材的形态进行运输，为方便表达材种，下面以K1（原木）和K2（薪材）2种木材为主进行研究。
选取这2个采育场主要的5个点［A1（水东源）、A2（吉布岭）、A3（黄岩）、A4（大西坑）、A5（半村）］为供材点，供材点下游有2个木材物流配送中心P1（公司货场1）、P2（公司货场2），物流配送中心为其下游的4个需材点［B1（永安人选板厂）、B2（永林蓝豹）、B3（永安福星）、B4（福州福人）］供应木材。
各木材的供求数量及单位运输（汽车运输）费用如表1所示，每个需材点每种木材直达运输订发货量起点限制值Ei为80m3，物流配送中心呑吐能力为500m3/月。
请设计一种运输方案，使总运费最小。
二、问题分析
木材在实际运输过程中按其发货地和目的地之间的距离运输条件及运输路线的通达情况，存在2种基本的运输形式:
一是直接从供材点运送到需材点，称为直达运输；二是木材经过物流配送中心等物流结点贮存中转后才运达需材点，称为中转运输。
由这2种运输构成的问题为混合运输问题。
设有m个供材点，n个需材点，q个物流配送中心，则木材直达、中转混合运输模式如图1。
然后，针对木材运输总费用最小的问题，我们建立线性规划模型，运用lingo软件对该模型进行求解。
三、基本假设
1、假设只对将木材运输费用作为单目标问题进行了研究；
2、木材销售市场销售量稳定，不会出现经济紧缩、市场萧条等动荡因素等
影响销售量。
3、木材运输途中没有突发状况产生影响，不会造成木材的浪费。
4、运输过程中不会出现其它客观问题（如交通事故、天气影响和工具维修等不利因素），木材可以安全到达目的地。
四、名词解释及符号说明
符号
意义
从第i个供求点到第p个物流配送中心的第k种木材的运输费用
从第p个物流配送中心到第j个需求点的第k种木材的运输费用
从第i个供求点到第j个需求点的第k种木材的运输费用
从第i个供求点到第p个物流配送中心的第k种木材的运输量
从第p个物流配送中心到第j个需求点的第k种木材的运输量
从第i个供求点到第j个需求点的第k种木材的运输量
第i个供求点与第j个需求点有第k种木材的供需关系
为第i个供材点的订发货起点限制值
为供材点i的第k种木材的供应量
为需求点j的第k种木材的需求量
木材物流中心p的最大吞吐能力
m
供材点个数
n
需材点个数
q
木材物流中心个数
o
木材等级数
五、模型的建立与求解
5.1模型一的建立
题中要求每个需材点每种木材直达运输定发货量起点限制值为80，那么如果需材点的订货量少于80时，需求方就会从木材的中专贮存地或者物流配送中心处订购，，通过物流配送中心先将伐区楞场没有直接运输的木材调集起来，再进行配送，因为他们会考虑到运输成本。
采用这种运输形式，虽然物流费用增加，但对于需求者来说，却会带来很多方便，由于这些中转结点的木材材种比较齐全，需求者可以在此一次采购到所需的材种及数量，减少交易次数，同时由物流配送中心统一配送，这样既节约了运输费用，降低了交易成本，又加速了物资的流通周转。
吞吐能力则是动态概念，它是某计划期内仓库中转货物的能力，这与调运决策模型中的调量是相吻合的，所以木材的中转运输量与配送中心的吞吐能力有关由于物流配送中心的中转活动只是物流的一个中间环节，它从供材点调运木材时相当于一个需材点，在向用户供应木材时又相当于一个供材点因此，考虑中转运输时，要把物流配送中心同时看成供材点和需材点，其最大供应量等于最大需求量，均为吞吐能力的一半。
在实际的木材运输中对于某种木材来说往往其供材点的总供应量与其需材点的总需求量是不相等的，有时会供过于求，有时会供不应求。
当木材采用中转运输时，木材中转站相当于一个中间点，由于中间点只起转运作用，所以中间点的流量为零，即运出这点的木材总量与运进这点的木材总量之差为零。
因此，当供材点某种木材的总供应量小于需材点的总需求量时，供材点虽会将该木材全部出售，但需材点对该木材的需求仍会出现不足，而供材点某种木材的总供应量大于需材点的总需求量时，供材点只会出售需材点对该木材所需要的量此时供材点的该木材则会出现剩余。
综合考虑多种因素，木材运输成本最低的优化模型为：
现采用0—1规划模型，
其中：
当时，以上模型为木材直达运输模型；
当以上模型为木材中转运输模型
模型一的求解：
对于第一种k1的总供材量和总需求量分别为
对于第一种k2的总供材量和总需求量分别为
因此，对于k1,k2来说供材点原木的总供应量小于需材点原木的总需求量。
，
5.2模型二的建立
遗传算法（geneticalgorithm，GA）是一种根据生物进化引出的强大启发式搜索和优化方法，它借用了生物遗传学的观点，通过自然选择遗传变异等作用机制，实现各个个体的适应性的提高具有全局优化性能通用性强且适合于并行处理的算法。
遗传算法求解问题的运算包括5个步骤
步骤一，初始化:
随机产生M个染色体（表示问题的解），构成初始种群，设定迭代总次数为T
步骤二，个体评价:
评价当代种群中各个染色体的适应度
步骤三，选择运算:
将选择算子作用于群体，产生新种群
步骤四，产生新种群:
将交叉算子和变异算子作用于新种
步骤五，判断当前迭代次数r，若返回步骤二，否则结束
遗传算法求解问题的核心是进行编码、遗传操作算子设计、适应度函数的设计和对约束的处理
①编码
编码是应用遗传算法时要解决的首要问题，把问题的解编码成为染色体是遗传算法使用中的关键。
编码可以采用二进制编码实数编码整数或字母排列编码等形式
②设计适应度函数
适应度函数是用来区分群体中个体好坏的标准，是遗传算法计算的一个驱动力。
为了直接将适应度函数与群体中个体的优劣程度相联系，在遗传算法中适应度函数值规定为非负，其值越大表明适应度越好，适应度较高的个体遗传到下一代的概率较大通常可以采用界限构造法来确定其适应度函数，适应度函数可以表示为：
式中:
是当前所有代目标函数的最大值，此时随着代数会有所变化
③遗传操作算子选择策略
遗传算法的遗传操作算子一般包括选择交叉和变异3种基本形式，主要是它们使遗传算法具有了强大搜索能力
a、选择算子选择操作是为了从当前群体中选出优良的个体，使它们的基因有机会进入到下一代。
Holland提出的轮盘赌选择是最知名的选择方式，它的基本原理是根据每个染色体适应度值的比例来确定该个体的选择概率或生存概率。
b、交叉算子交叉运算是遗传算法区别于其他进化运算的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。
适合于二进制编码的个体交叉算子有单点交叉、两点交叉与多点交叉及均匀交叉。
单点交叉操作较简便，两点交叉法及多点或均匀交叉的信息量较大。
c、变异算子变异运算是对交叉过程中可能丢失的遗传基因进行修复和补充，并防止遗传算法收敛到局部最优解。
变异概率控制着变异操作被使用的频度变异概率取值较大时，可以产生较多的个体，增加群体的多样性，但会使遗传搜索变成随机搜索，变异概率取值较小时，会使某些基因位过早丢失的信息无法恢复。
④对约束的处理
在遗传算法中必须对约束条件进行处理，处理约束条件的方法主要有搜索空间限定法可行解变换法罚函数法。
其中，罚函数法是遗传算法用于约束优化问题最常用的方法，它通过对不可行解的惩罚将约束问题转换为无约束问题。
因此对木材运输问题采用罚函数法进行约束处理。
对于等式约束，可以将其转化为的形式，构造如下不等式约束的惩罚函数
对于不等式约束，可以将其转化为的形式，构造如下不等式约束的惩罚函数
式中:
为惩罚因子，为当前遗传代数，,取;递增系数为,为等式约束的个数，为不等式约束的个数。
根据以上约束条件可知原木需求点及薪材需求点需要中转运输，其它均为直达运输。
采用便于表达解的十进制编码方法根据运输问题解的特征将上述问题中的一个染色体表达成一个具有49个元素的矩阵，即,其中前20个元素分别表示原木从水东源、吉布岭、黄岩、大西坑半村分别运输2种木材到2个物流配送中心的运输量，第21个元素到第24个元素分别表示从2个物流配中心分别运输2种木材到永林蓝豹和福州福人，第25个元素到第49个元素分别表示从水东源、吉布岭、黄岩、大西坑半村运输原木到永安人造板厂、永安福星、福州福人的运输量和由水东源、吉布岭、黄岩、大西坑半村运输薪材到永安人造板厂福州福人的运输量。
随机生成40条染色体构成初始群体采用界限构造法来确定其适应度函数，采用与其适应度成比例的概率方法进行选择，选择概率,采用两点交叉法进行交叉操作，应用线性递减函数产生交叉概率，在第一代，取80%，线性递减到最后一代为40%，采用一个线性函数产生变异概率，即
当前代数/总代数，最大迭代次数设为200代
经过以上设计的遗传算法操作过程，得到其最小运输费用为110704元，该问题的最优运输方案如表2所示
六、模型的评价与推广
模型的优点：
1、本文建立的是以最小费用为目标的线性规划模型，采用lingo软件编程，实用价值高，结果准确。
2、本文所建立的模型分析思路简洁清晰，可以紧密联系到现实实际问题，只需要更改数据便可求其他的运输问题，具有推广型。
3、我们先对问题分析得到最优解，再用lingo编程验证了结果的最优性，使最后的结果更加真实可靠，具有说服力。
模型的缺点：
1、模型给出的约束条件可能也不太现实。
2、在实际生活中，运输问题一般不会达到供求量与需求量相等的情况，而我们的模型只是针对产销平衡的运输问题的，具有狭隘性。
七、模型结果的分析与检验
在所建立的模型中，我们的运算结果是通过工具软件Lingo运行得到的，运算结果较为准确。
我们根据运输问题中的供求关系，以及在假设成立的条件下，使用线性规划，遗传算法，Lingo软件编程等方法进行分析求解，使得我们的结果变得更合理、更简单。
但因为忽略一些的自然因素影响，使得结果与真实情况下存在一定误差。
由运算结果可知：
在运输问题中，在这种有若干个产销地的运价不变的情况下，有调运量增加，总运费反而会下降的奇怪现象。
所以我们可以根据所得到的结果来更有效的解决这种物流运输问题。
八、参考文献
［1］刘娜翠，林雅惠，邱荣祖．我国木材物流的现状与发展趋势［J］．物流技术，2006（8）:
19－22．
［2］伍学滨，刘国良，彭友霖．表上作业法在物资调运问题中的应用［J］．商场现代化，2007（522）:
30－31．
[3]丁满泉，朱锋峰，吴广潮．混合遗传算法求解双准则线性运输问题［J］．科学技术与工程，2007，7（8）:
1532－1535．
[4]戴庆，申静波．基于遗传算法的运输问题最优解研究［J］．天津理工大学学报，2008，24（3）:
43－46．
［5］雷英杰，张善文，李续武，等．MATLAB遗传算法工具箱及应用［M］．西安:
西安电子科技大学出版社，2005:
61．
[6]
[7]http：
//viewa51c95fb0242a8956bece431.html
九、附录
模型一：
model:
sets:
s/1..5/:
x,y;
t/1..2/:
Q;
d1/1..4/:
d,b;
link1（s,d1）:
c1,a1,x1,y1;
link2（s,t）:
c2,a2,x2,y2;
link3（t,d1）:
c3,a3,x3,y3;
endsets
data:
q=400500;
x=120143705065;
y=1901531007886;
d=1257018090;
b=2504060170;
c1=90110120200
78100115180
9395100250
8588110230
8010095140;
c2=87407152607050626340;
c3=70901002708010070300;
a1=110120130220
85110127180
110100110230
9298115300
85120103210;
a2=85507063708060706855;
a3=90112125245708295280;
enddata
min=@sum（link1（i,u）:
c1（i,u）*x1（i,u）+a1（i,u）*y1（i,u））+
@sum（link2（i,j）:
c2（i,j）*x2（i,j）+a2（i,j）*y2（i,j））+
@sum（link3（j,u）:
c3（j,u）*x3（j,u）+a3（j,u）*y3（j,u））;
@FOR（s（i）:
@sum（t（j）:
x2（i,j））+@sum（d1（u）:
x1（i,u））=x）;
@FOR（s（i）:
@sum（t（j）:
y2（i,j））+@sum（d1（u）:
y1（i,u））<=y）;
@FOR（t（j）:
@sum（s（i）:
x2（i,j））+@sum（s（i）:
y2（i,j））<=0.5*Q（j））;
@FOR（t（j）:
@sum（d1（u）:
x3（j,u））=@sum（s（i）:
x2（i,j）））;
@FOR（t（j）:
@sum（s（i）:
y2（i,j））=@sum（d1（u）:
y3（j,u）））;
@for（d1（u）:
@sum（s（i）:
x1（i,u））+@sum（t（j）:
x3（j,u））<=d）;
@for（d1（u）:
@sum（s（i）:
y1（i,u））+@sum（t（j）:
y3（j,u））=b）;
@for（link1:
@semic（80,x1,200））;
@for（link1:
@semic（100,y1,200））;
end
模型二：
model:
sets:
s/1..14/:
a;d/1..6/:
b1,b2;
link（s,d）:
c,x;
endsets
data:
a=1201437050655005001901531007886500500;
b1=1257018090500500;b2=2504060170500500;
c=901101202008740
781001151807152
93951002506070
85881102305062
80100951406340
709010027010001000
801007030010001000
1101201302208550
851101271807063
1101001102307080
92981153006070
851201032106855
9011212524510001000
70829528010001000;
enddata
min=@sum（link:
c*x）;
@for（s（i）|i#le#5:
@sum（d（j）:
x（i,j））=a）;
@for（d（j）|j#le#4:
@sum（s（i）|i#le#7:
x（i,j））<=b1）;
@for（s（i）|i#ge#8#and#i#le#12:
@sum（d（j）:
x（i,j））<=a）;
@for（d（j）|j#le#4:
@sum（s（i）|i#ge#8:
x（i,j））=b2）;
@for（d（j）|j#eq#6#or#j#eq#5:
@sum（s（i）|i#ge#8#and#12#ge#i#or#i#le#5:
x（i,j））<=0.5*b2）;
@sum（link（i,j）|i#eq#6#and#j#le#4:
x（i,j））=@sum（link（i,j）|j#eq#5#and#i#le#5:
x（i,j））;
@sum（link（i,j）|i#eq#13#and#j#le#4:
x（i,j））=@sum（link（i,j）|j#eq#5#and#i#ge#8#and#i#le#12:
x（i,j））;
@sum（link（i,j）|i#eq#7#and#j#le#4:
x（i,j））=@sum（link（i,j）|j#eq#6#and#i#le#5:
x（i,j））;
@sum（link（i,j）|i#eq#14#and#j#le#4:
x（i,j））=@sum（link（i,j）|j#eq#6#and#i#ge#8#and#i#le#12:
x（i,j））;
!
@sum（link（i,j）|i#eq#13#and#j#le#4:
x（i,j））+@sum（link（i,j）|i#eq#6#and#j#le#4:
x（i,j））<=250;
!
@sum（link（i,j）|i#eq#14#and#j#le#4:
x（i,j））+@sum（link（i,j）|i#eq#7#and#j#le#4:
x（i,j））<=250;
@for（link（i,j）|i#le#12#and#i#ge#8#and#j#le#4:
x（i,j）>=100）;
@for（link（i,j）|i#le#5#and#j#le#4:
x（i,j）>=80）;
@for（link:
x>0）;
!
@for（link:
@semic（80,x,200））;
end
升级会员 