Ekonomické lineárne rezanie materiálov (rezanie výliskov) je relevantné pre mnohé priemyselné odvetvia a v stavebníctve. Ide o rezanie kmeňov a dosiek pri obrábaní dreva, rezanie tyčí, armovacích tyčí, uholníkov, kanálov, rúr, I-nosníkov na polotovary ...

Vo výrobe kovových konštrukcií a strojárstve, priečnom rezaní kotúčov s papierom a tkaninou v celulózovom a ľahkom priemysle.

Napriek zjavnej jednoduchosti nie je riešenie problémov s lineárnym rezaním veľmi jednoduché, ale stojí za to. Zavedenie vedeckého prístupu k rezaniu lisovaných materiálov vám umožňuje znížiť náklady na ne, niekedy o viac ako 10%! Prečítajte si článok až do konca a uistite sa, že tieto slová sú správne.

Uvažovaná téma sa týka problémov lineárneho programovania. Na vyriešenie takýchto problémov vedci za posledných 70 rokov prišli s niekoľkými rôznymi metódami.

Metóda indexov L.V. Kantorovič a V.A. Zalgallera s určitou zručnosťou umožňuje efektívne vykonávať lineárne rezanie „ručne“ bez použitia výpočtovej techniky. Zvedavým čitateľom odporúčam oboznámiť sa s touto metódou prečítaním knihy vyššie menovaných autorov „Rational Cutting of Industrial Materials“.

Simplexová metóda založená na myšlienkach L.V. Kantoroviča, v polovici 20. storočia podrobne opísalo a rozvinulo množstvo vedcov z USA. Doplnok MS Excel "Hľadať riešenie" (Solver) používa tento algoritmus. Práve pri tejto metódeexcelproblém lineárneho rezania vyriešime v tomto článku.

Neskôr sa objavili a boli vyvinuté genetické algoritmy, algoritmy chamtivých a mravcov. Obmedzíme sa však na ich vymenovanie a pustíme sa do práce bez toho, aby sme liezli do džungle teórií (hoci tam, „v divočine“, je to veľmi zaujímavé).

Zapneme si Excel a na jednoduchom príklade rezania kovových tyčí na diely sa zoznámime s jedným zo spôsobov riešenia praktických problémov lineárneho rezania. Matematici tento problém často označujú ako „problém rezania“.

Počiatočné údaje pre príklad som si nevymyslel, ale prevzal som ich z článku Pokrovského M.A. „Minimalizácia nevyhnutných strát materiálov v priemyselnej výrobe pri ich rezaní na kusové polotovary“ publikované v č. 5 (máj 2015) elektronického vedecko-technického časopisu „Engineering Bulletin“ vydavateľstva FGBOU VPO „MSTU im. N.E. Bauman (odkaz:engbul. bmstu. en/ doc/775784. html).

Cieľom, ktorý som sledoval, bolo porovnať výsledky riešenia problému.

Príklad riešenia úlohy lineárneho rezania v MS Excel.

Zhodnime sa na tom, že:

1. Predvalky sú surovinou vo forme tyčí, pásov, tyčí atď. rovnakú dĺžku.

2. Detaily sú prvky, ktoré je potrebné získať rozrezaním pôvodných polotovarov na kusy.

3. Šírka píly, rezu, trenia sa rovná nule.

Úloha:

Na dokončenie jednej zo zákaziek musí úsek obstarávania narezať tri štandardné veľkosti dielov na kombinovaných nožniciach z rovnakých tyčí-prírezov s dĺžkou 1500 mm:

151 kusov s dĺžkou 330 mm

206 kusov s dĺžkou 270 mm

163 kusov s dĺžkou 190 mm

Je potrebné nájsť optimálny rezací plán, ktorý využíva minimálne množstvo materiálu a teda dáva minimálne množstvo odpadu.

Počiatočné údaje:

1. Dĺžka pôvodných polotovarov Lh v milimetroch píšeme do kombinovanej bunky

D3E3F3: 1500

2. Priraďujeme čísla i všetky štandardné veľkosti dielov, počnúc najdlhšou a končiacou najkratšou v bunkách

D4; E4; F4: 1; 2; 3

3. Dĺžky dielov Ldi zapisujeme v milimetroch

D5; E5; F5: 330; 270; 190

4. Počet detailov Ndi v kusoch vložiť do

D6; E6; F6: 151; 206; 163

5. Prejdeme k veľmi dôležitej fáze - vyplnenie možností rezania.

Treba pamätať a pochopiť 2 zásady pre túto prácu.

1. Dĺžka odpadu musí byť menšia ako najmenšia časť ( 0< lo j < Ldmin ).

2. Začneme „ukladať“ diely do obrobku s najväčšími dielmi a s ich najväčším počtom, pričom sa neustále pohybujeme v smere klesania.

Ak v možnosti rezania nie je žiadna veľkosť časti, potom necháme bunku prázdnu, nebudeme písať nulu, aby sme uľahčili vizuálne vnímanie tabuľky.

Možnosť rezania č. 1:

Pokus vystrihnúť 5 dielov č.1 z jedného polotovaru je nemožný, preto zapíšeme do bunky

Do hniezda je tiež nemožné pridať časť č.2 alebo časť č.3, preto necháme bunky prázdne

Možnosť rezania č. 2:

Počet dielov č. 1 znížime o 1 oproti predchádzajúcej verzii a zapíšeme

Snažíme sa pridať 2 diely č. 2 - nejde to, tak pridávame

Zostáva možnosť doplniť strih detailom č.3. Vstupujeme do

Pri dodržaní uvedených zásad analogicky vyplníme všetkých 18 možností rezu, ktoré sú v tomto prípade možné.

Po vytvorení niekoľkých tabuliek možností rezania sami pochopíte logiku akcií a strávite pár minút touto prácou.

Ak pri rezaní nie je splnená prvá zásada, potom sa bunka s dĺžkou odchodu automaticky vyfarbí červenou farbou. Pri tejto práci vám jednoznačne pomôže podmienené formátovanie aplikované na bunky G7…G24.

Do buniek H7 ... H24 nič nepíšte! Slúžia na zobrazenie výsledku riešenia!

Príprava na riešenie:

* V bunkách G7 ... G24 sa dĺžky odpadu (rezov), ktoré zostávajú v dôsledku rezania, vypočítajú podľa vzorca

lo j = L h -Σ (Ldi * Ndij )

6. Počet častí každej štandardnej veľkosti, vyrobených podľa všetkých použitých možností vnorenia, sa vypočíta v bunkách D26, E26 a F26 podľa vzorca

Ndicalc = Σ (Ndij * Nhj )

Počet dielov v nárezovom pláne nájdený na konci riešenia musí plne zodpovedať uvedenému počtu dielov!

7. Požadovaný počet obrobkov na dokončenie optimálneho rezného plánu sa určí v kombinovanej bunke D27E27F27 pomocou vzorca

N kalkul =ΣN hj

8. Celková dĺžka všetkých polotovarov potrebných na vytvorenie lineárneho hniezda všetkých častí sa vypočíta v kombinovanej bunke D28E28F28 pomocou vzorca

Lh Σ = L h*Nz výpočtu

9. Celková dĺžka všetkého odpadu, ktorý vznikne pri realizácii nájdeného nárezového plánu, sa vypočíta v kombinovanej bunke D29E29F29 pomocou vzorca

Lo Σ = Σ (Loj * Nhj )

10. Podiel odpadu vytvoreného optimálnym lineárnym rezným plánom z celkového množstva použitého materiálu sa vypočíta v zlúčenej bunke D30E30F30 pomocou vzorca

Ωo = Lo Σ /Lз Σ

Riešenie:

Príprava je dokončená, je určených 18 možností pre najoptimálnejšie rezanie jedného obrobku na diely a sú zadané všetky potrebné vzorce. Teraz musíme vyriešiť hlavný problém: určiť optimálny nárezový plán - koľko prírezov, a podľa akých možností strihu rezať aby ste konečne dostali všetky potrebné diely v správnom množstve s minimom odpadu.

1. V hlavnom menu zvoľte "Služba" - "Vyhľadať riešenie ...".

2. V okne s rovnakým názvom „Vyhľadať riešenie“, ktoré sa zobrazí, vykonáme nastavenia.

2.1. K účelovej funkcii priradíme celkovú dĺžku odpadu Lo Σ a zadajte odkaz do okna cieľovej bunky.

2.2. Nastavte prepínač "Equal:" do polohy "minimálna hodnota".

2.3. Zadajte bunky s premennými Nz j v okne Zmena buniek.

2.4. Obmedzenia zadávame do rovnomenného okna. Ako podmienky uvádzame potrebu rovnosti daného Nd i a vyrovnanie Nd icalc počet dielov, ako aj premenné Nz j- odhadovaný počet polotovarov podľa možností rezania - ukladáme obmedzenie: musia to byť celé čísla.

