木材运输问题数学建模论文

1、b题木材运输问题摘要木材运输问题是木材物流系统优化决策的一个重要问题，科学合理地进行木材运输方案的制定对提高木材物流效率，降低物流成本具有直接的影响。在本题中，我们通过建立线性规划模型和用遗传模型（运输问题），使木材运输总费用最小。针对木材运输总费用最小的问题，我们建立线性规划模型，使用lingo软件对该模型进行求解。由于木材在实际运输过程中按其发货地和目的地之间的距离运输条件及运输路线的通达情况，存在2种基本的运输形式: 一是直接从供材点运送到需材点，称为直达运输;二是木材经过物流配送中心等物流结点贮存中转后才运达需材点，称为中转运输；由这2种运输构成的问题为混合运输问题。最终对该模型求解，

2、所得的最小费用为131461元。同时，对于这个问题，我们也建立了遗传模型，使用遗传算法的方法，运用matlab软件对这个模型进行求解。最终得出最小费用为110704元。建立这两种模型，我们可以通过这两个模型进行对比，以便我们选出最优的方案来解决费用最小的问题，从而延伸到实际生活中，解决实际问题。通过对比，建立遗传模型比建立规划模型更好，因此最优费用为110704元。对于以上模型，还是有很多的不足之处，需要对这些模型进行修改。关键词： 线性规划模型 lingo软件 遗传模型 总费用最小一、 问题重述1.1问题背景木材运输问题是木材物流系统优化决策的一个重要问题 科学合理地进行木材运输方案的制定对

3、提高木材物流效率，降低物流成本具有直接影响，更重要的是能为客户提供优质高效的物流服务。由于森林资源分布客户分布供需状况道路网络和自然条件等特点决定了木材运输问题的复杂性和动态性。1.2问题介绍以2个采育场永安林业（集团）股份有限公司福溪采育场和半村采育场4月份木材生产供应及其下游企业需求的基本数据为基础进行分析。这2个采育场主要生产杉木、松木和其它杂木，这些木材主要以原木（含有多种等级）和薪材的形态进行运输，为方便表达材种，下面以k1（原木）和k2（薪材）2种木材为主进行研究。选取这2个采育场主要的5个点a1（水东源）、a2（吉布岭）、a3（黄岩）、a4（大西坑）、a5（半村）为供材点，供材点

4、下游有2个木材物流配送中心p1（公司货场1）、p2（公司货场2），物流配送中心为其下游的4个需材点b1（永安人选板厂）、b2（永林蓝豹）、b3（永安福星）、b4（福州福人）供应木材。各木材的供求数量及单位运输（汽车运输）费用如表1所示，每个需材点每种木材直达运输订发货量起点限制值ei为80m3，物流配送中心呑吐能力为500 m3/月。请设计一种运输方案，使总运费最小。二、 问题分析木材在实际运输过程中按其发货地和目的地之间的距离运输条件及运输路线的通达情况，存在2种基本的运输形式: 一是直接从供材点运送到需材点，称为直达运输；二是木材经过物流配送中心等物流结点贮存中转后才运达需材点，称为中转运

5、输。由这2种运输构成的问题为混合运输问题。设有m个供材点，n个需材点，q个物流配送中心，则木材直达、中转混合运输模式如图1。 然后，针对木材运输总费用最小的问题，我们建立线性规划模型，运用lingo软件对该模型进行求解。 三、 基本假设1、 假设只对将木材运输费用作为单目标问题进行了研究；2、 木材销售市场销售量稳定，不会出现经济紧缩、市场萧条等动荡因素等影响销售量。3、 木材运输途中没有突发状况产生影响，不会造成木材的浪费。4、 运输过程中不会出现其它客观问题（如交通事故、天气影响和工具维修等不利因素），木材可以安全到达目的地。 四、名词解释及符号说明符号意义从第i个供求点到第p个物流配送中

6、心的第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模型一的建立题中要求每个需材点每种木材直达运输定发货量起点限制值

7、为80，那么如果需材点的订货量少于80时，需求方就会从木材的中专贮存地或者物流配送中心处订购，通过物流配送中心先将伐区楞场没有直接运输的木材调集起来，再进行配送，因为他们会考虑到运输成本。采用这种运输形式，虽然物流费用增加，但对于需求者来说，却会带来很多方便，由于这些中转结点的木材材种比较齐全，需求者可以在此一次采购到所需的材种及数量，减少交易次数，同时由物流配送中心统一配送，这样既节约了运输费用，降低了交易成本，又加速了物资的流通周转。吞吐能力则是动态概念，它是某计划期内仓库中转货物的能力，这与调运决策模型中的调量是相吻合的，所以木材的中转运输量与配送中心的吞吐能力有关由于物流配送中心的中转

