基于EPFF算法的下料問題模型

徐標，陳昊，安佰玲

淮北師范大學 數學科學學院，安徽 淮北 235000

基于EPFF算法的下料問題模型

徐標，陳昊，安佰玲

淮北師范大學 數學科學學院，安徽 淮北 235000

1 問題重述

原料下料問題是企業生產中最為重要的問題之一。原材料利用率的高低直接反映著企業的生產水平，也是影響企業經濟效益的主要因素之一，同時切割模式的單一化也有利于降低成本，提高生產率。因而提高原料利用率，減少切割方式對我國經濟發展具有特別重要的意義。

“下料問題”是把相同形狀的一些原材料分割加工成若干個不同規格大小的零件的問題，此類問題在工程技術和工業生產中有著重要和廣泛的應用。

對單一原材料下料問題[1]進行探討；設此種原材料是長度為L，寬度為W的長方形，現有這種長方形原料一批，要將其制作成m種型號的零件，全部零件均保持與原材料一樣的厚度，但長度和寬度有所變化，分別為(l1，w1)，(l2，w2)，…，(lm，wm)，其中wi＜li＜L，wi＜W，i=1，2，…，m。m種零件的加工量分別為n1，n2，…，nm。加工時，零件的各邊要分別和原材料的邊相平行；這就是工程上所謂的二維下料問題。尤其當所有型號零件的寬度均與原材料相同，即wi=W，i=1，2，…，m，就是一維下料問題。

對于上述一維單一原材料下料問題，建立相應的數學模型，并同時求解下列問題：在生產能力允許的情況下給出滿足要求的下料方案，然后求出完成相同任務所需的原材料數，并計算廢料總長度和使用的下料方式數和。單一原材料的長度為3 000 mm，現有53種不同長度的零件需要加工。具體參數見文獻[1]中表1，其中li為需求零件的長度，ni為需求零件的數量。此外，在每個下料點處，由鋸縫所產生的損耗為5 mm。據估計，該企業每天下料的最大能力是100塊，要求在4天內完成的零件標號（i）為：5，7，9，12，15，18，20，25，28，36，48；要求不遲于6天完成的零件標號（i）為：4，11，24，29，32，38，40，46，50。

2 問題分析與建模

2.1 問題分析

原材料利用率的高低直接反映著企業的生產水平，也是影響企業經濟效益的主要因素之一。因而采用有效的方法，提高原材料的切割利用率，節約原料，對我國經濟發展具有特別重要的意義。

下料問題可以歸結為一個整數線性規劃問題，可以使用分枝定界法、單純形方法或者遺傳算法進行求解，由于在要求下料的零件種數較多時，其線性規劃的約束條件中的式子也較多，考慮使用Lingo軟件進行求解。對于下料的方式采用EPFF算法求出所有的下料組合，代入模型中，求出最優解，同時確定所用的下料方式。

2.2 符號說明

L：原材料的長度（為3 000 mm）；

W：原材料的寬度（為100 mm）；

li：第i種零件的長度，i=1，2，…，p；

wi：第i種零件的寬度，i=1，2，…，p；

ni：第i種零件的需求量，i=1，2，…，p；

(xkj)：下料方案矩陣，即第k天以第j種下料方式切割的原材料塊數，j=1，2，…，q ，k=1，2，…，d；

(aij)：下料方式矩陣，即第j種下料方式下每塊原材料生產第i種零件的數量，i=1，2，…，p，j=1，2，…，q；

(si)：第i類零件在某種下料方式下切割數量；

ci：第i類零件的面積，即ci=liwi；

c：每天的最大生產能力；

z：所需要的原材料數；

v：材料利用率（%）；

m：采用的下料方式個數。

2.3 建立模型

建立一個以消耗原材料總數最小為目標，下料方式又少的整數線性規劃[2-3]數學模型，目標函數為：

要求滿足一定的生產能力，即每天的生產總量不大于c，則有約束條件：

同時要求滿足需求量，有約束條件：

對于有時間限制的模型，則要給出給定時間內生產數量的下界約束，即：

i為要求在給定時間內完成的零件標號，xkj≥0，aij≥0且為整數。

至此，一維單一原材料實用下料問題的數學模型建立起來了，其中的第j種下料方式下每個原材料生產第i種零件的數量aij在零件種類比較少的情況下，可以采用枚舉法確定下料方式。對于零件種類比較多的，采用Lingo求解沒有可行解，無法給出下料方式矩陣。因此采用EPFF算法，用Matlab編程求出相應的下料方式，代入模型中，再交給Lingo求解，就求出了可行解，結果中可以確定具體采用了哪種下料方式使結果達到最優。原材料的平均利用

3 模型的求解

現有單一原材料的長度為3 000 mm，需要完成一項有53種不同長度零件的下料任務。此外，在每個下料點處由鋸縫所產生的損耗為5 mm。企業每天最大下料能力是100塊，又要求分別在4天、6天內完成不同類型的零件，給出最優方案。

首先確定下料方式矩陣(aij)p×q，同時將鋸縫所產生的損耗為5 mm考慮在內。由于零件種類有53種，使用枚舉法工作量太大，不可行，采用Lingo求解沒有可行解，也無法解出下料方式矩陣。這里采用EPFF算法，應用Matlab編程求解，給出下料方式矩陣。

一維下料問題可建模為裝箱問題。馮曉慧[4]等的EPFF算法是求解裝箱問題的一種較新的算法，它將所有的箱子分成8組，將實數列中的元素分成8類，稱（2/3，1），（7/12，2/3），（1/2，7/12），（5/12，1/2），（1/3，5/12），（1/4，1/3），（1/5，1/4），（0，1/5）上的元素分別為α1，α2，α3，β1，β2，β3，β4，γ共8類元素，同時用a1，a2，a3，b1，b2，b3，b4，r分別表示8類元素的數目。EPFF算法步驟如下：

