Badania operacyjne opracowanie.doc

Metoda geometryczna

Aby zdrowo wyglądać pies musi miesięcznie zjeść przynajmniej 100g składnika                 1 (S1), 200g składnika 2 (S2) i nie więcej jak 300g składnika 3 (S3).
Na rynku dostępne są dwie karmy, gdzie porcja karmy 1 (K1) zawiera 10g składnika 1, 1g składnika 2 i 10g składnika 3. Natomiast karma 2 (K2) zawiera 1g składnika 1, 10g składnika 2 i 10g składnika 3.

Porcja karmy 1 (K1) kosztuje 5 zł, natomiast porcja karmy 2( K2) 8zł.
W jakich porcjach zmieszać karmy aby pies dostał składników ile potrzeba a koszt był jak najmniejszy.

Ustalamy funkcję celu, która dąży do minimum (chcemy uzyskać minimalny koszt):
(granatowy wiersz tabelki) f(x) = 5x1 + 8x2 --> MIN

Następnie należy napisać nierówności dla każdego ze składników:
(lewa strona nierówności to zielona część tabelki, prawa - pomarańczowa)
10x1 + 1x2 >= 100
1x1 + 10x2 >= 200
10x1 + 10x2 <= 300
oraz ograniczenia postawione rozwiązaniu:
x1 >= 0, x2 >= 0

W następnym kroku ustalamy gradient dla funkcji celu:
F(x) = 5x1 + 8x2 --> MIN
gradient: [x1=5,x2=8]

Krok kolejny to przekształcenie nierówności w równania i wyznaczenie punktów przecięcia z osiami x1 i x2.
(1) 10x1 + 1x2 = 100      zakładam, że x2=0 stąd x1=10; teraz x1=0 stąd x2=100
(2) 1x1 + 10x2 = 200      zakładam, że x2=0 stąd x1=200; teraz x1=0 stąd x2=20
(3) 10x1 + 10x2 = 300    zakładam, że x2=0 stąd x1=30; teraz x1=0 stąd x2=30

Tak wyliczone punkty nanosimy na wykres. Zacznijmy od prostej dla równania 1:
punkt 1 - [10,0]
punkt 2 - [0,100]
 

Następnie prosta dla równania 2:
punkt 1 - [200,0]
punkt 2 - [0,20]

Prosta dla równania 3:
punkt 1 - [30,0]
punkt 2 - [0,30]

Mając już narysowane proste nanosimy na wykres gradient.
Gradient dla funkcji celu:
punkt 1 - [0,0]
punkt 2 - [5,8]

Poniżej widać nieco powiększone zdjęcie. Narysowane proste utworzyły mały trójkąt. Właśnie jeden z wierzchołków tego trójkąta będzie rozwiązaniem naszego zadania. Aby przekonać się który, musimy poprowadzić jeszcze jedną prostą prostopadłą do gradientu     i zaczepioną w punkcie [0,0].

W celu otrzymania dokładnego wyniku obliczamy układ równań dla prostych, które przecinają się w wyznaczonym wierzchołku:
(1) 10x1 + 1x2 = 100
(2) 1x1 + 10x2 = 200

(1)x2 = 100-10x1
(2) x1 + 10*(100-10x1) = 200

x1-100x1 = 200-1000
x1 = 800/99 = 8.08

x2 = 100-10*8.08 = 19.19

Koszt = 5x + 8x2 = 5*8.08 + 8*19.19 = 193.92

Należy zmieszać 8.08 porcji karmy 1 i 19.19 porcji karmy 2. Mieszanka ta będzie kosztowała 193.92 zł.

Metoda simpleks

Rozwiążmy następujące zadanie metodą simpleks.
Piekarnia produkuje 3 rodzaje bułek (B1, B2, B3), które odpowiednio kosztują 1, 3 i 2 złote.
Na wypiek bułki pierwszej (B1) potrzeba 1 dkg mąki, 1 dkg cukru.
Na wypiek bułki drugiej (B2) potrzeba 2 dkg mąki, 1 dkg cukru i 1 dkg rodzynek.
Bułka trzecia (B3) wymaga 1 dkg mąki, 1 dkg cukru i 2 dkg rodzynek.
Przy czym w magazynie piekarni dostępne jest tylko 5 dkg mąki, 4 dkg cukru i 1 dkg rodzynek.
Nasze zadanie polega na ustaleniu ile i jakich bułek powinniśmy upiec, aby otrzymać największy zysk, biorąc pod uwagę ograniczone zapasy składników.

