Algorytm Simplex

Zagadnienia przedstawione w notatce zawierają: omówienie algorytmu, przykładowe zadania i zastosowanie, obliczenia i wzory.

Notatka zawiera wzory z objaśnieniami.

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: M1, M2, M3. Maszyna M1 może być zatrudniona przez 24000 sekund, maszyna M2 przez 40000 sekund i maszyna M3 przez 27000 sekund. 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.
Maszyny
Ilość pracy (w sek.) na jednostkę produktu
Maksymalny łączny czas pracy maszyn (w sek.)
A
B
M1
M2
M3
3
8
9
6
4
3
24000
40000
27000
Model zagadnienia jest następujący:
3XA + 6XB ≤ 24 000 (1)
8XA + 4XB ≤ 40 000 (2)
9XA + 3XB ≤ 27 000 (3)
Z = 9XA + 6XB (maksimum) (4)
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.
3XA + 6XB + S1= 24 000 (1`)
8XA + 4XB + S2= 40 000 (2`)
9XA + 3XB + S3= 27 000 (3`)
gdzie S1, S2, S3 to, tzw. zmienne swobodne. Mając powyższy system równości (1`), (2`), (3`) przystępuje się do budowy tablicy SIMPLEX.
Tabl. 1
S1
S2
S3
XA
XB
:3=8000
:8=5000
:9=3000
S1
1
0
0
3
6
24 000
S2
0
1
0
8
4
40 000
S3
0
0
1
9
3
27 000
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 S1 itd. Czytając kolumnami, trzeba pamiętać, że S

(…)

… drugiemu odpowiada pkt R
Rozwiązaniu ostatecznemu pkt S
Ogólnie wyznaczanie optymalnego rozwiązania zadania programowania liniowego za pomocą metody SIMPLEX ma następujące etapy:
Wyznaczanie wyjściowego bazowego dopuszczalnego rozwiązania programu
Sprawdzenie, czy dane rozwiązanie bazowe jest rozwiązaniem optymalnym, czy też nie. Jeśli dane rozwiązanie jest optymalne, to postępowanie kończy…
... zobacz całą notatkę