TECHNIKA OPTYMALIZACJI laboratorium
Ćwiczenie I: Metoda przymalna simpleks
Grupa:

1. Cel ćwiczenia

Celem ćwiczenia jest poznanie podstawowej metody rozwiązywania liniowych zadań optymalizacji prymarną metodą simpleks.

Prymarna metoda simpleks pozwala na wyliczenie takiego wektora zmiennych decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X, dla którego funkcja celu osiąga maksimum:

przy ograniczeniach:

dim x= nx1, dim c=nx1, dim A’=mxn, dim b = mx1

Wektor b nazywany jest wektorem wyrazów wolnych w ograniczeniach i powinien przyjmować wartości nieujemne.

2. Wykonanie ćwiczenia

2.1 Przykład l – jedno rozwiązanie optymalne przy n=2

maxx₀=−2x₁ + 4x₂

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

Rozwiązanie za pomocą programu Matlab:

x = 1$\frac{2}{3}$ 7$\frac{1}{3}$	fval = -26	exitflag = 1	output = iterations: 2 algoritm ‘medium scale: simplex’

Graficzne przedstawienie:

Rozwiązanie prymarną metodą simpleks:

Tablica „0”:

	b	x1	x2
x0	0	2	1
x3	9	1	1
x4	4	-2	1
x5	14	2	1

Wnioskujemy , że do bazy wchodzi x2 za zmienną x4.

Naszą tabelkę poddajemy iteracji i otrzymujemy tablkę 1:

Tabela po iteracji 1:

	b	x1	x4
x0	16	-6	4
x3	5	3	-1
x2	4	-2	1
x5	10	4	-1

$$min\ x1\left\{ \frac{5}{3},\frac{10}{4} \right\} = \frac{5}{3}$$

Wnioskujemy , że do bazy wchodzi x1 za zmienną x3.

Tabela po iteracji 2:

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

Z tabeli odczytujemy maksymalne rozwiązanie , wnioskując z warunków na maksimum funkcji celu:

x1 = 1$\frac{2}{3}$, x2 = 7$\frac{1}{3}$; max x0 = 26.

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

2.2 Przykład ll – zadanie nieograniczone przy n=2

maxx₀ = 6x₁ + 5x₂

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

Rozwiązanie za pomocą programu Matlab:

x = 1.0e+016 * 1.0000 0	fval = -6.0000e+016	exitflag = 3	algoritm ‘medium scale: simplex’

Graficzne przedstawienie:

Rozwiązanie prymarną metodą simpleks:

Tablica „0”:

	b	x1	x2
x0	0	-6	-5
x3	3	-1	1
x4	5	-$\frac{1}{3}$	1

Możemy zauważyć , że cała kolumna x1 przyjmuje wartości ujemne. Wnioskujemy ze zadanie jest nieograniczone , co jest zgodne z wynikiem w matlabie(exitflag=3).

2.3 Przykład lll – zadanie praktyczne przy n>2

Fabryka części zamiennych do samochodów sportowych odzyskuje 3 rodzaje części:x1,x2,x3.Pierwszy pracownik potrzebuje 3 godzin na odzyskanie części x1 ze zużytego samochodu , dwóch godziny by odzyskać część x2 oraz 2 godzin bo odzyskać część x3.Pracownik ten posiada umowę na 60 godzin pracy miesięcznie. Drugi pracownik potrzebuje 4 godzin by odzyskać część x1 , 3 by odzyskać część x2 oraz godziny by odzyskać część x3.Stażysta ten posiada umowę na 48 godzin pracy w zakładzie prze miesiąc. Zysk z jednej części x1 to - 80 funtów, z jednej części x2 - 65 funtów , a z jednej części x3 - 50 funtów. Opracuj optymalny pod kątem zysku cykl pracy wymienionych wyżej pracowników.

maxx₀ = 80x₁ + 65x₂ + 50x₃

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

Rozwiązanie za pomocą programu Matlab:

x = 0 9 21	fval = -1635	exitflag = 1	algoritm ‘medium scale: simplex’

Rozwiązanie prymarną metodą simpleks:

Tablica „0”:

	b	x1	x2	x3
x0	0	-80	-65	-50
x4	60	3	2	2
x5	48	4	3	1

$$min\ x1\left\{ \frac{60}{3},\frac{48}{4} \right\} = 12$$

Wnioskujemy , że do bazy wchodzi x1 za zmienną x5.

Tabela po iteracji 1:

	b	x5	x2	x3
x0	960	20	-5	-30
x4	24	-$\frac{3}{4}$	-$\frac{1}{4}$	$$\frac{5}{4}$$
x1	12	-$\frac{1}{4}$	$$\frac{3}{4}$$	$$\frac{1}{4}$$

$$min\ x3\ \left\{ \frac{24}{1.25},\frac{12}{0.25} \right\} = 19.2$$

Wnioskujemy , że do bazy wchodzi x3 za zmienną x4.

Tabela po iteracji 2:

	b	x5	x2	x4
x0	1536	2	-11	24
x3	19.2	-$\frac{3}{5}$	-$\frac{1}{5}$	$$\frac{8}{10}$$
x1	7.2	$$\frac{2}{5}$$	$$\frac{4}{5}$$	-$\frac{1}{5}$

min x2 {9} = 9

Wnioskujemy , że do bazy wchodzi x2 za zmienną x1.

Tabela po iteracji 3:

	b	x5	x1	x4
x0	1635	7$\frac{1}{2}$	13$\frac{3}{4}$	21$\frac{1}{4}$
x3	21	-$\frac{1}{2}$	$$\frac{1}{4}$$	$$\frac{3}{4}$$
x2	9	$$\frac{1}{2}$$	$$\frac{5}{4}$$	-$\frac{1}{4}$

Z tabeli odczytujemy maksymalne rozwiązanie , wnioskując z warunków na maksimum funkcji celu:

x3 = 21, x2 = 9; max x0 = 1635.

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

3.Wnioski

W graficznym przedstawieniu pierwszego przykładu zauważyć można , że proste tworzą zamknięty wielokąt(po którego wierzchołkach poruszamy się w metodzie simpleks).Dzięki ograniczeniu obszaru możemy znaleźć maksimum funkcji celu.

Drugi przykład ukazuje nam obszar nieograniczony (otwarty w kierunku dodatniej osi x) , w związku z powyższym funkcja celu może wzrastać bez ogarniczeń. Wartość maksymalna dla tego przykładu nie istnieje.

Ostatnie zadanie pozwoliło nam poznać zastosowanie metody simpleks w optymalizacji procesów produkcyjnych , a także innych procesów które można opisać funkcją celu oraz ograniczeniami wzrostu tej funkcji.