最優(yōu)下料問題

1、主講：黃先玖黃先玖研究生建模研究生建模2004年年B題題l“下料問題下料問題(cutting stock problem)”是把是把相同形狀的一些原材料分割加工成若干相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題，此類問個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用廣泛的應(yīng)用. 這里的這里的“實用下料問題實用下料問題”則是在某企業(yè)的實際條件限制下的單一則是在某企業(yè)的實際條件限制下的單一材料的下料問題。材料的下料問題。 l現(xiàn)考慮單一原材料下料問題現(xiàn)考慮單一原材料下料問題. 設(shè)這種原材料呈設(shè)這種原材料呈長方形，長度為長

2、方形，長度為L,寬度為寬度為W，現(xiàn)在需要將一，現(xiàn)在需要將一批這種長方形原料分割成批這種長方形原料分割成m種規(guī)格的零件種規(guī)格的零件, 所所有零件的厚度均與原材料一致，但長度和寬有零件的厚度均與原材料一致，但長度和寬度分別為度分別為(l1,w1) ，(lm,wm )，其中，其中wiliL，wiW. (i=1,2,m)。m種零件的需求量分別為種零件的需求量分別為n1,n2,nm。下料時，零件的邊必須分別和原下料時，零件的邊必須分別和原材料的邊平行。這類問題在工程上通常簡稱材料的邊平行。這類問題在工程上通常簡稱為二維下料問題。特別當(dāng)所有零件的寬度均為二維下料問題。特別當(dāng)所有零件的寬度均與原材料相等，即

3、，則問題稱為一維下料問與原材料相等，即，則問題稱為一維下料問題。特別當(dāng)所有零件的寬度均與原材料相等，題。特別當(dāng)所有零件的寬度均與原材料相等，即即wi=W. (i=1,2,m) ，則問題稱為一維下料，則問題稱為一維下料問題。問題。 l一個好的下料方案首先應(yīng)該使原材料的一個好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低成本，利用率最大，從而減少損失，降低成本，提高經(jīng)濟效益。其次要求所采用的不同提高經(jīng)濟效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的的下料方式盡可能少，即希望用最少的下料方式來完成任務(wù)。因為在生產(chǎn)中轉(zhuǎn)下料方式來完成任務(wù)。因為在生產(chǎn)中轉(zhuǎn)換下料方式需要費用和時間

4、，既提高成換下料方式需要費用和時間，既提高成本，又降低效率。此外，每種零件有各本，又降低效率。此外，每種零件有各自的交貨時間，每天下料的數(shù)量受到企自的交貨時間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實用下料問題業(yè)生產(chǎn)能力的限制。因此實用下料問題的目標(biāo)是在生產(chǎn)能力容許的條件下，以的目標(biāo)是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時完成需最少數(shù)量的原材料，盡可能按時完成需求任務(wù)求任務(wù), 同時下料方式數(shù)也盡量地小同時下料方式數(shù)也盡量地小.請請你們?yōu)槟称髽I(yè)考慮下面兩個問題。你們?yōu)槟称髽I(yè)考慮下面兩個問題。l1.建立一維單一原材料實用下料問題的數(shù)學(xué)模型, 并用此模型求解下列問題，制定出在生產(chǎn)

5、能力容許的條件下滿足需求的下料方案, 同時求出等額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長度. 單一原材料的長度為 3000mm, 需要完成一項有53種不同長度零件的下料任務(wù). 具體數(shù)據(jù)見表一，其中 li為需求零件的長度，ni為需求零件的數(shù)量. 此外，在每個切割點處由于鋸縫所產(chǎn)生的損耗為5mm. 據(jù)估計，該企業(yè)每天最大下料能力是100塊 ，要求在4天內(nèi)完成的零件標(biāo)號(i)為: 5,7,9,12,15,18,20,25, 28,36,48; l要求不遲于6天完成的零件標(biāo)號(i)為:4,11,24,29,32,38,40,46,50. (提示：可分層建模。(1).先考慮用材料既少,下料

6、方式又少的模型, 或先僅考慮所用材料最少的模型及增加一種下料方式大致相當(dāng)于使原材料總損耗增加0.08%情況下的最佳方案。 (2).在解決具體問題時,先制定4天的下料方案,再制定6天的下料方案,最后制定53種零件的下料方案. 這一提示對第2題也部分適用.)l2.建立二維單一原材料實用下料問題的數(shù)學(xué)模建立二維單一原材料實用下料問題的數(shù)學(xué)模型型, 并用此模型求解下列問題并用此模型求解下列問題.制定出在企業(yè)生制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的下料方案產(chǎn)能力容許的條件下滿足需求的下料方案, 同同時求出等額完成任務(wù)所需的原材料塊數(shù)和所時求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù)需下料方式數(shù).

