Példa egy gráf csúcsai közötti távolságok mátrixára. Algoritmus az erősen kapcsolódó komponensek azonosítására

cm. Lineáris programozási modellek forgácsolási problémák megoldására.

1. számú példa. A papírgyártó cég termékeit szabványos szélességű - egyenként 2 méteres - papírtekercsek formájában állítják elő. A fogyasztók külön megrendelése alapján a vállalat más méretű tekercseket szállít, amelyekhez szabványos tekercseket vágnak. A tipikus tekercsrendelések nem szabványos méretek táblázatban vannak megadva.

Ilyen kombinációkat kell találnunk különféle lehetőségek szabványos tekercsek vágása, hogy a beérkezett rendelések teljes mértékben elégedettek legyenek minimális veszteségek(Pazarlás).
Nézzük meg az összes lehetséges lehetőséget a szabványos tekercs vágására, a megfelelő adatokat a táblázat tartalmazza.

tekercs szélessége (m)	Tekercsvágási lehetőségek						Minimális tekercsszám
	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
Hulladék m	0,4	0,3	0,1	0	0,1	0,2	-

Határozzuk meg a változókat:
X j - az opció szerint vágott standard tekercsek száma j, j = 1, 2, 3, 4, 5, 6.
A korlátozások közvetlenül kapcsolódnak ahhoz a követelményhez, hogy biztosítsák a szükséges számú nem szabványos tekercs előállítását. A táblázat adatait felhasználva a következőket kapjuk:
2X 2 + 2 X 3 + 4 X 4 + X 5 = 150 - 0,5 m széles tekercsek száma,
X 1 + X 2 + 2 X 5 = 200 - 0,7 m széles tekercsek száma,
X 1 + X 3 + 2 X 6 = 300 - 0,9 m széles tekercsek száma.

A papírveszteség (hulladék) teljes mennyisége (m-ben) a következő formában jelenik meg
0,4 x 1 + 0,3 x 2 + 0,1 x 3 + 0,1 x 5 + 0,2 x 6.

És így, matematikai modell V Általános nézetúgy néz ki, mint a
min f(x) = 0,4 x 1 + 0,3 x 2 + 0,1 x 3 + 0,1 x 5 + 0,2 x 6.
korlátozásokkal:
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

Anyagvágási probléma

Ez a feladat egy olyan terv kidolgozása, amely minimális hulladékkal (hosszban, területen, súlyban, költségben stb.) biztosítja a szükséges termékkészletet az anyagok vágásakor, vagy biztosítja a termékkészletek maximális számát. 2. példa. Optimális tervet kell kidolgozni a szabványos acéllemezek vágására, biztosítva a tervezett számú különböző típusú nyersdarab minimális összes hulladékkal történő kitermelését, ha ismert, hogy egy tétel acéllemezből négyféle acéllemezt kell vágni. különböző nyersdarabok b i mennyiségben (i = 1, 2, ..., 4) darab . Egy szabványos méretű acéllemez négyféleképpen vágható. Mindenkinek lehetséges módja vágás megfelel a vágási térképnek. A nyersdarabok darabonkénti kibocsátása a vágási térképekről ismert különböző típusok a ij (i = 1, 2,…4; j = 1,2,…,4), valamint c j hulladékterület (j = 1, 2,…,n) egy acéllemez j-edik vágással történő vágásakor módszer . Hány acéllapot kell ilyen vagy olyan módon levágni, hogy a hulladék minimális legyen?

3. táblázat

