ZESTAW 6
1.rozwiązanie bazowe i optymalne
2.istota programowania liniowego
3.dynamiczne-opisz
4.interpretacja ogólna dualności
5.macierzowe i niemacierzowe modele postaci kanonicznej i
standardowej
1.Roz. optymalne.- dop., które optymalizuje funkcję celu, określa decyzję optymalną; Roz. bazowe-dowolne rozwiązanie uzyskane przez przyjęcie za n-m zmiennych 0 oraz rozwiązania warunków ograniczających ze względu na pozostałe m-zmiennych. Max. ilość rozwiązań bazowych jest równa liczbie kombinacji: c^n-m,n=n!/(n-m)!m! gdzie n - liczba zmiennych decyzyjnych; m - liczba warunków brzegowych;
2.Program. liniowe w liczbach całkowitych- zad. programowania liniowego gdzie do warunków brzegowych dołączamy dodatkowe warunki całkowitoliczbowości wszystkich zmiennych decyzyjnych.
Część całkowita- liczby [a] nazywamy największa liczbę całkowitą mniejszą lub równą. Część ułamkowa- f(a)=a-[a]; 0<=f(a)<1 Dwie liczby wymierne a i b nazywamy kongruentnymi (przystającymi) jeśli ich różnica jest liczba całkowitą Własności: 1) a ≡ b f(a) ≡f(b); 2) f(a+b) ≡ f(a) + f(b); 3) na ≡ f(na) ≡ n f(a), nєC
3.PROGRAMOWANIE DYNAMICZNE, WIELOETAPOWE PROCESY DECYZYJNE. Skutki decyzji podjętych w etapach wcześniejszych mogą w istotny sposób zmieniać możliwości decyzyjne w kolejnych 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 dopuszczalnej wartości zm decyzyjnych, zwanych wielkościami sterującymi. 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ści między stanem procesu na początku następnego etapu a stanem procesu na początku bieżącego etapu i podjętą decyzją nazywamy funkcją przejścia. Jednocześnie z przejściem takim związana jest etapowa korzyść lub strata. Strategią nazywamy funkcję, która każdemu stanowi dopuszczalnego przyporządkowuje pewną decyzję dopuszczalną. Strategią optymalną - która każdemu stanowi dopuszczalnemu przyporządkowuje decyzję optymalną. Rozwiązując zadanie programowania dynamicznego można wykorzystać jego strukturę etapową. Podział procesu na etapy powoduje, że zamiast rozwiązywać jedno duże i zazwyczaj trudne zadanie, rozwiązuje się szereg mniejszych i łatwiejszych do rozw., powiązanych ze sobą zadań.
4.Dualizm w programowaniu liniowym charakteryzuje się tym ,z e każde zadanie liniowe polegające na max lub min posiada pewne ekwiwalentne zadanie liniowe polegające na min lub max. Przyjmuje się że oryginalne sformułowanie problemu jest zadaniem pierwotnym prymalnym, natomiast sformułowania alternatywne jest zadaniem dualnym (wtórnym). Model prymalny : L(x)= CTX max AX ≤ B X≥0 Model dualny : L(Y)= BTY min ATY ≥ C Y≥0 Y - wektor zmiennych dualnych
5.Postać kan.- jeżeli wszystkie warunki ograniczające w modelu mają charakter równań. Postać stand.- gdy układ warunków ograniczających ma charakter nierówności typu ≥ albo ≤. Zamiana: każde zadanie w postaci standardowej można sprowadzić do postaci kanonicznej przez zmianę charakteru warunków ograniczających, tzn zastąpienie nierówności liniowych równaniami liniowymi poprzez wprowadzenie do modelu dodatkowych zmiennych zwanych swobodnymi, bilansującymi. Dla zmiennych swobodnych zakłada się zerowe wartości funkcji celu. Jeżeli warunek ograniczający jest nierównością o znaku „≤” to zmienną swobodną wprowadzamy ze znakiem „+”. Natomiast, gdy warunek ograniczający jest nierównością o znaku „≥” to zmienną swobodną wprowadzamy ze znakiem „─”. Zmienne swobodne mają interpretację ekonomiczną, przy czym inaczej ich wartość interpretuje się gdy są wprowadzone ze znakiem „+”, tzn. że oznaczają zapasy (rezerwy) tego środka produkcji, w którym występują, a inaczej w przypadku gdy są wprowadzone ze znakiem „─”.
POSTAĆ STANDARDOWA POSTAĆ KANONICZNA MACIERZOWA
z = 2x1 + 5x2 → max z = 2x1 + 5x2 + 0x3 + 0x4 + 0x5 → max
x1 + 4x2 ≤ 24 x1 + 4x2 + x3= 24
3x1 + x2 ≤ 21 3x1 + x2 + x4 = 21
x1 + x2 ≤ 9 x1 + x2 +x5 = 9
x1, x2 ≥ 0 x1, x2, x3, x4, x5 ≥0
m = 3 n = 2 m = 3 n = 5 n > m
W postaci kanonicznej liczba zmiennych jest większa od ilości równań. Jeżeli m = n to układ ma dokładnie jedno rozwiązanie. Nie istnieje tu problem optymalizacji. Gdy n > m to układ posiada nieskończenie wiele rozwiązań, a więc w tym to przypadku istnieje możliwość wybrania rozwiązania optymalnego.