7、這個問題的單一原材料的長度這個問題的單一原材料的長度為為 3000mm,寬度為寬度為100mm, 需要完成一項有需要完成一項有43種不同長度和寬度零件的下料任務(wù)種不同長度和寬度零件的下料任務(wù). 具體數(shù)具體數(shù)據(jù)見表二，其中據(jù)見表二，其中 li,wi,ni分別為需求零件的長分別為需求零件的長度、寬度和數(shù)量度、寬度和數(shù)量. 切割時的鋸縫可以是直的也切割時的鋸縫可以是直的也可以是彎的，切割所引起的鋸縫損耗忽略不可以是彎的，切割所引起的鋸縫損耗忽略不計計.據(jù)估計，該企業(yè)每天最大下料能力是據(jù)估計，該企業(yè)每天最大下料能力是20塊塊 要求在要求在4天內(nèi)完成的零件標(biāo)號天內(nèi)完成的零件標(biāo)號(i)為為: 3,7,9,

8、12,15, 18, 20, 25, 28, 36. 1、下料問題下料問題(cutting stock problem)”是把相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題；2、二維下料問題二維下料問題-下料時，零件的邊必須分別和原材料的邊平行 ;3、一維下料問題一維下料問題-所有零件的寬度均與原材料相等 。 本題是有交貨時間限制的大規(guī)模單一原本題是有交貨時間限制的大規(guī)模單一原材料下料問題。材料下料問題。 l1、目標(biāo)是既要所用材料最少，也要下、目標(biāo)是既要所用材料最少，也要下料方式少。料方式少。l2、有交貨時間限制、有交貨時間限制 l（1）每天下料的數(shù)量受到企業(yè)生產(chǎn)能力）每天下料的

9、數(shù)量受到企業(yè)生產(chǎn)能力的限制，在未完成需求任務(wù)前，每天下料的限制，在未完成需求任務(wù)前，每天下料的數(shù)量等于最大下料能力。的數(shù)量等于最大下料能力。l（2）每個切割點處由于鋸縫所產(chǎn)生的損）每個切割點處由于鋸縫所產(chǎn)生的損耗不可忽略。耗不可忽略。l（3）增加一種下料方式大致相當(dāng)于使原）增加一種下料方式大致相當(dāng)于使原材料總損耗增加材料總損耗增加0.08%。l（4）每種零件有各自的交貨時間，若某）每種零件有各自的交貨時間，若某零件無交貨時間，則記該零件交貨時間為零件無交貨時間，則記該零件交貨時間為無窮大。無窮大。 一維下料問題一維下料問題 零件種類總數(shù) 第i種下料方式下料的根數(shù) 下料方式的種類數(shù) 第i種下料方