8、活动只是物流的一个中间环节，它从供材点调运木材时相当于一个需材点，在向用户供应木材时又相当于一个供材点因此，考虑中转运输时，要把物流配送中心同时看成供材点和需材点，其最大供应量等于最大需求量，均为吞吐能力的一半。在实际的木材运输中 对于某种木材来说 往往其供材点的总供应量与其需材点的总需求量是不相等的，有时会供过于求，有时会供不应求。当木材采用中转运输时，木材中转站相当于一个中间点，由于中间点只起转运作用，所以中间点的流量为零，即运出这点的木材总量与运进这点的木材总量之差为零。因此，当供材点某种木材的总供应量小于需材点的总需求量时，供材点虽会将该木材全部出售，但需材点对该木材的需求仍会出现不足

9、，而供材点某种木材的总供应量大于需材点的总需求量时，供材点只会出售需材点对该木材所需要的量 此时供材点的该木材则会出现剩余。 综合考虑多种因素，木材运输成本最低的优化模型为： 现采用01规划模型， 其中：当 时，以上模型为木材直达运输模型； 当 以上模型为木材中转运输模型模型一的求解：对于第一种k1的总供材量和总需求量分别为对于第一种k2的总供材量和总需求量分别为因此，对于k1,k2来说供材点原木的总供应量小于需材点原木的总需求量。，5.2模型二 的建立 遗传算法( geneticalgorithm，ga) 是一种根据生物进化引出的强大启发式搜索和优化方法，它借用了生物遗传学的观点，通过自然选

10、择遗传变异等作用机制，实现各个个体的适应性的提高 具有全局优化性能通用性强且适合于并行处理的算法。遗传算法求解问题的运算包括5个步骤 步骤一，初始化: 随机产生m个染色体( 表示问题的解)，构成初始种群，设定迭代总次数为t 步骤二，个体评价: 评价当代种群中各个染色体的适应度 步骤三，选择运算: 将选择算子作用于群体，产生新种群 步骤四，产生新种群: 将交叉算子和变异算子作用于新种 步骤五，判断当前迭代次数r，若返回步骤二，否则结束遗传算法求解问题的核心是进行编码、遗传操作算子设计、适应度函数的设计和对约束的处理 编码编码是应用遗传算法时要解决的首要问题，把问题的解编码成为染色体是遗传算法使用

11、中的关键。编码可以采用二进制编码实数编码整数或字母排列编码等形式设计适应度函数适应度函数是用来区分群体中个体好坏的标准，是遗传算法计算的一个驱动力。为了直接将适应度函数与群体中个体的优劣程度相联系，在遗传算法中适应度函数值规定为非负，其值越大表明适应度越好，适应度较高的个体遗传到下一代的概率较大 通常可以采用界限构造法来确定其适应度函数，适应度函数可以表示为：式中:是当前所有代目标函数的最大值，此时随着代数会有所变化 遗传操作算子选择策略遗传算法的遗传操作算子一般包括选择交叉和变异3种基本形式，主要是它们使遗传算法具有了强大搜索能力a、 选择算子 选择操作是为了从当前群体中选出优良的个体，使它

12、们的基因有机会进入到下一代。holland提出的轮盘赌选择是最知名的选择方式，它的基本原理是根据每个染色体适应度值的比例来确定该个体的选择概率或生存概率。b、 交叉算子 交叉运算是遗传算法区别于其他进化运算的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。适合于二进制编码的个体交叉算子有单点交叉、两点交叉与多点交叉及均匀交叉。单点交叉操作较简便，两点交叉法及多点或均匀交叉的信息量较大。c、 变异算子 变异运算是对交叉过程中可能丢失的遗传基因进行修复和补充，并防止遗传算法收敛到局部最优解。变异概率控制着变异操作被使用的频度 变异概率取值较大时，可以产生较多的个体，增加群体的多样性，但

13、会使遗传搜索变成随机搜索，变异概率取值较小时，会使某些基因位过早丢失的信息无法恢复。 对约束的处理在遗传算法中必须对约束条件进行处理，处理约束条件的方法主要有搜索空间限定法可行解变换法罚函数法。其中，罚函数法是遗传算法用于约束优化问题最常用的方法，它通过对不可行解的惩罚将约束问题转换为无约束问题。因此对木材运输问题采用罚函数法进行约束处理。对于等式约束，可以将其转化为的形式，构造如下不等式约束的惩罚函数 对于不等式约束，可以将其转化为的形式，构造如下不等式约束的惩罚函数式中: 为惩罚因子，为当前遗传代数，,取;递增系数为,为等式约束的个数，为不等式约束的个数。根据以上约束条件可知原木需求点及薪