3. Stlačíme tlačidlo "Parametre" a v okne "Parametre vyhľadávania riešení", ktoré sa objaví, vykonáme nastavenia, ako je znázornené na nasledujúcom obrázku. Zatvorte okno tlačidlom OK.

4. V okne „Vyhľadať riešenie“ kliknite na tlačidlo „Spustiť“ a počkajte, kým Excel nájde riešenie. Toto môže trvať niekoľko minúť.

5. Po uložení nájdeného riešenia tlačidlom OK sa výsledky zobrazia v bunkách H7 ... H24 na liste Excel.

Nasledujúci obrázok ukazuje nájdený optimálny lineárny rezný plán.

aký je výsledok?

Lineárne rezanie v polotovaroch programu Excel pre úlohy, ako je tá, o ktorej sa hovorí v tomto článku, sa vykonáva metódou opísanou vyššie za 10-15 minút! „Ručne“, bez znalosti metódy Kantorovičových indexov, v takom čase nenájdete riešenie.

Niekoľkonásobným spustením „Hľadať riešenie“ s rôznymi parametrami vyhľadávania sa nám podarilo nájsť 5 rôznych plánov na výrub prírezov. Všetkých 5 plánov vyžaduje rovnaký počet prírezov - 93 a dáva len 2,21% odpadu!!! Tieto plány sú takmer o 6 % lepšie ako plán vypočítaný Pokrovským a o viac ako 10 % hospodárnejšie ako plán „Tradičný“ (pozri odkaz na pôvodný zdroj v prvej časti článku). Veľmi hodný výsledok sa dosiahol rýchlo a bez použitia drahých programov.

Je potrebné poznamenať, že doplnok Excel Solver ("Hľadať riešenie"), ktorý pri riešení úloh lineárneho programovania používa simplexnú metódu, môže pracovať maximálne s 200 premennými. Pri použití na problém lineárneho rezania, ktorý sme uvažovali, to znamená, že počet rezov nemôže presiahnuť 200 možností. Pre jednoduché úlohy to stačí. Pri zložitejších úlohách by ste sa mali pokúsiť použiť „zmes“ „nenásytného“ algoritmu a metódy simplex Solver, pričom z úplného zoznamu odrezkov nevyberiete viac ako 200 najúspornejších. Potom sa zásobíme trpezlivosťou a dosiahneme výsledky. Môžete sa pokúsiť rozdeliť zložitý problém na niekoľko jednoduchých, ale „úroveň optimálnosti“ nájdeného riešenia bude s najväčšou pravdepodobnosťou nižšia.

Možno, že zvažovanou možnosťou riešenia problémov s lineárnym rezaním nie je „akrobacia“, ale rozhodne je to krok vpred v porovnaní s „tradičným“ prístupom v mnohých odvetviach.

O použití doplnku MS Excel „Hľadať riešenie“ (Solver) sa už na blogu raz v článku hovorilo. Myslím si, že tento úžasný nástroj si zaslúži veľkú pozornosť a pomôže viac ako raz elegantne a rýchlo vyriešiť množstvo nových netriviálnych problémov.

P.S. Odkazy na najlepší bezplatný softvér na lineárne rezanie, ktorý som našiel na webe:

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/

Programy na posledných dvoch odkazoch implementujú nenásytnú heuristiku a vykonávajú lineárne vnorenie v úlohe z článku s použitím až 103 medzier. Použitie nenásytných algoritmov je opodstatnené v prípadoch, keď je potrebné skrátiť celkový čas operácie rezania príliš veľkým počtom rezných možností v optimálnejších plánoch.

Pod článkom v bloku „Recenzie“ môžete písať svoje postrehy, milí čitatelia.

Problémy s hniezdením nájdete v časti Modely lineárneho programovania.

Príklad č. 1. Výrobky papierenskej spoločnosti sa vyrábajú vo forme papierových kotúčov štandardnej šírky - každý 2 metre. Na špeciálne objednávky spotrebiteľov spoločnosť dodáva kotúče iných veľkostí, na ktoré sú rezané štandardné kotúče. Typické objednávky kotúčov neštandardných rozmerov sú uvedené v tabuľke.

Je potrebné nájsť také kombinácie rôznych možností rezania štandardných kotúčov, aby boli prijaté objednávky plne uspokojené s minimálnymi stratami (odpadom).
Zvážme všetky možné možnosti rezania štandardného kotúča, príslušné údaje uvedieme v tabuľke.

Šírka rolky (m)	Možnosti rezania rolkami						Minimálny počet roliek
	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
Odpad v m	0,4	0,3	0,1	0	0,1	0,2	-

Definujme premenné:
X j - počet štandardných kotúčov narezaných podľa voľby j, j = 1, 2, 3, 4, 5, 6.
Obmedzenia priamo súvisia s požiadavkou zabezpečiť výrobu potrebného počtu neštandardných roliek. Pomocou údajov v tabuľke dostaneme:
2X 2 + 2 X 3 + 4 X 4 + X 5 \u003d 150 - počet kotúčov so šírkou 0,5 m,
X 1 + X 2 + 2 X 5 \u003d 200 - počet kotúčov so šírkou 0,7 m,
X 1 + X 3 + 2 X 6 \u003d 300 - počet kotúčov so šírkou 0,9 m.

Vyjadrenie pre celkovú výšku straty papiera (odpadu) (v m) je
0,4 x 1 + 0,3 x 2 + 0,1 x 3 + 0,1 x 5 + 0,2 x 6.

Všeobecný matematický model má teda formu
min f (x) \u003d 0,4 x 1 + 0,3 x 2 + 0,1 x 3 + 0,1 x 5 + 0,2 x 6.
s obmedzeniami:
2X 2 + 2 X 3 + 4 X 4 + X5 = 150
X2 + X2 + 2 X5 = 200
X2 + X3 + 2 X6 = 300

Problém rezania materiálov

Touto úlohou je vypracovať taký plán, ktorý zabezpečí potrebnú sadu produktov s minimálnym odpadom (dĺžka, plocha, hmotnosť, náklady atď.) pri rezaní materiálov alebo poskytne maximálny počet sád produktov. Príklad č. 2. Je potrebné vypracovať optimálny plán rezania štandardných oceľových plechov, ktorý zabezpečí výstup plánovaného počtu prírezov rôznych typov s minimálnym celkovým odpadom, ak je známe, že z dávky oceľového plechu je potrebné vyrezať štyri druhy rôznych prírezov. v množstve bi (i = 1, 2, ..., 4) kusov . Oceľový plech štandardných veľkostí je možné rezať štyrmi spôsobmi. Každý možný spôsob rezania zodpovedá tabuľke rezu. Z nárezových tabuliek je výstup obrobkov v kusoch rôznych typov a ij (i = 1, 2,…4; j = 1,2,…,4), ako aj odpadová plocha cj (j = 1, 2 ,…,n) pri rezaní jedného oceľového plechu j-tým spôsobom rezania. Koľko oceľových plechov je potrebné narezať tak či onak, aby bol odpad minimálny?

Tabuľka 3

Druhy polotovary	Plán úloh pre počet polotovarov (b 1)	Výstup prírezov (ks) rôznych typov z vnorených máp (a ij)
		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
Plocha odpadu, m 2 (cj)		1,4	0,1	2,1	0,1

Urobme si ekonomicko-matematický model problému. Označme x j - množstvo východiskového materiálu (oceľových plechov), ktoré je potrebné narezať jedným zo spôsobov j. Obmedzenia v úlohe musia zodpovedať plánovanému výkonu prírezov rôznych typov. Cieľovou funkciou je nájsť minimálny odpad pri rezaní

F=1,4 x 1 + 0,1 x 2 + 2,1 x 3 + 0,1 x 4 →(min)..
Obmedzenia výstupu polotovarov i-tého typu pre všetky spôsoby rezania j:

Príklad č. 3. Na rezanie (pílenie, spracovanie) sa materiál jednej vzorky dodáva v jednotkách. Je potrebné z neho vyrobiť l rôznych komponentov v množstvách úmerných číslam b 1 , b 2 ,…,b l (podmienka úplnosti). Každá jednotka materiálu môže byť rezaná n rôznymi spôsobmi a pomocou i-tej metódy (i = 1, 2,…,n) sa získa ik jednotiek k-tého produktu (k = 1, 2,…,l ). Je potrebné nájsť rezací plán, ktorý poskytuje maximálny počet sád.
Urobme si ekonomicko-matematický model problému.
Nech x i označuje počet jednotiek materiálu narezaného i-tou metódou a x počet vyrobených sád výrobkov. Potom sa účelová funkcia redukuje na hľadanie

F=x→(max),
s obmedzeniami: celkovým množstvom materiálu, ktorý sa rovná súčtu jeho jednotiek, rozrezaných rôznymi spôsobmi; podľa požiadavky úplnosti a nezápornosti premenných.

