Wykonalny region - Feasible region

Problem z pięcioma ograniczeniami liniowymi (na niebiesko, w tym ograniczeniami nieujemności). W przypadku braku ograniczeń całkowitoliczbowych dopuszczalnym zbiorem jest cały region ograniczony kolorem niebieskim, ale w przypadku ograniczeń całkowitoliczbowych jest to zbiór czerwonych kropek.

Zamknięty obszar dopuszczalny zadania programowania liniowego z trzema zmiennymi jest wielościanem wypukłym .

W optymalizacji matematycznej obszar dopuszczalny , zbiór wykonalny , przestrzeń poszukiwań lub przestrzeń rozwiązań to zbiór wszystkich możliwych punktów (zbiorów wartości zmiennych wyboru) problemu optymalizacyjnego, które spełniają ograniczenia problemu , potencjalnie obejmujące nierówności , równości i ograniczenia liczb całkowitych . Jest to początkowy zestaw kandydatów do rozwiązania problemu, zanim zestaw kandydatów został zawężony.

Rozważmy na przykład problem

Zminimalizować ${\ Displaystyle x ^ {2} + Y ^ {4}}$

w odniesieniu do zmiennych i${\displaystyle x}$${\displaystyle y}$

podlega

${\displaystyle 1\leq x\leq 10}$

i

${\displaystyle 5\równ r\równ 12.\,}$

Tutaj zbiorem dopuszczalnym jest zbiór par ( x , y ), w którym wartość x wynosi co najmniej 1 i co najwyżej 10, a wartość y wynosi co najmniej 5 i co najwyżej 12. Zauważ, że zbiór wykonalny problemu jest oddzielona od funkcji celu , która określa kryterium do optymalizacji i która w powyższym przykładzie jest${\ Displaystyle x ^ {2} + Y ^ {4}.}$

W wielu problemach zestaw wykonalny odzwierciedla ograniczenie, że jedna lub więcej zmiennych musi być nieujemna. W problemach z programowaniem na liczbach całkowitych dopuszczalnym zbiorem jest zbiór liczb całkowitych (lub ich podzbiór). W problemach programowania liniowego dopuszczalnym zbiorem jest wypukły politop : region w przestrzeni wielowymiarowej, którego granice tworzą hiperpłaszczyzny, a narożniki są wierzchołkami .

Satysfakcja z ograniczeń to proces znajdowania punktu w realnym regionie.

Wypukły zestaw wykonalny

W problemie programowania liniowego szereg ograniczeń liniowych tworzy wypukły, dopuszczalny obszar możliwych wartości tych zmiennych. W przypadku dwóch zmiennych obszar ten ma kształt wypukłego wielokąta prostego .

Wypukły wykonalne zestaw jest jednym z której odcinek łączący dwa dowolne punkty wykonalnych przechodzi tylko innych możliwych punktów, a nie za pośrednictwem jakichkolwiek punktów poza możliwym zestawie. Wypukłe zbiory dopuszczalnych pojawiają się w wielu typach problemów, w tym w problemach programowania liniowego, i są szczególnie interesujące, ponieważ jeśli problem ma wypukłą funkcję celu, która ma zostać zmaksymalizowana, na ogół łatwiej będzie go rozwiązać w obecności wypukłej dopuszczalny zestaw, a każde optimum lokalne będzie również optimum globalnym .

Brak wykonalnego zestawu

Jeśli ograniczenia problemu optymalizacji są wzajemnie sprzeczne, nie ma punktów, które spełniają wszystkie ograniczenia, a zatem obszarem dopuszczalnym jest zbiór wartości null . W tym przypadku problem nie ma rozwiązania i mówi się, że jest niewykonalny .

Ograniczone i nieograniczone zestawy wykonalne

Ograniczony zbiór dopuszczalny (góra) i nieograniczony zbiór wykonalny (dół). Zestaw na dole ciągnie się w nieskończoność w prawo.

Dopuszczalne zbiory mogą być ograniczone lub nieograniczone . Na przykład zbiór wykonalny zdefiniowany przez zbiór ograniczeń { x ≥ 0, y ≥ 0} jest nieograniczony, ponieważ w niektórych kierunkach nie ma ograniczeń co do tego, jak daleko można zajść i nadal znajdować się w obszarze wykonalności. W przeciwieństwie do tego zbiór wykonalny utworzony przez zbiór ograniczeń { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} jest ograniczony, ponieważ zakres ruchu w dowolnym kierunku jest ograniczony przez ograniczenia.

W problemach programowania liniowego z n zmiennymi, warunkiem koniecznym, ale niewystarczającym, aby zbiór wykonalny był ograniczony, jest to, aby liczba ograniczeń wynosiła co najmniej n + 1 (jak pokazano w powyższym przykładzie).