Fajták üresek	Célterv a munkadarabok számára (b 1)	Különböző típusú nyersdarabok (db) kimenete kártyák vágásából (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
Hulladék terület, m2 (cj)		1,4	0,1	2,1	0,1

Készítsük el a probléma gazdasági és matematikai modelljét. Jelöljük x j-vel azt a forrásanyag (acéllemez) mennyiségét, amelyet a j módszerek valamelyikével le kell vágni. A feladatban szereplő kényszereknek meg kell felelniük a munkadarabok tervezett kimenetének különféle típusok. A célfüggvény lényege, hogy a vágás során megtaláljuk a minimális hulladékmennyiséget

F=1,4 x 1 +0,1 x 2 +2,1 x 3 +0,1 x 4 →(perc).
Az i-edik típusú munkadarabok teljesítményének korlátozásai minden j forgácsolási módnál:

3. példa. Egy mintából egy egységnyi anyag kerül átvágásra (vágásra, feldolgozásra). L különböző komponenst kell belőle készíteni a b 1, b 2,…, b l számokkal arányos mennyiségben (teljességi feltétel). Minden anyagegység vágható n különböző utak, és az i-edik módszerrel (i = 1, 2,…,n) a k-adik szorzat ik egységeit adja (k = 1, 2,…,l). Olyan vágási tervet kell találni, amely a maximális számú készletet biztosítja.
Készítsük el a probléma gazdasági és matematikai modelljét.
Jelöljük x i-vel – az i-edik módszerrel levágott anyagegységek számát, x-szel pedig a legyártott termékkészletek számát. Ekkor a célfüggvény keresésre redukálódik

F=x→(max),
korlátozásokkal: az egységeinek összegével megegyező teljes anyagmennyiséggel, különféle módon vágva; a változók teljességének és nem-negativitásának követelménye szerint.

4. számú példa. A vállalkozás rendelkezik L m hosszúságú rönkökkel, amelyeket l 1, l 2, l 3 m hosszúságú darabokra kell vágni p 1, p 2, p 3 mennyiségben.
Optimális tervet kell készíteni az anyag vágására, amely minimális hulladékot biztosít, a munkadarabok kimeneti tervének teljesülése mellett. A kiinduló adatokat a táblázat tartalmazza.

Feladat	Hossz	A munkadarabok méretei, m			Üresdarabok száma, db.
		l 1	l 2	l 3	1. o	p2	3. o
68	6,5	2,1	2,3	1,4	600	720	900

Megoldás: Először is készítsük el a feladatunk matematikai modelljét. Lehetséges lehetőségek A vágást és a hulladékot mindegyikre táblázat formájában írjuk le.

Munkadarab hossza	Vágási lehetőségek							Üreshelyek száma
	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
Maradt, m	0,2	0	0,9	0,7	0,2	0,5	0

Jelöljük x i-vel az i-edik opció szerint kivágott rönkök számát (i=1..7). Ekkor a teljes hulladékegyenleget lineáris függvényként írjuk fel:
Z = 0,2x1 + 0x2 + 0,9x3 + 0,7x4 + 0,2x5 + 0,5x6 + 0x7
Ebben az esetben meg kell felelni a terv teljesítésének feltételeinek a üregszámra, pl.
3x 1 + 2x 2 + 2x 3 + x 4 + x 5 = 600
x 2 + x 4 + 2x 6 + x 7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900

Így a probléma megoldásához meg kell találni a minZ-t a korlátozások alatt. Mivel minZ = -max(-Z(x)), akkor a függvény minimalizálásának problémája helyett a függvény maximalizálásának problémáját fogjuk megoldani:
Z = -(0,2x1 + 0x2 + 0,9x3 + 0,7x4 + 0,2x5 + 0,5x6 + 0x7)

5. számú példa. Egy termék varrásához 6 részt kell kivágnia az anyagból. A ruhagyár két lehetőséget fejlesztett ki az anyag vágására. A táblázat (alul található) a vágási lehetőségek jellemzőit mutatja 10 m 2 -es szövetre, a teljességet, i.e. részletek száma bizonyos típus, amelyek egy termék varrásához szükségesek. Havi szövetellátás varrástermékekhez ebből a típusból 405 m2. A tervek szerint ezen az estén 90 tárgyat varrnak meg.
Készítse el a probléma matematikai modelljét, amely lehetővé teszi a varrási tervet minimális mennyiségű hulladékkal a következő hónapban.

táblázat - Vágási lehetőségek jellemzői 10m2-es szövetdarabokhoz

Vágási lehetőség	Alkatrészek száma, db/vágás						Hulladék, m 2 /vágás
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Teljesség, db/termék	1	2	2	2	2	2

A feladat matematikai megfogalmazása

Feladatváltozók
Ebben a feladatban a szükséges mennyiségek nincsenek kifejezetten feltüntetve, de elhangzik, hogy a havi tervet 90 termék varrására kell teljesíteni. Havi 90 termék varrásához szigorúan meghatározott számú alkatrészt kell levágni. A vágás 10 m2-es szövetdarabokból kétféle módon készül, ami lehetővé teszi, hogy különböző számú alkatrészt kapjon. Mivel előre nem ismert, hogy mennyi szövetet vágunk le az első módszerrel és mennyit a második módszerrel, a szükséges értékeket az egyes módszerekkel vágott 10 m2-es szövetdarabok számára lehet beállítani:
x 1 - az egyenként 10 m 2 -es szövetdarabok száma, az első módszerrel vágva egy hónapon belül, [vágás/hó];
x 2 - az egyenként 10 m 2 -es szövetdarabok száma, az első módszerrel vágva egy hónapon belül, [vágás/hó];

Objektív funkció
A probléma megoldásának célja a terv minimális mennyiségű hulladékkal való teljesítése. Mivel a termékek száma szigorúan megtervezett (90 db/hó), ezért ez a paraméter nem a TF-et írja le, hanem egy korlátozásra utal, melynek be nem tartása azt jelenti, hogy a probléma nem oldódott meg. A terv végrehajtásának hatékonyságának kritériuma pedig a „hulladék mennyisége” paraméter, amelyet minimálisra kell csökkenteni. Mivel az 1. lehetőség szerinti egy darab (10 m2) szövet vágásakor 0,5 m2 hulladék keletkezik, a 2. lehetőség szerint pedig 0,35 m2 (lásd az 1. táblázatot), akkor teljes vágási hulladéknak (CF) van a formája
L(x) = 0,5x1 + 0,35x2 = perc,

Korlátozások
A különböző módokon végzett szövetvágások számát a következő feltételek korlátozzák:

• A varrástermékek tervet teljesíteni kell, vagyis a vágott részek összlétszáma akkora legyen, hogy havonta 90 termék lehessen belőle varrni, azaz: legyen legalább 90 db 1. típusú és legalább 90 darab. egyéb típusok 180 (a teljességért lásd a táblázatot).
• A szövet fogyasztása nem haladhatja meg a raktárban egy havi készletet;
• A vágott anyag darabszáma nem lehet negatív.

A kabátvarrási terv korlátozásainál a következő értelmes jelentkezési lap található.
(Össz. darabszám 1. darab minden opcióhoz)≥ (90 darab);
(Össz. darabszám 2. darab minden opcióhoz) ≥ (180 darab);
(Össz. darabszám 6. darab minden opcióhoz) ≥ (180 darab);

Matematikailag ezek a korlátozások a következőképpen vannak megírva :
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;

A textília felhasználásának korlátozása van következő űrlapokat bejegyzés:
Tartalmas
(összes havi vágás mennyisége)≤ (405 m2)
Matematikai
x 1 + x 2 ≤ 405/10

A vágott szegmensek számának nem-negativitását az űrlap adja meg
x 1 ≥ 0, x 2 ≥ 0

Így a probléma matematikai modelljének formája van
L(x) = 0,5x1 + 0,35x2 = min [m 2 hulladék/hónap],
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

6. számú példa. A fűtési hálózathoz 69 db cső van, egyenként 1070 cm. 130, 150 és 310 cm-es csövekre kell vágni.

1. szakasz. Határozza meg az optimális csővágási lehetőségeket.

Vágási lehetőségek	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
Maradék	10	0	20	40	60	50	70	90	110	100	120	10	30

2. szakasz.
Készítsük el a probléma gazdasági és matematikai modelljét. Jelöljük x j-vel azoknak a csöveknek a számát, amelyeket a j módszerek valamelyikével el kell vágni. A célfüggvény a vágás során keletkező minimális hulladék megtalálásában rejlik:
10x1 + 20x3 + 40x4 + 60x5 + 50x6 + 70x7 + 90x8 + 110x9 + 100x10 + 120x11 + 10x12 + 30x13 → perc

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

Válasz: csak a második vágási lehetőséget kell használni (nulla hulladék)

A fűrészüzemi termelés gazdasági hatékonysága nagymértékben függ az alapanyag felhasználás mértékétől. Gyártásban használt berendezések, rönkök ésszerű vágása az optimális szállítások szerint, hozzáértő tervezés vágás határozza meg hatékony használat erőforrások és ennek megfelelően kiváló minőségű termékek.

A fűrészelt alapanyagok vágásának alapvető sémája

A rönkök vágásának módszerei és sémái közvetlenül függenek az előállított termékek minőségére és méretére vonatkozó követelményektől, a nyersanyagok jellemzőitől és a használt berendezések típusától.

A rönkfűrészelés alapvető módszerei
a - kacsázik; b - fával; b’ - két gerenda fogadásával; b" - a gerendák összeomlása; c - szektor; c’ - a szektor fűrészelése radiális deszkákba; c" - érintőtáblákon; g - szegmentális; g’ - összeomlás-szegmens; g" - fa szegmens; d - kör alakú; 1 - szélezetlen táblák; 2 - szélezett táblák; 3 - rack; 4- rúd; 5 – rönkök részei szektorok formájában; 6 — rönkdarabok szegmensek formájában; 7 - egyoldalas szélű táblák

Vágja le a rönköket kacsázik abból áll, hogy elosztjuk vele párhuzamos síkok egy vagy több vágószerszámot. Ez a séma lehetővé teszi, hogy az éves rétegekhez képest eltérő rétegelrendezésű élezetlen táblákat kapjunk. A módszer racionális 18 cm átmérőjű rönkök vágásakor és görbületű törzsű fűrészrönkök esetében (leggyakrabban nyírfa nyersanyagok vágásakor használják, amelyek az esetek 70% -ában egyszerű vagy összetett görbületűek).

A buktatós vágás után kapott szélezetlen táblákat élezettre dolgozzák fel, vagy szélezetlen nyersdarabokba vágják át.

Abban az esetben, ha a késztermékek túlnyomó mennyiségének rendelkeznie kell megállapított méreteket keresztmetszet, vágási módszert alkalmaznak faanyaggal. Ezt a sémát nagy átmérőjű rönkök vágására is használják általános célú fűrészáru előállítása során.

A gerendákkal történő fűrészelés több ripszgépen, két menetben történik. Ebben az esetben az első szakaszban a kívánt deszka szélességével megegyező vastagságú gerendákat nyernek kerek fából. Ezeket a gerendákat ezután a szükséges vastagságú és méretű táblákra osztják.

Nagy méretű gerincek vágására használják szegmens és szektor mód. Érdemes megjegyezni, hogy ezek a sémák specifikusak és használatosak speciális típusok tangenciális és radiális fűrészáru előállítására.

A nagy rönkök és a belső rothadásos rönkök egyedi vágását végzik körkörös módon.

Kerekfa feldolgozása marási módszerrel

A fűrészelt nyersanyagok marással történő keresztmetszetének kialakítása ennek a módszernek a fűrészeléssel történő kombinálásával történik. Ebben az esetben három fő vágási sémát használnak:

• kétélű nyaláb beszerzése az első csomópontnál;
• szélezetlen deszkák és kétélű faanyag beszerzése a fejgépen;
• a szélezett fűrészáru keresztmetszeti méreteinek megfelelő méretű profilgerendák előállítása táblák gyártásával egy berendezésen.

A kétélű fűrészáru félkész termék szélezett fűrészáru további előállításához a fa deszkákra osztásával.

A rönkök marással történő vágásának alapvető módszerei
a - kétélű fa gyártása a fejgépen; b - kétélű fa és szélezetlen deszka gyártása; c - profilgerenda beszerzése; d - hosszú élű fűrészáru beszerzése; d - szélezett fűrészáru beszerzése különféle hosszúságok; e - különböző hosszúságú és szélességű szélezett fűrészáru gyártása; 1 - fűrészáru zóna; 2 - szélezett fűrészáru; 3 - alakos gerenda; 4 - kétélű gerenda; 5- szélezetlen fűrészáru

A szállítás fogalma körfa fűrészeléséhez

Az állvány fűrészekből, szorítóelemekből és fűrészközi távtartókból álló készlet, amelyet egy fűrészkeretbe szerelnek be, hogy meghatározott vastagságú fűrészárut állítsanak elő.

Vagyis a szállítás az egységes minőségű és méretű fűrészalapanyagok (rönkök) adott paraméterű és minőségű termékekké történő darabolásának terve.

Fűrészeléskor a kacsázó helyzet megvalósul digitális egymás mellett a fűrészelt táblák vastagságát milliméterben megadva:

19-19-32-32-19-19.

Ez a számsor azt jelenti, hogy a rönk középső részéből két 32 mm vastag deszkát, az oldalsó részekből pedig négy 19 mm vastag deszkát vágunk le.

Például fűrészeléssel történő dőlésszögeléskor a beállítás két számsorba van írva, rönk (első menet) és fa (második menet) fűrészeléséhez:

19-19-150-19-19 (első menet);

19-32-40-40-32-19 (második menet).

Az előző példához hasonlóan ezek a számok azt jelentik, hogy az első sor fejgépén, amelyen a rönk van fűrészelve, egy 150 mm vastag gerenda és ennek megfelelően négy élezetlen, egyenként 19 mm-es deszka (két-két oldalon) ) kapunk, és a második sor gépén a kapott faanyagot 40, 32 és 19 mm vastag deszkákra fűrészeljük.

