Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Przykład I. Zadania sterowania siecią dystrybucji wody minimalizujące 
zuŜycie energii elektrycznej

Dana jest sieć dystrybucji wody w postaci:

m- węzłów, 

s - odbiorców  z odpowiednimi potrzebami, w których utrzymywane jest

odpowiednie ciśnienie oraz n łuków,

kaŜdy  łuk „i” charakteryzuje się przepływem y

i

:

Opis sieci:

spadek ciśnienia x

i

na łuku „i”:

gdzie: r

i

- opór hydrauliczny łuku „i”

d

i

- róŜnica wysokości geodezyjnych łuku „i”

Ograniczenia wynikające ze struktury sieci:

I prawo Kirchhoff’a:  

A – macierz incydencji dla węzłów sieci wodociągowej, 

II prawo Kirchhoff’a:     

B – macierz oczkowa dla węzłów sieci wodociągowej.

i

i

i

i

i

d

y

y

r

x

+

=

sgn

2

n

R

y∈

n

R

x∈

s

R

∈

σ

σ

=

y

A

0

=

x

B

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Sterowanie siecią dystrybucji wody minimalizujące zuŜycie energii 
elektrycznej

( )

i

n

i

i

y

f

y

f

∑

=

=

1

)

(

min

gdzie:

( )

i

i

i

i

i

i

i

i

i

y

d

y

y

r

y

x

y

f

+

=

=

sgn

3

przy ograniczeniach

:

σ

=

y

A

0

=

x

B

i

i

i

i

i

d

y

y

r

x

+

=

sgn

2

n

R

y∈

n

R

x∈

s

R

∈

σ

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Przykład II: Znaleźć najlepszą liniową aproksymację nieznanej funkcji 
określonej poprzez tabelę 20 pomiarów.

Wyznaczyć optymalne wartości wektora współczynników b=[b

1 

, b

2

, b

3

, b

4

]

formy liniowej :

gdzie:  u - wektor wielkości sterujących,  y - wektor wielkości wyjściowych 

Dane: tabela z 20 pomiarami wektora u  wielkości sterujących oraz wektora   wielkości 

wyjściowych 

dla następujących kryteriów jakości:

1.

minimum sumy wartości bezwzględnych róŜnic między wartościami wektora wyjść a 
wartościami otrzymanymi z modelu liniowego:

gdzie:     

- wartości zmierzone wielkości wyjściowych

i=1,...,20 - wielkości wyjściowe obliczone na podstawie 

modelu

Zadanie trudne do rozwiązania, poniewaŜ funkcja celu jest nie-róŜniczkowalna.

u

b

y

T

=

( )

∑

=

−

=

20

1

~

)

