TEORIA I METODY
OPTYMALIZACJI
Wydział Elektroniki
Kier. Automatyka i Robotyka
Studia II st.
dr in\
. Ewa Szlachcic
Zakład Sterowania i Optymalizacji
Instytut Informatyki, Automatyki i Robotyki
Politechnika Wrocławska
pok. 219 C-3
email: [e-mail]
Zaliczenie przedmiotu
Wykonanie i oddanie projektu ( przed terminem kolokwium 
zgodnie z ustalonym harmonogramem dla ka\
dej grupy
projektowej)
Kolokwium z wykładu w terminie: 7.06.2011 r.
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Program wykładu
Wprowadzenie do zagadnień optymalizacji
Definicja zadania optymalizacji i jego klasyfikacja
Metody programowania liniowego PL
Metody programowania liniowego dla zmiennych
całkowitoliczbowych PCL
Metody programowania nieliniowego PN:
Metody optymalizacji bez ograniczeń
Metody optymalizacji z ograniczeniami
Metod optymalizacji lokalnej
Metody optymalizacji globalnej
Techniki meta-heurystyczne optymalizacji  (algorytmy
genetyczne, ewolucyjne, immunologiczne, mrówkowe, algorytmy
optymalizacji rojem czÄ…stek, poszukiwania harmonii)
Zadania optymalizacji wielokryterialnej
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Literatura
Stadnicki J., Teoria i praktyka rozwiązywania zadań optymalizacji z
przykładami zastosowań technicznych, WNT, Warszawa, 2006.
Kusiak J., Danielewska-Tułecka A., Oprocha P., Optymalizacja
Wybrane metody z przykładami zastosowań, PWN, Warszawa,
2009.
Cegielski A. Programowanie matematyczne, Wyd. Uniw. Zielonog.
2004
Stachurski A., Wierzbicki A.P., Podstawy optymalizacji, PWN
Warszawa 1999
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
AiR studia II st.
AiR studia II st.
 Programowanie liniowe. Podstawy teoretyczne PL. Warunki
konieczne i dostateczne optymalizacji liniowej. Metody simpleks,
dwufazowy simpleks, dualny simpleks. 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 dyskretne ( binarne)
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.
Programowanie całkowitoliczbowe nieliniowe
Programowanie mieszane
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Sformułowanie zadania optymalizacji
Wektor zmiennych decyzyjnych x:
T
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 çÅ‚ dla i =1,...,m
çÅ‚ R1
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
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
'" '"
ëÅ‚ öÅ‚
x
f x d" f (x )
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
Co jest równoznaczne zapisowi:
'"
ëÅ‚xöÅ‚
f (x)= f
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"X
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Przykłady praktycznych zastosowań:
Optymalne projektowanie procesów technologicznych
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
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Przykłady praktycznych zastosowań cd.:
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
AiR studia II st.
AiR studia II st.
Podział zadań optymalizacji
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Zadanie programowania liniowego PL
max f (x)= cT x
przy ograniczeniach:
A1x d" b1
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
AiR studia II st.
AiR studia II st.
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
AiR studia II st.
AiR studia II st.
Przykład nieliniowego zadania optymalizacji z ograniczeniami
min f (x) = 2(x1)2 + 4x1(x2 )3 -10x2x1 + (x2 )2
x"X
2
X = {(x , x ) | x (x ) (2.4 + x ) d" 3
1 2 1 2 2
'" 3/ 2x + x e" 0
1 2
'" (-3 d" x d" 3,i = 1,2)}.
i
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.
Wydział Elektroniki
Wydział Elektroniki
AiR studia II st.
AiR studia II st.