TECHNIKA OPTYMALIZACJI laboratorium
Ćwiczenie I: Metoda przymalna simpleks
Grupa: WAWELSKI Smok BAMBO Murzynek

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z podstawową metodą rozwiązywania liniowego zadania optymalizacji na przykładzie prymarnej metody simpleks.

Metoda prymalnego 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:

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.

1. Przebieg ćwiczenia

   1. Przykład I – zadanie z jednym rozwiązaniem optymalnym, n=2

maxx₀=−x₁ + 4x₂

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

Rozwiązanie obliczone za pomocą Matlaba:

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

Interpretacja graficzna:

Rozwiązanie za pomocą tablicowej metody simpleks:

Tablica „0”:

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

Tworzenie tablicy 1 (iteracja 1.):

	b	x1	x5
x0	$$0 - \frac{3*( - 4)}{6}$$	$$1\frac{- 3*\left( - 4 \right)}{6}$$	$$- \frac{4}{6}$$
x3	$$16 - \frac{3*( - 5)}{6}$$	$$2\frac{- 3*\left( - 5 \right)}{6}$$	$$- \frac{- 5}{6}$$
x4	$$9 - \frac{3*3}{6}$$	$$1\frac{- 3*3}{6}$$	$$- \frac{- 3}{6}$$
x2	$$\frac{3}{6}$$	$$\frac{- 3}{6}$$	1

Tablica 1:

	b	x1	x5
x0	2	-1	0.666667
x3	18.5	-0.5	0.833333
x4	7.5	2.5	0.5
x2	0.5	-0.5	1

Tworzenie tablicy 2 (iteracja 2.):

	b	x4	x5
x0	$$2 - \frac{7.5*( - 1)}{2.5}$$	$$\frac{- 1}{2.5}$$	$$\frac{2}{3} - \frac{0.5*( - 1)}{2.5}$$
x3	$$14 - \frac{7.5*(0.5)}{2.5}$$	$$\frac{- 0.5}{2.5}$$	$$\frac{5}{6} - \frac{0.5*( - 0.5)}{2.5}$$
x1	$$\frac{8}{2.5}$$	1	$$\frac{0.5}{2.5}$$
x2	$$1 - \frac{7.5*( - 0.5)}{2.5}$$	$$\frac{- 0.5}{2.5}$$	$$1 - \frac{0.5*( - 0.51)}{2.5}$$

Tablica 2:

	b	x4	x5
x0	5	0.4	0.866667
x3	20	0.2	0.933333
x1	3	1	0.2
x2	2	0.2	1.1

Zawiera optymalne rozwiązanie: x1 = 3, x2 = 2; max x0 = 5.

Rozwiązanie i ilość iteracji są zgodne z obliczeniami w Matlabie

1. Przykład II –zadanie nieograniczone, n=2

maxx₀ = 3x₁ + x₂

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

Rozwiązanie obliczone przy pomocy Matlaba:

x = 1.0e+016 * 1.0000 0	fval = -3.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 „0”:

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

Wszystkie wartości w kolumnie x4 są ujemne, a zatem zadanie jest nieograniczone.

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

Fabryka wytwarza 3 rodzaje produktu: x1, x2 i x3. Jedna z maszyn produkcyjnych potrzebuje 5 godzin na wyprodukowanie jednej sztuki x1, 2 godzin na wyprodukowanie jednej sztuki x2 oraz 4 godzin na wyprodukowanie jednej sztuki x3. Może ona pracować przez 60 godzin tygodniowo. Druga maszyna potrzebuje 3 godziny na wyprodukowanie jednej sztuki x1 i x3, oraz 2 godziny na wyprodukowanie jednej sztuki x2. Jej maksymalny tygodniowy czas pracy to 48 godzin. Zysk z jednej sztuki towaru x1 wynosi $80, z jednej sztuki x2 - $40, a z jednej sztuki x3 - $50. Opracuj optymalny cykl pracy tych maszyn w celu zmaksymalizowania tygodniowego zysku.

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

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

Rozwiązanie przy pomocy Matlaba:

x = 6 15 0	fval = 1080	exitflag = 1	output = iterations: 2 message: 'Optimization terminated.'

Rozwiązanie metodą tablicową simpleks:

Tablica „0”:

	b	x1	x2	x3
x0	0	-80	-40	-50
x5	60	5	2	4
x6	48	3	2	3

Tablica 1 (iteracja 1.):

	b	x5	x2	x3
x0	960	16	-8	14
x1	12	1	0.4	0.8
x6	12	-0.6	0.8	0.6

Tablica 2 (iteracja 2.):

	b	x5	x6	x3
x0	1080	1	25	29
x1	6	1.3	0.5	0.5
x2	15	-0.75	1	0.75

Zawiera optymalne rozwiązanie: x1 = 6, x2 = 15, x3 = 0; max x0 = 1080

Rozwiązanie i ilość iteracji są zgodne z obliczeniami w Matlabie.

1. Wnioski

W pierwszym przykładzie 3 proste ograniczające tworzą zamknięty obszar. Wzrost funkcji jest w tym przypadku powstrzymywany, a jej maksimum przypada w jednym punkcie (3, 2).

W drugim przykładzie proste ograniczające tworzą obszar otwarty, który nie powstrzymuje wzrostu funkcji celu. W związku z tym nie istnieje wartość maksymalna – zadanie jest nieograniczone.

Metody prymalnego simpleksu można używać do optymalizacji wielu procesów, na przykład maksymalizacji zysków w procesach produkcyjnych.