(

[

min

i

i

i

b

y

y

b

f

20

,...,

1

~

=

i

y

i

)

(b

y

i

( )

i

i

i

i

i

u

b

u

b

u

b

u

b

b

y

4

4

3

3

2

2

1

1

+

+

+

=

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

RównowaŜne zadanie programowania liniowego

Wprowadzono nową zmienną: 

Ø

Zwiększenie wymiaru zadania: 24 zmienne niezaleŜne

przy ograniczeniach:

dla i=1,...,20

Zadanie programowania liniowego:

Ø

funkcja celu jest wypukła

Ø

rozwiązano metodą dwufazową simpleks

.

.

Wektor b optymalnych wsp

Wektor b optymalnych wsp

ó

ó

ł

ł

czynnik

czynnik

ó

ó

w :

w :

( )

b

y

y

z

i

i

i

−

= ~

∑

=

=

20

1

)

(

min

i

i

z

b

f

i

i

i

i

i

i

i

z

u

b

u

b

u

b

u

b

y

z

≤

−

−

−

−

≤

−

4

4

3

3

2

2

1

1

~

87

,

51

1

=

b

232

,

1

2

=

b

122

,

0

3

−

=

b

08

,

1

4

−

=

b

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

2. minimum sumy kwadratów róŜnic między wartościami wektora wyjść a 

wartościami otrzymanymi z modelu liniowego:

gdzie:  

- wartości zmierzone wielkości wyjściowych

- i=1,...,20 - wielkości wyjściowe obliczone na podstawie 

modelu

Zadanie programowania nieliniowego:

funkcja celu jest wypukła

rozwiązano metodą gradientów sprzęŜonych w wersji Polak’a-Ribiere’y.

( )

(

)

2

20

1

~

)

(

[

min

∑

=

−

=

i

i

i

b

y

y

b

f

20

,...,

1

~

=

i

y

i

)

(b

y

i

( )

i

i

i

i

i

u

b

u

b

u

b

u

b

b

y

4

4

3

3

2

2

1

1

+

+

+

=

Wyniki identyfikacji zaleŜą od wyboru kryterium optymalizacji i przyjętej 

dokładności obliczeń.

28

,

39

1

=

b

07

,

1

2

=

b

16

,

0

3

=

b

94

,

0

4

−

=

b

Drugie kryterium jakości:

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Przykład III.  Zadanie wyznaczania optymalnego ukształtowania 
autostrady

Koszt budowy jest proporcjonalny do ilości podłoŜa dodawanego lub 
usuwanego

T – długość drogi, c(t) – wysokość terenu dla kaŜdego 

Autostrada będzie budowana na nierównym terenie

NaleŜy wyznaczyć wysokość drogi y(t) dla   

ZałoŜenia:



Warunki początkowe trasy: y(0) = a



Warunki końcowe trasy:      y(T) = b



Maksymalne nachylenie nie moŜe przekraczać b

1

dla uniknięcia 

nadmiernych spadków:



NaleŜy graniczyć szybkość zmian nachylenia drogi (wyeliminowanie 
garbów na jezdni):

( )

1

.

b

t

y

≤

( )

2

..

b

t

y

≤

[ ]

T

t

,

0

∈

∀

]

,

0

[ T

t∈

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Zadanie wyznaczania optymalnego ukształtowania autostrady
y(t)

Przy ograniczeniach:

dt

t

c

t

y

T

∫

−

0

)

(

)

(

min

( )

[ ]

T

t

dla

b

t

y

,

0

1

.

∈

≤

( )

[ ]

T

t

dla

b

t

y

,

0

2

..

∈

≤

a

y

=

)

0

(

T

b

y

=

)

(

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Przekształcenie zadania

:

ZałoŜenia: 



drogę naleŜy podzielić na K równych  odcinków o długości l, k=1,...,K



zmienna sterująca:  u(t)=y(t)-c(t)



zmienna modelu dynamicznego: 

Przyjmując oznaczenia:   y

1 

= y,     ,  

c(k) = c

k

,    y

1

(k) = y

1,k

,  y

2

(k) = y

2,k

Zadanie optymalizacji statycznej:

przy ograniczeniach:

Powstało zadanie optymalizacji liniowej z ograniczeniami większościowymi i 

mniejszościowymi.

)

(

)

(

.

t

y

t

x

=

∑

=

−

K

k

k

k

c

y

1

,

1

min

1

,

2

1

,

1

,

1

−

−

=

−

k

k

k

y

y

y

1

,

2

1

b

y

b

k

≤

≤

−

2

1

,

2

,

2

2

b

y

y

b

k

k

≤

−

≤

−

−

a

y =

0

,

1

b

y

k

=

,

2

.

2

y

y =

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Zadanie programowania ilorazowego:

( )

x

d

x

c

x

f

extr

T

T

=

przy ograniczeniach:

0

,

0

,

0

≥

≥

≥

x

d

c

oraz

b

x

A ≤

n

R

x∈

n

R

c∈

n

R

d ∈

1

:

R

X

f

→

dim A=[mxn]

m

R

b∈

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wykład 2

Wydział Elektroniki 
EiT III r. subkier. EKA

Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych    , 
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

Punkt       - minimum globalne funkcji f (x) na zbiorze X

∧

x

∧

x