Programowanie celowe wieloobiektowe
- Autor metody
- Charnes, A. and Cooper, W. W.
- Rok
- 1961
- Typ
- Mathematical programming / multi-criteria 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 celowe wieloobiektowe (MOGP) to technika programowania matematycznego, która jednocześnie dąży do osiągnięcia kilku celów aspiracyjnych poprzez minimalizację ważonych odchyleń od każdego z nich.
Zakorzenione w oryginalnych ramach programowania celowego Charnesa i Coopera (1961), MOGP rozszerza je, aby radzić sobie z wieloma konkurencyjnymi celami, co czyni je niezastąpionym w badaniach operacyjnych, projektowaniu łańcuchów dostaw, alokacji zasobów i analizie polityk, gdzie decydenci muszą spełnić — lub zbliżyć się do spełnienia — wiele sprzecznych wymagań jednocześnie.
Intuicja stojąca za metodą
Wyobraźmy sobie menedżera, który musi jednocześnie osiągnąć cel zysku, zmieścić się w budżecie węglowym i utrzymać nadgodziny pracowników poniżej określonego progu. Czysta optymalizacja może optymalizować tylko jeden cel naraz, a traktowanie pozostałych jako twardych ograniczeń może prowadzić do niewykonalności. Programowanie celowe przekształca każdy cel w „zadanie” i minimalizuje odległość, o jaką rozwiązanie nie osiąga (lub przekracza) każdy cel. Wariant wieloobiektowy waży te odchylenia dla wszystkich celów i znajduje najlepszy wykonalny kompromis — podobnie jak znalezienie punktu w krajobrazie, który jest najbliżej kilku wierzchołków wzgórz jednocześnie.
Historia
Programowanie celowe zostało wprowadzone przez Charnesa i Coopera w 1961 roku jako rozszerzenie programowania liniowego do obsługi wielu celów poprzez poziomy aspiracji. Ijiri (1965) sformalizował wariant leksykograficzny, a Lee (1972) skonsolidował metodę dla zastosowań w naukach o zarządzaniu. Wielocelowe (wektorowe) sformułowanie zyskało na znaczeniu dzięki pracom Tamiza, Jonesa i Romero w latach 90., a dziś MOGP jest standardowym narzędziem w programach nauczania badań operacyjnych i optymalizacji stosowanej.
Kiedy stosować
Użyj MOGP, gdy problem decyzyjny obejmuje wiele, mierzalnych, potencjalnie sprzecznych celów i gdy decydenci mogą wyrazić poziomy aspiracji dla każdego z nich. Jest szczególnie odpowiednie do alokacji zasobów, wyboru portfela, planowania produkcji i polityki środowiskowej, gdzie wykonalność musi być utrzymana przy jednoczesnym dążeniu do kilku celów. Preferuj MOGP zamiast czystej optymalizacji wieloobiektowej, gdy interesariusze myślą w kategoriach „celów do osiągnięcia”, a nie „celów do maksymalizacji”. NIE używaj go, gdy celów nie można wyrazić jako ilościowych wartości docelowych, gdy problem jest z natury nieliniowy, a solvery są niedostępne, gdy wag kardynalnych nie można uzasadnić lub gdy wymagana jest ścisła analiza frontu Pareto (bez zakotwiczenia celów).
Ograniczenia i uwagi
- Poziomy celów (aspiracji) i wagi muszą być pozyskane od decydentów, co może być subiektywne i politycznie sporne.
- Rozwiązanie jest wrażliwe na wybrane wagi; różne schematy ważenia mogą prowadzić do znacznie odmiennych wyników.
- Standardowe liniowe programowanie celowe (GP) zakłada wypukłość; problemy niewypukłe lub kombinatoryczne wymagają specjalistycznych solverów i mogą stać się intensywne obliczeniowo.
- Nie gwarantuje optymalności Pareto — rozwiązanie GP może być zdominowane, jeśli cele i wagi są źle określone.
- Niewspółmierne skale celów wymagają normalizacji, co może wprowadzić dalsze subiektywne wybory.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Naturalnie radzi sobie z wieloma sprzecznymi celami w ramach jednego, łatwego do rozwiązania modelu optymalizacyjnego.
- Elastyczne funkcje osiągnięć — warianty ważone, leksykograficzne lub min-max — uwzględniają różne struktury preferencji interesariuszy.
- Generuje jedno zalecane rozwiązanie, a nie duży zbiór Pareto, co upraszcza komunikację z decydentami.
- Może być rozszerzone na sformułowania całkowitoliczbowe, binarne lub nieliniowe, obejmując szeroki zakres problemów rzeczywistych.
- Analiza wrażliwości na wagi i poziomy aspiracji jest prosta, ujawniając, jak solidne jest rozwiązanie wobec zmian preferencji.
Zastosowania
- Projektowanie sieci łańcucha dostaw równoważące koszty, poziom usług i cele dotyczące śladu węglowego.
- Alokacja zasobów szpitalnych spełniająca jednocześnie cele dotyczące obsady personelu, obłożenia łóżek i budżetu.
- Planowanie rolnicze, które optymalizuje plony, zużycie wody i zwrot ekonomiczny przy stałych ograniczeniach gruntowych.
- Wybór portfela finansowego spełniający poziomy aspiracji dotyczące zwrotu, ryzyka i płynności.
- Modelowanie polityki energetycznej, uwzględniające kompromisy między zdolnościami odnawialnymi, niezawodnością sieci i kosztami inwestycji.
- Planowanie harmonogramu zajęć uniwersyteckich z uwzględnieniem obciążenia wykładowców, pojemności sal i preferencji studentów.
Jak to działa
Jak to działa
Zidentyfikuj wszystkie K cele i ustal poziomy aspiracji g_k dla każdego celu f_k(x). Cele mogą odzwierciedlać docelowe zyski, pułapy kosztów, kwoty środowiskowe lub wymagania dotyczące poziomu usług. Zdecyduj, czy przekroczenie, niedotrzymanie, czy oba odchylenia są niepożądane dla każdego celu.
Wprowadź nieujemne zmienne odchylenia d_k^+ (przekroczenie) i d_k^- (niedotrzymanie) dla każdego celu k, tak aby f_k(x) + d_k^- - d_k^+ = g_k. Zmienne te kwantyfikują, jak daleko rozwiązanie jest od każdego poziomu aspiracji.
Wzór
d_k^+ = \max(f_k(x) - g_k, 0), \quad d_k^- = \max(g_k - f_k(x), 0)
Zbuduj funkcję osiągnięcia (celu) jako ważoną sumę zmiennych odchyleń: min Z = sum_k (w_k^+ * d_k^+ + w_k^- * d_k^-). Wagi w_k odzwierciedlają względne znaczenie osiągnięcia każdego celu. Alternatywnie, leksykograficzne uporządkowanie priorytetów może zastąpić wagi dla struktur o ścisłych priorytetach.
Wzór
\min \; Z = \sum_{k=1}^{K} (w_k^+ d_k^+ + w_k^- d_k^-)Rozwiąż wynikowy program liniowy (lub nieliniowy) za pomocą standardowych solverów. Dostosuj poziomy celów i wagi na podstawie analizy wrażliwości lub opinii interesariuszy i rozwiąż ponownie, aby zbadać przestrzeń decyzyjną i zrozumieć kompromisy między celami.
Sprawdź końcowe wartości odchyleń, aby określić, które cele zostały w pełni osiągnięte (d_k^+ = d_k^- = 0) i które wiążą się z pozostałymi odchyleniami. Przedstaw decydentom front Pareto-efektywny lub profil osiągnięć do ostatecznego wyboru i uzasadnienia.
Częste pułapki
- Ustalenie nierealistycznych poziomów aspiracji może sprawić, że wszystkie cele staną się jednocześnie nieosiągalne, prowadząc do dużych odchyleń dla każdego celu i nieinformacyjnego rozwiązania.
- Ignorowanie rozróżnienia między niepożądanym przekroczeniem a niepożądanym niedotrzymaniem (np. traktowanie nadmiernego zysku jako problemu) prowadzi do błędnie określonych kar za odchylenia.
- Łączenie celów o bardzo różnych jednostkach lub wielkościach bez normalizacji powoduje, że funkcja osiągnięcia jest zdominowana przez cele o dużej wartości liczbowej.
- Traktowanie wyników GP jako ostatecznej odpowiedzi bez analizy wrażliwości ryzykuje przeoczenie wpływu niepewności wag na wybrane rozwiązanie.
Najczęściej zadawane pytania
Czym MOGP różni się od standardowej optymalizacji wieloobiektowej?
Standardowa optymalizacja wieloobiektowa poszukuje pełnego frontu Pareto bez ustalania celów, podczas gdy MOGP zakotwicza każdy cel na określonym poziomie aspiracji i minimalizuje odchylenia od tych poziomów, dając jedno kompromisowe rozwiązanie zgodne z określonymi celami.
Jaka jest różnica między ważonym a leksykograficznym programowaniem celowym?
Ważone programowanie celowe (GP) łączy wszystkie zmienne odchyleń w jedną ważoną sumę, wymieniając cele między sobą. Leksykograficzne GP porządkuje cele w ścisłe poziomy priorytetów i optymalizuje każdy poziom sekwencyjnie, nigdy nie poświęcając celu o wyższym priorytecie dla celu o niższym priorytecie.
Czy MOGP może obsługiwać nieliniowe funkcje celu?
Tak, ale kosztem zwiększonych nakładów obliczeniowych. Nieliniowe MOGP wymaga nieliniowych solverów, a wypukłość nie jest już gwarantowana, więc globalna optymalność może nie być zapewniona. Linearyzacja lub aproksymacje kawałkami są często stosowanymi rozwiązaniami.
Jak należy określać wagi celów?
Wagi powinny odzwierciedlać preferencje decydentów i mogą być pozyskane poprzez bezpośrednie ocenianie, porównania parami (AHP) lub analizę wrażliwości metodą prób i błędów. Przejrzystość w wyborze wag jest kluczowa dla akceptacji przez interesariuszy.
Czy rozwiązanie programowania celowego jest zawsze optymalne w sensie Pareto?
Niekoniecznie. Ważone rozwiązanie GP może być słabo optymalne w sensie Pareto, ale nie ściśle, zwłaszcza jeśli niektóre wagi są zerowe. Zaleca się stosowanie dodatnich wag dla wszystkich odchyleń i sprawdzanie rozwiązań zdominowanych.
Pokrewne metody
Źródła
Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.
ISBN: 978-0471148258Skopiowano.Jones, D., Tamiz, M. (2010). Practical Goal Programming. Springer, New York.
Otwórz odnośnik DOISkopiowano.