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ęteobsługi masowej, teoriajakości (np. koszt, zysk, niezawodność,
kryterium (wskaz
nik)
Teoria kolejek, teoria
ryzyko). Badaniem metod optymalizacji zajmuje się teoria optymalizacji.
ogonków: w badaniach operacyjnych jedna
z opartych na rachunku prawdopodobieństwa teorii
Analiza funkcjonalna: dział matematyki powstały
podejmowania Zajmuje
W literaturzeoptymalnych optymalizacjasię jest często nazywana
ekonomii
wdecyzji. w., zajmujący się badaniem faktów
XX
konstruowaniem i rozwiązywaniem modeli
z różnorodnych dziedzin za pomocą metod
programowaniem gospodarczym, niekiedywa-
mówi się też o badaniach
matematyczno-statystycznych, przydatnych
matematycznychw (równania całkowe, równania
operacyjnych. Zespółobsługi w krótkim podstawie których wyznacza się
zależności, na
runkach konieczności okresie
różniczkowe, algebra liniowa i inne). Analiza
optymalne rozwiązania (decyzje), nazywa się modelem matematycznym.
czasu dużej ilości klientów. Impulsem jej
funkcjonalnapowstania
znalazła
Jeżeli wszystkie zależności mają charakter funkcjiszerokie to mamy do
liniowych,zastosowanie
były badania dotyczące projektowania
w różnych dziedzinach wiedzy, jej rozwojowi
i eksploatacji central telefonicznych. Przedmiot liniowe), jeżeli
czynienia z optymalizacją liniową (programowanie, m.in.: S. Banach
Rachunek wariacyjny: dział analizy
zasłużyli się matematycy polscy
teorii obsługi masowej stosowanebadający warunki
nią
natomiast choć jednaoraz(uważany zaprzez nieliniowaSteinhaus, S.
z zależności jesttwórcę), H. - zosiąganiaMazur,
optymalizacją
matematycznej
jej
metody szczegółowewartości Orlicz, J.P Schauderprzez funkcjonały.
opisał wekstremalnych .
1955. rosyjski
nieliniową.
W.
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:
Znalez
ć minimum funkcji:
f (�x)�=� -�2x1 -�3x3
przy ograniczeniach:
x1 +� 2x2 +� x3 Ł� 3,
3x2 +� 4x3 Ł� 4,
2x2 +� 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)�=� 2x1 +� 3x3
Ograniczenia przyjmą postać:
x1 +� 2x2 +� x3 +� x4 =� 3,
3x2 +� 4x3 +� x5 =� 4,
2x2 +� 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
�� ł�
ę�0 3 4 0 1ś�
O =�
ę� ś�
ę� ś�
��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��
0
�� ł�
gdyż brakuje w niej wektora kolumnowego:
ę�0ś�
ę� ś�
ę�
- 6 -
��1ś�
��
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)�=� 2x1 +� 3x3 -� wx6
Przy ograniczeniach:
x1 +� 2x2 +� x3 +� x4 =� 3,
3x2 +� 4x3 +� x5 =� 4,
2x2 +� 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
dla Wektory
i
jednostkowych współczynników
prawych stronach
Jednostkowe
Budujemyi pierwszą tablicę  simplexów :
wektorów A ograniczeń
ograniczeń
wektory A
Współczynniki i
występujące przy
ci 2 0 3 0 0 -w
zmiennych xi w
funkcji celu f1(x)
Baza cb b A1 A2 A3 A4 A5 A6
Współczynniki
lewych stron
A1 2 3 1 2 1 1 0 0
ograniczeń
A5 0 4 0 3 4 0 1 0
A6 -w 1 0 2 1 0 0 1
"( cb��b
" (cb��Ai)-ci
Wskaz
niki) 6 - w 0 4 - 2w -1 - w 2 0 0
Iloczyn skalarny cb��b 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ść wskaz
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ż wskaz
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:
bA
3
1
r01 =� =� ,
A2 A1 2
bA
4
5
r05 =� =� ,
A2 A5 3
bA
1
6
r06 =� =�
A2 A6 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
'
bA =� bA -� r0 A2 A1 =� 3-� �� 2 =� 2,
1 1
2
1 5
'
bA =� bA -� r0 A2 A5 =� 4 -� ��3 =�
5 5
2 2
- 11 -
Optymalizacja liniowa  programowanie liniowe:
Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Wprowadzany do bazy wektor przyjmuje wartości jednostkowe, a
wskaz
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
Baza cb b A1 A2 A3 A4 A5
A1 2 2 1 0 0
5
A5 0 D 2 0 0 1
A2 0 � 0 1 0
Wskaz
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 poza-
bazowych:
A3A
1
6
r36 =� A3A ' =� =� ,
2
A2 A6 2
A4 A6 0
r46 =� A4 A2 ' =� =� =� 0
A2 A6 2
- 13 -
Optymalizacja liniowa  programowanie liniowe:
Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
ci 2 0 3 0 0
Baza cb b A1 A2 A3 A4 A5
A1 2 2 1 0 0
5
A5 0 D 2 0 0 1
A2 0 � 0 1 � 0 0
Wskaz
niki 4 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
A3A ' =� A3A -� r36A2 A1 =�1-� �� 2 =� 0,
1 1
2
A4 A1 ' =� A4 A1 -� r46A2 A1 =�1-� 0�� 2 =�1,
1 5
A3A ' =� A3A -� r36A2 A5 =� 4 -� ��3 =� ,
5 5
2 2
A4 A5 ' =� A4 A5 -� r46A2 A5 =� 0 -� 0��3 =� 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
5 5
A5 0 D 2 0 0 D 2 0 1
A2 0 � 0 1 � 0 0
Wskaz
niki 4 0 0 -3 2 0
- 16 -
Optymalizacja liniowa  programowanie liniowe:
Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Najmniejsza (najbardziej ujemna) wartość wskaz
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):
bA
2
1
r01 =� =� ,
A3A 0
1
5
bA
5 2
r05 =� =� =� 1,
5
A3A
5
2
1
bA
2 2
r02 =� =� =� 1
1
A3A
2
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 =� bA -� r0 A3A =� 2 -�1��0 =� 2,
1 1 1
5 5
'
bA =� bA -� r0 A3A =� -�1�� =� 0
5 5 5
2 2
- 18 -
Optymalizacja liniowa  programowanie liniowe:
Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
Wprowadzany do bazy wektor przyjmuje wartości jednostkowe, a
wskaz
niki odpowiadające wektorom bazowym będą zawsze wynosić 0.
Wartość funkcji celu wzrasta do 7.
Ci 2 0 3 0 0
Baza cb b A1 A2 A3 A4 A5
A1 2 2 1 0 0
A5 0 0 0 0 1
A3 3 1 0 1 0
Wskaz
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 poza-
bazowych:
A2 A2
1
r22 =� A2 A3 ' =� =� =� 2,
1
A3A
2
2
A4 A2
0
r42 =� A4 A3 ' =� =� =� 0
1
A3A
2
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 -� r22A3A =� 0 -� 2��0 =� 0,
1
A4 A1 ' =� A4 A1 -� r42A3A =�1-� 0��0 =�1,
1
5
A2 A5 ' =� A2 A5 -� r22A3A =� 0 -� 2�� =� -�5,
5
2
5
A4 A5 ' =� A4 A5 -� r42A3A =� 0 -� 0�� =� 0
5
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
Wskaz
niki 7 0 6 0 2 0
- 22 -
Optymalizacja liniowa  programowanie liniowe:
Przykład rozwiązania zadania optymalizacyjnego metodą SIMPLEX:
W dolnym wierszu (wskaz
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 -