TECHNIKA OPTYMALIZACJI laboratorium
Ćwiczenie II: Dwufazowa metoda simpleks
Grupa:

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się metodą rozwiązywania liniowego zadania optymalizacji na przykładzie dwufazowej metody simpleks zwanej też metodą simpleks.

Metoda dwufazowego simpleksu pozwala na wyliczenie takiego wektora zmiennych decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X, dla którego funkcja celu osiąga maksimum (minimum): f(x) = x_o = c^Tx → max(min)

przy ograniczeniach: X = {x  : A₁ • x ≥ b₁;  x ≥ 0;  A₂ • x ≤ b₂}

dim x= nx1, dim c=nx1, dim A₁=m₁xn, dim A₂=m₂xn, dim b₁ = m₁x1, dim b₂ = m₂x1

Macierz A₁ jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m₁ ograniczeniach większościowych, a macierz A₂ jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m₂ ograniczeniach mniejszościowych. Wektory b₁,  b₂ nazywane są wektorami wyrazów wolnych w ograniczeniach i powinny przyjmować wartości nieujemne.

1. Przebieg ćwiczenia

   1. Przykład I – X≠Ø, istnieje optymalne rozwiązanie

minx₀=−x₁ + 2x₂

$$X:\ \left\{ \begin{matrix} 3x_{1} - 2x_{2} \geq 1 \\ x_{1} + 2x_{2} \leq 5 \\ \end{matrix} \right.\ ,\ x \geq 0$$

Rozwiązanie i kod z Matlaba:

f=[-1;2];

A=[-3 2;1 2];

b=[-1;5];

lb=[0;0];

options = optimset('largescale','off','simplex','on');

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb,[],[],options)

x = 5 0	fval = -5	exitflag = 1	output = iterations: 1 message: 'Optimization terminated.'

Interpretacja graficzna:

Rozwiązanie za pomocą tablicowej metody simpleks:

Tablica 1 (faza I):

	b	x1	x2
x0	0	-1	2
x3	-1	-3	2
x4	5	1	2

Tworzenie tablicy 2:

	b	X3	X2
x0	$$0 - \frac{- 1*( - 1)}{- 3}$$	$$\frac{- 1}{- 3}$$	$$2 - \frac{2*( - 1)}{- 3}$$
X1	$$\frac{- 1}{- 3}$$	$$\frac{1}{- 3}$$	$$- \frac{- 5}{6}$$
x4	$$5 - \frac{- 1*1}{- 3}$$	$$\frac{1}{- 3}$$	$$2 - \frac{2*1}{- 3}$$

Tablica 2 (faza II):

	b	x3	x2
x0	$$\frac{1}{3}$$	$$- \frac{1}{3}$$	$$1\frac{1}{3}$$
x1	$$\frac{1}{3}$$	$$- \frac{1}{3}$$	$$- \frac{2}{3}$$
x4	$$4\frac{2}{3}$$	$$\frac{1}{3}$$	$$2\frac{2}{3}$$

Tworzenie tablicy 3:

	b	x4	x2
x0	$$\frac{1}{3} - \left\lbrack 3*4\frac{2}{3}*\left( - \frac{1}{3} \right) \right\rbrack$$	$$- \left( - \frac{1}{3} \right)*3$$	$$1\frac{1}{3} - \left\lbrack 3*2\frac{2}{3}*\left( - \frac{1}{3} \right) \right\rbrack$$
x1	$$\frac{1}{3} - \left\lbrack 3*4\frac{2}{3}*\left( - \frac{1}{3} \right) \right\rbrack$$	$$- \left( - \frac{1}{3} \right)*3$$	$$- \frac{2}{3} - \left\lbrack 3*2\frac{2}{3}*\left( - \frac{1}{3} \right) \right\rbrack$$
x3	$$4\frac{2}{3}*3$$	3	$$2\frac{2}{3}*3$$

Tablica 3 (faza II):

	b	x4	x2
x0	5	1	4
x1	5	1	2
x3	14	3	8

W wierszu x0 wystepują wartości nieujemne.

