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: ewa.szlachcic@pwr.wroc.pl

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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)

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.



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

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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

. 

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.



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)

Przykłady praktycznych zastosowań

:

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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

Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r    EKA

III r    EKA

.

.

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