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