Egydimenziós vágás optimalizálás algoritmus
2011-08-29T11:33:01+02:00
2013-05-19T12:06:31+02:00
2022-06-29T08:40:37+02:00
  • A gyakorlati feladat: darabolni kell
    3480 mm-esből 17 darabot,
    2150 mm-esből 38 darabot,
    1820 mm-esből 22 darabot,
    670 mm-esből 8 darabot a 6000 mm-es alapanyagokból
    ...
    Kell: 34 darab 6 méteres szál


    Ezt 33 darabból(~5,9% hulladék) ki lehet hozni(a 34. 6m-es darab meg ajándék nekem ), A hulladékok között van egy 1700-as is.

    1 darab: 2150, 2150 hulladék: 1700 17 darab: 3480, 2150 hulladék: 370 4 darab: 2150, 2150, 670, 670 hulladék: 360 11 darab: 2150, 1820, 1820 hulladék: 210
    Mutasd a teljes hozzászólást!
  • Sziasztok!

    Ez a probléma nálam munkámból fakadóan mindennapos, az alábbi ingyenes szoftvert találtam rá, nekem bejött, mert amit manuálisan kikalkuláltam 10% hulladékra, azt ő megoldotta 0,6% hulladékkal. Szuper, egyszerű, és a nyelvet át lehet állítani magyarra is.

    Neve: CutStoP
    Letölthető regisztráció után innen:
    Nyeste Kft. // Letöltés 1000+ referenciakép
    Mutasd a teljes hozzászólást!
  • Válaszom remélem nem késő és használható erre az örök problémára...
    Sok elméleti matematikai munka található ebben a témakörben (tömény elmélettel, sok kriksz-kraksszal, bizonyításokkal) néhány, programírásra használhatatlan ötlet kódrészlettel.
    Kulcsszavak: bin packing problem, FFD algorithm, one dimensional knapsack problem, nyilvános kulcsú kriptográfia (nem elírás... ).

    Írtam VBA-ban (Excel) egy gyakorlatban is használható (eddig bevált) optimalizáló rutint (rekurzív hívásokkal, mohó sorbarendezéssel, maximalizált számú és -idejű függvényhívással, 5-szörös optimalizálás futással), amit a szakemberek használni tudnak csövek, nyílászáró alapanyagok, stb darabolására, minimalizálandó a darabolási selejteket (matematikaiul: egydimenziós FFD algoritmus aszimptotikus versenyképességi hányados minimalizálás .

    A gyakorlati feladat: darabolni kell
    3480 mm-esből 17 darabot,
    2150 mm-esből 38 darabot,
    1820 mm-esből 22 darabot,
    670 mm-esből 8 darabot a 6000 mm-es alapanyagokból (összesen 85 darabot, 186260 mm összhosszban).
    Kell: 34 darab 6 méteres szál, darabolási összselejt: 16040 mm ((16040+1700)/186260=9,5%), utolsó (6 darab) alapanyag szál maradéka(i): 1700 mm, mely(ek) felhasználható(ak) a következő projekt első alapanyaga(i)ként.
    Mutasd a teljes hozzászólást!
  • Nem tudnátok esetleg kész algoritmust (linket) ajánlani erről?

    De, szerintem biztos. Sőt, a fizetésed felvételét is vállalják érte...

    Amúgy klasszikus backtrack probléma - ez a pár óra alatt már rég megírhattad volna...
    Mutasd a teljes hozzászólást!
  • Ennyit írtam a Google-ba:
    vágás darab site:prog.hu
    Mutasd a teljes hozzászólást!
  • Biztosan én voltam az ügyetlen. Kérlek írd meg, hogy mit kellett volna (milyen címszavakat) keresnem, mert én sajnos nem találtam semmit (pontosabban hasonló kétdimenziós problémára volt bejegyzés, de csak általánosságokat írtak róla).
    Mutasd a teljes hozzászólást!
  • Hello!

    Szerintem ez egy NP-teljes probléma. A hátizsák probléma egy változatának tűnik, és esetedben a hátzsák kapacitása a 6m, a bepakolt tárgyak "súlya" és "értéke" is a levágandó darabok hossza lesz. Ez egy oktatásban teljesen szétszedett feladat, számos egész jó megoldása van.
    Ami számomra nehézzé teszi, hogy a kérdés, hogy hány 6 méteres csőre lesz szükséged. Ha egyenként optimalizálsz a 6m kapacitású "hátizsákokra", akkor a végén kijöhet egy hatalmas veszteség az utolsó pár levágandóból. Azt meg nem mondhatod, hogy egyetlen hosszú csöved van, mert nem.

    Lehet, hogy ez a probléma is jól ismert egyébként. Mindenesetre én biztos erre kutatnék, és dinamikus programozásos megoldást próbálnék adni rá.

    Link.
    Mutasd a teljes hozzászólást!
  • Látom prog.hu oldalain még nem keresgéltél.
    Próbáld ki, érdemes.
    Mutasd a teljes hozzászólást!
  • Adott hosszúságú csövekből szeretnék vágni N különböző hosszúságú és hosszanként különböző mennyiségű darabokat. Milyen sorrendben vágjuk az egyes darabokat, hogy a keletkező veszteség a legkisebb legyen?

    Például: 6 m hosszban gyártott csövekből kell levágni ezeket a méreteket:

    215 cm 38 db
    182 cm 22 db
    348 cm 17 db
    67 cm 8 db
    stb.

    Hány 6 m-es csövet kell felhasználni és mennyi lesz a csövek végén a leeső veszteség?

    Találtam erre vonatkozó angol nyelvű elméleti irodalmat persze kód nélkül.
    Nem tudnátok esetleg kész algoritmust (linket) ajánlani erről?

    Köszönöm a segítséget!
    Mutasd a teljes hozzászólást!
Címkék
abcd