To tylko jedna z 11 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Metoda simpleks Przykładowe zadanie 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 dag mąki, 1 dag cukru. Na wypiek bułki drugiej (B2) potrzeba 2 dag mąki, 1 dag cukru i 1 dag rodzynek. Bułka trzecia (B3) wymaga 1 dag mąki, 1 dag cukru i 2 dag rodzynek. Przy czym w magazynie piekarni dostępne jest tylko 5 dag mąki, 4 dag cukru i 1 dag 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. Na początek trzeba prawidłowo wypełnić tabelkę z danymi (Tabelka.1.)
Tabelka.1. Dane do zadania
Następnie należy doprowadzić zadanie do postaci standardowej:
Mając prawidłowo zestawioną tabelkę nie ma najmniejszego problemu z ułożeniem układu w 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ęna 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 oznaczona na niebiesko).
1x1 + 2x2 + 1x3 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 = 0, x2 = 0, x3 = 0 Kolejny krok to doprowadzenie do postaci kanonicznej układu:
W tym kroku pozbywamy sie 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.
... zobacz całą notatkę
Komentarze użytkowników (0)