下料问题.doc

关于一维下料问题的研究摘要： “下料问题”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题此类问题在工程技术和工业生产中有着重要和广泛的应用在生产实践中通常要求解决用料最省、浪费最少等问题下料问题即是其一。属最优化研究范畴一维下料问题是生产实践中常见的问题，优化下料要求最大限度地节约原材料，提高原材料的利用率。本文介绍了两种方法，其一提出分支定界算法优化一维下料问题，并用MATLAB编写程序，通过计算机来完成这一复杂的过程。另一种方法-lingo，针对单一原材料的一维下料问题, 建立了整数规划模型, 然后将模型转化为求解最优下料方式问题; 利用lingo进行编程, 实现循环调用得到一维下料问题的局部最优解。实际上本文就是给出了解决适当规模下料问题的求解方法该方法既可手工演算又可通过计算机求解。在实践中可以借鉴使用Abstract： The “utting Stock Problem”is a problem of dividing raw materials in the same shape into several parts in different shapes This kind of problem has important and wide appliance in engineering and industry productionBeing living to give birth to in the practice requires use to anticipate to save most usually and Squanders at least and so on ，First of all Immediate future the cutting stock problem is ，The category optimization is researched the category 。For one thing, Onedimensional cutting stock problems can be encountered at the production stage of many areas，the optimization of cutting requests to save raw material at most and improve the use of raw materia1A branch and bound algorithm for solving onedimensional cutting stock problems can be completed by computerFor another, Aimed at raw material for a single one-dimensional cutting stock problem, This paper established integer programming model and then transformed into themodel under optimal feeding method for solving the problem;the use of lingo programming to achieve loop calls are one- dimensional cutting stock problem of the locally most optimal solution.Actually, Resolution means that the original is give out ，the proper scale issue may be resolved ，As yet the handwork performs mathematical calculations，But may solve a problem by means of the calculating machine ，Being living in the practice may draw lessons from the use关键词：一维下料问题 分支定界算法 ILp函数 最优化onedimensional cutting stock problems branch-andbound algorithm ILp function Optimization问题的提出研究背景下料问题”是把相同形状的原材料分割加工成若干不同规格大小的零件的问题 ，根据原材料长度是否相等，一维优化下料可以分为单一型材的优化下料和多型材的优化下料其中需求零件的宽度相等的情况称为一维下料问题。一维下料问题是在已知原材料和顾客需求坯料的情况下优化下料使原材料的使用率达到最大或废料达到最小的问题。一个好的下料方案首先应该使原材料的利用率最大, 从而减少损失, 降低成本, 提高经济效益。其次要求所采用的不同的下料方式尽可能少, 即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间, 既提高成本, 又降低效率。此外, 每种零件有各自的交货时间, 每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下, 以最少数量的原材料, 尽可能按时完成需求任务, 同时下料方式数也尽量地小。不同的下料方案需要的原材料数量不同，通过优化下料方案减少原材料的数量，降低成本。常用的求解一维下料问题的方法有分支定界法、动态规划法和整数规划法等方法。对于大规模的一维下料问题,许多专家尝试用遗传算法来求解,并取得了较为满意的结果。2003年李培勇分完全下料和不完全下料建立优化模型，并使用混合遗传算法求解。2004年王小东等提出了一种基于启发式多级序列线性优化思想的新算法，将下料优化问题转化为多级序列线性优化问题求解。2004年张春玲等讨论了解决一维下料问题的常用算法以及算法的适用情况。这些等等等等。下面我再具体介绍一下前人的解法。1.线性规划。首先建立优化线性模型，然后对模型进行求解。可以用分支定界法求解。2.遗传算法。从应用的角度对遗传算法做了认真的分析和研究，然后将其应用于一维下料问题的求解，提出了一种基于遗传算法的求解方法。 3.遗传模拟退火算法。针对遗传算法存在“过早收敛”的现象及其良好的兼容性，考虑将模拟退火算法与遗传算法相结合，用来求解一维下料问题。4.广义粒子群优化算法，结了合遗传算法和模拟退火算法。该算法通过引入交叉算子、变异算子和模拟退火操作，增加粒子的多样性，以求算法实现全局搜索能力和局部探索能力的平衡 5.顺序启发式算法。通过多种启发式策略和优化方法的应用 ,弱化了启发式算法生成排样方式时本身的贪婪性质。求解一维下料问题时 ,考虑多个优化目标 ,排样结果具有更广泛的应用价值 ,可满足各种生产环境的需求。该算法设计简洁明了 ,易于理解。且计算时间可以被生产实践所接受。6.非线性规划。对于较大规模的一维下料问题，材料的切割模式和数量要得到整数解，用非线性规划求解比较好。能实现一维下料的优化，等到满意结果，使用料最省，利润最大。研究意义对于工业和建筑业的许多原材料，例如圆钢、圆木、钢筋、铁板、薄铁皮、塑料板以及纸张、布匹等。一般都存在下料或裁剪问题。特别是在一些比较复杂的情况下，不采用科学方法、不寻求最优下料法，往往造成原材料的很大浪费 。所以在很多生产部门中，为了提高原材料利用率，降低生产成本，在给定长度的原材料上，要求消耗尽可能少的原材料数量 ，切割出不同数量和规格的零件。当零件数量较少时，可用人工方法解决，当零件数量较多时 ，用人工方法对原材料利用率不是很高，会造成资源大量浪费，导致生产成本上升。因此最大限度地节约原材料，提高原材料的利用率是生产中提高效益的一个重要手段。 在当今社会，随着国民经济的飞速发展，一维下料问题在建筑、电力、水利等领域获得了越来越广泛的应用。寻找一种最优的下料方案，不仅可以节省原材料，降低生产成本，而且能够为企业带来直接的经济效益，促进国民经济的健康发展。因此，开展对一维下料问题的研究具有重要的理论意义和工程应用价值。一维下料问题是一个经典的组合优化问题。怎样找到一种较好的下料方案,成为节约原材料,降低成本,从而提高企业的经济效益的重要问题之一。本文采用整数线性规划方法来求最优解。问题的陈述一个好的下料方案首先应该使原材料的利用率最大，从而减少损失 ，降低成本 ，提高经济低效率此外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地小。 我们来做两道例题来讲解一下一维下料问题的解法。例一：线材合理下料问题：有一批原料钢材(如钢管、钢筋、角钢、钢梁等)，每根长7.4m现需做100套钢架，每套利用长2.9 m、2.1 m、1.5m的钢材各一根问如何下料，才能使所用的原料最省?例二：钢管下料问题：现有原料钢管每根19米，客户需求4米50根，6米20根，8米15根，现有如下问题需要解决：如何下料最节省？如何尽可能满足厩客需求？问题的分析一维下料问题是生产实践中常见的问题，优化下料要求最大限度地节约原材料，提高原材料的利用率。对于优化下料问题 ，属于整数规划问题 ，要想求出下料方案的最优解，从计算复杂性理论分析， 该问题属于NP难题 ，即无法在多项式时间内求解。 虽然整数规划问题是 NP难题，但是线性问题却是有有效算法的。所以可以考虑不先求解整数规划问题而先来求解其相应的线性问题。本文主要是采用线性规划来求解，建立数学模型，分析求最优解。一维下料的数学模型早在 1939年就已由 Kantorovich提出由于这类模型属于整数规划。所以其求解十分复杂，其原因是可行的下料方式数目可能很大，从而造成要求解的整数规划的维数很高我们必须知道：首先，一个好的下料方案应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益其次，要求所采用的不同下料方式尽可能少，即希望用最少的下料方式来完成任务因为在生产中转换下料方式需要费用和时间 ，既提高成本，又降低效率因此下料问题的目标是在生产能力容许的条件下，以最少数量的原材料 ，尽可能按时完成需求任务 ，同时下料方式数也尽量地少为顺利解决下料问题 ，根据该问题的特点，我们先从最基本的单目标决策问题人手 ，以材料损耗最少为目标，通过不同的数学原理建立最优化模型 ，得出最初的结果。然后逐步增加其约束条件最小的下料方式数 ，并根据该约束条件进一步完善 我们的最优化模型 ，得到损耗最少，下料方式数又小的结果接下来检验在所得下料方式的排列中，是否存在可以满足时间条件限制的排列方式若存在 ，则该结果即为最优解；若不存在 ，则这个结果就不符合题意 ，必须重新构建多目标决策的最优化模型，在新模型中以客户时间需求为第一 目标 ，材料损耗最少，下料方式最少为第二 目标因此，在下料时就应该优先生产那些有时间限制要求的零件 ，并且求出在需求的时间段内下料方式和损耗的最优结果 ，紧接着再求 出剩余 板材下料方式和损耗的最优结果 ，从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果。模型建立的准备分支定界法的介绍与基本思想分支定界算法是20世纪60年代初由Land，Doig和Dakin等人提出的，其算法不仅可用于求解纯整数或混合整数线性规划问题，也适用于几乎任何组合优化问题。它采用了分而治之的算法策略，在分析一个组合最优化问题一切可行解的过程中，采取了必要的限制条件，设法排除可行域中大量非最优解区域，从而能够求解一些规模较大的问题。分枝定界法的思想是：先求解整数规划相应的线性规划问题，如果其最优解不符合整数条件，则需要增加新的约束来缩小可行域，得到新的线性规划问题再求鳃。这样通过求解一系列线性规划问题，最终得到问题的整数最优解。求解整数线性规划分支定界法MATLAB程序：function x，Y=ILp(f，G，h，Geq，heq，lb，ub，x，id，options)globa1 upper opt c x0 A b Aeq beq ID options；if nargjn10，options=optimset()；optionsDisplay=off;optionsLargeScale=0ff; endif nargjn9，id=ones(size(f)；endif nargjn8，x=；endif nargjn7 lisempty(ub)，ub=inf*ones(size(f)；endif nargjn6 lisempty(1b)，lb=zer0s(size(f)；endif nargjn 5，heq=；endif nargjn4，Geq=；endupper=inf；c=f；x0 = x；A =G；b= h；Aeq Geq；beq =heq；ID=id；ftemp=ILP(1b(：)，ub(：)；x=opt；Y=upper；function ftemp=ILP(vlb，,vub)globa1 upper opt c x0 A b Aeq beq ID options；x，ftemp，how=linprog(c，A，b，Aeq，beq，rib，rub，x0，options)；if how 000005 in 0rder to avoid errorreturn；end；if max(abs(x*IDround(x*ID)000005 in oId to avoid erroropt=x; upper=ftemp；retum ；elseopt=opt；x；return；end；end；notintx=find(abs(xround(x)=000005)；in 0rder toavoid errorint x=fix(x)；tempvlb=vlb；tempvub=rub；if rub(notintx(1，1)，1)：intx(notintx (1，1)，1)+1；tempvlb(notintx(1，1)，1)=intx(notintx (1，1)，1)+1ftemp=IntLP(tempvlb，vub)；end；if vlb(notintx(1，1)，1)C：0，0.1，0.2，0.3，0.8，0.9，1.1，1.4；A=1，2，0，1，0，1，0，0；0，0，2，2，1，1，3，0；3，1，2，0，3，1，0，4；b=100；100；100； =ILp(C，A，b，0，0，0，0，0，0，0，0，inf，inf，inf，inf，inf，inf，inf，inf)；=。例二按照客户需要在一根原料钢管上安排切割的一种组合。合理切割模式的余料应小于客户需要钢管的最小尺寸 合理切割模式如下：模式4米钢管根数6米钢管根数8米钢管根数余料（米）14003231013201341203511116030370023为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？两种标准1原料钢管剩余总余量最少2所用原料钢管总根数最少决策变量按第i种模式切割的原料钢管根数（i=1，27）目标1（总余量）min=3x1+x2+3x3+3x4+x5+x6+3x7模式4米根数6米根数8米根数余料14003231013201341203511116030370023需求502015满足需求的约束条件为最优解：x2=12,x5=15,其余为0；最优值：27 按模式2切割12根,按模式5切割15根，余料27米 当余料没有用处时，通常以总根数最少为目标 目标2（总根数）min=x1+x2+x3+x4+x5+x6+x7 s.t最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 与目标1的结果“共切割27根，余料27米” 相比: 虽余料增加8米，但减少了2根 当余料没有用处时，通常以总根数最少为目标 在模型窗口中输入如下代码：min=x1+x2+x3+x4+x5+x6+x7 4*x1+3*x2+2*x3+x4+x550x2+2*x4+x5+x6+x720x3+x5+2*x715都是第二种下料方式 125根原钢，第四种下料方式 50根原钢，共用 175根原钢小结下料问题的求解，答案比较活泛尽管在所需原材料总块数上答案一致，但在施工方案上却可以大相径庭通常，在求解小规模问题时利用手工演算，可以找到全部解，而利用Lindo、Microsoft Office Excel等只可找到部分解，而通常实际问题只需找到一个解即可结束语 经过几个月的学习，我终于完成了关于一维下料问题的研究这一毕业设计。刚开始时，我对下料问题并不是太了解，后来经过不断的学习和总结，现在已经变得很清晰了。本文介绍了简单的一维下料问题，我通过不断地查阅资料和书籍，同时在吕老师的耐心指导下，现在已经知道解决一维下料问题有很多种方法