10、式每根的余料 mixki模型的建立 1%08. 01)(min11kiikiiixsignalxxf然后代入，推得該線光源的范圍為0.03, 0.03m。模型的求解對于該問題，因為可能的下料方式將隨需要的零件種類數(shù)量成指數(shù)級增長，所以它是一個NPHard問題。這樣對于大多數(shù)問題，一般方法無法得到最優(yōu)結(jié)果或無法及時得到最優(yōu)結(jié)果。因此對于大規(guī)模的一維下料問題，我們給出了結(jié)合動態(tài)規(guī)劃和貪婪算法的新算法，稱之為DP貪婪算法?；舅枷胧牵簩δＰ陀嬎銜r，不用先得到一定數(shù)基本思想是：對模型計算時，不用先得到一定數(shù)量的下料方案，而是在選取下料方案時就以數(shù)學(xué)量的下料方案，而是在選取下料方案時就以數(shù)學(xué)模型中的目標(biāo)

11、和約束條件為基礎(chǔ)來進行尋找。模型中的目標(biāo)和約束條件為基礎(chǔ)來進行尋找。 為了保證盡量節(jié)省材料，應(yīng)該盡量將比較大的零件先進行處理，并同時輔以長度小的零件，以保證單個原料的利用率盡量大。因此對每一個零件按照其長度大小依次給定處理順序的權(quán)值。為了保證時間的要求，有要求的零件應(yīng)該盡量優(yōu)先處理，對每一個零件按時間緊迫度t依次給定一個處理順序的權(quán)值。兩者的結(jié)合將作為每一個零件動態(tài)規(guī)劃初始權(quán)值。在決定了處理順序后，首先利用貪婪思想，選取當(dāng)前尚沒有得到的零件集合中權(quán)值最大的一個進行處理。 調(diào)用動態(tài)規(guī)劃方法，得到一種下料方式，此方法里含有當(dāng)前的零件，在得到此下料方式后，先盡可能按照此方式進行處理，以盡量減少下料方

12、式數(shù)，然后再應(yīng)用貪婪思想。依次類推，直到得到所有的零件。這樣我們將得到一種下料方案。如果此方案滿足約束要求則停止處理，否則對權(quán)值進行調(diào)整，如果結(jié)果不能滿足時間緊迫度的限制，則將優(yōu)先權(quán)值步長直接調(diào)節(jié)到理論上限，隨后通過二分查找的方法進行選擇，如果材料利用率過低，則參照以上方法進行調(diào)節(jié)。而后重復(fù)上述過程，直到得到合理結(jié)果。 1. 局部最優(yōu)/計算當(dāng)前單根利用率最大值，并得到一組可行下料方案FOR I = 1 TO 工件總種類數(shù)FOR J = 原材料總長度 DOWNTO 0 IF 在J的位置已經(jīng)有解 FOR K = 第I件工件中未切割的數(shù)量 DOWNTO 1 當(dāng)前長度 = J + 第I件工件的長度*K

13、 IF 當(dāng)前長度位置尚未得到解 THEN 保存當(dāng)前解 ELSE 對兩個解進行比較選取較優(yōu)解FOR I = 材料長度 DOWNTO 1IF 當(dāng)前長度有解存在 THEN 返回解算法描述算法描述： 2.全局貪婪對所有需要的零件進行處理FOR I = 1 TO 工件種類總數(shù)WHILE 如果當(dāng)前種類還有剩余(按照權(quán)值大小依次處理) DO利用上述局部最優(yōu)處理選取一種至少含有當(dāng)前種類一根的最優(yōu)解累加計算結(jié)果 更新數(shù)據(jù)表格3.反復(fù)調(diào)整調(diào)整權(quán)值IF 得到全局的解法不合理IF 不能按時完成零件 按規(guī)則加大優(yōu)先權(quán)值ELSE 浪費過于大 按規(guī)則加大長度權(quán)值調(diào)用上述全局貪婪算法描述算法描述： l二維情況下，假設(shè)在矩形原

14、料切割時采用正二維情況下，假設(shè)在矩形原料切割時采用正交切割，切割時的鋸縫可以是直的也可以是交切割，切割時的鋸縫可以是直的也可以是彎的；不允許零件旋轉(zhuǎn)；而且切割所引起的彎的；不允許零件旋轉(zhuǎn)；而且切割所引起的鋸縫損耗忽略不計。鋸縫損耗忽略不計。二維下料問題二維下料問題 1%08. 01min11kiikiiixsignalxxf), 1;, 1(0,);, 1(), 1(), 1(max,.,1)(,1,1,1,mjkiyxddkixyymjnyamjdymjnxaajjljjdiijlididijkidiijjkidijkiiijmji且為整數(shù) 目前，解有交貨時間限制的二維下料問題的常用目前，解

15、有交貨時間限制的二維下料問題的常用方法是啟發(fā)式算法，但是這種方法在大規(guī)模的下方法是啟發(fā)式算法，但是這種方法在大規(guī)模的下料問題中并不能將問題的規(guī)模降到一個合理的范料問題中并不能將問題的規(guī)模降到一個合理的范圍。對于大規(guī)模的二維下料問題，本文給出新的圍。對于大規(guī)模的二維下料問題，本文給出新的求解方法。先利用降維思想將二維下料問題化為求解方法。先利用降維思想將二維下料問題化為兩個一維下料問題，對每一個一維下料問題，再兩個一維下料問題，對每一個一維下料問題，再使用本文一維下料問題的使用本文一維下料問題的DP貪婪算法進行計算，貪婪算法進行計算，再將兩者的結(jié)果結(jié)合起來，得到最終的結(jié)果。再將兩者的結(jié)果結(jié)合起來

16、，得到最終的結(jié)果。 模型求解模型求解 本文采用的降維思想為：第一步，先考慮長度（或?qū)挾龋┻@一維(以下采用先考慮寬度為例進行說明)，將寬度相同的零件歸為一類，對每一類,假設(shè)各自存在與該類等寬與原母板等長的母板。這樣，每一類零件寬度與各自的母板寬度相等，這就轉(zhuǎn)化為一維下料問題。故可借助一維下料模型的算法解出原母板在長度維上的切割方式。這種方式找到的是長度維上的局部近似最優(yōu)。第二步，考慮寬度（或長度）這一維。由上一步，我們可以得到每一寬度各自所需的母板根數(shù)，可將每一類寬度視為一維切割中一個零件的長度，將每一類所需的根數(shù)作為零件的下料任務(wù)，原母板的寬度作為現(xiàn)在一維切割原料的長，這樣又得到一個一維下料問

