Generarea coloanei

generarea coloanei sau generarea întârziată a coloanei este un algoritm eficient pentru rezolvarea programelor liniare mari.

ideea generală este că multe programe liniare sunt prea mari pentru a lua în considerare toate variabilele în mod explicit. Premisa este că majoritatea variabilelor vor fi non-de bază și vor presupune o valoare de zero în soluția optimă. Din această cauză, doar un subset de variabile trebuie luat în considerare teoretic la rezolvarea problemei. Generarea de coloane folosește această idee pentru a genera doar variabilele care au potențialul de a îmbunătăți funcția obiectivă—adică de a găsi variabile cu cost redus negativ (presupunând fără pierderea generalității că problema este o problemă de minimizare).

problema rezolvată este împărțită în două probleme: problema principală și subproblema. Problema master este problema inițială cu doar un subset de variabile fiind luate în considerare. Subproblema este o nouă problemă creată pentru a identifica o nouă variabilă. Funcția obiectivă a subproblemei este costul redus al noii variabile în raport cu variabilele duale actuale, iar constrângerile necesită ca variabila să respecte constrângerile naturale.

procesul funcționează după cum urmează. Problema master este rezolvată—din această soluție, suntem capabili să obținem prețuri duale pentru fiecare dintre constrângerile din problema master. Aceste informații sunt apoi utilizate în funcția obiectivă a subproblemei. Subproblema este rezolvată. Dacă valoarea obiectivă a subproblemei este negativă, a fost identificată o variabilă cu cost redus negativ. Această variabilă este apoi adăugată la problema master, iar problema master este re-rezolvată. Re-rezolvarea problemei master va genera un nou set de valori duale, iar procesul se repetă până când nu sunt identificate variabile negative de cost redus. Subproblema returnează o soluție cu un cost redus non-negativ, putem concluziona că soluția la problema master este optimă.

în multe cazuri, acest lucru permite rezolvarea programelor liniare mari care au fost considerate anterior imposibil de rezolvat. Exemplul clasic al unei probleme în care aceasta este utilizată cu succes este problema stocului de tăiere. O tehnică particulară în programarea liniară care folosește acest tip de abordare este algoritmul de descompunere Dantzig–Wolfe. În plus, generarea de coloane a fost aplicată la multe probleme, cum ar fi programarea echipajului, rutarea vehiculului și problema p-mediană capacitată.

acest articol despre matematică aplicată este un ciot. Puteți ajuta Wikipedia prin extinderea acesteia.