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

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

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

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

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

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

7、0830795766745732722714690665633302035303045503020309040121268741012270902122232425262728293063060059058858257854048845543430352020302050202030906125082082496246220162923132333435363738394042041541441140532831329027526520302030203050302030402440180536121286862002686414243255184155302050 69235752本文要解決

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

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

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

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

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

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

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

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

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

17、集合中的零件進行優(yōu)先處理，利用lingo軟件編程，先不考慮下料方式的數(shù)目對結(jié)果的影響，在滿足原材料總損失最小的前提下再調(diào)整下料方式的數(shù)目，同時在保證生產(chǎn)集合和集合中的零件的基礎(chǔ)上，只要在生產(chǎn)能力許可范圍內(nèi)，還可以生產(chǎn)其他對生產(chǎn)時間沒有限制的零件。對此，運行程序得到的這一批零件生產(chǎn)的結(jié)果，然后再利用matlab程序?qū)λ孟铝戏绞竭M行調(diào)整，然后針對個別存在問題的下料方式進行調(diào)解后得到的最終結(jié)果為：表3 優(yōu)先考慮有時間限制零件的處理結(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合計1235273由表3可知，優(yōu)先生產(chǎn)有時間限制的零件，則共有32種下料方式，所產(chǎn)生的廢料為1235mm，共需要原材料的數(shù)量為273塊。接下來開始生產(chǎn)沒有時間限制的零件，因為有時間限制的零件已經(jīng)生產(chǎn)完畢，故在此不予以考慮，除去生產(chǎn)有時間限制的零件后，利用lingo程序運行得到結(jié)果后，再利用matlab程序?qū)λ孟铝戏绞竭M行調(diào)整，然后針對個別存在問題的下料方式進行調(diào)解后得到的最終結(jié)果為： 表4 沒有時間限制零件的處理結(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合計550如表4所示，除去所有有時間限制的零件，以及為了調(diào)整其余料與有時間限制的零件一同優(yōu)先生產(chǎn)的零件之外，剩下的沒有時間限制的零件生產(chǎn)共需要55種下料方式，所產(chǎn)生的廢料總長度為6822mm，且需要550塊原材料。綜上可知，完成所有零件的生產(chǎn)，要采用種下料方式，且共需要塊原材料，所產(chǎn)生的余料總長度為：。通過對本文中的一維下

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

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

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

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

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

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

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

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

33、后需要原材料數(shù)目為：157/2+381.5根，這不滿足約束條件即不在生產(chǎn)能力的許可范圍內(nèi)，所以必須更改組合方式。通過結(jié)合計算機進行試算，將寬度為30mm的條材取出130根進行30302020寬度完全利用的組合方式，可知此種組合需要原材料的數(shù)目為130/265根，其余27根進行303030的組合方式，需要27/39根原材料，對6根寬度為50mm的條材進行5050的組合方式，需要原材料6/23根，所有組合完成后可知4天內(nèi)共需要原材料65+9+377根，每種寬度條材的切割方式如下： 1)寬度為20mm的條材切割方式表6 寬度為20mm的條材切割方式切割方式零件長度(mm)及個數(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合計1066130如表6可知，寬度為20mm的條材共有10種切割方式，在有時間限制的條件下，需要寬度為20mm的條材130根，總共剩余余料為1066mm。2)寬度為30mm的條材切割方式。表7 寬度為30mm的條材切割方式切割方式零件長度(mm)及個數(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合計711130如表7可知，寬度為30mm的條材共有9種切割方式，在有時間限制的條件下，需要寬度為30mm的條材130根，總共剩余余料為711mm。3)寬度為50mm的條材切割方式。表8 寬度為50mm的條材切割方式切割方式零件長度(mm)及個數(shù)余料(mm)所需數(shù)量(根)11046(2) 540(1) 313(1)55

36、6如表8可知，寬度為50mm的條材共有1種切割方式，在有時間限制的條件下，需要寬度為50mm的條材6根，剩余余料為55mm。4)綜上，可知4天內(nèi)集合中零件生產(chǎn)所對應(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合計77由表9可知，考慮優(yōu)先生產(chǎn)集合中的零件，共有13種下料方式，需要使用原材料的數(shù)量為77塊。接下來開始生產(chǎn)沒有時間限制的零件，因為有時間限制的零件已經(jīng)生產(chǎn)完畢，故在此不予以考慮，除去生產(chǎn)有時間限制的零件后，利用lingo程序運行得到結(jié)果后，再利用matlab程序?qū)λ孟铝戏绞竭M行調(diào)整，結(jié)合6.2.1的解決問題的思路，然得到的最終結(jié)果。1)寬度為20mm

38、的條材切割方式表10 寬度為20mm的條材切割方式切割方式零件長度（mm）及個數(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合計48641141由表10可知，寬度為20mm的條材共有23種切割方式，在有時間限制的條件下，需要寬度為20mm的條材1141根，總共剩余余料為4864mm。2)寬度為30mm的條材切割方式。表11 寬度為30mm的條材切割方式切割方式零件長度（mm）及個數(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合計4048321由表11可知，寬度為30mm的條材共有25種切割方式，在有時間限制的條件下，需要寬度為30mm的條材321根，總共剩余余料為4048mm。3)寬度為35mm的條材切割方式。表12 寬度為35mm的條材切割方式切割方式零件長度（mm）及個數(shù)余料（mm）所需數(shù)量（根）1766(2) 600

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

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

44、519由表15可知，寬度為60mm的條材共有1種切割方式，在有時間限制的條件下，需要寬度為60mm的條材19根，剩余余料為15mm。7)綜上，可知其余零件生產(chǎn)所對應(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合計410

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

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

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