Jeżeli zbiór wykonalny jest nieograniczony, może istnieć lub nie optimum, w zależności od specyfiki funkcji celu. Na przykład, jeśli dopuszczalny obszar jest zdefiniowany przez zbiór ograniczeń { x ≥ 0, y ≥ 0}, to problem maksymalizacji x + y nie ma optimum, ponieważ każde potencjalne rozwiązanie można poprawić przez zwiększenie x lub y ; jeśli jednak problemem jest zminimalizowanie x + y , to istnieje optimum (w szczególności w ( x , y ) = (0, 0)).

Kandydat na rozwiązanie

W optymalizacji i innych gałęzi matematyki , a także w algorytmach wyszukiwania (tematem w informatyce ), A rozwiązanie kandydat jest członkiem z zestawu możliwych rozwiązań w możliwym obszarze danego problemu. Kandydujące rozwiązanie nie musi być prawdopodobnym lub rozsądnym rozwiązaniem problemu — jest po prostu w zbiorze, który spełnia wszystkie ograniczenia ; to znaczy jest w zbiorze możliwych rozwiązań . Algorytmy rozwiązywania różnych typów problemów optymalizacyjnych często zawężają zbiór rozwiązań kandydujących do podzbioru rozwiązań dopuszczalnych, których punkty pozostają jako rozwiązania kandydujące, podczas gdy inne rozwiązania wykonalne są odtąd wykluczane jako rozwiązania kandydujące.

Przestrzeń wszystkich rozwiązań kandydujących, zanim jakiekolwiek punkty wykonalne zostaną wykluczone, nazywana jest obszarem wykonalnym, zbiorem wykonalnym, przestrzenią poszukiwań lub przestrzenią rozwiązań. Jest to zbiór wszystkich możliwych rozwiązań, które spełniają ograniczenia problemu. Satysfakcja z ograniczeń to proces znajdowania punktu w zbiorze wykonalnym.

Algorytm genetyczny

W przypadku algorytmu genetycznego kandydatami na rozwiązania są osobniki w populacji ewoluowanej przez algorytm.

Rachunek różniczkowy

W rachunku różniczkowym optymalne rozwiązanie jest poszukiwane za pomocą testu pierwszej pochodnej : pierwsza pochodna optymalizowanej funkcji jest równa zeru, a wszelkie wartości zmiennych do wyboru, które spełniają to równanie, są postrzegane jako rozwiązania kandydujące (podczas gdy te, które nie są wykluczeni jako kandydaci). Istnieje kilka sposobów, w których kandydujące rozwiązanie może nie być rzeczywistym rozwiązaniem. Po pierwsze, może dawać minimum, gdy poszukuje się maksimum (lub odwrotnie), a po drugie, może dawać ani minimum, ani maksimum, ale raczej punkt siodła lub punkt przegięcia , przy którym chwilowa przerwa w lokalnym wzroście lub nastąpi upadek funkcji. Takie kandydujące rozwiązania można wykluczyć za pomocą drugiego testu pochodnego , którego spełnienie jest wystarczające, aby kandydujące rozwiązanie było co najmniej lokalnie optymalne. Po trzecie, kandydatem na rozwiązanie może być optimum lokalne, ale nie globalne .

Przyjmując funkcja pierwotna stanowi jednomianów w postaci roztworu kandydującego pomocą wzoru kwadraturowego CAVALIERI za będzie Roztwór kandydat w rzeczywistości były wyjątkiem gdy${\ Displaystyle x ^ {n},}$${\ Displaystyle {\ tfrac {1} {n + 1}} x ^ {n + 1} + C.}$${\displaystyle n=-1.}$

Programowanie liniowe

Seria ograniczeń programowania liniowego na dwóch zmiennych tworzy obszar możliwych wartości dla tych zmiennych. Rozwiązywanie problemów z dwiema zmiennymi będzie miało dopuszczalny obszar w kształcie wypukłego wielokąta prostego, jeśli jest ograniczony. W algorytmie, który sekwencyjnie testuje punkty dopuszczalne, każdy testowany punkt jest z kolei rozwiązaniem kandydującym.

W jednostronnym sposobu rozwiązywania liniowych programowania problemów stosowano wierzchołek z możliwym Polytope jest wybrany jako początkowy roztwór kandydata i testowano na optymalność; jeśli zostanie odrzucone jako optymalne, sąsiedni wierzchołek jest uważany za następne rozwiązanie kandydujące. Proces ten jest kontynuowany do momentu znalezienia rozwiązania-kandydata jako optymalnego.

Bibliografia