PROGRAMOWANIE LINIOWE

Teoretyczne podstawy programowania liniowego

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ą:
                  (2.1.4)

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^opt
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ę 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^opt
D. 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^opt
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, 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 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. D^opt=
.
Dopt jest jednoelementowy. Jęsli 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, k
n ,tworzą wektor s
R^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.

 

MODEL EKONOMETRYCZNY

   Podstawowym obiektem rozpatrywanym w ekonometrii jest model ekonometryczny. Modelem ekonometrycznym nazywamy formalny opis stochastycznej zależności wyróżnionej wielkości, zjawiska lub przebiegu procesu ekonomicznego     ( zjawisk, procesów) od czynników, które je kształtują, wyrażony w formie pojedynczego równania bądź układu równań. Strukturę każdego równania określają: zmienna objaśniana, zmienne objaśniające (nielosowe lub losowe) mające ustaloną treść ekonomiczną, parametry strukturalne ,zmienna losowa (tradycyjnie nazywana składnikiem losowym) o nieznanej treści oraz określony typ związku funkcyjnego między zmienną objaśnianą a zmiennymi objaśniającymi i składnikiem losowym.

Przykład:1.1

Dany jest model ekonometryczny     

w którym Y oznacza produkcję cukru w Polsce (tys.t), X-powierzchnię uprawy buraka cukrowego (tys. ha). Zmienną Y nazywamy zmienną objaśnianą, zmienną X -objaśniającą,     
   
   są nieznanymi parametrami strukturalnymi modelu. Składnik losowy   
         wyraża tzw. błąd w równaniu, czyli wpływ na Y czynników nie uwzględnionych w modelu w sposób bezpośredni, takich jak: warunki klimatyczne, zawartość cukru w burakach cukrowych, przygotowanie cukrowni do kampanii cukrowniczej itp. Zależność produkcji cukru od powierzchni uprawy buraka cukrowego jest liniowa.

KLASYFIKACJA ZMIENNYCH WYSTĘPUJĄCYCH W MODELU EKONOMETRYCZNYM

Rozważamy dwa rozłączne podzbiory zmiennych występujących w modelach ekonometrycznych:

A - zmienne endogeniczne: bieżące i opóźnione (wyjaśniane przez model),

B - zmienne egzogeniczne: bieżące i opóźnione (nie wyjaśniane przez model).

Ze względu na rolę pełnioną przez poszczególne zmienne w modelu możemy jeszcze wprowadzić podział na:

C - zmienne objaśniane

D - zmienne objaśniające.

W ogólnym przypadku zbiory C i D nie są zbiorami rozłącznymi, ponieważ zmienna objaśniana może być jednocześnie ( w tym samym modelu) zmienną objaśniającą. Z taką sytuacją można zetknąć się w modelach wielorównaniowych.

KLASYFIKACJA MODELI EKONOMETRYCZNYCH

Modele ekonometryczne klasyfikujemy ze względu na pięć kryteriów.

KRYTERIUM 1. Liczba równań w modelu.

Podział: - modele jednorównaniowe (patrz przykład 1.1),

             -modele wielorównaniowe, w których każde równanie objaśnia jedną zmienną.

Przykład 1.2   Dany jest model ekonometryczny 

 w którym: 

PKB - produkt krajowy brutto,  

I - inwestycje, 

 Z - zatrudnienie,                                    

  - parametry modelu,    

  - składniki losowe,   

t - numer roku.

Wcześniej zdefiniowane, odpowiednie podzbiory zmiennych modelu ekonometrycznego są następujące:

A={PKB,I}    ,     B={Z}   ,     C= 
          , D=

Zmienne  
        nazywamy zmiennymi opóźnionymi.

KRYTERIUM 2. Postać analityczna zależności funkcyjnych modelu.

Podział: 

- modele liniowe (przykłady 1.1 i 1.2), w których wszystkie zależności modelu są liniowe,   

- modele nieliniowe, w których chociaż jedna zależność modelu jest nieliniowa.

Przykład 1.3  Dany jest jednorównaniowy, nieliniowy model ekonometryczny

 

w którym:     

 
- produkt krajowy brutto w roku t,  

- majątek produkcyjny w roku t,   

- zatrudnienie w gospodarce w roku t,   

- parametry,   

- czynnik losowy. 

  Zmienną losową    w przykładach 1.1 i 1.2 włączoną do modelu przez dodawanie  nazywamy addytywnym składnikiem losowym, a zmienną losową w przykładzie 1.3 włączoną do modelu przez mnożenie nazywamy multiplikatywnym składnikiem losowym.

KRYTERIUM 3. Rola czynnika czasu w równaniach modelu.

Podział: 

- modele statyczne (przykłady 1.1 i 1.3), nie uwzględniają czynnika czasu, wśród zmiennych objaśniających nie występują zmienne opóźnione ani zmienna losowa,    

 - modele dynamiczne, w których uwzględnia ie czynnik czasu (przykład 1.2). Najlepiej znanym przypadkiem modelu dynamicznego jest model autoregresyjny,  w którym wśród zmiennych objaśniających występują jedynie opóźnione w czasie zmienne objaśniane.

KRYTERIUM 4. Ogólno poznawcze cechy modelu.

Podział: 

- modele przyczynowo opisowe wyrażające związki przyczynowo skutkowe między zmiennymi objaśniającymi i objaśnianymi,  

- modele symptomatyczne, w których rolę zmiennych objaśniających pełnią zmienne skorelowane z odpowiednimi zmiennymi objasnianymi a nie wyrażające źródeł zmienności zmiennych objaśnianych.

Ostatnie kryterium podziału modeli ekonometrycznych dotyczy modeli wielorównaniowych.

KRYTERIUM 5. Charakter powiązań między nieopóźnionymi zmiennymi endogenicznymi w modelu wielorównaniowym.

Podział:

 - modele proste,   

- modele rekurencyjne,   

• modele o równaniach współzależnych.

Postać jednorównaniowego modelu ekonometrycznego.

 

Rozpatrujemy liniową zależność zmiennej objaśnianej od zmiennych objaśniających i składnika losowego

            (2.1)

gdzie:

Y- zmienna objaśniana,

- zmienne objaśniające, j=1,2,3,...,k,

- nieznane parametry strukturalne modelu, j=0,1,...,k

- składnik losowy

Naszym celem jest oszacowanie parametrów modelu na podstawie posiadanych informacji statystycznych, dotyczących wartości zmiennych występujących w modelu. zakładamy, że dysponujemy n-elementowymi szeregami czasowymi obserwacji dla wszystkich zmiennych modelu. W przypadku danych przekrojowych n oznacza liczbę obiektów. Oznaczamy:

- wartość zmiennej objaśnianej w okresie t, t=1,2,...,n,

- wartość j-tej zmiennej objaśniającej w okresie t, t=1,2,...,n,

oraz zapisujemy posiadane informacje w ujęciu macierzowym:

 

- wektor obserwacji zmiennej objaśnianej,

 

 

- macierz zaobserwowanych wartości zmiennych objaśniających.

Po uwzględnieniu znanych wartości poszczególnych zmiennych zależność (2.1) przyjmuje postać układu n-równań liniowych:

      
           (2.2)

Przy dodatkowym oznaczeniu:

 

-wektor składników losowych,

 

 

-wektor nieznanych parametrów modelu,

 

jednorównaniowy liniowy model ekonometryczny zapisujemy w postaci

      (2.3)

Równanie macierzowe (2.3) zawiera nieznane parametry strukturalne modelu 
  oraz składniki losowe 
   , których własności a priori nie znamy.

---