SPRAWOZDANIE Z LABORATORIUM Techniki Optymalizacji
Skład grupy: Krzysztof Zielonka Jacek Guzowski

Ćwiczenie I Zadanie programowania liniowego dla ograniczeń mniejszościowych METODA PRYMALNA SIMPLEKS	Ocena:

1. Wstęp teoretyczny

Celem ćwiczenia było zapoznanie się z zagadnieniem rozwiązywania układów programowania liniowego metodą prymalną simpleks. Istota metody Simpleks polega na badaniu rozwiązań bazowych. Mając rozwiązanie bazowe sprawdzamy, czy jest ono optymalne, czy nie. Jeśli dane rozwiązanie bazowe nie jest optymalne badamy następne rozwiązanie bazowe lepsze lub przynajmniej nie gorsze od poprzedniego, aż do momentu znalezienia rozwiązania optymalnego.

Zadanie programowania liniowego PL dla ograniczeń mniejszościowych

przy ograniczeniach przedstawia się następująco

przy ograniczeniach:

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

Metoda prymalnego simpleksu pozwala na wyliczenie wektora zmiennych decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X.

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

1. 
   Zadania testowe

   1. Zadanie PL ograniczone, , jedno rozwiązanie optymalne

• Funkcja celu:

max x₀= x₁ + 2x₂

• Postać ograniczeń:

• Wykres ograniczeń:

Rysunek 1: Wykres wykonano w programie Graph

Rozwiązanie zadania za pomocą tablicowej metody simpleks

Wprowadzenie zmiennych bazowych x₃, x₄, x₅ do nierówności ograniczających:

Algorytm postępowania w celu wyznaczenia rozwiązania optymalnego:

Tabela 1: Pierwsza tablica simpleksowa

	x0	x1	x2↑
x0	0	-1	-2
←x3	3	-2	1
x4	6	1	1
x5	20	5	2

= [x₃,x₄,x₅, x₁, x₂]^T=[3, 6, 20, 0, 0]^T

x₀=0

Jeżeli w pierwszym wierszu tabeli występuje jeden współczynnik mniejszy od zera, to możemy polepszyć rozwiązanie. W przypadku wystąpienia więcej niż jednego współczynnika mniejszego od zera, wybieramy najmniejszy. Indeks kolumny j wskazuje nam x_j wchodzące do bazy. W naszym przypadku x₂.

Wybieramy zmienną wychodzącą z bazy. Dzielimy wyraz wolny przez tylko dodatnie współczynniki w kolumnie x₂ (3/1, 6/1, 20/2). Mniejszy stosunek wskazuje nam punkt centralny, czyli dla kolumny x₂ jest to 1. Indeks wiersza wskazuje nam wyraz wychodzący z bazy. W naszym przypadku x₃.

Iteracja 1: Metodą eliminacji Gaussa, wyznaczamy drugą tablice simpleksową.

Tabela 2: Druga tablica simpleksowa

	x0	x1↑	x3
x0	6	-5	2
x2	3	-2	1
←x4	3	3	-1
x5	14	9	-2

= [x₂,x₄,x₅, x₁, x₃]^T=[3, 3, 14, 0, 0]^T

x₀=6

W wierszu pierwszym występuje przynajmniej jeden współczynnik mniejszy od zera, a wiec możliwe jest polepszenie wyniku. Powtarzamy czynność.

– Iteracja 2: Metodą eliminacji Gaussa, wyznaczamy trzecią tablice simpleksową.

Tabela 3: Trzecia tablica simpleksowa

	x0	x4	x3
x0	11	5/3	1/3
x2	5	2/3	1/3
x1	1	1/3	-1/3
x5	5	3	1

W pierwszym wierszu tabeli nie ma już żadnego współczynnika ujemnego, a więc nie można polepszyć wyniku. Optymalne rozwiązanie wygląda następująco:

= [x₂,x₁,x₅, x₄, x₃]^T=[5, 1, 5, 0, 0]^T

=11

Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

Optimization terminated.

x =

1

5

fval =

-11

exitflag =

1

output =

iterations: 2

algorithm: 'medium scale: simplex'

cgiterations: []

message: 'Optimization terminated.'

constrviolation: 0

firstorderopt: 2.2204e-016

lambda =

ineqlin: [3x1 double]

eqlin: [0x1 double]

upper: [2x1 double]

lower: [2x1 double]

1. Zadanie PL nieograniczone,

• Funkcja celu:

max x₀= x₁ + 2x₂

• Postać ograniczeń:

• Wykres ograniczeń:

Rysunek 2: Wykres wykonano w programie Graph

Rozwiązanie zadania za pomocą tablicowej metody simpleks

Wprowadzenie zmiennych bazowych x₃, x₄, x₅ do nierówności ograniczającej:

Postępujemy zgodnie z algorytmem podanym powyżej:

Tabela 4: Pierwsza tablica simpleksowa

	x0	x1	x2↑
x0	0	-1	-2
←x3	3	-2	1

-Aktualne rozwiązanie bazowe dopuszczalne:

= [x₃, x₁, x₂]^T=[2, 0, 0]^T

x₀=0

Mamy możliwość poprawienia wyniku, a więc tworzymy drugą tablice simpleksową

Iteracja 1:

Tabela 5: Druga tablica simpleksowa

	x0	x1	x3
