Algorytm simpleks

Algorytm simpleks jest uniwersalna metodą rozwiązywania programów liniowych.
Istota tego algorytmu polega na badaniu kolejnych rozwiązań bazowych (rozwiązań dopuszczalnych) programu liniowego w postaci kanonicznej w taki sposób, że :

a) znajdujemy (dowolne) rozwiązanie bazowe programu;
b) sprawdzamy, czy jest ono optymalne;
c) jeżeli dane rozwiązanie nie jest optymalne, konstruujemy następne rozwiązania bazowe lepsze (lub przynajmniej nie gorsze od poprzedniego).

Postępowanie kończy się w momencie stwierdzenia, że aktualne rozwiązanie bazowe jest optymalne, tzn. nie można już go poprawić.
Algorytm simpleks jest więc procedurą iteracyjna (etapową),a wyniki poszczególnych etapów zestawia się w kolejnych tablicach simpleks.

Pierwszym krokiem jest przekształcenie równań w postać macierzową

c₁x₁+c₂x₂+…+c_nx_n ≤ max

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁

a_mx₁+a_mx₂+…+a_mnx_n ≤ b_m

Przy czym, c₁, c₂ to współczynniki zysku przy każdym produkcie.

.

Macierz A, oznacza produkty. A jest macierzą współczynników warunków ograniczających

Macierz x, która oznacza zmienne

decyzyjne.

Macierz B oznacza maksymalne ograniczenie. Jest wektorem wyrazów wolnych warunków ograniczających.

Funkcja C, czyli funkcja celu, oznacza zysk. Zdefiniowane po wprowadzeniu zmiennych bilansujących.

Zmienne bilansujące:

cb	xb	A I	b
	zj	0
		Cj-zj		c

x_b - wektor zmiennych bazowych

c_b - wektor kolumnowy współczynników funkcji celu dla zmiennych bazowych.

I - macierz jednostkowa o wymiarach m x n

z_j - wiersz zerowy:

Plan produkcji wygląda następująco:

	P1	P2	ZASOBY
S1	5	4	22
S2	5	6	45
S3	3	7	33
ZYSK	3	4

NAJPIERW WYZNACZAMY FUNKCJĘ CELU

3x₁ + 4x₂ + 0x₄ + 0x₅ + 0x₆   --> MAX

W przypadku, gdy funkcja celu jest maksymalna - rozwiązanie dotąd nie będzie optymalne, dopóki w wierszu zerowym będą występować liczby nieujemne.

- kolejny krok to doprowadzenie do postaci kanonicznej układu:

5x₁ + 4x₂+x₃= 22

5x₁ +6x₂+x₄ = 45

5x₁ + 7x₂+x₅ =33

x₁ >= 0, x₂ >= 0, x₃ >= 0, x₄ >= 0, x₅ >= 0,

- układ doprowadzamy do bazowej postaci kanonicznej

5x₁ + 4x₂ + 1x₃ + 0x₄ + 0x₅ = 22
5x₁ + 6x₂ + 0x₃ + 1x₄ + 0x₅ = 45
5x₁ + 7x₂ + 0x₃ + 0x₄ + 1x₅ = 33

W moim przypadku macierze potrzebne do obliczeń będą wyglądać w sposób następujący:

; ; ;

- przystępujemy do tworzenia tabeli metody simpleks

Cx->max		3	4	0	0	0	b
Baza	Cb	x1	x2	x3	x4	x5
x3	0	5	4	1	0	0	22
x4	0	5	6	0	1	0	45
x5	0	5	7	0	0	1	33
Zj
Cj -Zj

- wyliczamy wskaźniki optymalności

*korzystamy ze wzorów; Z_j=∑Cb*a_ij ; Fc=∑ Cb*b

Cx->max		3	4	0	0	0	b
Baza	Cb	x1	x2	x3	x4	x5
x3	0	5	4	1	0	0	22
x4	0	5	6	0	1	0	45
x5	0	5	7	0	0	1	33
Zj		0*5+0*5+0*5=0	0*4+0*6+0*7=0	0*1+0*0+0*0=0	0*0+0*1+0*0=0	0*0+0*0+0*1=0	22*0+45*0+33*0=0
Cj -Zj		3-0=3	4-0=4	0-0=0	0-0=0	0-0=0

-pierwsza tablica simpleksowa

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

↓

* dlatego też następnym krokiem jest znalezienie kryterium wejściowego i wyjściowego;

Kryterium optymalności dla zadania maksymalizacji:

Jeżeli wartość wszystkich składników optymalności cj - zj jest niedodatnia, to rozpatrywane rozwiązanie jest optymalne. Jeżeli choć jeden ze wskaźników optymalności cj - zj jest dodatni, to istnieje możliwość poprawy tego rozwiązania.

