最優(yōu)下料問題的數(shù)學模型

1、最優(yōu)下料問題的數(shù)學模型摘要本文通過對兩個問題進行分析，分別建立模型一、模型二。針對模型一，設計程序 貪心算法，通過Matlab編程，得出相應結(jié)果。針對模型二，文中通過將二維問題轉(zhuǎn)換 成為一維問題，引用規(guī)劃模型，做出相應分析。在問題一中，為解決一維下料問題，根據(jù)一維下料問題的特點，建立起由其約束條 件組介而成的規(guī)劃模型，在隨機決策的基礎上利用貪心算法取每個決策中的最優(yōu)值，較 快地獲得問題的最優(yōu)解為：前6天下料方案整和為一個方案比制定4天，6天方案更優(yōu), 且前6天需用原材料根數(shù)為268,利用率為99. 21%, 3天完成：剩余下料方案為需用原 材料根數(shù)為538,利用率為98.92%, 6天完成。（

2、詳見表6-1和附錄表6-2、表6-3）在問題二中，基丁零件長、寬兩個方向上的限制的情況后，根據(jù)問題2中待加工的 零件的寬只集中在50mm, 30mm, 35mm, 20mm四種規(guī)格上，將二維問題轉(zhuǎn)化為一維問題, 分別用一維下料問題的方法尋求四種寬度條材在一維情況下的最優(yōu)方案。在這一過程 屮，可根據(jù)一維下料問題求解的方法，建立模型二，解多目標整數(shù)觀劃，再進行般優(yōu)組 介，可以得到兩個階段所使用的條材。關(guān)鍵詞：貪心算法最優(yōu)下料規(guī)劃1一、問題的重述"下料問題(cutting stock problem) ”是把相同形狀的一些原材料分割加匸成若干 個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)

3、和T.業(yè)生產(chǎn)中有著重要和廣泛的應 用.這里的“實用下料問題”則是在某企業(yè)的實際條件限制下的單一材料的下料問題?，F(xiàn)考慮單一原材料下料問題.設這種原材料呈長方形，長度為L,寬度為W,現(xiàn)在 需要將一批這種長方形原料分割成m種規(guī)格的零件，所有零件的厚度均與原材料一致， 但長度和寬度分別為(h，鄧)，其中W'Vl, <L，w <W,i = l,. ,m. m種零件 的需求最分別為山,寸下料時，零件的邊必須分別和原材料的邊平行。這類問題在 工程上通常簡稱為二維下料問題。特別當所有零件的寬度均與原材料相等，即 xy =W,i二1,m，則問題稱為一維下料問題。一個好的下料方案首先應該使原材

4、料的利用率最大，從而減少損失，降低成本，提 高經(jīng)濟效益。其次耍求所采用的不同的下料方式盡可能少，即希望用最少的下料方式來 完成任務。因為在生產(chǎn)中轉(zhuǎn)換卜"料方式需耍費用和時間，既提高成本，乂降低效率。此 外，每種零件有各I的交貨時間，每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制。因此實用 下料問題的冃標是在生產(chǎn)能力容許的條件卜，以最少數(shù)量的原材料，盡可能按時完成需 求任務，同時下料方式數(shù)也盡暈地小.請你們?yōu)槟称髽I(yè)考慮下面兩個問題。1、建立一維單一原材料實用下料問題的數(shù)學模世，并用此模樂求解下列問題，制 定出在生產(chǎn)能力容許的條件下滿足需求的下料方案，同時求出等額完成任務所需的原 材料數(shù)，所采用的

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

6、材料總損耗增加0. 08%情況下的最佳方案。(2) .在解決具體問題時,先制定4天的下料方案，再制定6天的下料方案，最后制定53 種零件的下料方案.這一提示對第2題也部分適用.)2、建立二維單一原材料實用下料問題的數(shù)學模型，并用此模型求解下列問題.制定 出在企業(yè)生產(chǎn)能力容許的條件下滿足需求的卜料方案，同時求出等額完成任務所需的 原材料塊數(shù)和所需下料方式數(shù)這個問題的單原材料的長度為3000mm,寬度為100mm, 需耍完成一項有43種不同長度和寬度零件的下料任務.具體數(shù)據(jù)見表二，其中-対，叫 分別為需求零件的長度、寬度和數(shù)量.切割時的鋸縫可以是H的也可以是彎的，切割 所引起的鋸縫損耗忽略不計據(jù)估