x0	4	-3	2
x2	2	-1	1

Rozwiązanie zadania nie jest możliwe, ponieważ żadne ograniczenie nie wstrzymuje wzrostu funkcji celu.

Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab :

Exiting: The problem is unbounded; the constraints are not restrictive enough.

x =

1.0e+016 *

1.0000

1.0000

fval =

-3.0000e+016

exitflag =

-3

output =

iterations: 1

algorithm: 'medium scale: simplex'

cgiterations: []

message: [1x78 char]

constrviolation: 0

firstorderopt: 2

lambda =

ineqlin: 0

eqlin: [0x1 double]

upper: [2x1 double]

lower: [2x1 double]

2. Zadanie PL,, wymiar 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.

• Funkcja celu:

max x₀ [$]= 80[$/szt.]x₁[szt.] + 40[$/szt.]x₂[szt.] + 50[$/szt.]x₃[szt.]

• Postać ograniczeń:

• Rozwiązanie zadania za pomocą tablicowej metody simpleks

  • Wprowadzenie zmiennych bazowych x₄, x₅, x₆ do nierówności ograniczającej

  • Postępujemy zgodnie z algorytmem podanym w pkt. 2.1:

Tabela 6: Pierwsza tablica simpleksowa

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

-Aktualne rozwiązanie bazowe dopuszczalne:

= [x₅,x_6,x₁,x₂,x₃]^T=[60, 48, 0, 0, 0]^T

x₀=0

-Jak widać, rozwiązanie można polepszyć, a więc tworzymy nową tablicę simpleksową.

-Iteracja 1: Tworzenie nowej tablicy simpleksowej

Tabela 7: Druga tablica simpleksowa

	x0	x5	x2↑	x3
x0	960	16	-8	14
x1	12	1	0,4	0,8
←x6	12	-0,6	0,8	0,6

-Aktualne rozwiązanie bazowe dopuszczalne:

= [x₁,x_6,x₅,x₂,x₃]^T=[12, 12, 0, 0, 0]^T

x₀=0

-Jak widać, rozwiązanie można polepszyć, a więc tworzymy nową tablicę simpleksową.

-Iteracja 2: Tworzenie nowej tablicy simpleksowej

Tabela 7: Trzeci tablica simpleksowa

	x0	x5	x6	x3
x0	1080	1	25	29
x1	6	1,3	0,5	0,5
x2	15	-0,75	1	0,75

-Rozwiązanie nie może być już polepszone.

-A więc optymalne rozwiązanie wygląda następująco:

= [x₁,x₂,x_5,x₆,x₃]^T=[6, 15,1, 25 , 29]^T

=1080

Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

x =

6.0000

15.0000

0

fval =

-1080

exitflag =

1

output =

iterations: 2

algorithm: 'medium scale: simplex'

cgiterations: []

message: 'Optimization terminated.'

constrviolation: 0

firstorderopt: 0

lambda =

ineqlin: [2x1 double]

eqlin: [0x1 double]

upper: [3x1 double]

lower: [3x1 double]

1. Wnioski:

   1. , jedno optymalne rozwiązanie

Zadanie testowe, jest zadaniem PL ograniczonym z jednym optymalnym rozwiązaniem. Funkcję celu ograniczają 3 funkcje ograniczające. Część wspólna ograniczeń jest przedstawiona na wykresie kolorem szarym. Problem rozwiązano za pomocą tablicowej metody simpleks, algorytm potrzebował 2 iteracji do otrzymania wartości optymalnej funkcji celu. Wartość optymalna to =11, dla x₁=1, x₂=5. Do tego podpunktu dołączono wynik działania matlaba, z użyciem funkcji linprog. Jak widać dla x=[1,5] mamy fval=-11 ( max f(x)=-min [-f(x)], a więc =11), liczba iteracji to 2, exitflag=1 co oznacza, że algorytm znalazł jedno rozwiązanie optymalne, oraz algorithm: 'medium scale: simplex' mówi, że algorytm opierał się na metodzie simpleks.

1. Zadanie PL nieograniczone,

Zadanie testowe jest zadaniem PL nieograniczonym o nieskończonej liczbie rozwiązań. Ograniczenia nie zatrzymują wzrostu wartości funkcji celu, przez co liczba punktów optymalnych jest nieograniczona. Wynik zwrócony po wykonaniu funkcji linprog przez program Matlab dla tego przypadku, zwrócił informacje o nieograniczonym problemie (‘The problem is unbounded’) i nieskończonej liczbie rozwiązań. Warto zwrócić uwagę również na exitflag którego wartość równa się -3, co potwierdza powyższą informacje o nieograniczonym zadaniu. Zadanie nie ma rozwiązania optymalnego.

1. Zadanie PL,, wymiar n>2

Zadanie testowe jest zadaniem PL trójwymiarowym. Funkcja celu ograniczona jest 2 funkcjami ograniczającymi. Wartość optymalną funkcji celu otrzymujemy po dwóch iteracjach algorytmu simpleks i wynosi ona:

Literatura:

-https://www.dropbox.com/s/gqasxqejgvip5os/zadanie.txt

- dr Ewa Szlachcic - Zadania testowe dla programowania liniowego

-http://simplex.republika.pl/

-Andrzej P. Wierzbicki, Andrzej Stachurski – „Podstawy optymalizacji”