METODY NUMERYCZNE I
OPTYMALIZACJA

Wydział Elektroniki
Kier. Automatyka i Robotyka III r.

dr inż. Ewa Szlachcic

Zakład Sterowania i Optymalizacji

Instytut Informatyki, Automatyki i Robotyki

Politechnika Wrocławska

pok. 219 C-3

email:

[e-mail]

Materiały: ewa.szlachcic.staff.iiar.pwr.wroc.pl

Wydział Elektroniki

AiR III r.

Program wykładu



Wprowadzenie do metod numerycznych i zadań optymalizacji



Definicja zadania optymalizacji i jego klasyfikacja



Przykłady praktycznych zadań optymalizacji



Metody rozwiązywania układów równań liniowych



Metody rozwiązywania równania nieliniowego



Metody rozwiązywania układu równań nieliniowych



Metody aproksymacji funkcji



Metody interpolacji funkcji



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

AiR III r.

Literatura cz. 1 Metody numeryczne



Klamka J., Ogonowski Z., Jamicki M., Stasik M., Metody

numeryczne, Wyd. Pol Śląskiej Gliwice 2004



Majchrzak E., Mochnacki B., Metody numeryczne, Podstawy

teoretyczne, aspekty praktyczne i algorytmy, Wyd. Pol Śląskiej
Gliwice 2004



Povstenko J., Wprowadzenie do metod numerycznych, Wyd. Akad.
Ofic. Wyd. EXIT, Warszawa 2002



Fortuna Z., Macukow B., Wąsowski J., Metody numeryczne, WNT
Warszawa 1998



Wanat K., Algorytmy numeryczne, Wyd. Dir, Gliwice, 1993



Bjorck A., Dahlquist G., Metody numeryczne, PWN 1987



Ralston A., Wstęp do analizy numerycznej, PWN, Warszawa, 1983



Dryja M., Jankowscy J. i M., Przegląd metod i algorytmów

numerycznych, WNT, Warszawa 1982

Wydział Elektroniki

AiR III r.



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.

Literatura cz.2 Metody optymalizacji

Wydział Elektroniki

AiR III r.

Układy równań liniowych

Należy rozwiązać układ m równań liniowych z n niewiadomymi:

T

n

x

x

x

x

]

,...,

,

[

2

1

n

j

i

j

ij

b

x

a

1

(i=1,2,3,…,m)

lub w zapisie macierzowym:

b

Ax

gdzie: A = [a

ij

] jest macierzą współczynników stopnia [m*n]

x-wektor niewiadomych,

b- wektor wyrazów wolnych.

T

m

b

b

b

b

]

,...,

,

[

2

1

Wydział Elektroniki

AiR III r.

Układy równań nieliniowych

0

)

,...,

,...,

,

(

........

..........

..........

..........

0

)

,...,

,...,

,

(

0

)

,...,

,...,

,

(

2

1

2

1

2

2

1

1

n

i

n

n

i

n

i

x

x

x

x

f

x

x

x

x

f

x

x

x

x

f

0

)

(x

F

x

f

x

f

x

f

x

f

x

F

n

i

...

...

)

(

2

1

Układ n równań nieliniowych zawierający n niewiadomych:

lub w postaci macierzowej

gdzie:

n

i

x

x

x

x

x

...

...

2

1

Wydział Elektroniki

AiR III r.

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ł Elektroniki

AiR III r.

Zadanie optymalizacji polega na znalezieniu wektora zmiennych
decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X w
postaci:

takiego, że dla

}

,...,

1

,

0

)

(

{

m

i

g

i

X

x

x

X

x

Co jest równoznaczne zapisowi

:

x

x

x

f

f

x

x

x

f

f

X

min

Wydział Elektroniki

AiR III r.



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

AiR III r.



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



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ń

:

Wydział Elektroniki

AiR III r.

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ł Elektroniki

AiR III r.

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