TECHNIKA OPTYMALIZACJI laboratorium
Ćwiczenie II:Dwufazowa przymalna 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.

2. Wykonanie ćwiczenia

2.1 Przykład l – X≠Ø,istnieje optymalne rozwiązanie

minx₀=−2x₁ + 2x₂

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

Rozwiązanie za pomocą programu Matlab:

x = 4$\frac{1}{2}$ 0	fval = -9	exitflag = 1	output = iterations: 1 algoritm ‘medium scale: simplex’

Graficzne przedstawienie:

Rozwiązanie dwufazową prymarną metodą simpleks:

Tablica „0”(faza I):

Tworząc pierwszą tablicę ograniczenie większościowe mnożymy przez (-1) , tak aby otrzymać ograniczenie mniejszościowe.W związku z powyższym wyraz wolny przyjmuje wartość ujemną niedozwoloną przy korzystaniu z prymarnej metody simplex.

Aby pozbyć się niechcianego minusa , poddajemy tablice I fazie dwufazowej metody simplex , w której jako funkcje celu traktujemy ograniczenie z minusem w wyrazie wolnym.

$$\min{x1}\left\{ \frac{3}{\frac{2}{3}} \right\} = 4\frac{1}{2}$$

Wnioskujemy , że do bazy wchodzi zmienna x1 za x3.

Naszą tabelkę poddajemy iteracji , otrzymujemy tabelkę pierwszą.

Tabela po iteracji 1(faza II):

Po przeprowadzeniu fazy pierwszej i pozbyciu się minusów w wyrazach wolnych możemy przejść do fazy drugiej. Jednak dalsze iteracje są zbędne gdyż z tabeli odczytujemy minimalne rozwiązanie , wnioskując z warunków na minimum funkcji celu:

x1 = 4$\frac{1}{2}$, x2 = 0; min x0 = -9.

Obliczenia oraz ilość iteracji zgadzają się z wynikami otrzymanymi w Matlabie.

2.2 Przykład ll – X=Ø,zbiór rozwiązań jest pusty

minx₀=6x₁ + 3x₂

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

Rozwiązanie za pomocą programu Matlab:

x = [ ]	fval = [ ]	exitflag = 2	output = iterations: 0 algoritm ‘medium scale: simplex’

Graficzne przedstawienie:

Rozwiązanie dwufazową prymarną metodą simpleks:

Tablica „0”(faza I):

Ze względu na minus , funkcją celu staje się x4 byśmy mogli skorzystać z dwufazowej metody simplex.

Najmniejszą wartość w wersie x4 przyjmuje kolumna x2.Kolejny raz korzystamy z odpowiedniej zależności:

$$\min{x2}\left\{ \frac{0}{3} \right\} = 0$$

Wnioskujemy , że do bazy wchodzi zmienna x2 za zmienną x0(obecnie x4 jest naszą funkcją celu , więc jest to możliwe). Naszą tabelkę poddajemy iteracji , otrzymujemy tabelkę pierwszą.

Tabela po iteracji 1(faza I):

$$\min{x1}\left\{ \frac{0}{2} \right\} = 0$$

Wnioskujemy , że do bazy wchodzi zmienna x1 za zmienną x2.Naszą tabelkę poddajemy nastepnej iteracji.

Tabela po iteracji 2(faza I):

Z tabeli wynika , że do bazy powinna wejść zmienna x2 za zmienną x1. Przed chwilą do bazy weszła zmienna x1 za zmienną x2 , co oznacza , że tabele zapętlają się a zbiór rozwiązań zadania jest pusty.

Obliczenia oraz ilość iteracji zgadzają się z wynikami otrzymanymi w Matlabie.

2.2 Przykład lll – X≠Ø istnieje rozwiązanie minimalne w zakresie liczb rzeczywistych

minx₀=x₁ + 2x₂

