最優(yōu)下料問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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