Istnieje jedno rozwiązanie optymalne: min(x0) = -5, x1 = 5, x2 = 0.

Rozwiązanie jest zgodne z wyliczonym za pomocą Matlaba.

Ilość iteracji nie zgadza się z liczbą tablic, ponieważ Matlab rozpoczyna numerację od „0” i tylko dla fazy II.

1. Przykład II – X=Ø, zadanie nie ma rozwiązania

minx₀ = 4x₁ + 2x₂

$$X:\ \left\{ \begin{matrix} - 3x_{1} + 2x_{2} \leq 1 \\ - x_{1} - 2x_{2} \geq 5 \\ \end{matrix} \right.\ ,\ x \geq 0$$

Rozwiązanie i kod z Matlaba:

f=[4;2];

A=[-3 2;1 2];

b=[1;-5];

lb=[0;0];

options = optimset('largescale','off','simplex','on');

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb,[],[],options)

x = [ ]	fval = [ ]	exitflag = -2	output = iterations: 0 message: ‘Optimization terminated during preprocessing phase. Exiting: The constraints are overly stringent; no feasible point exists.’

Interpretacja graficzna:

Rozwiązanie za pomocą tablicowej metody simpleks:

Tablica 1 (faza I):

	b	x1	x2
x0	0	4	2
x3	1	-3	2
x4	-5	1	2

Tablica 2 (faza I):

	b	x1	x3
x0	-1	7	-1
x2	0.5	-1.5	0.5
x4	-6	4	-1

Tablica 3 (faza I):

	b	x1	x2
x0	0	4	2
x3	1	-3	2
x4	-5	1	2

Tabele „zapętlają się”, nie można wyjść z fazy I, zadanie nie ma rozwiązań.

Zgodność z wynikiem z Matlaba, rozbieżność w liczbie iteracji jak w punkcie 2.1.

1. Przykład III – zadanie nieograniczone

minx₀=x₁ − 2x₂

$$X:\ \left\{ \begin{matrix} - x_{1} + x_{2} \geq 1 \\ - x_{1} - 2x_{2} \leq 10 \\ \end{matrix} \right.\ ,\ x \geq 0$$

Rozwiązanie i kod z Matlaba

f=[1;-2];

A=[1 -1;-1 -2];

b=[-1;10];

lb=[0;0];

options = optimset('largescale','off','simplex','on');

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb,[],[],options)

:

x = 1.0e+016 * 0 1.0000	fval = -2.0000e+016	exitflag = -3	output = iterations: 0 message: 'Exiting: The problem is unbounded; the constraints are not restrictive enough.'

Interpretacja graficzna:

Rozwiązanie za pomocą tablicowej metody simpleks:

Tablica 1 (faza I):

	b	x1	x2
x0	0	1	-2
x3	-1	1	-1
x4	10	-1	-2

Tablica 2 (faza II):

	b	x1	x2
x0	2	-1	-2
x3	1	-1	-1
x4	12	-3	-2

Wszystkie wartości w kolumnie x2 są ujemne, a w kolumnie b dodatnie – nie można wyznaczyć punktu centralnego, problem jest nieograniczony.

Rozwiązanie jest zgodne z wynikiem z Matlaba, rozbieżność ilości iteracji jak w punkcie 2.1.

1. Przykład IV - zadanie z interpretacją praktyczną, n>2

Maciek ma 3 rodzaje hobby: oglądanie seriali (x1), spacery (x2) i siatkówkę (x3). Obejrzenie jednego serialu powoduje, że Maciek przybiera na wadze 10 g, po jednym spacerze chudnie o 5 g, a po jednym meczu w siatkówkę chudnie o 15 g.

Jeden serial w telewizji trwa 1 godzinę, jeden spacer trwa 3 godziny, a jeden mecz w siatkówkę również trwa 1 godzinę. Podczas wakacji Maciek jest w stanie przeznaczyć na hobby nawet 20 godzin dziennie.

