For developers
Problem optymalnego cięcia materiału (1D)
Jak pociąć zestaw wymaganych długości z dostępnych sztang, zużywając ich jak najmniej – to problem optymalnego cięcia materiału (1D): klasyczny i naprawdę trudny problem optymalizacyjny. Wyjaśniamy, czym jest, dlaczego nie da się go rozwiązać siłowo i jak rozwiązuje się go w praktyce, w tym w API, na którym działa ta strona.
Na czym polega problem optymalizacji cięcia (1D)
Otrzymujesz materiał w sztangach o stałej długości (np. 6000 mm) oraz listę wymaganych części, każda o określonej długości i ilości. Schemat cięcia to jeden ze sposobów pocięcia pojedynczej sztangi na kilka z tych części; pozostały odcinek to odpad. Problem polega na wyborze schematów i liczby sztang do pocięcia według każdego z nich, tak aby wyprodukować wszystkie wymagane części przy jak najmniejszej liczbie zużytych sztang, czyli przy jak najmniejszym odpadzie. Jeden wymiar, ponieważ liczy się tylko długość: ostrze przecina cały przekrój, więc szerokość i profil nie mają znaczenia.
Problem pakowania (1D bin packing) i jego złożoność NP-trudna
Problem optymalizacji cięcia jest uogólnieniem problemu pakowania (1D bin packing). Pakowanie polega na umieszczeniu zestawu elementów o różnych rozmiarach w jak najmniejszej liczbie pojemników o stałej wielkości. Optymalizacja cięcia to to samo zagadnienie, ale dla elementów powtarzających się w dużych ilościach, więc operuje się na schematach, a nie na pojedynczych częściach. Problem pakowania to klasyczny problem NP-trudny, a jego forma decyzyjna (czy te elementy zmieszczą się w k pojemnikach?) jest NP-zupełna. Problem cięcia dziedziczy tę złożoność.
Powodem jest eksplozja kombinatoryczna. Liczba różnych schematów cięcia rośnie wykładniczo wraz z liczbą różnych długości części, a liczba sposobów na rozłożenie ilości na te schematy rośnie jeszcze szybciej. Nie jest znany żaden algorytm, który znalazłby gwarantowane optimum w czasie wielomianowym w stosunku do rozmiaru danych wejściowych i, o ile P nie równa się NP, nie będzie takiego. Dlatego prawdziwe solvery nie sprawdzają każdej możliwości; inteligentnie eliminują te, które można z góry wykluczyć.
Jak to się rozwiązuje w praktyce
Heurystyka First-Fit-Decreasing (FFD)
Podstawowa heurystyka: posortuj wymagane części od najdłuższej do najkrótszej, a następnie umieszczaj każdą na pierwszej sztandze, na której się jeszcze mieści. Nową sztangę otwieraj tylko wtedy, gdy na żadnej nie ma już miejsca. Jest szybka i zaskakująco dobra, z gwarancją wyniku w okolicach 11/9 optymalnej liczby sztang plus niewielka stała. Większość narzędzi na tym poprzestaje; dobre narzędzie używa FFD jako punktu wyjścia, a nie celu.
Generowanie kolumn (Gilmore i Gomory)
Sformułowanie, które umożliwiło rozwiązywanie dużych problemów. Gilmore i Gomory (1961) opisali problem za pomocą jednej zmiennej dla każdego schematu cięcia. Ponieważ jest ich wykładniczo wiele, rozwiązali relaksację liniową poprzez opóźnione generowanie kolumn: zaczynając od kilku schematów i cyklicznie generując kolejny najbardziej użyteczny przez rozwiązanie podproblemu plecakowego. Uzyskane w ten sposób dolne ograniczenie jest znane ze swojej dokładności.
Metoda podziału i ograniczeń (branch-and-bound) oraz „branch-and-price”
Aby zamienić ułamkową relaksację w całkowitą liczbę sztang, trzeba szukać, ale nie na ślepo. Metoda podziału i ograniczeń przeszukuje drzewo możliwych rozwiązań całkowitoliczbowych, używając ograniczenia z programu liniowego do odcinania całych gałęzi, które nie mogą dać lepszego wyniku niż najlepszy dotychczas znaleziony. W połączeniu z generowaniem kolumn staje się metodą „branch-and-price”, stanowiącą podstawę większości dokładnych solverów problemu cięcia.
Dolne ograniczenia i dowód optymalności
Poważny solver nie tylko zwraca plan, ale oblicza dolne ograniczenie (z relaksacji liniowej lub prostszego argumentu opartego na łącznej długości) i porównuje wyniki. Kiedy plan zużywa dokładnie tyle sztang, ile wynosi udowodnione minimum, jest optymalny: żaden plan nie może być lepszy, a solver może to stwierdzić, zamiast liczyć na szczęście.
Jak rozwiązuje to LinearCutting
LinearCutting działa następująco: szybka heurystyka daje natychmiastowy, poprawny plan. Następnie algorytm oparty na ograniczeniach poprawia go, aż osiągnie dolne ograniczenie (co jest dowodem optymalności i jest to sygnalizowane) lub wyczerpie limit czasu i zwróci najlepszy znaleziony plan. Modeluje też fizyczne aspekty cięcia: rzaz przy każdym cięciu, odcięcie czoła, odpady użytkowe o stałej długości i cięcia pod kątem, które zużywają więcej materiału. Plan, który ignoruje grubość ostrza, jest nie tylko nieoptymalny - jest błędny. Publikujemy zlecenia testowe, abyś mógł porównać wyniki z dowolnym innym narzędziem.
Jest on dostępny jako API JSON: wysyłasz swoje części i materiał, a otrzymujesz zweryfikowany plan cięcia z układami, ilością odpadu, liczbą ustawień i informacją, czy plan jest optymalny. Istnieją oficjalne klienty dla Pythona (pip install linearcutting) i JavaScript lub TypeScript (npm install linearcutting), więc wywołanie go to kilka linijek kodu w obu językach.
Rozwiązuj problemy cięcia z poziomu kodu
Nie pisz własnego solvera - użyj gotowego. Silnik napędzający kalkulator na tej stronie jest dostępny jako API JSON z oficjalnymi klientami dla Pythona i JavaScript, darmowym planem publicznym i działającym przykładem w dokumentacji.
pip install linearcutting npm install linearcutting