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: [e-mail]
ewa.szlachcic.staff.iiar.pwr.wroc.pl
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.
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Literatura
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.
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Sformułowanie zadania optymalizacji
T
Wektor zmiennych decyzyjnych x:
x =[x1, x2,..., xn]
gdzie: n  ilość zmiennych decyzyjnych.
çÅ‚
Funkcja celu (funkcja kryterialna) f(x) : f (x): Rn çÅ‚ R1
oraz m funkcji ograniczeń gi(x):
gi(x): Rn çÅ‚ R1 dla i = 1,..., m
çÅ‚
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Zadanie optymalizacji polega na znalezieniu wektora zmiennych
decyzyjnych x, nale\
ącego do zbioru rozwiązań dopuszczalnych X w
postaci:
X = {x gi(x)d" 0, i =1,...,m}
takiego, \
e dla
"x"X
'"
ëÅ‚ öÅ‚
f x d" f (x )
ìÅ‚ ÷Å‚
'"
x íÅ‚ Å‚Å‚
Co jest równoznaczne zapisowi:
'"
ëÅ‚xöÅ‚
f (x)= f
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"X
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Przykłady praktycznych zastosowań:
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
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Zadanie programowania liniowego PL
max f (x)= cT x
przy ograniczeniach: m1 ograniczeń
A1x d" b1
A2 x e" b2 m2 ograniczeń
x e"0
dim x=n, dim c=n
Macierze A1, A2 odpowiadają za współczynniki w m1 i m2
ograniczeniach
dim A1 =[m 1 x n], dim A2 =[m 2 x n]
Wektory b1, b2 odpowiadają za prawe strony ograniczeń
dim b1=m1, dim b2=m2
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Zadanie programowania kwadratowego
max f (x)= 0.5xT Ax + bT x
x"X
gdzie::
X ={x :DT x d" e, x e" 0}
Przykład zadania programowania nieliniowego
2 2
min f (x) =(x1 - 2) +(x2 -1)
przy ograniczeniach:
2
x1 d" x2
x1 + x2 d" 2
Wydział Elektroniki
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic