下料問(wèn)題含代碼程序

1、摘要關(guān)鍵字：整數(shù)規(guī)劃模型 多目標(biāo)決策優(yōu)化NP問(wèn)題 下料方案 分支定界法“下料問(wèn)題(cutting stock problem)”是把相同形狀的一些原材料分割加工成若干個(gè)不同規(guī)格大小的零件的問(wèn)題，此類(lèi)問(wèn)題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用. 這里的“實(shí)用下料問(wèn)題”則是在某企業(yè)的實(shí)際條件限制下的單一材料的下料問(wèn)題?，F(xiàn)考慮單一原材料下料問(wèn)題. 設(shè)這種原材料呈長(zhǎng)方形，長(zhǎng)度為,寬度為，現(xiàn)在需要將一批這種長(zhǎng)方形原料分割成種規(guī)格的零件, 所有零件的厚度均與原材料一致，但長(zhǎng)度和寬度分別為，其中wi. 種零件的需求量分別為.下料時(shí)，零件的邊必須分別和原材料的邊平行。這類(lèi)問(wèn)題在工程上通常簡(jiǎn)稱(chēng)為二維下料問(wèn)題

2、。特別當(dāng)所有零件的寬度均與原材料相等，即，則問(wèn)題稱(chēng)為一維下料問(wèn)題。一個(gè)好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低成本，提高經(jīng)濟(jì)效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來(lái)完成任務(wù)。因?yàn)樵谏a(chǎn)中轉(zhuǎn)換下料方式需要費(fèi)用和時(shí)間，既提高成本，又降低效率。此外，每種零件有各自的交貨時(shí)間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實(shí)用下料問(wèn)題的目標(biāo)是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料，盡可能按時(shí)完成需求任務(wù), 同時(shí)下料方式數(shù)也盡量地小.就某企業(yè)考慮下面兩個(gè)問(wèn)題：1 建立一維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型, 并用此模型求解下列問(wèn)題，制定出在生產(chǎn)能力容許的條

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

4、慮所用材料最少的模型及增加一種下料方式大致相當(dāng)于使原材料總損耗增加0.08%情況下的最佳方案。(2).在解決具體問(wèn)題時(shí),先制定4天的下料方案,再制定6天的下料方案,最后制定53種零件的下料方案. 這一提示對(duì)第2題也部分適用.)表1 需求材料的數(shù)據(jù) 單位：mm123456789101743168015321477131312851232121711801177421610438460486101112131415161718192011051055104610321030975893882847845824882830163821222324252627282930830795766745730

5、7197146956456303084434184490303132333435363738394061060059058858257854048835534330212108482196832452424142434445464748495032051541441140532831329027526588860136468286602286515253255184155 19257242 建立二維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型, 并用此模型求解下列問(wèn)題.制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的下料方案, 同時(shí)求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個(gè)問(wèn)題的單一原材料的長(zhǎng)度為

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

7、0830795766745732722714690665633302035303045503020309040121268741012270902122232425262728293063060059058858257854048845543430352020302050202030906125082082496246220162923132333435363738394042041541441140532831329027526520302030203050302030402440180536121286862002686414243255184155302050 69235752本文要解決

8、的是一個(gè)典型的多目標(biāo)決策優(yōu)化問(wèn)題。一個(gè)好的下料方案首先應(yīng)該使原材料的利用率最大，從而減少損失，降低成本，提高經(jīng)濟(jì)效益。其次要求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來(lái)完成任務(wù)。因?yàn)樵谏a(chǎn)中轉(zhuǎn)換下料方式需要費(fèi)用和時(shí)間，既提高成本，又降低效率，故企業(yè)都希望盡可能地減少下料方式的數(shù)目。此外，每種零件有各自的交貨時(shí)間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實(shí)用下料問(wèn)題的目標(biāo)是在生產(chǎn)能力容許的條件下，在規(guī)定的時(shí)間需求內(nèi)，以最少數(shù)量的原材料，盡可能按時(shí)完成需求任務(wù)，同時(shí)下料方式數(shù)也盡量地小。為順利解決這一問(wèn)題，我們先從最基本的單目標(biāo)決策問(wèn)題人手，以材料損耗最少為目標(biāo)，由于個(gè)別零件的生產(chǎn)

9、有時(shí)間的要求，因此，在下料時(shí)就應(yīng)該優(yōu)先生產(chǎn)那些有時(shí)間限制要求的零件，并且通過(guò)不同的數(shù)學(xué)原理建立多個(gè)單目標(biāo)決策的最優(yōu)化模型，得出最初的結(jié)果，并加以比較分析，然后逐步增加其約束條件，并根據(jù)這些約束條件進(jìn)一步完善我們的最優(yōu)化模型，求出在需求的時(shí)間段內(nèi)下料方式和損耗都最少的最優(yōu)結(jié)果，緊接著再求出剩余板材下料方式和損耗的最優(yōu)結(jié)果，從而最終得出既滿足時(shí)間條件限制又滿足損耗少、下料方式數(shù)小的最優(yōu)結(jié)果。具體流程圖如下： 圖1 總體流程圖1. 假設(shè)每次切割都準(zhǔn)確無(wú)誤。2. 每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制，在未完成需求任務(wù)前，每天下料的數(shù)量等于最大下料能力。3. 模型一中每切得一個(gè)規(guī)格的零件需要的原材料。4

10、. 除最后一天外，其余每天均達(dá)到最大下料能力。5. 除了要求在規(guī)定時(shí)間內(nèi)完成所需零件外，不要求其余零件加工排列順序。6. 模型二中，切割所引起的鋸縫損耗忽略不計(jì)。4.符號(hào)說(shuō)明符號(hào)符號(hào)解釋說(shuō)明需求零件的數(shù)量需求零件的長(zhǎng)度需求零件的寬度第i種下料方式可生產(chǎn)第j種零件的數(shù)量不同的下料方式所使用的原材料的數(shù)目每種下料方式應(yīng)用于每個(gè)原材料上所剩的余料使用下料方式的種類(lèi)第種零件所需要生產(chǎn)的數(shù)量原材料長(zhǎng)度，為30004天內(nèi)需要完成的零件編號(hào)建立集合6天內(nèi)需要完成的零件編號(hào)建立集合理論所采用的原材料數(shù)目實(shí)際采用原材料的數(shù)目完成任務(wù)后的材料利用率問(wèn)題二中4天內(nèi)需要完成的零件編號(hào)建立集合對(duì)于一維優(yōu)化下料問(wèn)題，屬于

11、整數(shù)規(guī)劃問(wèn)題，從計(jì)算復(fù)雜性理論分析，該問(wèn)題屬于NP難題,即無(wú)法在多項(xiàng)式時(shí)間(在計(jì)算復(fù)雜度理論中，指的是一個(gè)問(wèn)題的計(jì)算時(shí)間m(n)不大于問(wèn)題大小n的多項(xiàng)式倍數(shù))內(nèi)求解。雖然整數(shù)規(guī)劃問(wèn)題是NP難題，但是線性問(wèn)題卻是有有效算法的。所以要想求出下料方案的最優(yōu)解，可以考慮不先求解整數(shù)規(guī)劃問(wèn)題而先來(lái)求解其相應(yīng)的線性問(wèn)題，然后用計(jì)算機(jī)程序進(jìn)行求解。首先考慮在滿足時(shí)間需求的情況下，材料總損失最少的情況，然后盡量使得總的下料方式數(shù)目最少，故這里要尋找到所有下料方式中利用率最高的方式，同時(shí)在滿足生產(chǎn)力要求的情況下進(jìn)行適當(dāng)調(diào)整，采用盡可能少的下料方式，這樣便可以得到一維下料問(wèn)題的優(yōu)化結(jié)果。根據(jù)題意，現(xiàn)有數(shù)量充足的長(zhǎng)

12、度為3000mm的原材料，需要完成一項(xiàng)有53種不同長(zhǎng)度零件的下料任務(wù)。要求在生產(chǎn)能力許可的條件下，既省材料又容易操作(即下料方式盡可能少)，由于本文問(wèn)題的特殊性，還需要考慮個(gè)別標(biāo)號(hào)的零件在4天內(nèi)及6天內(nèi)完成。故先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將4天和6天內(nèi)完成的任務(wù)篩選出來(lái)，優(yōu)先處理后再進(jìn)行其他標(biāo)號(hào)零件的加工。按照前面的分析，我們現(xiàn)假設(shè)有m種不同的下料方式，再根據(jù)每種零件的需求量，可求得每種零件應(yīng)用的次數(shù)，這樣采用第一種下料方式生產(chǎn)的第一種零件的個(gè)數(shù)為個(gè)，同理可知，表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，則采用第m種下料方式所能得到的第j種零件的數(shù)量表示為，為更好地表示這個(gè)對(duì)應(yīng)關(guān)系，建立如下對(duì)應(yīng)關(guān)系矩陣

13、：則使用m種不同的下料方式所使用的原材料的數(shù)目為，同樣用矩陣的方式來(lái)表示，則有所需原材料數(shù)目為：由于我們以原材料總損耗最少為目標(biāo)，所以首先計(jì)算每種下料方式產(chǎn)生的余料長(zhǎng)度，由于在每個(gè)切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm. 故每種下料方式應(yīng)用于每個(gè)原材料上所剩的余料表達(dá)式為： 則建立原材料總損耗最少的目標(biāo)函數(shù)為： ()其中表示第種下料方式所消耗的原材料數(shù)目，表示第種下料方式所得余料。又為方便企業(yè)加工生產(chǎn)，減少不必要的更換下料方式所產(chǎn)生的麻煩，企業(yè)希望所采用的下料方式盡可能少，因此建立第二個(gè)目標(biāo)函數(shù)：1)由于所要生產(chǎn)的每種型號(hào)的零件數(shù)量題中已經(jīng)給定，故有限制條件： ()其中，表示第種下料方式可生產(chǎn)第

14、j種零件的數(shù)量，表示第種下料方式所消耗的原材料數(shù)目，表示第種零件所需要生產(chǎn)的數(shù)量，。2)由于題目中所給出的各個(gè)編號(hào)的零件都有給定的長(zhǎng)度，且原材料長(zhǎng)度已定，故在考慮了鋸縫后，還要考慮原材料長(zhǎng)度對(duì)下料方式的限制，即對(duì)于任意一種下料方式，所得到的零件總長(zhǎng)度與鋸縫總長(zhǎng)度之和要小于等于每根原材料的總長(zhǎng)度，同時(shí)還要考慮對(duì)于每一種下料方式的廢料長(zhǎng)度要小于零件的最小長(zhǎng)度，由題中所給數(shù)據(jù)可知，需要生產(chǎn)的零件長(zhǎng)度最小為，故此約束表達(dá)式為：其中為每個(gè)編號(hào)對(duì)應(yīng)的零件長(zhǎng)度。3)因?yàn)樗枇慵纳a(chǎn)有時(shí)間的限制，相應(yīng)編號(hào)的零件必須在規(guī)定的時(shí)間內(nèi)生產(chǎn)完成，要求4天完成的零件編號(hào)為：，共有11種零件；要求6天內(nèi)完成的零件編號(hào)為

15、：，共有9種型號(hào)的零件。為了在最短時(shí)間內(nèi)完成所有零件生產(chǎn)的任務(wù)，在滿足該企業(yè)每天最大下料能力100塊的生產(chǎn)能力條件下，我們?cè)?天內(nèi)完成的任務(wù)中增加4天內(nèi)需要完成的任務(wù)，即6天內(nèi)需要生產(chǎn)20種型號(hào)的零件，為方便下文敘述，我們將4天內(nèi)需要完成的零件編號(hào)建立集合，即，同理將6天內(nèi)需要完成的零件編號(hào)建立集合，即，對(duì)此建立約束條件表達(dá)式為：其中表示第種下料方式中所切割的第種零件數(shù)占這種下料方式中所切割的零件4天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此表示4天內(nèi)完成零件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能力要求，上述表達(dá)式所計(jì)算出采用的原材料總數(shù)要小于等于，另外若，則表示第種下料方式中沒(méi)有切割到集合中的零件；同

16、理，表示第種下料方式中所切割的第種零件數(shù)占這種下料方式中所切割的零件6天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此表示6天內(nèi)完成零件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能力要求，上述表達(dá)式所計(jì)算出采用的原材料總數(shù)要小于等于，另外若，則表示第種下料方式中沒(méi)有切割到集合中的零件。綜上所述，針對(duì)本文一維下料問(wèn)題建立如下數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件 對(duì)于該問(wèn)題，首先考慮在滿足時(shí)間需求的情況下，材料總損失最少的情況，然后盡量使得總的下料方式數(shù)目最少，由于本文問(wèn)題的特殊性，還需要考慮個(gè)別標(biāo)號(hào)的零件在4天內(nèi)及6天內(nèi)完成。故先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將4天和6天內(nèi)完成的任務(wù)篩選出來(lái)，優(yōu)先處理后再進(jìn)行其他標(biāo)號(hào)零件的加工。將集合和

17、集合中的零件進(jìn)行優(yōu)先處理，利用lingo軟件編程，先不考慮下料方式的數(shù)目對(duì)結(jié)果的影響，在滿足原材料總損失最小的前提下再調(diào)整下料方式的數(shù)目，同時(shí)在保證生產(chǎn)集合和集合中的零件的基礎(chǔ)上，只要在生產(chǎn)能力許可范圍內(nèi)，還可以生產(chǎn)其他對(duì)生產(chǎn)時(shí)間沒(méi)有限制的零件。對(duì)此，運(yùn)行程序得到的這一批零件生產(chǎn)的結(jié)果，然后再利用matlab程序?qū)λ孟铝戏绞竭M(jìn)行調(diào)整，然后針對(duì)個(gè)別存在問(wèn)題的下料方式進(jìn)行調(diào)解后得到的最終結(jié)果為：表3 優(yōu)先考慮有時(shí)間限制零件的處理結(jié)果下料方式零件尺寸(mm)及數(shù)量余料(mm)原材料(塊)1265(11)3542343(8) 184(1)3733600(4) 265(2)45514645(1) 60

18、0(3) 265(2)015645(4) 265(1)135216750(4)5171105(2) 600(1) 155(1)25181105(2) 645(1)135291477(1) 645(1) 600(1) 255(1)131101477(2) 411811290(2) 265(8) 255(1)0112735(2) 290(4) 355(1)0113290(10)552814578(1) 1105(2) 184(1)18115578(5)90116847(1) 730(1) 695(2)13217730(4)65718343(6) 265(1) 630(1)16119847(1) 7

19、30(2) 343(1) 328(1)2120847(3) 414(1) 35121348(7) 540(1)241122882(1) 488(4)146123882(3) 265(1)74100241030(1) 1477(1) 414(1)661251030(1) 577(1) 328(1) 265(2) 515(1)31261030(2) 645(1) 265(1)152271030(2) 577(1) 343(1)41281057(2) 265(1) 610(1)11291182(2) 600(1)263301232(2) 265(1) 255(1)62311313(2) 328(1)

20、99232343(3) 265(1) 1680(1)61合計(jì)1235273由表3可知，優(yōu)先生產(chǎn)有時(shí)間限制的零件，則共有32種下料方式，所產(chǎn)生的廢料為1235mm，共需要原材料的數(shù)量為273塊。接下來(lái)開(kāi)始生產(chǎn)沒(méi)有時(shí)間限制的零件，因?yàn)橛袝r(shí)間限制的零件已經(jīng)生產(chǎn)完畢，故在此不予以考慮，除去生產(chǎn)有時(shí)間限制的零件后，利用lingo程序運(yùn)行得到結(jié)果后，再利用matlab程序?qū)λ孟铝戏绞竭M(jìn)行調(diào)整，然后針對(duì)個(gè)別存在問(wèn)題的下料方式進(jìn)行調(diào)解后得到的最終結(jié)果為： 表4 沒(méi)有時(shí)間限制零件的處理結(jié)果余料(mm)下料方式零件尺寸(mm)及數(shù)量原材料(塊)151184(15) 155(1) 32052275(10)5814

21、33313(9)3144411(5) 184(4) 155(1)1935411(7)71256795(1) 515(4)1857320(8) 155(2)1898355(5) 184(4)11259355(8)428010540(5)27011582(5)384612766(1) 588(1) 155(10)14013588(5)26214590(1) 582(4)1315590(2) 540(1) 313(4)13016590(5)21017610(4) 540(1)318518610(4) 355(1)3519630(1) 610(3) 355(1) 155(1) 15120630(4)

22、414(1)110521630(4) 355(1)612922714(4)11123719(2) 588(2) 355(1)110924719(4)49925766(3) 588(1)16526795(3) 540(1)222527830(3) 275(1)118228830(1) 313(1)83029847(3) 414(1)213330893(1) 515(3) 414(1)13831975(2) 588(1) 414(1)138321032(2) 893(1)3131331032(2) 795(1)110341046(2) 893(1)2153351177(1) 830(2)19036

23、1177(1) 893(1) 830(1)11371177(2) 155(4)16381177(2) 355(1) 275(1)226391177(2) 610(1)116401217(2) 540(1)311411285(2) 414(1)1107421285(2) 313(1)29220431532(1) 411(3)1168441532(1) 255(6)37128451532(1) 405(2) 255(2)1108461532(1) 405(2) 275(1) 255(1) 1145471532(1) 405(3)44282481532(1) 588(2)20134491680(1)

24、 588(2)213112501680(1) 588(1) 610(1)172511680(1) 411(3)135521743(1) 1217(1)283531743(1) 582(2)139541743(1) 893(1) 155(2)1191555540(2)16822合計(jì)550如表4所示，除去所有有時(shí)間限制的零件，以及為了調(diào)整其余料與有時(shí)間限制的零件一同優(yōu)先生產(chǎn)的零件之外，剩下的沒(méi)有時(shí)間限制的零件生產(chǎn)共需要55種下料方式，所產(chǎn)生的廢料總長(zhǎng)度為6822mm，且需要550塊原材料。綜上可知，完成所有零件的生產(chǎn)，要采用種下料方式，且共需要塊原材料，所產(chǎn)生的余料總長(zhǎng)度為：。通過(guò)對(duì)本文中的一維下

25、料問(wèn)題建立數(shù)學(xué)模型，并結(jié)合lingo程序計(jì)算，得到了完成任務(wù)的滿意結(jié)果。為進(jìn)一步驗(yàn)證模型的結(jié)果，提出利用率這一概念，即理論用料所占實(shí)際用料的百分比。首先針對(duì)表1，我們可以求出完成這項(xiàng)任務(wù)所需要的理論用料數(shù)目(即所采用的原材料數(shù)目)，建立數(shù)學(xué)表達(dá)式為：其中為每種型號(hào)零件要求的長(zhǎng)度，為每種型號(hào)零件所要求的數(shù)量，。代入表1中相關(guān)數(shù)據(jù)進(jìn)行計(jì)算可以得到理論上需要采用的原材料數(shù)目為塊，由于實(shí)際采用原材料的數(shù)目為塊，所以可得完成任務(wù)后的材料利用率為：，可知利用率相對(duì)較高，也說(shuō)明了此模型的可用性。為方便查看，將所得到的結(jié)果做成如下表格： 表5 求得完成任務(wù)的最終結(jié)果原材料總數(shù)823塊采用下料方式數(shù)87種產(chǎn)生廢

26、料長(zhǎng)度8057mm材料利用率96.80%對(duì)于二維下料問(wèn)題，下料方式要同時(shí)滿足零件長(zhǎng)、寬方面的要求，所以要遠(yuǎn)比一維下料問(wèn)題復(fù)雜。由于二維下料問(wèn)題與一維下料問(wèn)題有一定的相似性，我們嘗試著將二維下料問(wèn)題轉(zhuǎn)化為一維下料問(wèn)題來(lái)解決。1）對(duì)表2所給出的數(shù)據(jù)進(jìn)行分析，可以知道所有需求加工的零件寬度均集中于20mm、30mm、35mm、50mm這四種規(guī)格，對(duì)于這四種規(guī)格的零件進(jìn)行集中處理，原材料的長(zhǎng)度為3000mm，寬度為100mm，將其看成是寬度分別為20mm、30mm、35mm、50mm且長(zhǎng)度為3000mm的條材。2）為了盡量節(jié)省材料，我們使原材料在寬邊上盡量利用完全，這樣只有幾種寬邊完全利用的組合方式(

27、7種)，分別為：5050，503020， 30302020，353530，2020202020，453520，602020。我們把零件按寬邊的規(guī)格分為6類(lèi)(20，30，35，45，50，60)，由于所給數(shù)據(jù)中只有一種型號(hào)的零件寬度為45mm，也只有一種型號(hào)的零件寬度為60mm，因此在總材料損耗最小的前提下，可以對(duì)這兩個(gè)型號(hào)的零件進(jìn)行單獨(dú)處理。由上分析可知每一類(lèi)零件都可按模型一的處理一維下料問(wèn)題的方式找到最優(yōu)的方案，然后再把它們按上述的幾種方式進(jìn)行優(yōu)化組合，最后再對(duì)優(yōu)化組合剩余的部分進(jìn)行考慮。組合方式例子如圖2所示：圖2組合方式為50-30-20的下料方式示意圖 3）建立如一維下料問(wèn)題的數(shù)學(xué)模型

28、，現(xiàn)假設(shè)有k種不同的下料方式，再根據(jù)每種零件的需求量，可求得每種零件應(yīng)用的次數(shù)，這樣采用第一種下料方式生產(chǎn)的第一種零件的個(gè)數(shù)為個(gè)，同理可知，表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，則采用第k種下料方式所能得到的第j種零件的數(shù)量表示為，為更好地表示這個(gè)對(duì)應(yīng)關(guān)系，建立如下對(duì)應(yīng)關(guān)系矩陣：則使用k種不同的下料方式所使用的原材料的數(shù)目為，同樣用矩陣的方式來(lái)表示，則有所需原材料數(shù)目為：由于我們將問(wèn)題二轉(zhuǎn)化為了一維下料問(wèn)題，所以采用模型一的建模方式，將原材料分為6種寬度規(guī)格的條材，同樣以每種寬度規(guī)格的原材料總損耗最少為目標(biāo)，首先計(jì)算每種寬度每種下料方式產(chǎn)生的余料長(zhǎng)度，然后進(jìn)行組合。故每種下料方式應(yīng)用于每個(gè)

29、原材料上所剩的余料表達(dá)式為： ，其中 。則建立每種寬度原材料總損耗最少的目標(biāo)函數(shù)為： ()其中表示第種下料方式所消耗的原材料數(shù)目，表示第種下料方式所得余料。又為方便企業(yè)加工生產(chǎn)，減少不必要的更換下料方式所產(chǎn)生的麻煩，企業(yè)希望所采用的下料方式盡可能少，因此建立第二個(gè)目標(biāo)函數(shù)：1)由于所要生產(chǎn)的每種型號(hào)的零件數(shù)量題中已經(jīng)給定，故有限制條件： ()其中，表示第種下料方式可生產(chǎn)第j種零件的數(shù)量，表示第種下料方式所消耗的原材料數(shù)目，表示第種零件所需要生產(chǎn)的數(shù)量，。2)由于題目中所給出的各個(gè)編號(hào)的零件都有給定的長(zhǎng)度，且原材料長(zhǎng)度已定，故還要考慮原材料長(zhǎng)度對(duì)下料方式的限制，即對(duì)于任意一種下料方式，所得到的零

30、件總長(zhǎng)度與鋸縫總長(zhǎng)度之和要小于等于每根原材料的總長(zhǎng)度，同時(shí)還要考慮對(duì)于每一種下料方式的廢料長(zhǎng)度要小于零件的最小長(zhǎng)度，由題中所給數(shù)據(jù)可知，需要生產(chǎn)的零件長(zhǎng)度最小為，故此約束表達(dá)式為：其中為每個(gè)編號(hào)對(duì)應(yīng)的零件長(zhǎng)度。3)因?yàn)樗枇慵纳a(chǎn)有些型號(hào)有時(shí)間的限制，相應(yīng)編號(hào)的零件必須在規(guī)定的時(shí)間4天內(nèi)生產(chǎn)完成，要求4天完成的零件編號(hào)為：，共有10種零件，為方便下文敘述，我們將4天內(nèi)需要完成的零件編號(hào)建立集合，即為了在最短時(shí)間內(nèi)完成所有零件生產(chǎn)的任務(wù)，在滿足該企業(yè)每天最大下料能力20塊的生產(chǎn)能力條件下，我們優(yōu)先考慮有時(shí)間限制的零件進(jìn)行生產(chǎn)，對(duì)此建立約束表達(dá)式為：其中表示第種下料方式中所切割的第種零件數(shù)占這種

