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: ewa.szlachcic@pwr.wroc.pl
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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
Wydzia
ł
ł
Elektroniki
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
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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.
Literatura
Wydzia
Wydzia
ł
ł
Elektroniki
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
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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
Wydzia
Wydzia
ł
ł
Elektroniki
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:
takiego, Ŝe dla
{
}
m
i
g
x
X
i
,...,
1
,
0
)
(
=
≤
=
x
X
∈
∀x
Co jest równoznaczne zapisowi
:
∧
x
( )
x
x
f
f
≤
∧
( )
=
∧
∈
x
x
x
f
f
X
min
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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
Przykłady praktycznych zastosowań
:
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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ń cd.
:
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
Podział zadań optymalizacji
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
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
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.
2
2
1
2
3
2
1
2
1
)
(
10
)
(
4
)
(
2
)
(
min
x
x
x
x
x
x
x
f
X
x
+
−
+
=
∈
)}.
2
,
1
,
3
3
(
0
2
/
3
3
)
4
.
2
(
)
(
|
)
,
{(
2
1
2
2
2
1
2
1
=
≤
≤
−
∧
≥
+
∧
≤
+
=
i
x
x
x
x
x
x
x
x
X
i
Przykład nieliniowego zadania optymalizacji z ograniczeniami
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
AiR studia II st.
AiR studia II st.