17、題，同樣借助一維下料 模型的解法來獲得局部近似最優(yōu)解。經(jīng)過上述兩步后，二維下料問題就轉(zhuǎn)化為了兩個一維下料問題，在借助一維下料問題的求解算法得到兩個局部最優(yōu)解后，可以通過兩者的結(jié)合得到最終解。算法的基本思想是： 首先比較長的種類和寬的種類，從中選取種類比較少的一個作為第一次降維考慮的基礎(chǔ)(在不影響一般性的前提下，以下假設(shè)寬度種類較少來進行描述)。按照寬度對所有零件進行分類，然后假設(shè)已經(jīng)有各種寬度的模板足夠多，而模板的長和原材料的長相等。這樣在接下來的切割過程中將不考慮跨度問題，這樣將完全變?yōu)橐痪S下料問題。為了得到更優(yōu)的解應(yīng)該優(yōu)先處理寬度最寬的一類，所以依據(jù)寬度給定每一類零件一個權(quán)值。同時要考慮到

18、交貨時間的要求，交貨時間比較短的零件應(yīng)該優(yōu)先處理，所以依據(jù)交貨時間給定每一類零件一個權(quán)值，兩者的結(jié)合作為處理順序的權(quán)值。 在接下來的處理中，應(yīng)該選取當(dāng)前未處理集合中權(quán)值最大一類寬度的零件借助一維下料算法進行處理，以得到需要此類寬度模板的數(shù)量。為了提高原材料利用率，當(dāng)一類寬度零件處理完畢后，如果有一些余料，將采用動態(tài)規(guī)劃方法，在利用率高的要求下將其它寬度的零件盡量用這些余料來獲得，直到剩下的余料不能再被使用為止。重復(fù)這個過程，可以得到每一類寬度的模板需要多少數(shù)目，同時得到一種下料方案。 接下來，將每一種寬度作為一維下料問題中零件的規(guī)格，而每一類寬度需要的數(shù)目就是一維下料問題中零件的數(shù)量要求，而此次一維下料問題的原材料長度是二維下料問題中原材料的寬度，對于這個一維下料問題借助上文的算法對其進行處理，得到一種下料方案。將第一次得到的一維下料方案和第二次得到的一維下料方案按順序進行組合，即得到這個問題的下料方案。而第二次一維下料問題所需要的原材料個數(shù)就是在二維下料問題中所需要原材料塊數(shù)。 比較所有零件每一維的類別數(shù)對所有零件以其中類別數(shù)最少的一維為主進行排序WHILE 能取出一個等長（寬）