Metoda Simpleks

Kroki jakie należy wykonać w metodzie simpleks:

  1. Doprowadzenie zadania do postaci standardowej
  2. Doprowadzenie zadania do postaci kanonicznej
  3. Doprowadzenie zadania do bazowej postaci kanonicznej
  4. Przygotowanie tabeli simpleks
  5. Wyliczenie wskaźników optymalności
  6. Sprawdzenie optymalności rozwiązania

Jeżeli rozwiązanie nie jest optymalne:

7.Zamiana zmiennej bazowej wyjściowej na zmienną nie bazową wejściową
8. Zaktualizowanie tabeli wg nowej bazy
9. Powrót do kroku 5

Zadanie nr.1

Piekarnia wypieka 3 rodzaje produktów P1, P2, P3, które odpowiednio kosztują 1, 3 i 2 złote.
Do produkcji pierwszego P1 potrzeba 1 dkg mąki, 1 dkg cukru.
Na wypiek drugiego P2 potrzeba 2 dkg mąki, 1 dkg cukru i 1 dkg słonecznika.
Trzeci produkt P3 wymaga 1 dkg mąki, 1 dkg cukru i 2 dkg słonecznika.
W magazynie piekarni dostępne jest tylko 5 dkg mąki, 4 dkg cukru i 1 dkg słonecznika.
Ustalić rozmiary produkcji produktów P1, P2, P3, które gwarantują maksymalny przychód z ich sprzedaży przy istniejących zapasach składników.

Tabela do zadania

Zużycie surowca (dkg)
na 1 szt. produktu
Zapas w magazynie
(dkg)
P1 P2 P3
mąka
cukier
słonecznik
1
1
0
2
1
1
1
1
2
5
4
1
Cena (zł) 1 3 2 max

Krok 1 - postać standardowa układu

Funkcja celu

Celem jest uzyskanie odpowiedzi na pytanie:
Ile upiec produktów P1, P2, P3 aby otrzymać maksymalny zysk ?
Funkcja celu będzie wyglądała następująco:

1x1 + 3x2 + 2x3 --> MAX

x1 - wielkość produkcji produktu P1
x2 - wielkość produkcji produktu P2
x3 - wielkość produkcji produktu P3

Układ nierówności

Należy nałożyć ograniczenia na zużycie składników podczas wypieku uwzględniając zapasy w magazynie.

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

Postać standardowa układu

Należy założyć, że rozwiązanie będzie większe lub równe zero.
Ostateczna postać układu będzie następująca:

1x1 + 3x2 + 2x3 --> MAX

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

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

Krok 2 - postać kanoniczna układu

Aby sprowadzić zadanie do postaci kanonicznej należy dodać do lewych stron nierówności zmienne swobodne x4, x5, x6. Zmienne te również zostaną dodane do funkcji celu ale ze współczynnikiem zero dlatego nie mają wpływu na wartość zysku.

Postać kanoniczna:

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

Krok 3 - bazowa postać kanoniczna układu

Na początku należy sprawdzić czy każde z równań posiada dodatkową zmienną z dodatnim współczynnikiem. Następnie do każdego równania zostają wstawione zmienne z pozostałych równań.

Bazowa postać kanoniczna układu:

1x1 + 3x2 + 2x3 + 0x4 + 0x5 + 0x6 --> MAX

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

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

Krok 4 - przygotowanie tabeli simpleks

Najpierw następuje uzupełnienie wartościami które są znane:

cb cj 1 3 2 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
0
0
0
x4
x5
x6
1
1
0
2
1
1
1
1
2
1
0
0
0
1
0
0
0
1
5
4
1
zj
cj - zj

cb - współczynniki przy zmiennych bazowych w funkcji celu.
cj - współczynniki przy zmiennych w funkcji celu.
bi - wartości zmiennych bazowych.
zj - wskaźniki pomocnicze.
cj - zj - wskaźniki optymalności (kryterium simpleks).

Krok 5 - wyliczenie wskaźników optymalności

Obliczenie wskaźników pomocniczych oraz optymalności:

cb cj 1 3 2 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
0
0
0
x4
x5
x6
1
1
0
2
1
1
1
1
2
1
0
0
0
1
0
0
0
1
5
4
1
zj 0 0 0 0 0 0 0
cj - zj 1 3 2 0 0 0

Elementy zj to iloczyn skalarny wartości cb oraz kolejnych wartości współczynników.

Ostatni element w wierszu zj nazywany jest wartością funkcji celu w bieżącym rozwiązaniu.

Krok 6 - sprawdzenie optymalności rozwiązania

Ponieważ współczynniki optymalności mają wartości dodatnie - rozwiązanie nie jest optymalne.

Krok 7 - zamiana zmiennej bazowej wyjściowej na zmienną nie bazową wejściową

Funkcja celu jest maksymalizowana, dlatego do kolejnego rozwiązania bazowego wejdzie zmienna o największej wartości kryterium simpleks (czyli największa wartość w wierszu ze wskaźnikami optymalności). Dla obliczanego przypadku jest to zmienna x2. Należy teraz ustalić w miejsce z której dotychczasowych zmiennych bazowych zostanie wprowadzona. W tym celu wartości bi należy podzielić przez współczynniki stojące przy wprowadzanej zmiennej w aktualnej tablicy simpleksowej i wybrać tą, dla której ten iloraz jest najmniejszy:

Ilorazy:

Najmniejszy iloraz odpowiada zmiennej x6.

