Laboratorium	Technika optymalizacji
Autorzy:	Wrocław, 20.11.2012 Prowadzący: Dr inż.. Ewa Szlachcic
Ćwiczenie I	Metoda prymalna simpleks

1. Wstęp

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.

2. Opis opracowanego zadania, interpretacja graficzna problemu.

2.1. , jedno optymalne rozwiązanie.

Rysunek 1

Sposób rozwiązania:

Doprowadzamy ograniczenia do postaci kanonicznej:

Tworzymy tablicę simpleks:

	b	-x1	-x2
x0	0	-1	2
x3	5	-2	1
x4	8	1	1
x5	10	5	2

1. Warunek dopuszczalności jest spełniony - w pierwszej kolumnie nie występują elementy ujemne.

2. Tablica nie przedstawia rozwiązania optymalnego, ponieważ w pierwszym wierszu występuje element ujemny.

3. Najmniejsza wartość w pierwszym wierszu min{0, -1, 2} = -1.

4. Wyznaczamy punkt centralny (nie bierzemy pod uwagę elementów ujemnych)
min{8/1, 10/5} = 10/5; s=5

5. Metodą eliminacji Gaussa tworzymy nową tablicę:

.

-nowa wartość w tablicy, -stara wartość w tablicy, s – element centralny

	b	-x5	-x2
x0	0-((10*(-1)/5)=2	1/5	2-((-1*2)/5) =12/5
x3	5-((10*(-2))/5=9	2/5	1-((-2*2)/5) =9/5
x4	8-((10*1)/5)=6	-1/5	1-((1*2)/5)=3/5
x1	2	1/5	2/5

Otrzymana tablica zawiera rozwiązanie optymalne, ponieważ w wierszu x0 brak jest elementów ujemnych

x₁ = 2; x₂ = 0;

Wartość funkcji celu:

x₀ = 2;

Kod i wyniki z Matlaba:

f=[1;-2];

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

b=[5;8;10];

lb=zeros(2,1);

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

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

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

2. Zadania nieograniczone , n=2

Rysunek 2

Tworzymy tablicę simplex

1.

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

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

Wyniki i kod z matlaba:

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

f=[1;1];

A=[-1 1];

b=[2];

lb=zeros(2,1);

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

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

2.3 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 i kod z Matlaba:

f=[-80;-40;-50];

A=[5 2 4;3 2 3];

b=[60;48];

lb=[0;0;0];

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

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

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, ponieważ w wierszu x0 brak jest elementów ujemnych : 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 (2, 0).

W drugim przykładzie prostq ograniczajądq tworzy 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