Az egyfűrészes gépeken történő rönkfűrészeléskor a pozíció határozza meg a vágási sorrendet.

Szállítások előkészítése

A kínálat összeállítása lényegében a táblák optimális méreteinek és vastagságarányainak meghatározását jelenti, biztosítva racionális használat a rönk átmérőjének keresztmetszete.

A szállítmány elkészítésének alapszabályai:

• a pozícióknak szimmetrikusnak kell lenniük;
• egy készletben nem lehetnek 5 mm-nél kisebb vastagságú táblák;
• A készlet összeállításakor kezdje a legnagyobb keresztmetszetű fűrészáruval;
• a deszkák vastagságának csökkennie kell a rönk tengelyétől a kerület felé;
• ne biztosítson kettőnél több vékony (16, 19 mm-es) deszka vágását a betáplálás szélén, amikor nyersanyagot vág a fűrészüzem keretein;
• válassza ki a fa magasságát az első menetben a specifikációkban felsorolt ​​táblavastagságok szélessége szerint;
• látta a második lépésben fűrészelt fa homlokzatát azonos vastagságú deszkákba;
• a fűrészáru készletek elkészítésekor a specifikációk megadása nélkül használjon táblázatos vagy grafikus módszereket;
• gerenda módszerrel történő fűrészeléskor határozza meg a gerenda vastagságát a rönk felső átmérőjének (0,06-0,08) arányából - d;
• a beállítás nem haladhatja meg a rönk átmérőjének maximális lefedettségét;
• határozza meg a központi táblák minimális vastagságát ezt a táblázatot:

