Cutter - 1D cutting optimizer, 1D vágás optimalizálás.
A Cutter program fém, fa és műanyag szálak darabolására szolgál(na). A programozó és matematikus "szakik" sem tudnak a problémára megoldást találni. Látszat megoldás(főleg "Magyarország legnagyobb fejlesztői portálja"-nak nevezett oldalon lévő "szakik"-ra jellemző), hogy "káromkodás"-nak tűnő kifejezéseket használnak(amit másoktól hallottak).
Ilyen kifejezések pl.: a 'linear programming, 'LPSolve', 'Scip', 'egydimenziós FFD algoritmus', 'aszimptotikus versenyképességi hányados minimalizálás' meg nem tudom én micsodák. A másik megoldás
"Magyarország legnagyobb fejlesztői portálja"-n, hogy elbagatelizálják a problémát. Pl. Sting a következőt írta az egyik kérdezőnek: "Amúgy klasszikus backtrack probléma - ez a pár óra alatt már rég megírhattad volna... "
Azért azt a pár órát ő is rá szánhatná, hogy megkapja a Nobel-csontot...
Ezzel azt hiszi a mindennapi ember, hogy milyen tudással vannak megáldva, és hogy mennyire értenek hozzá. A helyzet azonban az, hogy a probléma megoldhatatlan(legalábbis ha normális számítási időt feltételezünk relative sok darabra). Ezt fontos már az elején leszögezni.
Tehát erre a programom sem alkalmas. Azonban annál lényegesen jobb, mint amire számítottam.
A publikus kódjaim Itt megtalálhatók.. Az alap probléma a wikipédián megtalálható: Cutting stock problem, vagy más néven 1D cutting optimizer, 1D vágás optimalizálás.
A programom a következő megoldási sémát használja:
A példában a következőket kell kivágni 6000 mm-es szálakból:
1725, 2
1625, 2
1540, 2
1500, 2
1346, 2
Ez így néz ki, ha egymás után tesszük:
1725 1725 1625 1625 1540 1540 1500 1500 1346 1346
Megnézzük, hogy ebben a sorrendben mennyi szálra fér rá. Az első szálra csak az első 3 darab fér rá, a negyedik darab már csak a második szálra. És így megyünk tovább...
Ha ezzel megvagyunk, akkor "megkeverjük" a sorrendet. Megint megnézzük, hogy így mennyi szálra fér rá. stb...
Nyilván az a jobb, amelyik kevesebb szálat használ fel.
Ha ugyanannyi szálra férnek rá, akkor pedig az a jobb, amelyiknél a leeső darabok négyzetösszege nagyobb(pl. 100 darab 5 cm-es leeső darabnál jobb, ha csak 1 darab 5 m-es darab esik le
-mert az 1 db 5m-est több mindenre fel tudjuk használni, mint az 5cm-eseket-).
A "megkeverés" lehet "véletlenszerűen", vagy ismétléses permutációval. A "véletlenszerű" megkeverésnek is lehet kismillió formája.
A program így néz ki a wikin található példával:
A program nem túl design-os, de nem is erre törekedtem, hanem a minél nagyobb hatékonyságra(már amennyire lehetséges).
A bal oldali szövegmező a levágandó darabok hosszát(ráhagyással együtt!) és darabszámát tartalmazza vesszővel elválasztva.
Jobb oldalt a fenti kettő szövegmezőt szerintem nem kell magyarázni. A szálhossz mm-ben értendő.
A módosított 1.0.0.1-es verzióban már a ráhagyást is meg lehet adni. Lásd alább.
A felső start gomb a legegyszerűbbet csinálja: egyszerűen csak "véletlenszerűen" felcserél két darabot az aktuális sorrendben lévő darabokban.
Felülről a második gomb már jóval bonyolultabbat csinál. Ennek van előnye is, és hátránya is. Ez is a "véletlenen" alapul.
Az alsó start gomb ismétléses permutációt tartalmaz. Ez ha "emberi" idő alatt végezne, akkor ez biztos megoldás lenne a problémára. Ha megfelelő idő alatt lefut, akkor az optimális megoldást adja. Csak sajnos ez kevés darabszám esetén végez emészthető időn belül.
Ahogy kipróbálod, rövid időn belül rájössz, hogy ez a gomb igazából csak dísz. Gyakorlati példákon nem alkalmazható, mert sosem végez.
A középső szövegmezőben jelenik meg az eredmény.
Az Import gomb egyszerű szövegfájlból olvassa be az adatokat. Ezek a szövegfájlok így néznek ki:
Az első sor egy adatot tartalmaz: a szálak hosszát mm-ben. Az utána való sorokban gyakorlatilag a program bal oldali szövegmezőjének a tartalma van.
Az Export gomb egyszerű szövegfájlba írja ki a középső szövegmező tartalmát.
Az Import és Export gombok is nélkülözhetők(főleg az Export), mivel egyszerü szövegmezőben vannak az adatok(ezért a kijelölés(CTRL+A), CTRL+C, a CTRL+X és a CTRL+V is működik, ezért oda írjuk az adatokat, ahová csak akarjuk).
A program nem támogatja, de megengedi, hogy akár mind a három Start gombot elindíthatjuk egyszerre. A középső(eredmény) szövegmezőt ugyanis kézzel kell törölni, valamint a gombok elindítása után azok külön szálon futnak.
A gombok mindig az aktuális szövegmező értékekkel indulnak el, így mindig csak a legutolsó érték látszik, az előzőket nem tudjuk megnézni, hogy milyen adatokkal indítottuk el(ezért írtam, hogy nem támogatja).
A programnak és a "MyCutters.dll"-nek egy mappában kell lennie. A "Cutter.rar" file tartalmaz még öt darab mintát a "peldak" mappában.
A program használata nagyon egyszerü. A bal oldali szövegmezőt, a Szálhosszt és a Próbák számát kell megadni, majd a megfelelő start gombbal elindítani. Ha a szál végzett, akkor a középső szövegmezőben jelenik meg az eredmény(A törléséről nekünk kell gondoskodni).
A program elindítása után az entert megnyomva el is indul a számítás. A 434000 próbával elindítva 40-120 sec. között fut le(gyorsabb gépen szabad maggal gyorsabb).
Ennyi próba után nálam megtalálja a Wikis(Cutting stock) példában az 580 mm-es legnagyobb leeső darabot.
A próbák darabszámát 450-700 ezer közé érdemes beállítani a középső Start gomb használata esetén. A felső Start gomb használata esetén pedig 1-2 millióra. Az alsó Start gomb használatánál nincs jelentősége.
A program, ha indítása után entert nyomunk, akkor nálam a fent látható kimenetet adja.
A wikin található példa 140 mm-es legnagyobb leeső darabbal számol. Az algoritmusomban ez 580 mm. Sztem az 58 centis mégiscsak jobb, mint a 14 centis.
Mert a következő alkalommal sokkal nagyobb valószínűséggel lehet használni.
A "peldak" mappában a "_96_db.txt"-ben lévő példa esetén az általam ismert legjobb megoldás, amikor 22 szálból kihozná, és 3709 mm-es leeső darabot adna ki. Erre azonban a programom nem képes.
A középső start gomb használatával egymillió próba beállítása esetén azonban 3404 mm-es legnagyobb leeső darabot megtalál.Ezért is írtam az elején, hogy erre a problémára megoldás nincs.
Az első start gomb 2215000 próba után(50-120 sec.) 3431 mm-es legnagyobb leeső darabot talál.
Aztán hogy ezt "közeli" eredménynek tartjuk-e, az elég szubjektív dolog. Mindenesetre annál azért jobb, mint amire számítottam.
Van még az alsó start gomb használatára egy példa. "_ism_perm.txt" a file neve. Ezekkel a darabszámokkal még viszonylag elfogadható idő alatt lefut. Amúgy ez tuti az optimális megoldást adja. De próbáld csak megemelni a darabszámokat!
Na ezért mondtam, hogy ez gyakorlatilag csak dísz...
Ha a design nem felel meg, vagy saját magad szeretnél programozni, akkor ott van a "MyCutters.dll". Ezt úgy használod fel, ahogy akarod. A References közé kell felvenni. A névtér neve "MyCutters".
Ebben van három osztály: "Cutter_1", "Cutter_2", "Cutter_3". Mindegyiknek a konstruktora egy stringet vár. Ez a string ugyanúgy néz ki, mint az adatfájlban lévő szöveg. Első sor -> szálhossz.
A többi sorban a levágandó hosszok és darabszámuk vesszővel elválasztva.
A megfelelő osztály létrehozása után a Manipulal() metódust kell meghívni. A "Cutter_3"-at paraméter nélkül. A másik kettő paramétere a próbák száma.
Végezetül a ToString() metódust kell meghívni. A legegyszerűbb használat egy Form alkalmazásban:
C#:
private void button1_Click(object sender, EventArgs e)
{
string str = "5600" + Environment.NewLine +
"2200, 20" + Environment.NewLine +
"2150, 18" + Environment.NewLine +
"2140, 16" + Environment.NewLine +
"2100, 14" + Environment.NewLine +
"2050, 12" + Environment.NewLine +
"2000, 10" + Environment.NewLine +
"1930, 20" + Environment.NewLine +
"1880, 18" + Environment.NewLine +
"1820, 18" + Environment.NewLine +
"1710, 14" + Environment.NewLine +
"1560, 12" + Environment.NewLine +
"1520, 25" + Environment.NewLine +
"1380, 22";
Cutter_2 ct_2 = new Cutter_2(str);
ct_2.Manipulal(434000);
MessageBox.Show(ct_2.ToString());
}
Vb.Net:
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim str As String = "5600" + Environment.NewLine +
"2200, 20" + Environment.NewLine +
"2150, 18" + Environment.NewLine +
"2140, 16" + Environment.NewLine +
"2100, 14" + Environment.NewLine +
"2050, 12" + Environment.NewLine +
"2000, 10" + Environment.NewLine +
"1930, 20" + Environment.NewLine +
"1880, 18" + Environment.NewLine +
"1820, 18" + Environment.NewLine +
"1710, 14" + Environment.NewLine +
"1560, 12" + Environment.NewLine +
"1520, 25" + Environment.NewLine +
"1380, 22"
Dim ct_2 As Cutter_2 = New Cutter_2(str)
ct_2.Manipulal(434000)
MsgBox(ct_2.ToString())
End Sub
VC++:
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
String^ str = "5600" + Environment::NewLine +
"2200, 20" + Environment::NewLine +
"2150, 18" + Environment::NewLine +
"2140, 16" + Environment::NewLine +
"2100, 14" + Environment::NewLine +
"2050, 12" + Environment::NewLine +
"2000, 10" + Environment::NewLine +
"1930, 20" + Environment::NewLine +
"1880, 18" + Environment::NewLine +
"1820, 18" + Environment::NewLine +
"1710, 14" + Environment::NewLine +
"1560, 12" + Environment::NewLine +
"1520, 25" + Environment::NewLine +
"1380, 22";
Cutter_2^ ct_2 = gcnew Cutter_2(str);
ct_2->Manipulal(434000);
MessageBox::Show(ct_2->ToString());
}
Ez ugyanazt csinálja, mint a "Cutter.exe" file induláskor, ha entert nyomunk. Csak nem külön szálban, és persze itt MessageBox-ban jelenik meg az eredmény.
Sajnos a programom az ilyen(végein x dőlésszögü) speciális vágásokkal nem tud mit kezdeni:
A C#-ban készült(de Vb.Net-ben, vagy akár VC++-ban is használható) .dll-t és a .exe-t nem kell telepíteni. A futáshoz .net 3.5 szükséges. Teljesen ingyenes, nem kell hozzá még regisztrálni sem, főleg nem megújítani évente. Annyi lenne csupán a kérésem(de ez is csak kérés), hogy lehetőleg ezen az oldalon keresztül töltsd le.
Annyit csinálok, hogy számontartom a letöltések számát.
Cutter.rar letöltése(14 KB). A Cutter_1.0.0.1.rar Letöltése ajánlott.
A file-t eddig 73 felhasználó töltötte le.
Utoljára frissítve: 2021.03.11