Generowanie kolumn

generowanie kolumn lub opóźnione generowanie kolumn jest wydajnym algorytmem do rozwiązywania dużych programów liniowych.

nadrzędną ideą jest to, że wiele programów liniowych jest zbyt dużych, aby uwzględnić wszystkie zmienne jawnie. Założenie jest takie, że większość zmiennych nie będzie podstawowa i przyjmie wartość zero w rozwiązaniu optymalnym. Z tego powodu tylko podzbiór zmiennych musi być brany pod uwagę w teorii przy rozwiązywaniu problemu. Generowanie kolumn wykorzystuje tę ideę do generowania tylko tych zmiennych, które mają potencjał do poprawy funkcji celu—czyli znalezienia zmiennych o ujemnym obniżonym koszcie (zakładając bez utraty ogólności, że problem jest problemem minimalizacji).

problem jest podzielony na dwa problemy: problem główny i podproblem. Problem główny jest pierwotnym problemem, w którym brany jest pod uwagę tylko podzbiór zmiennych. Podproblem jest nowym problemem utworzonym w celu identyfikacji nowej zmiennej. Funkcją celową podproblemu jest obniżony koszt nowej zmiennej w odniesieniu do obecnych zmiennych podwójnych, a ograniczenia wymagają, aby zmienna była zgodna z naturalnie występującymi ograniczeniami.

proces przebiega w następujący sposób. Problem główny został rozwiązany—z tego rozwiązania jesteśmy w stanie uzyskać podwójne ceny za każde z ograniczeń w problemie głównym. Informacje te są następnie wykorzystywane w funkcji celu podproblemu. Podproblem rozwiązany. Jeśli obiektywna wartość podproblemu jest ujemna, zidentyfikowano zmienną o ujemnym obniżonym koszcie. Ta zmienna jest następnie dodawana do problemu głównego, a problem główny jest ponownie rozwiązany. Ponowne rozwiązanie problemu głównego wygeneruje nowy zestaw podwójnych wartości, a Proces jest powtarzany, dopóki nie zostaną zidentyfikowane żadne ujemne zmienne obniżone koszty. Podproblem zwraca rozwiązanie o nieujemnym obniżonym koszcie, możemy stwierdzić, że rozwiązanie problemu głównego jest optymalne.

w wielu przypadkach pozwala to na rozwiązanie dużych programów liniowych, które wcześniej były uważane za trudne do rozwiązania. Klasycznym przykładem problemu, w którym jest to z powodzeniem stosowane, jest problem cięcia materiału. Szczególną techniką w programowaniu liniowym wykorzystującą ten rodzaj podejścia jest algorytm rozkładu Dantziga-Wolfe ‘ a. Dodatkowo, generacja kolumn została zastosowana do wielu problemów, takich jak planowanie załogi, routing pojazdu i problem capacitated P-mediana.

Ten artykuł związany z matematyką stosowaną jest fragmentem. Możesz pomóc Wikipedii, rozszerzając ją.