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: [e-mail]
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)
Wydział Elektroniki
Wydział Elektroniki
EiT III r EKA.
EiT III r EKA.
Dr in\
. Ewa Szlachcic
Literatura
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.
Wydział Elektroniki
Wydział Elektroniki
EiT III r EKA.
EiT III r EKA.
Dr in\
. Ewa Szlachcic
 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.
Wydział Elektroniki
Wydział Elektroniki
EiT III r EKA.
EiT III r EKA.
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
EiT III r EKA.
EiT III r EKA.
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 (x)d" 0, i =1,...,m}
gi
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
EiT III r EKA.
EiT III r EKA.
Dr in\
. Ewa Szlachcic
Przykłady praktycznych zastosowań:
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)
Wydział Elektroniki
Wydział Elektroniki
EiT III r EKA.
EiT III r EKA.
Dr in\
. Ewa Szlachcic
Zadanie programowania liniowego PL
max f (x)= cT x
A1x d" b1
przy ograniczeniach:
A2 x e" b2
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
EiT III r EKA.
EiT III r EKA.
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
EiT III r EKA.
EiT III r EKA.
Dr in\
. Ewa Szlachcic