A szállítmányok elkészítésének grafikus módja

Lehetőség van a GOST szabványoknak megfelelő racionális szállítás összeállítására konkrét keresztmetszeti méretek megadása nélkül (specifikációs feladatok nélkül) - speciális grafikonok segítségével.

Példa a fűrészáru maximális vastagságának diagramjának használatára a P.P. szerint. Aksenov

A maximális vastagság meghatározásához az állvány tengelye és a kívánt tábla állványfelületének belső része közötti távolságot ábrázoljuk az abszcissza tengelyen. Ezután függőleges vonalat húzunk, amíg az egy adott átmérőnek megfelelő ferde vonallal nem metszi, és a kapott metszéspontot a koordináta tengelyére mozgatjuk.

A fűrészáru optimális vastagságának grafikonja G.G. szerint. Titkov

A program célja, hogy optimalizálja a profilok és más hosszú anyagok (fa, rönkök, csövek, ablakpárkányok) vágását.
A „sűrű fektetés” algoritmust alkalmazzák, vagyis a kivett terméket a munkadarab legrövidebb fennmaradó részére fektetik, amelyre felhelyezik. Ha nem fér el sehova, új üres lapot vesznek. Az optimalizálási feladat egy olyan terméksor megtalálása, amelyben kevesebb munkadarabot használnak fel, és hosszabb lesz az üzleti selejt hossza. Az első lépésben a termékeket a rudakba helyezzük véletlenszerű sorrendben. Kialakul egy „kezdeti populáció”. A döntési folyamat során a populáció mutálódik és szaporodik, a sikertelen példányok elpusztulnak, a legjobbak pedig tovább fejlődnek. Minden olyan, mint az állatban és növényvilág + mesterséges szelekció.

Élő bemutató a weboldalon

Az alábbi példa nem egy statikus kép, hanem egy működő webalkalmazás.
A profilvágást a gombbal indíthatja el Rajt, állítsa be a termék és a munkadarab méreteit, módosítsa az optimalizálási beállításokat és értékelje a megoldást.
Természetesen a böngészőoptimalizáló lassabban működik, mint a natív program, de lehetővé teszi, hogy működőképes eredményeket érjen el ingyenesen anélkül, hogy bármit is le kellene töltenie és telepítenie kellene a számítógépére.