Príklad č. 4. Firma disponuje guľatinami dĺžky L m, ktoré je potrebné narezať na kusy dĺžky l 1, l 2, l 3 m v množstve p 1, p 2, p 3 resp.
Je potrebné vypracovať optimálny plán rezania materiálu, ktorý zabezpečuje minimálny odpad, v súlade s plánom výroby prírezov. Počiatočné údaje sú uvedené v tabuľke.

Úloha	Dĺžka	Rozmery prírezov, m			Počet prírezov, ks.
		l 1	l 2	l 3	p1	p2	p 3
68	6,5	2,1	2,3	1,4	600	720	900

Riešenie: Najprv urobme matematický model nášho problému. Možné možnosti rezania a odpad pre každý z nich budú napísané vo forme tabuľky.

Dĺžka obrobku	Možnosti rezania							Počet medzier
	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
Zostávajúce, m	0,2	0	0,9	0,7	0,2	0,5	0

Označme x i počet narezaných polien podľa i-tej možnosti (i=1..7). Potom sa celkový zvyškový odpad zapíše ako lineárna funkcia:
Z = 0,2x1 + 0x2 + 0,9x3 + 0,7x4 + 0,2x5 + 0,5x6 + 0x7
Zároveň musia byť splnené podmienky plnenia plánu z hľadiska počtu prírezov, t.j.
3x1 + 2x2 + 2x3 + x4 + x5 = 600
x2 + x4 + 2x6 + x7 = 720
x 3 + x 4 + 3 x 5 + x 6 + 3 x 7 = 900

Na vyriešenie uvedeného problému je teda potrebné nájsť minZ pod obmedzeniami. Keďže minZ = -max(-Z(x)), tak namiesto problému minimalizácie funkcie budeme riešiť problém maximalizácie funkcie:
Z = -(0,2 x 1 + 0 x 2 + 0,9 x 3 + 0,7 x 4 + 0,2 x 5 + 0,5 x 6 + 0 x 7)

Príklad číslo 5. Na šitie jedného produktu musíte z látky vystrihnúť 6 častí. V odevnej továrni boli vyvinuté dve možnosti strihania látky. V tabuľke (umiestnenej nižšie) sú uvedené charakteristiky možností strihu na 10 m 2 látky, kompletnosť, t.j. počet dielov určitého druhu, ktoré sú potrebné na ušitie jedného výrobku. Mesačná zásoba látky na šitie výrobkov tohto typu je 405 m 2 . V nadchádzajúcom večeri je naplánované ušitie 90 položiek.
Zostavte matematický model problému, ktorý vám umožní dokončiť plán na mieru s minimálnym množstvom odpadu v nasledujúcom mesiaci.

Tabuľka - Charakteristika možností rezania kusov látky 10m 2

Možnosť rezania	Počet dielov, kus/rez						Odpad, m 2 / rez
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Kompletnosť, kus/produkt	1	2	2	2	2	2

Matematické vyjadrenie problému

Premenné úlohy
V tomto probléme nie sú výslovne uvedené požadované hodnoty, ale hovorí sa, že musí byť dokončený mesačný plán šitia 90 produktov. Na prispôsobenie 90 produktov za mesiac je potrebné vyrezať presne stanovený počet dielov. Strih je vyrobený z kusov látky 10 m 2 dvoma rôznymi spôsobmi, ktoré umožňujú získať rôzny počet detailov. Keďže nie je vopred známe, koľko látky sa nastrihá prvým spôsobom a koľko druhým spôsobom, potom ako požadované hodnoty môžete nastaviť počet segmentov látky po 10 m 2 nastrihaných každým zo spôsobov:
x 1 - počet kusov látky 10m 2 nastrihaných prvým spôsobom v priebehu mesiaca [strih / mesiac];
x 2 - počet kusov látky, každý 10 m 2, strihaných prvým spôsobom v priebehu mesiaca, [strih / mesiac];

objektívna funkcia
Cieľom riešenia problému je naplnenie plánu s minimálnym množstvom odpadu. Keďže počet produktov je striktne plánovaný (90 ks/mesiac), tento parameter nepopisuje CF, ale odkazuje na obmedzenie, ktorého zlyhanie znamená, že problém nebol vyriešený. A kritériom efektívnosti implementácie plánu je parameter „množstvo odpadu“, ktorý je potrebné minimalizovať. Keďže pri rezaní jedného kusu (10 m 2) látky podľa 1. možnosti sa získa 0,5 m 2 odpadu a pri 2. možnosti - 0,35 m 2 (pozri tabuľku 1), celkové množstvo odpadu pri strihaní ( CF) má výhľad
L(x) = 0,5x1 + 0,35x2 = min,

Obmedzenia
Počet strihov látok rôznymi spôsobmi je obmedzený nasledujúcimi podmienkami:

• Musí byť vypracovaný plán šitia výrobkov na mieru, inými slovami, celkový počet strihaných dielov musí byť taký, aby sa z neho dalo ušiť 90 výrobkov za mesiac, a to: musí byť aspoň 90 1. druhu a dielov ostatných druhov - najmenej 180 (pozri úplnosť v tabuľke).
• Spotreba látky by nemala presiahnuť mesačnú zásobu v sklade;
• Počet kusov strihanej látky nemôže byť záporný.

Obmedzenie plánu na šitie kabátov má nasledujúcu zmysluplnú formu vstupu.
(Celkový počet dielov č. 1 odrezaných pre všetky možnosti) ≥ (90 kusov);
(Celkový počet dielov č. 2 vyrezaných pre všetky možnosti) ≥ (180 kusov);
(Celkový počet dielov č. 6 vyrezaných pre všetky možnosti) ≥ (180 kusov);

Matematicky sú tieto obmedzenia napísané ako :
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;

Limit spotreby tkaniva má tieto formy zaznamenávania:
zmysluplný
(celkový strih látky za mesiac)≤ (405 m2)
matematický
x 1 + x 2 ≤ 405/10

Nezápornosť počtu rezaných segmentov je uvedená vo formulári
x 1 ≥ 0, x 2 ≥ 0

Matematický model problému má teda formu
L(x) \u003d 0,5x 1 + 0,35x 2 \u003d min [m 2 odpadu / mesiac],
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

Príklad číslo 6. Pre vykurovaciu sieť je 69 rúr, každá 1070 cm. Musia byť narezané na rúry 130, 150 a 310 cm Nájdite si takú možnosť rezania prívodných rúr, pri ktorej by bol odpad minimálny.

Etapa 1. Určujeme možnosti optimálneho rezania rúr.

Možnosti rezania	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
Zvyšky	10	0	20	40	60	50	70	90	110	100	120	10	30

2. fáza
Urobme si ekonomicko-matematický model problému. Označme x j - počet rúr, ktoré je potrebné narezať podľa jedného zo spôsobov j. Cieľovou funkciou je nájsť minimálny odpad pri rezaní:
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

Odpoveď: mala by sa použiť iba druhá možnosť rezu (nulový odpad)

Program je určený na optimalizáciu rezania profilov a iných dlhých materiálov (tyč, guľatina, rúrka, parapet).
Používa sa algoritmus "hustého stohovania", to znamená, že odoberaný produkt je umiestnený na najkratšom zvyšku obrobku, na ktorom je umiestnený. Ak sa nikam nezmestí, vyberie sa nový polotovar. Úlohou optimalizácie je nájsť postupnosť produktov, pri ktorých sa použije menej prírezov a dĺžka obchodných prírezov bude dlhšia. Pri prvom takte sú predmety umiestnené na biče v náhodnom poradí. Existuje „počiatočná populácia“. V procese riešenia populácia mutuje a množí sa, neúspešné exempláre umierajú a tie najlepšie sa naďalej vyvíjajú. Všetko ako vo svete zvierat a rastlín + umelý výber.

Živá ukážka na stránke

Štart

Výhody

• Windowssoft:cutting poskytuje vysoko kvalitné rezané mapy. Početné implementácie potvrdzujú skutočný rezný faktor nie väčší ako 1% pri optimalizácii dávok z 30 obrysov (~120 rezov)
• Na čítanie počiatočných údajov a zaznamenávanie výsledkov rezania program používa jednoduché formáty textových súborov, čo zjednodušuje integráciu s účtovnými systémami implementovanými zákazníkom
• V prípade potreby je možné vnorenie vykonať pod Linuxom alebo OS X v prehliadači alebo Node.js odovzdávaním parametrov cez url, webový socket alebo javascriptové objekty

Lineárne optimalizačné algoritmy

