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

1

, M

2

, M

3

. Maszyna M

1

może być

zatrudniona przez 24000 sekund, maszyna M

2

przez

40000 sekund i maszyna M

3

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

M

1

M

2

M

3

3
8
9

6
4
3

24000
40000
27000

Model zagadnienia jest następujący:

3X

A

+ 6X

B

≤ 24 000

(1)

8X

A

+ 4X

B

≤ 40 000

(2)

9X

A

+ 3X

B

≤ 27 000

(3)

Z = 9X

A

+ 6X

B

(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.

3X

A

+ 6X

B

+ S

1

= 24 000

(1`)

8X

A

+ 4X

B

+ S

2

= 40 000

(2`)

9X

A

+ 3X

B

+ S

3

= 27 000

(3`)

gdzie S

1

, S

2

, S

3

to, tzw. zmienne swobodne. Mając

powyższy system równości (1`), (2`), (3`) przystępuje
się do budowy tablicy SIMPLEX.

Tabl. 1

S

1

S

2

S

3

X

A

X

B

:3=8000
:8=5000
:9=3000

S

1

1

0

0

3

6

24 000

S

2

0

1

0

8

4

40 000

S

3

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 S

1

itd.

Czytając kolumnami, trzeba pamiętać, że S

1

, S

2

i S

3

oznaczają nie wykorzystane zdolności produkcyjne
maszyn M

1

, M

2

, M

3

można przeczytać kolumnę np.

„X

B

” w sposób następujący: dla otrzymania jednej

jednostki X

B

należy użyć 6 jednostek nie wykorzystanej

zdolności produkcyjnej maszyny M

1

, 4 jednostki – nie

wykorzystanej zdolności – produkcji maszyny M

2

i 3

jednostki nie wykorzystanej zdolności produkcyjnej
maszyny M

3

. Kolumna X

B

może być interpretowana

jako relacja: X

B

= 6S

1

+ 4S

2

+ 3S

3

itd.

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

1

= 24 000 ; S

2

= 40 000 ; S

3

= 27 000

http://notatek.pl/algorytm-simplex?notatek