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

1、實(shí)用下料問(wèn)題優(yōu)化模型摘要關(guān)鍵字：整數(shù)規(guī)劃模型多目標(biāo)決策優(yōu)化NP問(wèn)題下料方案分支定界法1.問(wèn)題的重述下料問(wèn)題（cuttingstockproblem）是把相同形狀的一些原材料分割加工成若干個(gè)不同規(guī)格大小的零件的問(wèn)題，此類問(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)度為L(zhǎng),寬度為W,現(xiàn)在需要將一批這種長(zhǎng)方形原料分割成m種規(guī)格的零件，所有零件的厚度均與原材料一致，但長(zhǎng)度和寬度分別為（li,Wi）,，（lm,Wm）,其中Wi<liML,Wi<W,i=1,，m.m種零件

2、的需求量分別為”,，nm.下料時(shí)，零件的邊必須分別和原材料的邊平行。這類問(wèn)題在工程上通常簡(jiǎn)稱為二維下料問(wèn)題。特別當(dāng)所有零件的寬度均與原材料相等，即必=W,i=1,，m,則問(wèn)題稱為一維下料問(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ù)也盡量地

3、小.就某企業(yè)考慮下面兩個(gè)問(wèn)題：1.建立一維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型，并用此模型求解下列問(wèn)題，制定出在生產(chǎn)能力容許的條件下滿足需求的下料方案，同時(shí)求出等額完成任務(wù)所需的原材料數(shù)，所采用的下料方式數(shù)和廢料總長(zhǎng)度.單一原材料的長(zhǎng)度為3000mm,需要完成一項(xiàng)有53種不同長(zhǎng)度零彳的下料任務(wù).具體數(shù)據(jù)見(jiàn)表一，其中l(wèi)i為需求零件的長(zhǎng)度，小為需求零件的數(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,4眼求不遲于6天完成的零件標(biāo)號(hào)（i）為：4,11,24,29,

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

5、84720845ni8248828301638ili21830227952376624745257302671927714286952964530630ni308443418449030ili31610326003359034588355823657837540384883935540343ni3021210848219683245242ili41320425154341444411454054632847313482904927550265ni88860136468286602286ili512555218453155ni19257242.建立二維單一原材料實(shí)用下料問(wèn)題的數(shù)學(xué)模型，并用此模型

6、求解下列問(wèn)題.制定出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的下料方案，同時(shí)求出等額完成任務(wù)所需的原材料塊數(shù)和所需下料方式數(shù).這個(gè)問(wèn)題的單一原材料的長(zhǎng)度為3000mm,寬度為100mm,需要完成一項(xiàng)有43種不同長(zhǎng)度和寬度零件的下料任務(wù).具體數(shù)據(jù)見(jiàn)表二，其中l(wèi)i,Wi,ni分別為需求零件的長(zhǎng)度、寬度和數(shù)量.切割時(shí)的鋸縫可以是直的也可以是彎的，切割所引起的鋸縫損耗忽略不計(jì).據(jù)估計(jì)，該企業(yè)每天最大下料能力是20塊要求在4天內(nèi)完成的零件標(biāo)號(hào)(i)為:3,7,9,12,15,18,20,25,28,36.表2需求材料的數(shù)據(jù)單位：mmi12345678910li1105105510461032103099589

7、3882847845w30205030206030203030ni2461224245724100120108i11121314151617181920li830795766745732722714690665633w30203530304550302030A904012126874101227090i21222324252627282930li630600590588582578540488455434w30352020302050202030n90612508208249624622016292i31323334353637383940li4204154144114053283132902

8、75265w20302030203050302030ni402440180536121286862002686i414243li255184155w302050n692357522 .問(wèn)題的分析本文要解決的是一個(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)

9、能力容許的條件下，在規(guī)定的時(shí)間需求內(nèi)，以最少數(shù)量的原材料，盡可能按時(shí)完成需求任務(wù)，同時(shí)下料方式數(shù)也盡量地小。為順利解決這一問(wèn)題，我們先從最基本的單目標(biāo)決策問(wèn)題人手，以材料損耗最少為目標(biāo)，由于個(gè)別零件的生產(chǎn)有時(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é)果。具體流

10、程圖如下：圖1總體流程圖原材料損耗最少3 .模型的假設(shè)1 .假設(shè)每次切割都準(zhǔn)確無(wú)誤。2,每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制，在未完成需求任務(wù)前，每天下料的數(shù)量等于最大下料能力。3,模型一中每切得一個(gè)規(guī)格的零件需要（L+5）mm的原材料。4,除最后一天外，其余每天均達(dá)到最大下料能力。5,除了要求在規(guī)定時(shí)間內(nèi)完成所需零件外，不要求其余零件加工排列順序。6,模型二中，切割所引起的鋸縫損耗忽略不計(jì)。4 .符號(hào)說(shuō)明符號(hào)符號(hào)解釋說(shuō)明n需求零件的數(shù)量li需求零件的長(zhǎng)度Wi,需求零件的寬度a0ji第i種下料方式可生產(chǎn)第j種零件的數(shù)量x不同的下料方式所使用的原材料的數(shù)目Ci每種下料方式應(yīng)用于每個(gè)原材料上所剩的

11、余料m使用下料方式的種類nj第j種零件所需要生產(chǎn)的數(shù)量L原材料長(zhǎng)度，為3000M14天內(nèi)需要完成的零件編號(hào)建立集合m26天內(nèi)需要完成的零件編號(hào)建立集合Ni理論所采用的原材料數(shù)目N2實(shí)際采用原材料的數(shù)目d完成任務(wù)后的材料利用率M3問(wèn)題二中4天內(nèi)需要完成的零件編號(hào)建立集合5 .一維下料問(wèn)題對(duì)于一維優(yōu)化下料問(wèn)題，屬于整數(shù)規(guī)劃問(wèn)題，從計(jì)算復(fù)雜性理論分析，該問(wèn)題屬于NP難題,即無(wú)法在多項(xiàng)式時(shí)間（在計(jì)算復(fù)雜度理論中，指的是一個(gè)問(wèn)題的計(jì)算時(shí)問(wèn)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)