14、材需求点需要中转运输，其它均为直达运输。采用便于表达解的十进制编码方法 根据运输问题解的特征将上述问题中的一个染色体表达成一个具有49个元素的矩阵，即,其中前20个元素分别表示原木从水东源、吉布岭、黄岩、大西坑半村分别运输2种木材到2个物流配送中心的运输量，第21个元素到第24个元素分别表示从2个物流配中心分别运输2种木材到永林蓝豹和福州福人，第25个元素到第49个元素分别表示从水东源、吉布岭、黄岩、大西坑半村运输原木到永安人造板厂、永安福星、福州福人的运输量和由水东源、吉布岭、黄岩、大西坑半村运输薪材到永安人造板厂福州福人的运输量。随机生成40条染色体构成初始群体 采用界限构造法来确定其适应

15、度函数，采用与其适应度成比例的概率方法进行选择，选择概率 ,采用两点交叉法进行交叉操作，应用线性递减函数产生交叉概率，在第一代，取80%，线性递减到最后一代为40%，采用一个线性函数产生变异概率，即当前代数/总代数，最大迭代次数设为200代经过以上设计的遗传算法操作过程，得到其最小运输费用为110704元，该问题的最优运输方案如表2所示六、 模型的评价与推广模型的优点： 1、本文建立的是以最小费用为目标的线性规划模型，采用lingo软件编程，实用价值高，结果准确。2、本文所建立的模型分析思路简洁清晰，可以紧密联系到现实实际问题，只需要更改数据便可求其他的运输问题，具有推广型。3、我们先对问题分

16、析得到最优解，再用lingo编程验证了结果的最优性，使最后的结果更加真实可靠，具有说服力。模型的缺点：1、 模型给出的约束条件可能也不太现实。2、 在实际生活中，运输问题一般不会达到供求量与需求量相等的情况，而我们的模型只是针对产销平衡的运输问题的，具有狭隘性。七、模型结果的分析与检验在所建立的模型中，我们的运算结果是通过工具软件lingo运行得到的，运算结果较为准确。我们根据运输问题中的供求关系，以及在假设成立的条件下，使用线性规划，遗传算法，lingo软件编程等方法进行分析求解，使得我们的结果变得更合理、更简单。但因为忽略一些的自然因素影响，使得结果与真实情况下存在一定误差。由运算结果可知

17、：在运输问题中，在这种有若干个产销地的运价不变的情况下，有调运量增加，总运费反而会下降的奇怪现象。所以我们可以根据所得到的结果来更有效的解决这种物流运输问题。八、参考文献1刘娜翠，林雅惠，邱荣祖我国木材物流的现状与发展趋势j物流技术，2006( 8) :19222伍学滨，刘国良，彭友霖表上作业法在物资调运问题中的应用j商场现代化，2007( 522) :30313丁满泉，朱锋峰，吴广潮混合遗传算法求解双准则线性运输问题j科学技术与工程，2007，7( 8) :153215354戴庆，申静波基于遗传算法的运输问题最优解研究j天津理工大学学报，2008，24( 3) :43465雷英杰，张善文，李

18、续武，等 matlab遗传算法工具箱及应用m西安: 西安电子科技大学出版社，2005:61 6 /p-289644334.html 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;endsetsdata:q=400 500;x=120 143 70 50

19、 65;y=190 153 100 78 86;d=125 70 180 90;b=250 40 60 170;c1=90 110 120 200 78 100 115 180 93 95 100 250 85 88 110 230 80 100 95 140;c2=87 40 71 52 60 70 50 62 63 40;c3=70 90 100 270 80 100 70 300;a1=110 120 130 220 85 110 127 180 110 100 110 230 92 98 115 300 85 120 103 210;a2=85 50 70 63 70 80 60 70

20、 68 55;a3=90 112 125 245 70 82 95 280;enddatamin=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

21、):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

22、;d/1.6/:b1,b2;link(s,d):c,x;endsetsdata:a=120 143 70 50 65 500 500 190 153 100 78 86 500 500 ;b1=125 70 180 90 500 500;b2=250 40 60 170 500 500;c=90 110 120 200 87 40 78 100 115 180 71 52 93 95 100 250 60 70 85 88 110 230 50 62 80 100 95 140 63 40 70 90 100 270 1000 1000 80 100 70 300 1000 1000 110 120 130 220 85 50 85 110 127 180 70 63 110 100 110 230 70 80 92 98 115 300 60 70 85 120 103 210 68 55 90 112 125 245 1000 1000 70 82 95 280 1000 1000;enddatamin=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);