31、下料方式中所切割的零件4天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此表示4天內(nèi)完成零件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能力要求，上述表達(dá)式所計(jì)算出采用的原材料總數(shù)要小于等于，另外若，則表示第種下料方式中沒(méi)有切割到集合中的零件。綜上所述，針對(duì)本文二維下料問(wèn)題建立如下數(shù)學(xué)模型：目標(biāo)函數(shù)其中其中約束條件對(duì)于該問(wèn)題，首先考慮在滿足時(shí)間需求的情況下，各種寬度的條材總損失最少的情況，然后盡量使得總的下料方式數(shù)目最少，由于本文問(wèn)題的特殊性，還需要考慮個(gè)別標(biāo)號(hào)的零件在4天內(nèi)完成。故先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將4天內(nèi)需要完成的任務(wù)篩選出來(lái)，優(yōu)先處理后再進(jìn)行其他標(biāo)號(hào)零件的加工。將集合中需要在4天內(nèi)完成的零件進(jìn)行優(yōu)先處理，通過(guò)

32、對(duì)這些數(shù)據(jù)的分析，有7種型號(hào)的零件(共需722個(gè))需要采用寬度為30mm的條材，有2種型號(hào)的零件(共需60個(gè))需要寬度為20mm的條材，有1種型號(hào)的零件共需12個(gè)需要寬度為50mm的條材。然后利用lingo軟件編程，運(yùn)行程序得到的這一批寬度不同的零件生產(chǎn)結(jié)果，然后再利用matlab程序?qū)λ冕槍?duì)各種寬度條材的切割方式進(jìn)行調(diào)整，在滿足不同寬度的條材總損失最小的前提下，計(jì)算出集合中各型號(hào)零件需要寬度為30mm的條材為157根，需要寬度為50mm的條材6根，考慮寬度完全利用的組合方式30302020、5050，也應(yīng)該需要與寬度為30mm相同數(shù)目的寬度為20mm的條材進(jìn)行組合，需要但是組合之后會(huì)發(fā)現(xiàn)最

33、后需要原材料數(shù)目為：157/2+381.5根，這不滿足約束條件即不在生產(chǎn)能力的許可范圍內(nèi)，所以必須更改組合方式。通過(guò)結(jié)合計(jì)算機(jī)進(jìn)行試算，將寬度為30mm的條材取出130根進(jìn)行30302020寬度完全利用的組合方式，可知此種組合需要原材料的數(shù)目為130/265根，其余27根進(jìn)行303030的組合方式，需要27/39根原材料，對(duì)6根寬度為50mm的條材進(jìn)行5050的組合方式，需要原材料6/23根，所有組合完成后可知4天內(nèi)共需要原材料65+9+377根，每種寬度條材的切割方式如下： 1)寬度為20mm的條材切割方式表6 寬度為20mm的條材切割方式切割方式零件長(zhǎng)度(mm)及個(gè)數(shù)余料(mm)條材數(shù)(根

34、)1488(6)7232795(1) 1055(2)9513795(3) 590(1)25114795(3) 488(1)12725184(16)5666275(10)250357420(7)6058578(5)11049665(4) 184(12) 275(3)1152合計(jì)1066130如表6可知，寬度為20mm的條材共有10種切割方式，在有時(shí)間限制的條件下，需要寬度為20mm的條材130根，總共剩余余料為1066mm。2)寬度為30mm的條材切割方式。表7 寬度為30mm的條材切割方式切割方式零件長(zhǎng)度(mm)及個(gè)數(shù)余料(mm)所需數(shù)量(根)1582(5)90992

35、633(2) 582(1) 1105(1)4713633(4) 328(1)14094633(4) 434(1)34135690(4)24036732(4)72177847(2) 328(3) 290(1)3218847(2) 434(1)2569893(3) 290(1)318合計(jì)711130如表7可知，寬度為30mm的條材共有9種切割方式，在有時(shí)間限制的條件下，需要寬度為30mm的條材130根，總共剩余余料為711mm。3)寬度為50mm的條材切割方式。表8 寬度為50mm的條材切割方式切割方式零件長(zhǎng)度(mm)及個(gè)數(shù)余料(mm)所需數(shù)量(根)11046(2) 540(1) 313(1)55

36、6如表8可知，寬度為50mm的條材共有1種切割方式，在有時(shí)間限制的條件下，需要寬度為50mm的條材6根，剩余余料為55mm。4)綜上，可知4天內(nèi)集合中零件生產(chǎn)所對(duì)應(yīng)各種寬度條材的組合方式，以及最終的下料方式和原材料數(shù)，組合結(jié)果如下表：表9 4天內(nèi)原材料的下料方式下料方式組合方式所需原材料（塊）130(1)30(1)20(9)20(9)30230(1)30(1)20(6)20(6)17330(9)30(9)20(8)20(7)4430(8)30(8)20(5)20(5)3530(5)30(5)20(10)20(10)1630(5)30(7)20(7)20(9)1730(1)30(1)20(4)2

