Algorytm simplex. Istota polega na badaniu kolejnych rozwiązań bazowych ( dopu- szczalnych). Szukamy rozwiązania podstawowego. Tworzymy postać standardową: 1 funkcja celu, 2 warunki uboczne, 3 warunki brzegowe. Następnie tworzymy postac kanoniczną. Znajdujemy rozwiązanie bazowe programu. Sprawdzamu czy jest ono dopuszczalne. Wykorzystujemy w tym celu kryterium optymalności Δj=Σcizij-cij. Gdy Δj < 0 a f. celu →max to plan można ulepszyć. Aby ulepszyć rozwiązanie należy ustalić wiersz i kolumnę kluczową. K. Kluczowa oznacza jaką zmienną należy wprowadzić do bazy aby ulepszyć rozwiązanie. Wiersz k. Jest to najmniejszy iloraz wynikający z podzielenia wektora B przez odpowiedni element z kolumny k. ( θ ). Wiersz k oznacza którą zmienną należy usunąć z bazy aby na jej miejsce wprowadzić zmienną z kolumny k . na przecięciu wiersza i kolumny znajduje się element rozwiązujący. Jeżeli dane rozwiązanie nie jest optymalne konstruujemy następne rozwiązanie bazowe lepsze a przynajmniej nie gorsze.
Prawo tworzenia tablic oprócz pierwszej. 1 dzielimy każdy element wiersza k przez element rozwiązujący. Otrzymane ilorazy będą odpowiednimi elementami nowego wiersza następnej tablicy. 2 wszystkie pozostałe elementy obliczamy wg następującego wzoru; NE=WE-(EKKxEWK)/ER
Metoda sztucznej bazy. Metodę tę stosujemy wówczas kiedy warunki uboczne modelu są nierównościami typu ≥ albo równaniami. Aby taki model sprowadzić do postaci kanonicznej należy do każdej nierówności wprowadzić zm. Swobodną ze znakiem - .
a11x1+a12x2+...+a1nxn-xn+1=b1
w tym przypadku istnieje problem zbudowania rozwiązania podstawowego ponieważ wartości zmiennych nie spełniają warunku bazowego. Aby zbudować rozwiązanie podstawowe należy wprowadzić do każdego równania zmienną sztuczną, która spełnia warunki brzegowe.
a11x1+a12x2+...+a1nxn-xn+1 +u1=b1 Zmienia się f celu:
Z=c1x1+c1x1 +...+cnxn+Mu1
M bardzo duża liczba dodatnia. Zmienne sztuczne nie mają interpretacji ekon. Wprowadzamy je tylko w celu rachunkowym. Przy max -M, przy min +M.
Twierdzenia dotyczącej metody M.
Jeżeli rozwiązanie wyjściowe ma chociaż jedno rozwiązanie optymalne to jest ono również rozwiązaniem zadania rozszerzonego. Zastosowanie metody simplex do zadania rozszerzonego zapewnia takie rozwiązanie w którym każda ze zmiennych sztucznych=0.
2 jeżeli zadanie wyjściowe nie ma rozwiązania to rozwiązanie zadania rozszerzonego będzie zawierać przynajmniej jedno ui.
Algorytm transportowy.
1 Polega on na ustaleniu rozwiązania podstawowego. Dwie metody: metoda lewego górnego rogu polega na przyporządkowaniu zmiennym wartości liczbowych zaczynając od lewego górnego rogu, przez korektę odpowiednich wartości przesuwamy się po przekątnej do prawego dolnego rogu. Metoda minimum macierzy polega na znalezieniu macierzy kosztów bezpośrednich, najniższego kosztu i wprowadzeniu w tę kratkę odpowiedniego ładunku. Następnie wpisujemy odpowiednie wielkości ładunków i wykreślamy wiersz lub kolumnę. Aż do wykreślenia całej macierzy.
2 Sprawdzamy, czy rozwiązanie podstawowe jest optymalne. W tym celu wychodzimy z jednego z planów ustalonych przedstawionymi metodami. W tym celu należy wyznaczyć tablicę kosztów pośrednich cij . W tym celu stosujemy metodę jednakowych różnic. W kratki bazowe wpisujemy koszty bezpośrednie i bierzemy je w kółka. Pozostałe miejsca w tablicy wypełniamy w sposób następujący. Uwzględniając koszty w kratkach bazowych
ustalamy różnicę między nimi dotyczy wierszy lub kolumn. Ustalona różnica musi być zachowana do końca tablicy. Następnie obliczamy kryterium optymalności:∆j=cij-cij koszty pośrednie - koszty bezpośrednie. Jeżeli wszystkie elementy w tablicy ∆j są ≤ 0 to kończymy obliczenia przyjmując rozwiązanie podstawowe za optymalne. Jeżeli choć jedna kratka w tablicy ∆j jest >0 to rozwiązanie nie jest optymalne. 3 Modyfikacja rozwiązania. W tym etapie korzystamy z metody simplex, która mówi, że do nowego rozwiązania wprowadzamy tę zmienną, dla której Δj jest największa. Wprowadzając tę zmienną do bazy musimy inną zmienną z bazy usunąć, a ponadto pociąga to za sobą zmianę wartości innych niektórych zmiennych decyzyjnych. Reguły pozwalające na korygowanie wartości zmiennych: w ostatnim planie wytyczamy graf zaczynając od kratki gdzie koszt jest największy wprowadzając do niej symbol + i na zmianę symbol - , przy czym nie wolno jest zmienić kierunku przez pustą kratkę. Ilość ładunku jaką należy przenieść jest równa najmniejszej liczbie opatrzonej symbolem - l. W metodzie simplex odpowiada to wartości θ. Aby stwierdzić czy plan jest optymalny należy powtórzyć etap 2 czyli obliczyć koszty pośrednie. Dualizm. Dla każdego zadania decyzyjnego nazwanego zadaniem pierwotnym, istnieje pewne inne zadanie decyzyjne nazwane dualnym Dualizm można rozpatrywać w aspekcie ekonomicznym i matematycznym. Model dualny jest odrębnym programem z nowymi nie występującymi w programie pierwotnym zmiennymi yi.
Własności programu dualnego.
1. jeżeli w zadaniu pierwotnym chodzi o maksymalizację funkcji celu to w zad dualnym należy minimalizować.
2. liczba zmiennych w zadaniu dualnym jest równa liczbie równań w zadaniu pierwotnym.
3. wagi funkcji celu zadania pierwotnego są wyrazami wolnymi zadania dualnego.
4. wyrazy wolne zadania pierwotnego są wagami funkcji celu zadania dualnego.
5. macierz współczynników przy zmiennych decyzyjnych w programie dualnym jest macierzą transponowaną macierzy z programu pierwotnego.
6. kierunek nierówności w warunkach ubocznych programu dualnego jest przeciwny.
Związki matematyczne.
1. przy dowolnych rozwiązaniach dopuszczalnych programu pierwotnego i dualnego wartość funkcji celu pr. Pierwotnego nie przewyższa f celu pr dualnego. 2. oba programy mają rozwiązania optymalne. Są to takie i tylko takie rozwiązania, przy których wartości f celu programów i rozwiązania optymalne programów są sobie równe. 3. na to aby wektory były odpowiednio optymalnymi rozwiązaniami swoich programów potrzeba i wystarczy aby spełnione były warunki; a) jeżeli i-ty warunek pr pierwotnego jest optymalnym rozwiązaniem tego pr spełniony z nierównością to i-ta zmienna w optymalnym rozwiązaniu pr dualnego przyjmuje wartość 0. b) jeżeli j-ty warunek pr dualnego jest optymalnym rozwiązaniem tego pr spełniony z nierównością to j-ta zmienna w optymalnym rozwiązaniu pr pierwotnego przyjmuje wartość 0.
Metoda geometryczna.
Metodę tę stosujemy w przypadku gdy model decyzyjny składa się z 2 lub 3 zmiennych . Etap 1 polega na wyznaczeniu obszaru dopuszczalnych rozwiązań. W tym celu należy wykreślić proste, których punkty spełniają równania odpowiadające danym nierównością. Następnie należy rozstrzygnąć, po której stronie prostych znajdują się punkty spełniające dane nierówności. Ponieważ wszystkie te nierówności muszą być spełnione jednocześnie, poszukujemy obszaru, który jednocześnie spełnia ten układ. Obszar ten jest wypukły. Z wypukłości obszaru dopuszczalnych rozwiązań wynika, że rozwiązania optymalnego należy szukać wśród wierzchołków tego obszaru.
Etap 2. Aby wyznaczyć rozwiązanie optymalne należy wyjść z f celu. Znajdujemy równanie izokwanty (linii izocelowej)
dla zerowej wartości f celu.
Przesuwając równolegle Izokwantę nie zmieniają się parametry . jeżeli f celu→ max to poszukujemy wierzchołka leżącego najdalej od początku układu wsp. Jeżeli f celu→min to poszukujemy wierzchołka położonego najbliżej początku układu .
Klasyfikacja modeli decyzyjnych.
1 ze względu na zmienne decyzyjne: a) linowe - zmienne w modelu są w pierwszej potędze b) nieliniowe - wtedy gdy przynajmniej jedna ze zmiennych jest w innej niż pierwszej potędze
2 ze względu na parametry: a) deterministyczne - wszystkie parametry modelu są stałe i znane b) stochastyczne - przynajmniej jeden parametr jest niestały niepewny: aa) probabilistyczne - choć jeden parametr jest zmienną losową o znanym rozkładzie prawdopodobieństwa bb) statystyczne - choć jeden parametr jest zm los o nie znanym rozkładzie prawdopodobieństwa cc) strategiczne - o parametrze wiemy tylko to że przyjmuje wartości z pewnego przedziału
3 ze względu na czas: a) statyczne - model dotyczy jednego okresu b) dynamiczne - gdy dotyczy kilku okresów.
Etapy BO.
1 budowa modelu - należy określić cel lub cele działania , wyodrębnić czynniki od których zależy osiągnięcie tego celu. Konstruujemy postać analityczną modelu.
2 rozwiązanie modelu ( wyznaczenie decyzji optymalnej) - w zależności od postaci analitycznej stosujemy metody za pomocą których wyznaczamy decyzje optymalne analitycznego zagadnienia.
3 weryfikacja modelu i uzyskanie rozwiązania - analiza rozwiązania powinna odpowiedzieć na pytanie jak dalece rozwiązanie zmieni się w toku procesu decyzyjnego w zależności od zmiany niektórych czynników
4 wdrażanie modelu