110714

f (i) = cTx —> max(min) pr2y warunkach (Ax<.b [x 20

Zbiór decyzji wyznaczonych przez warunki (2.1.2) oraz (2.1.3) nazywamy zbiorem decyzji dopuszczalnych I oznaczamy symbolem D.

Najczęściej zbiór D ma nieskończenie wiele elementów, ale może się zdarzyć, że jest on jednoelementowy lub pusty. Elementy zbioru D nazywane decyzjami dopuszczalnymi określane są także mianem rozwiązań dopuszczalnych.

W ogólnym przypadku zbiór D jest domkniętym wielościennym zbiorem wypukłym o skończonej liczbie wierzchołków. W szczególności jeśli D jest zbiorem ograniczonym, to jest on powłoką wypukłą rozpięta na swoich wierzchołkach. Wówczas nazywamy go wielościanem wypukłym.

Wobec kryterium optymalności nałożonego na wartości funkcji celu można porównać każde dwa rozwiązania dopuszczalne

x,xeD

Mianowicie:

-przy minimalizacji funkcji f, decyzja ^x jest lepsza niż decyzja ^x wtedy i tylko wtedy, _gdy /(*)>/<*),

-przy minimalizacji funkcji f, decyzja ^x jest lepsza niż decyzja ^x wtedy i tylko wtedy,

g_dy/(*)>/(*),

-przy dowolnym kryterium decyzja ^x jest równoważna decyzji ^x wtedy I tylko wtedy, gdy /(*) = /(*).

Roztrzygnięcie problemu opisanego modelem PL sprowadza się do wskazania decyzji najlepszych, czyli takich elementów xopt^€D, że dla każdego x^eD:

-w przypadku maksymalizacji wartości funkcji f

/(x^)2/(x)

-w przypadku minimalizacji funkcji f

(2.1 6a)

(2.1.6b)

Każdą decyzję xopt spełniającą warunki (2.1.6a). odpowiednio (2.1.6b) nazywamy decyzją optymalną, a wartość f(xopt) nazywamy optymalną wartością funkcji celu.

Zbiór decyzji optymalnych oznaczamy Dopt. Zauważmy, że Dopt^eD. Ponadto dwa różne rozwiązania optymalne nazywamy alternatywnymi decyzjami optymalnymi.

Zatem rozwiązanie zadania PL polega na wyznaczeniu zbioru Dopt oraz na obliczeniu optymalnej wartości funkcji celu f(xopt) dla xopt - D.

Jeżeli zbiór rozwiązań dopuszczalnych jest pusty (D= ®), to Dopt też jest zbiorem pustym a zadanie PL nie ma rozwiązania. Powiemy wtedy ,że zadanie jest sprzeczne.

Jeżeli zbiór rozwiązań dopuszczalnych jest jednoelementowy, to jedyne rozwiązanie dopuszczalne x^eD jest jednocześnie rozwiązaniem optymalnym, Dopt=D.

2