12、求解其相應(yīng)的線性問(wèn)題，然后用計(jì)算機(jī)程序進(jìn)行求解。首先考慮在滿足時(shí)間需求的情況下，材料總損失最少的情況，然后盡量使得總的下料方式數(shù)目最少，故這里要尋找到所有下料方式中利用率最高的方式，同時(shí)在滿足生產(chǎn)力要求的情況下進(jìn)行適當(dāng)調(diào)整，采用盡可能少的下料方式，這樣便可以得到一維下料問(wèn)題的優(yōu)化結(jié)果。5.1 模型一的建立根據(jù)題意，現(xiàn)有數(shù)量充足的長(zhǎng)度為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)先

13、處理后再進(jìn)行其他標(biāo)號(hào)零件的加工。按照前面的分析，我們現(xiàn)假設(shè)有m種不同的下料方式，再根據(jù)每種零件的需求量，可求得每種零件應(yīng)用的次數(shù)，這樣采用第一種下料方式生產(chǎn)的第一種零件的個(gè)數(shù)為.個(gè)，同理可知，aj表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，則采用第m種下料方式所能得到的第j種零件的數(shù)量表示為ajm,為更好地表示這個(gè)對(duì)應(yīng)關(guān)系，建立如下對(duì)應(yīng)關(guān)系矩陣：alla12alma21a22a2mA=:如ajiajm_則使用m種不同的下料方式所使用的原材料的數(shù)目為x,同樣用矩陣的方式來(lái)表示，則有所需原材料數(shù)目為：TX=X1,x2,x3,Xm5.1.1 建立目標(biāo)函數(shù)由于我們以原材料總損耗最少為目標(biāo)，所以首先計(jì)算每