Előnyök

• Az Oknosoft:cutting vágási térképeket biztosít Jó minőség. Számos megvalósítás igazolja, hogy 30 kontúrból álló kötegek (~120 szegmens) optimalizálása esetén a tényleges vágási arány nem haladja meg az 1%-ot.
• A forrásadatok olvasásához és a vágási eredmények rögzítéséhez a program egyszerű szöveges fájlformátumokat használ, ami leegyszerűsíti az integrációt az ügyfél által megvalósított számviteli rendszerekkel
• Szükség esetén a vágás végrehajtható Linux vagy OS X alatt böngészőben vagy Node.js-ben, a paraméterek url-en, web-socket-en vagy javascript-objektumokon keresztül történő átadásával

Lineáris optimalizáló algoritmusok

A windowssoft:cuttingben használt genetikai algoritmus. A lényeg a következő:
Nevezzünk megoldásnak minden termékeloszlást a sorok között. Határozunk meg egy célfüggvényt, amely lehetővé teszi a megoldások minőségének összehasonlítását. Alakítsunk több önkényes döntések, nevezzük őket generációnak. Határozzuk meg a következő generáció megszerzésének szabályait. Másolatok a legjobbakkal cél funkció továbbítani a legtöbb„génállományunk”, ez a „mesterséges szelekciónk”. Most már csak a rendszert a saját eszközeire kell hagyni, hagyni, hogy mutáljon, és optimalizálja a vágási eredményeket
A fejlesztés során teszteltük a „Monte Carlo” módszert, amikor „példányaink” véletlenszerűek és egymástól függetlenek, valamint a „Hangya algoritmusokat” (ACO-hangya kolónia optimalizálás). Mindegyik módszer elég hatékonynak bizonyult, de a genetikai algoritmus valamivel hatékonyabbnak bizonyult

Szállítási lehetőségek

Két szállítási lehetőség van az Oknosoft vágómodulhoz: vágás – mellékelve átfogó megoldás Egyedi gyártás kezelése és külön futtatható fájl formájában. A vágóprogrammal való interakció az első forgatókönyvben teljesen el van rejtve a felhasználó elől. Az operátor szabványos 1C dokumentumokkal dolgozik:

• A vevői megrendelések alapján gyártási terv készül
• A terv alapján - műszakos megbízások terméklistával és szükséges anyagokkal
• A vágás optimalizálás a termelési feladaton belül történik
• Az optimalizálási folyamat során a program átveszi a folyamatban lévő munkából az üzleti szálakat, és elhelyezi az újonnan kialakított üzleti darabokat a mobil raktárban
• A műszakos feladat vágólapokat nyomtathat kézi gyártáshoz, vagy fájlokat generálhat CNC gépekhez
• Ezenkívül műszakos munkából nyomtatják a vágott termékek címkéit, valamint a kocsik és piramisok elrendezési diagramjait.
• A gyártási megbízások alapján követelményeket alakítanak ki - számlák az anyagok műhelybe történő szállításáról, figyelembe véve az igényeket és a szabványos csomagolást

Program interfész (lineáris vágó API)

A bemeneti adatfájl a setup.ini, amely a végrehajtható fájl mappájába kerül.
A kimeneti adatfájlok - result.txt, resultproduct.txt és resulttick.txt - ugyanabban a mappában jönnek létre.
Az oldal végén található hivatkozás segítségével letöltheti az Oknosoft:cutting bemutató adatait tartalmazó fájlokat. A következő címkék használatosak a fájlokban:

• Outputvariant – a fájl kimeneti fájlstruktúrája. Lehetséges értékek: tab, oknosoft, alapértelmezett oknosoft
  • Az "oknosoft" opcióban az resultproduct.txt és az resultstick.txt fájlok generálódnak a termékek munkadarabokon való elhelyezésével és az eredményül kapott trimmekkel kapcsolatos információkkal.
  • A "tab" opció öt értéket jelenít meg "tab" karakterekkel elválasztva: termékhossz, rúdszám, rúdhossz, vágási szám és maradék munkadarab
• Algoritmus – a használt algoritmus. Lehetséges értékek: véletlenszerű, konzervatív, genetikai, alapértelmezett genetikai
  • Véletlenszerű – az opciók véletlenszerű kiválasztása
  • Konzervatív – a következő iteráció példányai ugyanattól a „szülőtől” származnak
  • Genetikai - két szülőtől
• Variáció - variabilitás, a "konzervatív" és a "genetikus" algoritmusok paramétere. Minél magasabb, annál kevésbé „hasonlítanak” az utódok a szüleikre. Az alapértelmezett az 1.
• Generációk – algoritmus iterációk száma, alapértelmezett 40000
• Személyek - a „példányok” száma a „populációban”, az egy iteráció során használt megoldások száma. A "véletlenszerű" algoritmus egyszerűen generációk*személyek iterációit hajt végre egy példányban (megoldás)
• KnifeWidth - fűrészszélesség
• StickLength – az új bot hossza
• Termékek - termék hossza
• Scraps – a darabolás során használt selejt hossza
• Wrongsnipmin – egy „rossz” minta minimális hossza
• Wrongsnipmax – a „rossz” díszítés maximális hossza
  Az optimalizálási eredmények nem tartalmaznak olyan vágásokat, amelyek hossza Wrongsnipmin és Wrongsnipmax között van

