TECHNIKA
OPTYMALIZACJI
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Subkierunek: Elektronika
dr inż. Ewa Szlachcic
Zakład Sterowania i Optymalizacji
Instytut Informatyki, Automatyki i Robotyki
Politechnika Wrocławska
pok. 219 C-3
email: ewa.szlachcic@pwr.wroc.pl
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Program wykładu
Wprowadzenie
Definicja zadania optymalizacji i jego klasyfikacja
Przykłady praktycznych zadań optymalizacji
Metody programowania liniowego PL
Metody programowania nieliniowego PN:
Metody optymalizacji bez ograniczeń
Metody optymalizacji z ograniczeniami
Przegląd metod optymalizacji lokalnej i globalnej
Techniki meta-heurystyczne optymalizacji – oparte nie tylko na biologii
(algorytmy genetyczne, ewolucyjne, immunologiczne, mrówkowe,
algorytmy optymalizacji rojem cząstek, poszukiwania harmonii)
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Stachurski A., Wierzbicki A.P., Podstawy optymalizacji, PWN
Warszawa 1999
Cegielski A. Programowanie matematyczne, Wyd. Uniw. Zielonog.
2004
Findeisen S., Szymanowski W., Wierzbicki A., Teoria i metody
obliczeniowe optymalizacji, PWN, 1987
Garfinkel R.S, Nemhauser G.L., Programowanie całkowitoliczbowe,
PWN, Warszawa, 1978
Michalewicz Z., Algorytmy genetyczne+struktury danych=
programy ewolucyjne, WNT Warszawa, 1999
Arabas J., Wykłady z algorytmów ewolucyjnych, WNT Warszawa,
2001
Wierzchoń S.T., Sztuczne systemy immunologiczne, Teoria i
zastosowania, EXIT Warszawa, 2002.
Literatura
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Programowanie liniowe. Podstawy teoretyczne PL. Warunki
konieczne i dostateczne optymalizacji liniowej. Metody simpleks,
dwufazowy simpleks, dualny simpleks. Inne algorytmy liniowe.
Programowanie liniowe ze zmiennymi rzeczywistymi,
programowanie liniowe ze zmiennymi dyskretnymi.
w tym:
Programowanie całkowitoliczbowe liniowe
Metody odcięć. Metody podziału i ograniczeń. Klasyczne zadania
optymalizacji dyskretnej (problem plecakowy, przydziału,
komiwojażera, problemy szeregowania zadań.), przepływy w
sieciach i zadania transportowe.
Programowanie nieliniowe. Podstawy teoretyczne PN. Warunki
konieczne i wystarczające optymalności. Metody dokładne i
heurystyczne (m.in.. genetyczne i ewolucyjne) poszukiwania
ekstremum bez ograniczeń i z ograniczeniami
.
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Wektor zmiennych decyzyjnych x:
gdzie: n – ilość zmiennych decyzyjnych.
Funkcja celu (funkcja kryterialna) f(x) :
oraz m funkcji ograniczeń g
i
(x):
[
]
T
n
x
x
x
,...,
,
2
1
=
x
( )
1
:
R
R
f
n
→
x
( )
m
i
dla
R
R
g
n
i
,...,
1
:
1
=
→
x
Sformułowanie zadania optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x,
należącego do zbioru rozwiązań dopuszczalnych X w postaci:
takiego, że dla
}
,...,
1
,
0
)
(
{
m
i
g
i
X
=
≤
=
x
x
X
∈
∀x
Co jest równoznaczne zapisowi:
∧
x
( )
x
x
f
f
≤
∧
( )
=
∧
∈
x
x
x
f
f
X
min
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Optymalne projektowanie procesów technologicznych, sieci
elektrycznych, sieci rezystorów, aparatury elektronicznej
Identyfikacja procesów technologicznych
Optymalne zarządzanie przedsiębiorstwem - minimalizacja kosztów,
maksymalizacja zysków w przedsiębiorstwie
Polioptymalne zadanie dla modelu gospodarki narodowej (np.:
maksymalizacja konsumpcji i środków trwałych oraz minimalizacja
poziomu zadłużenia zagranicznego gospodarki)
Sterowanie procesem technologicznym
Projektowanie efektywnej struktury systemu (np. sieci komputerowej)
Projektowanie optymalnego przepływu w sieciach ( sieci dystrybucji
wody, sieci dystrybucji gazu, sieci komputerowej)
Zadania optymalnego przydziału, zadania dystrybucji produktów
Zadania optymalnego rozmieszczenia ( minimalizacja strat czy
odpadów- optymalny rozkrój , optymalne cięcie, optymalny kształt)
Przykłady praktycznych zastosowań
:
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Zadanie programowania liniowego PL
przy ograniczeniach
:
( )
x
c
x
T
f
=
max
0
2
2
1
1
≥
≥
≤
x
b
x
A
b
x
A
dim x=n, dim c=n
Macierze A
1
, A
2
odpowiadają za współczynniki w m
1
i m
2
ograniczeniach
dim A
1
=[m
1
x n], dim A
2
=[m
2
x n]
Wektory b
1
, b
2
odpowiadają za prawe strony ograniczeń
dim b
1
=m
1
, dim b
2
=m
2
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r EKA
III r EKA
.
.
Zadanie programowania kwadratowego
(
) (
)
2
2
2
1
1
2
)
(
min
−
+
−
=
x
x
f x
( )
x
b
Ax
x
x
x
T
T
X
f
+
=
∈
5
.
0
max
gdzie:
:
{
}
0
,
:
≥
≤
=
x
e
x
D
x
T
X
Przykład zadania programowania nieliniowego
przy ograniczeniach:
2
2
1
2
2
1
≤
+
≤
x
x
x
x