14、種下料方式產(chǎn)生的余料長(zhǎng)度，由于在每個(gè)切割點(diǎn)處由于鋸縫所產(chǎn)生的損耗為5mm.故每種下料方式應(yīng)用于每個(gè)原材料上所剩的余料表達(dá)式為：Ci=L-|_aimli5a2mI25ajmlj.55則建立原材料總損耗最少的目標(biāo)函數(shù)為：mmin(二gx)(i=1,2,m)i1其中Xi表示第i種下料方式所消耗的原材料數(shù)目，Ci表示第i種下料方式所得余料。又為方便企業(yè)加工生產(chǎn)，減少不必要的更換下料方式所產(chǎn)生的麻煩，企業(yè)希望所采用的下料方式盡可能少，因此建立第二個(gè)目標(biāo)函數(shù)：一一二-7+minmmZ5.1.2 建立約束條件1)由于所要生產(chǎn)的每種型號(hào)的零件數(shù)量題中已經(jīng)給定，故有限制條件：m'ajiXi=nj(aji

15、,xZ)其中，aj表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，為表示第i種下料方式所消耗的原材料數(shù)目，nj表示第j種零件所需要生產(chǎn)的數(shù)量，j=1,2,，53。2）由于題目中所給出的各個(gè)編號(hào)的零件都有給定的長(zhǎng)度，且原材料長(zhǎng)度已定，故在考慮了鋸縫后，還要考慮原材料長(zhǎng)度L=3000mm對(duì)下料方式的限制，即對(duì)于任意一種下料方式，所得到的零件總長(zhǎng)度與鋸縫總長(zhǎng)度之和要小于等于每根原材料的總長(zhǎng)度L=3000mm,同時(shí)還要考慮對(duì)于每一種下料方式的廢料長(zhǎng)度要小于零件的最小長(zhǎng)度，由題中所給數(shù)據(jù)可知，需要生產(chǎn)的零件長(zhǎng)度最小為155mm,故此約束表達(dá)式為：532845交ajilj5-5<3000j=i其中l(wèi)j為每

16、個(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)為:5,7,9,12,15,18,20,25,28,36,48,共有11種零件；要求6天內(nèi)完成的零件編號(hào)為：4,11,24,29,32,38,40,46,50,共有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)建立集合M1,即M1=5,7,9,12,15,18,20,25,28,36

17、,48,同理將6天內(nèi)需要完成的零件編號(hào)建立集合M2,即M2=5,7,9,12,15,18,20,25,28,36,48,41124,29,32,38,40,46,50,對(duì)此建立約束條件表達(dá)式為：=1=ajiXiZZ<100X4ui£aji<uJ20zzjTiajiXi20<1006ZajijVJ其中Z1以表示第i種下料方式中所切割的第j種零件數(shù)占這種下料方式中iajifajiX.二ajij1表示4天內(nèi)完成零11所切割白零件4天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此££j二i件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能力要求，上述表達(dá)式所計(jì)算出采11用的原材

18、料總數(shù)要小于等于100父4,另外若£aji=0,則表示第i種下料方式中沒(méi)j1a；x；有切割到集合M1中的零件；同理，£擊，表小第i種下料萬(wàn)式中所切割的第j種i%，ajij1零件數(shù)占這種下料方式中所切割的零件6天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此、20zj1a：x：.、一.-,、一.za表示6天內(nèi)完成零件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能izajihJ力要求，上述表達(dá)式所計(jì)算出采用的原材料總數(shù)要小于等于100M6,另外若20Zaji=0,則表示第i種下料方式中沒(méi)有切割到集合M2中的零件。j15.1.3最終模型的建立綜上所述，針對(duì)本文一維下料問(wèn)題建立如下數(shù)學(xué)模型：目標(biāo)函數(shù)mm

19、in”(cixi)i1minm約束條件m工ajiXii4532845Mzaji(lj+5)-5<3000s.t.11zj1ajiXiiZajij4J<100420zj1ajiX20Zajij4J十<1006j=1,2,53i=1,2,m5.2模型一的求解對(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)零件的加工。5.2.1 優(yōu)先處理零件將集合M1和集合M2中的零件進(jìn)行優(yōu)先處理，利