37、0(1)2830(4)30(4)20(3)20(3)5930(1)30(4)20(6)20(1)11030(4)30(4)20(3)20(2)11130(6)30(6)30(3)81230(2)30(3)30(6)11350(1)50(1)3合計(jì)77由表9可知，考慮優(yōu)先生產(chǎn)集合中的零件，共有13種下料方式，需要使用原材料的數(shù)量為77塊。接下來(lái)開(kāi)始生產(chǎn)沒(méi)有時(shí)間限制的零件，因?yàn)橛袝r(shí)間限制的零件已經(jīng)生產(chǎn)完畢，故在此不予以考慮，除去生產(chǎn)有時(shí)間限制的零件后，利用lingo程序運(yùn)行得到結(jié)果后，再利用matlab程序?qū)λ孟铝戏绞竭M(jìn)行調(diào)整，結(jié)合6.2.1的解決問(wèn)題的思路，然得到的最終結(jié)果。1)寬度為20mm

38、的條材切割方式表10 寬度為20mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1275（10）184（1）661642405（7）165753414（7）10254455（6）270165455（6） 184（1）86116578（3） 414（3）2417588（5）604168590（1） 184（12）20219590（1） 405（5）385110590（5）509811665（1） 184（12）127112665（4）340613405（4） 275（5）5114882（3）354332151030（2） 882（1）584161030（2） 588（1

39、）3522171030（2） 414（2）1121181030（2） 420（2）1001191030（2） 578（1） 275（1）871201030（2） 665（1） 184（1）911211055（2） 882（1）81221055（2） 882（1）80123420（3）17401合計(jì)48641141由表10可知，寬度為20mm的條材共有23種切割方式，在有時(shí)間限制的條件下，需要寬度為20mm的條材1141根，總共剩余余料為4864mm。2)寬度為30mm的條材切割方式。表11 寬度為30mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1255(11)19

40、5622265(11)85623290(10)100674845(1) 411(5)10015411(7)12316415(7)9537434(4) 265(4)20418434(6) 255(1) 411(1)419434(6) 255(1)141910630(3) 434(1) 411(1)265111630(4) 255(1) 411(1)225112630(4) 411(1)692013745(4)20314830(4) 411(1)992915845(1) 290(7)125116845(1) 830(2) 411(1)84117845(3) 411(1)5434181032(2)

41、411(1)5253191032(2) 434(2)685201032(2) 830(1)1061211032(2) 845(1)913221105(2) 411(1)3792231105(2) 415(1)3752241105(2) 434(1)3565251105(2) 630(1)1603合計(jì)4048321由表11可知，寬度為30mm的條材共有25種切割方式，在有時(shí)間限制的條件下，需要寬度為30mm的條材321根，總共剩余余料為4048mm。3)寬度為35mm的條材切割方式。表12 寬度為35mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1766(2) 600

42、(2)26822600(4)60013600(5)01184766(1) 600(3)43245766(3) 600(1)1022合計(jì)1402127由表12可知，寬度為35mm的條材共有5種切割方式，在有時(shí)間限制的條件下，需要寬度為35mm的條材127根，剩余余料為1402mm。4)寬度為45mm的條材切割方式。表13 寬度為45mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1722(2) 155612722(4)11218合計(jì)166819由表13可知，寬度為45mm的條材共有2種切割方式，在有時(shí)間限制的條件下，需要寬度為45mm的條材19根，剩余余料為1668mm

43、。5)寬度為50mm的條材切割方式。表14 寬度為50mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1155(19)5522714(2) 313(5)7113313(5)143534313(9)18315540(1) 155(14)29016540(5)30017714(4)1441合計(jì)241420由表14可知，寬度為50mm的條材共有7種切割方式，在有時(shí)間限制的條件下，需要寬度為50mm的條材20根，剩余余料為2414mm。6)寬度為60mm的條材切割方式。表15 寬度為60mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1995(3)1

44、519由表15可知，寬度為60mm的條材共有1種切割方式，在有時(shí)間限制的條件下，需要寬度為60mm的條材19根，剩余余料為15mm。7)綜上，可知其余零件生產(chǎn)所對(duì)應(yīng)各種寬度條材的組合方式，以及最終的下料方式和原材料數(shù)，組合結(jié)果如下表：表16其余零件生產(chǎn)原材料的下料方式下料方式組合方式所需原材料（塊）160(1)20(15)20(15)19245(2)35(3)20(15)18345(1)35(2)20(6)1435(3)35(3)30(1)50535(1)35(5)30(23)2635(4)35(4)30(22)2750(2)50(3)3850(1)50(2)2950(2)50(2)31050

45、(4)50(5)11150(6)50(7)11230(20)30(20)20(10)20(10)11320(1)20(1)30(2)30(3)621420(3)20(12)30(3)30(19)51530(1)30(9)20(4)20(5)91630(1)30(6)20(4)20(4)31730(13)30(18)20(7)20(7)31830(21)30(25)20(10)20(10)31930(14)30(24)20(1)20(1)52030(12)30(14)20(2)20(2)202130(4)30(5)20(11)20(12)12230(7)30(8)20(8)20(9)12330(

46、10)30(11)20(4)20(13)12430(15)30(16)20(17)20(18)12530(14)30(14)20(5)20(16)22630(17)30(17)20(2)20(2)172720(1)20(1)20(1)20(1)20(1)62820(19)20(20)20(21)20(22)20(23)12920(2)20(14)20(14)20(15)20(15)13020(14)20(14)20(14)20(14)20(14)663120(7)20(7)20(7)20(7)20(7)20(7)823220(10)20(10)20(10)20(10)20(10)18合計(jì)410

