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