20、用lingo軟件編程，先不考慮下料方式的數(shù)目對(duì)結(jié)果的影響，在滿足原材料總損失最小的前提下再調(diào)整下料方式的數(shù)目，同時(shí)在保證生產(chǎn)集合M1和集合M2中的零件的基礎(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)1843733:600(4)265二45514645600265015645(4)2651352

21、16750(4)-517：1105(2)600(1)155(1)25181105(2)645(1)1352911477(1)645(1)600(1)255(1)131101477(2)411811:290(2)265(8)255(1)0112735(2)290(4)355(1)01131290(10)552814578(1)1105(2)184(1)18115P578(5)P90116847(1)730(1)695(2)13217P730(4)P65718343(6)265(1)630(1)16119P847(1)730(2)343(1)328(1)r2120847(3)414(1)35121

22、P348540r241122882(1)488(4)146123882265r7410024p030(1)1477(1)414(1)661251030(1)577(1)328(1)265(2)515(1):31261030(2)645(1)265(1)152271030(2)57734341281057(2)265610(1)11291182(2)600263301232(2)26525562311313(2)32899232343265168061合計(jì)1235273由表3可知，優(yōu)先生產(chǎn)有時(shí)間限制的零件，則共有32種下料方式，所產(chǎn)生的廢料為1235mm,共需要原材料的數(shù)量為273塊。5.2.2

23、其余零件處理接下來(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)581433313(9)3144411(5)184(4)155(1)1935411(7)71256795(1)515(4)1857320(8)155(2)1898355(5)184(4)11259

24、355(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)414(1)110521630(4)355(1)612922714(4)11123719(2)588(2)355(1)110924719(4)49925766(3)588(1)16526795540(1)222527830

25、(3)275(1)118228830313(1)83029847(3)414(1)213330893(1)515(3)414(1)r13831975(2)588(1)414(1)138321032893(1)P3131331032(2)795(1)110341046(2)893(1)r2153351177(1)830190361177(1)893(1)830(1)r11371177(2)155(4)16381177355(1)275(1)r226391177(2)610(1)116401217(2)540(1)r311411285(2)414(1)1107421285(2)313(1)2922

26、0431532(1)411(3)1168441532(1)255(6)37128451532(1)405(2)255(2)1108461532405275(1)255(1)1145471532(1)405(3)44282481532(1)588(2)20134491680(1)588(2)213112501680(1)588(1)610(1)172P511680(1)411(3)P135521743(1)1217(1)283r531743(1)582(2)139541743(1)893(1)155(2)119155554016822合計(jì)550如表4所示，除去所有有時(shí)間限制的零件，以及為了調(diào)整其

27、余料與有時(shí)間限制的零件一同優(yōu)先生產(chǎn)的零件之外，剩下的沒(méi)有時(shí)間限制的零件生產(chǎn)共需要55種下料方式，所產(chǎn)生的廢料總長(zhǎng)度為6822mm,且需要550塊原材料。5.2.3完成所有零件綜上可知，完成所有零件的生產(chǎn)，要采用32+55=87種下料方式，且共需要273+550=823塊原材料，所產(chǎn)生白余料總長(zhǎng)度為：1235+6822=8057mm。5.3模型一的結(jié)果分析通過(guò)對(duì)本文中的一維下料問(wèn)題建立數(shù)學(xué)模型，并結(jié)合lingo程序計(jì)算，得到了完成任務(wù)的滿意結(jié)果。為進(jìn)一步驗(yàn)證模型的結(jié)果，提出利用率這一概念，即理論用料所占實(shí)際用料的百分比。首先針對(duì)表1,我們可以求出完成這項(xiàng)任務(wù)所需要的理論用料數(shù)目（即所采用的原材料