Następnym krokiem jest stworzenie drugiej tablicy simpleksowej. Z pierwszej tabeli wymieniamy zmienną bazową znajdującą się w zaznaczonym wierszu (x6) na zmienną nie bazową znajdującą się w zaznaczonej kolumnie (x2). Wraz ze zmienną przenosimy odpowiadający jej współczynnik z funkcji celu.

cb cj 1 3 2 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
0
0
3
x4
x5
x2
1
1
0
2
1
1
1
1
2
1
0
0
0
1
0
0
0
1
5
4
1
zj
cj - zj

Krok 8 - zaktualizowanie tabeli wg nowej bazy

Następnym krokiem jest aktualizacja wartości w wierszach tablicy.

Etap 1
Aktualizacje zaczynamy od wiersza w którym znalezione zostało kryterium simpleksu. Nowe wartości są ilorazem wartości z kolejnej komórki tego wiersza przez wartość z komórki znajdującej się na przecięciu wiersza i kolumny ze znalezionym kryterium simpleksu.

Etap 2
Teraz następuje aktualizacja wierszy powyżej wiersza w którym znalezione zostało kryterium simpleksu. Zwrócona wartość to różnica kolejnej komórki tego wiersza i iloczynu wartości znajdującej się na przecięciu tego wiersza i kolumny, w której znalezione zostało kryterium simpleksu oraz wartości obliczonych w etapie 1.

Etap 3
Dokonywana jest aktualizacja wiersza powyżej, zgodnie z takimi samymi zasadami jak w etapie 2.

Etap 4
Wyliczenie wskaźników pomocniczych.

Etap 4
Wyliczenie wskaźników optymalności.

cb cj 1 3 2 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
0
0
3
x4
x5
x2
1
1
0
0
0
1
-3
-1
2
1
0
0
0
1
0
-2
-1
1
3
3
1
zj 0 3 6 0 0 3 3
cj - zj 1 0 -4 0 0 -3

Ponieważ współczynniki optymalności mają wartości dodatnie - rozwiązanie dalej nie jest optymalne.
Nowa tabela simpleksowa:

cb cj 1 3 2 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
1
0
3
x1
x5
x2
1
0
0
0
0
1
-3
2
2
1
-1
0
0
1
0
-2
1
1
3
0
1
zj 1 3 3 1 0 1 6
cj - zj 0 0 -1 -1 0 -1

Żaden współczynnik nie jest dodatni - wynika stąd, że znalazło się rozwiązanie optymalne.

Rozwiązanie:
x1 = 3
x5 = 0
x2 = 1

Reszta zmiennych równa jest zero.
x3 = 0
x4 = 0
x6 = 0
Uzyskany zysk równy jest 6.
Przy nałożonych ograniczeniach składników aby otrzymać maksymalny zysk należy upiec:
3 produkty P1 i 1 produkt P2.

Zadanie nr.2

Przedsiębiorstwo produkuje dwa rodzaje produktów P1 i P2. Zysk ze sprzedaży jednej tony produktu P1 wynosi 1000 złotych, a z jednej tony produktu P2 2000 złotych. Do produkcji są wykorzystywane dwa surowce: S1 i S2, których ilość dostępna w ciągu jednej doby wynosi odpowiednio 8 ton i 3 tony. Ilości surowców (w tonach) wykorzystywane do produkcji jednej tony produktu P1 i jednej tony produktu P2 zamieszczono w tabeli poniżej.

Tabela do zadania

Zużycie surowca na
jedną tonę produktu
Dostępne zapasy
(tony)
P1 P2
S1
S2
2
0
2
1
8
3
Cena (zł) 1000 2000 max

Przedstaw zadanie w postaci klasycznej oraz zoptymalizuj funkcję celu maksymalizującą zysk z produkcji.

Tabela końcowa:

cb cj 1 3 2 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4
1000
2000
x1
x2
1
0
0
1
0.5
0
-1
1
1
3
zj 1000 2000 500 1000 7000
cj - zj 0 0 -500 -1000

Zadanie nr.3

Sprowadź poniższe problemy programowania liniowego do postaci standardowej i zmaksymalizuj

x1 + 2x2 − 3x3

przy warunkach:

x1 − x2 + x3 ≤ 3

x1 − x3 ≥ 2

x1 + x2 − 2x3 = 4

xi ≥ 0 (i = 1, 2, 3)

Tabela końcowa:

cb cj 1 2 -3 0 0 -M -M Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6 x7
0
1
2
x4
x1
x2
0
1
0
0
0
1
1
-1
-1
1
0
0
2
-1
1
-2
1
-1
1
0
1
3
2
2
zj 1 2 -3 0 1 -1 2 6
cj - zj 0 0 0 0 -1 -M+1 -M-2

Zadanie nr.4

Sprowadź poniższe problemy programowania liniowego do postaci standardowej i zmaksymalizuj

60x1 + 30x2 + 20x3

przy warunkach:

8x1 + 6x2 + x3 ≤ 960

8x1 + 4x2 + 3x3 ≤ 800

4x1 + 3x2 + x3 ≤ 320

xi ≥ 0 (i = 1, 2, 3)

Tabela końcowa:

cb cj 60 30 20 0 0 0 Rozwiązanie (bi)
Zmienne bazowe x1 x2 x3 x4 x5 x6
0
20
60
x4
x3
x1
0
0
1
-2
-2
1.25
0
1
0
1
0
0
1
1
-0.25
-4
-2
0.75
480
160
40
zj 60 35 20 0 5 5 5600
cj - zj 0 -5 0 0 -5 -5