（机械设计及理论专业论文）基于线性规划的一维优化下料系统研究与开发.pdf

摘要 一维优化下料问题是设计领域的一个重要部分，在工程实践中有着广泛的应 用，它的求解自动化理论及方法对于设计自动化领域具有典型意义。由于其本身 具有n p 一完全的性质，求解具有很大的难度。为了满足诸多的限制条件，找到原材 料数量长度、零件毛坯数量长度之间的最佳对应关系，问题的解集 分庞大作 业研究的领域内也一直没有绝对合适的解决方案。 论文中在对目前存在的多种建模方法及求解方法进行综合比较之后，结合整 数规划跟线性规划的特点，提出了一种先利用树搜索算法求解可行下料方式，建 立使用材料最少的数学模型，然后利用m a t l a b 数学库中线性规划求解函数结合 分枝定界法对模型进行求解的解决方案，详细介绍了基于此模型算法结构的一维 优化下料系统的设计过程，并列出了在w i n d o w s 系统下的实例运行结果。此外又对 二、三维优化下料的模型建立和求解算法进行了探讨。 利用v i s u mc + + 开发的系统性能稳定，用户界面友好，基本实现了优化下料、 余料管理、下料原始数据和刀口数据管理等功能。对于节约生产原材料、减少物 资储备、降低产品成本、进一步增加企业利润，都有一定程度上的重要意义。 关键词：下料问题：整数规划；线性规划：n p 一完全；模型；算法 r e s e a r c ha n d d e v e l o p m e n t o no n ed i m e n s i o n a l o p t i m u m c u t t i n gs y s t e m b a s el i n e a r p r o g r a m m i n g a b s t r a c t o n ed i m e n s i o n a lc u t t i n gs t o c kp r o b l e mi s c a t e g o r i z e da s ac l a s s0 。 i m p o r t a n ta n dt y p i c a ld e s i g nt a s k s ，w h i c hh a sb e e nw i d e l yu s e di nv a r i o u s i n d u s t r i e s ，s ot h a ti t ss o l u t i o nm e t h o d o l o g ya n dt e c h n i q u e sa r ei m p o r t a nl n o to n l yt oi t s e l f ，b u ta l s ot oo t h e rd e s i g np r o b l e m s i ti s o n eo ft h e c o n s i d e r a b i fc o m p l i c a t e ds c h e d u l i n gp r o b l e m sd u et oi t sn p - c o m p l e t e n e s s t h ef u n d a m e n t a li s s u ei i e si nh o wt of i n dt h eb e s tc o r r e s p o n d i n gr e t a t i o r s b e t w e e nd i f f e r e n tf a c t o r ss u c hg ss t o c k l e n g t h s ，s t o c ks u p p lv ，p i e c e l e n g t h sa n dp i e c eo r d e rd e m a n d s i no r d e rt os a t i s f ys om a n yc o n sl r a i n t s t h ep r o b l e mr e s u l t si na ne x t r e m e l yl a r g en u m b e ro fs o h t i o ns e t s h e n c e o n e c a nh a r d l yf i n da b s o l u t e l ys a t i s f y i n g s o l u t i o n sw h e n d e a l i n gt h is p r o b l e mi n t h ef i e i do fp r o j e c tr e s e a r c h t h r o u g hg e n e r a lm o d e l sa n da l g o r i t h m sc o m p a r i s o nt h ec o m b i n a t i o n m e t h o do fl i n e a rp r o g r a m m i n ga n di n t e g e rp r o g r a m m i n gi sa d o p t e dt ot h i s t o t a lm a t e r i a lc o s tm i n i m i z a t i o nc o n s t r u c ts o l u t i o nm o d e l s as e a r c ht r e e i su s e dt od e v e l o pt h ep a t t e r ng e n e r a t i o nm e t h o da n dt h e i a t l a bc + 十m a t h l i b r a r y b r a n c ha n db o u n dt e c h n i q u ea r eu t i l i z e dt og e tt h eo p t i m iz a t i o n r e s u l t t h eo n ed i m e n s i o n a l o p t i m u mc u t t i n gs y s t e mb a s e ( o nt h i s a r c h i t e c t u r eh a sb e e n i m p l e m e n t e da n dt e s t e d o naw i n d o y v so sb a s e d w o r k s t a t i o n 2 - da n d3 - dc u t t i n gs t o c kp r o b l e m sa r ed i s c u s s e di na d d it i o n s o f t w a r ed e v e l o p e du s i n gv i s u a lc + + i se a s yo fo p e r a t i o nw it haf r i e n d l y a n dc o n v e n i e n tu s e r i n t e r f a c e ，i nw h i c hf u n c t i o n sa so p t i m u mc u t t i 【1 9 ， s u r p l u sm a t e r i a l sm a n a g e m e n t ，s t a n d a r ds l i t t e rk n i f ep a r a m e t e r sq u e r y ， s t o c k sa n d p i e c e s d a t am a n a g e m e n t a r ei n v 0 1 v e d r e s e a r c h e si nt h i s d i s s e r t a t i o nw i i ic o n t r i b u t et oe c o n o m i z er a wm a t e r i a l s ，r e d u c eo p e r a t i n g c o s t sa n di m p r o v et h ee n t e r p r i s e se c o n o m i ce f f i c i e n c y k e yw o r d s ：c u t t i n gs t o c kp r o b i e m ：i n t e g e r p r o g r a m m i n g ：l i n e a r p r o g r a m m i n g ：n p - c o m p l e t e ：m o d e l ：a 1 9 0 r i t h m 基于线性规划的一维优化下料系统研究与开发 1 绪论 制造、建筑等行业对角钢、钢管等一维型材消耗数量巨大，最大限度地节约 原材料，提高材料利用率，是工厂实际生产中的一项根本原则，这就对生产企业 的原材料的合理利用提出更高的要求。因此在现代企业生产中运用计算机进行生 产过程的材料消耗定额管理、生产工艺中的优化下料已成为迫切需要。 1 1 研究背景 11 1 选题背景 下料与排列问题可以视为相同的一个问题。两者都是针对如何使研究对象在 有限的空间中做最有效的空间利用所衍生出来的题目。排列问题是将已知的数个 对象依照其限制与特性在特定空间中做一有效的排列，使其空间使用率达到最 高。而切割下料问题是在一个预先给定的物料原材料上，将所要切割的对象摆放 在上面，进而使得物料浪费率最低。 制造过程中的优化下料问题是制造系统中资源优化利用问题之一。优化下料 涉及的问题很多，其中一维优化下料问题是制造过程中经常遇到的下料问题。钢 材、铝合型材等的切割中许多都是一维优化下料问题。 大连造船新厂每年消耗的钢材和铝合型材、管材数量巨大，涉及大景的一维 优化下料问题。一维优化下料问题一般描述为：在一定数量的给定长度的原材 上如何以最少的原材根数切割出所需数量的各种长度的零件毛坯。然而现行的 解决方法主要为利用传统的人工经验方法来处理此类问题，一般的人工下料法是 在给定的原材上先切割出长度最大的零件，然后在剩下的零件中切割出可能的最 长零件，依次切割，直至最后无法切割出任何一种规格零件为止，剩下的边角余 料就当废料处理。这种人工下料方法除浪费十分惊人外，下料计算复杂，耗费工 程技术人员的大量精力，并且容易下料出错。 也有一些应用行业采用计算机辅助下料，但是所用的算法和人工下料法基本 一样，原材料利用率并没有得到明显改善，仅仅是提高了工作效率。 大连理工大学硕士论文 1 1 2技术背景 一维优化下料问题作为一个经典的切割数学问题，前人已经进行过非常多的 研究并且已经得到了较为成熟的数学建模方法和求解方法，随着研究的不断深入 及各种新的优化方法的提出，在这个领域中国内外从理论和实际应用都取得了非 常大的突破。 从计算复杂性理论上看，一维优化下料问题属n p 完全问题，即不存在多项 式界算法。专家认为求解一个问题的解法，仅当其复杂性随输入规模的增加而多 项式增长时，这个算法才是实际有效的。因此，对于n p 完全问题，通常只能用 那种虽然不能保证是最优解但是接近最优解的近似算法来求解。为此，国内外关 于这方面的研究十分活跃，并提出了不少近似算法，g i l m o r e 与g o m o r y 1 - 2 1 用线 性规划建立的一刀切问题的数学模型；h a r l dd y c k h o f f h 【j 提出的线性规划方法 以及s a r k e rbr1 5 1 提出的动态规划方法等。 1 2 研究目的与任务 1 2 1 研究目的 下料与排列闯题对于切割制造工业而言是相当的重要的，一个好的下料算 法，可以增加原材料的使用率，降低材料的成本，当材料成本降低，相对的其价 格的弹性空间将变大，进而增加企业的市场竞争力。近来市场上也出现了一些优 化下料的软件，如华软科技发展有限公司的钢筋优化下料系统，主要用于建 筑钢筋下料计算；o p t i m u mc u t 的o p t i m u m c u t 一1 d 软件，主要实现了一维优化下 料方式的计算。以上软件或者是用于专业领域，功能单一，或者界面操作不方 便，因而未能在企业中得到广泛的应用。 论文的选题以企业的实际工作需要为背景以降低企业原材料成本，提高生 产效率为主要研究内容。通过对大连造船新厂一维线性原材料切割下料问题的综 合分析，利用科学的方式，建立理想的下料计算模型，并选取合适的求解算法设 计开发了一维优化下料系统，来解决均质规则线性材料下料问题。并期望最终解 能够达到使原材料利用率最高、材料浪费量最小的目的，进而使本研究能够在生 产制造企业中得到实际应用。 基于线| 生规划的一维优化下料系统研究与开发 1 2 2课题的任务 1 2 2 ，1问题描述 有m 种规格的原材料，长度分别为h i ( i = 1 ，2 ，m ) ，每种原材料的根数 为p ：要利用它们加工成n 种型号的坯料，它们的长度分别为l k ( k = 1 ，2 ， n ) ，每种型号坯料的需求量分别为q k ( k = 1 ，2 ，n ) ，这样可能的f 牛m 式1 f | 1 l 数为g 。针对n 种坯料，设长度为h i 的原材料共有h i 种截取方法。假设这些截 取方法是已知的，分别为( a ”a l ，2 。，a i j 。) 0 = 1 ，2 ，h 。) ，相应的余料为 ( c j l ，c 1 2 ，c j 3 ，e j n ) ( j = 1 ，2 ，h i ) ，其中a 1 k ( k = 1 2 ，n ) 表示长度为 h i 的原材料的第j 种截取方法中截取长度为l k 的坯料的根数。 显然，对i = 1 ，2 ，m ；j = l ，2 ，h i 满足： a 缸k h ( 1 ) ，l 设x j 表示长度为h i 的原材料采取第j 种截取方法的根数，当x j = o 时表示不采取 m。 此截取方法。为使用料最省，则必须使原材料用料总长度h l x j 达到最小同 i j 时还必须满足下料要求和约束条件( 1 ) 。由此，得到如下的整数规划问题： ， r a i n z = h i x j ， x i p i ，( i = l ，2 ，n ) 一 h i x a i k x l j 一 q k ( k = 1 ，2 ， 爿 x l j 0 ，x j 取整数 ( 5 ) 其中，a i k 还需满足约束条件( 1 ) 。 问题( 2 ) ( 5 ) 是一个整数规划问题，它的解x ：就是采取每种截取方法的原材料根 数。下料问题的一种下料方案由原材料h i 的h i 种截取方法( 吐l ，a i j 2 ，a j 。) 及采取这种截取方法的原材料根数x j 表示其中i = 1 ，2 ，r f l ：j ：1 ， 2 ，h 。 大连理工大学硕士论文 在这个问题中如果原料的种类m 与成品的规格n 的值都比较小，且最短成 品长度值较大时，可能的下料方式的种数g 不会很多，可以用人工试算的方法求 出a 及其相应边料o i ，从而建立线性规划问题的目标函数和约束条件，再用线性 规划解法求出模型的最优解，即得最优下料方案。但是，当m 和n 的值较大及 l k ( k = l ，2 ，n ) 较小时，可能的下料方式种数将成裂变式增加，无法通过人 工试算来建模和求解。因此，采用计算机自动确定本问题的所有可能的下料方 式，自动形成数学模型并求出最优解是十分必要的。 1 2 2 2 研究范围 本研究针对大连造船新厂一维线性原材料的切割下料问题，提出一有效的优 化算法，主要完成以下几个方面的工作： 1 针对大连造船新厂一维线材下料现状，建立一最佳或是近似最佳的下料 模型。 2 选取合适的下料算法，求解下料模型，设计开发一维优化下料系统。 3 。 将开发出来的优化下料系统应用到实际下料问题之中，可让企业通过此 系统最大限度的节约材料，提高材料利用率。 在本系统的程序设计开发过程中，根据计算要求，程序系统的计算部分完成 以下工作： 1 确定所有可行的下料方式并计算相应边料长度； 2 从第一步的结果中读出线性规划模型的约束方程组系数矩阵及目标函数 的系数，形成初始单纯形表，进行数据转换； 3 利用线性规划算法求最忧解。 基于线性规划的一维优化下科系统研究与开发 一维下料问题研究现状 优化下料技术的研究理论涉及到线性规划( l p ) 、动态规划、启发式算法 ( s h p ) 以及人工智能( a i ) 等多种学术研究前沿理论，国内外学者在优化下料 问题上进行过不断的努力，寻求了各种方法。 优化下料问题的研究，开始于2 0 世纪四五十年代，但其奠基性工作当属 g i l m o r e 与g o m o r y t 卜2 】在6 0 年代的工作。此后对此1 7 题的研究，从一维发展到 二、三、四维( 引入时间维) ，研究的重点则是建立特定问题的数学模型和寻求有 效的求解途径。 2 1 下料过程的建模方法研究现状 下料问题知识模型的建立是目前下料领域的一个弱点。复杂下料问题是多约 束多目标的组合优化问题。由于下料知识( 约束、目标) 的多样性，这种组合优化 问题无法用单一的数值优化模型来表达，因而属于一种广义优化问题。下料问题 的模型主要包括数学模型、图论模型、符号知识模型、人工神经网络模型等。 2 1 1 数学模型 现有的大部分下料问题的模型，一般都是将原问题进行简化( 包括几何形 体、约束和目标知识) ，建立单纯的数学模型，然后用组合最优化中广泛应用的 线性规划法、整数规划法、动态规划法或分枝定界法等数学方法进行问题的求 解。 g i l m o r e 与g o m o r y ( 1 9 6 1 ，1 9 6 3 ) 用线性规划建立了一刀切问题的数学模 型，把线性规划的求解转化为一个背包子问题，然后构造求解背包问题的有效方 法。用的数学工具主要是线性规划、动态规划与背包函数，算法可用于求解无阶 段限制的无约束一二维切割问题。 大连理工大学硕士论文 h a d dd y c k h o f f t 3 】( 1 9 8 1 ) 提出了另一种线性规划的模型。并于1 9 9 0 年对于一 维的c u t t i n gs t o c k 问题提出了经典算法，他将这类问题分为两类：i t e m o r i e n t e d ( 项目导向法) 和p a t t e m o r i e n t e d ( 式样导向法) 【4 j 。 v a l e r i od ec a r v a l h o 等1 6 将两阶段下料问题抽象为约束优化问题，并用一简化 的线性规划模型来表达该约束优化问题，最后用列生成技术对得到的线性规划模 型进行求解。 b e a s l e y l 7 将下料问题抽象为0 - 1 整数规划模型。其基本思路是用一个二值变 量表示某类型特定物体的可行位置，代表下料容器的长方形则可表示为可行位置 左上角点的坐标分割成的网格。只要每个网格位置仅被不多于一个的下料物体所 占据，得到的一组下料物体的位鼍是可行的。 2 0 0 1 年，聂义勇、申志勇、王宏、文成秀、张福顺【8 l 应用典型的轩材下料算 法，引进背包问题，提出一个考虑库存余材利用的杆材下料方案。 将下料问题抽象简化建立数学模型，为求解提供了便利。但是当原问题涉及 些不易用数学模型表达的约束条件时，采用各种近似方法得到的数学模型往往 会与原问题产生较大的偏差，并且当问题规模增大、解空间急剧增加时，它们的 求解复杂性变得很强，很难甚至无法得到有效解。 2 1 2图论模型 以图中的结点代表待下料物体，弧线代表下料物体之间的关联关系，由此将 下料问题转化为在一个己知的连接图中寻找最大独立集或最大权平面子图问题： 然后借助于分枝定界、整数规划及动态规划等方法进行问题的求解。 相邻拓扑图模型是用图论方法表示下料的典型方法。 m i t c h e l l 例，r o t h 1 0 l 和d o w s l a n d i i i i 等先后研究了该方法的下料表示与生成。 由于该方法涉及图的平面化问题，难以将其扩充用于3 d 下料。 吴慧中等i l 刈提出了一个长方体下料问题的立体正交结构图( s o l i do r t h o g o n a l s t r u c t u r a lg r a p h ，s o s g ) 模型。 尽管作为组合数学的重要组成部分的图论方法在许多领域有着广泛的应用并 卓有成效，但下料问题的图论方法只限于小规模规则物体下料问题的求解，仍然 不能充分表达布局知识及约束。当下料问题的规模较大且涉及不规则物体时，下 料问题的图论求解方法将不再适用。 基于线性规划的一维优化下科系统研究与开发 2 。1 3复合知识模型 复杂下料问题不仅涉及可用数学模型描述的知识，如问题豹几何、运动学和 动力学约束和优化目标等，而且涉及无法用数学模型描述的知识，如下料物体的 材料性能以及装卸工艺，特别是人类专家的下料领域知识。由此，任何单一模式 的知识模型( 数学模型、图论模型、人工神经元网络等) 都不足以精确地表达该问 题。根据智能工程理论d 3 ，这种复杂系统求解自动化应该建立复合知识模型 各种单一模型的集成。 许多研究者0 4 - 1 5 都进行了探索，为复杂系统下料求解自动化的建模迈出了关 键一步。 事实上，下料领域专家的领域知识、经验及“灵感”能起到事半功倍的作 用，特别是在处理不规则物体下料过程中，人类的智能显示出极大的优越性。而 这种能力( 知识、智慧) 有相当的部分还无法用知识模型的形式来描述，因而无法 为计算机所模仿和利用。另一方面，计算机在数值、图形和符号运算方面具有强 大的威力，通过对数据、信息模型化的知识的自动化处理和运用，计算机可以在 定量决策方面发挥巨大作用，把人类专家从繁杂的较低级别的计算和决策任务中 解脱出来，充分发挥人类专家的创造性和关键决策的作用。采用人机智能结合的 方法求解复杂下料问题，符合人机结合的思想，已成为复杂系统下料自动化的发 展方向。虚拟现实技术【i6 】的发展为人机智能合作提供了有利的工具。 从以上研究可以看出，图论模型、复合知识模型等解决方法还处于探索研究 状态，并没有广泛的应用于工程实际中来。而建立数学模型是现今比较成熟也是 应用最广泛的求解下料问题的方法，前人对于这种方法进行了深入的研究并提出 了各种新的优化方法，在此领域中国内外从理论和实际应用都取得了巨大的突 破。因此本课题本着将研究成果转化为实际工程应用，建立一维优化下料系统的 原则，采用了建立数学模型的成熟解决方法，来求解一维优化下料问题。 2 2下料模型的求解算法研究现状 2 2 1数学方法 下料问题被抽象简化为一定的数学模型后，通常采用数学规划或数值优化的 方法求解 - s 。 1 9 8 8 年s a r k e r b r r 5 1 提出动态规划法，1 9 8 9 年。袁忠良提出了多规格一维 型材优化下料的数学模型，介绍了基于单纯形法的条材板材套裁下料的方法，但 大连理工大学硕士论文 仍需要凭经验给出在每种长度规格的型材上进行下料的若干方案，然后决定每种 方案实施的次数，以达到优化的且的。 a n t o n i o 等 1 8 】针对工业切割问题提出了两种基于动态规划的方法，一种倾向 于求解时间的缩短，另一种倾向于解的质量。 t o t h 1 9 j 建立了组合优化问题的数学模型，并认为求解的最优化方法是各种数 学规划方法的混合。 数值优化方法只能找到局部最优解，所得解的质量在很大程度上依赖于初始 解的选择，因而一些学者致力于研究下料初始方案的自动生成方法。 数学规划方法依赖于数学模型解析性原因而导致局部最优解的局限性为根多 研究者所重视。他们采用具有全局搜索能力的计算智能算法与局部搜索的数学规 划算法相结合，得到较好的结果。在纯数学推导中加入启发式经验，极大地提高 问题求解能力，这一思想值得借鉴。 2 2 2 圈论方法 以图论为工具建立下料问题的图论模型 9 - 1 2 1 后，借助图论方法求解。下料问 题的图论方法只限于小规模规则物体布局问题的求解。当下料问题的规模较大且 涉及不规则物体时，下料问题的图论求解方法将不再适用。 2 2 3 专家系统技术 下料问题是一个领域性很强的问题，有不少学者认为利用专家系统与适合于 某一领域的知识模型相结合是解决具体领域计算机下料设计的有效方法，并对下 料知识获取、描述和创造性推理傲了很多有益的研究。利用专家系统技术辅助机 械产品的下料设计，可以充分利用积累在专家头脑中的大量下料知识，构造下料 设计领域知识库。专家系统的推理机制和人机接口可以使计算机和用户对比知 识，进行处理和利用，在一定程度上完成下料决策工作。但利用专家系统进行下 料设计，在下料知识的获取、表达等方面存在很多困难，只能按照预定的模式进 行推理，缺乏创造性，更缺乏自学习和自适应能力。 由于专家系统技术只能处理单一知识领域范畴的符号推理问题，因此下料专 家系统只能在下料过程的某一阶段起到作用，它的封闭性、领域针对性、缺乏自 适应能力和自学习能力，都使之无法单独承担复杂系统下料的求解任务。 8 基于线性规划的一维优化下料系统研究与开发 2 2 4 人工神经网络方法 自从h o p f i e l d 利用h 0 p f i e l d 神经网络4 4 】成功地求解了旅行商( t s p ) i n 以来， 人工神经网络方法在组合优化领域得到越来越多的重视。人工神经网络具有自适 应性、自学习性、强容错性和巨并行性等许多人脑所具有的特性。 混沌神经网络是一种新兴的神经网络，由于其混沌动力学特性，易于摆脱局 部极小点。文献 2 0 1 将混沌神经网络用于二维下料求解中，得到较好的解。 2 2 5 启发式方法 下料问题是应用背景较强的离散组合最优化问题。即使是最简单的规则形体 下料问题，也属于n p 完全问题。7 0 年代末，根据g a r e y 和j o h n s o n 【2 1 i 关于n p 完 全性理论的研究表明：在有限合理的时间内，不可能求得大规模n p 完全问题的 精确解，问题的求解只能依赖于各种启发式方法。由此，下料问题的研究人员开 始注重对各种启发式方法的研究，而且发展了目前比较流行的计算智能算法，例 如遗传算法1 2 ”、模拟退火算法【3 4 】、禁忌搜索等。 每一个具体的启发式算法都可看作是其中的某一方法或几种基本方法的有机 组合。而且，启发式方法大多基于特定的应用领域，不同的方法在不同的应用领 域所收到的效果是不同的。因此可以根据下料问题在各个不同的应用领域的具体 特点，结合各领域中的成功经验，设计出具有领域特色的各种启发式下料求解算 法。 在上一节中，经过比较确定了求解此类问题的解决方法是先建立相应的数学 模型因而也就确定了数学规划或数值优化方法的模型求解算法。概括来说，就 是先把一维下料问题抽象简化为线性整数模型，然后采用线性规划、整数规划的 数学求解算法求解模型，从而达到优化课题研究、下料系统设计的目的。 大连理工大学硕士论文 3 一维下料系统总体方案设计 在作业研究的领域里面，目前己发展出许多的方法来解决各种的问题。现今 较为大众所熟知并且使用的，有整数规划( i n t e g e rp r o g r a m m i n g ) 、线性舰戈f j ( 1 i n e a r p r o g r a m m i n g ) 、非线性规划( n o n l i n e a rp r o g r a m m i n g ) 、多目标规划( m u l t io b j e c t i v e p r o g r a m m i n g ) 、网络规划( n e t w o r kp r o g r a m m i n g ) 、动态规划( d y n a m i cp r o g r a m m i n 9 1 等，这些规划都是采用数学的方式。在这些规划之中，除了动态规划之外，其它 的规划( 整数规划、网络规划、线性规划、非线性规划、多目标规划等) ，它们最 后所形成的决策模型，事实上是非常相近的。也就是都利用问题所组成的目标函 数( o b j e c t i v ef u n c t i o n ) 及各种的限制条件式( c o n s t r a i n t s ) 所组合而成，之后再利用所 建立的计算方法去求得最佳的解答，也因此是有一定的规律可以依循。而其相异 之处，主要是在于有些是由于限制式是具有网络结构的特性，如网络规划；有些 是由于目标函数或者是限制条件式形成为非线性函数，如非线性规划；有些变量 僮的限制式是在于整数范围之内，如整数规划；另外有些则是由于目标函数的数 目可能具有两个或者是两个以上，如多目标规划。 3 1 线性规划 线性规划( 1 i n e a rp r o g r a m m i n g ) 是一种数学模型，其着重于最优化( 极大化或 者是极小化) 一个线性的目标函数，同时又满足一组线性的限制式，包括等式以 及不等式，然后运用数学的方法，再利用模型的建立想办法去解决切与决策、 管理、规划等有关的问题。在这些所遭遇的问题之中，可能是一种最佳化设计的 问题、有限资源分配的问题、工程作业之规划的问题、或者是生产规划的问题。 为了能够合理的去解决这些与决策有关的问题，并更进一步地去提出一种最佳的 选择方案，因此，有必要去寻找解决这些问题的工具。 早期在线性规划刚开始发展的时候，求解问题时唯一的方法，就是利用人工 计算的方式，以极其繁杂的数学计算过程来求解，而最普遍所采用的方式叫做单 纯形法( s i m p l e xm e t l l o d ) 。如果一个线性规划的问题有解时，最优解的出现必定是 在可行解区域中其边界上的端点。因此，只要从可行解区域上的某一个端点开 始，作为起始检验值的初始点，之后再逐次带入其它各端点的值，就可以得到一 个最佳的解点。 基于线性规划的一维优化下料系统研究与开发 所以，单纯形法就是利用上述的概念，直重复的去做数学运算，直到最后 得出一个最适合的解。 线性规划是利用一种决策模型来解决问题，而模型的组成要素包括了目标函 数、决策变量，以及由决策变量和参数所共同组合而成的限制模型。其大致上可 以分为以下几个过程： 1 定义出问题的核心 当面对一个问题或者案例时，必须先找出这个问题的中心意义，并思考要用 何种方法去解决。之后，才能针对问题的重点去寻求所需要的资料，这样才能对 这个案例做出适当的分析。 2 构建出问题的决策模型 当所要研究的问题可以利用数学的方法来加以解决时，此时，就需要构建出 一个合理的数学模型来求出解答。而模型的构建则包括了目标函数的建立、决策 变量的定义及限制条件的建立。决策变量的定义，通常为了要建立出目标函数和 限制条件的数学公式上所必须的。当决策变量已经明确以后，就可以从所要研究 的问题当中去分析限制条件，以利于将这些限制条件转化为可以计算的数学函 数。 3 算法的确立： 因为规划模型有很多种，所以要采用各模型最适宜的算法去求解。例如：整 数规划的切面方法、以及分支界限法；网络规划的网络单纯形法、以及超限算 法，而在这里线性规划法中所要用到的就是单纯形法。 最后，利用敏感度的分析来决定参数值变动时，所造成的影响以及影响程度 的大小。因为敏感度分析主要是在检验线性规划问题中，当每个系数或者是右侧 值求出最优解之后，若将其僚改变之后，对于最优解所造成的影响。因此，当限 制式的系数、右侧值变动时：目标函数的系数变动时；目标函数的系数及右侧值 一起变动时；或者是增加限制式、增加决策变量时，都可以用来探讨其改变对于 最优解的影响。 就很多设计或选择问题而言，除非其资源是受到限制的，或是有限的，否 则，线性规划将不会存在。而一完整的线性规划体系如下： 大连理工大学硕士论文 m a x ( m i n ) z = c l x i 十c 2x 2 + + c 。x 。 s u b j e c t t o ： a l ix l + a l2x 2 + + a lnx n 至b a 2 ix 2 + a 22x 2 + + a 2n x t l 要b 2 a m lx 24 - a m2x 2 + + a mnx n 耋b m ( 3 一1 ) ( 3 2 ) x i 至0 ，i = l ，2 ，nf 3 3 ) 若以矩阵的形式表示则为： m a x ( m i n ) z ；c x 式中c = 【c l ，c 2 ， s u b j e c t t o ：a x 薹b a = x 至0 ， c n 】 a 1 1a 1 2 口h a 2 1a 2 2 a 2 d m la 1 1 口m 1 2 ( 3 5 ) ( 3 6 ) ( 3 8 ) ( 3 7 ) 岛k k 。l 肛 基于线性规划的一维优化下料系统研究与开发 x = x i x 2 m x m 若再将a 矩阵分割为a = 【p i ，p 2 故p 1 = q 1 a 2 l m 口】 p n = 口2 n m ( 3 9 ) ( 3 一1 0 ) 则线性规划亦可写为 m a x ( m i n ) z = c x ( 3 一1 1 ) s u b j e c t t o ： 乏x i p i - - p 2 ph ，如表3 1 所列 表3 1 原材料型材表 从库存的多规格长度的原材料加工成已知各种长度规格l j 的零件毛坯n j 根 j = 1 ，2 ，j 不妨设l i l 2 l j ，如表3 2 所列 表3 2 待加工零件毛坯规格表 1 4 基于线性规划的一维优化下科系统研究与开发 表3 3 经验给出的若干下料方法 设在各种不同的长度规格上已有若干种下法的方法，如表3 3 所列。表中 ， r h = p h 一a l o h = l ，2 “，h x ，靴，x k l 。嘶为待决定的菲负整数。于是问题的数学模型为 目标函数为所浪费的余料长度最小 约束条件为： r a i n 黔饷+ + 厂铀。嘞x k , + 嘞 a i l + 七氆? k + 晦一嗦h n a j r x l + + 吩与+ 嘞+ 嘞n j x i + + x k l q j + 艄“+ + 屯+ 嘞( q h x i ，吆+ 懈为非负整数 ， 5 一 厂filll、ilii、一 大连理工大学颐士论文 3 2 1 2 多种长度规格型材的改进模型 设x 俐表示在型材长度为p h 的第i 根上截取长度规格为l j 的根数伪= ， 2 ，： f - ，2 ，厶，= ，2 ，印，其中厶待定( h = 1 ，2 ，h ) ， 这样问题的数学模型为： 目标函数为所用的型材总长度最小 m i n s = 2 l h p h ；l 约束条件为： i 。fh l x 帅，= 竹，仃= ，2 ，印 2 i 扭l f 弋j h ( q h似= l ，2 ，h ) 妒q lj p h ( h = i 2 ，h ，i = j ，2 ，l o i 忙， i 。 x ( h ) o o m = i ，h ：j = i ，j ：i = i ，i 0 x “，为整数，若磊产0 ，则说明没有选用第 种型材。 3 2 2 常用计算方法 3 2 2 1 简易图解处理方法 如果遇到变量少，即下料长度为两个变量，在处理这类下料问题时，图解法 更直观，简便。 例如：在造船过程中，需要用每根长1 2 m 的相同直径钢管截下3 2 m ，2 5 m 两种长度钢管，设计使余料最少的下料方法。则可列相关方程： + 主1 口a 其中j ，k 分别为用每根长1 2 m 的供应原材料截下2 5 m ，3 2 m 的根数。当x ；o 时，k = a = 1 2 3 2 = 3 7 5 。当k = o 时，j _ a = 12 2 5 = 4 8 。 1 6 基于线性规划的一维优化下料系统研究与开发 很明显，a ，a 分别为在某根钢管上单纯下2 5 m ，3 2 m 料的情况，而直线a a 。则为其联合在供应原材料上截取的下料方法，位于a a 线上的表示残料为零， a a 以下表示有余料的可联合截取情况，本例设计最优方案为直线a a7 下最近点 d 点，即在1 2 m 长的钢管上截取3 2 m 和2 5 m 长料各两根，此时余下残料为0 6 m ，材料利用率为9 5 。而e 点的下料方法其材料利用率仅为8 0 。 e d 234a 5 图3 1 两点定线下料法、 但是图解法受到了作图空间的限制，即当变量超过三个以上时，就很难利用 图解法来加以求解。 3 2 2 2 单纯形法( s i m p l e xm e t h o d ) 。 单纯形法是利用表格的方式，来求出其最优解，此种方式较为简捷迅速。而 为了利用单纯形法来求解线性规划问题，则于限制条件中引进剩余变量( s u r p l u s v a r i a b l e ) 或松弛变量( s l a c kv a r i a b l e ) 以使不等式转换为等式，成为： a l ix l + a l2x 2 + - b b 1nx n + a lb + ix n + l + + a ln + m x n + m ：b a 2 lx 2 + a 22x 2 + 十a 2 n x n + a 2n + lx n + l + + a 2n + m x n 十m _ b 2 a m lx 2 + a 巾2x 2 + n x n + a i l l 叶lx n + l + + a mn + m x n + m = b m ( 3 1 6 ) x i 耋0 ，i = 0 ，1 ，2 ，n ， 简而言之，单纯形法的执行步骤如下： 1 7 ( 3 1 7 ) 5 4 a 3 2 1 ) ) h 巧 一 一 3 1 j ( ( 大连理工大学硕士论文 z ， c|一zi 表3 4 单纯形法执行步骤 1 、将模型限制式不等式转换为方程式。 2 、建立以原点为基本可行解的起始表，并且计算z j 和c j z j 之值。 3 、选择在q z j 列有最大正值的行做为主轴行( 该行所对应的变量作为介入变 量、。 4 、将( 值) 行的各值除以主轴行对应位置的值，并且选择有最小非负比值的列 为主轴列( 该行所对应的变量作为代出变量) 。 5 、利用下面公式算出新主轴列的值 新表主删的僻鼍警 6 、使用下面公式算出所有其它列的值 新表主轴列的值= 旧表的列值一( 主轴行在该列的系数新表的列值) 7 、计算新的z j 和c j z j 列的值。 8 、检查c j - z j n ，决定所求的之新解是否为最优解。如果c j z j 列的所有值均 为零或是负数，此解即为最优解。否则如果仍有正值存在，则回到步骤3 并且反复单纯形法的步骤。 现今，由于计算机软件与硬件的设备不断更新，且运算的速度也大幅的提 升，所以求解线性规划模型的工作已经逐渐由计算机所取代。而目前普遍被应用 在线性规划方面问题的软件，包括l i n d o 、q s b + 、a b ：q m 等，其它更新的软 1 8 基于线性规划的一维优化下料系统研究与开发 件还有一些如l i n g o 、g a m s 、a m p l 等。本研究的求解主要是利用m a t l a b 软 件所带的数学库中线性规划函数来进行。 3 2 2 3分枝定界法( b r a n c ha n db o u n d ) 。 分枝定界算法求解组合优化的基本思想是隐式的枚举切可行解。当然这种 枚举不是简单的枚举，而是逐次对解空间进行划分。所谓分枝就是指这个划分过 程；而所谓定界就是指对于每个划分后的解空间要计算原问题的最优解的下界。 这些下界用来在求解的过程判定是否需要对目前的解空间进一步地划分，也就是 尽可能去掉些明显的非最优点，从而避免了完全枚举。 r a i n f = c j _ 口。0 = 6 ， ( 1 ) x ：z + 用分枝定界算法来求解上面的问题时，先求解线性规划( l p ) 的松弛问题 m i n f = c j t o = 岛 如果得到的最优解x 。是整数，则求解结束。该最优解也是整数规划的最优 解。否则，得到的最优解只是( 1 ) 的最优解的个下界。这样可以把( 1 ) 划分为两个 子问题： m i n f = c j x j j t l 一= 包 。 j - iu j x 0 7 x j i x l i + l 工。2 + 1 9 大连理工大学硕士论义 和 m i n f = o _ _ = 6 f x 0 x 。，则这一分枝不必再考虑了，因为在这一分枝中不会找到小于x 。的 解。如果x 。 x 。，煲i j 分枝过程还要继续下去。 上述分技定界算法可以简单的描叙为： s t e p l 令a c t i v e s e t = o ) ：u _ ：c u r r e n t b e s t = 0 ； s t e p 2 如果a c t i v c s e t = 空集，则原问题的最优解已经得到，程序结束；否则从 a c t i v e s e t 集合中选择一个分校点k ；将k 从a c t i v e s e t 中去掉，c o n t i n u e s t e p 3 * s t e p 3 生成k 的各分枝诤l ，2 ，n 。及其对应的下界x 。 s t e p 4 对分枝i = l ，2 ，n l ：如果分枝i 得到的是全整数且x ， u ，则令 u 。x 。且c u r e n t b e s t = i 如果分技得到的不是全整数解且x 诅( m ) ，则l ( i ) 与a ( i ) 应该满足下列关系 式： 肼 l l m i n l ( 1 ) - l ( 2 ) 1 ( m ) l ( i ) 、