Metody optymalizacji dr inż. Paweł Zalewski Akademia Morska w Szczecinie Zadaniem optymalizacji jest wyznaczenie spośród dopuszczalnych rozwiązań dane...
67 downloads
28 Views
1MB Size
Metody optymalizacji
dr inż. Paweł Zalewski Akademia Morska w Szczecinie
Optymalizacja - definicje: Zadaniem optymalizacji jest wyznaczenie spośród dopuszczalnych rozwiązań danego problemu rozwiązania najlepszego za względu na przyjęte kryterium (wskaźnik) koszt, zysk, niezawodność, Teoria obsługi masowej, teoriajakości kolejek,(np. teoria ryzyko). Badaniem metod optymalizacji ogonków: w badaniach operacyjnychzajmuje jedna się teoria optymalizacji. z opartych na rachunku prawdopodobieństwa teorii Analiza funkcjonalna: dział matematyki powstały podejmowania optymalnych decyzji. Zajmuje się W literaturze ekonomiiw XX optymalizacja jest się często nazywana w., zajmujący badaniem faktów konstruowaniem i rozwiązywaniem modeli z różnorodnych za też pomocą metod programowaniem gospodarczym, niekiedy dziedzin mówi się o badaniach matematyczno-statystycznych, przydatnych w wamatematycznych (równania całkowe, równania operacyjnych. Zespół obsługi zależności, na podstawie których wyznacza się runkach konieczności w krótkim okresie różniczkowe, algebra liniowa matematycznym. i inne). Analiza optymalne (decyzje), się modelem czasu dużejrozwiązania ilości klientów. Impulsemnazywa jej powstania funkcjonalna znalazła szerokie zastosowanie Jeżeli mają charakter funkcji liniowych, to mamy do były wszystkie badania zależności dotyczące projektowania w różnych dziedzinach wiedzy, jej rozwojowi i eksploatacji centralRachunek telefonicznych. Przedmiot czynienia z optymalizacją liniową (programowanie liniowe), jeżeli wariacyjny: dział m.in.: analizy zasłużyli się matematycy polscy, S. Banach teorii obsługi masowej oraz stosowanebadający przez nieliniowa nią warunki - zosiągania natomiast choć jedna z (uważany zależności optymalizacją matematycznej za jest jej twórcę), H. Steinhaus, S. Mazur, metody szczegółowe opisał w 1955 rosyjski nieliniową. wartości ekstremalnych funkcjonały. W. Orlicz, J.P. Schauder.przez matematyk A.J. Chinczin. Rachunek wariacyjny jest jedną z podstawowych metod fizyki matematycznej.
Do innych matematycznych metod optymalizacji należą: programowanie sieciowe (sieci neuronowe) i rozmyte, stochastyczne (polegające na wyborze decyzji „przeciętnie optymalnej”), teoria gier, teoria kolejek, rachunek wariacyjny, metody analizy funkcjonalnej. -2-
Optymalizacja liniowa – programowanie liniowe: Rozwiązanie zadania programowania liniowego metodą SIMPLEX:
Zadanie należy sprowadzić do postaci kanonicznej, to znaczy do postaci, w której poszukujemy maksimum funkcji przy ograniczeniach równościowych i wszystkich zmiennych nieujemnych, przy czym w tablicy ograniczeń musi dać się wyróżnić macierz jednostkowa, a prawe strony muszą być dodatnie. W przypadku poszukiwania minimum funkcji dla zależności liniowych:
min f x max f x , gdzie x jest wektorem argumentów funkcji f. Aby ograniczenia przekształcić w równości, dodajemy do lewych stron (lub odejmujemy) zmienne uzupełniające o wartościach dodatnich.
-3-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Znaleźć minimum funkcji:
f x 2 x1 3x3 przy ograniczeniach:
x1 2 x2 x3 3, 3x2 4 x3 4, 2 x2 x3 1, x1 , x2 , x3 0
-4-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Poszukiwanie minimum funkcji liniowej f(x) jest równoważne poszukiwaniu maksimum tej funkcji wziętej z przeciwnym znakiem, a więc funkcji:
f1 x f x 2 x1 3x3
Ograniczenia przyjmą postać:
x1 2 x2 x3 x4 3, 3 x2 4 x3 x5 4, 2 x2 x3 1, x1 , x2 , x3 , x4 , x5 0
-5-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Macierz ograniczeń, czyli tablica współczynników przy argumentach x1, x2, x3, x4, x5 w trzech równaniach ograniczeń ma postać:
1 2 1 1 0 O 0 3 4 0 1 0 2 1 0 0 W tablicy tej nie można jednak jeszcze wyróżnić macierzy jednostkowej:
1 0 0 0 1 0 , 0 0 1 gdyż brakuje w niej wektora kolumnowego:
0 0 1
-6-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Po lewej stronie trzeciego ograniczenia trzeba więc dodać zmienną „sztuczną” x6, która ten brak wyrówna. Aby zmienna x6 nie miała wpływu na rozwiązanie i aby można ją było szybko wyeliminować z zadania w trakcie jego rozwiązywania, uzupełniamy funkcję celu o składnik -wx6 z bardzo dużym współczynnikiem dodatnim w. W ten sposób niejako „pogarszamy” znacznie funkcję celu „oddalając” jej wartość (znacznie zmniejszając) od prawdziwego maksimum.
-7-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Zadanie przyjmie więc postać (kanoniczną) wyznaczenia maksimum funkcji celu f1(x):
max f1 x 2 x1 3x3 wx6
Przy ograniczeniach:
x1 2 x2 x3 x4 3, 3x2 4 x3 x5 4, 2 x2 x3 x6 1, x1 , x2 , x3 , x4 , x5 , x6 0
-8-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Wartości cWartości po Wektory i dla jednostkowych prawych współczynników stronach Jednostkowe Budujemy „simplexów”: Ai tablicę ograniczeń ograniczeń wektorywektorów Ai pierwszą Współczynniki występujące przy ci x w 2 0 zmiennych i funkcji celu f1(x)
Baza
cb
Współczynniki A1lewych 2stron ograniczeń
3
0
0
-w
b
A1
A2
A3
A4
A5
A6
3
1
2
1
1
0
0
A5
0
4
0
3
4
0
1
0
A6
-w
1
0
2
1
0
0
1
0
4 - 2w
-1 - w
2
0
0
∑( ) ∑ c(cbb Wskaźniki bAi)-ci 6 - w
Iloczyn skalarny cbb określa wartość funkcji celu w danym kroku, wektor b wartości zmiennych bazowych xi.
-9-
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Najmniejsza (najbardziej ujemna) wartość wskaźnika w dolnym wierszu wyznacza wektor, jaki w następnym kroku wprowadzimy do bazy. W naszym przypadku będzie to wektor A2. Rozwiązanie osiągniemy, gdy nie będzie już wskaźnika o wartości ujemnej. Wektor usuwany z bazy wyznacza się obliczając ilorazy charakterystyczne dla wszystkich dodatnich elementów wektora wprowadzanego do bazy (A2) według zależności:
r01 r05 r06
bA1 A2 A1 bA5 A2 A5 bA6 A2 A6
3 , 2 4 , 3
1 2
- 10 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Z bazy należy usunąć wektor, którego element występuje w ilorazie o najmniejszej wartości spośród wyznaczonych – w omawianym przykładzie będzie to wektor A6 (r06 = r0 = ½) Ponieważ jest to wektor odpowiadający zmiennej sztucznej, usuwamy go nie tylko z bazy, ale z całej tablicy simplexów. Wyznaczony iloraz r0 podaje jednocześnie nową wartość elementu wektora b w wierszu wektora wprowadzanego do bazy (b’A2 = r0, gdyż wprowadzamy wektor A2). Pozostałe dwa nowe elementy wektora b wyznacza się z zależności:
1 b bA1 r0 A2 A1 3 2 2, 2 1 5 bA' 5 bA5 r0 A2 A5 4 3 2 2 ' A1
- 11 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Wprowadzany do bazy wektor przyjmuje wartości jednostkowe, a wskaźniki odpowiadające wektorom bazowym (dolny wiersz tabeli simplexów) będą zawsze wynosić 0. Wartość funkcji celu wzrasta do 4. Ci
2
0
3
0
0
A3’
A4’
A5’
Baza
cb
b’
A1’
A2’
A1
2
2
1
0
0
A5
0
5⁄
2
0
0
1
A2
0
½
0
1
0
Wskaźniki
4
0
0
0 - 12 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Następnie należy wyznaczyć ilorazy kolumnowe dla wektorów pozabazowych:
r36 A3 A2 '
r46 A4 A2 '
A3 A6 A2 A6 A4 A6 A2 A6
1 , 2
0 0 2
- 13 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
ci
2
0
3
0
0
A3’
A4’
A5’
Baza
cb
b’
A1’
A2’
A1
2
2
1
0
0
A5
0
5⁄
2
0
0
1
A2
0
½
0
1
Wskaźniki
4
0
0
½
0
0 0
- 14 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Na podstawie otrzymanych ilorazów kolumnowych wyznacza się brakujące elementy tablicy:
1 A3 A1 A3 A1 r36 A2 A1 1 2 0, 2 ' A4 A1 A4 A1 r46 A2 A1 1 0 2 1, '
A3 A5 A3 A5 r36 A2 A5 '
A4 A5 A4 A5 r46 A2 A5 '
1 5 4 3 , 2 2 0 03 0
- 15 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Druga tablica simplexów:
ci
2
0
3
0
0
Baza
cb
b
A1
A2
A3
A4
A5
A1
2
2
1
0
0
1
0
A5
0
5⁄
2
0
0
5⁄
2
0
1
A2
0
½
0
1
½
0
0
Wskaźniki
4
0
0
-3
2
0 - 16 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Najmniejsza (najbardziej ujemna) wartość wskaźnika w dolnym wierszu wyznacza wektor, jaki w następnym kroku wprowadzimy do bazy. W naszym przypadku będzie to wektor A3. Wektor usuwany z bazy wyznacza się obliczając ilorazy charakterystyczne dla wszystkich dodatnich elementów wektora wprowadzanego do bazy (A3):
r01 r05 r02
bA1
A3 A1 bA5 A3 A5 bA2 A3 A2
2 , 0 5
2 1, 5 2 1 2 1 1 2
- 17 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Z bazy należy usunąć wektor, którego element występuje w ilorazie o najmniejszej wartości spośród wyznaczonych – mamy dwa takie wektory: A2 i A5. Wybieramy jeden z nich np. A2 (r02 = r0 = 1) Wyznaczony iloraz r0 podaje jednocześnie nową wartość elementu wektora b w wierszu wektora wprowadzanego do bazy (b’A3 = r0, gdyż wprowadzamy wektor A3). Pozostałe dwa nowe elementy wektora b wyznacza się z zależności:
bA' 1 bA1 r0 A3 A1 2 1 0 2, b bA5 r0 A3 A5 ' A5
5 5 1 0 2 2
- 18 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Wprowadzany do bazy wektor przyjmuje wartości jednostkowe, a wskaźniki odpowiadające wektorom bazowym będą zawsze wynosić 0. Wartość funkcji celu wzrasta do 7. Ci
2
0
3
0
0
A2’
A3’
A4’
A5’
Baza
cb
b’
A1’
A1
2
2
1
0
0
A5
0
0
0
0
1
A3
3
1
0
1
0
Wskaźniki
7
0
0
0 - 19 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Następnie należy wyznaczyć ilorazy kolumnowe dla wektorów pozabazowych:
r22 A2 A3
A2 A2
r42 A4 A3
A4 A2
'
'
A3 A2 A3 A2
1 2, 1 2 0 0 1 2
- 20 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Na podstawie otrzymanych ilorazów kolumnowych wyznacza się brakujące elementy tablicy:
A2 A1 A2 A1 r22 A3 A1 0 2 0 0, '
A4 A1 A4 A1 r42 A3 A1 1 0 0 1, '
A2 A5 A2 A5 r22 A3 A5 '
A4 A5 A4 A5 r42 A3 A5 '
5 0 2 5, 2 5 0 0 0 2
- 21 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Trzecia tablica simplexów:
ci
2
0
3
0
0
Baza
cb
b
A1
A2
A3
A4
A5
A1
2
2
1
0
0
1
0
A5
0
0
0
-5
0
0
1
A3
3
1
0
2
1
0
0
Wskaźniki
7
0
6
0
2
0 - 22 -
Optymalizacja liniowa – programowanie liniowe: Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
W dolnym wierszu (wskaźnikowym) nie ma już elementów ujemnych, a więc rozwiązano zadanie. Wartość funkcji f1(x) jest równa 7, a wartości zmiennych x1=2, x5=0, x3=1. Pozostałe zmienne (nie występujące w kolumnie b ostatniej tablicy simplexów) są równe zeru (x2=0, x4=0). Zatem pomijając zmienne sztuczne otrzymujemy ostateczne rozwiązanie zadania dla funkcji f(x), dla której poszukiwaliśmy minimum:
min f 2,0,1 7
- 23 -