6.1. Rozwiązanie optymalne i bazowe
Tw: Jeżeli zadanie programowania liniowego ma rozwiązanie optymalne to ma także rozwiązanie optymalne - bazowe.
Wniosek: rozwiązania optymalnego należy szukać wśród rozwiązań bazowych, których liczba jest skończona.
Definicja: Rozwiązanie bazowe - nazywa się dowolne rozwiązanie uzyskane przez podstawienie (przyjęcie) za n-m zmiennych 0 i rozwiązanie układu równań ze względu na pozostałe m-zmiennych.
Rozwiązań bazowych jest skończona liczba.
Rozwiązań jest tyle, ile jest kombinacji
, np. n=5, m=3
6.2 Istota programowania liniowego
Modele programowania liniowego są jednymi z najbardziej popularnych i uniwersalnych struktur modelowych służących matematycznej analizie ekonomicznych problemów decyzyjnych. Ich rozpowszechnienie uwarunkowane jest z jednej strony dużymi możliwościami liniowego przybliżenia większości procesów gospodarczych, z drugiej strony prostotą posługiwania się modelami tego typu. Proces kwantyfikacji problemu decyzyjnego oraz budowa modelu liniowego podlega ogólnym regułom budowy modelu matematycznego. Należy jedynie podkreślić warunki szczególne, którymi powinna cechować się sytuacja decyzyjna, aby możliwe było zastosowanie optymalizacyjnych modeli liniowych.
Ogólnie model liniowy można zapisać:
1) funkcja celu
f(x)=c1x1+ c2x2+...+ ckxk=
2) warunki ograniczające
a11x1+ a12x2+...+ a1kxk
a21x1+ a22x2+...+ a2kxk
...
am1x1+ am2x2+...+ amkxk
3)warunki brzegowe
xj
0 ; j=1,2,...k
cj-parametry funkcji celu; aij- parametry ograniczające; bij - parametry informujące o wielkości i-tego ograniczenia
6.3. Ogólna charakterystyka programowania dynamicznego
Jak decyzja podejmowana jest jednorazowo to --> zadanie statyczne.
Jak decyzja jest podejmowana wielokrotnie --> zadanie dynamiczne.
Jest to jedna z technik matematycznych, którą można wykorzystać do zarządzania procesami wieloetapowymi. Istnieje wiele zagadnień, których decyzji nie podejmujemy jednorazowo, lecz wielokrotnie, dlatego nazywa się je wieloetapowymi procesami decyzyjnymi.
Na ocenę interesującego nas procesu mają wpływ wszystkie decyzje podejmowane w trakcie jego trwania. Chcąc zoptymalizować wieloetapową funkcję celu obejmującą wszystkie etapy nie wystarczy rozwiązać ciągu zadań jednoetapowych, lecz trzeba na rozwiązanie popatrzeć kompleksowo.
Skutki decyzji podjętych w etapach wcześniejszych mogą w istotny sposób zmieniać możliwości decyzyjne w następnych etapach.
Na początku każdego etapu proces charakteryzowany jest wielkościami nazywanymi zmiennymi stanu. Decydent na początku każdego etapu ma możliwość obserwowania tych wielkości.
W kolejnych etapach istnieje możliwość sterowania przebiegiem takiego procesu przez wybór dopuszczalnych wartości zmiennych decyzyjnych. Zbiór tych wartości uzależniony jest od stanu w jakim znajduje się proces.
Podjęcie decyzji etapowej powoduje, że na początku następnego etapu proces znajduje się w kolejnym stanie.
Funkcję opisującą zależność między stanem procesu na początku następnego etapu a stanem procesu na początku etapu i podjętą decyzją nazywamy funkcją przejścia. Jednocześnie z przejściem takim związana jest etapowa korzyść lub strata.
Przy rozwiązywaniu zadań używana jest zasada optymalności Bellmana, która pozwala na dekompozycję zadania wyjściowego na ciąg powiązanych ze sobą prostych zadań, które rozwiązujemy kolejno rozpoczynając od ostatniego etapu. Przykładem zadania tego typu jest problem dyliżansu (należy przetransportować ładunek z punktu A do E. Układ komunikacyjny między punktami wraz z odległościami jest dany. Zadanie polega na wyborze najkrótszej trasy.).
6.4. Interpretacja ekonomiczna zagadnienia dualnego
Jeżeli zadanie pierwotne jest modelem pierwotnego problemu decyzyjnego i ma określoną interpretacje ekonomiczną, to również odpowiednią interpretację ma zbudowane w odniesieniu do niego zadanie dualne.
Jeżeli zdanie pierwotne opisuje problem maxymalizacji zysku, a ograniczenia dotyczą zużycia środków produkcji, które nie może przekroczyć poziomu posiadanych zasobów to zmienną dualną yi można interpretować jako cenę jednostkową i-tego środka produkcji.
Optymalna wartość zmienniej yi określa o ile wzrośnie przychód (zysk) jeśli zwiększy się zasób i-tego środka produkcji o jednostkę.
Ten wniosek jest prawdziwy gdy zmiany mieszczą się w dopuszczalnych granicach i dotyczą tylko jednego środka produkcji.
Zmienną dualną określa się więc jako krańcową produktywność jednostki i-tego środka.
6.5. Modele programowania liniowego w postaci standardowej i kanonicznej
Jeżeli w modelu warunki ograniczające mają charakter nierówności to taki model liniowy ma postać standardową. Natomiast jeśli mają postać równań to model ma postać Kanoniczną.
Każdą postać standardową można sprowadzić do postaci kanonicznej poprzez wprowadzenie do modelu postaci standardowej dodatkowych zmiennych (swobodnych, bilansowych)
n - liczba zmiennych w modelu; m - liczba równań ; n>m
Postać standardowa 9x1+6x2max
|
Postać kanoniczna 9x1+6x2max
|