PROGRAMOWANIE LINIOWE
Teoretyczne podstawy programowania liniowego
Znaleść maksimum (minimum) funkcji:
przy założeniu że zmienne x1 ,x2,...., xn czynią zadość następującym warunkom:
oraz
nazywamy modelem programowania liniowego, w skrócie modelem PL. Stosuje się także oznaczenie ZPL. Zadanie PL (2.1.1)-(2.1.3) wykorzystuje się do modelowania i optymalizacji wielu rzeczywistych problemów decyzyjnych.
Zadanie programowania liniowego jest określone jednoznacznie, gdy znane są wartości wszystkich parametrów występujących we wzorach (2.1.1) i (2.1.2) , to znaczy liczby ci, aij oraz bj, dla i=1,...,n, j=1,...,m.
Ze strukturą modelu PL wiążą się pojęcia:
zmienne decyzyjne - zmienne x1,x2,...,xn, decyzja (rozwiązanie) - wektor wartości zmiennych decyzyjnych (x1,x2,...,xn) Rn, funkcja celu - funkcja f dana wzorem (2.1.1), współczynniki funkcji celu - parametry c1,c2,...,cn, warunki ograniczające - nierówności występujące w układzie (2.1.2), warunki nieujemności - nierówności (2.1.3) dotyczące znaku wartości zmiennych decyzyjnych, kryterium optymalności - wartość funkcji celu f podlegająca maksymalizacji albo minimalizacji, (max albo min).
Jeżeli z treści problemu wynika, że pewien warunek ograniczający ma postać równania:
ai1x1+...+ainxn=bi
wówczas w układzie (2.1.2) jest on reprezentowany przez parę nierówności:
W celu uproszczenia zapisu wzorów (2.1.1), (2.1.2), (2.1.3) wprowadzamy notację macierzową:
Zgodnie z tymi oznaczeniami zadanie PL ma postać:
(2.1.5)
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
. Mianowicie:
-przy minimalizacji funkcji f, decyzja jest lepsza niż decyzja wtedy i tylko wtedy, gdy ,
-przy minimalizacji funkcji f, decyzja jest lepsza niż decyzja wtedy i tylko wtedy, gdy
(…)
…
(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 D. 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 D jest jednocześnie rozwiązaniem optymalnym, Dopt=D.
Jeżeli zbiór rozwiązań dopuszczalnych…
… jest wierzchołkiem zbioru D. 3. Dopt ma nieskończenie wiele elementów. Należy podkreślić, że wśród tych elementów musi wystąpić conajmniej jeden wierzchołek zbioru D. Na przykład zbiór Dopt jest odcinkiem łączącym dwa wierzchołki zbioru D, albo półprostą wychodzącą z wierzchołka zbioru D.
1
…
... zobacz całą notatkę
Komentarze użytkowników (0)