7、計，該企業(yè)每天嚴大下料能力是20塊耍求在4天內(nèi)完 成的零件標號(i)為：3,7,9,12,15, 18, 20, 25, 28, 36.二、問題的假設(1) 問題一中的零件厚度和寬度均與原材料相等：(2) 問題二中的零件厚皮均與原材料相等。(3) 切割過程中無人工誤差三、符號的說明3.1問題一的符號說明符號說明km«x等額完成任務所需的原材料數(shù)k原材料個數(shù)1零件標號Xb在笫k個原材料上切割的第i個零件標號的零件數(shù)最111規(guī)格種數(shù)k需求零件長度L單一原材料長度d】(i = 1,2,- -,111)需求零件數(shù)帚s需下料的全部零件總長度Q下料方式數(shù)L*廢料總長度四、問題的分析對丁問題一，為

8、一維下料問題，考慮首耍目標為使原材料利用率最大，然后再使下 料方式數(shù)盡可能少。建立起以原材料使用數(shù)最最少為目標函數(shù)的規(guī)劃模型，易知該問題 為NP問題，故用一般的規(guī)劃算法很難求解，在現(xiàn)有的算法中也沒有一種算法可以求出 確定的最優(yōu)解，求解此類問題的算法有單口標或多口標模型，遺傳算法，模擬退火法，啟 發(fā)式算法，分支定界法等，木文利用貪心算法在隨機決策方案的棊木上采取擇優(yōu)原則， 經(jīng)多次選取后可將需耍量全部完成。對丁問題二，這是特殊的二維下料問題。很容易觀察到：問題二中所有零件的長度 都大于原材料的寬度，零件的寬度只有4種，大于80的寬度組合大約10多種。因此由 上述度眩知實際寬度組合會更少。這樣解問題

9、二的通常想法是將其轉(zhuǎn)化成問題一的形 式，同時也可以得出與問題一相類似的理論模熨。五. 模型的建立與求解5.1問5. 1. 1模型一的建立與求解1、模型一的建立1）.約東條件如題，設原材料呈長方形，長度為L,現(xiàn)在需耍將一批這種長方形原料分割成m種 規(guī)格的零件，所有零件的厚度和寬度均與原材料一致，第i種規(guī)格的零件的長度為J 需求量為（i =個。共耗用此瘁個原材料，且在第k個原材料上切割的第i個零件標號的零件數(shù)量為xh , 則有：（1）原材料觀格與鋸縫損耗約束條件為：mm工 1兀+5工Xk k = lX-.kinas1=1X=1（2）需求帚約束條件為：以及對屯的非負整數(shù)要求。（3）下料方式約束條件為

10、:Q = min5左 Xxkx-1k-1（4）下料能力約束條件為：每天的最大下料能力有：<1002）.目標函數(shù)的建立冃標換數(shù)的建立是為求得kn迪的故小值，【大I此建立如下:min工 X). = cti, i =1,2,mk-i其中,Z+= 0,1,2,. 為非負整數(shù)的集合。3）求得所需原材料最小值設2劉“， 表示需下料的全部零件總長度。進而定義:'s/L, s/L為整數(shù)iiit(s/L) + 1,其他則所需原材料的最小值為kJ若由目標函數(shù)求得的結(jié)果k_<k*,則計算結(jié)果有誤, 需耍修正程序算法，或是重新建立模熨。由式求得的最小值可避免犯一些明顯的錯 誤，并且可對程序進行驗證

11、。4）結(jié)果表示：(1) 等額完成任務所需的原材料數(shù)：(2) 下料方式數(shù)：Qm(3) 廢料總長度：L* = 3000 - £ 1 = 3000- s1=1(4) 下料方案：從上述模型可得出，下料方案為滿足模熨約柬條件的最優(yōu)解。2、算法實現(xiàn)隨機決策下的貪婪算法Stepl:對于給定需耍完成的產(chǎn)品，長度和需求量分別為L和m構(gòu)造一個n行1列矩陣NL,L1!形如：NL= L n其中0表示第1種材料的第i個排列，Ll中的n表示第一種材料的總需求量。Step2:產(chǎn)生100個隨機數(shù)組，每個隨機數(shù)組包含20個數(shù)，隨機數(shù)組R.的取值范圍為(llei】gth(NL),其屮R表示第i個數(shù)組里面的第j個隨機數(shù)的

12、值。將每一組數(shù)組的值R1對應到Stepl構(gòu)造的矩陣NL中的第B?個數(shù)中，結(jié)果是產(chǎn)生100組策略，每組策略有20個值。Step3；將產(chǎn)生的Step2產(chǎn)生的100組策略裝進100個隊列中，對毎個隊列進行分流操作， 從笫1組的第一個值開始累加到第一組的第20個數(shù)，累加過程中如果累加值超出30007的，該值不被采用，否則該值被分流進盒子，如果循環(huán)操作至第100組隨機值，瑕后結(jié) 果將產(chǎn)生出100組隨機策略組件，每組的累加值均滿足小T- 3000,即：S = S + R打 + 5, if(sx + R/+5 <3000)Sx = S£, if(Sx + R/+5 >3000 )i =

13、 1,2,-100 j = h2,208#Step4：對Step3產(chǎn)生的100種滿足條件的隨機組介采取擇優(yōu)選擇，即選擇max(SJ,此為 一次貪心決策結(jié)果，將構(gòu)成max(Sx)的各長度值從NL矩陣屮去掉，即將其值變?yōu)?.Step5:判斷NL矩陣中的非零值個數(shù)，當NoZeros(NL) = 0時，即表示NL中的每個值都 己經(jīng)被選出，否則繼續(xù)Step2Step5。由以上SteplStep5結(jié)束后易知垠終結(jié)果為各類型需求量均能被滿足，此為最終 的解。在實際操作中可能Step2屮的100個隨機數(shù)組中有些數(shù)組的20個隨機值出現(xiàn)雷同數(shù)値, 亦即R=R,此時如果R所對應的S為max(SJ,那么該隨機決策將是

14、-種偽決策， 此行為將導致NL矩陣中的某一值被&累加了多次,為此,可以將Step5中的判斷函數(shù):NoZeros(NL) = 0 改為 NoZeros(NL) = 5】豐(皿)即NL中剩下堆未被選擇時即跳出，然后對剩下的%°進行重組合，即將NL屮等0的數(shù)剔除，非零數(shù)值重新組介成新的NL,再繼續(xù)運行SteplStep5即可盡最避免當 Rxj = Rxk時，R”所對應的耳為max(Sx)的情況。至此，利用Matlab編程可求出滿足題目耍求的方案，從方案中可以檢測出 Rxj = Rxk時，用所對應的S為max(SJ的情況僅為四種，對四種方案人為處理后即可 得到最終結(jié)果。易求出該算法的

15、時間復雜度僅為O(sxiin(n) K T),其!> siim(n)表示總需求帚:，K表示隨機決策的個數(shù)(本文中取100), T表示每個隨機決策中的隊列長度(木文中取20）。此算法較之遺傳算法等的優(yōu)點是減少時間復雜皮，可以在較短時間內(nèi)求出滿意解, 而空間復雜度基本相同，缺點是下料方案是隨機性的，結(jié)果中有些下料方案可能只被執(zhí) 行數(shù)次。5. 2問題二5.2.1模型二的建立1、問題二模型的初步分析與建立問題二中的二維下料問題，由丁零件長、寬兩個方向上的限制，相比丁一維下料問 題復雜得多。這一問題還耍求集合D中的零件必須在第一階段（前四天）完成，而企業(yè)每 天的下料能力是20塊。妹丁這一條件，本文

16、模型的目標是盡可能節(jié)省原材料，并采用 盡最少的下料方式。kkmin工bmin工6©） ,<=,m;I,% >00,b- =0k 工冋 kYJ-11S （為 ）bj <80 ieD1 < ij < i2 < m;l <kj < ahJ ;1 < k2 < a“j- i2 +k】一 k】H 0其中，k：全部可行下料方式數(shù)：aXJ:表示第i號零件在第j種方式下切得的個數(shù); bJ：表示第j種下料方式耗材塊數(shù)；D= 零件i |i=3,7, 9,12,15,18, 20, 25,28,36, 即前4天須完成的零件集介；第i號零件的長、寬

17、、加工個數(shù)；勺,：第i號 零件在笫j中下料方式卜切得笫k塊冬件中心的橫坐標、縱坐標。2、模型的進一步分析根據(jù)問題2的特點,待加匚的零件的寬只集中在50mm, 30mm, 35mm, 20mm四種規(guī) 格上，可將二維問題轉(zhuǎn)化為一維問題，對四種寬度且長3000mm的條材，分別用一維下 料問題的方法尋求四種寬度條材在一維情況卜的般優(yōu)方案。根據(jù)-維下料問題求解的方法，解多目標整數(shù)規(guī)劃，可以得到兩個階段所使用的條 材。然后，將上述四種寬度的條材進行搭配，按僅有的無損失的方式列出。并進行優(yōu)化 組即以原板材消耗塊數(shù)最少為目標，建立整數(shù)規(guī)劃模型，模型二：mill ii +m2 +m3 +m4 +11152111

18、 + ni2 >m2 十 2m3 + m4 >S.t/m2 + 2m3 + 5m5 >2m4 >利用mat lab編程可得到第一階段最優(yōu)解和第二階段最優(yōu)解。六、模型的實證與評價6.1問題一模型一的實證分析根據(jù)模型一，結(jié)合貪婪算法，利用mat lab編程得出結(jié)果，如表6-1。表6-1各方案對比結(jié)果表項目數(shù)量計劃一計劃二前4天任務5-6天任務前6天任務剩余任務零件總長度4446493543617990101599898原材料個數(shù)152123267536原材料最小值149119267534下料方式數(shù)424570206廢料總長度11351146391099017102完成天數(shù)2

19、236利用率97. 51%96. 03%99. 21%98. 92%從表61中，可知，采用計劃二所使用的原材料數(shù)量耍比采用計劃一少7個，且利 用率也更優(yōu)，總廢料長度也更少。另外，也可得出，根據(jù)完成天數(shù)的不同而選出的最佳方案，產(chǎn)生了兩個最佳生產(chǎn)計 劃，可供企業(yè)站在不同角度選擇合適企業(yè)的生產(chǎn)計劃進行生產(chǎn)。計劃一：考慮到原材料的供給不足，尚不夠完成前6天的任務；且公司資金需耍周轉(zhuǎn)，不打 算將大量資金投入到原材料的購進，使倉庫幗積貨物。因此考慮在第1、2天完成四天的下料方案，第3, 4天不生產(chǎn)，第5, 6天完成6 天剩下的下料方案；完成剩余的53種零件的下料方案。計劃二公司已經(jīng)將53種零件需耍的原材料

20、全部購進：且公司仍有繼續(xù)接到定單的打算， 因此需要盡早完成全部下料方案的生產(chǎn)。則先選擇完成用3天時間完成前6天任務，再 完成剩余的53種零件的下料方案。綜合以上兩方而的考慮，本文給出計劃二的下料方案，詳見附錄表6-2和表6-36.2問題二模型二的實證分析略11參考文獻1 土 姐、溫陽俊.二維實用下料問題的數(shù)學模型及較優(yōu)解.數(shù)學的實踐與認識第36卷第7期2 倪 勤.實用下料問題的評注.數(shù)學的實踐與認識.笫35卷第7期.3 金詠怡.產(chǎn)品下料問題的一種求解方法.湖南商學院學報.第10卷第1期.4 谷峰、韓潤春、暢亞鋒、土帥印.一維實用下料問題的一種解法河北理工大學學報（自然科學版）第32卷第3期附錄

21、:表6-26天下料方案序號下料數(shù)11477147711801477290138821477600941105131326529015882147729029014614776002906000000o713138827320000018882882118000000598821030103000000r1088214772903280000O1188202908820000oS122901313110526500001138822906901105000011460060014772900000o1588204347320000116665147726529026500011788288288

22、229000002118882882600600000041988212322656000000420882745882434000012110552902907326000001290043484584526500123882434882732000092466529088284529000025434578882265265000126882882265265665000127600103029029074500012810308452652652902650012960088208820000130732265265845845000131290665845882265000132290

23、434103060060000013388229029088260000034290745745882290000135434434882578000013660088260060029000013743410556008820000138131300000001398824342652652650578014084588266557800001418826006008820000542265882265600665265001438822906002906002900014443426526588226529029001452652652652908827322650146290665290

24、8458820001147578265103066543400014888266588226526500014926526529029084573226501502652652655788822654340151434265290110526560000152600290600600882000285326526588273229026500154434845290290265845005554348452658822652650015660026566529029057826501572902902901105434290265045826560026526588269000o5960066

25、5265882265290006360845665265600265328001616004343282908824340016226588273226529026526501663290665600690434290001642902908452906652902900n6526526529026584543460003668822652902652654342902656729029026529073202652652651682902906652905782652902901692904346654342652902902901702652902902907322902652652651

26、表6-3剩余下料方案序號下料數(shù)112851680000000001221680104625500000002383017434050000000141680975313000000015117715322750000000765886301743000000016305821743000000018168041189300000003959071416800000000110168071958200000006115887141680000000021216808303131550000001138301680275184000000114588633168000000001151680630

27、590000000011631379516801840000001175905881680000000031816805885880000000211958216805880000000320766168027525500000022158801680000000022216805820000000022358817431842751840000012416805400000000012516802757192750000001262755881680000000032716805822750000000128411128512850000000229633168041125500000011

28、306304141680255000000131255633168040500000063216806302554110000001331680540275000000013416805402550000000135455588168025500000044363136301680275000000237420588275168000000033827516805904140000001394115901680275000000240590405168025500000014141558816802750000001421680000000000343411588168027500000044

29、459016804052750000003452754051680588000000124640516802555820000001471680313588313000000148275168058831300000049588275168025500000015027558816802750000001512552751680582000000252275275168000000001535882751680275155000001754540313168025518400000155168027500275184000015627516802750275000002571680255025

30、525500000158893153227527500000015916802751844204050000016025516804882752750000046131316802752754050000036216802552552552550000016316802752752752750000026415324057662750000002651680275275275275184000016631315324057190000001672555885881532000000168153258259027500000033695881532582275000000487031315325

31、4059000000017131358854015320000001724056301532405000000173630313184313153200000174153227525563327500000275153263325527527500000761532588184415255000002i i31331315325402750000017815324053134053130000017940518431327515322550000180590847255128500000018112858305882750000009825822758301285000000183830121

32、758818415500000184719121758845500000018558858212175880000003865825825881217000000187313128558858818400000188255128559025558800000989128525525558858800000129027558212852755400000019112855882754154050000019241112855882754050000029359012852754054050000019412854055884052750000019512855884112752551550000

33、196128540525525558218400001972552555821285313275000019812852754052755401840000199255255830588104600000110054040512172552752750000110158858258818410320000051024052551217405275405000011031177582405255275275000031042752552752751285255184155001105275103225571941127500001106630588588893275000003107719582

34、588830255000001108719588275540847000001109275588795719590000001110411893455633582000001111104640558225527540500001112588313630830588000001113405255414103258827500001114275103241140558825500001115590588405540847000001116588313975255255582000011175888305405884050000011188305404115885820000011197955884

35、115885900000011205884155887955880000011215885887954115880000011227955825884055900000011237196305825884550000011245825905906305820000011255885886335825820000021265406305825826300000011275885885885885880000021282758302754115885900000212983027558827558841100002130405588830275588275000021318305822752755

36、884050000113258840558831379527500001133633630588588255275000021345902756305882556300000113584754018458827527525500021363136335902555905880000113758840540571958225500001138313588588590255630000011395885882756332755880000214058818440558858859000002141588255588275275795184000114258831359058827558800001

37、143540582588411255588000031448475824552752552752750001145588275275184405405830000114631340527527527559083000011474055824054055885820000114858258858859027515518400011491845825881845885822550002150255590588588411275000011512755882555884050588000115225558231371958225525500011532752757195825822552750001

38、15471458827527527525558200011551845886335884114051550001156275830275275275255588184002157582255630405582255255000115827525559058859025541100011592755884115885902552550001160588255415275588588255000216125527558841458858825500021625885882754112555882550001163405255590588588255275000216425558858858227542025500021652755824202555885822550001166275275582582405590255000916758240558258825527527500051685885883132752755823130001169588588313540405255275000617054031358241158827525500021715884054054056302552750002172405405275411582255630000117358841145525541158825500011742755886302551842