Algorytm SIMPLEX
Uniwersalnym algorytmem do rozwiązywania
problemów liniowych jest tzw. algorytm SIMPLEX. ,
Idea algorytmu SIMPLEX polega na tym, że za punkt
wyjścia przyjmuje się pewne rozwiązanie modelu, o
którym wiadomo, że jest dopuszczalne. Następnie w
kolejnych etapach rozwiązania to poprawiamy, aż po
pewnej skończonej liczby etapów otrzymujemy
rozwiązanie optymalne.
Przykład 1
Zakład przemysłowy wytwarza dwa produkty:
A i B. Do ich produkcji potrzebna jest praca trzech
maszyn: M , M , M . Maszyna M może być
1 2 3 1
zatrudniona przez 24000 sekund, maszyna M przez
2
40000 sekund i maszyna M przez 27000 sekund.
3
Znane są również czasy pracy poszczególnych
maszyn potrzebne do wytwarzania jednostki
produktu A i produktu B. Podaje to tablica 0. Zysk
na jednostce A wynosi 9 gr. I na jednostce B 6 gr.
W jakich rozmiarach wytwarzać produkty A i B,
aby osiągnąć największy łączny zysk.
Ilość pracy (w sek.) na Maksymalny
jednostkę produktu łączny czas
Maszyny pracy
A B maszyn
(w sek.)
M 3 6 24000
1
M 8 4 40000
2
M 9 3 27000
3
Model zagadnienia jest następujący:
3X + 6X d" 24 000 (1)
A B
8X + 4X d" 40 000 (2)
A B
9X + 3X d" 27 000 (3)
A B
Z = 9X + 6X (maksimum) (4)
A B
Nie będziemy już zapisywać warunków orzekających,
że zmienne decyzyjne muszą przyjmować wartości
nieujemne. Trzeba jednak pamiętać, że warunki te
zawsze muszą być spełnione. Technika rachunkowa
algorytmu SIMPLEX wymaga, aby wszystkie relacje
modelu przekształcić na równania i z lewej strony 
umieścić zmienne decyzyjne (niewiadome), z prawej
strony  nieujemne wyrazy wolne.
3X + 6X + S = 24 000 (1`)
A B 1
8X + 4X + S = 40 000 (2`)
A B 2
9X + 3X + S = 27 000 (3`)
A B 3
gdzie S , S , S to, tzw. zmienne swobodne. Mając
1 2 3
powyższy system równości (1`), (2`), (3`) przystępuje
się do budowy tablicy SIMPLEX.
Tabl. 1
S S S X X
1 2 3 A B
S 1 0 0 3 6 24 000 :3=8000
1
:8=5000
S 0 1 0 8 4 40 000
2
http://notatek.pl/algorytm-simplex?notatek
:9=3000
S 0 0 1 9 3 27 000
3
Tablica składa się z pewnej ilości kolumn,
odpowiadającej łącznej ilości zmiennych swobodnych i
zmiennych decyzyjnych. Ilość wierszy odpowiada ilości
zmiennych swobodnych. Tablicę można czytać
dwojako: wierszami lub kolumnami. Pierwszy wiersz
podaje współczynniki równania (1`), tj. równania, w
którym występuje pierwsza zmienna swobodna S itd.
1
Czytając kolumnami, trzeba pamiętać, że S , S i S
1 2 3
oznaczają nie wykorzystane zdolności produkcyjne
maszyn M , M , M można przeczytać kolumnę np.
1 2 3
 X  w sposób następujący: dla otrzymania jednej
B
jednostki X należy użyć 6 jednostek nie wykorzystanej
B
zdolności produkcyjnej maszyny M , 4 jednostki  nie
1
wykorzystanej zdolności  produkcji maszyny M i 3
2
jednostki nie wykorzystanej zdolności produkcyjnej
maszyny M . Kolumna X może być interpretowana
3 B
jako relacja: X = 6S + 4S + 3S itd.
B 1 2 3
W algorytmie SIMPLEX, jako rozwiązanie początkowe,
z reguły przyjmuje się takie rozwiązanie, któremu
odpowiadają wartości zerowe wszystkich zmiennych
decyzyjnych, tzn. jako rozwiązanie dopuszczalne,
któremu odpowiadają następujące wartości zmiennych
swobodnych:
S = 24 000 ; S = 40 000 ; S = 27 000
1 2 3