28、數(shù)目），建立數(shù)學(xué)表達(dá)式為:Ni53=£jilj*nj3000其中l(wèi)j為每種型號(hào)零件要求的長(zhǎng)度,nj為每種型號(hào)零件所要求的數(shù)量,j=1,2,53。代入表1中相關(guān)數(shù)據(jù)進(jìn)行計(jì)算可以得到理論上需要采用的原材料數(shù)目為Ni=797塊，由于實(shí)際采用原材料的數(shù)目為=823塊，所以可得完成任務(wù)后的材料利用率為：7=797><100%=96.8%,可知利用率相對(duì)較高，也說(shuō)明了此模型的可用性。為823方便查看，將所得到的結(jié)果做成如下表格：表5求得完成任務(wù)的最終結(jié)果原材料總數(shù)823塊米/料方式數(shù)87種產(chǎn)生廢料長(zhǎng)度8057mm96.80%材料利用率6.二維下料問(wèn)題對(duì)于二維下料問(wèn)題，下料方式要同時(shí)滿

29、足零件長(zhǎng)、寬方面的要求，所以要遠(yuǎn)比一維下料問(wèn)題復(fù)雜。由于二維下料問(wèn)題與一維下料問(wèn)題有一定的相似性，我們嘗試著將二維下料問(wèn)題轉(zhuǎn)化為一維下料問(wèn)題來(lái)解決。6.1模型二的建立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é)省材料，我們使原材料在寬邊上盡量利用完全，這樣只有幾種寬邊完全利用的組合方式（7種），分別為：50-50,50-30-20,30302

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

31、，可求得每種零件應(yīng)用的次數(shù)，這樣采用第一種下料方式生產(chǎn)的第一種零件的個(gè)數(shù)為加個(gè)，同理可知，地表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，則采用第k種下料方式所能得到的第j種零件的數(shù)量表示為ajk,為更好地表示這個(gè)對(duì)應(yīng)關(guān)系，建立如下對(duì)應(yīng)美系矩陣：a11a12a1ka21a22a2kB=sa*aj1aj1ajk則使用k種不同的下料方式所使用的原材料的數(shù)目為為，同樣用矩陣的方式來(lái)表示，則有所需原材料數(shù)目為：TX=X1>x2,X3>>xki6.1.1建立目標(biāo)函數(shù)由于我們將問(wèn)題二轉(zhuǎn)化為了一維下料問(wèn)題，所以采用模型一的建模方式，將原材料分為6種寬度規(guī)格的條材，同樣以每種寬度規(guī)格的原材料總損

32、耗最少為目標(biāo)，首先計(jì)算每種寬度每種下料方式產(chǎn)生的余料長(zhǎng)度，然后進(jìn)行組合。故每種下料方式應(yīng)用于每個(gè)原材料上所剩的余料表達(dá)式為：Cib=L(aikli+a2kI2+ajklj),其中b=20,30,35,45,50,60。則建立每種寬度原材料總損耗最少的目標(biāo)函數(shù)為：kmincibx)(i=1,2,k;b=20,30,35,45,50,60.)i1其中Xi表示第i種下料方式所消耗的原材料數(shù)目，金表示第i種下料方式所得余料。又為方便企業(yè)加工生產(chǎn)，減少不必要的更換下料方式所產(chǎn)生的麻煩，企業(yè)希望所采用的下料方式盡可能少，因此建立第二個(gè)目標(biāo)函數(shù)：minkkZ6.1.2建立約束條件1)由于所要生產(chǎn)的每種型號(hào)的

33、零件數(shù)量題中已經(jīng)給定，故有限制條件：k'、ajx二nj問(wèn)，xZ)i1其中，aj表示第i種下料方式可生產(chǎn)第j種零件的數(shù)量，Xi表示第i種下料方式所消耗的原材料數(shù)目，7表示第j種零件所需要生產(chǎn)的數(shù)量，j=1,2，,43。2)由于題目中所給出的各個(gè)編號(hào)的零件都有給定的長(zhǎng)度，且原材料長(zhǎng)度已定，故還要考慮原材料長(zhǎng)度L=3000mm對(duì)下料方式的限制，即對(duì)于任意一種下料方式，所得到的零件總長(zhǎng)度與鋸縫總長(zhǎng)度之和要小于等于每根原材料的總長(zhǎng)度L=3000mm,同時(shí)還要考慮對(duì)于每一種下料方式的廢料長(zhǎng)度要小于零件的最小長(zhǎng)度，由題中所給數(shù)據(jù)可知，需要生產(chǎn)的零件長(zhǎng)度最小為155mm,故此約束表達(dá)式為：532845