47、由表16可知，考慮優(yōu)先生產(chǎn)集合中的零件，共有32種下料方式，需要使用原材料的數(shù)量為410塊。6綜上可知，完成所有零件的生產(chǎn)，要采用種下料方式，且共需要塊原材料。通過(guò)對(duì)本文中的一維下料問(wèn)題建立數(shù)學(xué)模型，并結(jié)合lingo程序計(jì)算，得到了完成任務(wù)的滿意結(jié)果。為進(jìn)一步驗(yàn)證模型的結(jié)果，提出利用率這一概念，即理論用料所占實(shí)際用料的百分比。首先針對(duì)表1，我們可以求出完成這項(xiàng)任務(wù)所需要的理論用料數(shù)目(即所采用的原材料數(shù)目)，建立數(shù)學(xué)表達(dá)式為：其中為每種型號(hào)零件要求的長(zhǎng)度，為每種型號(hào)零件所要求的數(shù)量，。代入表1中相關(guān)數(shù)據(jù)進(jìn)行計(jì)算可以得到理論上需要采用的原材料數(shù)目為塊，由于實(shí)際采用原材料的數(shù)目為塊，所以可得完成任

48、務(wù)后的材料利用率為：，可知利用率相對(duì)較高，也說(shuō)明了此模型的可用性。為方便查看，將所得到的結(jié)果做成如下表格： 表17 求得完成任務(wù)的最終結(jié)果原材料總數(shù)487塊采用下料方式數(shù)45種材料利用率92%、改進(jìn)與推廣評(píng)價(jià)1）對(duì)于問(wèn)題一所建立的多目標(biāo)整數(shù)規(guī)劃模型，很準(zhǔn)確的概括了該問(wèn)題的所有約束和目標(biāo)，從理論上講是一個(gè)很?chē)?yán)謹(jǐn)?shù)哪Ｐ?。但是?duì)于這一模型的求解卻是非常困難的，必須尋找比較好的算法支持它，而文中我們提出優(yōu)化方法就很好的支持了這個(gè)模型，并且有很好的求解效果，材料的利用率很高（廢料很少），計(jì)算速度快，結(jié)果很好。此模型和算法適應(yīng)能力強(qiáng)，求解結(jié)果好，有很強(qiáng)的普遍性和實(shí)用性。2）對(duì)于問(wèn)題二所建立的分類(lèi)逐層分析模

49、型較好的解決了問(wèn)題二，此方法根據(jù)具體問(wèn)題的具體特點(diǎn)進(jìn)行分析，找出針對(duì)性的解決方案，這樣我們同樣得到較好的結(jié)果，材料利用率高，計(jì)算速度快；但此模型有一定的缺陷，沒(méi)有很強(qiáng)的普遍性，為適應(yīng)某一特殊問(wèn)題都需要具體的分析計(jì)算，尋求針對(duì)性的方案。改進(jìn)從本文的兩個(gè)問(wèn)題的解決可看出，針對(duì)本問(wèn)題將多目標(biāo)整數(shù)規(guī)劃模型分解為多層整數(shù)線性規(guī)劃模型和分支定界的優(yōu)化方法是十分有效的。它在大大降低計(jì)算復(fù)雜度的同時(shí)保持了很高的材料利用率和尚可接受的下料方式數(shù)。但是簡(jiǎn)化后的模型與算法在計(jì)算結(jié)果穩(wěn)定性方面未來(lái)得及分析證明，也就是說(shuō)此模型用于其它類(lèi)似問(wèn)題是否還可以得到和本題兩個(gè)問(wèn)題同樣高的利用率沒(méi)有理論基礎(chǔ)。改進(jìn)的模型可以在證明或增加模型穩(wěn)定性方面作研究。推廣前人的研究以及上述算法的評(píng)價(jià)說(shuō)明，現(xiàn)有的單一的模型與算法都有自身的缺陷，如常規(guī)的整數(shù)線性規(guī)劃求解法計(jì)算結(jié)果最優(yōu)，但是NPC問(wèn)題，隨著問(wèn)題規(guī)模的增加，計(jì)算量和存儲(chǔ)空間的會(huì)產(chǎn)生組合爆炸；神經(jīng)網(wǎng)絡(luò)法、模擬退火法以及蒙特卡羅法初始收斂速度快，特別適用于優(yōu)化目標(biāo)和約束條件復(fù)雜的問(wèn)題，但是為求出精確解付出的機(jī)時(shí)卻特別大。因此接下來(lái)可以考慮將蒙特卡羅模擬與我們的方法結(jié)合，以期得到一定的穩(wěn)定性與精確度。本模型在前人研究的