Programowanie liniowe wielokryterialne (MOLP)
- Autor metody
- Steuer, R. E.; Charnes, A.; Cooper, W. W.
- Rok
- 1955–1986
- Typ
- Mathematical optimization / vector optimization
- Rodzina
- Simulation / optimization
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie liniowe wielokryterialne (MOLP) rozszerza klasyczne programowanie liniowe o obsługę wielu sprzecznych, liniowych funkcji celu jednocześnie w obszarze dopuszczalnym zdefiniowanym przez ograniczenia liniowe.
Zamiast pojedynczego rozwiązania optymalnego, MOLP generuje Pareto-efektywną granicę, z której decydent wybiera preferowany kompromis. Jest to podstawa badań operacyjnych i nauk o zarządzaniu w problemach alokacji zasobów, planowania i projektowania z konkurującymi celami.
Intuicja stojąca za metodą
W zwykłym programowaniu liniowym minimalizuje się jeden koszt lub maksymalizuje jeden zysk, ale rzeczywiste decyzje prawie zawsze obejmują wiele konkurujących celów — minimalizację kosztów przy jednoczesnej maksymalizacji poziomu usług i minimalizacji emisji. MOLP uznaje, że żadne pojedyncze rozwiązanie nie jest najlepsze pod względem wszystkich celów jednocześnie. Mapuje pełną granicę niedominowanych (Pareto-efektywnych) rozwiązań, gdzie poprawa jednego celu koniecznie pogorszyłaby inny. Decydent następnie wykorzystuje informacje o preferencjach — wagi, poziomy aspiracji lub interaktywne zapytania — do wyboru ostatecznego rozwiązania z tej granicy, ujawniając kompromisy, zamiast ukrywać je w zagregowanym wskaźniku.
Historia
Teoretyczne podstawy programowania liniowego wielokryterialnego sięgają prac Charnesa i Coopera z lat 50. XX wieku nad programowaniem celów oraz Koopmansa nad efektywnością produkcji. Podręcznik Steuera z 1986 roku skonsolidował tę dziedzinę, systematyzując metody sumy ważonej, epsilon-ograniczeń i metody interaktywne, które pozostają standardem do dziś. MOLP jest obecnie podstawowym tematem w programach nauczania badań operacyjnych na całym świecie.
Kiedy stosować
Używaj MOLP, gdy problem ma wiele konkurujących, liniowych celów i liniowych ograniczeń, dane są ciągłe i precyzyjnie znane (lub mogą być traktowane jako deterministyczne), a decydent potrzebuje zrozumieć kompromisy w sposób jawny, zamiast akceptować wstępnie zagregowany wynik. Typowe zastosowania obejmują planowanie produkcji, alokację portfela, optymalizację tras transportowych i budżetowanie zasobów publicznych. NIE używaj, gdy cele lub ograniczenia są nieliniowe (zamiast tego użyj nieliniowego programowania wielokryterialnego lub metaheurystyk), gdy dane są dyskretne lub binarne (użyj całkowitoliczbowego programowania wielokryterialnego), gdy liczba celów przekracza pięć lub sześć (efektywna granica staje się obliczeniowo nieporęczna) lub gdy decydent nie chce angażować się w iteracyjne określanie preferencji.
Ograniczenia i uwagi
- Ograniczone do liniowych funkcji celu i liniowych ograniczeń; problemy świata rzeczywistego są często nieliniowe.
- Efektywna granica może zawierać wykładniczo wiele punktów ekstremalnych w wyższych wymiarach, co czyni kompleksową enumerację niepraktyczną.
- Wymaga precyzyjnych danych liczbowych; niepewność lub rozmycie w współczynnikach nie jest natywnie obsługiwane.
- Metody interaktywne zależą w dużej mierze od dostępności decydenta i jego zdolności do spójnego wyrażania preferencji.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Generuje pełną Pareto-efektywną granicę, dając decydentom kompletny obraz kompromisów.
- Obliczeniowo wykonalne dla umiarkowanych rozmiarów problemów za pomocą solverów opartych na simplexie.
- Gwarantuje matematyczną optymalność każdego punktu na efektywnej granicy.
- Dobrze wspierane przez dojrzałe oprogramowanie (CPLEX, Gurobi, alternatywy open-source).
- Kompromisy są ujawniane, zamiast być sprowadzonymi do nieprzejrzystego indeksu złożonego.
Zastosowania
- Planowanie produkcji balansujące koszty, przepustowość i wykorzystanie zasobów.
- Optymalizacja portfela inwestycyjnego balansująca zwrot, ryzyko i płynność.
- Projektowanie sieci transportowych i logistycznych z konkurującymi celami kosztów i obsługi.
- Planowanie systemów energetycznych minimalizujące koszty przy jednoczesnym spełnianiu celów emisyjnych i niezawodnościowych.
- Alokacja zasobów w opiece zdrowotnej balansująca równość, efektywność i ograniczenia budżetowe.
- Zarządzanie środowiskowe optymalizujące jednocześnie wyniki ekonomiczne i ekologiczne.
Jak to działa
Jak to działa
Sformułuj k liniowych funkcji celu f1(x) do fk(x) oraz obszar dopuszczalny X zdefiniowany przez liniowe ograniczenia nierównościowe i równościowe (Ax <= b, x >= 0). Zidentyfikuj, które cele mają być minimalizowane, a które maksymalizowane. Potwierdź, że wszystkie funkcje celu i ograniczenia są liniowe względem zmiennych decyzyjnych.
Wzór
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0Wygeneruj zbiór Pareto-efektywnych (niedominowanych) rozwiązań. Powszechne podejścia obejmują metodę sumy ważonej (zmienne wagi w simplexie), metodę epsilon-ograniczeń (optymalizacja jednego celu przy jednoczesnym ograniczaniu pozostałych) oraz metodę Czebyszewa. Każde podejście śledzi część lub całość efektywnej granicy.
Zastosuj technikę skalaryzacji do przekształcenia problemu wektorowego w sekwencję problemów LP z jednym celem. W podejściu sumy ważonej rozwiązuj min suma(wi * fi(x)) dla systematycznie zmienianych wektorów wag. Zapisz każdy efektywny punkt ekstremalny przestrzeni celów.
Wzór
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1Zbierz efektywne punkty ekstremalne i łączące je krawędzie, aby scharakteryzować granicę Pareto. Przeanalizuj zakres każdego celu wzdłuż granicy, aby zrozumieć wielkość kompromisów. Przedstaw granicę decydentowi za pomocą tabel lub wykresów dwukryterialnych.
Zaangażuj decydenta w celu wyboru preferowanego rozwiązania ze zbioru efektywnego. Metody interaktywne (STEM, NIMBUS) przeplatają prezentację rozwiązań z pytaniami do decydenta o wyrażenie preferencji, zbiegając do ostatecznego wyboru, który najlepiej odzwierciedla jego priorytety.
Częste pułapki
- Używanie stałych wag w skalaryzacji sumy ważonej i raportowanie tylko jednego rozwiązania zaciemnia granicę i niweczy cel MOLP.
- Mylenie efektywności Pareto z optymalnością: każdy punkt na granicy jest efektywny, ale żaden nie jest globalnie 'najlepszy' bez informacji o preferencjach.
- Zaniedbanie sprawdzenia, czy obszar dopuszczalny jest ograniczony; problem nieograniczony nie daje skończonego zbioru efektywnego.
- Traktowanie MOLP jako czarnej skrzynki bez angażowania decydenta w proces wyboru prowadzi do arbitralnych wyborów końcowych.
- Stosowanie MOLP do problemów z natury całkowitoliczbowych bez przejścia do całkowitoliczbowego programowania wielokryterialnego, co prowadzi do rozwiązań naruszających warunek całkowitoliczbowości.
Najczęściej zadawane pytania
Czym MOLP różni się od programowania celów?
Programowanie celów jest szczególnym przypadkiem lub wariantem: przekształca każdy cel w poziom aspiracji, a następnie minimalizuje odchylenia od tych celów, dając jedno rozwiązanie. MOLP w swojej ogólnej formie dąży do scharakteryzowania pełnej efektywnej granicy bez wstępnego określania poziomów docelowych, dając decydentowi większą elastyczność.
Czy MOLP może obsługiwać więcej niż dwa cele?
Tak, ale granica Pareto staje się trudniejsza do wizualizacji powyżej dwóch lub trzech celów, a liczba Pareto-efektywnych punktów ekstremalnych może rosnąć wykładniczo. W przypadku czterech lub więcej celów zaleca się metody interaktywne i techniki reprezentatywnych podzbiorów.
Co jeśli moje dane są niepewne?
Standardowe MOLP zakłada deterministyczne współczynniki. Niepewność można uwzględnić, rozszerzając problem do stochastycznego programowania liniowego wielokryterialnego (ograniczenia szansowe, podejścia oparte na scenariuszach) lub do robustnej optymalizacji wielokryterialnej, które są odrębnymi metodami.
Czy MOLP to to samo co optymalizacja wielokryterialna?
MOLP jest szczególnym przypadkiem optymalizacji wielokryterialnej, w którym wszystkie cele i ograniczenia są liniowe. Optymalizacja wielokryterialna jest szerszą dziedziną, która obejmuje również warianty nieliniowe, całkowitoliczbowe i kombinatoryczne.
Którą metodę skalaryzacji powinienem zastosować?
Metoda sumy ważonej jest prosta, ale pomija niedwuwypukłe części granicy. Metoda epsilon-ograniczeń może odtworzyć pełną granicę nawet dla niedwuwypukłych obszarów i jest generalnie preferowana do dokładnej analizy. Metody interaktywne są najlepsze, gdy możliwe jest zaangażowanie decydenta.
Pokrewne metody
Źródła
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.
ISBN: 9780471888468Skopiowano.Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.
Otwórz odnośnik do publikacjiSkopiowano.