For developers
Problema debitării 1D
Cum se taie un set de piese dintr-un stoc de bare folosind un număr minim de bare: aceasta este problema debitării 1D, o problemă clasică de optimizare, autentic dificilă. Iată ce este, de ce nu poate fi rezolvată prin forță brută și cum se rezolvă în practică, inclusiv în API-ul din spatele acestui site.
Ce este problema debitării 1D
Se dă un stoc de bare de lungime fixă (să zicem 6000 mm) și o listă de repere necesare, fiecare cu lungime și cantitate. Un model de tăiere este o modalitate de a tăia o singură bară brută în câteva dintre acele repere; orice lungime rămasă este pierdere. Problema este de a alege modelele și numărul de bare de tăiat pentru fiecare, astfel încât toate reperele necesare să fie produse cu un număr minim de bare brute, echivalent cu pierderi minime. O singură dimensiune, pentru că doar lungimea contează: pânza taie întreaga secțiune, deci lățimea și profilul nu intră în calculul de aranjare.
Problema împachetării 1D și de ce este NP-hard
Problema debitării este o generalizare a problemei împachetării 1D: aceasta cere aranjarea unui set de articole de dimensiuni distincte în numărul minim de recipiente de mărime fixă. Debitare este aceeași problemă, dar cu articole care se repetă în cantități mari, deci raționamentul se bazează pe modele, nu pe articole individuale. Problema împachetării este una clasică NP-hard, iar forma sa decizională, pot aceste articole încăpea în k recipiente, este NP-completă. Problema debitării moștenește această dificultate.
Motivul este explozia combinațiilor. Numărul de modele de tăiere distincte crește exponențial cu numărul de dimensiuni de repere, iar numărul de moduri de a distribui cantitățile pe acele modele explodează și mai mult. Nu există un algoritm cunoscut care să găsească optimul garantat într-un timp care scalează polinomial cu datele de intrare și, dacă P nu este egal cu NP, nici nu va exista. Deci, sistemele de rezolvare reale nu enumeră totul; ele elimină inteligent anumite posibilități.
Cum se rezolvă în practică
First-fit-decreasing (FFD)
Euristica de bază: sortați reperele necesare de la cel mai lung la cel mai scurt, apoi plasați fiecare reper pe prima bară pe care încape, deschizând o bară nouă doar atunci când niciuna nu mai are loc. Este rapidă și surprinzător de bună, demonstrabil în jur de 11/9 din numărul optim de bare, plus o constantă mică. Majoritatea uneltelor se opresc aici; una bună folosește FFD ca punct de plecare, nu ca linie de sosire.
Generarea de coloane (Gilmore și Gomory)
Formularea care a făcut rezolvabile instanțele mari. Gilmore și Gomory (1961) au descris problema cu o variabilă per model de tăiere și, cum există un număr exponențial, au rezolvat relaxarea liniară prin generare întârziată de coloane: se pornește cu câteva modele și se generează repetat următorul cel mai util, rezolvând o subproblemă a rucsacului. Limita inferioară produsă este recunoscută pentru precizia sa.
Branch-and-bound și branch-and-price
Pentru a transforma acea relaxare fracționară într-un număr întreg de bare, trebuie să căutați, dar nu orbește. Branch-and-bound explorează arborele de alegeri întregi, folosind limita LP pentru a tăia ramuri întregi care nu pot depăși cel mai bun plan găsit; combinat cu generarea de coloane devine branch-and-price, baza majorității sistemelor de rezolvare exacte pentru debitare.
Limite inferioare și o dovadă
Un sistem de rezolvare serios nu returnează doar un plan, ci calculează o limită inferioară (din relaxarea LP sau dintr-un argument mai simplu bazat pe lungimea totală) și le compară. Când un plan folosește exact atâtea bare cât demonstrează limita că sunt inevitabile, planul este demonstrabil optim: niciun alt plan nu poate fi mai bun, iar sistemul poate afirma acest lucru în loc să spere că a avut noroc.
Cum rezolvă LinearCutting problema
LinearCutting rulează următorul proces: o euristică rapidă pentru un plan fezabil instantaneu, apoi o căutare ghidată de limite care se îmbunătățește continuu până când atinge limita inferioară (demonstrabil optim, și vă anunță) sau își epuizează bugetul de timp și returnează cel mai bun plan găsit. Modelează și fizica reală: lățimea tăieturii la fiecare debitare, curățarea capetelor, resturi utilizabile în cantitate fixă și tăieturi în unghi care consumă material suplimentar, deoarece un plan care ignoră pânza nu este doar suboptimal, este greșit. Joburile de referință sunt publicate pentru a putea verifica rezultatele în comparație cu orice altă unealtă.
Este expus ca un API JSON: trimiteți reperele și stocul, primiți înapoi un plan de debitare verificat cu schemele de tăiere, pierderile, numărul de reglaje și dacă planul a atins limita optimă. Există clienți oficiali pentru Python (pip install linearcutting) și JavaScript sau TypeScript (npm install linearcutting), deci apelarea durează câteva linii în oricare limbaj.
Rezolvați direct din codul dumneavoastră
Nu mai scrieți un sistem de rezolvare, apelați unul. Același motor din spatele calculatorului de pe acest site este un API JSON cu clienți oficiali Python și JavaScript, un nivel gratuit de utilizare și un exemplu live pe care îl puteți rula în documentație.
pip install linearcutting npm install linearcutting