Windowsoft: Rezanie používa genetický algoritmus. Jeho podstatou je toto:
Každú distribúciu produktov bičmi nazvime riešením. Definujme objektívnu funkciu, ktorá nám umožňuje porovnávať kvalitu riešení. Vytvorme niekoľko ľubovoľných riešení, nazvime ich generácia. Definujme pravidlá pre získanie ďalšej generácie. Inštancie s najlepšou objektívnou funkciou prenášajú väčšinu svojho „genofondu“, toto je náš „umelý výber“. Teraz zostáva nechať systém pre seba, nechať ho zmutovať a optimalizovať výsledky rezania
Počas procesu vývoja bola testovaná metóda „Monte Carlo“, kedy sú naše „inštancie“ náhodné a nezávisia na sebe, a „Ant algorithms“ (optimalizácia kolónií ACO-ant). Všetky metódy sa ukázali ako celkom účinné, ale genetický algoritmus sa ukázal byť o niečo efektívnejší.

Možnosti doručenia

Pre rezací modul Windowsoft:cutting existujú dve možnosti dodávky – ako súčasť integrovaného riešenia pre riadenie zákazkovej výroby a ako samostatný spustiteľný súbor. Interakcia s rezacím programom v prvom scenári je pred používateľom úplne skrytá. Operátor pracuje so štandardnými dokumentmi 1C:

• Na základe objednávok zákazníkov sa vytvára plán výroby
• Na základe plánu - zmenové úlohy so zoznamom produktov a potrebných materiálov
• Vnorenie je optimalizované v rámci výrobnej zákazky
• V procese optimalizácie program odoberie obchodnú úpravu z prebiehajúcej výroby a umiestni novovytvorenú obchodnú úpravu do mobilného skladu
• Na smeny je možné tlačiť výrezové formuláre pre ručnú výrobu alebo generovať súbory pre CNC stroje
• Tiež štítky pre rezané produkty a schémy rozloženia pre vozíky a pyramídy sú tlačené z práce na smeny.
• Na základe výrobných úloh sa tvoria požiadavky - faktúry za presun materiálu do dielne, s prihliadnutím na potreby a štandardné balenie

Softvérové ​​rozhranie (Linear Nesting API)

Vstupný dátový súbor setup.ini sa umiestni do priečinka so spustiteľným súborom.
Výstupné dátové súbory - result.txt, resultproduct.txt a resultstick.txt - sa generujú v rovnakom priečinku.
Súbory s ukážkovými údajmi Oknosoft:cutting si môžete stiahnuť z odkazu na konci stránky. Súbory používajú nasledujúce značky:

• Outputvariant - štruktúra výstupného súboru súboru. Možné hodnoty: tab, oknosoft, predvolené oknosoft
  • Vo voľbe „oknosoft“ sa vygenerujú súbory resultproduct.txt a resultstick.txt s informáciami o umiestnení produktov na prírezoch a výslednom orezaní
  • Variant „tab“ zobrazuje päť hodnôt oddelených znakmi „tab“: dĺžka produktu, číslo biča, dĺžka biča, číslo rezu a zvyšok obrobku
• Algoritmus – použitý algoritmus. Možné hodnoty: náhodné, konzervatívne, genetické, predvolené genetické
  • Náhodný - náhodný výber možností
  • Konzervatívny – inštancie ďalšej iterácie pochádzajú od toho istého „rodiča“
  • Genetický - od dvoch rodičov
• Variabilita - variabilita, parameter "konzervatívnych" a "genetických" algoritmov. Čím vyššie, tým menej potomkov „podobných“ rodičom. Predvolená hodnota je 1.
• Generations - počet iterácií algoritmu, predvolene 40 000
• Osoby – počet „inštancií“ v „populácii“, počet riešení použitých v jednej iterácii. „Náhodný“ algoritmus jednoducho vykoná niekoľko generácií* osôb opakovaní s jednou inštanciou (riešením)
• KnifeWidth - šírka píly
• StickLength - dĺžka novej palice
• Produkty - dĺžka produktu
• Šrot - dĺžka šrotu použitého v hniezde
• Wrongsnipmin – minimálna dĺžka „zlého“ vzorkovníka
• Wrongsnipmax – maximálna dĺžka „zlého“ strihu
  Výsledky optimalizácie nebudú mať výstrižky s dĺžkami medzi Wrongsnipmin a Wrongsnipmax

Párové rezanie

Používa sa pri príprave údajov pre stroje, ktoré podporujú párové rezanie. V tomto prípade sú do stroja umiestnené dva profilové biče naraz a v jednom cykle rezania sa vytvoria dva rovnaké polotovary.

Úloha párového rezania sa rieši zoskupením údajov pred ich prenosom do optimalizačného programu a následným zdvojením výsledkov rezania do párov výrobkov a obrobkov. Pri vkladaní do UPZP systém zohľadňuje vlastnosti názvoslovia a používa jednoduchý alebo párový rez v závislosti od možností rezacích strojov.

Rezanie veľkého množstva výrobkov

Na jednej strane pre dosiahnutie vysokej kvality optimalizácie musí byť na vstup programu prijaté značné množstvo produktov rôznych dĺžok, aby mal optimalizátor „čo triediť“. Na druhej strane, pri veľmi veľkých dávkach klesá pravdepodobnosť nájdenia maxima pri pevnom počte opakovaní enumerácie. Experimenty ukázali, že dávka 60-120 prírezov je optimálna (čo zodpovedá výrobnému cyklu 30-60 výrobkov s párovým rezaním). Ak potrebujete optimalizovať viac ako 120 obrobkov, najlepšie výsledky možno dosiahnuť rozdelením problému na N častí a vykonaním postupných optimalizácií pre každú časť. Spracovanie tvorby sérií výrobných úloh umožňuje zoskupovať produkty podľa typu profilu a vyberať produkty s maximálnym rozptylom do zmenových úloh, čím ušetrí operátorovi rutinnú prácu pri zostavovaní výrobných podkladov

Stiahnite si príklady rezania a dokumentáciu

• Demo karty s jednoduchým a dvojitým rezom: 60,01 listov na rezanie
• Dokumentácia a vzorové súbory:

Cutting Line - Program pre lineárne rezanie

Verzia: 2.49


Bitová hĺbka: 32 bit


Tabletka: Vyliečená


Pri vývoji algoritmickej časti programov bol ako hlavné kritérium zvolený princíp minimalizácie odpadu a pri vývoji časti rozhrania sa autor snažil, aby programy boli jednoduché a pohodlné pri každodennom používaní.

Program optimálneho rezania lineárnych polotovarov na diely

Program má nasledujúce funkcie a vlastnosti:

Náš cenník obsahuje tri produkty súvisiace so spoločnou témou triedenia a optimalizácie:

• Lineárny rezací program pre profily a dlhé materiály
• Program na dvojrozmerné rezanie skla, sendvičov, drevotrieskových dosiek a iných tabuľových materiálov
• Program na optimalizáciu trasy na riešenie logistických problémov

Nesting moduly je možné dodať ako súčasť integrovaného riešenia Windowsoft: Custom Production Management, tak aj ako samostatné programy. Pri volaní rezacích programov z 1C nie je potrebný import - export dát do medzisúborov. Používateľ pracuje v štandardnom rozhraní a všetky jemnosti interakcie 1C s externými optimalizátormi vykonávajú spracovanie vypĺňania tabuľkových častí. Na účely účtovania zostatkov zásob, obchodných odrezkov a materiálov vo výrobe sa používajú štandardné dokumenty a registre typických konfigurácií 1C.

Lineárne rezanie (profil, rúrka, guľatina)

Poskytuje percento úrody potvrdené inventárom

Živá ukážka na stránke

Nižšie uvedený príklad nie je statický obrázok, ale funkčná webová aplikácia.
Rezanie profilu môžete spustiť tlačidlom Štart, nastavte si rozmery produktov a obrobkov, zmeňte nastavenia optimalizácie a vyhodnoťte riešenie.
Samozrejme, optimalizátor v prehliadači je pomalší ako natívny program, ale umožňuje vám získať funkčné výsledky zadarmo bez toho, aby ste museli čokoľvek sťahovať a inštalovať do počítača.

20 000 r.

Rezanie skla a tabuľových materiálov

Vytvára tabuľky rezov najvyššej kvality. Poskytuje percento úspory materiálu blízko teoretického limitu. O 10-12% lepšie ako obľúbené programy Opty-Way, MaxCut, PerfectCut, Rezanie atď. v takých ukazovateľoch, ako je plocha nepracujúcich zvyškov, celková plocha rezaného materiálu a počet celých listov použité

Všetky 2D hniezdne algoritmy boli vyvinuté OOO Programs of Cutting, Novosibirsk, vývojár: Shilyaev Vladimir Genrikhovich. Oknosoft je oficiálnym predajcom vývojára a na základe sublicenčnej zmluvy má právo predávať program ako samostatný produkt a používať ho ako súčasť nášho vývoja.

40 000 r.

Prečo optimalizovať vnorenie v programe?