Páros vágás

Páros vágást támogató gépek adatainak előkészítésekor használatos. Ebben az esetben egyszerre két profilrudat helyeznek a gépbe, és egy vágási ciklusban két egyforma félkész terméket készítenek

A páros vágás problémáját úgy oldjuk meg, hogy az adatokat csoportosítjuk az optimalizáló programba való átvitel előtt, majd a vágási eredményeket termékpárokra és nyersdarabokra duplikáljuk. Az UPZP belsejében történő vágáskor a rendszer figyelembe veszi az elem tulajdonságait, és a vágógépek képességeitől függően egyszeri vagy páros vágást alkalmaz

Nagyszámú termék darabolása

Egyrészt a jó minőségű optimalizálás eléréséhez jelentős számú terméket kell bevinni a programba különböző hosszúságú, hogy az optimalizálónak legyen „rendeznivalója”. Másrészt nagyon nagy kötegeknél csökken annak a valószínűsége, hogy meghatározott számú iteráció mellett megtaláljuk a maximumot. Kísérletek kimutatták, hogy a 60–120 darabból álló nyersdarabok tétele az optimális (ami páros vágás esetén 30–60 termékből álló gyártási ciklusnak felel meg). Ha több mint 120 munkadarabot kell optimalizálni, legjobb eredményeketúgy érhető el, hogy a problémát N részre osztjuk, és minden részhez szekvenciális optimalizálást hajtunk végre. A gyártási feladatok kötegek kialakításának feldolgozása képes a termékeket profiltípusok szerint csoportosítani, és a műszakos feladatokhoz maximális varianciával kiválasztani a termékeket, tehermentesítve a kezelőt rutinmunka a gyártási dokumentumok elkészítésével kapcsolatban

Vágási példák és dokumentáció letöltése

• Demo kártyák egyszeres és dupla vágáshoz: 60.01 Lapok vágása
• Dokumentáció és példafájlok:

A matematikában az úthálózatokat (út és egyéb) súlyozott gráf ábrázolja. Települések(vagy metszéspontok) a gráf csúcsai, az élek az utak, az élek súlya az ezen utak mentén mért távolságok.

Számos algoritmust javasoltak súlyozott gráfokhoz. Például a népszerű Dijkstra algoritmus az egyik csúcstól a másikig vezető legrövidebb út megtalálására. Mindezeknek az algoritmusoknak van egy közös alapvető (matematikai) jellemzőjük – univerzálisak, pl. sikeresen alkalmazható bármilyen kialakítású grafikonon. Különösen minden algoritmus esetében ismert a bonyolultsága - ez megközelítőleg megfelel az algoritmus végrehajtási idejének növekedésének a gráf csúcsainak számától függően. Mindez részletesen olvasható például a Wikipédián.

Térjünk vissza gyakorlati feladatokat. Az utakat súlyozott grafikon ábrázolja, de az utak nem akármilyen grafikonok. Más szóval, semmilyen gráfból lehetetlen úthálózatot felépíteni. Ellentétben a virtuális gráfokkal, mint matematikai absztrakciókkal, az utakat emberek építik valós anyagokból, és meglehetősen drágák. nagy pénz. Ezért nem véletlenül rakják le őket, hanem bizonyos gazdasági és gyakorlati szabályok szerint.

Ezeket a szabályokat nem ismerjük, azonban úthálózatokkal való munka során teljesen lehetséges olyan algoritmusok használata, amelyek hatékonyak az útgráfokhoz, bár nem alkalmasak a gráfokhoz egy univerzális ill. matematikai érzék. Nézzünk meg két ilyen algoritmust.

Néhány fontos fogalom és konvenció

1. Súlyozott irányítatlan gráfokat fogunk használni nem negatív élsúlyokkal. Egy régión (országon) belüli utak pontosan egy ilyen grafikont képviselnek.

2. Legrövidebb távolságú mátrix (SDM) – ennek kicsi és egyszerű példája számos útatlaszban található. Ezt a táblát általában így hívják: „távolságok a legfontosabb városok között”. Úgy néz ki, mint a mátrix egy része a főátló alatt vagy felett (a bal felsőtől a jobb alsó sarokig), mert a főátló másik oldalán pontosan ugyanazok a számok vannak, vagyis az M(i, j) = M(j,i). Ez azért történik, mert a gráf, ahogy a matematikusok mondják, nem irányított. A sorok és oszlopok városoknak felelnek meg (a grafikon csúcsai). Valójában egy ilyen táblázat sokkal nagyobb, mivel a gráf csúcsai a városokon kívül az összes falut és kereszteződést is tartalmazzák, de ilyenek nyomtatása nagy asztal az atlaszban persze lehetetlen.

Először is folytassuk (mentálisan) a táblázatunkat felső rész, kapunk egy MKR-t, amely szimmetrikus a főátlóhoz képest, és mostantól csak egy ilyen táblázatot fogunk szem előtt tartani. Ebben az esetben egy bizonyos számú oszlop egyenlő egy azonos számú sorral, és nem mindegy, hogy melyik fogalmat használjuk. Mindkettőt használjuk metszésükhöz.