Następnie należy doprowadzić zadanie do postaci standardowej:

Najpierw układamy funkcję celu.
Naszym celem jest odpowiedź na pytanie: ile upiec pierwszych bulek B1 (x1), ile drugich B2 (x2) a ile trzecich B3 (x3) aby otrzymać maksymalny zysk ?.
Cel dotyczył będzie kosztów - interesuje więc nas ostatni wiersz tabelki.
Przemnażamy nasze niewiadome x1, x2, x3 (ilości bułek) przez ich ceny (ostatni wiersz: 1, 3, 2), które po zsumowaniu mają nam dać jak największą wartość.
1x1 + 3x2 + 2x3    -->    MAX
 

Następnie sporządzamy układ nierówności.
W tym miejscu nałożymy ograniczenia na zużycie podczas wypieku składników do ilości jaka jest dostępna w magazynie piekarni.
Wykorzystamy dane z wnętrza tabelki (pomarańczowa część), które przemnożymy przez szukane niewiadome (x1, x2, x3). Poczym nałożymy ograniczenie, że suma ich nie może być większa niż zapas w magazynie (ostatnia kolumna).

1x1 + 2x2 + 1x3 <= 5
1x1 + 1x2 + 1x3 <= 4
0x1 + 1x2 + 2x3 <= 1

Na koniec nakładamy ograniczenia na rozwiązanie.
Logicznym jest, że nie możemy upiec minus 5 bułek - dlatego zakładamy, że rozwiązanie będzie większe lub równe zero;  x1 >= 0, x2 >= 0, x3 >= 0

Ostatecznie - postać standardowa układu
1x1 + 3x2 + 2x3    -->    MAX

1x1 + 2x2 + 1x3 <= 5
1x1 + 1x2 + 1x3 <= 4
0x1 + 1x2 + 2x3 <= 1

x1 >= 0, x2 >= 0, x3 >= 0

Kolejny krok to doprowadzenie do postaci kanonicznej układu:

W tym kroku pozbywamy się wszystkich nierówności. Zrobimy to poprzez dodanie do naszych nierówności zmiennych swobodnych x4, x5, x6. Zmienne te dodajemy również do funkcji celu - jednak nie wpłyną a one na wartość zysku gdyż dodawane są ze współczynnikiem = 0.

Postać kanoniczna układu
1x1 + 3x2 + 2x3 + 0x4 + 0x5 + 0x6    -->    MAX

1x1 + 2x2 + 1x3 + x4 = 5
1x1 + 1x2 + 1x3 + x5 = 4
0x1 + 1x2 + 2x3 + x6 = 1

x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 0, x6 >= 0

Na koniec doprowadzamy do bazowej postaci kanonicznej układu:

W tym miejscu należy upewnić się, czy każde z równań posiada dodatkową zmienną (oprócz x1, x2, x3) z dodatnim współczynnikiem = 1.
Po czym wstawiamy do każdego równania zmienne występujące w pozostałych równaniach. Dodajemy je ze współczynnikiem = 0, w kolejności od najmniejszego do największego indeksu.

Bazowa postać kanoniczna układu
1x1 + 3x2 + 2x3 + 0x4 + 0x5 + 0x6    -->    MAX

1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 = 5
1x1 + 1x2 + 1x3 + 0x4 + 1x5 + 0x6 = 4
0x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 1

x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 0, x6 >= 0

Teraz możemy przystąpić do tworzenia tabelki metody simpleks

Mając przygotowaną tabelkę bierzemy się za obliczenia

Krok.1.

Ostatni wiersz - wskaźniki optymalności - liczymy odejmując od cen, wiersz drugi od dołu, z wyliczonymi przed chwilą wartościami. Wskaźniki te pozwalają nam określić czy dane rozwiązanie jest rozwiązaniem optymalnym.
Jeżeli wszystkie wskaźniki będą niedodatnie w przypadku maksymalizacji f-kcji celu lub nieujemne dla minimalizacji f-kcji celu wówczas nasze rozwiązanie będzie optymalne.
Ponieważ współczynniki optymalności mają wartości dodatnie - rozwiązanie nie jest optymalne.

...