Veľa zákazníkov hovorí: "Mám dobrú pílu. Perfektne reže sklo a profil v hlave. Do odpadu sa dostanú len trojuholníky."
Najčastejšie je to pravda. Jednou z úloh lídra je zároveň zorganizovať predvídateľný proces, ktorého stabilita nezávisí od geniality účinkujúcich. Optimalizácia softvérového rezu na základe výrobného plánu je jedným z opatrení, ktoré tento cieľ približujú.

Ak predpokladáme, že človek dokáže prejsť v hlave viac kombinácií ako počítač za rovnaký čas, ~1% koeficient cutoff získaný automatickým rezaním bude vyzerať atraktívnejšie ako nekontrolované a neriadené 1%, ktoré môže poskytnúť Genius. Prenesením optimalizačných úloh do programu sa môže uvoľniť dodatočný čas (1-2 hodiny denne), ktorý strávi v prospech podnikania.

V skutočnosti je situácia s orezávaním vo väčšine podnikov horšia. V špecifikácii sú stanovené koeficienty rádovo 4-7%, a ak dielňa pracuje s 3-5% orezaním, považuje sa to za dobrý výsledok. Zníženie skutočného faktora plodiny o 3-5% je ušetrených 30-50 tisíc rubľov za každý milión vynaložený na materiály. A napriek tomu to umožní nezahŕňať ďalšie ruble do plánovaných nákladov a ponúknuť kupujúcemu priaznivejšie ceny.

Problém optimálnej spotreby materiálov pozostáva z niekoľkých častí.

Skladové účtovníctvo meraných materiálov

V závislosti od charakteristík podniku zákazníci používajú niekoľko účtovných schém pre materiály:

• Na základe výrobného plánu sa tvoria požiadavky - faktúry označujúce produkty. Vydanie dodatočných materiálov (nedostatočných) sa odráža v samostatných dokumentoch. Označenie produktov v týchto dokumentoch je žiadúce, nie však nevyhnutnou podmienkou. V tomto prípade sa do dielne vydávajú len tie materiály, ktoré sú v špecifikáciách dnes vyrábaných produktov a len v požadovanom množstve. Nevýhodou tohto prístupu je potreba vypracovať viac dokumentov a nedostatok materiálu na pracoviskách (možno je to výhoda?)
• Požiadavky - faktúry sú generované asynchrónne, bez odkazu na plán výroby, na základe požiadaviek majstrov. Tento prístup vám umožňuje získať „živý sklad“ s minimálnymi nákladmi na obsluhu pre skladníka, ale nechráni pred prečerpaním materiálu. Celú zodpovednosť za súlad spotreby so špecifikáciami majú v tomto prípade majstri a pracovníci. Analýza nákladov podľa plánu ukáže odchýlky, ale už môže byť neskoro

Účtovníctvo pre obchodnú úpravu

Je to možné v scenári, kde sú požiadavky - faktúry generované na základe plánu výroby. Zvyšok obchodného orezania na začiatku rezania je prevzatý zo špeciálneho registra a môže byť upravený operátorom v súlade so skutočným zostatkom. Pri realizácii výrobného zadania sa do požiadaviek - faktúr umiestňujú údaje o množstve materiálu, ktorý je potrebné prijať zo skladu, a údaje o výslednom obchodnom náreze sa dopĺňajú späť do evidencie.

Interakcia účinkujúcich

Pri rozhodovaní, či použiť optimalizátor vnorenia, zvážte:

• Pri automatickom rezaní nie je možné organizovať zváranie (montáž) produktov „pod pílou“, pretože segmenty súvisiace s jedným produktom budú „rozsypané“ po celej optimalizačnej mape.
• Výrobný cyklus sa predlžuje, je potrebné zorganizovať rezervoár na skladovanie prírezov. Kompromisom je rezanie v dávkach 30 - 50 kusov. Súčasne sa dosahujú vysoké rezné rýchlosti a rovnomerné zaťaženie zvarových plôch a tvaroviek.
• Znižuje sa efektivita, s akou môže obchod reagovať na zmeny v pláne. Ak manažér potrebuje zakliniť nový produkt do dnešného plánu, zhorší to výsledky optimalizácie.

Softvér na lineárne rezanie

Verzia: 2.49
Vývojár: Shibaev Yury Anatolyevich Ukraine, Cherkasy
Stránka vývojára: http://www.cuttinghome.com/
Bitová hĺbka: 32 bit
Kompatibilné s Windows 7: áno
Jazyk rozhrania: angličtina + ruština
Tabletka: Vyliečená
Systémové požiadavky: Minimálne
Popis: Program CUTTING je určený pre optimálne rezanie materiálu na lineárne časti. Program je možné použiť pri obrábaní dreva, výrobe nábytku, rezaní kovov, rezaní skla a pod. Programy sú založené na jedinečnom vysokorýchlostnom algoritme, ktorý vám umožňuje rýchlo rezať s minimálnym odpadom.

Pri vývoji algoritmickej časti programov bol ako hlavné kritérium zvolený princíp minimalizácie odpadu a pri vývoji časti rozhrania sa autor snažil, aby programy boli jednoduché a pohodlné pri každodennom používaní.
Program má nasledujúce funkcie a vlastnosti:
. nastavenie ľubovoľného počtu obrobkov a segmentov, ktoré sa majú rezať
. nastavenie polotovarov a segmentov podľa určitých charakteristík, napríklad názvu a farby
. výpočet zohľadňujúci typ materiálu (názov materiálu, farba)
. nastavenie šírky rezného nástroja
. výpočet celkových dĺžok segmentov a zvyškov
. nastavenie rôznych režimov rezania
. obnovenie predchádzajúcich hniezd aktuálnej relácie
. ukladanie špecifikovaných obrobkov a rezov ako špecifikácií
. pridanie uloženého kusovníka do novej možnosti analýzy
. uloženie hniezda do súboru s možnosťou neskoršej obnovy
. prezeranie a tlač výsledkov rezania v grafickej aj tabuľkovej forme
. kompletný systém referenčných informácií.

Náš cenník obsahuje tri produkty súvisiace so spoločnou témou triedenia a optimalizácie:

• Lineárny rezací program pre profily a dlhé materiály
• Program na dvojrozmerné rezanie skla, sendvičov, drevotrieskových dosiek a iných tabuľových materiálov
• Program na optimalizáciu trasy na riešenie logistických problémov

Nesting moduly je možné dodať ako súčasť integrovaného riešenia Windowsoft: Custom Production Management, tak aj ako samostatné programy. Pri volaní rezacích programov z 1C nie je potrebný import - export dát do medzisúborov. Používateľ pracuje v štandardnom rozhraní a všetky jemnosti interakcie 1C s externými optimalizátormi vykonávajú spracovanie vypĺňania tabuľkových častí. Na účely účtovania zostatkov zásob, obchodných odrezkov a materiálov vo výrobe sa používajú štandardné dokumenty a registre typických konfigurácií 1C.

Lineárne rezanie (profil, rúrka, guľatina)

Poskytuje percento úrody potvrdené inventárom<1%. Ряд клиентов приобрели наши алгоритмы для замены программ оптимизации, поставлявшихся производителями отрезных станков. В программе использован алгоритм плотной укладки и генетический алгоритм поиска решения. На вход поступают данные о количестве и размерах изделий и деловых отходов. На выходе формируются карты раскроя с указанием тележек и ячеек. При необходимости, формируются файлы для обрабатывающих центров, станков с ЧПУ и этикетки с подробной информацией об отрезаемой заготовке и примыкающих элементах.

Živá ukážka na stránke

Nižšie uvedený príklad nie je statický obrázok, ale funkčná webová aplikácia.
Rezanie profilu môžete spustiť tlačidlom Štart, nastavte si rozmery produktov a obrobkov, zmeňte nastavenia optimalizácie a vyhodnoťte riešenie.
Samozrejme, optimalizátor v prehliadači je pomalší ako natívny program, ale umožňuje vám získať funkčné výsledky zadarmo bez toho, aby ste museli čokoľvek sťahovať a inštalovať do počítača.

20 000 r.

Rezanie skla a tabuľových materiálov

Vytvára tabuľky rezov najvyššej kvality. Poskytuje percento úspory materiálu blízko teoretického limitu. O 10-12% lepšie ako obľúbené programy Opty-Way, MaxCut, PerfectCut, Rezanie atď. v takých ukazovateľoch, ako je plocha nepracujúcich zvyškov, celková plocha rezaného materiálu a počet celých listov použité

Všetky 2D hniezdne algoritmy boli vyvinuté OOO Programs of Cutting, Novosibirsk, vývojár: Shilyaev Vladimir Genrikhovich. Oknosoft je oficiálnym predajcom vývojára a na základe sublicenčnej zmluvy má právo predávať program ako samostatný produkt a používať ho ako súčasť nášho vývoja.

40 000 r.

Prečo optimalizovať vnorenie v programe?

