Obszar dopuszczalnych rozwiązań
Obszar dopuszczalnych rozwiązań (ODR) (także zbiór dopuszczalnych rozwiązań, ang. Feasible region, feasible set) — w badaniach operacyjnych, optymalizacji i modelowaniu matematycznym jest to zbiór wszystkich możliwych rozwiązań (zestawów wartości zmiennych), które spełniają wszystkie ograniczenia nałożone na zadanie.
ODR stanowi podprzestrzeń, w której prowadzone jest poszukiwanie optymalnego rozwiązania. Każde rozwiązanie znajdujące się poza tym obszarem jest niedopuszczalne.
Definicja i formowanie
Obszar dopuszczalnych rozwiązań formowany jest jako przecięcie zbiorów określanych przez każde poszczególne ograniczenie zadania. Ograniczenia mogą być przedstawione w postaci:
- Nierówności: Ustalają górne lub dolne granice dla wartości zmiennych lub ich kombinacji (np. „zużycie zasobu A nie może przekraczać 100 jednostek", „liczba wyprodukowanych wyrobów musi wynosić co najmniej 50 sztuk").
- Równości: Wymagają dokładnego spełnienia warunku (np. „łączna wielkość przewozów musi być równa 1000 ton", „bilans przepływów wchodzących i wychodzących równa się zero").
- Warunków co do znaku zmiennych: Często zmienne muszą być nieujemne, całkowitoliczbowe lub należeć do określonego zbioru dyskretnego.
Punkt (lub wektor wartości zmiennych) należy do ODR wtedy i tylko wtedy, gdy jednocześnie spełnia wszystkie te ograniczenia.
Interpretacja geometryczna
ODR często ma przejrzystą interpretację geometryczną, szczególnie w zadaniach z niewielką liczbą zmiennych:
- W przestrzeni dwuwymiarowej (2 zmienne): Każde liniowe ograniczenie-nierówność wyznacza półpłaszczyznę. ODR stanowi przecięcie tych półpłaszczyzn — wypukły wielokąt (ewentualnie nieograniczony lub pusty).
- W przestrzeni trójwymiarowej (3 zmienne): Każde liniowe ograniczenie-nierówność wyznacza półprzestrzeń. ODR jest przecięciem tych półprzestrzeni — wypukłym wielościanem (poliedrem).
- W przestrzeni wielowymiarowej: ODR określony przez ograniczenia liniowe jest wypukłym wielościanem (polytopem).
W przypadku ograniczeń nieliniowych ODR może mieć bardziej złożoną postać i nie być wypukły.
Rola w optymalizacji
Obszar dopuszczalnych rozwiązań odgrywa fundamentalną rolę w optymalizacji:
1. Określenie przestrzeni poszukiwań: Optymalne rozwiązanie zadania (jeśli istnieje) zawsze znajduje się wewnątrz ODR lub na jego granicy. Algorytmy optymalizacji poszukują ekstremum funkcji celu właśnie w tym obszarze. 2. Sprawdzenie istnienia rozwiązań: Jeśli ODR jest zbiorem pustym (tj. ograniczenia są ze sobą sprzeczne), to zadanie nie ma dopuszczalnych rozwiązań, a co za tym idzie — również optymalnego rozwiązania. 3. Wpływ na optymalne rozwiązanie: Kształt i rozmiar ODR bezpośrednio wpływają na możliwość osiągnięcia ekstremum funkcji celu oraz na wartość tego ekstremum.
Własności ODR (w zadaniach programowania liniowego)
W zadaniach programowania liniowego (PL), gdzie wszystkie ograniczenia i funkcja celu są liniowe, ODR posiada ważne własności:
- Wypukłość: Jeśli dwa punkty należą do ODR, to również cały odcinek łączący te punkty należy do ODR. Własność ta gwarantuje, że optymalne rozwiązanie (jeśli istnieje i jest jedyne) będzie znajdować się w jednym z wierzchołków wielościanu ODR.
- Domkniętość: ODR zawiera swoje granice (ze względu na nieostrą nierówność ≤, ≥ oraz równości).
ODR może być:
- Ograniczony: Ma skończone rozmiary.
- Nieograniczony: Rozciąga się nieskończenie w jednym lub kilku kierunkach.
- Pusty: Nie zawiera żadnego punktu.
Literatura
- Wentcel J. S. Badania operacyjne: zadania, zasady, metodologia. — M.: Nauka, 1988.
- Ackoff R., Sasieni M. Podstawy badań operacyjnych. — M.: Mir, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
Zobacz też
- Badania operacyjne
- Optymalizacja
- Model matematyczny
- Ograniczenia
- Rozwiązanie dopuszczalne
- Rozwiązanie optymalne
- Funkcja celu
- Programowanie liniowe
- Zbiór wypukły