下载文档原格式
第35卷第7期2005年7月数学的实践与认识M A TH EM A T I CS I N PRA CT I CE AND TH EO R YV o l135 N o17 July,2005 实用下料优化问题模型建立及解法李丹俊, 曾 锐, 孙 伟指导教师:唐建宁(解放军理工大学工程兵工程学院,南京 210007)摘要: “下料问题(cutting stock p roblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题,此类问题在工程技术和工业生产中有着重要和广泛的应用.本文首先以材料最省为原则建立模型,采用分层基因算法模型求解出模型的解,若此结果不符合时间限制条件,则通过以客户时间需求为第一目标的分组抽样模型处理后,再借助分层基因算法给出该模型的最优解.关键词: 下料;基因算法;二维下料问题;分组抽样1 问题的提出(省略)2 问题的分析这是一个典型的多目标决策优化问题.首先,一个好的下料方案应该使原材料的利用率最大,从而减少损失,降低成本,提高经济效益.其次,要求所采用的不同下料方式尽可能少,即希望用最少的下料方式来完成任务.因为在生产中转换下料方式需要费用和时间,既提高成本,又降低效率.此外,由题意知每种零件有各自的交货时间,每天下料的数量又受到企业生产能力的限制.因此实用下料问题的目标是在生产能力容许的条件下,以最少数量的原材料,尽可能按时完成需求任务,同时下料方式数也尽量地少.为顺利解决该下料问题,根据该问题的特点,我们先从最基本的单目标决策问题入手,以材料损耗最少为目标,通过不同的数学原理建立多个单目标决策的最优化模型,得出最初的结果,并加以比较分析.然后逐步增加其约束条件——最小的下料方式数,并根据该约束条件进一步完善我们的最优化模型,得到损耗最少,下料方式数又小的结果.接下来检验在所得下料方式的排列中,是否存在可以满足时间条件限制的排列方式.若存在,则该结果即为最优解;若不存在,则这个结果就不符合题意,必须重新构建多目标决策的最优化模型,在新模型中以客户时间需求为第一目标,材料损耗最少,下料方式最少为第二目标.因此,在下料时就应该优先生产那些有时间限制要求的零件,并且求出在需求的时间段内下料方式和损耗的最优结果,紧接着再求出剩余板材下料方式和损耗的最优结果,从而最终得出既满足时间条件限制又满足损耗少、下料方式数小的最优结果.具体流程图如下:3 符号的约定11L——原材料的长度21W——原材料的宽度31I——板料用量图1 总体流程图41J ——加工零件的种类51K ——下料方式种类61l j ——第j 种零件的长度(j =1,…,J )71w j ——第j 种零件的宽度(j =1,…,J )81d j ——第j 种零件的加工个数(j =1,…,J )91M ——以向量形式表示问题中所要求各种零件的个数,即M (j )=d j101b ——锯缝宽度111∆i ——第i 块板料利用率121x ij ——第i 根的板材上截取长度规格为l j 的根数(i =1,…,I ;j =1,…,J )131a jk ——第k 种下料方式下第j 种零件的个数(j =1,…,J ;k =1,…,K )131b k ——第k 种下料方式产生的余料141x k ——使用第k 种下料方案需要切割原材料的数目4 模型的假设11切割时的锯缝可以是直的也可以是弯的,切割所引起的锯缝损耗忽略不计.21零件非定向:这里的‘定向’是指在有纹路的面板上下料时是否允许将零件既能横着排又可转个方向竖着排,对于定向取材的零件,零件的长度与宽度尺寸不能随便互换,等到下料图出来后还应该仔细检查一下这零件的纹路方向是否正确.而对于本题,我们假设不存在这个问题,即零件非定向.31除了要求在四天和六天内完成所需零件外,不要求其余零件加工排列顺序.41切割时零件的长和宽要与原材料的长或宽平行.51增加一种下料方式大致相当于使原材料总损耗增加0108◊.5 模型的建立与求解实用下料问题模型的建立,从计算的复杂性上来讲,这是一个N P (N ondeter m in istic Po lynom ial )难题,很难精确求解.通常所用的近似算法有3种:①FF (F irst F it )近似算法,即:将m 种零件顺次加工,对于任一个零件,它总是按顺序从第一块能加工它的板材中切割下来.②B F (B est F it )近似算法,即:把零件顺次加工,要求板材加工完零件后,所剩下的材料最小.③FFD (F irst F it D ecreasing )或BFD (B est F irst D ecreasing )近似算法,即:在加44数 学 的 实 践 与 认 识35卷工零件之前先把零件按大小降次排列,然后再利用FF (或B F )近似算法.我们经过先期的尝试性试验,发现这些近似算法的求解结果与给定的数据有很大的关系,效果不理想.于是我们采用先进的优化算法:E P F F 算法和遗传基因算法来计算我们的模型,虽然过程较为复杂,而且处理的数据相当庞大,但是结果却十分理想.(一)一维实用下料问题的模型按照前面的分析,我们先考虑用料最省的单目标决策优化模型,然后讨论时间限制问题.这里我们采用了分别采用了两种算法即E P F F 算法和遗传算法来对模型进行求解.模型 用料最省模型:11基本模型假设有K 种下料方式,再根据每种零件的需求量,可求得每种零件应用的次数.这样在第1种方式下第1种零件的个数为a 11个,以此类推,则a jk 表示用第k 种下料方式所能得到的第j 种零件的个数.由以上模型得到如下对应关系矩阵 A =a 11a 12…a 1K a 21a 22…a 2Ka J 1a J 2…a J K(121)则使用k 种不同下料方式所使用原材料的根数为 X =(x 1,x 2…,x K )T(122)而每种下料方式产生的废料长度为 b k =L -(a 1k l 1+a 2k l 2+…+a J k l J ), k =1,2,3,…,K根据对所用板材剩下的余料最省这一目标,则可得优化下料方式的模型为目标函数 m in ∑K k =1b k x k(123)约束条件 ∑K k =1a jk x k =d j (j =1,2,…,J )x k ≥0(k =1,2,…,K )(124)但往往在进行加工切割下料时会产生部分切缝b ,这样我们的废料长度就变为 b ′k =L +b -(a 1k (l 1+b )+a 2k (l 2+b )+…+a jk (l j +b ))相应的目标函数为 m in ∑Kk =1b ′k x k(125)21求解方法211 EPFF 算法通过建立下料问题模型我们可以将此问题转化为装箱问题,而装箱问题是个典型的N P (N ondeterm in istic Po lynom ial )难题,如果使用传统的算法编写程序,在零件数量较大的情况下,将会使传统的搜索算法有相当大的数据空间,为此我们采用EPFF 算法[8]来对零件进行分类组合.通过分类组合,零件可以划分成八类,从而就使程序搜索的数据空间明显减小,这样我们就能先找出这些零件的所有的1级产品向量,即所有的零件组合后使所用原材料的547期李丹俊,等:实用下料优化问题模型建立及解法余料最小.在使用EPFF 进行搜索时我们结合以上的目标函数和约束条件来找出最优解.调整的目标是使下料矩阵满足目标函数而且是最优解,也就是说使得新的下料矩阵逐渐向最优产品下料矩阵逼近.为此在调整中我们考虑以下因素:a 1当∑Kk =1ajk x k ≥M (j )时,换入向量的第j 分量应当小于换出向量的第j 分量,并尽可能使换入向量在相应下料矩阵中的位置靠前;b 1当∑K k =1ajk x k ≤M (j )时,换入向量的第j 分量应当大于换出向量的第j 分量,并尽可能使换入向量在相应下料矩阵中的位置靠前.根据该算法编写M atlab 程序,得到多种结果的序列.考虑到增加一种下料方式大致相当于使原材料总损耗增加0108%的约束条件,我们最终筛选出此模型在EPFF 算法下的最优解:板材的用量为801块,板材利用率为99155%,下料方式为57种,详细的零件加工清单、下料方式,板材用量的分布见附录 的表格.212 遗传算法本问题由于约束条件和目标函数的特点,如用线性规划的方法求解,目标函数一般都会取得相同的最小值,从而分枝界定的方法失效.所以我们决定采用基因遗传算法.遗传算法是一种基于自然选择和群体遗传机理的搜索算法,它有5个基本组件:染色体编码、适应度函数、初始化群体、在两个连续染色体群体之间进行进化的一组操作符以及工作参数.Hoffm eister 和Back 把遗传算法作为一个9组实体提出:GA =(p 0,I ′,Κ,L ′,f ,s ,c ,m ′,T ″)p 0——初始化群体I ′=(0,1)L ——染色体编码Κ′——群体规模L ′——染色体长度f ∶I ′R ——适合函数s ∶I ′ΚI ′——父本选择c ∶I ′2I ′2——交叉操作m ∶I ′I ′——变异操作T ′∶I ′Κ{0,1}——终止条件该算法具有以下特点:(1)遗传算法以决策变量的编码作为运算对象;(2)遗传算法直接以目标函数作为搜索信息.把搜索范围集中到适应度较高的部分搜索空间中,从而提高了搜索效率;(3)遗传算法同时使用多个搜索点的搜索信息;(4)遗传算法是用概率搜索技术.实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解.另一方面,与其他一些算法相比,遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能的低.21211 编码解码采用等长的十进制编码:将每一种零件进行编号:i =1,2,…n t ,n t =∑53j =1n j,把零件编号64数 学 的 实 践 与 认 识35卷作为染色体编码[p 1,p 2,…,p i ,…,p nt ].每一种编码表示一种下料方案.如[1,4,5…]表示下料顺序为:1号,4号,5号,….得到码长为3970的十进制染色体编码.针对编码产生的个体,可按零件的序号i =1,2,…n t 依次取零件长度累加,即求得所需原材料数I .21212 适应度函数用适应度函数来评价遗传算法时,适应度越大,解的质量越好.最优解的目标是使下料根数最少.但我们注意到,在两种下料方式下料根数相等的情况下,能使最后一根板材产生浪费最少的方式更优.所以适应度函数定义如下: f (p )=∑ni =1l i n i(L (I m -1)+L ′)(229)式中:I m 为该考虑下料方式后个体p 所需原材料的总数I m =I 实(1+0.08k ),k 为下料方式总数L ′为最后一根材料用去的长度.21213 初始种群对零件进行编码,随机产生由子辈群体,且长度为p nt 的编码构成的初始种群.并计算每一个个体的适应度.21214 遗传算子(1)选择算子采用比例选择方式:第一步:先计算出群体中所有个体的适应度的总和;第二步:其次计算出每个个体的相对适应度的大小,它即为各个个体被遗传到下一代群体中的概率.第三步:最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数.(2)交叉算子采用单点交叉算子:第一步:对群体中的个体进行两两随机配对.第二步:对每一对相互配对的个体,随机设置某一基因座之后的位置为交叉点.第三步:对每一对相互配对的个体,依设定的交叉概率p c 在其交叉点处相互交换两个个体的部分染色体,从而产生出两个新的个体.(3)变异算子采用基本位变异:第一步:对个体的每一个基因座,依变异概率p m 指定其为变异点.第二步:对每一个指定的变异点,对其基因值做取反运算或用其他等位基因值来代替,从而产生出一个新的个体.21215 运行参数(1)群体大小M :为避免遗传算法的早熟现象,取M =50.(2)交叉概率p c :用自适应的方式,初始值取019随着遗传算法在线性能调整交叉概率.取值范围为:014<p c <0199747期李丹俊,等:实用下料优化问题模型建立及解法(3)变异概率p m :取变异概率为p m =011.随着遗传算法在线性能的下降,可以减小变异概率p m 的值.取值范围为:010001<p m <011.(4)终止代数T :取T 为100.21216 最优保存策略在遗传算法的运行过程中,通过对个体进行交叉、变异等遗传操作而不断地产生出新的个体.虽然随着群体的进化过程会产生出越来越多的优良个体,但由于选择、交叉、变异等遗传操作的随机性,他们也有可能破坏掉当前群体的平均适应度,并且对遗传算法的运行效率、收敛性都有不利的影响.所以我们希望适应度最好的个体要尽可能地保留到下一代群体中.为达到这个目的,我们采用最优保存策略化模型(Elitist M odel )来进行优胜劣汰操作,即当前群体中适应度最高的个体不参与交叉和变异运算,而是用它来替换掉末代群体中经过交叉、变异等遗传操作所产生的适应度最低的个体.最优保存策略进化模型的具体过程是:(1)找出当前群体中适应度最高的个体和适应度最低的个体.(2)若当前群体中最佳个体的适应度比总的迄今为止最好个体的适应度还要高,则以当前群体中的最佳个体作为新的迄今为止得到的最好个体.(3)用迄今为止最好的个体替换掉当前群体中最佳的个体.21217 满足时间要求问题中对下料的时间要求如下:企业每天最大的下料能力是一百块要求在4天内完成的零件标号(i )为:5,7,9,12,15,18,20,25,28,36,48;要求不迟于6天完成的零件标号(i )为:4,11,24,29,32,38,40,46,50.在遗传算法中加入时间约束,若所求得的最优解不满足时间要求则抛弃该解,在剩余的个体中求最优解.21218 遗传算法流程图:图2 遗传算法流程图21219 求解结果经过编程调试试算,遗传算法具有较好的收敛性.但由于编码长度很长,算法很难收敛84数 学 的 实 践 与 认 识35卷于全局最优解.故我们采用进行多次试算的方法.经过2000次试算,求出板材用料最少而且下料方式最少的最优方案.最后结果为板材用料I =798,下料方式的数目为56和总的材料利用率为99190◊.显然遗传算法求得的结果比E P F F 算法更优.理想情况下,既没有任何浪费,所需板材的最小值为797(在实际中是不可能达到的).而我们的结果只增加了一块板,所以可以认为我们的结果一定是全局最优解.详细的零件加工清单、下料方式,板材用量的分布见附录 .按照题目要求,需要在4天内完成的零件标号(j )为:5,7,9,12,15,18,20,25,28,36,48;需要在6天完成的零件标号(j )为:4,11,24,29,32,38,40,46,50.我们把这些有时间需求的零件提前生产,并根据所耗费的板材总数除以企业每天最大下料数来判断完成时间.根据附录 的表格,经过简单的排序,按以下方式序号顺序下料:4,5,6,7,9,12,13,14,18,19,21,22,24,27,28,29,30,32,37,38,39,43,44,46,51,52,55,1,15,16,17,25,26,31,36,42,47,48,49,54,56.这时,需要在4天内完成的零件3天就可以完成,而需要在6天完成的零件也只需要5天半的时间,所以我们得到的这个最优方案完全可以满足时间限制要求,不需要改变决策目标,重新构建模型.因此本方案即为最终结果.(二)二维实用下料问题的模型对于二维下料问题,虽然也能够采用第一个问题的模型 向二维问题的扩展,但是由于问题条件的所需要的数目很多,尤其是采用类似装箱问题的模型时,在放置操作,在确定了放置次序后,该如何确定下一个矩形的放置位置,即在矩形大小不同的条件下,如何在有限的空间里与当前矩形放置位置达到最好组合是解决装箱问题的关键,在选择位置上共有两到四种位置可选,这就加大了程序的运算量,而且在考虑矩形的长度的同时还要考虑矩形的宽,这在程序的实现上也是需要很大的时间,所以我们在解决二维下料问题时,不采用E P F F 算法.从模型 的求解过程中我们还注意到遗传基因算法在组合优化中的操作直观、表现力强,因而我们尝试利用遗传基因算法来处理二维下料问题:模型 二维约定下的遗传基因算法模型11基本模型在第二问中涉及到了长和宽同时改变,也就是说不是单纯的一个变量,而是两个变量在变,所以在建立模型时以剩余原材料的余量面积最小和使用的原材料的数量最少为其目标.我们仍然假设有m 种下料方式,再根据每种零件的需求量,求得每种零件应用的次数.这样在第1种方式下第1种零件的个数为a 11个,以此类推,则a jk 表示用第k 种下料方式所能得到的第j 种零件的个数.由以上模型得到如下对应关系矩阵 A =a 11a 12…a 1K a 21a 22…a 2Ka J 1a J 2…a J K(321)则使用k 种不同下料方式所使用原材料的根数为 X =(x 1,x 2…,x K )T(322)而每种下料方式产生的废料面积为947期李丹俊,等:实用下料优化问题模型建立及解法 S k =LW -(a 1k l 1w 1+a 2k l 2w 2+…+a J k l J w J ), k =1,2,3,…,K对于所有搜索到的余料最省的下料方式,我们有以下模型用来筛选:目标函数: m in ∑K k =1S k x k(323)基本算法与约束条件: ∑Kk =1ajk x k =d j ∑K k =1a jk l k ≤L ∑K k =1ajk w k ≤W(j =1,2,…,J )(324)要解决的问题:要在固定长宽的矩形原材料里,放置大小不一样但固定的下料件,如何使得原材料所用的件数最少及产生的废料面积最少.不妨将所要切割的下料件编成一个序列T (i ),其中i =1,2,…,n ,则算法的基本思想是按从下到上、从左到右的顺序下料规则,也就是说将从一块原材料的左下角开始切割T (1)零件,记录下当前位置,接着再从左下角切割T (2)零件,看能否切割,不能的话向上移动,以此类推,当切割到原材料的顶端时,继续从余料件左下角切割,示意如下图(图中i ,j ,k 为已切割部分,m 为待下料切割的零件形状):图3 下料过程示意图当切割到一定数量的零件后,判断是否还能再进行切割,如能,则继续下去直至此板料所余部分无法按所需尺寸下料为止.将剩下的零件继续按照此方法在新板料上进行下料,继续这样的步骤直至所要加工零件全部下料完毕.这样一个完整的下料方案其实就是一个排序,以最后余料的大小作为每个排序的评价标准,于是该问题就转化为最优排序问题.21求解方法方法是将原材料被零件切割后所得余料一起作为一个区间段,将要进行下料的零件与这所有可能的区间段进行长度比较,选择可以切割的位置,对选出的位置进行宽度比较,选择最佳切割区,切割完后,再对区间段进行重新计算,调整其参数.我们这里为了实现这个算法,采用的是遗传基因法,对于染色体的编码采用整数模式.由于最短的零件长度也大于原料件的宽度,所以我们不用考虑存在切割时零件的旋转,具体操作步骤如下:(1)编码方法采用随机键表达来产生一串(0,1)之间的随机数.比如,一个10个矩形的染色体为[0111,0114,0143,0118,0153,0128,0147,0173,0164,0167]我们将随机数按照升序排列,得到如下放置顺序:8-10-9-5-7-3-6-4-2-1这条染色体表示先后经过编号为8,10,9,5,7,3,6,4,2,1城市,即表示把编号为8,10,05数 学 的 实 践 与 认 识35卷9,5,7,3,6,4,2,1的下料件按前述顺序依次在原料件上进行切割.(2)杂交将选出杂交的两个个体进行顺时针或逆时针旋转排列[]比如被选中的2个个体分别为:P 1:9-1-2-3-4-5-6-7-8P 2:5-3-4-9-7-2-8-1-6按照上述方法杂交后得到:P 11:1-2-3-4-5-6-7-8-9P 22:3-4-5-9-7-2-8-1-6这种杂交方法保证了不生成致死染色体,又保证了前一代的性质遗传性.(3)变异我们考虑采用互换变异,也就是在染色体中选择两个基因,将其互换:P 3:9-1-2-3-4-5-67-8编译后的染色体:P 33:9-7-2-3-4-5-6-1-8(4)求解结果经过编程调试计算,以此遗传变异算法进化若干代后,我们得出了最优解I =458块.同样地,在顺序随机产生的上千个可行方案中,在增加一种下料方式大致相当于使原材料总损耗增加0108◊的约束条件下,得出的最优方案结果仍为I =458块,由此得出总的材料利用率为97183◊,而且我们得出该方案下料方式的数目为50,详细的零件加工清单、下料方式,板材用量的分布见附录 的表格.紧接着我们来讨论二维下料模型的时间限制问题.按照题目要求,需要在4天内完成的零件标号(i )为:3,7,9,12,15,18,20,25,28,36.同一维下料模型的时间限制讨论方法一样,我们把这些有时间需求的零件提前生产,并根据所耗费的板材总数除以企业每天最大下料数来判断完成时间.根据附录 的表格,不论怎么排序,都无法满足时间限制的需求,所以我们得到的这个材料最优方案不能满足时间条件,需要改变决策目标,重新构建模型.根据以上的模型和算法,我们注意到如果该企业只加工那些有时间限制要求的零件,则三天内便可以完成,但是材料的利用率并不是很高.因此我们下面要做的工作是:在满足时间限制的条件下,如何使得材料的利用率最高.模型 分组抽样模型由题意,这批零件需要在4天之内完成,而且企业每天的下料能力为20块,也就是说在80块原料之内必须加工完所有.但是80块原料在加工完这批有时间限制要求的零件后还有很多剩余,由此就带来一个问题,如何合理安排前4天生产的零件,使得最终的结果为最优呢?我们知道在加工零件的种类和数量繁多的时候,零件越小,材料的利用率越趋于增大.因此,在安排前4天生产的零件时,加工的小零件越多,其材料的利用率越趋于增大,但是同时也使得后期生产的大批零件的利用率越趋于减小,得不偿失;若是在安排前4天生产的零件时,加工较多的大零件,也会造成总体的材料利用率降低,因为在加工零件的种类和数量157期李丹俊,等:实用下料优化问题模型建立及解法25数 学 的 实 践 与 认 识35卷较少的时候,加工大零件会造成更大的浪费.因此最好的情况是使得前后两个生产阶段加工的零件形状趋于平衡,为此我们仿效数理统计中的抽样检验的方法,把没有时间限制要求的33种零件按种类依次平均分成11个样本,这样可使得每个样本中的样本值较为接近.每个样本各出一个样本值和有时间限制要求的零件(共21种类型)一起加工,采取这种形式可使得在两个时间段中加工零件的大小形状趋于平衡,从而对两个时间段里的材料利用率的影响降到最低.考虑到这21种类型零件的总面积要尽量接近80块原料的总面积,我们编程对所有的样本值组合进行筛选,得到最适合的11个样本值(零件种类编号)为2,6,13,14,21, 26,30,32,37,40,43,(程序得到的结果是所选样本值在样本中的位置).利用上面的模型和算法,我们对这21种类型零件进行材料最优的优化处理,得到如下结果:板材数量88,材料利用率91163◊,下料方式24.然后对剩余的零件进行同样的处理,得到结果如下:板材数量376,材料利用率95168◊,下料方式25在进行了局部微调之后,再把两个时间段生产的最后一块材料合并为一个,这样做很有必要,因为最后一块材料的利用率很低,相互合并后可以提高总体的材料利用率,使得总体的利用率分别高于这两个时间段,也就是我们常说的“1+1〉2”效应.我们最终得到板材数量463,材料利用率96111◊,下料方式48.全部零件的生产清单、下料方式和板材用量的分布见附录 的表格.经过简单的排序,优先按以下方式序号下料:1,2,3,4,5,6,7,8,9,10,15,16,17,19,20,22,23,24即可满足时间限制条件.6 模型的优缺点及其推广板材下料是许多企业的生产实际问题.不同规格、数量零件的合理套裁可以有效地减少废料,提高材料的利用率,直接关系到产品成本和企业的经济效益.在生产实际问题中,由于不同尺寸规格、不同数量的零件套裁具有成千上万种的排列组合,想用人工思考方法寻求合符要求的最佳方案是不可能的.许多企业都存在批量下料问题,如家具木器厂、电梯厂、装璜公司等不同品种、尺寸规格的板材、型材用量很大,千百万的材料费中省其一二,经济效益就十分可观了.我们所建立的数学模型有效地解决了特定的有时间限制的一维、二维多目标决策下料问题,比起一般的计算方法,我们建立的数学模型有以下优点:11对于问题一模型:E P F F代换算法,采用了分组配对的方法,有效地缩小了可行解空间的搜索范围.因此其特点是速度很快,可以在较短时间内找到比较令人满意的解.其缺点是分组配对有可能会漏掉最优解.而利用遗传基因算法可以随机搜索所有解空间,虽然效率比模型一低,但经过反复多次搜索可以得到比模型一更优的解.本文的结果也说明了这一事实.但是遗传算法求得最优解所耗的时间较长.21明显提高材料的利用率,使得方案最大限度的趋于最优化,有着巨大的经济效益.与人工设计方案和计算机简易编程算法相比较,一个中型家具厂一年就能节省几十万到几百万元的材料成本费用.31提高工作效率,而且可以根据用户需求排出带有时间限制条件的最优方案.一个由50多种不同规格的零件、成千上万块板料组成的下料工艺设计方案,在很短的时间内即得到成最优的生产计划表.在生产用料管理、原材料的采购定量预算、成本核算、对市场的反应速度等方面大大增强了企业的竞争能力.。
物资调运问题的优化模型肖凤莲 涂礼才 何三才摘 要:本题所说的是防洪抗涝物质调运问题。
在此问题中我们求各企业、物资仓库及国家级储备库之间物资的运费每一百件最少的路线，把附件2（生产企业，物资仓库及国家级储备库分布图）的分布图转化为数学直观简图（见模型求解中图1），所得图是连通图，设为()E V G ,=，各个边的权为相连两点每百件物资的运费。
我们利用“破圈法”和“最短路”求任意企业、物资仓库及国家级储备库两两之间及仓库与仓库之间的最优路线，显然我们建立的数学（简单图形）模型是可行的、合理的。
得出最优路线见表二、三、四、五。
我们根据实际情况，在保证国家级储备库的情况下，采用就近原则，在此基础上建立线性规划模型（如下）：)))()(())()()(((min 1111111111∑∑∑∑∑∑∑∑∑∑=++==++==++=====⋅+⋅+⋅+⋅+⋅⨯=bi cb b k k i ki a i cb b k k i ikbi cb b k j i b i bj j i j i ji ai bj j i j i w zy xq w z w zy x p A F运用Lingo 软件对我们所建立线性规划问题进行计算。
再把天数为20带入上述线性规划，运用Lingo 运用软件进行计算，可以得到企业2—6—40—储备库1，其他中断路段对物资运输的路线无影响。
建立线性规划，运用Lingo 运用软件求解，其结果见问题4的求解。
此模型简单易懂，容易推广。
运用了LINGO 数学软件，提高了计算的速度。
解得的结果符合实际。
关键词：破圈法、最短路、线性规划模型、Lingo.一、问题的重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。
某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。
钢管的订购和运输优化模型摘要本文建立的多元非线性优化模型。
问题一在保证天然气管道铺设可以顺利实施的情况下，给出了钢管的订购与运输总费用最小的方案。
在求钢管由钢厂运输到站点的费用和铺设钢管时产生的运输费，根据图一，我们通过深度优先遍历的方法对整个图一进行路径搜索，然后根据每条搜索到的路径上的铁路和公路上的不同权重，找到了各个钢厂到各个天然气管道上的站点的最佳路径。
对于整个优化过程我们给出了相关的算法，并用matlab 软件编程，经过一系列计算之后，得出了最优的订购与运输方案。
对于问题 1，我们求得的最优解为对于问题2我们经过计算比较得出：6S 钢管销价的变化对购运计划和总费用影响最大。
1S 的生产上限的变化购运计划和总费用影响最大。
对于问题 3，当天然气管道呈现的是一个树状图的时候，我们得到的最优关键字：非线性优化 深度优先遍历 最佳路径一、问题重述要铺设一条1521A A A →→→ 的输送天然气的主管道, 如图一所示(见下页)。
经筛选后可以生产这种主管道钢管的钢厂有721,,S S S 。
图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km 主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。
钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1单位钢管为i p i 1 2 3 4 5 6 7 i s80080010002000 2000 2000 3000 i p160 155 155160 155150160 1里程(km) ≤300 301～350351～400 401～450 451～500 运价(万元) 2023262932里程(km) 501～600601～700 701～800 801～900 901～1000 运价(万元)37445055601000km 以上每增加1至100km 运价增加5万元。
钢管订购与运输的优化模型钢管订购与运输是现代经济中的一个重要问题。
钢管是建筑、制造、输送等多个领域必不可少的材料，一般情况下我们需要从厂家或供应商那里订购所需钢管，并通过运输将其送到指定地点。
在订购和运输的过程中，我们需要考虑许多因素，如运输距离、交通方式、需求量、时间限制、价格等等。
针对这些问题，我们需要使用优化模型来提高订购和运输的效率和经济性。
一、钢管需求模型在实际工作中，我们需要尽可能准确地了解钢管的需求情况。
这样才能更好地制定订购和运输计划。
钢管需求模型是一个重要的决策工具，可以帮助我们进行有效的决策。
其主要内容如下：（一）需求量需求量是指市场中对钢管的总需求量。
建立需求量模型需要考虑市场状况、产品质量、价格、季节等因素。
我们可以通过市场调研、历史销售数据等途径进行预测。
需求结构是指不同规格的钢管在市场中的占比情况。
了解需求结构可以帮助我们更好地制定订购方案，避免过度订购或订购不足情况的发生。
需求时间是指市场上对钢管的需求时间分布。
了解需求时间可以帮助我们更好地制定订购和运输计划，减少废弃和过度库存，提高物流效率。
在了解钢管需求的情况之后，我们需要制定订购计划。
为了提高采购效率，我们需要采用优化模型。
该模型的主要内容包括：订购量是指在一定时间内企业需要订购的钢管数量。
订购量的大小直接影响企业的成本和库存水平。
因此，我们需要根据实际需求，结合采购成本、库存水平等因素进行考虑，制定出合理的订购量。
（二）订购频率订购频率是指企业在一段时间内订购钢管的次数。
频繁而杂乱的订购计划会耗费大量的人力、物力和财力，同时也增加了库存和物流的费用。
因此，我们需要根据实际情况，制定出合适的订购频率。
（三）订购价格订购价格是采购者与供应商之间协商的价格。
采购者需要确保订购价格与采购成本相符，同时也要考虑到供应商的利润。
因此，合理的订购价格既要考虑到采购方的利益，也要考虑到供应商的利益。
订购钢管需要通过运输将其送到指定地点。
物资调运问题的优化模型肖凤莲 涂礼才 何三才摘 要:本题所说的是防洪抗涝物质调运问题.在此问题中我们求各企业、物资仓库及国家级储备库之间物资的运费每一百件最少的路线，把附件2（生产企业，物资仓库及国家级储备库分布图）的分布图转化为数学直观简图（见模型求解中图1），所得图是连通图，设为()E V G ,=，各个边的权为相连两点每百件物资的运费。
我们利用“破圈法”和“最短路"求任意企业、物资仓库及国家级储备库两两之间及仓库与仓库之间的最优路线,显然我们建立的数学(简单图形)模型是可行的、合理的。
得出最优路线见表二、三、四、五。
我们根据实际情况，在保证国家级储备库的情况下,采用就近原则，在此基础上建立线性规划模型（如下）：)))()(())()()(((min 1111111111∑∑∑∑∑∑∑∑∑∑=++==++==++=====⋅+⋅+⋅+⋅+⋅⨯=bi cb b k k i ki a i cb b k k i ikbi cb b k j i b i bj j i j i ji ai bj j i j i w zy xq w z w zy x p A F运用Lingo 软件对我们所建立线性规划问题进行计算。
再把天数为20带入上述线性规划，运用Lingo 运用软件进行计算，可以得到业2—6—40—储备库1，其他中断路段对物资运输的路线无影响。
建立线性规划，运用Lingo 运用软件求解，其结果见问题4的求解。
此模型简单易懂，容易推广。
运用了LINGO 数学软件,提高了计算的速度.解得的结果符合实际.关键词：破圈法、最短路、线性规划模型、Lingo 。
一、问题的重述我国地域辽阔,气候多变，各种自然灾害频频发生,特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。
某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。
. . . . 2012年数学建模培训第二次测试论文题目运输优化模型姓名马鹏系（院）数学系专业信息与计算科学、应用数学2012 年8 月27 日运输优化模型[摘要]在社会的经济生产活动中，产地（厂家）与客户都会想方设法合理调拨资源、降低运输费用，实现利益最大化，完成资源优化配置。
本文在运输费单价恒定，各产地发量一定，各客户的需求量也一定的条件下，努力解决多个特定目标实现问题。
力求最优的运输方案。
在确定问题为不平衡的运输问题时，先虚设一个产地，将问题装华为平衡运输问题，将问题转化为目标规划问题，按照目标规划问题的建模思想逐步建立模型。
本文的主要特点在于，将不平衡的线性规划问题合理地转化为目标规划问题，在求解时充分利用LINGO软件求解。
关键词：lingo 目标规划线性规划运输优化问题运费最少一．问题重述运输功能是整个现代物流七大基本功能之一，占有很重要的地位，运输成本在整个物流系统中所占的比重也很大，运输成本的有效控制对物流总成本的节约具有举足轻重的作用。
通过物流流程的改善能降低物流成本，能给企业带来难以预料的效益，影响运输成本的因素是多样化、综合性的，这就要求对运输成本的分析要采用系统的观点，进行综合分析。
由于影响物流运输成本的因素很多，控制措施既涉及运输环节本身，也涉及供应链的整个物流流程。
要想降低物流运输成本，就必须运用系统的观点和方法，进行综合分析，发现问题，解决问题，使物流运输活动更加优化、物流运输成本更加合理化。
本文已知把一种产品从产地一、二运到客户1、2、3处,产地的发量、客户的收量及各产地到各客户的运输单价已知。
本文要解决问题是：客户1为重要部门，必须全部满足需求量；满足客户2、3至少75%的的需求量；使总运费尽量少；从产地2到客户1的运量至少有1000个单位。
二．问题分析根据题目中所给出的条件知：有现成的两个产地和需要产品的三个客户。
且两个产地的产量不同，运送到各个客户的运费单价不同。