Veľa zákazníkov hovorí: "Mám dobrú pílu. Perfektne reže sklo a profil v hlave. Do odpadu sa dostanú len trojuholníky."
Najčastejšie je to pravda. Jednou z úloh lídra je zároveň zorganizovať predvídateľný proces, ktorého stabilita nezávisí od geniality účinkujúcich. Optimalizácia softvérového rezu na základe výrobného plánu je jedným z opatrení, ktoré tento cieľ približujú.

Ak predpokladáme, že človek dokáže prejsť v hlave viac kombinácií ako počítač za rovnaký čas, ~1% koeficient cutoff získaný automatickým rezaním bude vyzerať atraktívnejšie ako nekontrolované a neriadené 1%, ktoré môže poskytnúť Genius. Prenesením optimalizačných úloh do programu sa môže uvoľniť dodatočný čas (1-2 hodiny denne), ktorý strávi v prospech podnikania.

V skutočnosti je situácia s orezávaním vo väčšine podnikov horšia. V špecifikácii sú stanovené koeficienty rádovo 4-7%, a ak dielňa pracuje s 3-5% orezaním, považuje sa to za dobrý výsledok. Zníženie skutočného faktora plodiny o 3-5% je ušetrených 30-50 tisíc rubľov za každý milión vynaložený na materiály. A napriek tomu to umožní nezahŕňať ďalšie ruble do plánovaných nákladov a ponúknuť kupujúcemu priaznivejšie ceny.

Problém optimálnej spotreby materiálov pozostáva z niekoľkých častí.

Skladové účtovníctvo meraných materiálov

V závislosti od charakteristík podniku zákazníci používajú niekoľko účtovných schém pre materiály:

• Na základe výrobného plánu sa tvoria požiadavky - faktúry označujúce produkty. Vydanie dodatočných materiálov (nedostatočných) sa odráža v samostatných dokumentoch. Označenie produktov v týchto dokumentoch je žiadúce, nie však nevyhnutnou podmienkou. V tomto prípade sa do dielne vydávajú len tie materiály, ktoré sú v špecifikáciách dnes vyrábaných produktov a len v požadovanom množstve. Nevýhodou tohto prístupu je potreba vypracovať viac dokumentov a nedostatok materiálu na pracoviskách (možno je to výhoda?)
• Požiadavky - faktúry sú generované asynchrónne, bez odkazu na plán výroby, na základe požiadaviek majstrov. Tento prístup vám umožňuje získať „živý sklad“ s minimálnymi nákladmi na obsluhu pre skladníka, ale nechráni pred prečerpaním materiálu. Celú zodpovednosť za súlad spotreby so špecifikáciami majú v tomto prípade majstri a pracovníci. Analýza nákladov podľa plánu ukáže odchýlky, ale už môže byť neskoro

Účtovníctvo pre obchodnú úpravu

Je to možné v scenári, kde sú požiadavky - faktúry generované na základe plánu výroby. Zvyšok obchodného orezania na začiatku rezania je prevzatý zo špeciálneho registra a môže byť upravený operátorom v súlade so skutočným zostatkom. Pri realizácii výrobného zadania sa do požiadaviek - faktúr umiestňujú údaje o množstve materiálu, ktorý je potrebné prijať zo skladu, a údaje o výslednom obchodnom náreze sa dopĺňajú späť do evidencie.

Interakcia účinkujúcich

Pri rozhodovaní, či použiť optimalizátor vnorenia, zvážte:

• Pri automatickom rezaní nie je možné organizovať zváranie (montáž) produktov „pod pílou“, pretože segmenty súvisiace s jedným produktom budú „rozsypané“ po celej optimalizačnej mape.
• Výrobný cyklus sa predlžuje, je potrebné zorganizovať rezervoár na skladovanie prírezov. Kompromisom je rezanie v dávkach 30 - 50 kusov. Súčasne sa dosahujú vysoké rezné rýchlosti a rovnomerné zaťaženie zvarových plôch a tvaroviek.
• Znižuje sa efektivita, s akou môže obchod reagovať na zmeny v pláne. Ak manažér potrebuje zakliniť nový produkt do dnešného plánu, zhorší to výsledky optimalizácie.

Programy na optimalizáciu rezania materiálu

Tento katalóg obsahuje odkazy na niekoľko domácich počítačových programov na optimalizáciu rezania materiálu.a niekoľko publikácií na túto tému.

Metóda optimalizácie rezania materiálu je založená na práci „Výpočet racionálneho rezania priemyselných materiálov“, 1951, ktorú napísali sovietski vedci LV Kantorovich a VA Zalgaller, v ktorej sú systematicky prezentované algoritmy lineárneho programovania, ako aj dynamické programovanie pre daný problém. o strihaní a jeho kombinovaní s algoritmami lineárneho programovania.

Vo svete sa vyvinulo veľké množstvo programov na optimalizáciu rezania, a to ako všeobecného charakteru, tak aj čisto špeciálnych. Nižšie sú uvedené odkazy na programy dostupné na stiahnutie z webových stránok vývojárov. Sú tam aj ich popisy.

rezanie
program je určený na automatické zostavovanie optimálnych rezných máp pre plošné a kotúčové materiály,

napríklad drevotrieskové dosky, MLF (pri výrobe nábytku), sklo alebo akékoľvek iné doskové alebo rolované materiály. Umožňuje efektívne a rýchlo získať hniezdne karty s veľkým percentom výnosu. Platené, k dispozícii demo
vývojárska stránka http://picaro.ru
Rezanie Astra
program je navrhnutý tak, aby optimalizoval rezanie plošných materiálov ( drevotrieskové dosky, kov, sklo a plasty ). Astra Nesting poskytuje rýchle zadávanie informácií o objednávkach a materiáloch; automatické a manuálne generovanie tabuliek rezu; úplné zaúčtovanie rozmerových zvyškov a ich rezanie v nasledujúcich objednávkach; tlač tabuliek rezu a špecifikácií. Zaplatené
vývojárska stránka http://www.astrapro.ru Rezanie základov
program na automatizovanú tvorbu máp na rezanie plošného materiálu, ktorý kombinuje optimálne umiestnenie obrysov pravouhlých dielov v daných rozmeroch východiskového materiálu s vysokou rýchlosťou výpočtu. Je neoddeliteľnou súčasťou komplexu Základ - Konštruktér - Výrobca nábytku. Platené, k dispozícii demo
vývojárska stránka http://www.bazissoft.ru Rezanie
programy z rodiny CUTTING sú navrhnuté pre optimálne rezanie materiálu na pravouhlé alebo lineárne diely. Programy je možné využiť pri obrábaní dreva, výrobe nábytku, rezaní kovov, rezaní skla a pod. Programy sú založené na jedinečnom vysokorýchlostnom algoritme, ktorý vám umožňuje rýchlo rezať s minimálnym odpadom. Platené, k dispozícii demo
vývojárska stránka http://www.cuttinghome.com
reznú líniu
program je určený pre optimálne rezanie lineárnych prírezov na lineárne segmenty rôznych dĺžok a možno ho použiť v drevospracujúcom a celulózovo-papierenskom priemysle, kovoobrábaní, odevnej výrobe a pod. Platené, k dispozícii demo
vývojárska stránka http://www.cuttinghome.com

PaneCut je program na optimalizáciu rezania plechových a lineárnych materiálov, ktorý umožňuje výrazne znížiť percento použitých odpadových materiálov.Platené, k dispozícii demo
vývojárska stránka http://www.vsgroup.ua
NCL- P Program automatického rezania plošného materiálu pre detaily akejkoľvek konfigurácie. Developer Polevov A.V.zadarmo
webová stránka programu http://freesoft.ru/ncl_v13
Optimálne
program pre optimálne rezanie materiálov na pravouhlé diely.Shareware
vývojárska stránka http://wincad.ru

Výrobca nábytku Bazis
komplex vzájomne prepojených programov, ktoré vám umožňujú efektívne organizovať individuálnu alebo sériovú výrobu skriňového nábytku v akomkoľvek podniku: od nábytkárskych gigantov až po individuálnych podnikateľov. Zloženie systému: Basis-Furniture Maker (základné), Basis-Cutting, Basis-Estimate, Basis-Interiér.

Platené, k dispozícii demo
vývojárska stránka http://www.bazissoft.ru
bCAD-výrobca nábytku
špecializovaný softvérový balík určený pre návrh a prípravu výroby skriňového nábytku. Balík obsahuje základný modul bCAD doplnený o špecifické nástroje. Aplikácia Nesting vám umožňuje automaticky vytvoriť mapu hniezdenia pre podrobnosti o prijatých modeloch. Keď vyberiete materiál, aplikácia automaticky ponúkne zoznam dielov z vybraného materiálu, ktoré sú prítomné v projekte. Nastavujú sa parametre použitých plechov, smer prvej píly, počet súprav. Aplikácia umožňuje zohľadniť rezíduá, uložiť ich parametre a použiť ich v budúcnosti.
vývojárska stránka http://bcad-ug.ru

