Generarea coloanelor , sau generarea coloanelor leneșe , este o abordare eficientă pentru rezolvarea problemelor mari de programare liniară .
Ideea generală a metodei este că multe probleme de programare liniară sunt prea mari pentru a scrie în mod explicit toate variabilele. Deoarece majoritatea variabilelor nu vor fi incluse în bază și, prin urmare, vor avea o valoare zero în soluția optimă, este nevoie doar de un subset de variabile pentru a rezolva problema. Generarea coloanelor susține această idee prin generarea doar a acelor variabile care au potențialul de a îmbunătăți funcția obiectiv - adică sunt căutate doar variabilele cu un cost redus negativ (presupunem fără pierdere de generalitate că problema de minimizare este în curs de rezolvare).
Sarcina este împărțită în două - sarcina principală și o sarcină secundară. Problema principală este problema inițială cu presupunerea că este luat în considerare doar un subset de variabile. O subsarcină este o sarcină nouă, al cărei scop este găsirea de noi variabile. Funcția obiectivă a subproblemei este prețul redus pentru variabilele duale curente, iar constrângerile sunt generate de constrângeri naturale asupra variabilelor.
Procesul funcționează după cum urmează. Rezolvăm problema principală, din soluție obținem variabile duale pentru fiecare constrângere a problemei inițiale. Aceste informații sunt utilizate în funcția obiectivă a subsarcinii. Rezolvăm o subproblemă. Dacă funcția obiectivă a subsarcinii este negativă, se găsește o variabilă cu preț redus negativ și această variabilă se adaugă la problema principală și se produce următoarea soluție a problemei principale. Noua soluție optimă a problemei principale va da noi variabile duale, iar procesul se repetă atâta timp cât soluțiile subproblemei dau valori negative. Când soluția subproblemei dă o valoare pozitivă a funcției obiectiv, putem concluziona că a fost găsită soluția optimă a problemei principale.
În multe cazuri, această abordare permite rezolvarea unor probleme mari de programare liniară. Un exemplu clasic de aplicare a metodei de generare a coloanei este problema cuibării . O tehnică de programare liniară care utilizează aceeași abordare este descompunerea Danzig-Wolfe . În plus, generarea coloanei este utilizată în multe probleme precum planificarea muncii [1] , rutare și problema p-mediană constrânsă [2] [3] .
Când se rezolvă probleme mari folosind metoda bazei variabile (vezi metoda simplex , secțiunea „Metoda bazei variabile”), un caz similar apare adesea când este posibil să se genereze nu numai coloane, ci și rânduri. Metoda bazei variabile folosește faptul că în problemele mari de programare liniară, în care majoritatea constrângerilor sunt date de inegalități, majoritatea constrângerilor nu ating o constrângere strictă (o variabilă suplimentară nu este egală cu zero), ceea ce înseamnă că o astfel de constrângere nu poate fi luată în considerare în soluția finală. La rezolvarea problemelor folosind metoda bazei variabile, mai poate fi rezolvată o subsarcină - determinarea coloanei de ieșire. Folosind această abordare, este posibilă rezolvarea unor probleme de teoria jocurilor (vezi, de exemplu, jocurile Blotto ) care conțin milioane de rânduri și coloane.