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]

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.