$X:\ \left\{ \begin{matrix} {\ - 2x}_{1} + x_{2} \leq 4 \\ {6x}_{1} + {2x}_{2} \leq 8 \\ \frac{1}{4}x_{1} - x_{2} \leq 1 \\ \end{matrix} \right.\ \ \ ,\ x$⋲R²

By obliczyć powyższy przykład podstawiamy x₁=x₇ - x₈ , x₂=x₉ - x₁₀ .

Rozwiązanie za pomocą programu Matlab:

x = -2,8571 -1,7413	fval = -6,2857	exitflag = 1	output = iterations: 2 algoritm ‘medium scale: simplex’

Graficzne przedstawienie:

Rozwiązanie dwufazową prymarną metodą simpleks:

Nie musimy korzystać z pierwszej fazy metody , gdyż żaden z wyrazów wolnych nie jest ujemny. Tabela z nowo podstawionymi zmiennymi zamieszczona jest poniżej.

Tablica „0”(faza II):

Najniższą wartość w wersie x0 przyjmuje kolumna x10. Zgodnie ze znaną zależnością na minimum x10:

$$\min{x10}\left\{ \frac{1}{1} \right\} = 1$$

Wnioskujemy , że do bazy wchodzi zmienna x10 za zmienną x5. Naszą tabelkę poddajemy iteracji , otrzymujemy tabelkę pierwszą.

Tabela po iteracji 1(faza II):

Wnioskujemy , że do bazy wchodzi zmienna x8 za zmienną x3.Naszą tabelkę poddajemy kolejnej iteracji.

Tabela po iteracji 2(faza II):

Z warunku na minimum funkcji celu (w wersie x8 wszystkie kolumny poza wyrazem wolnym większe od zera) wnioskujemy , że otrzymaliśmy wynik postaci:

x8 = $\frac{20}{7}$, x10 = $\frac{12}{7}$; min x0 = - $\frac{88}{14}$.

Jako , że po podstawieniu powrotnym uzyskujemy zależności:

x1=-x8 oraz x2=-x10,

szukane wyniki przyjmują postać:

x1 =- $\frac{20}{7}$, x2 =- $\frac{12}{7}$; min x0 = - $\frac{88}{14}$.

Inaczaj : x1 =-2,8571, x2 =-1,7143; min x0 = - 6,2857.

Obliczenia oraz ilość iteracji zgadzają się z wynikami otrzymanymi w Matlabie.

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

Daniel wykonuje zarobkowo 3 rodzaje prostych układów elektronicznych.Są to układy typu I (x₁) , układy typu II (x₂) oraz ukłądy typu III (x₃).Wykonane układy sprzedaje w sklepie internetowym odpowiednio 6 złotych za układ typu I ,7 złotych za układ typu II oraz 8 złotych za układ typu III.Czas , który zajmuje złożenie układu I typu to 2 godziny , układ II typu to koszt również 2 godzin , natomiast układ III typu wymaga rezerwacji 3 godzin czasu.Daniel w ciągu tygodnia może poświęcić 12 godzin na pracę nad układami.Dbając o swój rozwój , Daniel założył sobie, że w każdym tygodniu złoży przynajmniej dwa układy typy III. Ilość ofert ,które Daniel może wystawić daromwo na stronie internetowej w ciągu tygodnia to maksymalnie 8 ofert.Ile układów , każdego typu powinien sprzedać Daniel , by uzyskać największy zysk w ciągu jednego tygodnia?

maxx₀=6x₁ + 7x₂ +8x₃

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

Jednostki: Jednostką funkcji celu , która jest zyskiem jest [złoty]. Jednostką x[i] jest [szt].

Jednostki w równaniu na funkcję celu:

[złoty] = $\frac{\lbrack zloty\rbrack}{\lbrack szt\rbrack}$ * [szt] + $\frac{\lbrack zloty\rbrack}{\lbrack szt\rbrack}$ * [szt] + $\frac{\lbrack zloty\rbrack}{\lbrack szt\rbrack}$ * [szt]

Jednostki w pierwszym ograniczeniu(wynik w godzinach):

$\frac{\lbrack h\rbrack}{\lbrack szt\rbrack}$ * [szt] + $\frac{\lbrack h\rbrack}{\lbrack szt\rbrack}$ * [szt] + $\frac{\lbrack h\rbrack}{\lbrack szt\rbrack}$ * [szt] = [h];

Itd.

Rozwiązanie za pomocą programu Matlab:

x = 0 3 2	fval = -37	exitflag = 1	output = iterations: 2 algoritm ‘medium scale: simplex’

Rozwiązanie dwufazową prymarną metodą simpleks:

Tablica „0”(faza I):

Koniecznym jest pozbycie się minusa w wersie x6, dlatego właśnie ten wers staję się funkcją celu w pierwszej fazie.Najmniejsza wartość w wersie x6 występuje w kolumnie x3.Korzystamy z zależności na minimum x3.

$$\min{x3}\left\{ \frac{12}{3},\frac{8}{1} \right\} = 4$$

Wnioskujemy , że do bazy wchodzi zmienna x3 za zmienną x4.Podajemy naszą tabelę iteracji.

Tabela po iteracji 1(faza II):

Po pozbyciu się minusa możemy przejść do fazy II.

$$\min{x2}\left\{ \frac{4}{\frac{2}{3}},\frac{4}{\frac{1}{3}},\frac{2}{\frac{2}{3}} \right\} = 3$$

Wnioskujemy , że zmienna x2 wchodzi do bazy za zmienną x6.Poddajemy tabelkę kolejnej iteracji.

Tabela po iteracji 2(faza II):

Z warunku na maksimum funkcji wnioskujemy , że otrzymaliśy optymalne rozwiązanie:

x3 =2, x2 =3 , x0=0; max x0 = 37.

Obliczenia oraz ilość iteracji zgadzają się z wynikami otrzymanymi w Matlabie.

3. Wnioski

Dwufazowa metoda simplex pozwala nam na liczenie przykładów z ograniczeniem większościowym , w którym po przemnożeniu przez (-1) uzyskujemy ograniczenie mniejszościowe z minusem w wyrazie wolnym. Pierwszy przykład tworzy trójkąt , na dodatnich powierchni x-ów , drugi tworzy przesztrzeń ale poza dodatnimi x-ami co sprawia , że zbiór rozwiązań tego zadania jest pusty. W trzecim przykładzie , poznaliśmy sposób na obliczenie minimum funkcji metodą simplex , gdy rozwiązanie należy do zbioru liczb rzeczywistych. Czwarte zadanie pozwoliło nam poznać praktyczne zastosowanie metody simplex , tym razem jednak mogliśmy skorzystać z ograniczenia większościowego, co pozwala nam na znaczne poszerzenie zbioru zadań , które możemy obliczać za pomocą metody simplex. Dwufazowa metoda simplex jest przydatną metodą przy zagadnieniu maksymalizowania np. zysków przy pewnych ograniczeniach nałożonych z góry.