（1）從β2，β3，β4類元素中取出a3個元素與α3類元素放在一起（若a3＞(b2+b3+b4)，則取完所有的β2，β3，β4類元素為止），再從β3，β4類元素中取出a2個元素與α2類元素放在一起。

（2）將α1類元素裝入第1組箱子中，每個箱子中裝入1個元素。

（3）將α2類元素及取出的β3，β4類元素裝入第2組箱子中，每個箱子最多裝1個α2類元素和1個β3或β4類元素。

（4）將α3類元素及取出的β2，β3，β4類元素裝入第3組箱子中，每個箱子最多裝1個α3類元素和1個β2或β3或β4類元素。

（5）將β1類元素及余下的β2，β3，β4類元素分別裝入第4～7組箱子中，各組箱子分別裝2，2，3，4個β1，β2，β3，β4類元素。

（6）將γ類元素按FF算法[4]裝人第8組箱子中。

這樣，利用Matlab編程最終就得到下料方式矩陣(aij)p×q，為53×62的矩陣。

首先考慮了4天的下料方式，建立模型如下：

同樣，可以得到6天的下料方式，其模型與4天的相似。但是，這些只是從局部考慮問題，二者得到的解不能統一到整體之中。于是，綜合二者于一個模型之中，制定出有4天、6天限制的53種零件的下料方案。在Matlab中用EPFF算法的計算結果得到需要的總原料數量約為809塊，這樣，估計需要d=9天，可以順利完成任務。于是得到模型：

表1 每天下料方式及相應切割的原材料塊數

用Lingo[8]編程求解得到可行解z＝808塊，以及每天使用的下料方式和在該種方式下切割的原材料塊數，如表1所示。

從表1中可以看出，第2天使用的下料方式有12、17、19、53、54，它們切割的原材料塊數分別為8塊、32塊、32塊、1塊、27塊。其他依此類推。

由此可以計算出材料利用率：

使用的下料方式有m=51種，廢料總長度為49 011 mm。

4 結束語

若單純采用線性整數規劃建立數學模型，則由于零件種類以及下料方式過多而無法得到最優解，給不出下料方式陣；若僅采用EPFF算法，通過編寫程序建模，則由于無法考慮對某些零件的加工時間的限制而使得到的解只是一個等額加工完所有零件的整體方案，無法給出具體每一天的加工方案。因此，綜合考慮兩種方式，建立了混合型模型，很好地解決了實用下料問題，得到了較少的下料方式和較高的原材料利用率。本模型具有思路簡潔，易于操作，適用性強等特點。

[1]第一屆全國研究生數學建模競賽試題[EB/OL].[2012-08-10]. http：//gmcm.seu.edu.cn/s/274/t/1419/68/70/info26736.htm.

[2]運籌學教材編寫組.運籌學[M].3版.北京：清華大學出版社，2005.

[3]胡祥培.運籌學講義.大連：大連理工大學管理學院，2001.

[4]馮曉慧，李菊娥，任春麗.裝箱問題的一種新算法及其性能比的證明[J].西安電子科技大學學報，1998，25（2）：231-233.

[5]姜啟源.數學模型[M].北京：高等教育出版社，2003.

[6]蕭樹鐵，姜啟源，何青，等.數學實驗[M].北京：高等教育出版社，1999.

[7]李瓊，金升平.一維優化下料問題的模型與算法的綜合比較[J].武漢交通科技大學學報，1998，22（4）.

[8]謝金星，薛毅.優化建模與LINDO/LINGO軟件[M].北京：清華大學出版社，2006.

[9]周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，1999.

[10]劉潤濤，陳媛婧.型材下料問題算法研究[J].計算機工程與應用，2009，45（25）：215-217.

[11]包奇金寶，姜靜清，宋初一，等.基于粒子群與模擬退火算法的板材優化下料[J].計算機工程與應用，2008，44（26）：246-248.

XU Biao,CHEN Hao,AN Bailing

School of Mathematical Science,Huaibei Normal University,Huaibei,Anhui 235000,China

The cutting-stork-problem of a single one-dimensional materials is considered,with optimal and EPFF algorithms, the hybrid model is built.Namely the cutting way array is obtained with EPFF algorithm,then it is substituted into the linear programming model.Under the limitation of the processing time and the maximum processing capacity,it gets the requirements of practical cutting program.

integer programming;cutting-stork-problem;EPFF algorithms;material utilization

研究一維單一原料下料問題，將最優化模型和EPFF算法相結合，建立了混合型模型，即先采用EPFF算法得到下料方式陣，再將其代入線性規劃模型中，加上了加工時間以及最大加工能力的限制；最后確定了滿足要求的實用下料方案。

整數規劃；下料問題；EPFF算法；材料利用率

A

O29

10.3778/j.issn.1002-8331.1303-0090

XU Biao,CHEN Hao,AN Bailing.Models of cutting stork problem based on EPFF algorithms.Computer Engineering and Applications,2013,49（13）：56-58.

國家自然科學基金（No.11171156）；安徽省高等學校省級自然科學研究項目（No.KJ2012Z346，No.KJ2013Z285）；皖淮北師范大學青年科研項目（No.700437）。

徐標（1981—），男，講師，研究方向為數值計算方法，數理統計與建模；陳昊（1982—），男，講師，研究方向為偏微分方程數值解；安佰玲（1977—），女，講師，研究方向為金融數學與建模。E-mail：xubiao512@163.com

2013-03-08

2013-04-30

1002-8331（2013）13-0056-03

◎網絡、通信、安全◎