34、ajilj<3000j4其中l(wèi)j為每個(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)為：3,7,9,12,15,18,20,25,28,36,共有10種零件，為方便下文敘述，我們將4天內(nèi)需要完成的零件編號(hào)建立集合M3,即M3=13,7,9,12,15,18,20,25,28,36）為了在最短時(shí)間內(nèi)完成所有零件生產(chǎn)的任務(wù)，在滿足該企業(yè)每天最大下料能力20塊的生產(chǎn)能力條件下，我們優(yōu)先考慮有時(shí)間限制的零件進(jìn)行生產(chǎn)，對(duì)此建立約束表達(dá)式為：0-aN£工前d£20父4及i£aji<

35、;jmJ一.a；x；其中£三表示第i種下料方式中所切割的第j種零件數(shù)占這種下料方式中iajiajiX70ajij1表示4天內(nèi)完成零jm10所切割白零件4天內(nèi)需要完成零件數(shù)的權(quán)數(shù)，因此ZZj日i件制定零件所用的原材料數(shù)，根據(jù)該企業(yè)的生產(chǎn)能力要求，上述表達(dá)式所計(jì)算出采10用的原材料總數(shù)要小于等于20M4,另外若aaji=0,則表示第i種下料方式中沒(méi)有jw切割到集合M3中的零件。6.1.3最終模型的建立綜上所述，針對(duì)本文二維下料問(wèn)題建立如下數(shù)學(xué)模型：目標(biāo)函數(shù)kmin五g小i）其中i=1,2，k;b=20,30,35,45,50,60.i1約束條件S.t.minkrk工ajiXi=nji其中

36、kZ432845交ajiljM3000j410zzjiiaz10_204aji,Xi-Zj=1,2,43i=1,2,k6.2 模型二的求解對(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)零件的加工。6.2.1 優(yōu)先處理零件將集合M3中需要在4天內(nèi)完成的零件進(jìn)行優(yōu)先處理，通過(guò)對(duì)這些數(shù)據(jù)的分析，有7種型號(hào)的零件（共需722個(gè)）需要采用寬度為30mm的條材，有2種型號(hào)的零件（共需60個(gè)）需要寬度為20m

37、m的條材，有1種型號(hào)的零件共需12個(gè)需要寬度為50mm的條材。然后利用lingo軟件編程，運(yùn)行程序得到的這一批寬度不同的零件生產(chǎn)結(jié)果，然后再利用matlab程序?qū)λ冕槍?duì)各種寬度條材的切割方式進(jìn)行調(diào)整，在滿足不同寬度的條材總損失最小的前提下，計(jì)算出集合M3中各型號(hào)零件需要寬度為30mm的條材為157根，需要寬度為50mm的條材6根，考慮寬度完全利用的組合方式30302020、5050,也應(yīng)該需要與寬度為30mm相同數(shù)目的寬度為20mm的條材進(jìn)行組合，需要但是組合之后會(huì)發(fā)現(xiàn)最后需要原材料數(shù)目為：157/2+3=81.5根，這不滿足約束條件即不在生產(chǎn)能力的許可范圍內(nèi)，所以必須更改組合方式。通過(guò)結(jié)合

38、計(jì)算機(jī)進(jìn)行試算，將寬度為30mm的條材取出130根進(jìn)行30302020寬度完全利用的組合方式，可知此種組合需要原材料的數(shù)目為130/2=65根，其余27根進(jìn)行30-30-30的組合方式，需要27/3=9根原材料，對(duì)6根寬度為50mm的條材進(jìn)行5050的組合方式，需要原材料6/2=3根，所有組合完成后可知4天內(nèi)共需要原材料65+9+3=77根，每種寬度條材的切割方式如下：1）寬度為20mm的條材切割方式表6寬度為20mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）條材數(shù)（根）1488(6)7232795(1)1055(2)9513795590(1)25114795(3)488(1)1