MKR-ünk lehet: a) előre ismert, mert az MKR keresési módszereinek egyikével számítottuk ki; b) lehet, hogy nem ismerjük az MKR-t, de szükség szerint soronként határozzuk meg. Soronként - ez azt jelenti, hogy a kívánt vonalhoz a távolságot csak a megfelelő csúcstól a többi csúcsig számítják ki, például Dijkstra módszerével.

3. Még néhány fogalom. Egy adott csúcs excentricitása az ettől a csúcstól a tőle legtávolabbiig mért távolság. A gráf sugara az összes csúcs excentricitása közül a legkisebb. A gráf középpontja egy csúcs, amelynek excentricitása megegyezik a sugárral.

Hogy néz ez ki a gyakorlatban? Az úthálózat középpontja az a város vagy kereszteződés, amely a hálózat összes többi pontjától a legkevésbé távol van. Sugár – maximális távolság ettől a központi csomóponttól a legtávolabbiig.

4. Csúcs foka – a csúcshoz kapcsolódó élek száma.
A grófoknál úthálózatok, az összes csúcs átlagos foka a 2-től 4-ig terjedő tartományban van. Ez teljesen természetes – nehéz és költséges metszéspontokat építeni nagy mennyiség szomszédos utakon nem kevésbé nehéz ilyen úthálózatot használni. Az alacsony átlagos csúcsfokozatú grafikonokat ritkanak nevezzük, amint látjuk, az úthálózatok gráfjai pont ilyenek.

1. feladat A gráf sugarának és középpontjának megkeresése a legrövidebb távolságok mátrixával

Vegye figyelembe, hogy a gráfnak több középpontja is lehet, de ezek közül bármelyiket meg akarjuk találni.

Hogyan oldják meg a problémát általános eset? Teljes nézet MKR. Megkeressük a sorban a maximális elemet (az egyes csúcsok excentricitását), majd ezekből a maximális elemekből megtaláljuk a minimumot.

Ez messze nem a legtöbb gyors út. Miért van szükség gyorsabban, ha, úgy tűnik, a grafikon sugara és középpontja egyszer megtalálható? Pl. ezekre vannak problémák, algoritmusok, ahol a keresés során a csúcsok folyamatosan „újra egyesülnek” csoportokba, és az egyes csoportok kritériuma a sugara. Ebben az esetben a sugarat sokszor újraszámolják, és a keresés sebessége azzá válik fontos paraméter. Hogyan lehet gyorsabban megtalálni a sugarat?

A titok az, hogy az úthálózati grafikonokhoz nem szükséges minden elemet megnézni. A gyakorlatban elegendő az összes sor egy nagyon kis részét megnézni.

Lássuk, hogyan működik ez. Tekintsük az MKR mátrix egy sorában lévő értékeket, más szóval, vegyük figyelembe az egyik csúcs és az összes többi közötti távolságot. Könnyen bebizonyítható, hogy a grafikon sugara nem lehet nagyobb, mint ebben a sorban a maximális érték, és nem lehet kisebb, mint a minimális érték ebben a sorban. Matematikailag elmondható, hogy megtaláltuk a felső ill alsó határ számokat, és ha egyeznek, megtaláljuk a számot.

Tegyük fel, hogy csak két A és B sorban találtunk értékeket. Ráadásul az A sorban a maximális érték minimális érték a B sorban (ez az érték az A oszlop és a B sor metszéspontjában lesz). Könnyen bebizonyítható, hogy A a gráf középpontja, a talált érték pedig a sugara. A probléma megoldódott.

Remek, de az úthálózati grafikonokon ilyen helyzet nem valószínű, és így nem is lehet majd megoldani a problémát. Csináljunk valami okosabbat.
Vegyünk néhány B1 és B2 sort. Ezekből a következőképpen fogunk alkotni egy M vektort: ​​M(i)=max. Könnyű bizonyítani, hogy ha minden i sorra a min(M(i)) érték egyenlő az A oszlopban lévő maximális értékkel, akkor ismét A a középpont, és a talált min(M(i)) a sugár.
Ha néhány sor nem elég, akkor több sort is vehet, például hármat: B1, B2 és B3, akkor M(i) = max. Az úthálózati grafikonok sajátossága, hogy nem kell sok vonal (lehet tartani tízig). Ez könnyen ellenőrizhető, ha kísérletezget a meglévő hálózati grafikonokkal, letölti azokat az internetről: link.

Általános esetben és a matematika szempontjából ez természetesen nem így van. Nagyon lehetséges egy olyan elméleti gráf felépítése, amelyben sok B sort kell használni (majdnem mindegyiket A kivételével). Egyszerűen lehetetlen ilyen típusú valódi úthálózatot építeni - nem lesz elég pénz.

Még egy utolsó feladat van hátra. Hogyan lehet gyorsan megtalálni azokat a szerencsés sorokat, B1, B2 stb. A valós úthálózatok grafikonjainál ez nagyon egyszerűen és gyorsan elvégezhető. Ezek lesznek azok a csúcsok, amelyek a legtávolabb vannak egymástól, de nem feltétlenül a legtávolabbiak (matematikailag nem kell megkeresnünk a gráf átmérőjét). Felveszünk egy tetszőleges csúcsot, megkeressük neki a legtávolabbiat, az újnak ismét a legtávolabbit, és így tovább, amíg a csúcspár a legtávolabbinak nem válik egymástól.