Nie je ťažké nájsť na nete ďalšie podobné programy, vr. zadarmo

Teória a prax automatizovaného rezania materiálov pri výrobe skriňového nábytku. Bunakov P.Yu., Kaskevich N.V., Kolomna: GOSGI, 2010. 170 s.

Optimalizácia rezania materiálu v strojárstve: učebnica / S.I. Vdovin, O.E. Jur. - Orol: OSU pomenovaná po I. S. Turgenevovi, 2016. - 45 s.

V.A. Skaternoy "Optimalizácia rezných materiálov v ľahkom priemysle" vyd. Odevný priemysel. Legprombytizdat, 1989,- 144 s

Zostavil Abushenko Alexander Viktorovič, okt. 2005, referencie skontrolované jan. 2017

OPTIMALIZÁCIA REZANIE PLECHOVÉHO MATERIÁLU NA ODLŽNÍKY RÔZNYCH VEĽKOSTI

Giniatullina Regina Airatovna

Študent 1. ročníka magisterského štúdia, Katedra aplikovanej matematiky a informatiky, KNRTU. A.N. Tupolev, Ruská federácia, Kazaň

Email:Regina[e-mail chránený] yandex. en

Galijev Šamil Ibragimovič

vedecký poradca, Dr. tech. Sci., profesor ITKiI KNRTU im. A.N. Tupolev, Ruská federácia, Kazaň

Gilotínové rezanie oceľových a iných plechov je široko používané v strojárstve a iných priemyselných odvetviach. Toto vkladanie je vlastne úlohou zbaliť štvorce rôznych veľkostí do daného listu pomocou gilotínového postupu. Je dôležité znížiť množstvo odpadu. Záujem o problémy s obalmi sa vysvetľuje ich veľkým praktickým významom. Takéto úlohy sa spravidla týkajú materiálovo náročných odvetví, kde jedným z hlavných faktorov znižovania nákladov na výrobky je racionálne využívanie zdrojov. Táto úloha má široké praktické využitie v tých odvetviach, kde sa úlohy balenia (rezania) tradične vyskytujú v strojárstve, drevospracujúcom, ľahkom a stavebnom priemysle. .

1. Kontrola podľa úlohy

V priemysle pri výrobe rôznych druhov finálnych výrobkov vzniká problém optimálne narezať plechy daných veľkostí na pravouhlé prírezy. Táto úloha je nasledovná: sú známe rozmery štvorcov, veľkosť listu. Dané štvorce je potrebné umiestniť do plechu bez toho, aby sa navzájom prekrývali, aby bolo možné plech prerezať gilotínou. Gilotínovým rezaním sa rozumie rezanie, realizované sekvenciou priechodných rezov rovnobežných s okrajmi materiálu. Okrem toho musia byť tieto štvorce ortogonálne zabalené bez rotácií, to znamená, že pre každý vybraný prvok typu musí byť strana s výškou rovnobežná so stranou listu s výškou H. Zvážime problém balenia štvorcov rôznych veľkostí do obdĺžnika. Vyriešme tento problém pomocou jedného presného algoritmu. Je založený na iteratívnom vykonávaní algoritmu vetvenia a väzby (pozrieme sa naň aj my) rekurzívne s rôznymi vstupnými parametrami na určenie optimálnej hodnoty riešenia.

2. Účel projektu

Cieľom tejto práce je študovať a implementovať algoritmus schopný nájsť riešenia na zbalenie štvorcov do obdĺžnika. Uvažovaný problém je široko používaný v rôznych priemyselných odvetviach: strojárstvo, drevospracujúci priemysel, ľahký a stavebný priemysel.

Je potrebné implementovať možnosť zobrazenia získaného výsledku vo forme štvorcov rôznych veľkostí vpísaných do obdĺžnika a zodpovedajúcich doplnkových informácií požadovaných používateľom. Napríklad: čas chodu algoritmu, rôzne informácie o chybách atď.

3. Všeobecné požiadavky

1) Ručné nastavenie rozmerov hárku-obdĺžnika (šírka a výška), do ktorého sa budú štvorce baliť;

2) Manuálne zadávanie veľkostí štvorcových (môžu byť rovnaké alebo rôzne);

3) Vizuálne prezeranie výsledkov vykonávania algoritmu (s výstupom relevantných informácií: čas vykonania algoritmu, počet štvorcov určitej veľkosti vpísaných do obdĺžnika);

4) Uloženie informácií o už zadaných štvorcoch do súboru.

4. Relevantnosť problému

Hlavným cieľom navrhnutého systému je súlad so základným algoritmom štvorcového balenia a jednoduchosť použitia koncovým používateľom, odolnosť voči chybám.

Úlohy a funkcie navrhnutého systému musia spĺňať požiadavky.

Algoritmus navrhnutý v tomto dokumente možno použiť na efektívne riešenie problému balenia štvorcov do obdĺžnikovej oblasti daných rozmerov. Tento problém má širokú škálu praktických aplikácií v tých odvetviach, kde sa tradične vyskytujú úlohy rezania a balenia. Uvažovaný algoritmus je možné použiť v praktických výpočtoch a zahrnúť do automatizovaných systémov návrhu a riadenia. Môžeme tiež povedať, že problém je v súčasnosti aktuálny, pretože je potrebné zbaliť štvorce do obdĺžnika a táto potreba nikdy neskončí, čo znamená, že problém bude vždy aktuálny.

Problémy rezania a balenia zaujímajú dôležité miesto v modernej kombinatorickej optimalizácii a priťahujú pozornosť mnohých vedcov v Rusku aj v zahraničí.

Záujem o problémy rezania a balenia sa vysvetľuje najmä ich veľkým praktickým významom. Aplikácie rezania a balenia spravidla súvisia s priemyselnými odvetviami náročnými na materiály, kde je jedným z hlavných faktorov znižovania nákladov na vyrábané produkty racionálne využívanie zdrojov.

5. Existujúce rezacie systémy.

Existuje mnoho softvérových produktov na rezanie plošného materiálu, ako napríklad ORION, ASTRA CUTTING, TEHTRAN. Uvažujme o jednom z nich na príklade TEHTRANU.

Pre podniky využívajúce tepelné rezacie stroje je jednou z najnaliehavejších úloh zavádzanie moderných informačných technológií. Je zrejmé, že skrátenie času prípravy rezacích programov, optimálne umiestnenie dielov na plech a nižšia spotreba materiálu rozhodujúcim spôsobom ovplyvnia cenu a kvalitu výrobkov.

Nový softvérový produkt Techtran / Rezanie dopĺňa programovú líniu rodiny Techtran a je určený na navrhovanie programov na rezanie plošného materiálu. Schopnosti CAM systému sa tu spájajú s funkciami organizácie výrobného procesu. Prístup k riešeniu použitý v programe sumarizuje skúsenosti mnohých podnikov prevádzkujúcich tepelné rezacie stroje. Úlohou je rýchlo optimálnym spôsobom usporiadať diely na plechy a získať riadiace programy na rezanie týchto dielov podľa rezacej úlohy, ktorá pozostáva z nomenklatúry vybraných dielov a ich množstva pre každú položku. Pracovné odpadové listy, ktoré zostali po práci, by sa mali zaznamenať do databázy systému pre ďalšie použitie.

6. Formalizácia problému a vývoj matematického modelu

V nadväznosti na prácu uvádzame matematický model problému.

Algoritmus vetvenia a ohraničenia je založený na modeli celočíselného lineárneho programovania (ILP). Pre jednoduchosť tejto formulácie predpokladáme, že každý prvok je odlišný, teda pre každý typ j obdĺžniky, definujeme identické prvky so šírkou, výškou a ziskom. Nech (1) je celkový počet prvkov. Pre každý prvok k zavedieme binárnu premennú, ktorá nadobudne hodnotu 1 vtedy a len vtedy, ak prvok k zahrnuté v optimálnom riešení. ILP model pre všeobecný dvojrozmerný problém s batohom je nasledovný:

kde: - rozmery vpísaného štvorca,

Rozmery samotného obdĺžnika,

U- akákoľvek horná hranica hodnoty optimálneho riešenia a C označuje množinu všetkých podmnožín prvkov, ktoré nemožno zbaliť gilotínou do listu. Pre prahovú hodnotu U používame , teda hodnotu optimálneho riešenia pre dvojrozmerný problém s batohom, zodpovedajúcu zjednodušeniu, podľa ktorého sú vynechané gilotínové obmedzenia. Všimnite si, že obmedzenia (3) a (4) sú nadbytočné, ale pridané do formulácie, aby ju posilnili. Náš algoritmus rieši zjednodušený problém, v ktorom sú eliminované obmedzenia (5) a či je aktuálne riešenie platné alebo nie, sa kontroluje vyriešením nasledujúceho separačného problému: budú všetky prvky z zapadnúť do listu gilotínovým prístupom? Ak je odpoveď kladná, potom sa nájde optimálne riešenie všeobecného dvojrozmerného problému s batohom. V opačnom prípade sa nájde nové porušené obmedzenie a proces sa zopakuje.

Tento prístup je podobný metóde, ktorú navrhli Caprara a Monasi na presné riešenie problému s 2D batohom a podľa Piesingera a Sigarda na riešenie samotného všeobecného problému s 2D batohom. Presnejšie, model (2)-(6) je riešený špecializovanou metódou vetvenia a viazania, v ktorej sú prvky usporiadané. Horné hranice sa získajú z LP relaxácie problému (2)-(3) pomocou hornej hranice Martella a Totha. Spätný prechod nastane vždy, keď horná hranica nepresiahne aktuálne riešenie, alebo keď sa porušia niektoré obmedzenia (3)-(5).

V úlohe 2-6 sa neberie do úvahy, že rezanie je gilotínové. Vzhľadom na všetky podmienky uvažujeme o rekurzívnej metóde riešenia.

7. Spôsob riešenia

V tejto podsekcii uvažujeme o rekurzívnom postupe na výpočet dvojrozmerných gilotínových obalov. V postupe nazývanom rekurzívny označujeme každé platné usporiadanie podmnožiny prvkov na liste ako platné balenie. Každé platné balenie môže byť reprezentované ako nezáporný celočíselný vektor, kde každá súradnica predstavuje počet prvkov typu v balíku. Označiť ako zisk z balenia. Hovoríme, že prípustné balenie je maximálne, ak do listu nemožno zabaliť žiadne ďalšie prvky, t.j. sa ukazuje ako nerealizovateľné pre všetky typy prvkov, takže . Na dva platné balíky a definujeme nové balenie takto: , .

Rekurzívna procedúra implicitne vymenúva všetky platné obaly rekurzívnym rozdelením listu na dve časti pomocou (horizontálneho alebo vertikálneho) rezu gilotínou. Postup berie ako vstup parameter , čo je spodná hranica zisku akéhokoľvek prípustného (gilotínového) balenia.

Ako poznamenali Christodes a Whitlog, pre akýkoľvek problém s dvojrozmerným obalom existuje optimálne riešenie zodpovedajúce normálnemu vzoru, to znamená riešenie, v ktorom pre každý zabalený prvok jeho ľavá strana susedí s pravou stranou iného prvku. prvok alebo pravú stranu listu. To znamená, že môžeme uvažovať len zvislé rezy podľa súradníc , ktoré možno získať ako kombináciu šírok prvkov, t. j. ktoré patria do množiny:

Podobným spôsobom uvažujeme iba vodorovné rezy pozdĺž súradníc patriace do nasledujúcej sady:

Predpokladáme, že prvky oboch množín a sú zoradené vzostupne a množiny a .

Daný a a rozhodovací prah , nech je množina všetkých realizovateľných (prípustných) balení daných prvkov do hárku veľkosti , ktorý môže priniesť (spolu so zvyškovými prvkami a hárkom) zisk väčší alebo rovný . Pre dve dané uspokojivé balenia A formálne označujeme párovým súčtom balení v súpravách a:

Intuitívne je sada obalov, ktorú možno získať kombináciou akéhokoľvek obalu s akýmkoľvek obalom, bez ohľadu na veľkosti sád a . Je jasné, že keď je množina definovaná, môžeme nájsť množiny s podmienkou, že všetky (resp. ) prvky patria do usporiadanej množiny (resp. ). Podobným spôsobom nám znalosť množiny umožňuje definovať množiny. V skutočnosti stačí poznamenať, že každý balík , ktorý môže produkovať zisk aspoň rovný , v obdĺžniku možno získať ako súčet dvoch prípustných balení definovaných pre menší obdĺžnik. Formálne: , kdekoľvek A pre niektorých, príp A pre niektoré . Ak teda vieme a pre každé a , môžeme ľahko získať (vygenerovať) rekurzívnym spôsobom .

Základný algoritmus možno vylepšiť nasledovne. Pre každý balík na hárku šírky a výšky možno pri výpočte zvyškovej plochy získať hornú hranicu, povedzme, pre maximálny zisk. Za týmto účelom zvážte príklady batohov s kapacitou , typy prvkov možné v kópiách, každý so ziskom a hmotnosťou. Optimálne riešenie z tohto prípadu alebo akákoľvek horná hranica tejto hodnoty poskytuje hornú hranicu maximálneho zisku, ktorý možno dosiahnuť zabalením zostávajúcich prvkov do zvyšku listu. Je jasné, že všetky prvky také, že môžu byť odstránené zo súboru, pretože nemôžu viesť k realizovateľnému riešeniu, ktoré má zisk väčší ako . V našej implementácii vypočítame hodnotu hornej hranice optimálneho riešenia (jednorozmerného) prípadu problému s batohom (pozri ). Hodnoty horných hraníc a získané Haifi a rovnaké hodnoty navrhnuté Yang-Gun a Kang pre dvojrozmerný (ortogonálny) problém s batohom bez obmedzení, používame minimum týchto hodnôt ako horné viazaný.

Okrem toho si všimnite, že šírka a výška plachty sa môže zmenšiť na a , čo má za následok nižšiu silu batohu pri riešení problému uvoľnenia batohu, teda presnejšie horné hranice. Nakoniec si všimnite, že pre každú súpravu musí byť uložené len maximálne povolené balenie a že akýkoľvek prvok, ktorý nie je maximálny, môže byť ignorovaný. To znižuje počet prvkov v , a tým aj požiadavky na pamäť a čas výpočtu algoritmu.

8. Vstupné a výstupné dáta systému

Vstupné Data:

1. Šírka obdĺžnikového listu;

2. Výška obdĺžnikového listu;

3. Veľkosti štvorcov;

Výkon:

5. Obdĺžniky umiestnené na obrazovke monitora;

6. Textový súbor s informáciami o vpísaných obdĺžnikoch;

7. Ďalšie informácie o prispôsobení obdĺžnikov vo forme rôznych správ na obrazovke.

8.5. Vývoj používateľského rozhrania

Používateľské rozhranie je vhodné urobiť v grafickej podobe, pretože je to najpohodlnejšie na používanie.

Vstupná a výstupná forma údajov

Obrázok 1. Používateľské rozhranie

Najprv zadáme šírku obdĺžnika, stlačíme enter, výšku - enter a zadáme veľkosti štvorcov, napríklad 23 - enter, 45 - enter atď., stlačením 0 zastavíme zadávanie štvorcov a zobrazí sa výsledný súbor na mieste, kde je uložený projekt .png, kde vidíte balenie štvorcov.

To isté okno zobrazuje informácie o počte štvorcov určitých veľkostí. Stlačte 0 a zobrazí sa informácia o čase vyplnenia obdĺžnikovej plochy štvorcami.

Po vykonaní všetkých akcií dostaneme:

Obrázok 2. Výsledok programu

a samotný balík:

Obrázok 3. Balenie štvorcov do obdĺžnika

Stôl 1.

Číselné výsledky programu

	Veľkosť obdĺžnika	Odhadovaný počet štvorcov	Celkový počet štvorcov

Záver: čím viac štvorcov zadáte, tým dlhší bude čas vykonania algoritmu.

9. Záver

V súlade s účelom štúdie boli stanovené a splnené tieto úlohy:

1. Formulácia uvažovaných problémov rezania a balenia v zmysle matematického programovania a kvalitatívne posúdenie metód ich riešenia;

2. Bol vyvinutý a preskúmaný algoritmus na riešenie problému skladania štvorcov rôznych veľkostí do obdĺžnika;

3. Efektívnosť vyvinutej metódy bola analyzovaná na základe výsledkov numerických experimentov.

Bibliografia:

1.Tekhtran / Cutting sheet material [Elektronický zdroj] - Režim prístupu. - URL: http://9132222.ru/catalog/soft/techtran/textran.html (prístup 6/12/2014).

2.Caprara A, Monaci M. K problému dvojrozmerného batohu. Operations Research Letters 2004;32:5–14.

3. Christofides N, Whitlock C. Algoritmus pre problémy dvojrozmerného rezania. Operačný výskum 1977;25:30–44.

4. Hifi M. Zlepšenie presného algoritmu Viswanathana a Bagchiho pre obmedzený dvojrozmerný rezný materiál. Počítače a operačný výskum 1997;24:727–36.

5. Martello S, Toth P. Problémy s batohom: algoritmy a počítačové implementácie. Chichester: John Wiley & Sons; 1990.

6.Pisinger D, Sigurd M. Použitie dekompozičných techník a programovania obmedzení na riešenie problému dvojrozmerného bin-packingu. INFORMUJE Journal on Computing 2007;19:36–51

7.Young-Gun G, Kang MK. Nová horná hranica pre neobmedzené dvojrozmerné rezanie a balenie. Journal of the Operational Research Society 2002;53:587–91.