Algorytm simpleks

Metoda algorytmu simpleks polega na budowaniu kolejnych rozwiązań bazowych. W pierwszej kolejności znajdujemy (dowolne) rozwiązanie bazowe programu. Sprawdzamy, czy jest ono optymalne. Jeżeli jednak okaże się być nieoptymalne znajdujemy następne rozwiązanie bazowe, które będzie lepsze. Procedurę kończymy wtedy, gdy nasze rozwiązanie jest optymalne.

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. Jest macierzą współczynników występujących po lewej stronie warunków ograniczających.

A=

Macierz x, która oznacza zmienne decyzyjne.

X=

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

B=

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

C=

Warunki:

c_x → max

a_x ≤ b

x ≥0

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

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. Liczby dodatnie zwiększają wartość celu.

Plan produkcji wygląda następująco:

	P1	P2	Zasoby
S1	12	15	44
S2	11	12	25
S3	14	3	26
Zysk	20	15

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

C=

B=

X=

I=

A=

Zakładamy, że x₁ i x₂ są równe 0. Wówczas otrzymujemy wartości:

x₃=b₁=44

x₄=b₂=25

x₃=b₃=26

Wiersz zerowy:

zj= ∑aij*cij

Plan produkcji:

*	P1	P2	Zasoby
S1	12	15	44
S2	11	12	25
S3	14	3	26
Zysk	20	15

Muszę doprowadzić do takiej postaci:

	zmienne bazowe	C		rozwiązanie
cbl	xbl	Bb^-1A	Bb^-1	Bb^-1b
	zj	Cb^TBbA	Cb^TBb^-1	Cb^TBb^-1b
	cj-zj	C-Cb^TBb^-1A	Cb^TBb-1

Korzystam z kryterium optymalności, wejścia i wyjścia.

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.

Macierz jednostkowa:

X3	X4	X5
1	0	0
0	1	0
0	0	1

Pierwsza postać bazowa:

Cx → max		20	15	0	0	0	b
baza	cb	X1	X2	X3	X4	X5
x3	0	12	15	1	0	0	44	3,666667
x4	0	11	12	0	1	0	25	2,272727
x5	0	14	3	0	0	1	26	1,857143
Zj		0	0	0	0	0
Cj - Zj		20	15	0	0	0

Kursywą zaznaczone są wyniki ilorazu.

Korzystam z kryterium wejścia i wyjścia.

Bazę opuszcza wg kryterium x₅. Do bazy wchodzi x₁.

Tablica simpleksowa wygląda wówczas tak:

Cx -> max		20	15	0	0	0	b
baza	cb	X1	X2	X3	X4	X5
x3	20	0	12,42857	1	0	-0,85714	21,71429
x4	0	0	9,642857	0	1	-0,78571	4,571429
x1	0	1	0,214286	0	0	0,071429	1,857143
Zj		0	248,5714	20	0	-17,1429
Cj - Zj		20	-233,571	-20	0	17,14286	434,2857

Nie jest to rozwiązanie optymalne.

Dlatego musimy przejść do następnej bazy.

Bazę opuszcza wg kryterium x₄. Do bazy wchodzi x₁.

Tablica simpleksowa wygląda wówczas w następujący sposób:

Cx -> max		20	15	0	0	0	b
baza	cb	X1	X2	X3	X4	X5
x3	20	0	1,909091	1	-1,09091	0	16,72727
x1	0	1	1,090909	0	0,090909	0	2,272727
x5	0	0	-12,2727	0	-1,27273	1	-5,81818
Zj		0	188,8017	20	-21,8182	0
Cj - Zj		20	-173,802	-20	21,81818	0	334,5455

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

Przechodzimy do następnej bazy.

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

Tablica wygląda następująco.

Cx -> max		20	15	0	0	0	b
baza	cb	X1	X2	X3	X4	X5
x3	20	1	1,25	0,083333	0	0	3,666667
x1	0	0	-1,75	-0,91667	1	0	-15,3333
x5	0	0	-14,5	-1,16667	0	1	-25,3333
Zj		20	235,25	1,666667	0	0
Cj - Zj		0	-220,25	-1,66667	0	0	73,33333

Według kryterium optymalności otrzymany wynik jest optymalny, czyli taki, którego poszukiwaliśmy.

Zagadnienia dualne

Postać klasyczna:

*	P1	P2	Zasoby
S1	12	15	44
S2	11	12	25
S3	14	3	26
Zysk	20	15

Ogólna wartość posiadanych surowców:

44y₁+25y₂+26y₃

Wartość surowców potrzebna do wytworzenia produktu:

P1: 12y₁+11y₂+14y₃

P2: 15y₁+12y₂+3y₃

Zadanie minimalizacji wartości zastosowanych surowców do produkcji P1 i P2:

44y₁+25y₂+26y₃ → min

12y₁+11y₂+14y₃ ≥ 20

15y₁+12y₂+3y₃ ≥ 15

y₁, y₂, y₃ ≥ 0

Zmienne decyzyjne:

y=

y b → min

y A ≥ c

y ≥ 0

Rozwiązując zadanie metodą dualną korzystam z podstawowych twierdzeń o dualności:

cx ≤ yb (wartości funkcji celu)

y(b-Ax) = 0 (związek 1)

x(yA-c) = 0 (związek 2)

cx = yb

Związek 1

y(b-Ax)=
*
=

=y1(44-12x1-15x2)+y2(25-11x1-12x2)+y3(26-14x1-3x2)

Związek 2

Y1=0, ponieważ spełniany jest jako nierówność ostra.

Jeżeli x1 i x2 sa dodatnie, wtedy

12y₁+11y₂+14y₃ = 20

15y₁+12y₂+3y₃₌15

---