Kaptunk egy pár B1 és B2 csúcsot. Megtaláljuk a pár M vektorát a fent leírtak szerint. Az a sor, amelyben min(M(i))-t találtunk, a középpont jelöltje, jelöljük A-val. Ha az A oszlopban a min(M(i)) a maximum, akkor a középpont és a sugár már meg van adva. megtalált. Ha nem, akkor az A oszlopban lévő maximális érték egy másik csúcs távolságának felel meg (nem B1 vagy B2). Szóval megkaptuk új csúcs B3 a listába az M vektor kereséséhez. Alternatív megoldásként megkeresheti a B3 legtávolabbi csúcsát is, és ha az nem B1 vagy B2, adja hozzá B4-ként. Így növeljük a B csúcsok listáját, amíg meg nem találjuk a középpontot és a sugarat.

Szigorúbban egy algoritmussal és szükséges bizonyítékokat-ben van leírva ez az algoritmus, ott vannak megadva az egyesült államokbeli úthálózatok egyes grafikonjain való használatának eredményei is, a linkben és linkben pedig kevésbé akadémikusan, de érthetőbben van leírva.

2. feladat A legrövidebb távolságok mátrixának megkeresése

Leírjuk a legnépszerűbb MKR keresési algoritmusokat (például Floyd-Warshell). Mindegyik univerzális, és egyikük - Dijkstra algoritmusa bináris kupaccal - figyelembe vesz egy olyan koncepciót, mint egy ritka gráf. Ugyanakkor nem használja ki az úthálózatok adottságait sem.

Teljesen más algoritmuson fogjuk használni őket, és a meglévő gráfokon tízszeres gyorsulást kapunk Dijkstra algoritmusához képest. Rögtön megjegyezzük, hogy ennek az algoritmusnak az a sajátossága, hogy egyszerre és pontosan (azaz nem hozzávetőlegesen, nem heurisztikusan) keresi az MCR-t.

Tekintsük az algoritmus alapötletét. Lényege, hogy eltávolítja a gráf csúcsait anélkül, hogy megváltoztatná a fennmaradó pontok legrövidebb távolságát. Ha ezt megtesszük, emlékezve arra, hogy az eltávolított csúcs mely pontokhoz és milyen távolságokra kapcsolódott, akkor egy kivételével az összes pontot törölhetjük, majd visszagyűjthetjük a grafikonba, de a távolságokat már kiszámoltuk.

Kezdjük egy egyszerűvel, egy 1-es fokozatú csúcstal. Mindenképpen eltávolítható. Nincsenek rajta keresztül a legrövidebb utak, kivéve magához a csúcshoz vezető utakat, és pontosan azon a csúcson mennek keresztül, amelyhez az eltávolított csúcsot csatolták.

Legyen A egy 2-es fokú csúcs, és legyen összekötve a B1 és B2 csúcsokkal. Ha a B1-A-B2 útvonal hosszabb ill élével egyenlő B1-B2, egyetlen útvonal sem halad át az A ponton, kivéve magához az A ponthoz vezető útvonalakat (az összes többi a B1-B2 ponton halad át). Ez azt jelenti, hogy az A pont törölhető. Ellenkező esetben, pl. ha a B1-A-B2 rövidebb, mint a B1-B2, vagy egyáltalán nincs B1-B2 él, akkor az A csúcs eltávolítható a B1-B2 él súlyának beállításával összeggel egyenlő mérleg: |B1-A|+|A-B2|. Az A-ból más pontokba vezető útvonal vagy B1-en vagy B2-n halad át, ha ismert a B1 és B2 távolsága, akkor az A-tól való távolság is könnyen kiszámítható.

Ugyanezen elv alapján tetszőleges fokozatú csúcsot eltávolíthat, szükség szerint Bi-A-Bj-t Bi-Bj-re cserélve. Igaz, meg kell értened, mit több fokozat csúcsokat, annál több lehetséges élt kell ellenőrizni. Egy n fokú csúcs esetén ez a szám n(n-1)/2.

Elméletileg így bármely gráfban lehetséges az összes csúcsot törölni, azonban általános esetben szembesülni fogunk az élek számának növekedésével járó gondokkal. Egy n fokú csúcs törlésekor a törlendővel szomszédos csúcsok foka: -1-gyel csökkenhet, változatlan maradhat, n-2-re nőhet. Ebből következik, hogy a 3-as és annál magasabb fokú csúcsok eltávolításakor a fennmaradó csúcsok foka általában nő, a gráf egyre ritkább lesz, és a végén a csúcsok eltávolítása meglehetősen munkaigényes feladattá válik. Az algoritmus általános esetben rendkívül munkaigényes és gyakorlatilag haszontalan, de az általános esetben pontosan ez van.

Az úthálózati grafikonok rendelkeznek egyedi funkció ilyen: sok csúcs nem csak növekedés nélkül, hanem a szomszédos csúcsok mértékének csökkenésével is eltávolítható. Sőt, ha egy adott csúcsot most nem lehet „sikeresen” törölni, akkor később, néhány szomszédos csúcs eltávolítása után, „sikeresen” törölhető.

Ennek megfelelően minden lépésnél egyszerűen ki kell választanunk a törölni kívánt csúcsokat, kezdve azokkal, amelyeket „sikeresebben” törölnek.

Maga az algoritmus részletesebben megtekinthető

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete