Ang matipid na linear na pagputol ng mga materyales (pagputol ng mga molding) ay may kaugnayan para sa maraming mga industriya at sa konstruksyon. Ito ay paglalagari ng mga log at board sa woodworking, pagputol ng mga bar, reinforcing bar, anggulo, channel, pipe, I-beam sa mga blangko ...
Sa produksyon ng mga istrukturang metal at mechanical engineering, nakahalang pagputol ng mga rolyo na may papel at tela sa pulp at magaan na industriya.
Sa kabila ng maliwanag na pagiging simple, ang solusyon sa mga problema sa linear cutting ay hindi napakadali, ngunit kapaki-pakinabang. Ang pagpapakilala ng isang pang-agham na diskarte sa pagputol ng mga molded na materyales ay nagpapahintulot sa iyo na bawasan ang halaga ng mga ito, kung minsan ay higit sa 10%! Basahin ang artikulo hanggang sa dulo at tiyaking tama ang mga salitang ito.
Ang paksang tinatalakay ay nauugnay sa mga problema sa linear programming. Upang malutas ang gayong mga problema, ang mga siyentipiko sa nakalipas na 70 taon ay nakabuo ng iba't ibang pamamaraan.
Paraan ng mga indeks L.V. Kantorovich at V.A. Ang Zalgallera, na may isang tiyak na kasanayan, ay nagbibigay-daan sa iyo upang epektibong magsagawa ng linear cutting "manu-mano" nang hindi gumagamit ng teknolohiya ng computer. Inirerekomenda ko sa mga mausisa na mambabasa na maging pamilyar sa pamamaraang ito sa pamamagitan ng pagbabasa ng aklat ng mga pinangalanang may-akda sa itaas na "Rational Cutting of Industrial Materials".
Ang simplex na paraan batay sa mga ideya ni L.V. Kantorovich, ay inilarawan at binuo nang detalyado ng isang bilang ng mga siyentipiko mula sa USA sa kalagitnaan ng ika-20 siglo. Ginagamit ng Add-in na MS Excel "Search for a solution" (Solver) ang algorithm na ito. Ito ay sa pamamaraang ito naexcelmalulutas namin ang problema ng linear cutting sa artikulong ito.
Nang maglaon, lumitaw at binuo ang mga algorithm ng genetic, greedy at ant colony. Gayunpaman, ikukulong namin ang aming mga sarili sa paglilista ng mga ito at bumaba sa negosyo, nang hindi umakyat sa gubat ng mga teorya (bagaman doon, "sa mga ligaw", ito ay lubhang kawili-wili).
I-on natin ang Excel at, gamit ang isang simpleng halimbawa ng pagputol ng mga metal rod sa mga bahagi, makikilala natin ang isa sa mga paraan upang malutas ang mga praktikal na problema ng linear cutting. Kadalasang tinutukoy ng mga mathematician ang problemang ito bilang "problema sa pagputol".
Hindi ko inimbento ang paunang data para sa halimbawa, ngunit kinuha ito mula sa artikulo ni Pokrovsky M.A. "Pag-minimize sa hindi maiiwasang pagkalugi ng mga materyales sa pang-industriyang produksyon kapag pinutol ang mga ito sa mga pirasong blangko" na inilathala sa No. 5 (Mayo 2015) ng electronic na pang-agham at teknikal na journal na "Engineering Bulletin" na inilathala ng FGBOU VPO "MSTU im. N.E. Bauman (link:engbul. bmstu. en/ doc/775784. html).
Ang layunin na hinabol ko ay ihambing ang mga resulta ng paglutas ng problema.
Isang halimbawa ng paglutas ng problema ng linear cutting sa MS Excel.
Sumang-ayon tayo na:
1. Ang mga billet ay hilaw na materyal sa anyo ng mga bar, strips, rods, atbp. parehong haba.
2. Ang mga detalye ay mga elemento na kailangang makuha sa pamamagitan ng pagputol ng mga orihinal na blangko sa mga piraso.
3. Ang lapad ng saw, hiwa, kuskusin ay kinuha katumbas ng zero.
Ang gawain:
Upang makumpleto ang isa sa mga order, ang seksyon ng pagkuha ay dapat maghiwa ng tatlong karaniwang sukat ng mga bahagi sa pinagsamang mga gunting mula sa magkaparehong mga bar-blangko na may haba na 1500 mm:
151 piraso 330 mm ang haba
206 piraso 270 mm ang haba
163 piraso 190 mm ang haba
Kinakailangang hanapin ang pinakamainam na plano sa pagputol na gumagamit ng pinakamababang halaga ng materyal at, nang naaayon, ay nagbibigay ng pinakamababang halaga ng basura.
Paunang data:
1. Ang haba ng orihinal na mga blangko Lh sa millimeters isinulat namin sa pinagsamang cell
D3E3F3: 1500
2. Nagtatalaga kami ng mga numero i lahat ng karaniwang sukat ng mga bahagi, simula sa pinakamahaba at nagtatapos sa pinakamaikli sa mga selula
D4; E4; F4: 1; 2; 3
3. Mga haba ng bahagi Ldi sa millimeters na isinusulat namin
D5; E5; F5: 330; 270; 190
4. Bilang ng mga detalye Ndi sa mga pirasong inilalagay
D6; E6; F6: 151; 206; 163
5. Nagpapatuloy kami sa isang napakahalagang yugto - pagpuno sa mga pagpipilian sa pagputol.
Dapat tandaan at unawain 2 prinsipyo para sa paggawa ng trabahong ito.
1. Ang haba ng basura ay dapat na mas mababa kaysa sa pinakamaliit na bahagi ( 0< lo j < Ldmin ).
2. Sinimulan namin ang "paglalagay" ng mga bahagi sa workpiece na may pinakamalaking bahagi at may pinakamalaking bilang ng mga ito, na patuloy na gumagalaw sa direksyon ng pagbaba.
Kung walang sukat ng bahagi sa pagpipilian sa paggupit, pagkatapos ay iiwan namin ang cell na walang laman, hindi kami magsusulat ng zero upang mapadali ang visual na pang-unawa ng talahanayan.
Opsyon sa pagputol No. 1:
Ang isang pagtatangka na gupitin ang 5 bahagi No. 1 mula sa isang blangko ay imposible, kaya sumulat kami sa cell
Imposible ring magdagdag ng bahagi No. 2 o bahagi No. 3 sa pugad, kaya iniiwan namin na walang laman ang mga cell.
Opsyon sa pagputol No. 2:
Binabawasan namin ng 1 ang bilang ng mga bahagi No. 1 mula sa nakaraang bersyon at isulat ito
Sinusubukan naming magdagdag ng 2 bahagi No. 2 - hindi ito gumana, kaya idinagdag namin
Ito ay nananatiling posible upang madagdagan ang pagputol na may detalye No. 3. Pumasok kami sa
Ang pagsunod sa mga prinsipyong binibigkas, pinupunan namin sa pamamagitan ng pagkakatulad ang lahat ng 18 opsyon sa pagputol na posible sa kasong ito.
Ang pagkakaroon ng paggawa ng ilang mga talahanayan ng mga pagpipilian sa pagputol sa iyong sarili, mauunawaan mo ang lohika ng mga aksyon at gugugol ng ilang minuto sa gawaing ito.
Kung ang unang prinsipyo ay hindi natupad sa panahon ng pagputol, pagkatapos ay ang cell na may haba ng pag-alis ay awtomatikong pininturahan ng pula. Ang conditional formatting na inilapat sa mga cell G7…G24 ay malinaw na makakatulong sa iyo sa gawaing ito.
Sa mga cell H7 ... H24 huwag sumulat ng anuman! Ginagamit ang mga ito upang ipakita ang resulta ng solusyon!
Paghahanda para sa solusyon:
* Sa mga cell G7 ... G24, ang mga haba ng basura (mga hiwa) na natitira bilang resulta ng pagputol ay kinakalkula ayon sa formula
lo j = L h -Σ (Ldi * Ndij )
6. Ang bilang ng mga bahagi ng bawat karaniwang sukat, na ginawa ayon sa lahat ng inilapat na opsyon sa pagpupugad, ay kakalkulahin sa mga cell D26, E26 at F26 ayon sa formula
Ndicalc = Σ (Ndij * Nhj )
Ang bilang ng mga bahagi sa cutting plan na matatagpuan sa dulo ng solusyon ay dapat na ganap na tumutugma sa tinukoy na bilang ng mga bahagi!
7. Ang kinakailangang bilang ng mga workpiece para makumpleto ang pinakamainam na cutting plan ay matutukoy sa pinagsamang cell D27E27F27 gamit ang formula
N calc =ΣN hj
8. Ang kabuuang haba ng lahat ng mga blangko na kinakailangan upang maisagawa ang isang linear na pugad ng lahat ng mga bahagi ay kakalkulahin sa pinagsamang cell D28E28F28 gamit ang formula
Lh Σ = L h*Nmula sa pagkalkula
9. Ang kabuuang haba ng lahat ng basura na nagreresulta mula sa pagpapatupad ng nakitang cutting plan ay kakalkulahin sa pinagsamang cell D29E29F29 gamit ang formula
Ltungkol sa Σ = Σ (Ltungkol saj * Nhj )
10. Ang proporsyon ng basura na nabuo ng pinakamainam na linear cutting plan mula sa kabuuang halaga ng materyal na ginamit ay kakalkulahin sa pinagsamang cell D30E30F30 gamit ang formula
Ωo = Lo Σ /Lз Σ
Solusyon:
Ang paghahanda ay nakumpleto, 18 mga pagpipilian para sa pinakamainam na pagputol ng isang workpiece sa mga bahagi ay tinutukoy at ang lahat ng kinakailangang mga formula ay ipinasok. Ngayon kailangan nating lutasin ang pangunahing problema: upang matukoy pinakamainam na plano sa pagputol - kung gaano karaming mga blangko, at ayon sa kung ano ang mga pagpipilian sa pagputol upang i-cut upang sa wakas ay makuha ang lahat ng kinakailangang bahagi sa tamang dami na may kaunting basura.
1. Piliin sa pangunahing menu na "Serbisyo" - "Maghanap ng solusyon ...".
2. Sa window ng parehong pangalan na "Maghanap ng solusyon" na lilitaw, ginagawa namin ang mga setting.
2.1. Itinatalaga namin ang kabuuang haba ng basura sa layuning pag-andar Lo Σ at ipasok ang link sa target na cell window.
2.2. Itakda ang switch na "Equal:" sa posisyon na "minimum value."
2.3. Tukuyin ang mga cell na may mga variable Nz j sa window ng Changing Cells.
2.4. Naglalagay kami ng mga paghihigpit sa window ng parehong pangalan. Bilang mga kondisyon, ipinapahiwatig namin ang pangangailangan para sa pagkakapantay-pantay ng ibinigay Nd i at pag-areglo Nd icalc ang bilang ng mga bahagi, pati na rin ang mga variable Nz j- ang tinantyang bilang ng mga blangko sa pamamagitan ng mga pagpipilian sa pagputol - nagpapataw kami ng paghihigpit: dapat itong mga integer.
3. Pinindot namin ang button na "Mga Parameter" at sa window na "Mga parameter ng paghahanap ng solusyon" na lalabas, ginagawa namin ang mga setting tulad ng ipinapakita sa sumusunod na screenshot. Isara ang window gamit ang OK button.
4. Sa window na "Search for a solution," i-click ang "Run" button at hintayin ang Excel na makahanap ng solusyon. Maaaring tumagal ito ng ilang minuto.
5. Pagkatapos i-save ang nahanap na solusyon gamit ang OK na buton, ang mga resulta ay ipapakita sa mga cell H7 ... H24 sa Excel sheet.
Ang sumusunod na larawan ay nagpapakita ng nahanap na pinakamainam na linear cutting plan.
Ano ang resulta?
Ang linear na pagputol sa mga blangko ng Excel para sa mga gawain tulad ng tinalakay sa artikulong ito ay isinasagawa ng pamamaraang inilarawan sa itaas sa loob ng 10-15 minuto! "Manu-mano", nang hindi nalalaman ang paraan ng mga indeks ng Kantorovich, hindi ka makakahanap ng solusyon sa ganoong oras.
Sa pamamagitan ng pagpapatakbo ng "Maghanap ng solusyon" nang maraming beses na may iba't ibang mga parameter sa paghahanap, nakahanap kami ng 5 magkakaibang mga plano para sa pagtanggal ng mga blangko. Ang lahat ng 5 plano ay nangangailangan ng parehong bilang ng mga blangko - 93 at nagbibigay lamang ng 2.21% na basura!!! Ang mga planong ito ay halos 6% na mas mahusay kaysa sa plano na kinakalkula ni Pokrovsky at higit sa 10% na mas matipid kaysa sa "Tradisyonal" na plano (tingnan ang link sa orihinal na pinagmulan sa unang bahagi ng artikulo). Ang isang napaka-karapat-dapat na resulta ay nakamit nang mabilis at nang walang paggamit ng mga mamahaling programa.
Dapat tandaan na ang Excel Solver add-in ("Search for a solution"), na gumagamit ng simplex na paraan kapag nilulutas ang mga problema sa linear programming, ay maaaring gumana nang hindi hihigit sa 200 variable. Tulad ng inilapat sa linear cutting na problema na aming isinasaalang-alang, nangangahulugan ito na ang bilang ng mga pinagputulan ay hindi maaaring lumampas sa 200 na mga variant. Para sa mga simpleng gawain, ito ay sapat na. Para sa mas kumplikadong mga gawain, dapat mong subukang mag-apply ng isang "halo" ng "matakaw" na algorithm at ang simplex na paraan ng Solver, na pumili ng hindi hihigit sa 200 pinaka-matipid mula sa kumpletong listahan ng mga pinagputulan. Pagkatapos ay nag-iipon kami ng pasensya at nakakamit ang mga resulta. Maaari mong subukang hatiin ang isang kumplikadong problema sa ilang mga simple, ngunit ang "antas ng pinakamainam" ng solusyon na natagpuan ay malamang na mas mababa.
Marahil ang itinuturing na opsyon para sa paglutas ng mga isyu sa linear cutting ay hindi "aerobatics", ngunit ito ay tiyak na isang hakbang pasulong kumpara sa "tradisyonal" na diskarte sa maraming mga industriya.
Ang paggamit ng MS Excel na "Search for a Solution" (Solver) add-in ay tinalakay na sa blog minsan sa isang artikulo. Sa tingin ko, ang kahanga-hangang tool na ito ay karapat-dapat na bigyang pansin at makakatulong nang higit sa isang beses nang maganda at mabilis na malutas ang isang bilang ng mga bagong di-maliit na problema.
P.S. Mga link sa pinakamahusay na libreng linear cutting software na nakita ko sa web:
http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html
http://forum-okna.ru/index.php?app=core&module=attach§ion=attach &attach_id=7508
http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74
http://www.planetcalc.ru/917/
Ang mga programa sa huling dalawang link ay nagpapatupad ng matakaw na heuristics at nagsasagawa ng linear nesting sa gawain mula sa artikulo, gamit ang kasing dami ng 103 blangko. Ang paggamit ng mga matakaw na algorithm ay makatwiran sa mga kaso kung saan kinakailangan upang bawasan ang kabuuang oras ng operasyon ng pagputol na may napakaraming pagpipilian sa pagputol sa mas pinakamainam na mga plano.
Sa ibaba ng artikulo sa block na "Mga Review," maaari mong isulat ang iyong mga komento, mahal na mga mambabasa.
Tingnan ang Mga Linear Programming Models para sa Mga Problema sa Nesting.
Halimbawa #1. Ang mga produkto ng kumpanya ng papel ay ginawa sa anyo ng mga papel na rolyo ng karaniwang lapad - 2 metro bawat isa. Sa mga espesyal na order ng mga mamimili, ang kumpanya ay nagbibigay ng mga rolyo ng iba pang mga laki, kung saan ang mga karaniwang roll ay pinutol. Ang mga karaniwang order para sa mga rolyo na hindi karaniwang sukat ay ibinibigay sa talahanayan.
Ito ay kinakailangan upang mahanap ang mga naturang kumbinasyon ng iba't ibang mga opsyon para sa pagputol ng mga karaniwang roll upang ganap na masiyahan ang mga natanggap na mga order na may kaunting pagkalugi (basura).
Isaalang-alang natin ang lahat ng posibleng mga opsyon para sa pagputol ng isang karaniwang roll, ibibigay namin ang kaukulang data sa Table.
| Roll Width(m) | Mga pagpipilian sa paggupit ng roll | Pinakamababang bilang ng mga rolyo | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 0,5 | 0 | 2 | 2 | 4 | 1 | 0 | 150 |
| 0,7 | 1 | 1 | 0 | 0 | 2 | 0 | 200 |
| 0,9 | 1 | 0 | 1 | 0 | 0 | 2 | 300 |
| Basura sa m | 0,4 | 0,3 | 0,1 | 0 | 0,1 | 0,2 | - |
Tukuyin natin ang mga variable:
X j - ang bilang ng mga karaniwang roll na pinutol ayon sa opsyon j, j=1, 2, 3,4,5, 6.
Ang mga limitasyon ay direktang nauugnay sa kinakailangan upang matiyak ang paggawa ng kinakailangang bilang ng mga hindi karaniwang mga rolyo. Gamit ang data sa talahanayan, nakukuha namin:
2X 2 + 2 X 3 + 4 X 4 + X 5 \u003d 150 - ang bilang ng mga roll na 0.5 m ang lapad,
X 1 + X 2 + 2 X 5 \u003d 200 - ang bilang ng mga roll na 0.7 m ang lapad,
X 1 + X 3 + 2 X 6 \u003d 300 - ang bilang ng mga roll na 0.9 m ang lapad.
Ang expression para sa kabuuang halaga ng pagkawala ng papel (basura) (sa m) ay
0.4X 1 + 0.3 X 2 + 0.1 X 3 + 0.1 X 5 + 0.2 X 6.
Kaya, ang pangkalahatang modelo ng matematika ay may anyo
min f (x) \u003d 0.4 X 1 + 0.3X 2 + 0.1X 3 + 0.1X 5 + 0.2X 6.
na may mga paghihigpit:
2X 2 + 2 X 3 + 4 X 4 + X 5 = 150
X 2 + X 2 + 2 X 5 = 200
X 2 + X 3 + 2 X 6 = 300
Ang problema sa pagputol ng mga materyales
Ang gawaing ito ay upang bumuo ng isang plano na nagbibigay ng kinakailangang hanay ng mga produkto na may kaunting basura (sa haba, lugar, timbang, gastos, atbp.) Kapag nag-cut ng mga materyales o nagbibigay ng maximum na bilang ng mga hanay ng produkto. Halimbawa #2. Kinakailangan na bumuo ng isang pinakamainam na plano para sa pagputol ng karaniwang mga sheet ng bakal, na tinitiyak ang output ng nakaplanong bilang ng mga blangko ng iba't ibang uri na may kaunting kabuuang basura, kung alam na ang apat na uri ng iba't ibang mga blangko ay dapat gupitin mula sa isang batch ng sheet na bakal. sa dami ng bi (i = 1, 2, ..., 4) piraso . Ang isang bakal na sheet ng karaniwang laki ay maaaring i-cut sa apat na paraan. Ang bawat posibleng paraan ng pagputol ay tumutugma sa isang cutting chart. Mula sa mga cutting chart, ang output ng mga workpiece sa mga piraso ng iba't ibang uri a ij (i = 1, 2,…4; j = 1,2,…,4), pati na rin ang lugar ng basura cj (j = 1, 2 ,…,n) sa pagputol ng isang sheet ng bakal ayon sa j-th na paraan ng pagputol. Ilang mga sheet ng bakal ang dapat putulin sa isang paraan o iba pa upang ang basura ay minimal?Talahanayan 3
Mga uri | Plano ng gawain para sa bilang ng mga blangko (b 1) | Output ng mga blangko (pcs) ng iba't ibang uri |
|||
| 1 | 2 | 3 | 4 | ||
| 1 | 240 | 1 | 4 | 0 | 1 |
| 2 | 200 | 1 | 0 | 4 | 0 |
| 3 | 120 | 1 | 0 | 0 | 3 |
| 4 | 140 | 1 | 1 | 0 | 3 |
| Lugar ng basura, m 2 (cj) | 1,4 | 0,1 | 2,1 | 0,1 | |
Gumawa tayo ng modelong ekonomiko-matematika ng problema. Tukuyin natin sa pamamagitan ng x j - ang dami ng pinagmumulan ng materyal (mga sheet ng bakal) na dapat putulin ayon sa isa sa mga pamamaraan j. Ang mga hadlang sa gawain ay dapat na tumutugma sa nakaplanong output ng mga blangko ng iba't ibang uri. Ang layunin ng pag-andar ay upang mahanap ang pinakamababang basura kapag pinutol
F=1.4 x 1 +0.1 x 2 +2.1 x 3 +0.1 x 4 →(min)..
Mga paghihigpit sa output ng mga blangko ng i-th type para sa lahat ng j cutting method:
Halimbawa #3. Para sa pagputol (paglalagari, pagproseso) ang materyal ng isang sample ay ibinibigay sa halaga ng isang yunit. Kinakailangang gumawa mula rito ng iba't ibang bahagi sa mga dami na proporsyonal sa mga numerong b 1 , b 2 ,…,b l (kondisyon ng pagkakumpleto). Ang bawat yunit ng materyal ay maaaring putulin sa n iba't ibang paraan, at gamit ang i-th na paraan (i = 1, 2,…,n) ay nagbibigay ng ik unit ng k-th na produkto (k = 1, 2,…,l ). Ito ay kinakailangan upang makahanap ng isang cutting plan na nagbibigay ng maximum na bilang ng mga set.
Gumawa tayo ng modelong ekonomiko-matematika ng problema.
Hayaang tukuyin ng x i ang bilang ng mga yunit ng materyal na pinutol ng i-th na pamamaraan, at x ang bilang ng mga ginawang hanay ng mga produkto. Pagkatapos ang layunin ng function ay nabawasan sa paghahanap
F=x→(max),
na may mga paghihigpit: sa pamamagitan ng kabuuang halaga ng materyal na katumbas ng kabuuan ng mga yunit nito, gupitin sa iba't ibang paraan; ayon sa pangangailangan ng pagkakumpleto at di-negatibiti ng mga variable.
Halimbawa #4. Ang kumpanya ay may mga log ng haba L m, na dapat i-cut sa mga piraso ng haba l 1 , l 2 , l 3 m sa halagang p 1 , p 2 , p 3 ayon sa pagkakabanggit.
Kinakailangan na gumuhit ng isang pinakamainam na plano para sa pagputol ng materyal, na nagsisiguro ng kaunting basura, napapailalim sa plano para sa output ng mga blangko. Ang paunang data ay ibinigay sa talahanayan.
| Isang gawain | Ang haba | Mga blangkong sukat, m | Bilang ng mga blangko, mga pcs. | ||||
| l 1 | l 2 | l 3 | p1 | p2 | p 3 | ||
| 68 | 6,5 | 2,1 | 2,3 | 1,4 | 600 | 720 | 900 |
Solusyon: Una, gumawa tayo ng mathematical model ng ating problema. Ang mga posibleng pagpipilian sa pagputol at basura para sa bawat isa sa kanila ay isusulat sa anyo ng isang talahanayan.
| Haba ng workpiece | Mga pagpipilian sa pagputol | Bilang ng mga blangko | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| 2,1 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 600 |
| 2,3 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 720 |
| 1,4 | 0 | 0 | 1 | 1 | 3 | 1 | 3 | 900 |
| Natitira, m | 0,2 | 0 | 0,9 | 0,7 | 0,2 | 0,5 | 0 | |
Ipahiwatig sa pamamagitan ng x i ang bilang ng mga log na pinutol ayon sa i-th na opsyon (i=1..7). Pagkatapos ang kabuuang natitirang basura ay isusulat bilang isang linear function:
Z = 0.2x1 + 0x2 + 0.9x3 + 0.7x4 + 0.2x5 + 0.5x6 + 0x7
Kasabay nito, ang mga kondisyon para sa pagtupad sa plano sa mga tuntunin ng bilang ng mga blangko ay dapat matugunan, i.e.
3x1 + 2x2 + 2x3 + x4 + x5 = 600
x2 + x4 + 2x6 + x7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900
Kaya, upang malutas ang nakasaad na problema, kinakailangan upang mahanap ang minZ sa ilalim ng mga hadlang. Dahil minZ = -max(-Z(x)), at sa halip na ang function minimization problem, lutasin natin ang function maximization problem:
Z = -(0.2x 1 + 0x 2 + 0.9x 3 + 0.7x 4 + 0.2x 5 + 0.5x 6 + 0x 7)
Halimbawa numero 5. Para sa pananahi ng isang produkto, kailangan mong gupitin ang 6 na bahagi mula sa tela. Sa pabrika ng damit, dalawang pagpipilian para sa pagputol ng tela ay binuo. Ang talahanayan (na matatagpuan sa ibaba) ay nagpapakita ng mga katangian ng mga pagpipilian sa pagputol para sa 10 m 2 ng tela, pagkakumpleto, i.e. ang bilang ng mga bahagi ng isang tiyak na uri na kailangan upang manahi ng isang produkto. Ang buwanang supply ng tela para sa mga produktong pananahi ng ganitong uri ay 405 m 2 . Sa darating na gabi, planong magtahi ng 90 item.
Bumuo ng mathematical model ng problema na nagbibigay-daan sa iyong kumpletuhin ang tailoring plan na may pinakamababang halaga ng basura sa susunod na buwan.
Talahanayan - Mga katangian ng mga opsyon para sa pagputol ng mga piraso ng tela na 10m 2
| Pagpipilian sa pagputol | Bilang ng mga bahagi, piraso/hiwa | Basura, m 2 / hiwa | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 | 60 | 0 | 90 | 40 | 70 | 90 | 0,5 |
| 2 | 80 | 35 | 20 | 78 | 15 | 0 | 0,35 |
| Pagkakumpleto, piraso/produkto | 1 | 2 | 2 | 2 | 2 | 2 | |
Matematika na pahayag ng problema
Mga Variable ng Gawain
Sa problemang ito, ang mga kinakailangang halaga ay hindi tahasang ipinahiwatig, ngunit sinasabi na ang isang buwanang plano para sa pananahi ng 90 mga produkto ay dapat makumpleto. Para sa pagsasaayos ng 90 mga produkto bawat buwan, kinakailangan na mag-cut ng isang mahigpit na tinukoy na bilang ng mga bahagi. Ang hiwa ay ginawa mula sa mga piraso ng tela na 10 m 2 sa dalawang magkaibang paraan, na nagpapahintulot sa iyo na makakuha ng ibang bilang ng mga detalye. Dahil hindi alam nang maaga kung gaano karaming tela ang gupitin sa unang paraan at kung magkano sa pangalawang paraan, kung gayon bilang mga nais na halaga, maaari mong itakda ang bilang ng mga segment ng tela na 10 m 2 na gupitin ng bawat isa sa mga pamamaraan:
x 1 - ang bilang ng mga piraso ng tela na 10m 2, pinutol sa unang paraan sa buwan, [cut / buwan];
x 2 - ang bilang ng mga piraso ng tela, 10m 2 bawat isa, pinutol sa unang paraan sa buwan, [cut / buwan];
layunin function
Ang layunin ng paglutas ng problema ay upang matupad ang plano na may pinakamababang halaga ng basura. Dahil ang bilang ng mga produkto ay mahigpit na binalak (90 pcs/month), hindi inilalarawan ng parameter na ito ang CF, ngunit tumutukoy sa isang hadlang, ang pagkabigo nito ay nangangahulugan na ang problema ay hindi pa nalutas. At ang criterion para sa pagiging epektibo ng pagpapatupad ng plano ay ang parameter na "dami ng basura", na dapat mabawasan. Dahil kapag ang pagputol ng isang piraso (10 m 2) ng tela ayon sa 1st option, 0.5 m 2 ng basura ang nakuha, at ayon sa 2nd option - 0.35 m 2 (tingnan ang talahanayan 1), ang kabuuang halaga ng basura kapag pinutol ( CF) ay may view
L(x) = 0.5x1 + 0.35x2 = min,
Mga paghihigpit
Ang bilang ng mga pagputol ng tela sa iba't ibang paraan ay nililimitahan ng mga sumusunod na kondisyon:
- Ang isang plano para sa pag-aayos ng mga produkto ay dapat matupad, sa madaling salita, ang kabuuang bilang ng mga hiwa na bahagi ay dapat na tulad na 90 mga produkto bawat buwan ay maaaring maitahi mula dito, ibig sabihin: dapat mayroong hindi bababa sa 90 ng unang uri at mga bahagi ng iba pang mga uri - hindi bababa sa 180 (tingnan ang pagkakumpleto sa talahanayan).
- Ang pagkonsumo ng tela ay hindi dapat lumampas sa isang buwanang stock sa bodega;
- Ang bilang ng mga piraso ng ginupit na tela ay hindi maaaring negatibo.
(Kabuuang bilang ng mga bahagi No. 1 na hiwa para sa lahat ng opsyon) ≥ (90 piraso);
(Kabuuang bilang ng mga bahagi No. 2 cut para sa lahat ng mga opsyon) ≥ (180 piraso);
(Kabuuang bilang ng mga bahagi No. 6 na hiwa para sa lahat ng mga opsyon) ≥ (180 piraso);
Sa matematika, ang mga paghihigpit na ito ay isinulat bilang
:
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;
Ang limitasyon sa paggamit ng tissue ay may mga sumusunod na anyo ng pagtatala:
makabuluhan
(kabuuang pagputol ng tela bawat buwan)≤ (405m2)
mathematical
x 1 + x 2 ≤405/10
Ang non-negatibiti ng bilang ng mga cut segment ay ibinibigay sa form
x 1 ≥ 0, x 2 ≥ 0
Kaya, ang modelo ng matematika ng problema ay may anyo
L(x) \u003d 0.5x 1 + 0.35x 2 \u003d min [m 2 basura / buwan],
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;
x 1 + x 2 ≤40.5
x 1 ≥ 0, x 2 ≥ 0
Halimbawa numero 6. Mayroong 69 na tubo para sa network ng pag-init, 1070 cm bawat isa. Dapat silang i-cut sa mga tubo na 130, 150 at 310 cm. Maghanap ng isang pagpipilian para sa pagputol ng mga papasok na tubo, kung saan ang basura ay magiging minimal.
Stage 1. Tinutukoy namin ang mga opsyon para sa pinakamainam na pagputol ng mga tubo.
| Mga pagpipilian sa pagputol | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 310 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 150 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
| 130 | 1 | 0 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | 7 | 8 |
| Labi | 10 | 0 | 20 | 40 | 60 | 50 | 70 | 90 | 110 | 100 | 120 | 10 | 30 |
Stage 2.
Gumawa tayo ng modelong ekonomiko-matematika ng problema. Tukuyin natin sa pamamagitan ng x j - ang bilang ng mga tubo na kailangang putulin ayon sa isa sa mga paraan j. Ang layunin ng pag-andar ay upang mahanap ang pinakamababang basura kapag pinutol:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min
x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69
Sagot: ang pangalawang cut option lamang ang dapat gamitin (zero waste)
Ang programa ay idinisenyo upang ma-optimize ang pagputol ng mga profile at iba pang mahabang materyales (bar, log, pipe, window sill).
Ang algorithm na "siksik na stacking" ay ginagamit, iyon ay, ang kinuha na produkto ay inilalagay sa pinakamaikling natitirang bahagi ng workpiece kung saan ito inilalagay. Kung hindi ito magkasya kahit saan, isang bagong blangko ang kukunin. Ang gawain ng pag-optimize ay upang makahanap ng isang pagkakasunud-sunod ng mga produkto kung saan mas kaunting mga blangko ang gagamitin at ang haba ng mga dekorasyon ng negosyo ay magiging mas mahaba. Sa unang sukat, ang mga bagay ay inilalagay sa mga latigo sa random na pagkakasunud-sunod. May "initial population". Sa proseso ng paglutas, ang populasyon ay nagmu-mute at dumami, ang mga hindi matagumpay na specimen ay namamatay, at ang mga pinakamahusay ay patuloy na nagbabago. Lahat, tulad ng sa mundo ng hayop at halaman + artipisyal na seleksyon.
Live na demo sa site
Magsimula
Mga kalamangan
- Nagbibigay ang Windowsoft:cutting ng mataas na kalidad na mga cut map. Kinumpirma ng maraming pagpapatupad ang aktwal na cutting factor na hindi hihigit sa 1% kapag nag-optimize ng mga batch mula sa 30 contours (~120 cuts)
- Upang basahin ang paunang data at itala ang mga resulta ng pagputol, ang programa ay gumagamit ng mga simpleng format ng text file, na nagpapadali sa pagsasama sa mga sistema ng accounting na ipinatupad ng customer
- Kung kinakailangan, maaaring isagawa ang nesting sa ilalim ng Linux o OS X sa isang browser o mga parameter na nagpapasa ng Node.js sa pamamagitan ng url, web socket o mga javascript na bagay.
Mga algorithm ng linear optimizer
Windowsoft: Ang pagputol ay gumagamit ng genetic algorithm. Ang kakanyahan nito ay ito:
Tawagan natin ang bawat pamamahagi ng mga produkto sa pamamagitan ng mga latigo bilang isang solusyon. Tukuyin natin ang isang layunin na function na nagbibigay-daan sa amin upang ihambing ang kalidad ng mga solusyon. Bumuo tayo ng ilang di-makatwirang solusyon, tawagin silang isang henerasyon. Tukuyin natin ang mga tuntunin para makuha ang susunod na henerasyon. Ang mga pagkakataong may pinakamahusay na layunin na function ay naglilipat ng karamihan sa kanilang "gene pool", ito ang aming "artipisyal na pagpili." Ngayon ay nananatiling iwanan ang system sa sarili nito, hayaan itong mag-mutate at i-optimize ang mga resulta ng pagputol
Sa panahon ng proseso ng pagbuo, ang "Monte Carlo" na paraan ay sinubukan, kapag ang aming "mga pagkakataon" ay random at hindi nakadepende sa isa't isa, at "Ant algorithm" (ACO-ant colony optimization). Ang lahat ng mga pamamaraan ay napatunayang lubos na mahusay, ngunit ang genetic algorithm ay naging bahagyang mas mahusay.
Mga opsyon sa paghahatid
Mayroong dalawang opsyon sa paghahatid para sa Windowsoft:cutting cutting module - bilang bahagi ng pinagsama-samang solusyon para sa Custom Production Management at bilang isang hiwalay na executable file. Ang pakikipag-ugnayan sa cutting program sa unang senaryo ay ganap na nakatago mula sa user. Gumagana ang operator sa mga karaniwang 1C na dokumento:
- Batay sa mga order ng customer, nabuo ang isang plano sa produksyon
- Batay sa plano - ilipat ang mga gawain na may isang listahan ng mga produkto at mga kinakailangang materyales
- Na-optimize ang nesting sa loob ng order ng produksyon
- Sa proseso ng pag-optimize, inaalis ng programa ang business trim mula sa kasalukuyang gawain at inilalagay ang bagong nabuong business trim sa cellular warehouse
- Ang isang shift job ay nakakapag-print ng mga cutting form para sa manu-manong produksyon o makabuo ng mga file para sa mga CNC machine
- Gayundin, ang mga label para sa mga cut products at layout scheme para sa mga cart at pyramids ay naka-print mula sa isang shift job.
- Sa batayan ng mga gawain sa produksyon, ang mga kinakailangan ay nabuo - mga invoice para sa paglipat ng mga materyales sa pagawaan, na isinasaalang-alang ang mga pangangailangan at karaniwang packaging
Software Interface (Linear Nesting API)
Ang input data file, setup.ini, ay inilalagay sa folder na may executable file.
Ang mga file ng data ng output - result.txt, resultproduct.txt at resultstick.txt - ay nabuo sa parehong folder.
Maaari kang mag-download ng mga file gamit ang Oknosoft:cutting demo data mula sa link sa dulo ng page. Ginagamit ng mga file ang mga sumusunod na tag:
- Outputvariant - ang istraktura ng output file ng file. Mga posibleng halaga: tab, oknosoft, default na oknosoft
- Sa opsyong "oknosoft", ang resultproduct.txt at resultstick.txt file ay nabuo na may impormasyon tungkol sa paglalagay ng mga produkto sa mga blangko at ang resultang trim
- Ang variant ng "tab" ay nagpapakita ng limang value na pinaghihiwalay ng mga character na "tab": haba ng produkto, whip number, whip length, cut number at workpiece remains
- Algorithm - ang ginamit na algorithm. Mga posibleng value: random, konserbatibo, genetic, default genetic
- Random - random na pagpili ng mga opsyon
- Konserbatibo - ang mga pagkakataon ng susunod na pag-ulit ay nagmula sa parehong "magulang"
- Genetic - mula sa dalawang magulang
- Pagkakaiba-iba - pagkakaiba-iba, parameter ng "konserbatibo" at "genetic" na mga algorithm. Ang mas mataas, mas kaunti ang supling "katulad" sa mga magulang. Ang default ay 1.
- Mga Henerasyon - bilang ng mga pag-ulit ng algorithm, default na 40000
- Mga Tao - ang bilang ng "mga pagkakataon" sa "populasyon", ang bilang ng mga solusyon na ginamit sa isang pag-ulit. Ginagawa lang ng "random" na algorithm ang mga henerasyon*tao ng mga pag-ulit na may isang pagkakataon (solusyon)
- KnifeWidth - lapad ng lagari
- StickLength - ang haba ng bagong stick
- Mga produkto - haba ng produkto
- Scraps - ang haba ng scrap na ginamit sa pugad
- Wrongsnipmin - ang pinakamababang haba ng isang "masamang" swatch
- Wrongsnipmax - ang maximum na haba ng isang "masamang" hiwa
Ang mga resulta ng pag-optimize ay hindi magkakaroon ng mga clipping na may haba sa pagitan ng Wrongsnipmin at Wrongsnipmax
Pares cutting
Ginagamit kapag naghahanda ng data para sa mga makinang sumusuporta sa pares na paglalagari. Sa kasong ito, dalawang profile whips ang inilalagay sa makina nang sabay-sabay, at sa isang cutting cycle, dalawang magkaparehong semi-tapos na mga produkto ang nabuo.
Ang gawain ng pagputol ng pares ay nalulutas sa pamamagitan ng pagpapangkat ng data bago ito ilipat sa programa ng pag-optimize at pagkatapos ay pagdodoble ng mga resulta ng pagputol sa mga pares ng mga produkto at workpiece. Kapag pugad sa loob ng UPZP, isinasaalang-alang ng system ang mga katangian ng nomenclature at gumagamit ng solong o pares na pagputol, depende sa mga kakayahan ng mga cutting machine.
Pagputol ng malaking bilang ng mga produkto
Sa isang banda, upang makamit ang isang mataas na kalidad ng pag-optimize, isang makabuluhang bilang ng mga produkto na may iba't ibang haba ay dapat matanggap sa input ng programa, upang ang optimizer ay may "kung ano ang pag-uuri-uriin". Sa kabilang banda, na may napakalaking batch, ang posibilidad na mahanap ang maximum sa isang nakapirming bilang ng mga pag-ulit ng enumeration ay bumababa. Ipinakita ng mga eksperimento na ang isang batch ng 60-120 na mga blangko ay pinakamainam (na tumutugma sa isang ikot ng produksyon ng 30-60 mga produkto na may ipinares na pagputol). Kung kailangan mong mag-optimize ng higit sa 120 workpieces, ang pinakamahusay na mga resulta ay maaaring makamit sa pamamagitan ng paghahati sa problema sa N bahagi at pagsasagawa ng sunud-sunod na pag-optimize para sa bawat bahagi. Ang pagpoproseso ng pagbuo ng mga batch ng mga gawain sa produksyon ay nakakapag-grupo ng mga produkto ayon sa uri ng profile at pumili ng mga produkto na may pinakamataas na dispersion sa mga shift na gawain, na nagliligtas sa operator mula sa nakagawiang gawain ng pag-compile ng mga dokumento ng produksyon
Mag-download ng mga halimbawa ng pagputol at dokumentasyon
- Demo ng single at double cut card: 60.01 Cutting sheets
- Dokumentasyon at mga halimbawang file:
Cutting Line - Programa para sa linear cutting
Bersyon: 2.49
Bit depth: 32bit
Tabletka: Gumaling
Kapag binuo ang algorithmic na bahagi ng mga programa, ang prinsipyo ng pag-minimize ng basura ay pinili bilang pangunahing criterion, at kapag binuo ang bahagi ng interface, hinahangad ng may-akda na gawing simple at maginhawa ang mga programa sa pang-araw-araw na paggamit.
Ang programa ng pinakamainam na pagputol ng mga linear na blangko sa mga bahagi
Ang programa ay may mga sumusunod na pag-andar at tampok:
Kasama sa aming listahan ng presyo ang tatlong produkto na nauugnay sa karaniwang tema ng pag-uuri at pag-optimize:
- Linear cutting program para sa mga profile at mahabang materyales
- Programa para sa dalawang-dimensional na pagputol ng salamin, sandwich, chipboard at iba pang mga sheet na materyales
- Route optimization program para sa paglutas ng mga problema sa logistik
Maaaring ibigay ang mga nesting module bilang bahagi ng pinagsamang solusyon na Windowsoft: Custom Production Management, at bilang magkahiwalay na mga programa. Kapag tumatawag sa mga cutting program mula sa 1C, walang pag-import ang kinakailangan - pag-export ng data sa mga intermediate na file. Gumagana ang gumagamit sa isang karaniwang interface, at ang lahat ng mga subtleties ng pakikipag-ugnayan ng 1C sa mga panlabas na optimizer ay nagsasagawa ng pagproseso ng pagpuno sa mga bahagi ng tabular. Para sa mga layunin ng accounting para sa mga balanse ng imbentaryo, business trimmings at mga materyales sa produksyon, karaniwang mga dokumento at mga rehistro ng mga tipikal na 1C configuration ay ginagamit.
Linear cutting (profile, pipe, log)
Nagbibigay ng porsyento ng pananim na nakumpirma ng imbentaryo
Live na demo sa site
Ang halimbawa sa ibaba ay hindi isang static na imahe, ngunit isang gumaganang web application.
Maaari mong simulan ang pagputol ng profile gamit ang pindutan Magsimula, itakda ang iyong mga sukat ng mga produkto at workpiece, baguhin ang mga setting ng pag-optimize at suriin ang solusyon.
Siyempre, ang optimizer sa browser ay mas mabagal kaysa sa katutubong programa, ngunit pinapayagan ka nitong makakuha ng mga resultang magagawa nang libre nang hindi kinakailangang mag-download at mag-install ng anuman sa iyong computer.
| 20000 r. | |
Pagputol ng mga materyales sa salamin at sheet
Bumubuo ng mga cutting chart na may pinakamataas na kalidad. Nagbibigay ng porsyento ng pagtitipid ng materyal na malapit sa teoretikal na limitasyon. Nahigitan ang mga sikat na Opty-Way, MaxCut, PerfectCut, Cutting, atbp. na mga programa ng 10-12% sa mga indicator tulad ng lugar ng mga hindi gumaganang nalalabi, ang kabuuang lugar ng materyal na pinuputol at ang bilang ng buong sheet ginamit
Ang lahat ng 2D nesting algorithm ay binuo ng OOO Programs of Cutting, Novosibirsk, developer: Shilyaev Vladimir Genrikhovich. Ang Oknosoft ay ang opisyal na dealer ng developer at, sa ilalim ng isang kasunduan sa sublicense, ay may karapatan na parehong ibenta ang program bilang isang hiwalay na produkto at gamitin ito bilang bahagi ng aming mga development
| 40000 r. | |
Bakit i-optimize ang nesting sa program?
Maraming mga customer ang nagsasabi: "Mayroon akong isang mahusay na sawer. Siya ay perpektong pinutol ang salamin at ang profile sa ulo. Tanging mga tatsulok ang nakakapasok sa basurahan."
Kadalasan, ito ay totoo. Kasabay nito, ang isa sa mga gawain ng pinuno ay upang ayusin ang isang mahuhulaan na proseso, ang katatagan nito ay hindi nakasalalay sa henyo ng mga gumaganap. Ang software cut optimization batay sa production plan ay isa sa mga hakbang na nagpapalapit sa layuning ito.
Kung ipagpalagay natin na ang isang tao ay maaaring dumaan sa mas maraming kumbinasyon sa kanyang ulo kaysa sa isang computer sa parehong yugto ng panahon, ang ~1% na cutoff coefficient na nakuha sa pamamagitan ng awtomatikong pagputol ay magiging mas kaakit-akit kaysa sa hindi nakokontrol at hindi pinamamahalaang 1% na maaaring ibigay ng Genius. Ang paglilipat ng mga gawain sa pag-optimize sa programa ay maaaring magbakante ng karagdagang oras (1-2 oras sa isang araw), na gagastusin niya para sa kapakinabangan ng negosyo.
Sa katunayan, ang sitwasyon sa pag-trim sa karamihan ng mga negosyo ay mas malala. Ang mga koepisyent ng pagkakasunud-sunod ng 4-7% ay inilatag sa detalye, at kung ang pagawaan ay gumagana sa 3-5% na pag-trim, ito ay itinuturing na isang magandang resulta. Ang 3-5% na pagbawas sa aktwal na crop factor ay 30-50 thousand rubles na na-save para sa bawat milyon na ginugol sa mga materyales. Gayunpaman, gagawin nitong posible na huwag isama ang mga dagdag na rubles sa nakaplanong gastos at mag-alok sa mamimili ng mas kanais-nais na mga presyo.
Ang problema ng pinakamainam na pagkonsumo ng mga materyales ay binubuo ng ilang bahagi.
Accounting sa bodega ng mga sinusukat na materyales
Depende sa mga katangian ng negosyo, ang mga customer ay gumagamit ng ilang mga scheme ng accounting para sa mga materyales:
- Batay sa plano ng produksyon, ang mga kinakailangan ay nabuo - mga invoice na nagpapahiwatig ng mga produkto. Ang pagpapalabas ng mga karagdagang materyales (hindi sapat) ay makikita sa magkahiwalay na mga dokumento. Ang indikasyon ng mga produkto sa mga dokumentong ito ay kanais-nais, ngunit hindi isang kinakailangang kondisyon. Sa kasong ito, ang mga materyales lamang na nasa mga pagtutukoy ng mga produktong ginawa ngayon at sa kinakailangang dami lamang ang ibinibigay sa workshop. Ang kawalan ng diskarteng ito ay ang pangangailangan na gumuhit ng higit pang mga dokumento at ang kakulangan ng isang stock ng mga materyales sa mga site (marahil ito ay isang kalamangan?)
- Mga Kinakailangan - ang mga invoice ay nabuo nang hindi magkakasabay, nang walang sanggunian sa plano ng produksyon, batay sa mga kahilingan ng mga masters. Ang diskarte na ito ay nagbibigay-daan sa iyo upang makakuha ng isang "live na bodega" na may kaunting gastos sa operator para sa storekeeper, ngunit hindi nagpoprotekta laban sa labis na paggastos ng mga materyales. Ang buong responsibilidad para sa pagsunod ng pagkonsumo sa mga pagtutukoy ay nakasalalay sa kasong ito sa mga master at manggagawa. Ang pagsusuri sa gastos ng plan-fact ay magpapakita ng mga paglihis, ngunit maaaring huli na
Accounting para sa business trim
Posible ito sa isang senaryo kung saan ang mga kinakailangan - ang mga invoice ay nabuo batay sa plano ng produksyon. Ang natitirang bahagi ng business trimming sa simula ng pagputol ay kinuha mula sa isang espesyal na rehistro at maaaring iakma ng operator alinsunod sa aktwal na balanse. Kapag nagsasagawa ng pagtatalaga sa produksyon, ang data sa dami ng mga materyales na kailangang matanggap mula sa bodega ay inilalagay sa mga kinakailangan - mga invoice, at ang data sa resultang trim ng negosyo ay idinagdag pabalik sa rehistro.
Interaksyon ng mga gumaganap
Kapag nagpapasya kung gagamitin ang nesting optimizer, isaalang-alang ang:
- Sa awtomatikong pagputol, imposibleng ayusin ang hinang (pagpupulong) ng mga produkto "mula sa ilalim ng saw", dahil ang mga segment na nauugnay sa isang produkto ay "kakalat" sa buong mapa ng pag-optimize
- Ang ikot ng produksyon ay nagpapahaba, kinakailangan upang ayusin ang isang pool para sa pag-iimbak ng mga blangko. Ang isang kompromiso ay pagputol sa mga batch ng 30 - 50 piraso. Kasabay nito, ang mataas na mga rate ng pagputol ay nakakamit at isang pare-parehong pag-load ng mga lugar ng hinang at mga kabit ay nakuha.
- Nababawasan ang kahusayan kung saan makakatugon ang shop sa mga pagbabago sa plano. Kung kailangan ng isang manager na i-wedge ang isang bagong produkto sa plano ngayon, ito ay magpapalala sa mga resulta ng pag-optimize.
Linear cutting software
Bersyon: 2.49
Nag-develop: Shibaev Yury Anatolyevich Ukraine, Cherkasy
Site ng developer: http://www.cuttinghome.com/
Bit depth: 32bit
Tugma sa Windows 7: oo
Wika ng interface: English + Russian
Tabletka: Gumaling
Mga Kinakailangan sa System: Minimum
Paglalarawan: Ang CUTTING program ay idinisenyo para sa pinakamainam na pagputol ng materyal sa mga linear na bahagi. Maaaring gamitin ang programa sa woodworking, paggawa ng muwebles, pagputol ng metal, pagputol ng salamin, atbp. Ang mga programa ay batay sa isang natatanging, high-speed algorithm na nagbibigay-daan sa iyo upang mabilis na mag-cut na may kaunting basura.
 |
Kapag binuo ang algorithmic na bahagi ng mga programa, ang prinsipyo ng pag-minimize ng basura ay pinili bilang pangunahing criterion, at kapag binuo ang bahagi ng interface, hinahangad ng may-akda na gawing simple at maginhawa ang mga programa sa pang-araw-araw na paggamit.
Ang programa ay may mga sumusunod na pag-andar at tampok:
. pagtatakda ng arbitrary na bilang ng mga workpiece at mga segment na puputulin
. pagtatakda ng mga blangko at mga segment ayon sa ilang mga katangian, halimbawa, pangalan at kulay
. pagkalkula na isinasaalang-alang ang uri ng materyal (pangalan ng materyal, kulay)
. pagtatakda ng lapad ng cutting tool
. pagkalkula ng kabuuang haba ng mga segment at nalalabi
. pagtatakda ng iba't ibang mga mode ng pagputol
. pagpapanumbalik ng mga dating pugad ng kasalukuyang session
. pag-save ng mga tinukoy na workpiece at cut bilang mga detalye
. pagdaragdag ng naka-save na BOM sa isang bagong opsyon sa pagsusuri
. pag-save ng pugad sa isang file na may posibilidad ng pagbawi sa ibang pagkakataon
. pagtingin at pag-print ng mga resulta ng pagputol, parehong sa graphical at tabular form
. kumpletong sistema ng impormasyon ng sanggunian.
Kasama sa aming listahan ng presyo ang tatlong produkto na nauugnay sa karaniwang tema ng pag-uuri at pag-optimize:
- Linear cutting program para sa mga profile at mahabang materyales
- Programa para sa dalawang-dimensional na pagputol ng salamin, sandwich, chipboard at iba pang mga sheet na materyales
- Route optimization program para sa paglutas ng mga problema sa logistik
Maaaring ibigay ang mga nesting module bilang bahagi ng pinagsamang solusyon na Windowsoft: Custom Production Management, at bilang magkahiwalay na mga programa. Kapag tumatawag sa mga cutting program mula sa 1C, walang pag-import ang kinakailangan - pag-export ng data sa mga intermediate na file. Gumagana ang gumagamit sa isang karaniwang interface, at ang lahat ng mga subtleties ng pakikipag-ugnayan ng 1C sa mga panlabas na optimizer ay nagsasagawa ng pagproseso ng pagpuno sa mga bahagi ng tabular. Para sa mga layunin ng accounting para sa mga balanse ng imbentaryo, business trimmings at mga materyales sa produksyon, karaniwang mga dokumento at mga rehistro ng mga tipikal na 1C configuration ay ginagamit.
Linear cutting (profile, pipe, log)
Nagbibigay ng porsyento ng pananim na nakumpirma ng imbentaryo<1%. Ряд клиентов приобрели наши алгоритмы для замены программ оптимизации, поставлявшихся производителями отрезных станков. В программе использован алгоритм плотной укладки и генетический алгоритм поиска решения. На вход поступают данные о количестве и размерах изделий и деловых отходов. На выходе формируются карты раскроя с указанием тележек и ячеек. При необходимости, формируются файлы для обрабатывающих центров, станков с ЧПУ и этикетки с подробной информацией об отрезаемой заготовке и примыкающих элементах.
Live na demo sa site
Ang halimbawa sa ibaba ay hindi isang static na imahe, ngunit isang gumaganang web application.
Maaari mong simulan ang pagputol ng profile gamit ang pindutan Magsimula, itakda ang iyong mga sukat ng mga produkto at workpiece, baguhin ang mga setting ng pag-optimize at suriin ang solusyon.
Siyempre, ang optimizer sa browser ay mas mabagal kaysa sa katutubong programa, ngunit pinapayagan ka nitong makakuha ng mga resultang magagawa nang libre nang hindi kinakailangang mag-download at mag-install ng anuman sa iyong computer.
| 20000 r. | |
Pagputol ng mga materyales sa salamin at sheet
Bumubuo ng mga cutting chart na may pinakamataas na kalidad. Nagbibigay ng porsyento ng pagtitipid ng materyal na malapit sa teoretikal na limitasyon. Nahigitan ang mga sikat na Opty-Way, MaxCut, PerfectCut, Cutting, atbp. na mga programa ng 10-12% sa mga indicator tulad ng lugar ng mga hindi gumaganang nalalabi, ang kabuuang lugar ng materyal na pinuputol at ang bilang ng buong sheet ginamit
Ang lahat ng 2D nesting algorithm ay binuo ng OOO Programs of Cutting, Novosibirsk, developer: Shilyaev Vladimir Genrikhovich. Ang Oknosoft ay ang opisyal na dealer ng developer at, sa ilalim ng isang kasunduan sa sublicense, ay may karapatan na parehong ibenta ang program bilang isang hiwalay na produkto at gamitin ito bilang bahagi ng aming mga development
| 40000 r. | |
Bakit i-optimize ang nesting sa program?
Maraming mga customer ang nagsasabi: "Mayroon akong isang mahusay na sawer. Siya ay perpektong pinutol ang salamin at ang profile sa ulo. Tanging mga tatsulok ang nakakapasok sa basurahan."
Kadalasan, ito ay totoo. Kasabay nito, ang isa sa mga gawain ng pinuno ay upang ayusin ang isang mahuhulaan na proseso, ang katatagan nito ay hindi nakasalalay sa henyo ng mga gumaganap. Ang software cut optimization batay sa production plan ay isa sa mga hakbang na nagpapalapit sa layuning ito.
Kung ipagpalagay natin na ang isang tao ay maaaring dumaan sa mas maraming kumbinasyon sa kanyang ulo kaysa sa isang computer sa parehong yugto ng panahon, ang ~1% na cutoff coefficient na nakuha sa pamamagitan ng awtomatikong pagputol ay magiging mas kaakit-akit kaysa sa hindi nakokontrol at hindi pinamamahalaang 1% na maaaring ibigay ng Genius. Ang paglilipat ng mga gawain sa pag-optimize sa programa ay maaaring magbakante ng karagdagang oras (1-2 oras sa isang araw), na gagastusin niya para sa kapakinabangan ng negosyo.
Sa katunayan, ang sitwasyon sa pag-trim sa karamihan ng mga negosyo ay mas malala. Ang mga koepisyent ng pagkakasunud-sunod ng 4-7% ay inilatag sa detalye, at kung ang pagawaan ay gumagana sa 3-5% na pag-trim, ito ay itinuturing na isang magandang resulta. Ang 3-5% na pagbawas sa aktwal na crop factor ay 30-50 thousand rubles na na-save para sa bawat milyon na ginugol sa mga materyales. Gayunpaman, gagawin nitong posible na huwag isama ang mga dagdag na rubles sa nakaplanong gastos at mag-alok sa mamimili ng mas kanais-nais na mga presyo.
Ang problema ng pinakamainam na pagkonsumo ng mga materyales ay binubuo ng ilang bahagi.
Accounting sa bodega ng mga sinusukat na materyales
Depende sa mga katangian ng negosyo, ang mga customer ay gumagamit ng ilang mga scheme ng accounting para sa mga materyales:
- Batay sa plano ng produksyon, ang mga kinakailangan ay nabuo - mga invoice na nagpapahiwatig ng mga produkto. Ang pagpapalabas ng mga karagdagang materyales (hindi sapat) ay makikita sa magkahiwalay na mga dokumento. Ang indikasyon ng mga produkto sa mga dokumentong ito ay kanais-nais, ngunit hindi isang kinakailangang kondisyon. Sa kasong ito, ang mga materyales lamang na nasa mga pagtutukoy ng mga produktong ginawa ngayon at sa kinakailangang dami lamang ang ibinibigay sa workshop. Ang kawalan ng diskarteng ito ay ang pangangailangan na gumuhit ng higit pang mga dokumento at ang kakulangan ng isang stock ng mga materyales sa mga site (marahil ito ay isang kalamangan?)
- Mga Kinakailangan - ang mga invoice ay nabuo nang hindi magkakasabay, nang walang sanggunian sa plano ng produksyon, batay sa mga kahilingan ng mga masters. Ang diskarte na ito ay nagbibigay-daan sa iyo upang makakuha ng isang "live na bodega" na may kaunting gastos sa operator para sa storekeeper, ngunit hindi nagpoprotekta laban sa labis na paggastos ng mga materyales. Ang buong responsibilidad para sa pagsunod ng pagkonsumo sa mga pagtutukoy ay nakasalalay sa kasong ito sa mga master at manggagawa. Ang pagsusuri sa gastos ng plan-fact ay magpapakita ng mga paglihis, ngunit maaaring huli na
Accounting para sa business trim
Posible ito sa isang senaryo kung saan ang mga kinakailangan - ang mga invoice ay nabuo batay sa plano ng produksyon. Ang natitirang bahagi ng business trimming sa simula ng pagputol ay kinuha mula sa isang espesyal na rehistro at maaaring iakma ng operator alinsunod sa aktwal na balanse. Kapag nagsasagawa ng pagtatalaga sa produksyon, ang data sa dami ng mga materyales na kailangang matanggap mula sa bodega ay inilalagay sa mga kinakailangan - mga invoice, at ang data sa resultang trim ng negosyo ay idinagdag pabalik sa rehistro.
Interaksyon ng mga gumaganap
Kapag nagpapasya kung gagamitin ang nesting optimizer, isaalang-alang ang:
- Sa awtomatikong pagputol, imposibleng ayusin ang hinang (pagpupulong) ng mga produkto "mula sa ilalim ng saw", dahil ang mga segment na nauugnay sa isang produkto ay "kakalat" sa buong mapa ng pag-optimize
- Ang ikot ng produksyon ay nagpapahaba, kinakailangan upang ayusin ang isang pool para sa pag-iimbak ng mga blangko. Ang isang kompromiso ay pagputol sa mga batch ng 30 - 50 piraso. Kasabay nito, ang mataas na mga rate ng pagputol ay nakakamit at isang pare-parehong pag-load ng mga lugar ng hinang at mga kabit ay nakuha.
- Nababawasan ang kahusayan kung saan makakatugon ang shop sa mga pagbabago sa plano. Kung kailangan ng isang manager na i-wedge ang isang bagong produkto sa plano ngayon, ito ay magpapalala sa mga resulta ng pag-optimize.
Mga programa para sa pag-optimize ng pagputol ng materyal
Kasama sa catalog na ito ang mga link sa ilang mga domestic computer program para sa pag-optimize ng pagputol ng materyal.at ilang publikasyon sa paksang ito.Ang paraan ng pag-optimize ng pagputol ng materyal ay batay sa gawaing "Pagkalkula ng makatwirang pagputol ng mga pang-industriyang materyales", 1951, na isinulat ng mga siyentipiko ng Sobyet na sina LV Kantorovich at VA Zalgaller, kung saan ang mga linear programming algorithm ay sistematikong ipinakita, at pati na rin ang dynamic na programming para sa problema ay inilarawan. tungkol sa pagputol at pagsasama nito sa mga linear programming algorithm.
Ang isang malaking bilang ng mga programa sa pag-optimize sa paggupit ay binuo sa mundo, parehong sa pangkalahatan at mga espesyal na lamang. Nasa ibaba ang mga link sa mga program na magagamit para sa pag-download mula sa mga website ng mga developer. Mayroon ding mga paglalarawan sa kanila.
pagputol
ang programa ay idinisenyo para sa awtomatikong pagsasama-sama ng pinakamainam na pagputol ng mga mapa para sa mga sheet at roll na materyales,
site ng developer http://picaro.ru
Pagputol ng Astra
ang programa ay idinisenyo upang i-optimize ang pagputol ng mga materyales sa sheet ( particle board, metal, salamin at plastik ). Nagbibigay ang Astra Nesting ng mabilis na input ng impormasyon tungkol sa mga order at materyales; awtomatiko at manu-manong henerasyon ng mga cutting chart; buong accounting ng dimensional residues at ang kanilang pagputol sa kasunod na mga order; pag-imprenta ng mga cutting chart at mga detalye. Binayaran
site ng developer http://www.astrapro.ru Batayan-pagputol
isang programa para sa awtomatikong paglikha ng mga mapa para sa pagputol ng materyal na sheet, na pinagsasama ang pinakamainam na lokasyon ng mga contour ng mga hugis-parihaba na bahagi sa ibinigay na mga sukat ng pinagmumulan ng materyal na may mataas na bilis ng pagkalkula. Ito ay isang mahalagang bahagi ng Basis - Constructor - Furniture Maker complex. May bayad, available ang demo
site ng developer http://www.bazissoft.ru Pagputol
ang mga programa ng pamilyang CUTTING ay idinisenyo para sa pinakamainam na pagputol ng materyal sa hugis-parihaba o linear na mga bahagi. Maaaring gamitin ang mga programa sa woodworking, paggawa ng muwebles, pagputol ng metal, pagputol ng salamin, atbp. Ang mga programa ay batay sa isang natatanging, high-speed algorithm na nagbibigay-daan sa iyo upang mabilis na mag-cut na may kaunting basura. May bayad, available ang demo
site ng developer http://www.cuttinghome.com
linya ng pagputol
ang programa ay idinisenyo para sa pinakamainam na pagputol ng mga linear na blangko sa mga linear na segment na may iba't ibang haba at maaaring gamitin sa woodworking at pulp at papel na industriya, metalworking, paggawa ng damit, atbp. May bayad, available ang demo
site ng developer http://www.cuttinghome.com
Ang PaneCut ay isang programa para sa pag-optimize ng pagputol ng mga sheet at linear na materyales, na nagpapahintulot sa iyo na makabuluhang bawasan ang porsyento ng mga basurang materyales na ginamit.May bayad, available ang demo
site ng developer http://www.vsgroup.ua
NCL- P Programa ng awtomatikong pagputol ng sheet na materyal para sa mga detalye ng anumang pagsasaayos. Developer Polevov A.V.Libre
website ng programa http://freesoft.ru/ncl_v13
Pinakamainam
programa para sa pinakamainam na pagputol ng mga materyales sa mga hugis-parihaba na bahagi.Shareware
site ng developer http://wincad.ru
Bazis Furniture Maker
isang kumplikadong magkakaugnay na mga programa na nagbibigay-daan sa iyo upang epektibong ayusin ang indibidwal o serial na paggawa ng mga kasangkapan sa cabinet sa anumang negosyo: mula sa mga higanteng kasangkapan hanggang sa mga indibidwal na negosyante. Ang komposisyon ng system: Basis-Furniture Maker (basic), Basis-Cutting, Basis-Estimate, Basis-Interior.May bayad, available ang demo
site ng developer http://www.bazissoft.ru
bCAD-tagagawa ng muwebles
isang espesyal na pakete ng software na idinisenyo para sa disenyo at paghahanda ng paggawa ng mga kasangkapan sa kabinet. Kasama sa package ang pangunahing bCAD module, na pupunan ng mga partikular na tool. Binibigyang-daan ka ng Nesting application na awtomatikong lumikha ng nesting map para sa mga detalye ng mga natanggap na modelo. Kapag pumili ka ng materyal, awtomatikong nag-aalok ang application ng isang listahan ng mga bahagi mula sa napiling materyal na naroroon sa proyekto. Ang mga parameter ng mga sheet na ginamit, ang direksyon ng unang nakita, ang bilang ng mga hanay ay nakatakda. Pinapayagan ka ng application na isaalang-alang ang mga nalalabi sa pagputol, i-save ang kanilang mga parameter at gamitin ang mga ito sa hinaharap.
site ng developer http://bcad-ug.ru
Hindi mahirap maghanap ng iba pang katulad na mga programa sa net, kasama. libre
Teorya at kasanayan ng awtomatikong pagputol ng mga materyales sa paggawa ng mga kasangkapan sa gabinete. Bunakov P.Yu., Kaskevich N.V., Kolomna: GOSGI, 2010. 170 p.
Pag-optimize ng pagputol ng materyal sa mechanical engineering: aklat-aralin / S.I. Vdovin, O.E. Sinabi ni Jur. - Agila: OSU na pinangalanang I. S. Turgenev, 2016. - 45 p.
V.A. Skaternoy "Pag-optimize ng mga materyales sa pagputol sa magaan na industriya" ed. Industriya ng pananamit. Legprombytizdat, 1989,- 144 s
OPTIMIZATION NG SHEET MATERIAL CUTTING SA MGA PAREKTONG NG IBA'T IBANG LAKI
Giniatullina Regina Airatovna
1st year master's student, Department of Applied Mathematics and Informatics, KNRTU. A.N. Tupolev, Russian Federation, Kazan
Email:Regina[email protected] yandex. en
Galiev Shamil Ibrahimovich
siyentipikong tagapayo, Dr. tech. Sci., Propesor ng ITKiI KNRTU im. A.N. Tupolev, Russian Federation, Kazan
Ang guillotine cutting ng bakal at iba pang mga sheet ay malawakang ginagamit sa mechanical engineering at iba pang industriya. Ang nesting na ito ay talagang ang gawain ng pag-iimpake ng mga parisukat na may iba't ibang laki sa isang ibinigay na sheet gamit ang guillotine procedure. Mahalagang bawasan ang basura ng sheet. Ang interes sa mga problema sa packaging ay ipinaliwanag sa pamamagitan ng kanilang mahusay na praktikal na kahalagahan. Bilang isang patakaran, ang mga naturang gawain ay nauugnay sa mga industriyang masinsinang materyal, kung saan ang isa sa mga pangunahing kadahilanan sa pagbawas ng gastos ng mga produkto ay ang makatwirang paggamit ng mga mapagkukunan. Ang gawaing ito ay may malawak na hanay ng mga praktikal na aplikasyon sa mga industriyang iyon kung saan ang mga gawain sa packaging (pagputol) ay tradisyonal na umuusbong sa mechanical engineering, woodworking, light at construction na mga industriya. .
1. Balik-aral ayon sa gawain
Sa industriya, sa paggawa ng iba't ibang uri ng mga produkto ng pagtatapos, lumitaw ang problema ng mahusay na pagputol ng mga sheet ng mga ibinigay na laki sa mga hugis-parihaba na blangko. Ang gawaing ito ay ang mga sumusunod: ang mga sukat ng mga parisukat, ang laki ng sheet ay kilala. Kinakailangan na ilagay ang ibinigay na mga parisukat sa sheet nang hindi magkakapatong sa isa't isa upang posible na i-cut ang sheet na may guillotine. Ang paggupit ng guillotine ay nauunawaan bilang pagputol, na ipinatupad sa pamamagitan ng pagkakasunod-sunod ng mga through cut na kahanay sa mga gilid ng materyal. Bilang karagdagan, ang mga parisukat na ito ay dapat na orthogonally na nakaimpake nang walang pag-ikot, iyon ay, para sa bawat napiling elemento ng uri , ang gilid na may taas ay dapat na kahanay sa gilid ng sheet na may taas. H. Isasaalang-alang namin ang problema ng pag-iimpake ng mga parisukat na may iba't ibang laki sa isang rektanggulo. Lutasin natin ang problemang ito gamit ang isang eksaktong algorithm. Ito ay batay sa isang recursive na pamamaraan na nagpapatakbo ng branch-and-bound algorithm (na titingnan din natin) nang paulit-ulit na may iba't ibang mga input upang matukoy ang pinakamainam na halaga ng solusyon.
2. Layunin ng proyekto
Ang layunin ng gawaing ito ay pag-aralan at ipatupad ang isang algorithm na may kakayahang maghanap ng mga solusyon para sa pagpapakete ng mga parisukat sa isang parihaba. Ang problemang isinasaalang-alang ay malawakang ginagamit sa iba't ibang industriya: mechanical engineering, woodworking, light at construction industry.
Kinakailangan na ipatupad ang posibilidad na ipakita ang resulta na nakuha sa anyo ng mga parisukat ng iba't ibang laki na nakasulat sa isang parihaba at ang kaukulang karagdagang impormasyon na kinakailangan ng gumagamit. Halimbawa, tulad ng: oras ng pagpapatakbo ng algorithm, iba't ibang impormasyon ng error, atbp.
3. Pangkalahatang mga kinakailangan
1) Manu-manong pagtatakda ng mga sukat ng sheet-rectangle (lapad at taas) kung saan ilalagay ang mga parisukat;
2) Manu-manong pag-input ng mga parisukat na laki (maaari silang pareho o magkaiba);
3) Visual na pagsusuri ng mga resulta ng pagpapatupad ng algorithm (na may output ng may-katuturang impormasyon: oras ng pagpapatupad ng algorithm, ang bilang ng mga parisukat ng isang tiyak na laki na nakasulat sa isang rektanggulo);
4) Pag-save ng impormasyon tungkol sa naipasok na mga parisukat sa isang file.
4. Kaugnayan ng problema
Ang pangunahing layunin ng idinisenyong sistema ay ang pagsunod sa pangunahing square packing algorithm at kadalian ng paggamit ng end user, fault tolerance.
Ang mga gawain at pag-andar ng dinisenyong sistema ay dapat sumunod sa mga kinakailangan.
Ang algorithm na iminungkahi sa papel na ito ay maaaring magamit upang mahusay na malutas ang problema ng pag-iimpake ng mga parisukat sa isang hugis-parihaba na lugar ng mga ibinigay na sukat. Ang problemang ito ay may malawak na hanay ng mga praktikal na aplikasyon sa mga industriyang iyon kung saan ang mga gawain sa pag-cut-pack ay tradisyonal na umuusbong. Ang itinuturing na algorithm ay maaaring gamitin sa mga praktikal na kalkulasyon at kasama sa mga automated na disenyo at mga control system. Masasabi rin na ang problema ay may kaugnayan sa sandaling ito, dahil may pangangailangan na mag-pack ng mga parisukat sa isang parihaba at ang pangangailangan na ito ay hindi kailanman magwawakas, na nangangahulugan na ang problema ay palaging may kaugnayan.
Ang mga problema sa pagputol-packing ay sumasakop sa isang mahalagang lugar sa modernong combinatorial optimization at nakakaakit ng pansin ng maraming mga siyentipiko, kapwa sa Russia at sa ibang bansa.
Ang interes sa mga problema sa pag-cut-packing ay ipinaliwanag, sa partikular, sa pamamagitan ng kanilang mahusay na praktikal na kahalagahan. Bilang isang patakaran, ang mga aplikasyon ng pag-cut-pack ay nauugnay sa mga industriyang masinsinang materyal, kung saan ang isa sa mga pangunahing kadahilanan para sa pagbawas ng gastos ng mga produktong gawa ay ang makatwirang paggamit ng mga mapagkukunan.
5. Umiiral nang cutting system.
Mayroong maraming mga produkto ng software para sa pagputol ng materyal na sheet, tulad ng ORION, ASTRA CUTTING, TEHTRAN. Isaalang-alang natin ang isa sa mga ito sa halimbawa ng TEHTRAN.
Para sa mga negosyo na gumagamit ng mga thermal cutting machine, ang pagpapakilala ng mga modernong teknolohiya ng impormasyon ay isa sa mga pinaka-kagyat na gawain. Malinaw na ang pagbawas ng oras para sa paghahanda ng mga programa sa pagputol, ang pinakamainam na paglalagay ng mga bahagi sa sheet, at ang mas mababang pagkonsumo ng materyal ay tiyak na makakaapekto sa gastos at kalidad ng mga produkto.
Bagong produkto ng software Techtran / Pagputol umaakma sa linya ng mga programa ng pamilya Techtran at nilayon para sa pagdidisenyo ng mga programa para sa pagputol ng materyal na sheet. Ang mga kakayahan ng sistema ng CAM ay pinagsama dito sa mga pag-andar ng pag-aayos ng proseso ng produksyon. Ang diskarte sa solusyon na ginamit sa programa ay nagbubuod sa karanasan ng isang bilang ng mga negosyo na nagpapatakbo ng mga thermal cutting machine. Ang gawain ay upang mabilis na ayusin ang mga bahagi sa mga sheet sa isang pinakamainam na paraan at makakuha ng mga programa ng kontrol para sa pagputol ng mga bahaging ito ayon sa gawain ng pagputol, na binubuo ng mga katawagan ng mga napiling bahagi at ang kanilang dami para sa bawat item. Ang mga basura sa negosyo na natitira pagkatapos ng trabaho ay dapat na itala sa database ng system para sa karagdagang paggamit.
6. Pormalisasyon ng problema at pagbuo ng isang modelo ng matematika
Nagpapakita kami ng isang modelo ng matematika ng problema, kasunod ng gawain.
Ang branch-and-bound algorithm ay batay sa integer linear programming (ILP) na modelo. Para sa kapakanan ng pagiging simple sa pagbabalangkas na ito, ipinapalagay namin na ang bawat elemento ay naiiba, iyon ay, para sa bawat uri j parihaba, tinutukoy namin ang magkaparehong mga elemento na may lapad , taas at nakuha . Hayaang (1) ang kabuuang bilang ng mga elemento. Para sa bawat elemento k ipinakilala namin ang isang binary variable na kumukuha ng halaga 1 kung at kung ang elemento lamang k kasama sa pinakamainam na solusyon. Ang modelo ng ILP para sa pangkalahatang problema sa dalawang-dimensional na knapsack ay ang mga sumusunod:
|
|
||
|
|
||
|
|
kung saan: - ang mga sukat ng nakasulat na parisukat,
Ang mga sukat ng parihaba mismo,
U- anumang upper bound sa halaga ng pinakamainam na solusyon, at C nagsasaad ng hanay ng lahat ng mga subset ng mga elemento na hindi maaaring ilagay sa guillotine sa isang sheet. Para sa halaga ng threshold U ginagamit namin , iyon ay, ang halaga ng pinakamainam na solusyon para sa dalawang-dimensional na knapsack na problema, na tumutugma sa pagpapasimple ayon sa kung saan ang guillotine constraints ay tinanggal. Tandaan na ang mga paghihigpit (3) at (4) ay kalabisan, ngunit idinagdag sa pormulasyon upang palakasin ito. Nilulutas ng aming algorithm ang isang pinasimpleng problema kung saan ang mga hadlang (5) ay inaalis at kung ang kasalukuyang solusyon ay wasto o hindi ay sinusuri sa pamamagitan ng paglutas sa sumusunod na problema sa paghihiwalay: ang lahat ng mga elemento ay mula sa 
magkasya sa sheet na may guillotine approach? Kung ang sagot ay positibo, kung gayon ang pinakamainam na solusyon ng pangkalahatang two-dimensional na knapsack na problema ay matatagpuan. Kung hindi, may makikitang bagong nilabag na hadlang, at mauulit ang proseso.
Ang diskarte na ito ay katulad ng pamamaraan na iminungkahi nina Caprara at Monasi para sa eksaktong solusyon ng problema sa 2D knapsack at ayon kay Piesinger at Sigard para sa paglutas ng pangkalahatang problema sa 2D knapsack mismo. Mas tiyak, ang modelo (2)-(6) ay nalutas sa pamamagitan ng isang espesyal na sangay at nakatali na pamamaraan kung saan ang mga elemento ay iniutos. Ang upper bounds ay nakuha mula sa LP relaxation ng problema (2)-(3) gamit ang Martello at Toth upper bound. Ang reverse pass ay nangyayari kapag ang upper bound ay hindi lalampas sa kasalukuyang solusyon, o kapag ang ilang mga hadlang (3)-(5) ay nilabag.
Sa problema 2-6, hindi isinasaalang-alang na ang pagputol ay guillotine. Isinasaalang-alang ang lahat ng mga kondisyon, isinasaalang-alang namin ang isang recursive na paraan ng solusyon.
7. Paraan ng solusyon
Sa subsection na ito, isinasaalang-alang namin ang isang recursive na pamamaraan para sa pag-enumerate ng dalawang-dimensional na guillotine packing. Sa isang pamamaraan na tinatawag na recursive, tinutukoy namin ang bawat wastong pag-aayos ng isang subset ng mga elemento sa isang dahon bilang isang wastong pag-iimpake. Ang bawat wastong packing ay maaaring katawanin bilang isang non-negative na integer vector, kung saan ang bawat coordinate 
kumakatawan sa bilang ng mga elemento ng uri sa pakete. Tukuyin bilang 
pag-iimpake ng kita. Sinasabi namin na ang pinahihintulutang pag-iimpake ay pinakamataas kung walang karagdagang mga elemento ang maaaring i-pack sa isang sheet, ibig sabihin, pag-iimpake 
lumalabas na hindi magagawa para sa lahat ng uri ng elemento, upang . Para sa dalawang wastong pakete at 
Tinukoy namin ang bagong packaging tulad ng sumusunod: 
, .
Ang recursive procedure ay tahasang binibilang ang lahat ng valid na packing sa pamamagitan ng recursively paghahati ng sheet sa dalawang bahagi sa pamamagitan ng isang (pahalang o patayong) guillotine cut. Kinukuha ng procedure bilang input ang parameter , na siyang lower bound sa tubo ng anumang admissible (guillotine) packing.
Tulad ng nabanggit nina Christodes at Whitlog, para sa anumang dalawang-dimensional na problema sa pag-iimpake ay may pinakamainam na solusyon na tumutugma sa isang normal na pattern, iyon ay, isang solusyon kung saan, para sa anumang naka-pack na elemento, ang kaliwang bahagi nito ay katabi ng alinman sa kanang bahagi ng isa pa. elemento o kanang bahagi ng sheet. Nangangahulugan ito na maaari lamang nating isaalang-alang ang mga vertical cut, ayon sa mga coordinate , na maaaring makuha bilang kumbinasyon ng mga lapad ng elemento, ibig sabihin, na nabibilang sa set:
Sa katulad na paraan, isinasaalang-alang lamang namin ang mga pahalang na seksyon, kasama ang mga coordinate kabilang sa sumusunod na hanay:
Ipinapalagay namin na ang mga elemento ng parehong set at ay pinagsunod-sunod sa pataas na pagkakasunud-sunod at set at .
Dahil sa at at isang limitasyon ng desisyon , hayaan ang hanay ng lahat ng magagawa (pinahihintulutan) na mga packing ng mga ibinigay na elemento sa isang sheet ng laki , na maaaring makagawa (kasama ang mga natitirang elemento at sheet) ng tubo na mas malaki kaysa o katumbas ng . Para sa dalawang ibinigay na kasiya-siyang packing 
At 
pormal naming tinutukoy ng pairwise na kabuuan ng mga packing sa mga set at :
Intuitively, ay ang hanay ng mga packing na maaaring makuha sa pamamagitan ng pagsasama ng anumang packing sa anumang packing , anuman ang laki ng mga set at . Malinaw na kapag natukoy na ang set ay makakahanap tayo ng mga set na may kondisyon na ang lahat ng (ayon sa pagkakabanggit ) na mga elemento ay nabibilang sa isang ordered set (ayon sa pagkakabanggit). Sa katulad na paraan, ang kaalaman sa isang set ay nagpapahintulot sa amin na tukuyin ang mga set. Sa katunayan, ito ay sapat na upang tandaan na ang bawat pakete 
, na maaaring makabuo ng tubo na hindi bababa sa katumbas ng , sa parihaba , ay maaaring makuha bilang kabuuan ng dalawang pinapayagang packing na tinukoy para sa mas maliit na parihaba. Pormal na: , kahit saan 
At 
para sa ilan, o 
At 
para sa ilang . Kaya, ang pag-alam at para sa bawat isa at , madali nating makuha (bumuo) sa isang recursive na paraan .
Ang pangunahing algorithm ay maaaring mapabuti tulad ng sumusunod. Para sa bawat pakete sa isang sheet ng lapad at taas , isang upper bound, halimbawa, para sa maximum na tubo, ay maaaring makuha kapag ang natitirang lugar ay kinakalkula. Sa layuning ito, isaalang-alang ang mga halimbawa ng mga backpack na may kapasidad na , ang mga uri ng elementong posible sa mga kopya, bawat isa ay may kita at timbang . Ang pinakamainam na solusyon mula sa kasong ito, o anumang upper bound sa halagang ito, ay nagbibigay ng upper bound sa pinakamataas na kita na maaaring makuha sa pamamagitan ng pag-pack ng natitirang mga elemento sa natitirang bahagi ng sheet. Ito ay malinaw na ang lahat ng mga elemento tulad na 
maaaring alisin mula sa set dahil hindi sila maaaring humantong sa isang magagawa na solusyon na may tubo na mas malaki kaysa sa . Sa aming pagpapatupad, kinakalkula namin ang halaga ng upper bound sa pinakamainam na solusyon ng (one-dimensional) na kaso ng problema sa knapsack (tingnan). Ang mga halaga ng itaas na mga hangganan at nakuha ng Haifi at ang parehong mga halaga na iminungkahi nina Yang-Gun at Kang para sa dalawang-dimensional (orthogonal) knapsack na problema nang walang mga hadlang, ginagamit namin ang pinakamababa sa mga halagang ito bilang ang itaas nakagapos.
Bilang karagdagan, tandaan na ang lapad at taas ng sheet ay maaaring bawasan sa at , ayon sa pagkakabanggit, na magreresulta sa mas mababang knapsack power kapag nilulutas ang problema sa relaxation ng knapsack, kaya mas tumpak ang upper bounds. Panghuli, tandaan na tanging ang maximum na pinapayagang pag-iimpake lamang ang dapat na nakaimbak para sa bawat hanay, at ang anumang hindi pinakamataas na elemento ay maaaring balewalain. Binabawasan nito ang bilang ng mga elemento sa , samakatuwid ang memorya at oras ng pagkalkula ay kinakailangan ng algorithm.
8. Input at output data ng system
Input na data:
1. Ang lapad ng rectangle-sheet;
2. Ang taas ng rectangle-sheet;
3. Sukat ng mga parisukat;
Output:
5. Mga parihaba na matatagpuan sa screen ng monitor;
6. Text file na may impormasyon tungkol sa mga nakasulat na parihaba;
7. Karagdagang impormasyon tungkol sa paglalagay ng mga parihaba sa anyo ng iba't ibang mga mensahe sa screen.
8.5. Pag-unlad ng user interface
Maipapayo na gawin ang user interface sa graphical na anyo, dahil ito ay pinaka-maginhawa para sa paggamit.
Form ng input at output ng data
Figure 1. User Interface
Una naming ipinasok ang lapad ng rektanggulo, pindutin ang enter, ang taas - ipasok, at ipasok ang mga sukat ng mga parisukat, halimbawa 23 - ipasok, 45 - ipasok, atbp., Pindutin ang 0 upang ihinto ang pagpasok sa mga parisukat at lilitaw ang resulta ng file sa lugar kung saan naka-save ang proyekto .png kung saan makikita mo ang pag-iimpake ng mga parisukat.
Ang parehong window ay nagpapakita ng impormasyon tungkol sa bilang ng mga parisukat ng ilang partikular na laki. Pindutin ang 0 at tingnan ang impormasyon tungkol sa oras ng pagpuno sa hugis-parihaba na lugar ng mga parisukat.
Pagkatapos ng lahat ng mga aksyon, nakukuha namin:
Larawan 2. Ang resulta ng programa
at ang pakete mismo:
Figure 3. Pag-iimpake ng mga parisukat sa isang parihaba
Talahanayan 1.
Numerical na mga resulta ng programa
|
Sukat ng Parihaba |
Tinantyang bilang ng mga parisukat |
Kabuuang bilang ng mga parisukat |
||
Konklusyon: mas maraming mga parisukat ang ipinasok, mas mahaba ang oras ng pagpapatupad ng algorithm.
9. Konklusyon
Alinsunod sa layunin ng pag-aaral, ang mga sumusunod na gawain ay itinakda at isinagawa:
1. Pagbubuo ng mga problema sa pag-cut-pack na isinasaalang-alang sa mga tuntunin ng mathematical programming at isang qualitative assessment ng mga pamamaraan para sa kanilang solusyon;
2. Isang algorithm para sa paglutas ng problema ng pag-iimpake ng mga parisukat na may iba't ibang laki sa isang rektanggulo ay binuo at sinaliksik;
3. Nasuri ang bisa ng binuong pamamaraan batay sa mga resulta ng mga numerical na eksperimento.
Bibliograpiya:
1.Tekhtran / Cutting sheet material [Electronic na mapagkukunan] - Access mode. - URL: http://9132222.ru/catalog/soft/techtran/textran.html (na-access noong 06/12/2014).
2.Caprara A, Monaci M. Sa dalawang-dimensional na knapsack na problema. Mga Liham ng Pananaliksik sa Operasyon 2004;32:5–14.
3. Christofides N, Whitlock C. Isang algorithm para sa dalawang-dimensional na mga problema sa pagputol. Pananaliksik sa Operasyon 1977;25:30–44.
4. Hifi M. Isang pagpapabuti ng eksaktong algorithm ng Viswanathan at Bagchi para sa limitadong dalawang-dimensional na cutting stock. Computers and Operations Research 1997;24:727–36.
5. Martello S, Toth P. Mga problema sa Knapsack: mga algorithm at pagpapatupad ng computer. Chichester: John Wiley & Sons; 1990.
6. Pisinger D, Sigurd M. Paggamit ng mga diskarte sa decomposition at constraint programming para sa paglutas ng two-dimensional na bin-packing na problema. INFORMS Journal on Computing 2007;19:36–51
7.Young-Gun G, Kang MK. Isang bagong upper bound para sa walang limitasyong two-dimen-sional na pagputol at pag-iimpake. Journal ng Operational Research Society 2002;53:587–91.
Personal na account ng taong nakaseguro
Automatic identification system Pinagsamang paggamit ng AIS na may electronic chart system
Wargame: Hindi nagsisimula ang Red Dragon?
Malungkot na escobar "Ang mukha ng sistema ng hudisyal ng Ukraine"
ROME Total War - paano i-unlock ang lahat ng paksyon?