TECHNIKA
OPTYMALIZACJI
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Potok: 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
ewa.szlachcic.staff.iiar.pwr.wroc.pl
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Program wykładu
Wprowadzenie
Definicja zadania optymalizacji i jego klasyfikacja
Przykłady praktycznych zadań optymalizacji
Techniki programowania liniowego PL
Techniki programowania nieliniowego PN:
Algorytmy optymalizacji bez ograniczeń
Algorytmy optymalizacji z ograniczeniami
Przegląd algorytmów optymalizacji lokalnej i globalnej
Techniki meta-heurystyczne optymalizacji – oparte nie tylko na
biologii.
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Stachurski A., Wierzbicki A.P., Podstawy optymalizacji, PWN
Warszawa 1999
Cegielski A. Programowanie matematyczne, Wyd. Uniw. Zielonog.
2004
Stadnicki J., Teoria i praktyka rozwiązywania zadań optymalizacji z
przykładami zastosowań technicznych, WNT, Warszawa, 2006.
Findeisen S., Szymanowski W., Wierzbicki A., Teoria i metody
obliczeniowe optymalizacji, PWN, 1987
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
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Optymalne projektowanie procesów technologicznych, sieci elektrycznych, sieci
rezystorów, aparatury elektronicznej
Optymalizacja sieci telekomunikacyjnej, sieci bezprzewodowej, sieci radiowej, sieci
światłowodowej
Optymalizacja sieci szkieletowej
Optymalizacja wykorzystania zasobów w planowaniu rozbudowy sieci
telekomunikacyjnej
Optymalne zarządzanie przedsiębiorstwem - minimalizacja kosztów, maksymalizacja
zysków w przedsiębiorstwie
Projektowanie efektywnej struktury sieci złożonej (np. sieci komputerowej)
Projektowanie optymalnego przepływu w sieciach (rozległe sieci komputerowe, sieci
dystrybucji wody, sieci dystrybucji gazu)
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)
Planowanie i optymalizacja wielokryterialna
Optymalizacja portfela akcji
Przykłady praktycznych zastosowań
:
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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
m
1
ograniczeń
m
2
ograniczeń
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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