Kryterium wejścia:

Wybieramy największą wartość wskaźnika optymalności cj - zj. Odpowiadającą mu zmienną wprowadzamy do nowej bazy. Jeżeli największa wartość wskaźnika optymalności odpowiada więcej niż jedna zmienna, to do nowej bazy wprowadzamy zmienną o niższym numerze.

Kryterium wyjścia:

Obliczamy iloraz kolejnych wyrazów wolnych przez odpowiadające im elementy kolumny wchodzącej do bazy dla tych elementów kolumny wprowadzonej do bazy, które są dodatnie. Bazę opuszcza ta zmienna, dla której odpowiadający jej iloraz jest najmniejszy. Jeżeli minimum jest przyjmowane przez więcej niż jeden raz, to jako zmienną opuszczającą bazę wybieramy zmienną o najniższym numerze.

- maksymalizujemy f-kcję celu więc szukamy maksymalnego wskaźnika optymalności (kryterium wejścia),poczym zaznaczamy całą kolumnę, w której znaleźliśmy max. wskaźnik.

↓

W naszym przypadku jest to wartość = 4

Cx->max		3	4	0	0	0	b
Baza	Cb	x1	x2	x3	x4	x5
x3	0	5	4	1	0	0	22
x4	0	5	6	0	1	0	45
x5	0	5	7	0	0	1	33
Zj		0	0	0	0	0	0
Cj -Zj		3	4	0	0	0

↓

MAX.

kryterium wejścia

-następnie wyliczamy kryteria wyjścia (ostatnia, szara kolumna) ,

Cx->max		3	4	0	0	0	b
Baza	Cb	x1	x2	x3	x4	x5
x3	0	5	4	1	0	0	22	22/4=5,5
x4	0	5	6	0	1	0	45	45/6=7,5
x5	0	5	7	0	0	1	33	33/7=4,7
Zj		0	0	0	0	0	0
Cj -Zj		3	4	0	0	0

↓

MAX.

kryterium wejścia

-teraz szukamy najmniejszej wartości w ostatniej kolumnie (szarej-kryterium wyjścia),poczym zaznaczamy całą kolumnę, w której znaleźliśmy najmniejszy wskaźnik. ;

Cx->max		3	4	0	0	0	b
Baza	Cb	x1	x2	x3	x4	x5
x3	0	5	4	1	0	0	22	22/4=5,5
x4	0	5	6	0	1	0	45	45/6=7,5
x5	0	5	7	0	0	1	33	33/7=4,7

↓

Kryterium wyjścia

MIN.

Zj	0	0	0	0	0	0
Cj -Zj	3	4	0	0	0

↓

Max.kryterium wejścia

-wymieniamy jedną zmienną bazową (kolumna żółta) znajdującą się w zaznaczonym wierszu (jest nią x₅ ) na zmienną niebazową ,znajdującą się w zaznaczonej kolumnie (jest nią x₂ ). Wraz ze zmienną przenosimy odpowiadający jej współczynnik z f-kcji celu ;

.

Bazę opuszcza wg kryterium x₅(korzystam z kryterium wejścia i wyjścia).Do bazy wchodzi x₂.

Tablica simpleksowa wygląda wówczas tak ;

Cx -> max		3	4	0	0	0	b
baza	Cb	x1	x2	x3	x4	x5
x3	0	3,285714	0	1	0	-0,57143	3,142857	0,956522
x4	0	2,428571	0	0	1	-0,85714	16,71429	6,882353
x2	4	0,428571	1	0	0	0,142857	4,714286	11
Zj		1,714286	4	0	0	0,571429	18,85714
C-Zj		1,285714	0	0	0	-0,57143

-druga tablica simpleksowa

W dalszym ciągu nie uzyskaliśmy rozwiązania optymalnego.

Przechodzimy do następnej bazy.

Bazę opuszcza x₃. Do bazy wchodzi x₁.

Cx -> max		3	4	0	0	0	b
baza	Cb	x1	x2	x3	x4	x5
x3	3	1	0	0,304348	0	-0,17391	0,956522
x4	0	0	0	-0,73913	1	-0,43478	14,3913
x2	4	0	1	-0,13043	0	0,217391	4,304348
Zj		3	4	0,391304	0	0,347826	20,08696
C-Zj		0	0	-0,3913	0	-0,34783

-trzecia tablica simpleksowa

Ponieważ w wierszu zerowym nie występują już liczby dodatnie (cj - zj), więc rozwiązanie jest optymalne.

Optymalne rozwiązanie:
	x1	0,956522
xb=	x4	14,3913
	x2	4,304348