Przez obejrzenie jednego serialu Maciek traci 5 złotych za prąd, jeden spacer powoduje że oszczędza 4 złote, a jeden mecz w siatkówkę kosztuje go 3 złote. Maciek może przeznaczyć dziennie 8 złotych na swoje hobby.

Dodatkowo postanowił, że będzie codziennie rozgrywał co najmniej 5 meczów w siatkówkę. Ustal dla Maćka taki plan dnia, aby jak najwięcej stracił na wadze.

minx₀[g]=10[g/j]x₁[j]−5[g/j]x₂[j]−15[g/j]x₃[j]

$$X:\ \left\{ \begin{matrix} 1\left\lbrack h/j \right\rbrack x_{1}\lbrack j\rbrack + 3{\left\lbrack h/j \right\rbrack x}_{2}\lbrack j\rbrack + 1\lbrack h/j\rbrack x_{3}\lbrack j\rbrack \leq 20\lbrack h\rbrack \\ 5\left\lbrack zl/j \right\rbrack x_{1}\left\lbrack j \right\rbrack - 4\rbrack\left\lbrack zl/j \right\rbrack x_{2}\left\lbrack j \right\rbrack + {3\left\lbrack zl/j \right\rbrack x}_{3}\left\lbrack j \right\rbrack \leq 8\lbrack zl\rbrack \\ {1\lbrack h/j\rbrack x}_{3}\left\lbrack j \right\rbrack \geq 5\lbrack h\rbrack \\ \end{matrix} \right.\ ,\ x \geq 0$$

Rozwiązanie i kod z Matlaba

f=[10;-5;-15];

A=[1 3 1;5 -4 3;0 0 -1];

b=[20;8;-5];

lb=[0;0;0];

options = optimset('largescale','off','simplex','on');

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb,[],[],options)

x = 0 4 8	fval = -140	exitflag = 1	output = iterations: 1 message: 'Optimization terminated.'

Rozwiązanie metodą tablicową simpleks:

Tablica 1 (faza I):

	b	x1	x2	x3
x0	0	10	-5	-15
x5	20	1	3	1
x6	8	5	-4	3
x7	-5	0	0	-1

Tablica 2 (faza I):

	b	x1	x2	x6
x0	40	35	-25	5
x5	17.3333	-0.6667	4.3333	-0.3333
x3	2.6667	1.6667	-1.3333	0.3333
x7	-2.3333	1.6667	-1.3333	0.3333

Tablica 3 (faza II):

	b	x1	x7	x6
x0	83.75	3.75	-18.75	-1.25
x5	9.75	4.75	3.25	0.75
x3	5	0	-1	0
x2	1.75	-1.25	-0.75	-0.25

Tablica 4 (faza II):

	b	x1	x5	x6
x0	140	31.154	5.769	3.077
x7	3	1.462	0.308	0.231
x3	8	1.246	0.308	0.231
x2	4	-0.154	0.231	-0.077

Zawiera optymalne rozwiązanie: min(x0) = -140, x3 = 8, x2 = 4, x1 = 0.

Rozwiązanie jest zgodne z wynikiem z Matlaba. Rozbieżność w liczbie iteracji jak w punkcie 2.1.

1. Wnioski

W pierwszym przypadku dwie proste ograniczające oraz oś x1 tworzą zamknięty obszar, na którym funkcja celu osiąga swoją minimalną wartość w punkcie (5,0).

W drugim przykładzie proste ograniczające nie mają części wspólnej w obszarze x ≥ 0, w związku z czym zbiór rozwiązań funkcji celu jest pusty, zadanie nie ma rozwiązania.

W trzecim przykładzie obszar tworzony przez proste ograniczające jest obszarem otwartym, w którym wartość funkcji celu maleje w nieskończoność – mówimy, że zadanie jest nieograniczone.

Przykład zadania z interpretacją praktyczną pokazuje, że metoda dwufazowego simpleksu nadaje się między innymi do optymalnego zarządzania czasem.

Podczas obliczania przykładów za pomocą Matlaba można zauważyć rozbieżność między liczbą literacji a ilością tablic simpleksowych. Numeruje on bowiem tylko iteracje fazy drugiej, poczynając od zera.