39、2725184(16)5666275(10)2503574206058578(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)90992633(2)582(1)1105(1)4713633(4)328(1)14094633(4)434(1)34135690(4)24036

40、732(4)72177847(2)328(3)290(1)3218847(2)434(1)25:69893(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)556如表8可知，寬度為50mm的條材共有1種切割方式，在有時(shí)間限制的條件下,需要寬度為50mm的條材6根，剩余余料為55mm。4）綜上，可知4天內(nèi)集合M3中零

41、件生產(chǎn)所對(duì)應(yīng)各種寬度條材的組合方式，以及最終的下料方式和原材料數(shù)，組合結(jié)果如下表：表94天內(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)20(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(

42、6)30(6)30(3)81230(2)30(3)30(6)11350(1)50(1)3合計(jì)77由表9可知，考慮優(yōu)先生產(chǎn)集合M3中的零件，共有13種下料方式，需要使用原材料的數(shù)量為77塊。6.2.2其余零件處理接下來(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的條材切割方式表10寬度為20mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1275(10)184(

43、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)385P110590(5)509811665(1)184(12)127112665(4)340r613405(4)275(5)5114882(3)354332151030(2)882(1)58r4161030(2)588(1)3522171030(2)414(2)1121181030(2)420(2)1001191030(2)578(1)275(1)871201

44、030(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)195622265(11)85623290(10)100674845(1)411(5)10015411(7)12316415(7)9537434(4)265(4)

45、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)411(1)5253191032(2)434(2)6852011032(2)830(1)1061211032(2)845(1)9132211105(2)411(1)3792231105(2)

46、415(1)3752241105(2)434(1)3565251105(2)630(1)1603合計(jì)4048321由表11可知，寬度為30mm的條材共有25種切割方式，在有時(shí)間限制的條件下，需要寬度為30mm的條材321根，總共剩余余料為4048mm3）寬度為35mm的條材切割方式。表12寬度為35mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1766(2)600(2)26822600(4)60013:600(5)01184766(1)600(3)432451766(3)600(1)1022合計(jì)1402127由表12可知，寬度為35mm的條材共有5種切割方式，在有時(shí)

47、間限制的條件下，需要寬度為35mm的條材127根，剩余余料為1402mm4）寬度為45mm的條材切割方式。表13寬度為45mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1722(2)155612722(4)11218合計(jì)166819由表13可知，寬度為45mm的條材共有2種切割方式，在有時(shí)間限制的條件下，需要寬度為45mm的條材19根，剩余余料為1668mm5）寬度為50mm的條材切割方式。表14寬度為50mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1155(19)5522714(2)313(5)7113313(5)143534313(

48、9)18315540(1)155(14)290161540(5)30017714(4)1441合計(jì)241420由表14可知，寬度為50mm的條材共有7種切割方式，在有時(shí)間限制的條件下，需要寬度為50mm的條材20根，剩余余料為2414mm6）寬度為60mm的條材切割方式。表15寬度為60mm的條材切割方式切割方式零件長(zhǎng)度（mm）及個(gè)數(shù)余料（mm）所需數(shù)量（根）1995(3)1519由表15可知，寬度為60mm的條材共有1種切割方式，在有時(shí)間限制的條件下，需要寬度為60mm的條材19根，剩余余料為15mm。7）綜上，可知其余零件生產(chǎn)所對(duì)應(yīng)各種寬度條材的組合方式，以及最終的下料方式和原材料數(shù)，組合

49、結(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(4)50(5)11150(6)50(7)11230(20)30(20)20(10)20(10)11320(1)20一30(2)30621420(3)20(12)30(3)30(19)515130(1)30(9)20(4)20(5)91630(1)30(6)20(4)20(4)