PROGRAMOWANIE LINIOWE

Teoretyczne podstawy programowania liniowego

Znaleźć maksimum (minimum) funkcji:

przy założeniu że zmienne x₁ ,x₂,...., x_n czynią zadość następującym warunkom:

oraz

Powyższe warunki  wraz określeniem funkcji celu 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 c_i, a_ij oraz b_j, dla i=1,...,n,  j=1,...,m.

Ze strukturą modelu PL wiążą się pojęcia:
zmienne decyzyjne                - zmienne x₁,x₂,...,x_n,
decyzja (rozwiązanie)            - wektor wartości zmiennych decyzyjnych (x₁,x₂,...,x_n)Rⁿ,
funkcja celu                           - funkcja f dana wzorem (2.1.1),
współczynniki funkcji celu    - parametry c₁,c₂,...,c_n,
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:

a_i1x₁+...+a_inx_n=b_i

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 x^optD, że dla każdego xD:

-w przypadku maksymalizacji wartości funkcji f

                                                    (2.1.6a)               

-w przypadku minimalizacji funkcji f

                                                   (2.1.6b)

Każdą decyzję x^opt spełniającą warunki (2.1.6a), odpowiednio (2.1.6b) nazywamy decyzją optymalną, a wartość  f(x^opt) nazywamy optymalną wartością funkcji celu. Zbiór decyzji optymalnych oznaczamy D^opt. Zauważmy, że D^optD. Ponadto dwa różne rozwiązania optymalne nazywamy alternatywnymi decyzjami optymalnymi.

Zatem rozwiązanie zadania PL polega na wyznaczeniu zbioru D^opt oraz na obliczeniu optymalnej wartości funkcji celu f(x^opt) dla x^optD.

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 xD jest jednocześnie rozwiązaniem optymalnym, D^opt=D.

Jeżeli zbiór rozwiązań dopuszczalnych ma nieskończenie wiele elementów, lecz jest ograniczony, to D^opt. 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)=c^Tx, dla c0 , 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. D^opt=.
Dopt jest jednoelementowy. Jeśli D^opt={x^opt}, to x^opt jest wierzchołkiem zbioru D.
3.   D^opt 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 D^opt jest odcinkiem łączącym dwa wierzchołki zbioru D, albo półprostą wychodzącą z wierzchołka zbioru D.

Zastosowanie metody simpleks w celu rozwiązania zadania programowania liniowego wymaga nadania temu zadaniu specjalnej postaci zwanej postacią standardową. Przyjmuje się wówczas następujące ustalenia:

1. Funkcja celu podlega kryterium maksymalizacji,
2. Wyrazy wolne w warunkach ograniczających są nieujemne,
3. Wszystkie warunki ograniczające są równościami,
4.Wszystkie zmienne występujące w tej postaci zadania są nieujemne.

Postulat 1 prowadzi , w przypadku kryterium minimalizacji wartości funkcji celu do następującej zmiany formuły (2.1.1):

Wobec 2, w przypadku występowania w układzie warunków ograniczających (2.1.2) ujemnego wyrazu wolnego, należy warunek z tym wyrazem pomnożyć obustronnie przez liczbę -1.

Postulat 3 wymaga wprowadzenia do nierówności występujących w układzie (2.1.2) nieujemnych zmiennych dodatkowych niedoboru albo nadmiaru, odpowiednio do zwrotu tych nierówności. Nieujemne zmienne dodatkowe s₁,s₂,...,s_k, kn ,tworzą wektor sR^k i spełniają postulat 4.

Zatem postać standardowa modelu (2.1.5), to:

                 (2.1.8)

gdzie    

Macierz ma wymiary zgodne z wymiarami macierzy A i elementy tych macierzy spełniają warunek dla i=1,2,...,n ,  j=1,2,...,m.

Ponadto macierz ma m wierszy i tyle kolumn ile zmiennych dodatkowych wprowadzono do modelu.

Problemy decyzyjne, dla których można zbudować model PL (2.1.5) najczęściej dotyczą następujących przejawów działalności ekonomicznej:

a) ustalenia wielkości i struktury produkcji,
b) problemu diety,
c) zagadnienia transportowego (ZT),
d) problemu rozkroju, i tym podobnych

Dodajmy na koniec, że wiele zadań PL odnosi się do zmiennych decyzyjnych, których interpretacja jest możliwa tylko dla wartości całkowitoliczbowych. Te klasę zagadnień nazywamy całkowitoliczbowymi zadaniami PL, w skrócie ZPLC.

Mapa strony ekonometria.4me.pl

Copyright © ekonometria.4me.pl 2005-2013. Wszelkie prawa zastrzeżone. Zabrania się kopiowania, redystrybucji, publikacji lub modyfikacji jakichkolwiek materiałów zawartych na stronie internetowej , bez wcześniejszej pisemnej zgody autorów.

PROGRAMOWANIE LINIOWE