TECHNIKA OPTYMALIZACJI - LABOLATORIUM
Ćwiczenie II: Dwufazowa metoda simpleks
Skład grupy:
- Dawid Cekus - Mateusz Grzelak

Zadania programowania liniowego dla ograniczeń mniejszościowych i większościowych. Dwufazowa metoda simpleks.

1. Cel ćwiczenia.

Celem ćwiczenia to zapoznanie się metodą rozwiązywania zadania LP na przykładzie dwufazowej metody simpleks. Pozwala ona, 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, macierz A₂ jest to macierz tworzona przez współczynniki przy zmiennych decyzyjnych w kolejnych m₂ ograniczeniach mniejszościowych. Wektory b₁, b₂ to wektory wyrazów wolnych w ograniczeniach

1. Przebieg ćwiczenia.

Przykład I X  ≠  O , istnieje optymalne rozwiązanie dla n = 2

Min { x₀ = -2x₁ + x₂ }

Ograniczenia:

$$\left\{ \begin{matrix} 2x_{1} + x_{2} \leq 1 \\ \ 4x_{1} - 3x_{2}\ \geq 2 \\ \end{matrix} \right.\ \ $$

x₁,  x₂  ≥ 0

Rozwiązanie uzyskane przy użyciu Matlaba - linprog:

$$x = \left\lbrack \ \begin{matrix} 0.5\ \\ 0 \\ \end{matrix} \right\rbrack$$

Fval = -1

Exitflag = 1

Iterations = 1

Algorithm = „simplex”

Interpretacja graficzna zadania:

Opis i rozwiązanie problemu LP z użyciem metody dwu fazowej.

Przed optymalizacją metoda simpleks, rozpoczynam od standaryzacji problemu. (Algorytm simpleks polega na badaniu postaci kanonicznej, więc przed przystąpieniem do budowy tablicy muszę zamienić wszystkie nierówności na równania.)

- Dla ograniczeń ze znakiem ≤ dodaję zmienne swobodne „slack” w celu utworzenia równań.

2x₁ + x₂ ≤ 1 →  2x₁ + x₂  +  s₁ = 1

- Dla ograniczeń ze znakiem ≥ odejmuję zmiennych swobodną / nadmiarową „excess” i dodaję zmienną sztuczą „artificial” w celu utworzenia równań.

4x₁ − 3x₂  ≥ 2 →  4x₁ − 3x₂ −  e₂ + a₂ = 2

Faza I

Celem jest minimalizacja sumy wszystkich zmiennych sztucznych.

(W fazie I zaczynam od minimalizacji niezależnie od tego czy oryginalną funkcją celu jest minimalizacja czy maksymalizacja).

Ponieważ mam tylko jedną zmienną sztuczną, więc moją funkcją celu jest:

Min x₀ = a₂

Następnie standaryzuję funkcję celu:

x₀ = a₂ →  x₀ −  a₂ = 0

Dodatkowo należy zaznaczy, że wszystkie zmienne decyzyjne mają wartości dodatnie. Tj:

x₁,  x_2,s₁, e₂, a₂  ≥ 0

Przechodzę do tworzenia tabeli simpleksowej. (RHS – „right hand side” – prawa strona równania)

	x1	x2	s1	a2	e2	RHS
s1	2	1	1	0	0	1
a2	4	-3	0	1	-1	2
x0	0	0	0	-1	0	0

W kolumnie zmiennej bazowej a₂ dla rzędu x₀ występuje wartość -1, co nie jest zgodne z typową definicją zmiennych bazowych. Innymi słowy wartość 1 może występować tylko w kolumnie i rzędzie a₂, a w innych rzędach dla tej kolumny musi występować 0.

Z tego powodu wykonuję operację elementarną R_x1 -> R_x1 + R_a2

	x1	x2	s1	a2	e2	RHS
s1	2	1	1	0	0	1
a2	4	-3	0	1	-1	2
x0	4	-3	0	0	-1	2

Warunkiem optymalizacji w tym kroku będzie osiągnięcie tabeli, w której wszystkie współczynniki zmiennych w rzędzie x₀ będą ≤0

Krok 1. Znajduję największą dodatnią wartość w rzędzie x₀, Kolumna x₁, w której znajduje się ta wartość to tzw. oś „pivot” (W celach wyjaśnień dla kolejnych przykładów, zaznacza, że gdyby operacja ta dotyczyła maksymalizacji, musiał bym wybrać najmniejsza ujemną wartość w tym kroku).

Krok 2. Wykonuję test minimum, dla wartości dodatnich w kolumnie x₁.

min { RHS_k / x_1k } – wybieram najmniejszą z obliczonych wartości (lub dowolną, jeśli są różne), a rząd, którego dotyczy będzie tzw. rzędem osi.

	x1	x2	s1	a2	e2	RHS	Min test
s1	2	1	1	0	0	1	$$\frac{1}{2}$$
a2	4	-3	0	1	-1	2	$$\frac{2}{4} = \frac{1}{2}$$
x0	4	-3	0	0	-1	2

Rząd i kolumna osi wyznaczają teraz tzw. Wartość osi. W kolejnej tabeli zamieniam więc a₂ z x₁

Wykonuję kolejno następujące operacje elementarne w celu uzyskania, jak wcześniej opisałem odpowiednich wartości dla zmiennych bazowych w kolumnie x₁. Tzn. 1 w osi oraz 0 dla innych wartości dla kolumny x­₁.

R₃ -> -R₂ + R₃

R₂ -> R₂ / 4

R₁ -> -2R₂ + R­₁

	x1	x2	s1	a2	e2	RHS
s1	0	$$\frac{5}{2}$$	1	$$\frac{- 1}{2}$$	$$\frac{1}{2}$$	0
x1	1	$$\frac{- 3}{4}$$	0	$$\frac{1}{4}$$	$$\frac{- 1}{4}$$	$$\frac{1}{2}$$
x0	0	0	0	-1	0	0

Otrzymane współczynniki w rzędzie x₀ są ≤0 więc osiągnięty został warunek na optimum i tabela jest optymalna.

W zmiennych bazowych, dzięki powyższym operacjom zniknęła nam zmienna sztuczna. Możemy teraz zinterpretować tabele, jako:

s₁ = 0, x₁ = 0.5

x₂ = e₂ = a₂ = 0

x₀ = a₂ = 0

Wartość funkcji celu to 0, co implikuje, że wartość zmiennej sztucznej to również zero i problem ma „rozwiązywalne” rozwiązanie.

Faza II

Przechodzę teraz do rozwiązywania oryginalnej funkcji, skoro pozbyłem się sztucznej zmiennej, i mogę usunąć jej kolumnę.

Analogicznie jak pokazałem w fazie pierwszej standaryzuję problem, przekształcam w celu otrzymania odpowiednich wartości dla zmiennych bazowych, wykonuje test minimum, i tak aż do osiągnięcia warunku na optymalną tabelę.

max { x₀ = -2x₁ + x₂ }

min x₀ + 2x₁ −  x₂ = 0

	x1	x2	s1	e2	RHS
s1	0	$$\frac{5}{2}$$	1	$$\frac{1}{2}$$	0
x1	1	$$\frac{- 3}{4}$$	0	$$\frac{- 1}{4}$$	$$\frac{1}{2}$$
x0	2	-1	0	0	0

R₃ -> -2R₂ + R₁

	x1	x2	s1	e2	RHS
s1	0	$$\frac{5}{2}$$	1	$$\frac{1}{2}$$	0
x1	1	$$\frac{- 3}{4}$$	0	$$\frac{- 1}{4}$$	$$\frac{1}{2}$$
x0	0	$$\frac{1}{2}$$	0	$$\frac{1}{2}$$	-1

$$R_{1} \rightarrow \frac{2}{5}R_{1}$$

$$R_{2} \rightarrow \frac{3}{4}R_{1} + \ R_{2}$$

$$R_{3} \rightarrow \frac{- 1}{2}R_{1} + \ R_{3}$$

	x1	x2	s1	e2	RHS
x2	0	1	$$\frac{2}{5}$$	$$\frac{1}{5}$$	0
x1	1	0	$$\frac{3}{10}$$	$$\frac{- 1}{10}$$	$$\frac{1}{2}$$
x0	0	0	$$\frac{- 1}{5}$$	$$\frac{2}{5}$$	-1

$$R_{2} \rightarrow \frac{R_{1}}{2} + \ R_{2}$$

R₃ → −2R₁ +  R₃

R₁ → 5R₁

	x1	x2	s1	e2	RHS
e2	0	5	2	1	0
x1	1	$$\frac{1}{2}$$	$$\frac{1}{10}$$	0	$$\frac{1}{2}$$
x0	0	-2	$$\frac{- 3}{5}$$	0	-1

Otrzymane współczynniki w rzędzie x₀ są ≤0 więc osiągnęliśmy warunek na optimum w przypadku dla minimalizacji i tabela jest optymalna.

Interpretacja wyników:

X₁ = 0.5

X₂ = 0

X₀ = -1

Wnioski:

Otrzymaliśmy wyniki takie same jak w przypadku obliczeń w matlabie. Ilość iteracji nie zgadza się z liczbą tablic, ponieważ matlab zlicza je począwszy od fazy II.

Przykład II X =  O , zbiór pusty, zadanie nie ma rozwiązania dla n = 2

Min { x₀ = 2x₁ + x₂ }

Ograniczenia:

$$\left\{ \begin{matrix} - 4x_{1} + 3x_{2} \leq 2 \\ - 2x_{1} - x_{2}\ \geq 1 \\ \end{matrix} \right.\ \ $$

x₁,  x₂  ≥ 0

Rozwiązanie uzyskane przy użyciu Matlaba - linprog:

x = [ ]

fval = [ ]

Output:

No feasible points exists.

Exitflag = -2

Iterations = 0

Algorithm = „simplex”

Interpretacja graficzna zadania:

Opis i rozwiązanie problemu LP z użyciem metody dwu fazowej.

Standaryzacja:

−4x₁ + 3x₂ ≤ 2 →   − 4x₁ + 3x₂  +  s₁ = 2

−2x₁ − x₂  ≥ 1 →   − 2x₁ − x₂ −  e₂ + a₂ = 1

Założenia:

x₁,  x_2,s₁, e₂, a₂  ≥ 0

Funkcja celu:

min x₀ =  a₂ 

Standaryzacja funkcji celu:

x₀ = a₂ →  x₀ −  a₂ = 0

Tablica simpleksowa:

	x1	x2	s1	a2	e2	RHS
s1	-4	3	1	0	0	2
a2	-2	-1	0	1	-1	1
x0	0	0	0	-1	0	0

R₃ → R₂ +  R₃

	x1	x2	s1	a2	e2	RHS
s1	-4	3	1	0	0	2
a2	-2	-1	0	1	-1	1
x0	-2	-1	0	0	-1	1

Interpretacja wyników:

Nie można wybrać, największej dodatniej wartości w rzędzie x₀, co oznacza, że nie ma optymalnego rozwiązania i minimalizacja nie jest możliwa.

Nie ma sensu wybierać również „zer”, ponieważ skutkowałoby to tzw. zapętleniem i nigdy nie otrzymalibyśmy wyniku.

Wynik zgodny, z obliczeniami w matlabie.

Przykład III X ≠  O , wektor x przyjmuje wartości z zakresu licz rzeczywistych tzn: x  ∈  Rⁿ- lub tylko kilka składowych wektora x _i ∈  R i istnieje rozwiązanie optymalne zadania.

Funkcja celu:

max x₀ =  x₁ − 2x₂

Ograniczenia:

$$\left\{ \begin{matrix} - 4x_{1} + 2x_{2} \leq 8 \\ 2x_{1} - 3x_{2} \leq 3 \\ 3x_{1} + 2x_{2} \leq 6 \\ \end{matrix} \right.\ \ $$

x₁,  x₂  ∈  R

Rozwiązanie uzyskane przy użyciu Matlaba - linprog:

$$x = \left\lbrack \ \begin{matrix} - 3.75\ \\ - 3.5 \\ \end{matrix} \right\rbrack$$

Fval = -3.25

Exitflag = 1

Iterations = 2

Algorithm = „simplex”

Interpretacja graficzna zadania:

Opis i rozwiązanie problemu LP z użyciem metody dwu fazowej.

Wprowadzam zmienne swobodne z powodu braku ograniczeń dla x₁ i x₂ w celu sprowadzenia zadania do postaci standardowej.

x₁ = u₁ −  v₁

x₂ = u₂ −  v₂

Standaryzacja:

−4x₁ + 2x₂ ≤ 8 →   − 4(u₁ −  v₁)+2(u₂ −  v₂)+ s₁ = 8

2x₁ − 3x₂ ≤ 3 →  2(u₁ −  v₁)−3(u₂ −  v₂)+ s₂ = 3

3x₁ + 2x₂ ≤ 6 →  3(u₁ −  v₁)+2(u₂ −  v₂)+ s₃ = 6

x₀ =  x₁ − 2x₂ →   x₀ −  (u₁ −  v₁)+2(u₂ −  v₂)=0

Tablica simpleksowa:

	u1	v1	u2	v2	s1	s2	s3	RHS	Min test
s1	-4	4	2	-2	1	0	0	8	-
s2	2	-2	-3	3	0	1	0	3	1
s3	3	-3	2	-2	0	0	1	6	-
x0	-1	1	2	-2	0	0	0	0

$$R_{2} \rightarrow \frac{R_{2}}{3}$$

R₁ → 2R₂ +  R₁

R₃ → 2R₂ +  R₃

R₄ → 2R₂ +  R₄

	u1	v1	u2	v2	s1	s2	s3	RHS	Min test
s1	$$\frac{- 8}{3}$$	$$\frac{8}{3}$$	0	0	1	$$\frac{2}{3}$$	0	10	$$\frac{15}{4}$$
v2	$$\frac{2}{3}$$	$$\frac{- 2}{3}$$	-1	1	0	$$\frac{1}{3}$$	0	1	-
s3	$$\frac{13}{3}$$	$$\frac{- 13}{3}$$	0	0	0	$$\frac{2}{3}$$	1	8	-
x0	$$\frac{1}{3}$$	$$\frac{- 1}{3}$$	0	0	0	$$\frac{- 2}{3}$$	0	2

$$R_{2} \rightarrow \frac{R_{1}}{4} + \ R_{2}$$

$$R_{3} \rightarrow \frac{{13R}_{1}}{8} + \ R_{3}$$

$$R_{1} \rightarrow \frac{{3R}_{1}}{8}$$

$$R_{4} \rightarrow \frac{1R_{1}}{3} + \ R_{4}$$

	u1	v1	u2	v2	s1	s2	s3	RHS
v1	-1	1	0	0	$$\frac{3}{8}$$	$$\frac{1}{4}$$	0	$$\frac{15}{4} = 3.75$$
v2	0	0	-1	1	0	$$\frac{1}{2}$$	0	$$\frac{7}{2} = 3.5$$
s3	0	0	0	0	$$\frac{13}{8}$$	$$\frac{7}{4}$$	1	$$\frac{97}{4}$$
x0	0	0	0	0	$$\frac{1}{8}$$	$$\frac{3}{4}$$	0	$$\frac{13}{4} = 3.25$$

Interpretacja wyników:

x₁ = u₁ −  v₁ = 0 −  3.75 =   −  3.75 

x₂ = u₂ −  v₂ = 0 −  3.5 =   −  3.5

x₀ = 3.25

Ilość iteracji otrzymanych w wyniku działania funkcji linprog w matlabie nie zgadza się z liczbą tablic, ponieważ matlab zlicza je począwszy od fazy II.

Wartość funkcji fval, również nie zgadza się, ponieważ, matlab z użyciem linprog liczy tylko minimum, przez co wartości obliczone zgadzają się, ale ich znak się nie zgadza (są przeciwne).

Przykład IV Przykład praktyczny. Zadanie PL z większa liczbą zmiennych (n>2)

Treść zadania:

Babcia Genowefa zachorowała na grypę. Bakterie można zabić na trzy sposoby.

-Antybiotykami - x₁

-Alkoholem – x₂

-Wodą z cytryną – x₃

Przyjęcie 1 porcji Antybiotyku zabija 40 Mld bakterii

Przyjęcie 1 porcji Alkoholu zabija 5 Mld bakterii

Przyjęcie 1 porcji Wody z cytryną zabija 1 Mld bakterii

Działanie 1 porcji Antybiotyku trwa 24h

Działanie 1 porcji Alkoholu trwa 5h

Działanie 1 porcji Wody z cytryną trwa 1h

Nie wolno podawać innych leków, kiedy działanie poprzedniego nie skończyło się. Kuracja nie może trwać więcej niż 7 dni, bo bakterie uodpornia się na Leki.

Koszt 1 porcji Antybiotyku wynosi 10 zł

Koszt 1 porcji Alkoholu wynosi 3 zł

Koszt 1 porcji Wody z cytryną wynosi 1 zł

Babcia może ze swojej renty wydać maksymalnie 31 zł, w innym wypadku nie będzie mieć, co jeść.

Należy ustalić dla babci kurację, która zabije najwięcej bakterii, za założeniem, że babcia przynajmniej raz spróbuje wody z cytryną, żeby się wyleczyć.

Rozwiązanie uzyskane przy użyciu Matlaba - linprog:

$$x = \left\lbrack \ \begin{matrix} 3\ \\ \begin{matrix} 0\ \\ 1 \\ \end{matrix} \\ \end{matrix} \right\rbrack$$

Fval = -121

Exitflag = 1

Iterations = 1

Algorithm = „simplex”

Funkcja celu:

max x₀ =  40x₁ + 5x₂ + x₃   [Mld bakt.]

Objaśnienia:

-Współczynniki w funkcji celu oznaczają ilość zabitych w Mld bakterii przypadająca na 1 porcję $\lbrack Mld\frac{\text{bakt.}}{porcje}\rbrack\ \ \ $

-Zmiennymi w funkcji celu jest ilość porcji.

Ograniczenia:

$$\left\{ \begin{matrix} \ 24x_{1} + {5x}_{2} + x_{3} \leq 168\ \lbrack godziny\rbrack \\ \ 10x_{1} + {3x}_{2} + x_{3} \leq 31\ \lbrack PLN\rbrack \\ x_{3} \geq 1 \\ \end{matrix} \right.\ \ $$

x₁,  x₂,  x₃  ≥ 0

Objaśnienia:

-Współczynniki w pierwszym ograniczeniu oznaczają ilość godzin działania leku przypadająca na 1 porcję leku $\lbrack\frac{\text{godziny}}{porcje}\rbrack\ \ \ $

-Współczynniki w drugim ograniczeniu funkcji oznaczają ilość złotych (kosztów) przypadająca na 1 porcję leku $\lbrack\frac{\text{PLN}}{porcje}\rbrack\ \ \ $

-Trzecie ograniczenie oznacza, że ilość przyjętych przez pacjenta porcji wody z cytryną ma być większa lub równa 1

Standaryzacja:

24x₁ + 5x₂ + x₃ ≤ 168 →  24x₁ + 5x₂ + x₃ +  s₁ = 168

10x₁ + 3x₂ + x₃ ≤ 31 →  10x₁ + 3x₂ + x₃ +  s₂ = 31

x₃ ≥ 1 →  x₃ −  e₃ +  a₃ = 31

Faza I

Funkcją celu w fazie I:

min = x₀ =  a₃

Standaryzacja funkcji celu:

x₀ = a₃ →  x₀ −  a₃ = 0

Tablica smipleks:

	x1	x2	x3	s1	s2	a3	e3	RHS
s1	24	5	1	1	0	0	0	168
s2	10	3	1	0	1	0	0	31
a3	0	0	1	0	0	1	-1	1
x0	0	0	0	0	0	-1	0	0

R₄ → R₃ +  R₄

	x1	x2	x3	s1	s2	a3	e3	RHS	Min test
s1	24	5	1	1	0	0	0	168	168
s2	10	3	1	0	1	0	0	31	31
a3	0	0	1	0	0	1	-1	1	1
x0	0	0	1	0	0	0	-1	1

R₁ → −R₃ +  R₁

R₂ → −R₃ +  R₂

R₄ → −R₃ +  R₄

	x1	x2	x3	s1	s2	a3	e3	RHS
s1	24	5	0	1	0	-1	1	167
s2	10	3	0	0	1	-1	1	30
x3	0	0	1	0	0	1	-1	1
x0	0	0	0	0	0	-1	0	0

Warunek optymalności tablicy spełniony.

x₀ = a₃ = 0

Faza II

Funkcją celu w fazie II - maksymalizacja

max x₀ −  40x₁ − 5x₂ − x₃ = 0

	x1	x2	x3	s1	s2	e3	RHS
s1	24	5	0	1	0	1	167
s2	10	3	0	0	1	1	30
x3	0	0	1	0	0	-1	1
x0	-40	-5	-1	0	0	0	0

R₄ → R₃ +  R₄

	x1	x2	x3	s1	s2	e3	RHS	Min test
s1	24	5	0	1	0	1	167	$$\frac{167}{24} = 6.958(3)$$
s2	10	3	0	0	1	1	30	$$\frac{30}{10} = 3$$
x3	0	0	1	0	0	-1	1	-
x0	-40	-5	0	0	0	-1	1

R₄ → 4R₂ +  R₄

$$R_{2} \rightarrow \frac{R_{2}}{10}$$

R₁ → −24R₂ +  R₁

	x1	x2	x3	s1	s2	e3	RHS
s1	0	$$\frac{- 11}{5}$$	0	1	$$\frac{- 24}{10}$$	$$\frac{- 14}{10}$$	95
x1	1	$$\frac{3}{10}$$	0	0	$$\frac{1}{10}$$	$$\frac{1}{10}$$	3
x3	0	0	1	0	0	-1	1
x0	0	7	0	0	4	3	121

Otrzymane współczynniki w rzędzie x₀ są ≥0 więc osiągnęliśmy warunek na optimum w przypadku dla maksymalizacji i tabela jest optymalna.

Interpretacja wyników:

X₁ = 3

X₂ = 0

X₃ = 1

X₀ = 121

Wnioski:

Ilość iteracji otrzymanych w wyniku działania funkcji linprog w matlabie nie zgadza się z liczbą tablic, ponieważ matlab zlicza je począwszy od fazy II.

Wartość funkcji fval, również nie zgadza się, ponieważ, matlab z użyciem linprog liczy tylko minimum, przez co wartości obliczone zgadzają się, ale ich znak się nie zgadza (są przeciwne).