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
,

-przy dowolnym kryterium decyzja
jest równoważna decyzji
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
D:

-w przypadku maksymalizacji wartości funkcji f

                                                    (2.1.6a)               

-w przypadku minimalizacji funkcji f

                                                   (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 ma nieskończenie wiele elementów, lecz jest ograniczony, to Dopt

. Zadanie PL ma wtedy rozwiązanie.

Jeżeli zbiór rozwiązań dopuszczalnych jest nieograniczony, to w pewnych przypadkach zadanie PL nie ma rozwiązania. Może sie bowiem zdarzyć, że liniowa funkcja celu f(x)=cTx, dla c
0 , określona na nieograniczonym zbiorze D przyjmuje dowolnie duże albo dowolnie małe wartości. Brak kresu górnego f(D) powoduje, że przy maksymalizacji wartości funkcji celu nie istnieje rozwiązanie optymalne. Podobną sytuację obserwujemy przy minimalizacji funkcji celu, która na nieograniczonym zbiorze D nie ma kresu dolnego.

W obu tych przypadkach stwierdzamy, że z powodu nieograniczonej optymalnej wartości funkcji f na zbiorze D zadanie PL nie ma rozwiązania.

Jeśli zbiór rozwiązań dopuszczalnych jest nieograniczony, lecz funkcja celu osiąga na tym zbiorze kres górny, to w przypadku kryterium maksymalizacji istnieje rozwiązanie zadania PL. Jeśli natomiast funkcja osiąga na zbiorze D kres dolny ,to w przypadku minimalizacji również istnieje rozwiązanie zadania PL.

Powyższe rozważania prowadzą do następującej konkluzji odnoszącej się do postaci zbioru Dopt. Możliwe są przypadki:

1. Dopt=
.
2. Dopt jest jednoelementowy. Jeśli Dopt={xopt}, to xopt 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

---