Akademia Techniczno-Humanistyczna

w Bielsku – Bia

áej

Katedra Mechaniki

i In

Īynierskich Metod Komputerowych

Bielsko – Bia

áa 2002

Dr hab. in

Ī. Jacek Stadnicki

prof. Akademii Techniczno - Humanistycznej

Optymalizacja

Spis tre

Ğci

- Ra-V

Formu

áowanie problemu optymalizacji ..............................1

Sformu

áowanie zadania ...........................................................2

Etapy formu

áowania i rozwiązywania zadania optymalizacji .2

Programowanie liniowe ........................................................3

Posta

ü ogólna zagadnienie programowania liniowego............3

Linowy model produkcji .........................................................4

Problem mieszanek, problem diety .........................................5

Wybór procesu technologicznego ...........................................6

Standardowe zagadnienie programowania liniowego .............7

Sens geometryczny sprowadzania zadania ogólnego do
standardowego.........................................................................8

Posta

ü kanoniczna zadania programowania liniowego ...........9

Metoda SYMPLEKS.............................................................10

Zagadnienie transportowe ..................................................17

Metoda najwi

Ċkszego przepáywu ..........................................18

Algorytm cechowania............................................................19

Pierwotne (prymalne) zadanie programowania liniowego ....22

Dualne zadanie programowania liniowego ...........................22

Algorytm prymalno-dualny zadania transportowego ............24

Zastosowania .........................................................................28

Zadanie transportowo-produkcyjne.......................................29

Zadanie lokalizacji produkcji ................................................30

Zadanie minimalizacji pustych przebiegów ..........................30

Optymalizacja na grafach...................................................33

Problem najkrótszej drogi .....................................................34

Algorytm Dijkstry .................................................................34

Problem komiwoja

Īera..........................................................36

Algorytm podzia

áu i ograniczeĔ ............................................37

Programowanie zero-jedynkowe........................................42

Zadanie programowania zero-jedynkowego .........................42

Metoda filtru Balasa ..............................................................44

Programowanie ca

ákowitoliczbowe....................................46

Zadanie programowania ca

ákowitoliczbowego .....................46

Podstawowe odci

Ċcie Gomory’ego .......................................48

Algorytm Gomory’ego ..........................................................51

Programowanie nieliniowe .................................................52

Zadanie programowania nieliniowego bez ogranicze

Ĕ .........52

Zadanie programowania nieliniowego z ograniczeniami w
postaci równo

Ğci....................................................................56

Metoda mno

Īników Lagrange’a............................................57

Zadanie programowania nieliniowego z ograniczeniami w
postaci nierówno

Ğci ...............................................................58

Komputerowe metody rozwi

ązywania zadaĔ

programowania nieliniowego................................................ 63

Zadanie programowania nieliniowego bez ogranicze

Ĕ............ 63

Metody rz

Ċdu zerowego (bezgradientowe) funkcji jednej

zmiennej .................................................................................. 64

Metoda z

áotego podziaáu.......................................................... 64

Metoda Powella (interpolacji kwadratowej)............................ 65

Metody rz

Ċdu pierwszego (gradientowe) funkcji jednej

zmiennej .................................................................................. 66

Metoda siecznych .................................................................... 67

Metody rz

Ċdu drugiego funkcji jednej zmiennej ..................... 68

Metoda Newtona...................................................................... 68

Metody rz

Ċdu zerowego (bezgradientowe) minimalizacji

funkcji wielu zmiennych.......................................................... 69

Metody poszukiwa

Ĕ prostych .................................................. 69

Metoda Gaussa-Seidela ........................................................... 69

Metoda losowego przeszukiwania ........................................... 70

Metody kierunków poprawy.................................................... 71

Metoda kierunków sprz

ĊĪonych Powella ................................ 71

Metody rz

Ċdu pierwszego (gradientowe) minimalizacji

funkcji wielu zmiennych.......................................................... 73

Metoda gradientu sprz

ĊĪonego ................................................ 74

Metody rz

Ċdu drugiego............................................................ 75

Metoda Newtona...................................................................... 75

Zadanie programowania nieliniowego z ograniczeniami ........ 75

Algorytmy (metody) podstawowe ........................................... 76

Metoda systematycznego przeszukiwania ............................... 76

Metoda poszukiwa

Ĕ losowych (Monte Carlo)......................... 77

Algorytmy (metody) z pami

Ċcią .............................................. 78

Metoda funkcji kary................................................................. 78

Metoda zewn

Ċtrznej funkcji kary ............................................ 79

Metoda wewn

Ċtrznej funkcji kary ........................................... 81

Metoda mieszanej wewn

Ċtrzno-zewnĊtrznej funkcji kary....... 82

Programowanie wielokryterialne ......................................... 83

Zadanie programowania wielokryterialnego ........................... 83

Relacja porz

ądku liniowego: ................................................... 83

Sprowadzanie problemu do zadania programowania
jednokryterialnego (pseudopolioptymalizacja)........................ 84

Metoda wa

Īonej funkcji celu................................................... 84

Przeniesienie zadania do przestrzeni kryteriów....................... 84

Metoda punktu docelowego..................................................... 85

Rozwi

ązania Pareto-optymalne ............................................... 87

Metoda wa

Īonej funkcji celu................................................... 88

Metoda punktu docelowego..................................................... 88

FORMU

àOWANIE PROBLEMÓW OPTYMALIZACJI

Niech dany b

Ċdzie punkt (wektor) o

N

sk

áadowych opisujących problem w

N

–

wymiarowej przestrzeni euklidesowej b

Ċdący matematycznym zapisem cech

problemu.

>

@

N

R

x

x



T

N

i

x

x

x

!

!

1

T

dane

parametry

N

n

decyzyjne

zmienne

n

x

,

,

x

,

x

,

,

x

»

»

¼

º

«

«

¬

ª









!







!

1

1

x

oraz warunki ograniczaj

ące zakresy zmiennoĞci wektora

x

.

Ograniczenia:

1. nierówno

Ğciowe:









m

,...,

j

x

,...,

x

g

n

j

1

0

1

d

2. równo

Ğciowe (funkcjonalne):









q

,...,

k

x

,...,

x

h

n

k

1

0

1

Zbiór punktów przestrzeni

R

n

spe

ániających przyjĊte ograniczenia nazywamy

zbiorem dopuszczalnym (zbiorem rozwi

ązaĔ dopuszczalnych, zbiorem decyzji

dopuszczalnych).

Zbiór dopuszczalny:

n

R



)

Aby zadanie mia

áo sens zbiór dopuszczalny nie moĪe byü zbiorem pustym

0

z

)

h

1

(x

1

,x

2

)= 0

)

g

4

(x

1

,x

2

)

t

0

g

3

(x

1

,x

2

)

t

0

g

2

(x

1

,x

2

)

t

0

g

1

(x

1

,x

2

)

t

0

x

1

x

2

)

g

4

(x

1

,x

2

)

t

0

g

3

(x

1

,x

2

)

t

0

g

2

(x

1

,x

2

)

t

0

g

1

(x

1

,x

2

)

t

0

x

1

x

2

Zbiór dopuszczalny dla problemu dwu-

+ jedno ograniczenie

wymiarowego

równo

Ğciowe

J.Stadnicki Optymalizacja 1

+ dwa ograniczenia równo

Ğciowe

h

2

(x

1

,x

2

)= 0

h

1

(x

1

,x

2

)= 0

)

g

4

(x

1

,x

2

)

t

0

g

3

(x

1

,x

2

)

t

0

g

2

(x

1

,x

2

)

t

0

g

1

(x

1

,x

2

)

t

0

x

1

x

2

Wnioski:

1. ogranicze

Ĕ nierównoĞciowych

mo

Īe byü dowolnie duĪo bylyby

0

z

)

,

2. ogranicze

Ĕ równoĞciowych moĪe

by

ü co najwyĪej

n

-1,

Aby ze zbioru dopuszczalnego wybra

ü punkt optymalny, definiujemy pewną funkcjĊ

, która b

Ċdzie miarą speánienia przyjĊtych celów (funkcja celu, kryterium

jako

Ğci).

 

x

Q

Sformu

áowanie zadania:

Znajd

Ĩ taki wektor

>

@

T

n

x

,

,

x

ˆ

!

1

x

, który nale

Īąc do obszaru dopuszczalnego

minimalizuje (maksymalizuje) funkcj

Ċ celu.

x dla problemu maksymalizacji:





 

 

^

`



:



x

x

x



š

d



)

)

Q

Q x

x dla problemu minimalizacji:





 

 

^

`



:



x

x

x



š

t



)

)

Q

Q x

@

Wektor

b

Ċdący rozwiązaniem powyĪszego zadania nazywamy

wektorem optymalnym.

>

T

n

xˆ

,...,

ˆ

ˆ

1

x

=

x

Etapy formu

áowania i rozwiązywania zadania optymalizacji:

1° okre

Ğliü zmienne decyzyjne

>

@

T

n

x

,

,

x

!

1

x

,

2° okre

Ğliü zbiór dopuszczalny

)

)

, x



i sprawdzi

ü czy

,

0

z

)

3° utworzy

ü funkcjĊ celu

 

Q x

,

4° znale

Ĩü wektor optymalny.

x

ˆ

.

J.Stadnicki Optymalizacja 2

PROGRAMOWANIE LINIOWE

Za

áoĪenia modeli liniowych:

1° proporcjonalno

Ğü – ograniczenia wyraĪające zuĪycie zasobów oraz funkcja celu

wyra

Īająca rezultat dziaáania są proporcjonalne do zmiennych decyzyjnych

(poziomu produkcji),

2° addywno

Ğü – caákowite zuĪycie zasobów jest sumą zuĪycia przypadającego na

poszczególne zmienne decyzyjne (produkty),

3° nieujemno

Ğü – Īadna ze zmiennych decyzyjnych nie moĪe przyjmowaü wartoĞci

ujemnych.

Oznaczenia:

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

t

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

m

j

1

mn

mi

m1

jn

ji

j1

1n

1i

11

n

i

1

n

i

1

b

b

b

a

a

a

a

a

a

a

a

a

0

x

x

c

c

c

#

#

"

"

#

#

#

"

"

#

#

#

"

"

#

#

#

#

=

b

=

A

x

=

x

=

c

x

wektor

wektor zmiennych

n

m



funkcji

zmiennych

- liczba ogranicze

Ĕ

m

celu

decyzyjnych

- liczba zmiennych decyzyjnych

n

Q

T

T

i

i

n

i

¦

c x

x c

1

c x

funkcja celu (iloczyn skalarny wektorów

)

c x

i

Posta

ü ogólna zagadnienie programowania liniowego:

Znale

Ĩü minimum:

Q

c x

T

przy warunkach:

0

t

d

˜

x

b

x

A

czym

przy

inaczej:

Q

c x

c x

c x

i i

n n

 

 

o

1 1

...

...

min

gdy spe

ánione są:

J.Stadnicki Optymalizacja 3

m

n

mn

i

mi

m

j

n

jn

i

ji

j

n

n

i

i

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

d









d









d









"

"

#

#

#

#

"

"

#

#

#

#

"

"

1

1

1

1

1

1

1

1

11

przy czym

x

t

i

0

Linowy model produkcji

Firma produkuje

n

wyrobów. Do ich produkcji zu

Īywane są zasoby dostĊpne w

ograniczonych ilo

Ğciach. OkreĞliü iloĞci produkowanych wyrobów aby nie

przekraczaj

ąc dostĊpnych zasobów osiągnąü maksimum zysku ze sprzedanej

produkcji.

Oznaczenia:

-

zu

Īycie Ğrodka produkcji

j

na wytworzenie jednostki wyrobu

i

,

ij

a

-

dost

Ċpne zasoby Ğrodka produkcji

j

,

j

b

- zysk jednostkowy ze sprzeda

Īy wyrobu

i,

i

c

- poszukiwana wielko

Ğü produkcji wyrobu

i.

i

x

Obszar dopuszczalny okre

Ğlony przez ograniczenia:

m

n

mn

i

mi

m

j

n

jn

i

ji

j

n

n

i

i

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

d









d









d









"

"

#

#

#

"

"

#

#

#

"

"

1

1

1

1

1

1

1

1

11

i

= 1,...,

n

j

= 1,...,

m

oraz

x

i

t

0

Funkcja celu:





max

,

,

,

1

1

1

o









n

n

i

i

n

i

x

c

x

c

x

c

x

x

x

Q

"

"

!

!

J.Stadnicki Optymalizacja 4

Np.
Firma produkuje dwa wyroby (W1, W2) za pomoc

ą trzech maszyn (M1, M2, M3).

W1

W2

8

6 M1

720

8

16 M2

1280

Zu

Īycie czasu na jednostkĊ wyrobu

[min]

12

8 M3

960

dzienny limit

czasu pracy

[min]

Zysk jednostkowy [z

á]

12

10

Obliczy

ü wielkoĞü dziennej produkcji zapewniającej maksimum zysku.

960

8

12

1280

16

8

720

6

8

2

1

2

1

2

1

d



d



d



x

x

x

x

x

x

max

10

12

2

1

o



x

x

Q

oraz

x

i

t

0

Problem mieszanek, problem diety

0

20

40

60

80

100

120

0

20

40

60

80

100

120

140

Obszar

dopuszczalny

Punkt

optymalny

(40,60)

8x

1

+ 6x

2

d 120

Q=12x

1

+ 10x

2

o max

12x

1

+ 8x

2

d 720

8x

1

+ 16x

2

d 1280

x1

x2

160

Jakie ilo

Ğci skáadników naleĪy zmieszaü, aby otrzymaü mieszankĊ o poĪądanym

sk

áadzie przy najniĪszych kosztach skáadników?

Okre

Ğliü iloĞci produktów ĪywnoĞciowych diety zapewniającej organizmowi

niezb

Ċdne skáadniki odĪywcze i energetyczne przy najniĪszym koszcie produktów?

Np.
ĩeliwo maszynowe wytwarzane z trzech stopów powinno zawieraü:
do 14% C, do 8% Si, co najmniej 25% Mn i co najmniej 12% P.

J.Stadnicki Optymalizacja 5

Zminimalizowa

ü koszt wytwarzania Īeliwa.

Zawarto

Ğü % pierwiastka

Stop

C

Si

Mn

P

Cena [z

á]

I

28

10

30

10

100

II

14

12

20

10

50

III

10

6

30

15

200

12

15

10

10

25

30

20

30

8

6

12

10

14

10

14

28

3

2

1

3

2

1

3

2

1

3

2

1

t





t





d





d





x

x

x

x

x

x

x

x

x

x

x

x

min

200

50

100

3

2

1

o





x

x

x

Q

oraz

x

i

t

0

Odp.:

x

1

= 0,1,

x

2

= 0,325,

x

3

= 0,517,

Q

= 129,6 z

á.

Wybór procesu technologicznego

Firma ma produkowa

ü

j

wyrobów w ilo

Ğciach

b

j

. Wykorzystuj

ąc proces

technologiczny

i

z jednostkow

ą intensywnoĞcią (jeden raz) uzyskuje siĊ produkty w

ilo

Ğciach

a

ij

i ponosi koszty

c

i

. Dobra

ü poszczególne procesy technologiczne tak,

aby wytworzy

ü potrzebne iloĞci wyrobów po najmniejszych kosztach.

Np.
Tartak ma wykona

ü 300 kompletów belek. KaĪdy komplet skáada siĊ z 7 belek o

d

áugoĞci 0,7m oraz 4 belek o dáugoĞci 2,5m. Jak zrealizowaü zamówienie, aby

odpad przy ci

Ċciu dáuĪyc o dáugoĞci 5,2m byá minimalny?

Sposoby ci

Ċcia pojedynczej dáuĪycy

Belki

I

II

III

0,7 m [szt]

7

3

0

2,5 m [szt]

0

1

2

Odpad [m]

0,3

0,6

0,2

.)

/

.

4

.

300

(

1200

2

.)

/

.

7

.

300

(

2100

3

7

3

2

2

1

kpl

szt

kpl

x

x

kpl

szt

kpl

x

x

u

t



u

t



oraz

x

i

t

0





min

2

,

0

6

,

0

3

,

0

,

,

3

2

1

3

2

1

o





x

x

x

x

x

x

Q

Odp.:

x

1

= 300,

x

2

= 0,

x

3

= 600,

Q

= 210

J.Stadnicki Optymalizacja 6

Standardowe zagadnienie programowania liniowego:

Znale

Ĩü minimum:

Q

c x

T

przy warunkach:

A x = b

x

˜

t

przy czym

0

OGÓLNE

o STANDARDOWE

1. pe

áne ograniczenie nierównoĞciowe typu

d

:

Ka

Īda z nierównoĞci:

a x

a x

a x

b

i i

n n

11 1

1

1

1

 

 

d

"

"

mo

Īe byü sprowadzona do równoĞci, przez wprowadzenie zmiennej dopeániającej

(sztucznej)

:

0

1

t



n

x

1

1

1

1

1

11

b

x

x

a

x

a

x

a

n

n

n

i

i













"

"

2. pe

áne ograniczenie nierównoĞciowe typu

:

t

Je

Īeli nierównoĞü miaáa zwrot przeciwny:

a x

a x

a x

b

i i

n

n

11 1

1

1

1

 

 

t

"

"

to przy sprowadzaniu do równo

Ğci, sztuczną zmienną naleĪy odjąü:

1

1

1

1

1

11

b

x

x

a

x

a

x

a

n

n

n

i

i













"

"

3. pe

áne dwustronne ograniczenie nierównoĞciowe:

Ka

Īdą z dwustronnych nierównoĞci:

2

1

1

1

11

1

1

1

b

x

a

x

a

x

a

b

n

n

i

i

d









d

"

"

Mo

Īna zastąpiü ukáadem typu 1 i 2 , a nastĊpnie sprowadziü do ukáady równoĞci tak

jak opisano poprzednio.

Sens geometryczny sprowadzania zadania ogólnego do standardowego:

Rozwa

Īmy przykáad dwuwymiarowego obszaru dopuszczalnego okreĞlonego

nierówno

Ğciami

:

0

,

0

,

2

2

2

1

2

1

t

t

d



x

x

x

x

Po wprowadzeniu dodatkowej zmiennej

otrzymamy trójk

ąt ABC leĪący w

przestrzeni trójwymiarowej:

3

x

0

,

0

,

0

,

0

2

2

3

2

1

3

2

1

t

t

t







x

x

x

x

x

x

J.Stadnicki Optymalizacja 7

d)

c)

A

)

^xo’

)

x^

x

2

x

1

x

2

x

1

b)

)

)

x

^

x

2

x

1

)

)

)

x

^

x

2

x

1

a)

2x

1

+

x

2

+

x

3

=2

2

x

3

=0

x

1

=0

x

2

=0

0

2

1

A

B

x

2

x

1

2x

1

+

x

2

=2

x

1

=0

x

2

=0

0

2

1

A

B

x

2

x

1

a) jednoznaczne rozwi

ązanie optymalne,

b) rozwi

ązaniem optymalnym jest kaĪdy punkt brzegu

zbioru dopuszczalnego równoleg

áy do prostej celu,

c) nie ma sko

Ĕczonego rozwiązania (maksymalizacja),

d) punkt A jest miejscem przeci

Ċcia trzech ograniczeĔ.

Okre

Ğlenie:

W ogólnym przypadku zbiór dopuszczalny jest

)

(

m

n



wymiarowym wypuk

áym

wielo

Ğcianem leĪącym w przestrzeni -wymiarowej, który nazywamy sympleksem.

n

W przyk

áadzie:

zmienne decyzyjne,

3

n

ograniczenie,

1

m

2

1

3



 m

n

- trójk

ąt jest obiektem

dwuwymiarowym.

Wnioski z rysunku:

1) Dla ogranicze

Ĕ i funkcji celu typu liniowego punkty obszaru dopuszczalnego, w

których funkcja celu mo

Īe mieü minimum, leĪą w punktach granicznych obszaru

dopuszczalnego (wierzcho

ákach).

2) Aby znale

Ĩü optymalne rozwiązanie zadania (minimum funkcji celu), naleĪy

przeszuka

ü wierzchoáki obszaru dopuszczalnego.

J.Stadnicki Optymalizacja 8

Wierzcho

áki to takie punkty obszaru dopuszczalnego, w których

zmiennych

decyzyjnych

ma warto

Ğü zero, a reszta okreĞlona jest ukáadem równaĔ:



m

n





i

x

b

=

x

A

˜

Zmienne, które przyrównujemy do zera nazywamy zmiennymi niebazowymi

,

N

x

pozosta

áe zmienne nazywamy zmiennymi bazowymi

.

B

x

Zatem:

x

x

x

»

¼

º

«

¬

ª

N

B

zmienne bazowe

zmienne niebazowe

ª

º

«

»

¬

¼

Posta

ü zadania programowania liniowego, w której wykonano powyĪsze

przekszta

ácenia nosi nazwĊ postaci kanonicznej.

Posta

ü kanoniczna zadania programowania liniowego:

Wybran

ą zmienną

uk

áadu równaĔ:

i

x

m

n

mn

i

mi

m

j

n

jn

i

ji

j

n

n

i

i

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

























"

"

#

#

#

#

"

"

#

#

#

#

"

"

1

1

1

1

1

1

1

1

11

mo

Īna wyeliminowaü ze wszystkich równaĔ z wyjątkiem równania

j

– tego:

1° dziel

ąc równanie

j

– te przez

,

ji

a

2° dziel

ąc pozostaáe równania przez wspóáczynniki

stoj

ące przy

,

ki

a

i

x

3° odejmuj

ąc od kaĪdego z otrzymanych równaĔ przeksztaácone równanie

j

– te.













"

"







"

"

"

"

'

1

'

1

'

11

1

1

1

1

1

1

1

11

1

1

1

1

1

1

1

1

11

0

1

_

1

b

ji

j

i

n

a

ji

jn

i

n

i

a

ji

j

i

ji

j

n

ji

jn

i

ji

j

i

n

i

n

i

i

a

b

a

b

x

a

a

a

a

x

x

a

a

a

a

a

b

x

a

a

x

x

a

a

a

b

x

a

a

x

x

a

a

n

¸

¸
¹

·

¨

¨
©

§



¸

¸
¹

·

¨

¨
©

§











¸

¸
¹

·

¨

¨
©

§

























J.Stadnicki Optymalizacja 9

Dla wszystkich równa

Ĕ ukáadu:

'

b

x

'

a

x

x

'

a

'

b

x

'

a

x

x

'

a

'

b

x

'

a

x

x

'

a

m

n

mn

i

m

j

n

jn

i

j

n

n

i





˜









˜









˜





"

"

#

#

#

#

"

"

#

#

#

#

"

"

0

1

0

1

1

1

1

1

1

1

11

powtarzaj

ąc operacjĊ dla

m

zmiennych

, po zmianie kolejno

Ğci równaĔ ukáadu

otrzymamy posta

ü kanoniczną ukáadu ograniczeĔ a co za tym idzie caáego zadania

programowania liniowego.

i

x

"

b

x

"

a

x

"

a

x

x

x

"

b

x

"

a

x

"

a

x

x

x

"

b

x

"

a

x

"

a

x

x

x

m

n

n

,

m

m

m

,

m

m

n

n

,

m

m

,

m

n

n

,

m

m

,

m







˜





˜



˜







˜





˜



˜







˜





˜



˜













"

"

#

#

#

#

#

"

"

"

"

1

1

2

1

2

2

1

1

2

2

1

1

1

1

1

1

2

1

1

0

0

0

1

0

0

0

1

Metoda SYMPLEKS:

Zadanie:

Znale

Ĩü minimum

, przy warunkach:

x

c

T

Q

(1)

A x = b

x

˜

t 0

Równanie (1) mo

Īna sprowadziü do postaci kanonicznej i zapisaü w postaci:

(2)

>

@

B

N

x

x

b

˜

ª

¬

«

º

¼

»

B

N

gdzie:

- wektor zmiennych bazowych,

B

x

- wektor zmiennych niebazowych,

N

x

J.Stadnicki Optymalizacja 10

Wyznaczanie bazowego rozwi

ązania dopuszczalnego:

Je

Īeli podstawimy za wartoĞci zmiennych niebazowych

x

N

0

to rozwi

ązanie

równania (2) nazywa si

Ċ rozwiązaniem bazowym.

-1

B

b

x

B

˜

˜

B

- rozwi

ązanie bazowe, nieosobliwą macierz

x

B

B

1

b

B

nazywamy baz

ą.

Je

Ğli ponadto

, to mówimy,

Īe

0

t

B

x

x

jest bazowym rozwi

ązaniem

dopuszczalnym.

W ten sposób wyznaczamy wierzcho

áek sympleksu, który moĪe kandydowaü do

rozwi

ązania zadania.

Zmiana bazowego rozwi

ązania dopuszczalnego (wybór zmiennej niebazowej

wprowadzanej do bazy):

Przekszta

ácamy funkcjĊ celu tak, aby wyraziü ją za pomocą zmiennych niebazowych

.

N

x

(3)

Q

B

T

B

N

T

N

B

N



ª

¬

«

º

¼

»

c x

c x

c

c

c

gdzie

(4)

Bx

N x

b

B

B

N



˜

1

x

B N x

B

B

N







1

1

b

N

(5)

wstawmy (5) do (3):

x

B b

B N x

B







1

1





Q

B

T

N

N

T

N









c

B b

B N x

c x

1

1

(6)





Q

B

T

N

T

B

T

N

T

N











c B b

c

c B N x

q

p x

1

1

0

J.Stadnicki Optymalizacja 11

gdzie:

(7)

q

c

(8)

B

0

1



B

T

b

N

p

c

c B

T

N

T

B

T



1

Równanie (6) wyra

Īa funkcjĊ celu za pomocą zmiennych niebazowych.

Mo

Īliwe są trzy przypadki:

1° wszystkie sk

áadowe wektora są dodatnie

,

Poniewa

Ī minimalizujmy funkcjĊ celu, wprowadzenie odpowiadających

sk

áadowym wektora

0

!

p

p

kolumn macierzy

N

do bazy zwi

Ċkszy (pogorszy)

warto

Ğü funkcji celu

bazowe rozwi

ązanie dopuszczalne

jest rozwi

ązaniem

optymalnym zadania

.

Ÿ

xˆ

B

x

B

x

2° wszystkie sk

áadowe wektora są zerowe

0

p

,

Rozwi

ązanie jest niejednoznaczne, tzn. Īe moĪna przejĞü do innego wierzchoáka

sympleksu baz zmiany warto

Ğci funkcji celu.

3° wektor

posiada ujemn

ą skáadową

p

0



k

p

,

Wprowadzenie odpowiadaj

ącej jej kolumny

macierzy

k

a

N

do bazy zmniejszy

(poprawi) warto

Ğü funkcji celu (tw. o poprawianiu).

Je

Īeli w wektorze

wyst

Ċpuje wiĊcej ujemnych skáadowych

, wybieramy

najmniejsz

ą z nich.

p

k

p

z (8):

N

B

c

c

p

Ȝ



T

T
B

T
N

T

1





oznaczaj

ąc:

T
B

T

T
B

T

c

B

B

B

c

Ÿ

˜



O

O

1

(9)

czyli (10)

O

T

B

B

c

N

c

p

T

T
N

T

O



O

- wektor mno

Īników sympleksowych,

p

- wektor wzgl

Ċdny funkcji celu.

Ujemn

ą skáadową wektora

p

oznaczymy

.

k

p

Je

Īeli:

p

n

k

1

m

d

d







dla

0

k

T

Nk

k

a

c

O

to kolumn

Ċ

wprowadzamy do bazy

k

a

B

w nast

Ċpnej iteracji, a wartoĞü funkcji celu

ulegnie zmniejszeniu.

Q

J.Stadnicki Optymalizacja 12

Poprawa bazowego rozwi

ązania dopuszczalnego (wybór zmiennej bazowej

wyprowadzanej z bazy):

Nale

Īy teraz znaleĨü kolumnĊ w bazie

B

, w miejsce której wprowadzimy

.

k

a

Z (5):

x

B b

B N x

B

N







1

1

oznaczaj

ąc bieĪące rozwiązanie bazowe przez

,

Īądamy aby nowe

bazowe rozwi

ązanie byáo dopuszczalne (

):

b

B

x

1

0



0

t

B

x

(11)

x

x

B a x

x

x

x

B

k

Nk

B

y



t



t



0

1

0

0

0

czyli by:

Nk

gdzie:

B a

y

B

a

B y



˜

Ÿ

1

k

(12)

k

k

a

B

y

1



Ÿ

przy czym

otrzymuje si

Ċ jako rozwiązanie ukáadu (12).

y

Warto

Ğü zmiennej bazowej moĪna zmniejszyü jeĪeli

, w przeciwnym przypadku

zbiór dopuszczalny jest nieograniczony i funkcja celu mo

Īe byü zmniejszona do

.

0

y

t

f



Baz

Ċ opuszcza ta kolumna, dla której:

(13)

¿

¾

½

¯

®

­

i

i

y

x

0

0

min

T

Przyk

áad:

Zminimalizowa

ü:

Q

x

x





0 5

0 4

1

.

.

x

x

x

x

1

2

1

2

2

24

18

11



d



d
d

2

4

przy

ograniczeniach:

x

x x

1

1

2

15

0

­

®

°

¯

°

t

.

,

1° Sprowadzamy zadanie ogólne do standardowego kanonicznego przez dodanie

do wektora sztucznych zmiennych:

x

x x x

3

4

5

0

,

,

t

x

x

x

x

x

x

x

x

1

2

3

1

2

4

1

5

2

2

15

18

11











­

®

°

¯

°

.

J.Stadnicki Optymalizacja 13

Powy

Īszy ukáad po zamianie kolejnoĞci zmiennych jest postaci kanonicznej!

Mamy wi

Ċc:

>

@

A

x

b

c

ª

¬

«

«

«

º

¼

»

»

»

ª

¬

«

«

«

«

«

«

º

¼

»

»

»

»

»

»

ª

¬

«

«

«

º

¼

»

»

»





1

2

1

0

0

15 1

0

1

0

1

0

0

0

1

24

18

11

0 5

0 4

0

0

0

3

.

.

x

x

x

x

x

1

2

4

5

T

.

1° Rozpoczynamy obliczenia dla

x

N

0

. Poniewa

Ī

B

jest nieosobliwa, traktujemy

j

ą jako bazĊ a

jako rozwi

ązanie bazowe.

x

B

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª



0

0

0

1

0

0

0

1

0

0

0

1

1

5

4

3

B

B

x

x

x

c

I

B

B

B

x

Rozwi

ązanie bazowe;

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

Ÿ



11

18

24

11

18

24

1

I

b

B

x

b

B

x

B

B

z (9):

>

@

0

0

0

1



T
B

T
B

T
B

T

c

I

c

B

c

Ȝ

z (10):

>

@ >

@

>

@

4

0

5

0

0

1

1

5

1

2

1

0

0

0

4

0

5

0

.

.

.

.

.

T

T
N

T





»

»

»

¼

º

«

«

«

¬

ª









N

Ȝ

c

p

2° Zgodnie z tw. o poprawianiu wybieramy ujemn

ą skáadową wektora

i

wprowadzamy j

ą do bazy

p

B

. Poniewa

Ī -0.5 < -0.4, do bazy

B

wprowadzamy

kolumn

Ċ 1 macierzy N odpowiadającą zmiennej

.

x

1

1

ª

¬

«

«

«

x

1

15

1

º

¼

»

»

»

.

Ÿ

Rozwi

ązujemy ukáad (12):

J.Stadnicki Optymalizacja 14

a

B y

y

B a

B x

I x

x

k

k

Ÿ

ª

¬

«

«

«

º

¼

»

»

»





1

1

1

1

1

1

15

1

.

3° Wyznaczamy kolumn

Ċ, która ma opuĞciü bazĊ

B

.

Z (13):

^

`

y

B

x

y

x

B

1

11

11

12

24

1

11

5

1

18

1

24



¿

¾

½

¯

®

­

¿

¾

½

¯

®

­

bo

min

.

min

min

i

Bi

Zatem baz

Ċ

B

opuszcza kolumna 5 odpowiadaj

ąca zmiennej

.

x

5

1

2

1

0

0

15 1

0

1

0

1

0

0

0

1

.

ª

¬

«

«

«

º

¼

»

»

»

4° Nowa macierz bazowa:

,

obliczamy



.

B

ª

¬

«

«

«

º

¼

»

»

»

1

0

1

0

1 15

0

0

1



.

B







ª

¬

«

«

«

º

¼

»

»

»

1

1

0

1

0

1

15

0

0

1

bo

 

.

.

B B

I

˜

ª

¬

«

«

«

º

¼

»

»

»

˜





ª

¬

«

«

«

º

¼

»

»

»

1

1

0

1

0

1 15

0

0

1

1

0

1

0

1

15

0

0

1

Nowe rozwi

ązanie bazowe:

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

˜

˜





˜

˜





˜

»

»

»

¼

º

«

«

«

¬

ª

˜

»

»

»

¼

º

«

«

«

¬

ª







11

5

.

1

13

11

1

11

)

5

.

1

(

18

1

11

)

1

(

24

1

11

18

24

1

0

0

5

.

1

1

0

1

0

1

ˆ

ˆ

1

b

B

x

B

Na tym ko

Ĕczy siĊ I iteracja. NastĊpne wykonujemy wg tego samego algorytmu.

Warto

Ğü funkcji celu:

J.Stadnicki Optymalizacja 15

x

przed I iteracj

ą:

>

@

Q

T

0

0 5

0 4

0

0

0

0

0

24

18

11

0





˜

ª

¬

«

«

«

«

«

«

º

¼

»

»

»

»

»

»

c x

.

.

x

po I iteracji:

>

@

Q

I

T





˜

ª

¬

«

«

«

«

«

«

º

¼

»

»

»

»

»

»



c x

0 5

0 4

0

0

0

11

0

13

15

0

11

2

.

.

.

J.Stadnicki Optymalizacja 16

Zagadnienie transportowe

i

=

n

i

=3

i

=2

i

=1

j

=

m

j

=2

j

=1

Dana jest sie

ü transportowa

skierowana.

R: wierzcho

áki dostawy:

j

=1,...,

m

N: wierzcho

áki odbioru:

i

=1,...,

n

Ka

Īdemu áukowi przyporządkowany

jest jednostkowy koszt przewozu

.

ji

c

Zadanie transportowe:

Wyznaczy

ü macierz wielkoĞci przewozu

^ `

x

ji

, która minimalizuje ca

ákowity koszt

transportu

Q

, przy spe

ánieniu ograniczeĔ:

¦¦

o

m

j

n

i

ji

ji

min

x

c

1

1

1°

¦

(poda

Ī wierzchoáków dostawy nie moĪe byü

przekroczona)



x

a

j

m

ji

j

i

n

d

1

1

,...,





n

(poda

Ī wierzchoáków d

2°

¦

(popyt wierzcho

áków odbioru musi byü zaspokojony)



x

b

i

n

ji

i

j

m

t

1

1

,...,

przy

czym:

x

ji

t

.

0

Zadanie ma rozwi

ązanie dopuszczalne

gdy:

ostawy

zaspokaja popyt wierzcho

áków odbioru).





a

b

j

m

i

j

i

i

n

j

m

t

¦

¦

1

1

1

1

,...,

,...,

Przy czym je

Īeli:

1

q

, to jest to zadanie transportowe

¦

¦

!

m

j

n

i

i

j

b

a

1

1

otwarte,

2

q

¦

, to jest to zadanie transportowe zamkni

Ċte.

¦

m

j

n

i

i

j

b

a

1

1

J.Stadnicki Optymalizacja

17

Rozwi

ązanie jest optymalne gdy:

(

áączna iloĞü

transportowanego dobra zaspokaja popyt).



x

b

i

n

ji

i

j

m

¦

1

1

,...,



1

,

Dla danej sieci

N=(V,E),

w której wyró

Īnione są dwa wierzchoáki:

s

=

Ĩródáo,

t

= odp

áyw, kaĪdemu áukowi przyporządkowujemy nieujemną liczbĊ caákowitą

zwan

ą przepustowoĞcią.

ji

k

Przep

áyw w sieci

N

to takie przyporz

ądkowanie kaĪdemu áukowi liczby rzeczywistej

takiej,

Īe:

1°

0

1





d

d

x

k

j

m

i

n

ji

ji

,...,

,..,

2° w ka

Īdym wierzchoáku

i

ró

Īnym od

s

i

t

spe

ánione jest równanie zachowania

przep

áywu:

,

x

x

ji

il

l

j

¦

¦

( )

( )

gdzie:

j

- odnosi si

Ċ do zbioru áuków wchodzących do wierzchoáka

i

,

l

- odnosi si

Ċ do zbioru áuków wychodzących z wierzchoáka

i

.

Inaczej:

to co wp

áywa do wierzchoáka

i

musi z niego wyp

áynąü.

Warto

Ğü przepáywu

f(t)

to suma przep

áywów wpáywających do wierzchoáka

odp

áywu.

Metoda najwi

Ċkszego przepáywu:

Znale

Ĩü najwiĊkszy przepáyw tzn. wyznaczyü macierz

^ `

x

ji

, która maksymalizuje

form

Ċ

Q

, przy ograniczeniach:

¦¦

j

i

ji

x

1

1

m

n



1°

¦

,





x

a

j

m

ji

i

n

j

d

1

1,...,

2°

¦

przy czym:

.



x

b

i

n

ji

j

m

i

t

1

1,...,

x

ji

t 0

J.Stadnicki Optymalizacja

18

Algorytm cechowania

Za

áoĪenia:

x liczby w nawiasach kwadratowych oznaczają:

,

ji

ji

k

x

ª

º œ

¬

¼

[

przepustowo

Ğü, przepáyw

],

x wszystkie wartoĞci liczbowe są caákowite i nieujemne,
x początkowe przepáywy wzdáuĪ áuków wynoszą

0

ji

x

.

Procedura A (cechowanie):

1. nada

ü Ĩródáu

s

cech

Ċ (-, ’),

2. wzi

ąü dowolny wierzchoáek

j

maj

ący cechĊ

(i ,

İ

j

) lub (i , -

İ

j

)

i zbada

ü go,

rozpatruj

ąc wszystkie nie ocechowane wierzchoáki

l

przyleg

áe do

j.

A. je

Ğli

( j , l )

jest

áukiem i

(

przep

áyw < przepustowoĞci

), to nada

ü

wierzcho

ákowi

l

cech

Ċ

(j ,

İ

jl

jl

k

x



l

)

, gdzie:

^

`

min

,

l

j

jl

jl

k

x

H

H



,

B. je

Ğli

( j , l )

jest

áukiem to nadaü wierzchoákowi

l

cech

Ċ

(j , -

İ

l

)

,

gdzie:

,

^

`

jl

min

,

l

j

x

H

H

3. powtórz krok 2 a

Ī do ocechowania odpáywu

t

lub stwierdzenia,

Īe jest to

niemo

Īliwe.

[1,0]

[1,0]

[4,0]

[2,0]

[3,0]

[5,0]

t

s

(-,

’

)

[1,0]

6

4

[2,0]

[4,0]

3

5

2

1

J.Stadnicki Optymalizacja

19

1 ocechowanie:

wierz-

cho

áek

j

l

x

jl

k

jl

İ

j

x

jl

< k

jl

A.

İ

l

=min{

İ

j

, k

jl

– x

jl

}

B.

İ

l

=min{

İ

j

, x

jl

}

(j ,

İ

l

)

(j ,-

İ

l

)

1

s

1

0

5

’

0 < 5

min

{

’ ,

5 – 0

}

(s , 5)

2

s

2

0

4

’

0 < 4

min

{

’ ,

4 – 0

}

(s , 4)

4

2

4

0

4

4

0 < 4

min

{ 4 , 4 – 0

}

(2 , 4)

1

3

0

3

5

0 < 3

min

{ 5 , 3 – 0

}

(1 , 3)

3

4

3

0

1

4

0 < 1

min

{ 4 , 1 – 0

}

(4 , 1)

1 < 3

Ÿ

(4 , 1)

5

3

5

0

2

1

0 < 2

min

{ 1 , 2 – 0

}

(3 , 1)

6

4

6

0

2

4

0 < 2

min

{ 4 , 2 – 0

}

(4 , 2)

5

t

0

1

1

0 < 1

min

{ 1 , 1 – 0

}

(5 , 1)

t

6

t

0

1

2

0 < 1

min

{ 2, 1 – 0

}

(6 , 1)

1 = 1

Ÿ

(5 , 1)

przep

áyw

poprzedni
wierzcho

áek

(4,2)

(2,4)

(s,4)

(s,5)

[1,0]

[1,0]

[4,0]

[3,0]

[5,0]

t

s

(5, 1)

(-,

’

)

[1,0]

6

4

[2,0]

[4,0]

5

3

[2,0]

(4,1)

(3,1)

2

1

Procedura B zmiana przep

áywu:

[1,0]

[1,1]

[4,1]

[2,1]

[3,0]

[5,0]

t

s

[1,1]

6

4

[2,0]

[4,1]

3

5

2

1

J.Stadnicki Optymalizacja

20

2 ocechowanie:

wierz-

cho

áek

j

l

x

jl

k

jl

İ

j

x

jl

< k

jl

A.

İ

l

=min{

İ

j

, k

jl

– x

jl

}

B.

İ

l

=min{

İ

j

, x

jl

}

(j ,

İ

l

)

(j ,-

İ

l

)

1

s

1

0

5

’

0 < 5

min

{

’ ,

5 – 0

}

(s , 5)

2

s

2

1

4

’

1 < 4

min

{

’ ,

4 – 1

}

(s , 3)

3

1

3

0

3

5

0 < 3

min

{ 5 , 3 – 0

}

(1 , 3)

2

4

1

4

3

1< 4

min

{ 3 , 4 – 1

}

(2 , 3)

4

3

4

1

1

1

1 = 1

min

{ 1 , 1

}

(3 , -1)

-1 < 3

Ÿ

(3 , -1)

5

3

5

1

2

3

1 < 2

min

{ 3 , 2 – 1

}

(3 , 1)

6

4

6

0

2

1

0 < 2

min

{ 1 , 2 – 0

}

(4 , 1)

5

t

1

1

1

1 = 1

min

{ 1 , 1

}

(5 , -1)

t

6

t

0

1

1

0 < 1

min

{ 1, 1 – 0

}

(6 , 1)

-1 =wyp

áyw

z „t”

Ÿ

(6 , 1)

(4,1)

(s,3)

(3,-1)

(s,5)

[1,0]

[1,1]

[4,1]

[3,0]

[5,0]

t

s

(6, 1)

(-,

’

)

[1,1]

6

4

[4,1]

[2,0]

5

3

[2,1]

(1,3)

(3,1)

2

1

Odp

áyw otrzymaá cechĊ

(l ,

İ

t

) tzn. (6 ,1). Oznacza to,

Īe w sieci z bieĪącym

przep

áywem istnieje ĞcieĪka powiĊkszająca z

s

do

t,

wzd

áuĪ której moĪna

powi

Ċkszyü przepáyw o

İ

t

tzn. o 1 a

l

tzn. 6 jest ostatnim wierzcho

ákiem na tej

ĞcieĪce.

J.Stadnicki Optymalizacja

21

[1,1]

[1,1]

[4,1]

[2,1]

[3,1]

[5,1]

t

s

przep

áyw=

1+1 =2

[1,-1]

[1,1]

6

4

[4,1]

[2,1]

3

5

2

1

3 ocechowanie: brak przej

Ğcia!

ko

Ĕcowe rozwiązanie:

x

s2

=x

s1

=x

24

=x

13

=x

46

=x

35

=x

6t

=x

5t

=

1

warto

Ğü przepáywu:

f(t)

= 1 +1 =2

Pierwotne (prymalne) zadanie programowania liniowego:

Znale

Ĩü wektor

, taki

Īe:

, przy ograniczeniach:

x

 

Q

T

x

c x

o min

1°

A x

b

d

2°

x

- zmienne prymalne,

t 0

x

Dualne zadanie programowania liniowego:

Znale

Ĩü wektor

y

, taki

Īe:

, przy ograniczeniach:

 

P

T

y

y b

o max

1°

A

c

y

t

T

2°

y

t 0

y

- zmienne dualne (sprz

ĊĪone).

Tw. o dualno

Ğci:

1) Je

Īeli jeden z problemów: dualny lub pierwotny ma rozwiązanie optymalne

x

ˆ

, to

i drugi je ma

y

ˆ

, przy czym warto

Ğci obu zadaĔ są takie same

.

 

 

y

x

ˆ

P

max

ˆ

Q

min

2) Je

Īeli jeden z problemów nie ma rozwiązania, ze wzglĊdu na nieograniczoną

warto

Ğü funkcji celu

f

o

f

o

y

x

P

Q

lub

, to zbiór dopuszczalny

drugiego problemu jest pusty (rozwi

ązanie nie istnieje).

 

 

J.Stadnicki Optymalizacja

22

Wnioski z tw. o dualno

Ğci

a) Warunkiem koniecznym i wystarczaj

ącym istnienia rozwiązania jest istnienie co

najmniej jednego dopuszczalnego rozwi

ązania problemu pierwotnego i dualnego.

b) Warunkiem koniecznym i wystarczaj

ącym optymalnoĞci rozwiązaĔ

dopuszczalnych

x

ˆ

i

y

ˆ

jest

 

 

y

x

ˆ

P

ˆ

Q

.

Przyk

áad:

Zadanie pierwotne:

Zadanie

dualne:

 

Q

x

x

x

x

x







o

2

4

1

2

3

4

max

 

P

y

y

y

y





o

4

3

3

1

2

3

min

x

x

x

x

x

x

x

x

1

2

4

1

2

2

3

4

3

4

2

4

3





3

d



d





d

1

1

4

4

3

2

2

3

1

3

3

2

1

2

1

t



t

t





t



y

y

y

y

y

y

y

y

min

0

T

Q

o

d

c x

Ax

b

x

t

max

0

T

T

T

T

P

o

t œ

t

t

yb

A y

c

y A

c

y

Je

Īeli

jest rozwi

ązaniem

ˆ

B

x

x

optymalnym to: Przyjmuj

ąc:

y

Ȝ

, (rozwi

ązanie

optymalne

zadania dualnego)

1

(

0

B



x

B b

x

T

T
B

)

N

Ȝ B

c

za

(9) mamy:

Zatem wektor

Ȝ

jest dopuszczalny.

Q

P

Ÿ

Warto

Ğci obu zadaĔ są równe.

>

@

,

,

T

T

T

T

T

B

N

ª

º

ª

t

¬

¼

¬

y

B N

y B y N

c

c

c

,

T

º¼

T

T

T

B

y B

Ȝ B

c

1

0

T

T

T

N

B





d

p

c

c B N

T

T

N

t

y N

Ȝ N

c

T

N

1

T

T

T

B

N



t

Ȝ

c B N

c

T

B

B

Q

c x

,

,

T

T

T

T

B

N

ª

º

ª

º

t

¬

¼

¬

¼

Ȝ B Ȝ N

c

c

T

c

N

1

B

T

T

T

B

B

B

P



x

Ȝ b c B b c x

J.Stadnicki Optymalizacja

23

Algorytm prymalno-dualny zadania transportowego

Znale

Ĩü macierz

^

, tak

ą Īe:

Q

c

przy ograniczeniach:

`



x

ji

 

x

ji

ji

i

n

j

m

x

o

¦

¦

min

1

1

1°

¦





x

a

j

m

ji

j

i

n

d

1

1

,..,

2°

¦

przy

czym:

x



x

b

i

n

ji

i

j

m

t

1

1

,..,

ji

t 0

Warunek (1°) mo

Īna zapisaü w postaci:

(1°)’



t 

¦

x

a

ji

j

i

n

1

2°

x

b

ji

i

j

m

t

¦

1

Formu

áujemy zadanie dualne, zmienne wystĊpujące w (1°)’ i (2°) zastąpimy

zmiennymi dualnymi

i

, takimi

Īe:

oraz

u

j

v

i

¦

n

i

ji

j

x

u

1

¦

m

j

ji

i

x

v

1

Nowa funkcja celu:

, przy ograniczeniach:

P

u a

v b

j

j

i i

i

n

j

m





o

¦

¦

1

1

max

3°

przy

czym:





d

u

v

c

j

i

ji



 



j

m

i

n

j

i

,

,...,

,...,

t

u v

0

1

1

Algorytm:

1° rozwi

ązaü zadanie dualne dla dowolnych wartoĞci początkowych

i

,

u

v

2° sprawdzi

ü ograniczenia (1°) i (2°),

a) je

Ğli są speánione, to jest to rozwiązanie optymalne zadania pierwotnego i

zarazem ca

áego zadania transportowego,

b) je

Ğli nie są speánione, przyjąü nowe wartoĞci

i

, rozwi

ązaü dla nich zadanie

dualne a nast

Ċpnie wróciü do punktu 2°.

u

v

J.Stadnicki Optymalizacja

24

Przyk

áad:

Przyjmijmy dane liczbowe zadania transportowego:

»

»

»

»

¼

º

«

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

45

15

10

30

55

30

15

b

a

,

,

^ `

3

4

5

7

6

8 13

9

3

7

2

3

ji

c

ª

º

«

»

«

»

«

»

¬

¼

c

i

=1...4

j

=1..3

1

q inicjalizacja zmiennych dualnych:

,

¦

n

i

ji

j

x

u

1

¦

m

j

ji

i

x

v

1

pocz

ątkowo przyjmujemy:

0

j

u

,

^ `

i

j

v

min

c

i

0

ji

,

x

,

>

@

T

0

0

0

u

>

@

T

3

2

7

3

v

Z

4

q Ÿ,

Īe przepáywy niezerowe (

x

ji

>0 ) s

ą moĪliwe tylko wzdáuĪ tych

kraw

Ċdzi, dla których speániony jest warunek

0





i

j

ji

v

u

c

.

1

2

3

4

1 3+0-3=0

7+0-7=0

3+0-2=1 4+0-3=1

2 5+0-3=2

7+0-7=0

2+0-2=0 6+0-3=3

3 8+0-3=5 13+0-7=6

9+0-2=7 3+0-3=0

2

q korzystając z algorytmu cechowania, ocechowaü powstaáą sieü:

(s

1

,15

(s

1

,15)

t

1

[10,0]

[30,0]

[

’,0]

[

’,0]

[55,0]

(-,

’)

(s

3

,45)

t

4

(s,15)

s

1

(s,30

[30,0]

)

(s,55)

s

3

(s

2

,15)

t

3

[45,0]

(s

2

,10)

t

2

(s

1

,0)

[

’,0]

[15,0]

s

s

2

t

[

’,0]

[

’,0]

[15,0]

J.Stadnicki Optymalizacja

25

Sie

ü po 1 ocechowaniu:

t

4

t

2

t

1

s

3

s

1

[45,45]

t

3

[10,10]

[30,15]

[

’,45]

[

’,0]

[

’,15]

[30,25]

[

’,15]

[15,15]

s

s

2

t

[

’,10]

[15,15]

[55,45]

Otrzymane rozwi

ązanie nie speánia wszystkich warunków

(wzd

áuĪ áuku

t

¦

t

m

j

i

ji

b

x

1

1

t mo

Īna powiĊkszyü przepáyw).

3

q zmiana przepáywu:

Aby zwi

Ċkszyü przepáyw trzeba utworzyü nowe áuki miĊdzy nie ocechowanymi

wierzcho

ákami tj. s

1

i t

1

.

Zbiór ocechowanych wierzcho

áków s

j

:

^

`

3

2,

J

.

Zbiór nie ocechowanych wierzcho

áków t

i

:

^ `

1

I

. (dope

ánienie zbioru

J

)

Niech :

^

`

I

i

,

J

j

v

u

c

min

i

j

ji









:

G

,

tzn.

2

5

3

0

8

2

3

0

5

¿

¾

½

¯

®

­









min

G

4

q zmiana zmiennych dualnych:

Nowym rozwi

ązaniem dualnym jest:

¯

®

­







I

j

,

u

J

j

,

u

u

j

j

j

G

,

¯

®

­







I

i

,

v

J

i

,

v

v

i

i

i

G

czyli

>

@

>

T

T

0

0

2

0

0

2

0



u

@

oraz

>

@

T

7

5

3

2

7

2

3



v

>

T

3

2

@

Ta zmiana usuwa

áuk s

1

t

2

i tworzy nowy s

2

t

1

.

J.Stadnicki Optymalizacja

26

t

4

t

2

t

1

s

3

s

1

[45,45]

t

3

[10,10]

[30,15]

[

’,45]

[

’,0]

[

’,15]

[30,25]

[

’,15]

[15,15]

s

s

2

t

[

’,10]

[15,15]

[55,45]

Dla nowej sieci powtarzamy post

Ċpowanie od punktu 2qaĪ do chwili speánienia

ogranicze

Ĕ na popyt:

.

¦

t

j

i

ji

b

x

1

m

n

m

m

x

W algorytmie na przemian zmieniamy rozwi

ązania prymalne i dualne (krok 1q).

x Ocechowując wierzchoáki sieci dąĪymy do maksymalnego przepáywu rozwiązania

dualnego

a tym samym znajdujemy sprz

ĊĪone

rozwi

ązanie prymalne, które

.

P

u a

v b

j

j

i i

i

j





o

¦

¦

1

1

max

 

i

n

j

m

x

¦

¦

1

Q

c x

ji

ji

o min

1

x KaĪde przejĞcie zwiĊksza wartoĞü przepáywu o co najmniej jedną jednostkĊ a

liczba przej

Ğü jest ograniczona popytem, który musi byü zaspokojony

, co oznacza

Īe algorytm jest skoĔczony.

¦

t

j

i

ji

b

x

1

x Zgodnie z tw. o dualnoĞci otrzymane rozwiązania zadaĔ prymalnego i dualnego

s

ą optymalne.

J.Stadnicki Optymalizacja

27

Zastosowania:

Zadanie transportowe:

Producenci

R

j

jednorodnego produktu, z których ka

Īdy ma zdolnoĞü produkcyjną

a

j

, zaopatruj

ą

N

i

odbiorców, z których ka

Īdy zgáasza zapotrzebowanie

b

i

.

Zak

áada siĊ, Īe áączne zdolnoĞci produkcyjne pokrywają lub przekraczają áączne

zapotrzebowanie.

Dane s

ą jednostkowe koszty transportu od

j

-tego producenta do

i

-tego odbiorcy

c

ji

.

Wyznaczy

ü plan przewozu miĊdzy dostawcami a odbiorcami tj. macierz przewozu

{ x

ji

}

minimalizuj

ący caákowity koszt transportu.

Np.

Odbiorcy

Producenci

N

1

N

2

N

3

N

4

Poda

Ī

a

j

R

1

50

40

50

20

70

R

2

40

80

70

30

50

R

3

60

40

70

80

80

Popyt

b

i

40

60

50

50

^ `

»

»

»

»

¼

º

«

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

50

50

60

40

80

50

70

80

70

40

60

30

70

80

40

20

50

40

50

b

a

c

ji

c

Rozwi

ązanie:

^ `

8000

0

20

60

0

10

0

0

40

40

30

0

0

»

»

»

¼

º

«

«

«

¬

ª

Q

xˆ

ˆ

ji

x

J.Stadnicki Optymalizacja

28

Zadanie transportowo-produkcyjne:

Producenci

R

j

jednorodnego produktu, z których ka

Īdy ma zdolnoĞü produkcyjną

a

j

, zaopatruj

ą

N

i

odbiorców, z których ka

Īdy zgáasza zapotrzebowanie

b

i

.

Zak

áada siĊ, Īe áączne zapotrzebowanie przekraczaja áączne zdolnoĞci produkcyjne.

Dane s

ą jednostkowe koszty transportu od

j

-tego producenta do

i

-tego odbiorcy

c

ji

oraz jednostkowe koszty produkcji

j

-tego producenta

h

j

.

Produkty nie zosta

áy jeszcze wytworzone i naleĪy podjąü decyzjĊ gdzie je

produkowa

ü i jak rozesáaü do odbiorców aby zminimalizowaü áączne koszty

produkcji i transportu.

x Wprowadzimy fikcyjnego odbiorcĊ

N

n+1

, który reprezentowa

ü bĊdzie nie

wykorzystane zdolno

Ğci produkcyjne poszczególnych producentów i którego

zapotrzebowanie:

¦

¦





i

i

j

j

i

b

a

b

1

1

1

n

m

n

i

,

m

j

!

!

1

1

tzn.

áączne zdolnoĞci produkcyjne – áączne zapotrzebowanie,

x Utworzymy macierz áącznych kosztów transportu i produkcji:

ji

j

ji

c

h

k



n

i

,

m

j

!

!

1

1

0

przy czym

tzn.

Īe nie wykorzystanym zdolnoĞciom produkcyjnym odpowiadają zerowe

koszty.

1



m

,

j

k

Np.

Odbiorcy

Producenci

N

1

N

2

N

3

N

4

Odbiorca

fikcyjny

N

5

Poda

Ī

a

j

R

1

50

40

50

20

0

70

R

2

40

80

70

30

0

50

R

3

60

40

70

80

0

80

Popyt

b

i

40

60

50

80

30

J.Stadnicki Optymalizacja

29

^ `

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

»

»

»

¼

º

«

«

«

¬

ª

80

50

50

60

40

80

50

70

0

80

70

40

60

0

30

70

80

40

0

20

50

40

50

b

a

c

ji

c

Rozwi

ązanie:

^ `

143600

30

0

0

50

0

0

10

0

0

40

0

40

50

10

0

»

»

»

¼

º

«

«

«

¬

ª

Q

x

ˆ

ˆ

ji

x

Uwaga:
Ostatnia kolumna w macierzy

{ x

ji

}

odpowiadaj

ąca fikcyjnemu odbiorcy wyraĪa nie

wykorzystane zdolno

Ğci produkcyjne poszczególnych producentów.

Zadanie lokalizacji produkcji:

Dana jest lokalizacja

n

odbiorców na pewien towar oraz lokalizacja

m

punktów, w

których mo

Īliwa jest produkcja tego towaru.

Pozosta

áe dane przyjmiemy jak zadaniu poprzednim tj.: podaĪ –

a

j

, popyt –

b

i

,

koszty transportu –

c

ji

, koszty produkcji –

h

j

.

Wyznaczy

ü lokalizacjĊ producentów towaru, która zaspokaja popyt i minimalizuje

áączne koszty produkcji i transportu.

Zadanie rozwi

ązujemy jak poprzednio.

Zadanie minimalizacji pustych przebiegów:
(optymalizacja kr

ąĪenia Ğrodków transportowych rozwoĪących towar)

pusty przebieg = przejazd bez

áadunku,

Przewóz towaru odbywa si

Ċ miĊdzy

n

punktami tworz

ącymi ukáad zamkniĊty ( tzn.

wymiana towaru odbywa si

Ċ tylko miĊdzy punktami a kaĪdy z nich moĪe byü

dostawc

ą i odbiorcą).

Do ka

Īdego z punktów przywozi siĊ i wywozi towar nadający siĊ do przewozu

Ğrodkiem transportu tego samego rodzaju. Nadmiar towaru w danym punkcie (o ile
istnieje) nale

Īy przewieĞü do innego punktu.

Znane s

ą odlegáoĞci miĊdzy punktami

d

ji

(j=i=1...n)

, znany jest równie

Ī przewóz

mi

Ċdzy punktami

x

ji

wyra

Īony liczbą peánych Ğrodków transportu (np.

samochodów).

J.Stadnicki Optymalizacja

30

Dla ka

Īdego punktu

j

mo

Īna okreĞliü:

¦

z

n

i

ji

j

x

w

1

– liczb

Ċ Ğrodków transportu potrzebną do wywiezienia towaru,

¦

z

n

i

ji

j

x

p

1

– liczb

Ċ Ğrodków transportu potrzebną do przywiezienia towaru.

Dla wszystkich

n

punktów

¦

¦

n

j

j

n

j

j

p

w

1

1

lecz dla poszczególnego punktu

w

j

nie musi by

ü równe

p

j

.

Zatem punkty w których wywóz jest wi

Ċkszy od przywozu (

w

j

>

p

j

) nale

Īy

zaopatrzy

ü w puste Ğrodki transportu.

Za optymalny uznamy taki przebieg, dla którego suma iloczynów

áadownoĞci

Ğrodków transportu i przejechanych przez nie odlegáoĞci bĊdzie minimalna.

Np.
Zminimalizowa

ü puste przebiegi samochodów o áadownoĞci 50t, przewoĪącymi

towar mi

Ċdzy siedmioma miastami (L...S) stanowiącymi ukáad zamkniĊty.

d

ji

L

M

N

O

P

R

S

w

j

L

0

20

10

100

150

200

100

1000

M

0

40

20

30

50

20

2000

N

0

100

150

200

100

1000

O

0

40

30

150

100

P

0

80

70

200

R

0

60

1000

S

0

500

p

j

500

1000

2000

1000

1000

300

0

5800

Dostawcami b

Ċdą punkty dla których:

p

j

>

w

j

(przywóz > wywozu)

i odwrotnie odbiorcami punkty dla których:

w

j

>

p

j

(wywóz > przywozu) .

L: (500-1000)/50=

-10

odbiorca,

M: (1000-2000)/50=

-20

odbiorca

N: (2000-1000)/50=

20

dostawca,

O: (1000-100)/50=

18

dostawca,

P: (1000-200)/50=

16

dostawca,

R: (300-1000)/50=

-14

odbiorca,

S :

(0-500)/50=

-10

odbiorca.

J.Stadnicki Optymalizacja

31

Odbiorcy

Dostawcy

L

M

R

S

Poda

Ī

a

j

N

10

40

200

100

20

O

100

20

30

150

18

P

150

30

80

70

16

Popyt

b

i

10

20

14

10

Zadanie rozwi

ązujemy jak zadanie transportowe.

Rozwi

ązanie:

^ `

2880

10

0

6

0

0

14

4

0

0

0

10

10

»

»

»

¼

º

«

«

«

¬

ª

Q

xˆ

ˆ

ji

x

J.Stadnicki Optymalizacja

32

J.Stadnicki Optymalizacja

33

OPTYMALIZACJA NA GRAFACH

Grafem (nieskierowanym)

G=( V, E )

nazywamy struktur

Ċ skáadającą siĊ ze

sko

Ĕczonego

n

- elementowego zbioru wierzcho

áków

V={v

1

,...,v

n

}

oraz

sko

Ĕczonego zbioru

m

- elementowego zbioru kraw

Ċdzi

E={e

1

,...,e

m

}

áączących

nieuporz

ądkowane pary wierzchoáków.

Grafem skierowanym (digrafem) jest graf, w którym E jest zbiorem
uporz

ądkowanych par wierzchoáków zwanych áukami.

Wierzcho

áki poáączone krawĊdzią nazywamy przylegáymi (sąsiednimi).

Ci

ąg krawĊdzi (

v

i

, v

i

) nazywamy p

Ċtlą.

Dwie kraw

Ċdzie miĊdzy tymi samymi wierzchoákami nazywamy równolegáymi lub

wielokrotnymi.

Drog

ą (ĞcieĪką) w grafie

G=( V, E )

nazywamy ci

ąg niejednakowych krawĊdzi lub

áuków (

e

k1

,..., e

kp

) wyznaczonych przez ci

ąg wierzchoáków (

v

i1

,..., v

ip

) i takich,

Īe

e

k1

=(

v

i0

,..., v

i1

), ... ,

e

kp

=(

v

i(p-1)

,..., v

ip

).

Oznacza to,

Īe droga prowadzi od

v

i0

(pocz

ątku drogi) do

v

ip

(ko

Ĕca drogi).

Liczb

Ċ krawĊdzi

p

– nazywamy d

áugoĞcią drogi.

Drog

Ċ zawierającą wszystkie krawĊdzie grafu nazywamy drogą Eulera.

1

2

3

4

5

6

1

2

3

4

5

Graf

(nieskierowany)

Digraf

(graf skierowany)

J.Stadnicki Optymalizacja

34

Droga

Eulera

Graf,

w

którym

droga

Eulera nie istnieje

Je

Īeli wszystkie wierzchoáki drogi są róĪne, to jest to droga prosta.

Drog

Ċ prostą, której początek pokrywa siĊ z koĔcem (

v

i0

=

v

ip

) nazywamy cyklem.

Cykl obejmuj

ący wszystkie wierzchoáki grafu nazywa siĊ cyklem Hamiltona.

Graf, w którym istnieje co najmniej jedna droga pomi

Ċdzy kaĪdą parą wierzchoáków,

nazywamy grafem spójnym.

PROBLEM NAJKRÓTSZEJ DROGI

Rozpatrzmy graf skierowany

G=( V, E )

utworzony z wierzcho

áków poáączonych

kraw

Ċdziami (

i, j

).

Ka

Īdemu áukowi przyporządkowano nieujemną liczbĊ

w

ij

• 0

zwan

ą wagą (moĪe to

by

ü np. dáugoĞü odcinka drogi lub koszt transportu).

Znale

Ĩü drogĊ o najmniejszej wadze (najkrótszą) oraz jej wagĊ (dáugoĞü) pomiĊdzy

ustalonymi wierzcho

ákami

s

(

Ĩródáem) i

t

(odp

áywem).

Algorytm Dijkstry

Idea: po

áukach grafu przemieszczamy siĊ od wierzchoáka

s

do

t

cechuj

ąc

tymczasowo kolejne wierzcho

áki bieĪącymi sumami wag (odlegáoĞciami) od

wierzcho

áka

s

w kierunku wierzcho

áka

t

. Tymczasow

ą cechĊ wierzchoáka

przyjmujemy za sta

áą, gdy jest równa najmniejszej sumie wag (odlegáoĞci) od

Ĩródáa.

J.Stadnicki Optymalizacja

35

Przyk

áad:

Znale

Ĩü drogĊ o najmniejszej sumie wag (najkrótszą) pomiĊdzy wierzchoákami

s

i

t

.

Kroki algorytmu:

1. nadaj wierzcho

ákowi

s

cech

Ċ 0 (ustaloną) a pozostaáym cechĊ tymczasową

’,

2. ka

Īdemu sąsiedniemu do wierzchoáka o ustalonej cesze wierzchoákowi

i

nadaj

cech

Ċ tymczasową równą sumie wag (dáugoĞci) áuków od wierzchoáka o

ustalonej cesze do

i ,

3. wybierz cech

Ċ o najmniejszej wartoĞci i przyjmij, Īe jest to ustalona cecha

wierzcho

áka,

4. je

Ğli wierzchoáek

t

zosta

á osiągniĊty – zakoĔcz postĊpowanie. W przeciwnym

wypadku powró

ü do punktu 2.

Rozwi

ązanie:

Drog

ą o najmniejszej sumie wag (najkrótszą) jest droga: s

ĺ

4

ĺ

3

ĺ

t

o sumie wag (d

áugoĞci) 9 + 2 + 7 = 18

Uwaga:

Algorytm mo

Īna zastosowaü równieĪ do grafu nieskierowanego, zastĊpując kaĪdą z

kraw

Ċdzi (

i

,

j

) par

ą áuków (

i

,

j

) oraz (

j

,

i

) o tej samej wadze (d

áugoĞci) co

zast

Ċpowana krawĊdĨ.

Je

Īeli áuki w grafie skierowanym nie mają przyporządkowanych wag, kaĪdemu z

nich przypisujemy taka sam

ą wagĊ (np. jeden).

Graf mo

Īe zawieraü wiele najkrótszych dróg o tej samej wartoĞci, algorytm znajduje

jedn

ą z nich.

Aby znale

Ĩü najkrótszą drogĊ z wierzchoáka

s

do wszystkich pozosta

áych

n

wierzcho

áków sieci naleĪy

n

razy powtórzy

ü algorytm zmieniając wierzchoáek

t

.

s 1 2 3 4 t

Inicjalizacja

0

’ ’ ’ ’ ’

Iteracja 1

0
0

15
15

’
’

’
’

9
9

’
’

Iteracja 2

0
0

13
13

’
’

11
11

9
9

’
’

Iteracja 3

0
0

13
13

’
’

11
11

9
9

18
18

Iteracja 4

0
0

13
13

48
48

11
11

9
9

18
18

s

4

1

2

3

t

[2]

[2]

[9]

[4]

[3]

[7]

[6]

[5]

[15]

[35]

[16]

[21]

J.Stadnicki Optymalizacja

36

Problem wyznaczania najkrótszej drogi w grafie mo

Īna sprowadziü do zadania

programowania zero-jedynkowego

1

postaci:

Zminimalizowa

ü

 

min

)

,

(

o

¦

E

j

i

ij

ij

x

w

Q x

Przy ograniczeniach

¦

¦





°

¯

°

®

­



z



E

j

E

i

ij

ij

t

i

dla

t

s

i

dla

s

i

dla

x

x

)

(

)

(

1

,

0

1

Przy czym

^ `

1

,

0



ij

x

Poniewa

Ī:

¦

E

j

ij

x

)

(

jest sum

ą áuków wychodzących z wierzchoáka,

¦

E

i

ij

x

)

(

jest sum

ą áuków wchodzących do wierzchoáka.

PROBLEM KOMIWOJA

ĩERA (TRAVELLING SALESMAN PROBLEM)

Komiwoja

Īer ma odwiedziü dokáadnie jeden raz kaĪdą z wybranych miejscowoĞci, a

nast

Ċpnie powróciü do tej z której zacząá podróĪ. Znane są koszty przejazdu (waga)

mi

Ċdzy kaĪdą parą miejscowoĞci. Zaplanowaü drogĊ przejazdu tak, by kaĪdą

miejscowo

Ğü odwiedziá jeden raz a caákowity koszt podróĪy byá najmniejszy.

Problem polega na znalezieniu najkrótszego cyklu Hamiltona (obejmuj

ącego

wszystkie wierzcho

áki grafu) w

n

wierzcho

ákowym peánym grafie (w którym kaĪda

para wierzcho

áków jest poáączona áukiem).

Cykle Hamiltona:

1. 1

o2o3o4o1,

2. 1

o4o3o2o1,

3. 1

o2o4o3o1,

4. 1

o4o2o3o1,

5. 1

o3o2o4o1,

6. 1

o3o4o2o1.

Dla 4 wierzcho

áków mamy (4-1)!=3!=1· 2 · 3 =6 cykli,

Dla

n

wierzcho

áków mamy (

n

-1)! cykli.

1

Problem programowania zero-jedynkowego omówiono w oddzielnym rozdziale.

3

4

1

2

œ

J.Stadnicki Optymalizacja

37

Problem komiwoja

Īera moĪna rozwiązaü generując wszystkie cykle Hamiltona i

porównuj

ąc ich wagi.

Wada: post

Ċpowanie nieefektywne

(np. dla n=20 trzeba wygenerowa

ü 19! > 10

17

cykli)

Algorytm podzia

áu i ograniczeĔ

Kroki algorytmu:

1. rozbi

ü zbiór rozwiązaĔ na dwa podzbiory za pomocą wyróĪnionego áuku (

i

,

j

) :

- jeden zawieraj

ący áuk (

i

,

j

),

- drugi nie zawieraj

ący áuku (

i

,

j

),

podzia

áu dokonaü w oparciu o zasadĊ heurystyczną zmierzającą do redukcji

czasu oblicze

Ĕ,

2. obliczy

ü dolne ograniczenia wag

LB

(

Lower Bound

) w podzbiorach,

3. wybra

ü podzbiór rozwiązaĔ posiadający mniejszą wartoĞü dolnego

ograniczenia

LB

,

4. post

Ċpowanie kontynuowaü aĪ do otrzymania cyklu Hamiltona,

5. rozwi

ązanie koĔcowe powstaje z tych podzbiorów, dla których dolne

ograniczenia s

ą mniejsze niĪ dáugoĞü najkrótszego dotychczas znalezionego

rozwi

ązania.

Zdefiniujmy graf za pomoc

ą macierzy wag:

^ `

ij

w

W

w

ij

=

’ -

oznacza brak

áuku miĊdzy wierzchoákami,

w

ij



w

ji

- oznacza,

Īe áuki miĊdzy tymi samymi wierzchoákami mają róĪne wagi

(macierz wag jest niesymetryczna),

Cykl Hamiltona zawiera wszystkie wierzcho

áki grafu a kaĪdy z wierzchoáków

wyst

Ċpuje w cyklu tylko jeden raz.

 

Ka

Īdy cykl Hamiltona zawiera jeden element z kaĪdego wiersza i jeden element z

ka

Īdej kolumny macierzy wag.

 

Je

Ğli odejmiemy staáą

k

od wszystkich elementów jakiego

Ğ wiersza lub jakiejĞ

kolumny macierzy wag, to waga cyklu Hamiltona zmniejszy si

Ċ o tĊ staáą





¦

¦









E

j

i

ij

E

j

i

ij

k

w

k

w

)

,

(

)

,

(

a rozwi

ązanie optymalne pozostanie optymalne.

REDUKCJA

Je

Īeli po odjĊciu staáych od wierszy i kolumn, kaĪdy wiersz i kolumna zawierają

dok

áadnie jedno zero, a pozostaáe elementy macierzy są nieujemne, to caákowita

suma odj

Ċtych liczb jest dolnym ograniczeniem wagi zbioru pozostaáych rozwiązaĔ.

J.Stadnicki Optymalizacja

38

Heurystyka wyboru

áuku podziaáu grafu:

Optymalnego cyklu szukamy po lewej stronie grafu (dolnej podmacierzy trójk

ątnej

macierzy wag), bowiem wtedy redukowany jest rozmiar problemu.

Aby okre

Ğliü áuk podziaáu powodujący najwiĊkszy wzrost wartoĞci dolnego

ograniczenia w prawej cz

ĊĞci grafu (górnej podmacierzy trójkątnej macierzy wag)

wybieramy ten element zerowy, który zamieniony na

’

pozwala w sumie najwi

Ċcej

odj

ąü od odpowiedniego wiersza i odpowiedniej kolumny.

Uwaga: skuteczno

Ğü heurystyki zaleĪy od danych zadania. W wiĊkszoĞci

przypadków rozmiar zadania istotnie si

Ċ redukuje. Są jednak takie przypadki, w

których liczba dzia

áaĔ wzrasta wykáadniczo i algorytm staje siĊ bezuĪyteczny.

Przyk

áad:

1 2 3 4 5 6

Macierz mo

Īna zredukowaü odejmując od elementów kolejnych wierszy najmniejsze

z warto

Ğci: 3, 4, 16, 7, 25, 3

(3+4+16+7+25+3=58)

6

5

4

3

2

1

6

5

4

3

2

1

a od elementów
kolumn:

(3) : 15,

(4) : 8,

(15+8=23)

(LB=58+23=81)

Wybieramy jako

áuk podziaáu áuk (6, 3) bo:

6,3

,3

6,

( )

( )

0

max

i

j

i

j

w

a

w

w



o

¦

¦

Jeden z otrzymanych podzbiorów nie b

Ċdzie zawieraá áuku (6, 3), zatem:

w

6,3

=

’

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

f

f

f

f

f

f

92

46

18

88

3

25

33

88

46

28

7

56

80

90

39

28

16

36

17

45

16

21

42

77

4

9

33

13

93

3

6

5

4

3

2

1

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

f

f

f

f

f

f

89

43

15

85

0

0

8

63

21

3

0

49

73

83

32

12

0

20

1

29

12

17

38

73

0

6

30

10

90

0

6

5

4

3

2

1

> @

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

f

f

f

f

f

f

89

31

0

85

0

0

0

48

21

3

0

49

58

83

32

12

0

12

1

29

12

17

30

58

0

6

30

2

75

0

6

5

4

3

2

1

J.Stadnicki Optymalizacja

39

1

2 4 5 6

1

2

3

4 5

6

> @

1

0

2

30

6

2 0

30 17

12

3 29

1

12

0

4 32 83

49

0

5 3

21

0

0

f

ª

º

«

»

f

«

»

f

«

»

«

»

f

«

»

«

»

f

¬

¼

wybieramy

áuk (6, 4), zatem:

w

4,6

=

’

 

 

od wiersza (4) mo

Īna odjąü 32

od kolumny (3) mo

Īna odjąü 48

Ÿ

LB=81+32=113

Ÿ LB= 81+48=129

1 2 4 5

1

2

4

5

6

> @

»

»

»

»

¼

º

«

«

«

«

¬

ª

f

f

f

0

21

3

0

12

1

29

17

30

0

30

2

0

5

3

2

1

áuk (3, 4) trzeba odrzuciü bo
rozwi

ązanie zawiera áuki (4, 6) i

(6, 3)

Ÿ wierzchoáek (4) byáby

odwiedzany dwukrotnie.
Zatem:

w

3,4

=

’

1 2 4 5

Wszystkie

rozwi

ązania

Rozwi

ązania

z (6, 3)

Rozwi

ązania

bez (6, 3)

LB=81

LB=129

LB=81

> @

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

f

f

f



f



f



f



f

89

31

85

0

0

0

0

48

48

21

3

0

49

10

48

58

83

32

12

0

12

1

29

12

17

30

10

48

58

0

6

30

2

27

48

75

0

6

5

4

3

2

1

Rozwi

ązania

z (6, 3)

Rozwi

ązania z

(6, 3) i (4, 6)

Rozwi

ązania z

(6, 3) i bez (4, 6)

LB=81

LB=113

LB=81

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

¬

ª

f

f



f





f

f

f

0

0

21

3

17

32

49

51

32

83

0

32

32

0

12

1

29

12

17

30

0

6

30

2

0

5

4

3

2

1

J.Stadnicki Optymalizacja

40

Do podzia

áu wybieramy áuk (2, 1) co pozwala na odjąü 17 od

elementów (2) wiersza i 3 od elementów 1 kolumny.
LB=81+17+3=101

2

4

5

1 2 4

5

àuk (1, 2) trzeba
odrzuci

ü bo

rozwi

ązanie zawiera

áuk (2, 1) i wierzchoáek
(1) by

áby odwiedzany

dwukrotnie

(cykl).

Zatem:

w

1,2

=

’

Od elementów (1) wiersza mo

Īna odjąü 2

a od elementów (1) kolumny (1).
LB=81+2+1=84

2 4 5

2

4

5

LB=84 LB=84

Do

podzia

áu wybieramy áuk (1, 4), od elementów

(1) wiersza mo

Īna odjąü 28,

LB=84+28=112

> @

»

»

»

»

¼

º

«

«

«

«

¬

ª

f

f

f

f

0

21

3

0

1

29

17

30

0

30

2

0

5

3

2

1

> @

»

»

»

¼

º

«

«

«

¬

ª

f

f

0

21

0

1

30

2

0

5

3

1

»

»

»

»

¼

º

«

«

«

«

¬

ª

f



f







f

f

f

0

21

0

3

3

0

1

26

3

29

0

17

17

13

17

30

30

2

0

5

3

2

1

Rozwi

ązania z

(6, 3) i (4, 6)

Rozwi

ązania z

(6, 3), (4, 6) i (2, 1)

Rozwi

ązania z

(6, 3) i (4, 6) bez (2, 1)

LB=81

LB=101

LB=81

»

»

»

¼

º

«

«

«

¬

ª

f



f







f

0

20

1

21

0

0

1

1

28

2

30

0

2

2

5

3

1

> @

»

»

»

¼

º

«

«

«

¬

ª

f

f

f

0

20

0

1

28

0

5

3

1

J.Stadnicki Optymalizacja

41

2 5

2 4

5

Otrzymana macierz jest 2 stopnia.

 

Nie mamy mo

ĪliwoĞci wyboru áuku do uzupeánienia dotychczasowej drogi

komiwoja

Īera – oba pozostaáe áuki muszą uzupeániü drogĊ komiwojaĪera.

 

Droga komiwoja

Īera:

(1, 4, 6, 3, 5, 2, 1)

LB=84+20+104

 

Wszystkie rozwi

ązania poĞrednie z LB<104 moĪna

pomin

ąü.

 

Tylko jedno rozwi

ązanie poĞrednie posiada

LB=101<104. Rozwi

ązanie to zawiera áuki: (6, 3),

(4,6) i (2, 1).

1 2 4 5

Powtarzaj

ąc postĊpowanie

otrzymamy drugie rozwi

ązanie

optymalne o warto

Ğci LB=104

zawieraj

ące áuki: (6, 3), (4, 6),

(5, 1) i (1, 4) bez (2, 1)

Drog

Ċ optymalną komiwojaĪera moĪna uzupeániü

tylko

áukami: (3, 2) i (2, 5).

Zatem znale

ĨliĞmy dwa rozwiązania optymalne

zadania.

Uwaga:
W grafie o 6-ciu wierzcho

ákach istnieje 5!=120

dróg. Dla wyboru optymalnej drogi wyznaczyli

Ğmy

13 rozwi

ązaĔ poĞrednich!

Rozwi

ązania z

(6, 3), (4, 6) i (2, 1)

Rozwi

ązania z

(6, 3), (4, 6), (2, 1) i (1,4)

Rozwi

ązania z

(6, 3), (4, 6) i (2, 1) bez (1, 4)

LB=84

LB=112

LB=84

»

»

»

¼

º

«

«

«

¬

ª

f

f



f

f

0

20

0

1

0

28

28

5

3

1

»

¼

º

«

¬

ª

f

f

20

0

5

3

1

2

6

3

5

4

»

»

»

»

¼

º

«

«

«

«

¬

ª

f

f

f

f

f

0

21

0

0

1

26

0

13

30

2

0

5

3

2

1

4

1

2

6

3

5

J.Stadnicki Optymalizacja

42

PROGRAMOWANIE ZERO-JEDYNKOWE

Zadanie programowania zero-jedynkowego

Znale

Ĩü minimum (maksimum):

Q

= c x

T

przy warunkach:

n

,..,

i

,

x

x

i

i

1

1

0

=

=

=

£

×

dla

lub

czym

przy

b

x

A

Wniosek:

Zbiór dopuszczalny zadania zero-jedynkowego jest zbiorem przeliczalnym i
sko

Ĕczonym.

Metody rozwi

ązywania zadania:

1. Przegl

ąd bezpoĞredni (jawny): polega na przeglądzie wszystkich rozwiązaĔ

spe

ániających ograniczenia i wyborze takiego, które minimalizuje funkcjĊ celu.

2. Przegl

ąd poĞredni (niejawny): polega na wykorzystaniu testów (filtrów), które

pozwalaj

ą odrzuciü niektóre spoĞród rozwiązaĔ bez ich bezpoĞredniego

sprawdzania przy za

áoĪeniu, Īe Īadne z odrzuconych rozwiązaĔ nie minimalizuje

funkcji celu.

Leksykograficzny ci

ąg wariantów (rozwiązaĔ):

Niech b

Ċdą dane trzy zmienne przyjmujące dowolne „wartoĞci” (liczbowe lub inne):

d

g

b

a

,

,

,

x

,

x

,

C

,

B

,

A

x

=

=

=

3

2

1

2

1

w podanej kolejno

Ğci.

Utwórzmy wszystkie mo

Īliwe trójkowe poáączenia:

.

3

2

1

x

x

x

2

1

C

B

A

A1, A2

2

1

C

B

A

2

1

C

B

A

B1, B2

C1, C2

d

g

C2

C1

B2

A1

a, A1b, A1g, A1d ¼

b

a

B1

A2

A1

Otrzymany porz

ądek nazywamy porządkiem leksykograficznym.

J.Stadnicki Optymalizacja

43

Filtr:

Dodatkowe ograniczenie pozwalaj

ące na odrzucenie niektórych wariantów

(rozwi

ązaĔ nieoptymalnych) zbioru z porządkiem leksykograficznym.

Rozwa

Īmy przykáad liczbowy:

( )

max

x

x

x

Q

®

+

-

=

3

2

1

5

2

3

x

( )

( )

( )

( )

ï

ï
î

ïï

í

ì

£

+

£

+

£

+

+

£

-

+

6

4

3

4

4

2

2

4

3

2

1

3

2

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

{ }

1

0

3

2

1

,

x

,

x

,

x

Î

Za

áóĪmy, Īe znamy jedno z rozwiązaĔ dopuszczalnych zadania np.

[

] [ ]

( )

3

0

0

1

3

2

1

=

=

x

Q

,

,

x

,

x

,

x

T

T

wtedy

Je

Ğli przyjmiemy, Īe dla rozwiązania optymalnego

, to 3 jest dolnym

oszacowaniem optymalnej warto

Ğci

( )

3

³

x

Q

( )

ˆx

Q

.

Wniosek:

Mo

Īna wprowadziü dodatkowe ograniczenie zwane filtrem:

( )

3

5

2

3

0

3

2

1

³

+

-

x

x

x

Przegl

ąd z filtrem:

Ograniczenie

x

1

,x

2

,x

3

(0)

(1)

(2)

(3)

(4)

Czy zachodzi

(1)...(4) i (0)

Q(x)

0,0,0

0

Nie

0,0,1

5

-1

1

0

1

Tak

5

0,1,0

-2

Nie

0,1,1

3

1

5

Nie

1,0,0

3

1

1

1

0

Tak

3

1,0,1

8

0

2

1

1

Tak

8

1,1,0

1

Nie

1,1,1

6

2

6

Nie

Przy przegl

ądzie leksykograficznym wszystkich wariantów naleĪaáoby wykonaü:

2

3

· 5= 40 operacji oblicze

Ĕ lewych stron wyraĪeĔ (0)...(5).

Zastosowanie filtru ograniczy

áo liczbĊ operacji do 24.

J.Stadnicki Optymalizacja

44

Metoda filtru Balasa

Polega na przegl

ądzie rozwiązaĔ dopuszczalnych z wykorzystaniem ograniczeĔ

filtruj

ących.

Rozwa

Īmy ten sam przykáad liczbowy:

( )

max

x

x

x

Q

®

+

-

=

3

2

1

5

2

3

x

( )

( )

( )

( )

ï

ï
î

ïï

í

ì

£

+

£

+

£

+

+

£

-

+

6

4

3

4

4

2

2

4

3

2

1

3

2

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

{ }

1

0

3

2

1

,

x

,

x

,

x

Î

Zamieniamy kolejno

Ğü zmiennych

tak, aby odpowiada

áy rosnącej kolejnoĞci

wspó

áczynników

funkcji celu

Q

.

i

x

( )

x

i

c

Poniewa

Ī:

[

]

T

x

,

x

,

x

3

1

2

5

3

2

=

Þ

<

<

-

x

Istnieje rozwi

ązanie dopuszczalne:

[

] [ ]

( )

5

1

0

0

3

1

2

=

=

x

Q

,

,

x

,

x

,

x

T

T

wtedy

Dodatkowe ograniczenie (filtr):

(0’)

5

5

3

2

3

1

2

³

+

+

-

x

x

x

Przegl

ąd z filtrem i uporządkowanymi zmiennymi:

Ograniczenie

x

2

,x

1

,x

3

(0’)

(1)

(2)

(3)

(4)

Czy zachodzi

(1)...(4) i (0’)

Q(x)

0,0,0

0

Nie

0,0,1

5

-1

1

0

1

Tak

5

Wyznaczono rozwi

ązanie dopuszczalne, dla którego

Q

.

( )

5

=

x

W

áączamy do listy dopuszczalnych wariantów punkt [0,1,0] i kontynuujemy przegląd.

Ograniczenie

x

2

,x

1

,x

3

(0’)

(1)

(2)

(3)

(4)

Czy zachodzi

(1)...(4) i (0’)

Q(x)

0,1,0

3

Nie

0,1,1

8

0

2

1

1

Tak

8

J.Stadnicki Optymalizacja

45

Wyznaczono polepszone rozwi

ązanie dopuszczalne, dla którego

Q

.

( )

8

=

x

Zatem otrzymujemy nowe ograniczenie filtruj

ące:

(0”)

8

5

3

2

3

1

2

³

+

+

-

x

x

x

W

áączamy do listy dopuszczalnych wariantów punkt [1,1,0] i kontynuujemy przegląd.

Ograniczenie

x

2

,x

1

,x

3

(0”)

(1)

(2)

(3)

(4)

Czy zachodzi

(1)...(4) i (0”)

Q(x)

1,0,0

-2

Nie

1,0,1

3

Nie

1,1,0

1

Nie

1,1,1

6

Nie

Dalsze polepszanie warto

Ğci

jest niemo

Īliwe; rozwiązaniem optymalnym jest

( )

x

Q

[

T

1

1

0

=

x

]

dla którego

Q

.

( )

8

=

x

Liczba operacji do wykonania 16.

Uwaga:
W przypadku wi

Ċkszej liczby zmiennych decyzyjnych ograniczenie liczby operacji

jest jeszcze wi

Ċksze!

Algorytm metody filtru Balasa:

1° Zamie

Ĕ kolejnoĞü zmiennych decyzyjnych, tak aby wystĊpowaáy w kolejnoĞci

zgodnej z odpowiadaj

ącym im wspóáczynnikom funkcji celu uporządkowanymi

rosn

ąco,

2° Zbuduj tablic

Ċ przeglądu wariantów rozwiązaĔ z ograniczeniem filtrującym.

Przegl

ąd wstrzymaj jeĞli znajdziesz wariant speániający wszystkie ograniczenia

áącznie z filtrującym.
Je

Īeli procedura przeglądu wyczerpie siĊ, to albo znalezione do tej pory

rozwi

ązanie jest optymalne, albo nie istnieje.

3° Je

Īeli uda siĊ znaleĨü wariant dający polepszenie funkcji celu, to przyjmij go jako

nowe ograniczenie filtruj

ące i zastąp nim poprzednie.

4° Wznów przeszukiwanie od wariantu po

áoĪonego leksykograficznie wyĪej niĪ ten

który otrzymano w poprzedniej tablicy przegl

ądu.

5° Powró

ü do punktu 2.

J.Stadnicki Optymalizacja

46

PROGRAMOWANIE CA

àKOWITILICZBOWE

Zadanie programowania ca

ákowitoliczbowego

Znale

Ĩü minimum (maksimum):

Q

= c x

T

przy warunkach:

s

ą caákowite oraz

i

x

czym

przy

b

x

A

£

×

0

³

i

x

Wniosek:

Je

Īeli zbiór dopuszczalny zadania caákowitoliczbowego jest ograniczony to jest

zbiorem przeliczalnym.

Metody rozwi

ązywania zadania:

1. Dokona

ü leksykograficznego przeglądu punktów zbioru dopuszczalnego i wybraü

ten, dla którego

Q = min.

Q=c

2

x

1

+c

2

x

2

® max

a

21

x

1

+a

22

x

2

£ b

2

a

11

x

1

+a

12

x

2

£ b

1

0

x

2

x

1

Wady:

· JeĞli zbiór dopuszczalny jest liczny, proces przeszukiwania trwa dáugo.
· JeĞli zmiennych decyzyjnych jest wiĊcej, nie moĪna wyspecyfikowaü wszystkich

punkty nale

Īących do zbioru dopuszczalnego (przestrzeĔ wielowymiarowa).

2. Sprowadzi

ü – o ile to moĪliwe – zadanie programowania caákowitoliczbowego do

zadania programowania zero-jedynkowego i rozwi

ązaü.

J.Stadnicki Optymalizacja

47

Uwaga:

Sprowadzenie zadania ca

ákowitoliczbowego do zadania zero-jedynkowego jest

sensowne wtedy, gdy liczba zmiennych decyzyjnych nie jest du

Īa i gdy ich

maksymalne warto

Ğci są stosunkowo maáe.

Je

Ğli zmienna caákowita

jest ograniczona,

, to mo

Īe byü wyraĪona

jako:

, gdzie:

.

y

p

y

2

0

£

£

,

i

,

1

0

=

i

p

i

i

x

y

å

=

=

0

2

p

,...,

1

x

i

0

=

lub

Tzn.,

Īe zmienna caákowita

zostaje zast

ąpiona

y

1

+

p

zmiennymi binarnymi

.

i

x

Np.

,

1

2

1

2

1

2

1

2

2

15

3

2

1

0

4

×

+

×

+

×

+

×

=

Þ

£

=

y

y

zamiast jednej zmiennej ca

ákowitej otrzymaliĞmy cztery zmienne binarne.

3. Rozwi

ązaü zadanie za pomocą algorytmu programowania liniowego (np.

sympleks) a nast

Ċpnie otrzymane wartoĞci zmiennych decyzyjnych zaokrągliü do

liczb ca

ákowitych.

Wada:

· Rozwiązanie ciągáe moĪe byü róĪne od rozwiązania dyskretnego (caákowitego).

4. Je

Īeli wspóáczynniki w ograniczeniach i w funkcji celu są liczbami caákowitymi, to

stosuj

ąc do rozwiązania algorytm sympleks z elementami gáównymi

wykorzystywanymi podczas wprowadzania wektorów odpowiadaj

ących

zmiennym niebazowym do bazy b

Ċdą równe +1 lub –1 (unikniemy dzielenia)

otrzyma si

Ċ rozwiązanie caákowitoliczbowe.

5. Odrzuci

ü za pomocą odpowiednich ciĊü (páaszczyzn odcinających) te czĊĞci

zbioru dopuszczalnego, które nie zawieraj

ą rozwiązaĔ caákowitoliczbowych.

P

áaszczyzna odcinająca dziaáając jak ograniczenie odcina czĊĞü zbioru

dopuszczalnego nie gubi

ąc Īadnego rozwiązania caákowitoliczbowego.

Rozwi

ązanie w ograniczonym w ten sposób obszarze dopuszczalnym

znajdujemy za pomoc

ą standardowych algorytmów programowania liniowego.

J.Stadnicki Optymalizacja

48

Podstawowe odci

Ċcie Gomory’ego

Q=c

2

x

1

+c

2

x

2

® max

a

21

x

1

+a

22

x

2

£ b

2

0

x

2

a

11

x

1

+a

12

x

2

£ b

1

x

1

Rozpatrzmy zadanie:

max

x

x

Q

®

+

=

2

1

( )

( )

( )

( )

ca

ákowite

x

,

x

x

,

x

x

x

x

x

2

1

2

1

2

1

2

1

4

0

3

4

3

2

1

1

³

£

+

£

+

-

x

1

Q

Q

(

3

/

4

,

7

/

4

)=

10

/

4

(1)

(2)

-1

4

x

2

4

3

3

2

2

1

1

0

W punkcie b

Ċdącym rozwiązaniem

zadania warto

Ğci zmiennych

decyzyjnych nie s

ą caákowite.

Sprowad

Ĩmy zdanie do postaci standardowej:

max

x

x

Q

®

+

=

2

1

( )

( )

( )

( )

ca

ákowite

x

,

x

,

x

,

x

,

x

,

x

,

x

,

x

x

x

x

x

x

x

4

3

2

1

4

3

2

1

4

2

1

3

2

1

4

0

3

4

3

2

1

1

³

=

+

+

=

+

+

-

Rozwi

ązując ukáad wzglĊdem

i

otrzymamy:

1

x

2

x

4

4

4

3

4

3

1

x

x

x

-

+

=

,

3

4

2

3

7

4

4

4

x

x

x

= -

-

.

Za

áóĪmy, Īe wspóáczynniki w równaniach (1), (2) są caákowite.

Wtedy, poniewa

Ī

i

s

ą caákowite oraz prawe strony równaĔ są caákowite,

1

x

2

x

to

i

te

Ī są caákowite.

3

x

4

x

Konstruujemy odci

Ċcie Gomory’ego:

· PoniewaĪ

jest ca

ákowite, to

1

x

3

4

3

4

4

4

x

x

+

-

jest tak

Īe caákowite.

· PoniewaĪ

jest ca

ákowite, to

4

x

4

4

3

4

4

4

3

x

x

x

+

-

+

jest tak

Īe caákowite, a zatem

równie

Ī

4

3

4

4

3

4

3

x

x +

+

jest ca

ákowite.

· PoniewaĪ

i

najmniejsz

ą moĪliwą wartoĞcią poprzedniego wyraĪenia

jest 1.

3

x

0

4

³

x

3

3

4

4

3

3

3

1

1

4

4

4

4

4

x

x

x

x

Þ +

-

³ Þ

+

³

4

Ostatnia nierówno

Ğü jest szukanym dodatkowym ograniczeniem (páaszczyzną

ci

Ċcia), odcinającym czĊĞü zbioru dopuszczalnego, która nie zawiera rozwiązania

ca

ákowitoliczbowego.

Wyra

Īając

i

poprzez

i

otrzymamy:

3

x

4

x

1

x

2

x

(

) (

)

3

2

12

4

8

4

1

3

4

4

3

1

4

1

2

1

2

1

2

1

2

1

£

+

Þ

-

³

-

-

Þ

³

-

-

+

-

+

x

x

x

x

x

x

x

x

J.Stadnicki Optymalizacja

49

J.Stadnicki Optymalizacja

50

Zadanie przyjmie posta

ü:

max

x

x

Q

®

+

=

2

1

( )

( )

( )

( )

( )

3

2

5

4

0

3

4

3

2

1

1

5

2

1

5

4

3

2

1

5

4

3

2

1

4

2

1

3

2

1

=

+

+

³

=

+

+

=

+

+

-

x

x

x

ca

ákowite

x

,

x

,

x

,

x

,

x

x

,

x

,

x

,

x

,

x

x

x

x

x

x

x

(5)

Q

(

2

/

3

,

5

/

3

)=

7

/

3

Q

(2)

(1)

4

x

2

4

3

3

2

2

1

1

0

-1

W punkcie b

Ċdącym rozwiązaniem

zadania warto

Ğci zmiennych

decyzyjnych nie s

ą caákowite.

Wniosek:

Konstruujemy kolejn

ą páaszczyznĊ

ci

Ċcia.

3

5

2

1

3

1

1

3

5

1

2

1

1

3

3

3

3

z(1)

do (5)

x

x

x

x

x

2x

x

x

x

x

Þ = + -

+ + - +

= Þ

= +

-

x

1

3

5

1

2

3

2

3

2

5

2

2

5

1

2

2

3

3

3

3

z(1) do (5)

x

x

x

x

x

2x

x

x

x

x

Þ =

+ -

+

- +

+

= Þ

= -

-

3

5

5

3

5

2

1

2

3

3

3

x

x

x

x

x

+

-

+

³ Þ

+

³ 1

2

x

5

1

3

2

z(5)

x

x

Þ = -

-

(

) (

)

1

2

1

2

1

2

1

2

1

2

1

2 3 2

1

1

6

4

2

1

3

3

x

x

x

x

x

x

x

x

x

x

+ -

+

-

-

³

Þ + - + -

-

³

Þ -

-

³ -6

ostatecznie:

1

2

2

x

x

+

£

Zadanie przyjmie posta

ü:

max

x

x

Q

®

+

=

2

1

( )

( )

( )

( )

( )

( )

2

6

3

2

5

4

0

3

4

3

2

1

1

6

2

1

5

2

1

6

5

4

3

2

1

6

5

4

3

2

1

4

2

1

3

2

1

=

+

+

=

+

+

³

=

+

+

=

+

+

-

x

x

x

x

x

x

ca

ákowite

x

,

x

,

x

,

x

,

x

,

x

x

,

x

,

x

,

x

,

x

,

x

x

x

x

x

x

x

x

1

(6)

(1)

Q

(1,1)=2

Q

(2)

(5)

-1

4

x

2

4

3

3

2

2

1

1

0

W punkcie b

Ċdącym

rozwi

ązaniem zadania wartoĞci

zmiennych decyzyjnych s

ą

ca

ákowite.

Punkt ten jest rozwi

ązaniem

zadania.

Algorytm Gomory’ego:

1° Odrzu

ü warunek caákowitoliczbowoĞci rozwiązania i rozwiąĪ zadanie jak zadanie

programowania liniowego (np. procedur

ą sympleks),

2° Je

Ğli rozwiązanie nie istnieje zadanie jest sprzeczne; zakoĔcz algorytm,

3° Je

Ğli rozwiązanie istnieje i wszystkie zmienne są caákowite, jest to rozwiązanie

zadania; zako

Ĕcz algorytm,

4° Je

Ğli rozwiązanie istnieje a nie wszystkie zmienne decyzyjne są caákowite, dla

zmiennej o najmniejszym numerze utwórz równanie p

áaszczyzny ciĊcia,

5° Do

áącz równanie do istniejących ograniczeĔ i wróü do punktu 1°.

J.Stadnicki Optymalizacja

51

PROGRAMOWANIE NIELINIOWE

Je

Īeli wektor zmiennych decyzyjnych

n

R

x



, tzn. jego sk

áadowe są liczbami a nie

funkcjami, wtedy klasyfikacja problemu optymalizacji zale

Īy od postaci funkcji celu

i funkcji ogranicze

Ĕ

:

 

Q x

 

x

i

g

a) Problem programowania liniowego: charakteryzuje si

Ċ liniowymi funkcjami

celu i ogranicze

Ĕ,

b) Problem programowania nieliniowego: wyst

Ċpuje wtedy, gdy co najmniej

jedna z funkcji jest nieliniowa wzgl

Ċdem wektora

x

,

c) Problem programowania kwadratowego: wyst

Ċpuje wówczas, gdy funkcja

celu ma posta

ü

Q

, gdzie:

a

– sta

áa,

b

– wektor,

A

– macierz kwadratowa a ograniczenia

 

x

A

x

x

b

x

,

a

5

0





T

T

 

L

n

x

i

g

s

ą funkcjami liniowymi,

d) Problem programowania geometrycznego: wyst

Ċpuje wówczas, gdy

funkcje celu i ograniczenia s

ą uogólnionymi wielomianami potĊgowymi z

rzeczywistymi wyk

áadnikami potĊg

a

jli

:

,

 

¦ –

l

i

a

i

jl

j

jli

x

c

f

1

1

x

np.

 

123

121

112

111

2

1

12

2

1

11

1

a

a

a

a

x

x

c

x

x

c

f



x

Zadanie programowania nieliniowego bez ogranicze

Ĕ

Zbiorem dopuszczalnym jest ca

áa przestrzeĔ

.

n

R

Metody analityczne

Minimalizacja funkcji bez ogranicze

Ĕ

Punkt

jest minimum lokalnym funkcji

ˆx

 

Q x

w przestrzeni

, je

Īeli istnieje

takie otwarte otoczenie

n

R

n

U

R



punktu

x

ˆ

,

Īe

 

x



x

x



ˆ

Q

Q

,

U

t





, przy

czym je

Īeli nierównoĞü jest ostra

 

 

x

x

ˆ

Q

!

Q

, to jest to

Ğcisáe minimum

lokalne.

Punkt

x

ˆ

jest minimum globalnym funkcji

 

Q x

w przestrzeni

, je

Īeli

, przy czym je

Īeli nierównoĞü jest ostra

, to jest to

Ğcisáe minimum globalne.

n

R

 



x

x

x

ˆ

Q

Q

,

n

t





 

 

x

x

ˆ

Q

Q



R

!

J.Stadnicki Optymalizacja

- 52 -

J.Stadnicki Optymalizacja

- 53 -

minimum
globalne

minimu
m

x

Q(x)

Za

áoĪenie:

okre

Ğlona w przestrzeni

, jest klasy C

 

Q x

n

R

2

(tzn. jest

ci

ągáa wraz z drugą

pochodn

ą).

Rozwijaj

ąc

w

szereg Taylora w punkcie

zachowuj

ąc dwa pierwsze skáadniki (aproksymacja

liniowa):

 

Q x

0

x

 

 

 



 

 

 

0

0

0

0

0

0

x

x

x

x

x

x

x

x

x

x

Q

Q

Q

,

Q

Q

Q

T

T

’





Ÿ



’



#

gdzie:

 

 

 

 

0

2

1

0

x

x

x

x

x

x

¸¸

¹

·

¨¨

©

§

w

w

w

w

w

w

’

n

T

x

Q

,

,

x

Q

,

x

Q

Q

!

jest gradientem

,

 

Q x

mo

Īna wykazaü, Īe

jest kierunkiem najszybszego wzrostu funkcji



0

x

Q

T

’



 

Q x

w punkcie

.

0

x

Je

Ğli

0

x

x

o

 

 

 

   

0

0

0

0

0

0

0

0

0

0

0

0

’

Ÿ





’

œ





o

o

x

t

x

x

x

x

x

x

x

x

x

x

x

x

x

x

Q

Q

Q

Q

T

T

lim

lim

(iloczyn skalarny

wektorów)

gdzie:



0

x

t



jest jednostkowym wektorem stycznym do warstwicy funkcji

w

punkcie

.

 

const

Q

x

0

x

Q(x)

Wniosek:

Gradient funkcji w punkcie

jest

ortogonalny do wektora stycznego
do warstwicy funkcji

0

x

const

Q

x

.

’Q(x

0

)

 

q x

0

t(x

0

)

x

1

x

2

t(x

0

)

q

x

q x

0

x-x

0

x

1

’Q(x

0

)

Warunki konieczne i wystarczaj

ące istnienia min (max) lokalnego w punkcie

:

0

x

(1)

 

 

 

 

0

2

1

0

w

w





w

w



w

w

n

x

Q

x

Q

x

Q

Q

grad

x

x

x

x

x

x

"

(2)

(maksimum)

(minimum)

0

0

0

0



!

x

x

x

x

j

i

2

j

i

2

x

x

Q

x

x

Q

w

w

w

w

w

w

dla



 



n

1,...,

j

n

1,...,

i

Warunki (2) mo

Īna zapisaü w formie symetrycznej kwadratowej macierzy drugich

pochodnych zwanej hesjanem funkcji

 

Q x

:

J.Stadnicki Optymalizacja

- 54 -

J.Stadnicki Optymalizacja

 

0

2

1

2

1

2

2

1

2

1

2

1

2

0

x

x

x

H

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

n

n

2

n

2

n

2

n

2

2

2

n

2

2

2

x

x

Q

x

x

Q

x

x

Q

x

x

Q

x

Q

x

x

Q

x

x

Q

x

x

Q

x

Q

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

w

"

#

#

#

#

"

"

Warunki (2) s

ą speánione, jeĞli hesjan

 

0

x

H

jest okre

Ğlony dodatnio (minimum) lub

ujemnie (maksimum), tzn.

jest wi

Ċksze (mniejsze) od zera.

> @

x

H

x

T



W przypadku gdy

=0 nale

Īy badaü wyĪsze pochodne.



0

x

H

Je

Īeli speánione są tylko warunki (1) punkt

jest tzw. punktem stacjonarnym

(maksimum lub minimum lub punktem siod

áowym).

0

x

Typy punktów stacjonarnych:

- 55 -

-7.5

-5

-2.5

0

2.5

5

7.5

-7.5

-5

-2.5

0

2.5

5

7.5

-60

-50

-40

-30

-20

-10

0

10

20

30

40

50

60

f(x,y)

x

y

-7.5

-5

-2.5

0

2.5

5

7.5

-7.5

-5

-2.5

0

2.5

5

7.5

0

5

10

15

20

25

30

35

40

45

50

f(x,y)

x

y

-7.5

-5

-2.5

0

2.5

5

7.5

-7.5

-5

-2.5

0

2.5

5

7.5

-50

-45

-40

-35

-30

-25

-20

-15

-10

-5

0

f(x,y)

x

y

maksimum

minimum

siod

áo

J.Stadnicki Optymalizacja

- 56 -

Zadanie programowania nieliniowego z ograniczeniami w postaci równo

Ğci

Rozwa

Īmy problem dwuwymiarowy





2



ĭ

R

:

Dana jest funkcja celu

klasy C



2

1

x

,

x

Q

x

g

1

1







2

, zbiór dopuszczalny okre

Ğlony jest przez

ograniczenie równo

Ğciowe

0

x

,

2

. Znajd

Ĩ minimum funkcji celu

2

1

x

,

x

Q

.









Z ograniczenia równo

Ğciowego moĪna wiĊc z niego wyliczyü np.

.

 

1

2

x

h

x











1

1

x

h

,

x

Q

x

,

x

Q

2

1

,



2

1

x

,

x

Q

ma minimum

 

 









0

1

1

œ

x

h

,

x

Q

grad

Q

grad

(warunek

konieczny)

(3.1)

 

0

0

1

2

2

1

w

w



w

w

Ÿ

dx

dx

x

Q

x

Q

Q

grad

Podobnie dla ograniczenia





0

x

,

x

g

2

1

1

(3.2)

0

1

2

2

1

1

1

w

w



w

w

dx

dx

x

g

x

g

Z uk

áadu równaĔ (3.1) (3.2) moĪna wyliczyü:

to

i

je

Ğli

zatem

0

0

2

1

2

2

1

1

1

1

2

2

1

1

2

z

w

w

z

w

w

w

w

w

w



w

w

w

w



x

g

x

Q

x

g

x

g

dx

dx

,

x

Q

x

Q

dx

dx

°

°
¯

°°

®

­

w

w



w

w

w

w



w

w

œ

w

w

w

w



w

w

w

w



œ

w

w

w

w



w

w

w

w



0

0

2

1

2

1

1

1

2

1

2

1

1

1

2

1

1

1

2

1

x

g

x

Q

x

g

x

Q

x

g

x

Q

x

g

x

Q

x

g

x

g

x

Q

x

Q

O

O

O

(3.3)

Równania (3.3) wyra

Īają warunki konieczne istnienia minimum funkcji:









)

x

,

x

(

g

x

,

x

Q

,

x

,

x

L

2

1

1

2

1

2

1

O

O



- funkcja Lagrange’a,

J.Stadnicki Optymalizacja

- 57 -

bo





0

2

1

1

w

w

x

,

x

g

L

O

,

O

- mno

Īnik Lagrange’a,

Wniosek:

Pierwotny dwuwymiarowy problem minimalizacji funkcji





2

1

x

,

x

Q

z ograniczeniem

równo

Ğciowym

zosta

á zastąpione trójwymiarowym problemem

minimalizacji zast

Ċpczej funkcji









0

x

,

x

g

2

1

1

O

,

x

,

x

L

2

1

bez ogranicze

Ĕ.

Uogólnienie post

Ċpowania na wiĊkszą liczbĊ zmiennych i ograniczeĔ prowadzi do

metody mno

Īników Lagrange’a.

Metoda mno

Īników Lagrange’a

Dana jest funkcja celu

klasy C

 

Q

x

1

. Zbiór dopuszczalny utworzony jest przez

ograniczenia równo

Ğciowe (funkcjonalne).

(4)

ĭ

 

^

`

n

j

;

n

m

;

m

,...,

j

;

g

:

R

ĭ

x

x





1

0

gdzie:

- liczba ogranicze

Ĕ funkcjonalnych,

m

- liczba zmiennych decyzyjnych.

n

Funkcje

s

ą równieĪ klasy C



x

j

g



1

.

Utwórzmy funkcj

Ċ:

(5)





 

 

 

 

x

x

x

x

Ȝ

x,

m

m

g

...

g

g

Q

L

O

O

O









2

2

1

1

gdzie:

- wektor mno

Īników Lagrange’a.

>

T

m

,...,

O

O

O

2

1

Ȝ

@



Warunkiem koniecznym istnienia ekstremum lokalnego funkcji

, przy

za

áoĪeniu Īe jest ona klasy C



Ȝ

x,

L

1

jest:

(6)









°

°
¯

°°

®

­

m

,...,

j

,

L

n

,...,

i

x

,

L

j

i

1

0

1

0

O

w

w

w

w

Ȝ

x

Ȝ

x

Rozwi

ązując ukáad (6)

równa

Ĕ znajdujemy punkty

i

m

n



x

Ȝ

, w których zeruje

si

Ċ gradient a zatem punkty w których mogą istnieü lokalne extrema funkcji celu.

J.Stadnicki Optymalizacja

- 58 -

Zadanie programowania nieliniowego z ograniczeniami w postaci nierówno

Ğci

Zbiory i funkcje wypuk

áe

Zbiór

ĭ

jest wypuk

áy, jeĪeli dla kaĪdej pary punktów

odcinek

áączący te punkty naleĪy do tego zbioru.

n

R



ĭ



2

1

x

,

x

zbiór nie

k

á

x

2

x

2

x

1

zbiór wypuk

áy

x

2

x

1

x

1

f

funkcja wkl

Ċsáa

x

2

x

1

x

1

funkcja

ĞciĞle wklĊsáa

x

2

x

1

f

x

1

f

funkcja wypuk

áa

x

2

x

1

x

1

funkcja

ĞciĞle wypukáa

x

2

x

1

f

x

1

x

2

x

1

Funkcja

okre

Ğlona na zbiorze wypukáym

jest wypuk

áa jeĪeli

nadgrafik nad wykresem funkcji jest zbiorem wypuk

áym.

R

R

o

:

f

n

ĭ

W

áasnoĞci funkcji wypukáej:

1° dla dowolnych

 

 





1

2

1

1

2

2

1

x

x

x

x

x

ĭ

x

x



w

w

t





f

f

f

,

,

2° hesjan

dla wszystkich

,

 





>

@

0

t

x

f

H

x

3° w zbiorze

ĭ

funkcja ma jedno ekstremum

Ÿ ekstremum lokalne jest ekstremum

globalnym.

Wniosek:

Ka

Īda funkcja liniowa jest wypukáa (bo druga pochodna funkcji liniowej jest równa

zero).

Mo

Īna wykazaü, Īe ukáad ograniczeĔ w postaci równoĞci i nierównoĞci:

 
 

m

,...,

m

,

m

j

,

g

m

,...,

,

j

,

g

j

j

2

1

0

2

1

0

1

1

1





d

x

x

okre

Ğla zbiór wypukáy wtedy i tylko wtedy gdy:

funkcje

s

ą funkcjami wypukáymi, a pozostaáe funkcje

 

1

j

1,2,...,m

j

g

dla

x

2,...,m

1,m

m

j

1

1



 

g

j



dla

x

s

ą funkcjami liniowymi.

Problem, w którym funkcja celu jest wypuk

áa i zbiór dopuszczalny jest wypukáy,

nazywamy problemem programowania wypuk

áego.

Rozwa

Īmy problem dwuwymiarowy





2



ĭ

R

:

Dana jest funkcja celu

klasy C



2

1

x

,

x

Q

g

j







1

, zbiór dopuszczalny okre

Ğlony jest przez

ograniczenia nierówno

Ğciowe

3

2

1 ,

,

j

0,

x

,

x

2

1

d

. Znajd

Ĩ minimum funkcji

celu

Q

.





2

1

x

,

x

J.Stadnicki Optymalizacja

- 59 -

J.Stadnicki Optymalizacja

- 60 -

Utwórzmy funkcj

Ċ Lagrange’a:





 

 

 

 

 

 

x

x

x

x

x

x

Ȝ

x,

¦









3

1

3

3

2

2

1

1

j

j

j

g

Q

g

g

g

Q

L

O

O

O

O

xˆ

)

 

0

1

x

g

 

0

2

x

g

 

0

3

x

g

2

1

x

xˆ

)

 

0

1

x

g

 

0

2

x

g

 

0

3

x

g

2

x

1

x

xˆ

)

 

0

1

x

g

 

0

2

x

g

 

0

3

x

g

2

x

1

x

c)

b)

a)

 

const

ˆ

Q

x

 

const

ˆ

Q

x

 

const

ˆ

Q

x

x

a)

ma minimum w punkcie

le

Īącym wewnątrz

ĭ

,

 

Q x

xˆ

 

0

0

w

w

œ

x

x

x

x

ˆ

j

ˆ

x

Q

Q

grad

oraz

 

3

2

1

0

,

,

j

,

ˆ

g

j



x

(6.1)

3

2

1

0

0

3

1

,

,

j

,

x

g

x

Q

x

L

j

ˆ

j

j

j

j

ˆ

j

ˆ

j

w

w



w

w

w

w

¦

O

O

je

Ğli

x

x

x

x

x

x

Warunek

jest aktywny w punkcie

, je

Īeli

 

0

d

xˆ

g

j

xˆ

 

0

xˆ

g

j

.

Warunek

jest nieaktywny w punkcie

, je

Īeli

 

0

d

xˆ

g

j

xˆ

 

0



xˆ

g

j

.

b)

 

 

 

,

ˆ

g

,

ˆ

g

,

ˆ

g

0

0

0

3

2

1





x

x

x

Zatem w dostatecznie ma

áym otoczeniu

zadanie jest równowa

Īne problemowi

optymalizacji z ograniczeniem równo

Ğciowym.

xˆ

Z równa

Ĕ (3.3)

0

3

1

1

1

1

1

w

w



w

w

w

w

œ

w

w



w

w

¦

x

x

x

x

x

x

x

x

x

x

ˆ

j

j

j

j

ˆ

j

ˆ

j

ˆ

ˆ

x

g

x

Q

x

L

x

g

x

Q

O

O

0

0

3

2

1

!

O

O

O

,

je

Ğli

c)

 

 

 

,

ˆ

g

,

ˆ

g

,

ˆ

g

0

0

0

3

2

1



x

x

x

Zatem w dostatecznie ma

áym otoczeniu

zadanie jest równowa

Īne problemowi

optymalizacji z dwoma ograniczeniami równo

Ğciowymi.

xˆ

J.Stadnicki Optymalizacja

- 61 -

0

3

1

2

2

2

1

1

1

1

w

w



w

w

w

w

œ

w

w



w

w



w

w

¦

x

x

x

x

x

x

x

x

x

x

x

x

ˆ

j

j

j

j

ˆ

j

ˆ

j

ˆ

ˆ

ˆ

x

g

x

Q

x

L

x

g

x

g

x

Q

O

O

O

0

0

0

3

2

1

!

!

O

O

O

,

,

je

Ğli

Podsumujmy przypadki a), b), c):

Zawsze dla

0

3

2

1

t

j

,

,

j

O

, ponadto:

1° je

Īeli

(warunek nieaktywny) to odpowiedni mno

Īnik Lagrange’a jest

równy zero

 

0



xˆ

g

j

j

0

O

,

2° je

Īeli

(warunek aktywny) to odpowiedni mno

Īnik Lagrange’a jest

dodatni

 

0

xˆ

g

j

0

!

j

O

,

Punkt

jest rozwi

ązaniem zadania, gdy speánia wszystkie ograniczenia:

xˆ

 

0

0

d

¸

¸
¹

·

¨

¨
©

§

w

w

œ

d

x

x

x

ˆ

j

j

L

ˆ

g

O

, (6.2)

warunki 1° i 2° oznaczaj

ą:

 

0

0

¸

¸
¹

·

¨

¨
©

§

w

w

œ

x

x

x

ˆ

j

j

j

j

L

ˆ

g

O

O

O

(6.3)

Bior

ąc po uwagĊ warunki (6) metody mnoĪników Lagrange’a do zadania z

ograniczeniami w postaci równo

Ğci oraz warunki (6.2) i (6.3), warunkami

koniecznymi istnienia rozwi

ązania zadania optymalizacji nieliniowej z

ograniczeniami w postaci nierówno

Ğci są:

J.Stadnicki Optymalizacja

- 62 -

(7)

ˆ

ˆ

ˆ

0

1,...,

0

0

1,...,

0

i

j

j

j

j

L

i

n

x

L

L

j

m

O

O

O

O

­§

·

w

°¨

¸

w

©

¹

°

°

½

§

·

w

°

d

°

¨

¸

°¨

¸

w

°

©

¹

°

°

®

§

·

°

w

°

°

¨

¸

¾

°

¨

¸

w

°

©

¹

°

°

°

t

°

°

°

°

°¿

¯

x x

x x

x x

Warunki (7) nazywane s

ą warunkami Khuna-Tuckera.

KOMPUTEROWE METODY ROZWI

ĄZYWANIA ZADAē PROGRAMOWANIA

NIELINIOWEGO

Rz

ąd algorytmu optymalizacji rozumiemy jako stopieĔ pochodnych

minimalizowanej funkcji celu wykorzystywany w algorytmie.

x Algorytmy (metody) rzĊdu zerowego (bezgradientowe) – korzystają tylko z

warto

Ğci funkcji celu.

x Algorytmy (metody) rzĊdu pierwszego (gradientowe) – korzystają z

pochodnych rz

Ċdu pierwszego funkcji celu.

x Algorytmy (metody) rzĊdu drugiego – korzystają z pochodnych rzĊdu drugiego

(hesjanu) funkcji celu.

Kryterium zako

Ĕczenia obliczeĔ jest najczĊĞciej badanie zmian wektora oraz

funkcji celu

. Je

Īeli zmiany te są mniejsze od przyjĊtej dokáadnoĞci

x

 

x

Q

İ

, to

ko

Ĕczymy obliczenia.

Algorytm optymalizacji jest zbie

Īny, jeĪeli istnieje i naleĪy do zbioru

dopuszczalnego granica kolejnych punktów

otrzymanych w jego wyniku:

i

x

x

x

ˆ

i

i

lim

f

o

,

przy czym je

Īeli

i

jest sko

Ĕczone, to mówimy o skoĔczonej zbieĪnoĞci

algorytmu.

Je

Īeli algorytm jest zbieĪny, to liczbĊ

, dla której istnieje sko

Ĕczona granica

1

t

q

q

q

i

i

i

r

ˆ

ˆ

lim







f

o

x

x

x

x

1

, gdzie:

– jest wspó

áczynnikiem zbieĪnoĞci,

q

r

nazywamy rz

Ċdem zbieĪnoĞci algorytmu.

Je

Īeli

1

2

to mówimy o zbie

ĪnoĞci liniowej,

to mówimy o zbie

ĪnoĞci kwadratowej,

q

­

®

¯

Zadanie programowania nieliniowego bez ogranicze

Ĕ

Znajd

Ĩ minimum

Q

dla

 

min

o

x

n

R

x



, przy czym

 

x

Q

jest klasy C

1

.

J.Stadnicki Optymalizacja

- 63 -

J.Stadnicki Optymalizacja

- 64 -

Metody rz

Ċdu zerowego (bezgradientowe) funkcji jednej zmiennej

Metoda z

áotego podziaáu

Dla

1

2

1

2

1

a

a

a

a

a

a

!

, zatem

a

a

2

a

1





,

,

,

a

a

618

0

1

5

5

0

1

#







,

,

,

a

a

382

0

5

3

5

0

2

#



Krok wst

Ċpny:

x Wyznacz przedziaá, w którym lokalne minimum musi istnieü.

x Oblicz wartoĞci funkcji

Q

dla kolejnych

o sta

áym odstĊpie

.

 

x

i

x

x

'

Je

Īeli dla kolejnych

zachodzi

1

1





i

i

i

x

,

x

,

x





 





 

i

i

i

i

x

Q

x

Q

oraz

x

Q

x

Q

!

!





1

1

 

x

Q

,

to w przedziale

musi znajdowa

ü siĊ minimum funkcji

.





1

1





i

x

,

i

x

x Oznaczmy przedziaá

jako





1

1





i

i

x

,

x





p

l

x

,

x

.

Q(x

2

k

)> Q(x

1

k

)

Q(x

1

k

)

Q(x

2

k

)

x

2

k

=

pkt. prawy

x

1

k

=

pkt. lewy

x

p

=x

p

k

x

l

=x

l

k

x

Q(x)

Kolejne kroki algorytmu:

1° Przyjmij

.

p

k

p

l

k

l

x

x

x

x

k

1

2° Je

Īeli

H





k

l

k

p

x

x

to zako

Ĕcz algorytm.

W przeciwnym przypadku wyznacz punkty wewn

Ċtrzne:

pkt. lewy:





k

l

k

p

x

x

,



382

0

k

l

k

x

x



1

, pkt. prawy:





k

l

k

p

k

l

k

x

x

,

x

x





618

0

2

i oblicz warto

Ğci funkcji celu w tych punktach.

3° Je

Īeli

   

œ

!

k

k

x

Q

x

2

1

Q

Q

(pkt-u lewego) >

Q

(pkt-u prawego) odrzu

ü przedziaá



k

1

k

l

x

,

x

(tzn. lew

ą czĊĞü

k

p

k

l

x

,

x

), podstawiaj

ąc:

l

x

x

1

k

k

pkt. lewy,

1



k

k

i wró

ü do punktu 2°.

W przeciwnym przypadku odrzu

ü przedziaá



k

p

k

x

,

x

2

(tzn. praw

ą czĊĞü

k

p

k

l

x

,

x

), podstawiaj

ąc:

k

k

p

x

x

2

pkt. prawy,

1



k

k

i wró

ü do punktu

2°.

Metoda Powella (interpolacji kwadratowej)

Przez trzy kolejne punkty

mo

Īna poprowadziü parabolĊ o równaniu:

3

2

1

x

,

x

,

x

 

  











  











  











2

3

1

3

2

1

3

3

2

1

2

3

1

2

3

1

2

1

3

2

1

x

x

x

x

x

x

x

x

x

Q

x

x

x

x

x

x

x

x

x

Q

x

x

x

x

x

x

x

x

x

Q

x

Q

~





























posiadaj

ącej ekstremum w punkcie





0

m

x

x

dx

Q

~

d

:

 





 





 





 



 



 



>

@

2

1

3

1

3

2

3

2

1

2

2

2

1

3

2

1

2

3

2

2

3

2

2

1

2

x

x

x

Q

x

x

x

Q

x

x

x

Q

x

x

x

Q

x

x

x

Q

x

x

x

Q

x

m





















Kolejne kroki algorytmu:

1° Podstaw

0

k

, przyjmij punkt startowy

i krok

k

x

k

x

'

,

2° W punkcie

oblicz warto

Ğü

k

k

k

x

x

x

'



1

 

1



k

x

Q

.

J.Stadnicki Optymalizacja

- 65 -

3° Je

Īeli

   

k

k

x

Q

x

d

1

Q

to podstaw

k

k

x

x

'

'



2

1

i powró

ü do kroku 2°

przyjmuj

ąc

1



k

k

.

W przeciwnym przypadku

oblicz





k

k

x

.

x

'





5

0

1

Q

.

Q(x)

Q(x)

~

Otrzymamy trzy

równoodleg

áe punkty

przez które

mo

Īemy poprowadziü

parabol

Ċ

2

1





i

i

i

x

,

x

,

x

Q

 

x

ˆ

.

Q(x)

i

i+2

x

min

i+1

x

m

ǻx

k

x

k

x

k+1

x

k+2

2

ǻx

k

x

J.Stadnicki Optymalizacja

- 66 -

Uwaga:

Je

Īeli w pierwszej iteracji w kroku 3°

   

k

k

x

Q

x

Q

!

1

to odwracamy kierunek

poszukiwa

Ĕ.

4° Obliczamy warto

Ğü

przyjmuj

ąc:

m

x

,

x

x

,

x

x

,

x

x

i

i

i

2

3

1

2

1





x

x

x

x

x

'





1

2

2

3

5° Je

Īeli

H





1

i

m

x

x

1



i

x

m

x

, to obliczenia ko

Ĕczymy przyjmując

.

W przeciwnym przypadku powtarzamy algorytm od punktu 2° zmniejszaj

ąc krok z

punktu

lub

.

m

min

x

x

#

Podsumowanie:

Obie metody s

ą proste i efektywne, moĪna je stosowaü gdy nie istnieje pochodna

lub trudno j

ą wyznaczyü.

Metody rz

Ċdu pierwszego (gradientowe) funkcji jednej zmiennej

Korzystaj

ą z pierwszej pochodnej funkcji celu i bazują na dwóch koncepcjach:

1. Interpolacji funkcji celu wielomianami wy

Īszych stopni.

Np. interpolacja sze

Ğcienna Davidona – w przedziale, w którym znajduje siĊ

minimum funkcji celu na podstawie znajomo

Ğci wartoĞci funkcji celu oraz jej

pochodnych w dwóch punktach ograniczaj

ących przedziaá znajdowana jest

parabola sze

Ğcienna. Minimum paraboli podobnie jak w metodzie Powella w

kolejnych iteracjach zd

ąĪa do minimum funkcji celu.

2. Szukaniu miejsca zerowego pochodnej.

J.Stadnicki Optymalizacja

- 67 -

Metoda siecznych:

Dany jest przedzia

á

p

l

x

,

x

, w którym funkcja celu

 

x

Q

ma minimum.

Q’(x

l

)

Q’(x

p

)

Į

P

L

x

m

2

=x

l

3

x

m

1

=x

l

2

x

m

0

=x

l

1

x

p

x

l

x

Q’(x)

Kolejne kroki algorytmu:

1° Przyjmij

0

k

i oblicz wspó

árzĊdną punktu przeciĊcia odcinka LP z osią

x

.

 

 

 

 

 

 

 

k

p

k

l

k

l

k

p

k

p

k

l

k

p

k

p

k

m

k

l

k

l

x

'

Q

x

'

Q

x

x

'

Q

x

x

'

Q

tg

x

'

Q

x

x

x

x

'

Q

tg











D

D

k

p

k

p

x

x

'

Q

2° Oblicz

 

k

m

x

'

Q

i sprawd

Ĩ czy

 

H



k

m

x

'

Q

. Je

Ğli tak to zakoĔcz obliczenia.

3° Je

Īeli

   

0

!

k

p

k

m

x

'

Q

x

'

Q

to podstaw

 

 

k

m

k

p

k

m

k

p

x

'

Q

x

'

Q

x

x





1

1

.

W przeciwnym przypadku

 

 

k

m

k

l

x

'

Q

x

'

Q

1

k

m

k

l

x

x

1

.

Podstaw

1



k

k

i powró

ü do punktu 1°.

J.Stadnicki Optymalizacja

- 68 -

Metody rz

Ċdu drugiego funkcji jednej zmiennej

Metoda Newtona

Wymaga obliczenia drugiej pochodnej funkcji celu

 

x

Q

, która dodatkowo musi by

ü

ci

ągáa(

klasy C

 

x

Q

2

).

Kolejne kroki algorytmu:

1° Podstaw

0

k

.

2° W otoczeniu punktu startowego

rozwi

Ĕ funkcjĊ celu

k

x

 

x

Q

w szereg Taylora

ograniczaj

ąc siĊ do skáadnika z drugą pochodną:

 

 

 



 



2

5

k

k

k

k

k

x

x

x

"

Q

,

x

x

x

'

Q

x

Q

x

Q







#

0



3° Przyrównuj

ąc pierwszą pochodną otrzymanego wyraĪenia do zera, wyznacz

punkt, w którym ma ono minimum (punkt startowy do nast

Ċ ne iteracji):

p

j

 

 

 



 

 

k

k

k

k

m

k

k

m

k

k

x

"

Q

x

'

Q

x

x

x

x

x

"

Q

x

'

Q

x

'

Q



Ÿ





#

0

Uwaga:

Zatem algorytm jest zbie

Īny tylko wtedy, gdy

 

0

!

k

x

"

Q

4° Je

Īeli

H





k

k

m

x

x

to zako

Ĕcz obliczenia.

W przeciwnym przypadku podstaw

i powró

ü do punktu 2°.

1

1





k

k

x

x

k

m

k

x

m

2

x

m

1

x

m

0

x

0

x

Q(x)

Metody rz

Ċdu zerowego (bezgradientowe) minimalizacji funkcji wielu

zmiennych

Metody poszukiwa

Ĕ prostych:

Charakteryzuj

ą siĊ prostotą algorytmu, brakiem wraĪliwoĞci na ksztaát

minimalizowanej funkcji lecz s

ą mniej efektywne od omawianych dalej.

Metoda Gaussa-Seidela:

Funkcja celu

Q

jest minimalizowana wzd

áuĪ kolejnych kierunków bazy

ortogonalnych (wzajemnie prostopad

áych) wersorów

wspó

árzĊdnych

kartezja

Ĕskich. Wersory w trakcie obliczeĔ pozostają niezmienne.

 

x

n

,

,

,

ȟ

ȟ

ȟ

!

2

1

Q(x)

x

k

O

*

[

i

[

2

[

1

Q(x)=const

x

2

1

x

2

1

=x

1

x

1

1

x

0

x

2

x

1

Kolejne kroki algorytmu:

1° Przyjmij punkt startowy

0

x

, podstaw

.

0

1

0

x

x

k

i

i

k

2° W kierunku wersora

znajd

Ĩ odlegáoĞü

i

ȟ

*

O

od punktu

w jakiej funkcja celu

ma minimum.

Zadanie polega wi

Ċc na minimalizacji funkcji jednej zmiennej:

k

i

x

 

x

Q





 

min

Q

i



O

O

ȟ

i

Q

k

i

x

o

i mo

Īe byü rozwiązane jedną z metod omówionych poprzednio po przyjĊciu

warto

Ğci

H

oznaczaj

ącej wymaganą dokáadnoĞü rozwiązania zadania dla

kierunku

i

.

J.Stadnicki Optymalizacja

- 69 -

J.Stadnicki Optymalizacja

- 70 -

3° Przyjmij

i

k

wyznacz punkt

le

Īący w odlegáoĞci

k

i

x

*

O

od

w kierunku

i

.

Podstaw

i

.

Je

Īeli

i

powró

ü do punktu 2°.

1



k

i

x

1



i

n



4° Przyjmij nowy punkt startowy

oraz podstaw

k

i

k

x

x

0

0

i

.

Je

Īeli

1

0

0

k

k

0

H





!

x

x

to powró

ü do punktu 2°.

W przeciwnym przypadku zako

Ĕcz obliczenia.

Uwaga:

Metoda ma

áo efektywna, gdy warstwice funkcji celu są dáugimi wąskimi krzywymi.

Metoda losowego przeszukiwania

Losujemy punkt startowy

, a nast

Ċpnie tworzymy taki ciąg punktów

0

x

^ `

k

x

takich,

Īe:

 

 

 

 

0

1

ˆ

k

Q

Q

Q

Q

t

t

t

t

t

x

x

x

!

!

x

, przy czym

k

k

k

ǻ

x

x



1

,

gdzie

k

ǻ

– jest pewnym na ogó

á losowym przyrostem zmiennej decyzyjnej.

jednostkowy wektor losowy

(promie

Ĕ sfery)

[

1

0

x

1

x

2

x

3

x

3

x

2

r

x

1

Q(x)=const

x

0

x

2

x

1

Kolejne kroki algorytmu:

1° Wylosuj punkt startowy

0

x

, ustal promie

Ĕ sfery

r

oraz liczb

Ċ losowaĔ

N

,

podstaw

0

k

.

2° Z punktu

k

x

wylosuj

N

punktów na powierzchni sfery o promieniu

r

.

J.Stadnicki Optymalizacja

- 71 -

3° Je

Īeli

  



1





k

k

Q x

x

Q

, to spo

Ğród wylosowanych punktów

wybierz taki

,

w którym warto

Ğü funkcji celu jest najmniejsza

k

i

x

k

i

ˆx

 

 

k

k

i

i

k

x

ˆ

1,...

Q

Q

dla i



x

x

ˆx

, ,

n

,

zast

ąp nim punkt

i powró

ü do punktu 2°.

W przeciwnym przypadku zako

Ĕcz obliczenia i przyjmij

k

i

k

ˆx

x

. W odleg

áoĞci

mniejszej od

r

od

k

x

nie ma punktu, w którym funkcja celu osi

ągaáaby wartoĞü

mniejsz

ą od dotychczas uzyskanej.

Uwaga:

Metoda ma

áo efektywna. Przebieg obliczeĔ bezpoĞrednio zaleĪy od przyjĊtych

r

(promienia sfery) oraz

N

(liczby losowa

Ĕ).

Metody kierunków poprawy:

Kierunkami poprawy funkcji

Q

w punkcie

 

x

k

x

nazywamy wektory

, dla

których istnieje

n

R



ȟ

0

0

!

O

takie,

Īe dla kaĪdego



0

0



O

O

,



, zachodzi





 

k

k

Q

Q

O





x

ȟ

x

.

Kierunki (wektory)

i

i

ȟ

j

ȟ

nazywamy sprz

ĊĪonymi wzglĊdem kwadratowej

dodatnio okre

Ğlonej macierzy

>

, je

Īeli

@

H

> @

0

iT

j

dla i

j

z

H

ȟ

ȟ

.

Wniosek:

Je

Īeli

> @ > @

H

I

(

I –

macierz jednostkowa) to otrzymamy kierunki ortogonalne.

Metoda kierunków sprz

ĊĪonych Powella:

Tw.

Je

Īeli startując z punktu początkowego

0

x

w kierunku

minimum funkcji

kwadratowej

Q

osi

ągamy w punkcie

ȟ

 

x

a

x

, a startuj

ąc z innego punktu

0

1

x

x

z

w

tym samym kierunku

minimum osi

ągamy w punkcie

ȟ

b

x

, to przy

   

a

Q x



b

x

Q

kierunek





b

x



a

x

jest sprz

ĊĪony wzglĊdem hesjanu

> @

H

.

Dla problemu dwuwymiarowego,
w którym warstwice funkcji celu

s

ą koáowe

> @ >

I

H

@

, a kierunki

sprz

ĊĪone są ortogonalne.

x

1

ȟ

x

2

Minimum (0,0) osi

ągamy w

drugim kroku algorytmu!

x

0

ȟ

x

a

- x

b

x

1

x

b

x

a

x

0

ȟ

2

0

x

^

x

3

0

=x

1

x

3

1

=x

2

ȟ

2

2

ȟ

2

1

x

2

1

x

1

1

ȟ

1

1

ȟ

2

1

ȟ

2

0

ȟ

1

0

x

3

0

-x

1

0

ȟ

2

0

ȟ

1

0

Q(x)=const

x

3

0

x

2

0

x

1

0

x

2

x

1

Kolejne kroki algorytmu:

1° Wybierz punkt startowy

0

x

, podstaw

0

k

oraz przyjmij

n

liniowo niezale

Īnych

wersorów

(najcz

ĊĞciej są to wersory kartezjaĔskiego ukáadu wspóárzĊdnych).

i

k

ȟ

2° Wykonaj minimalizacj

Ċ funkcji





k

k

i

Q

O



x

ȟ

dla kolejnych kierunków bazy

gdzie

i=n,1,2,...,n-1

, przyjmuj

ąc minimum kolejnej minimalizacji jako

po

Ğredni punkt startowy nastĊpnej.

i

k

ȟ

J.Stadnicki Optymalizacja

- 72 -

J.Stadnicki Optymalizacja

- 73 -

3° Ostatni z otrzymanych punktów

przyjmij jako nowy punkt startowy

k

n 1



x

1



k

x

.

Je

Īeli

H







k

k

x

x

1

to zako

Ĕcz obliczenia.

4° Wyznacz kierunek sprz

ĊĪony

1

1

1

1

1

k

k

k

n

n

k

n











x

x

ȟ

x

x

k

i wprowad

Ĩ go do bazy, tzn.

zamie

Ĕ pierwszy kierunek bazy kierunkiem sprzĊĪonym

.

Wyznacz kolejny punkt

na przeci

Ċciu kierunków

i

.

Podstaw

1

1

k

k

i

n





ȟ

ȟ

k

n

1

k

n



ȟ

k

n 1



x

ȟ

1



k

k

i wró

ü do punktu 2°.

Metody rz

Ċdu pierwszego (gradientowe) minimalizacji funkcji wielu zmiennych

Metoda najszybszego spadku:

Q(x)=const

x

2

ȟ

1

=-

’

Q(x

0

)

Kierunek przeciwny do
gradientu

jest

kierunkiem poszukiwa

Ĕ.



k

k

Q

’

ȟ

x

x

1



x

3

x

^

x

2

ȟ

2

=-

’

Q(x

2

)

x

0

x

1

ȟ

0

=-

’

Q(x

0

)

Kolejne kroki algorytmu:

1° Wybierz punkt startowy

0

x

, podstaw

0

k

2° Oblicz gradient

 

k

Q x

’

i przyjmij kierunek poszukiwa

Ĕ

 

k

k

Q

’

ȟ

x

.

3° Minimalizuj funkcj

Ċ





k

k

O



x

ȟ

Q

w kierunku

wyznaczaj

ąc punkt

k

ȟ

1



k

x

.

4° Je

Ğli kryterium zbieĪnoĞci

 





H

d

’

˜

’

1

k

k

Q

Q

x

x

1

jest spe

ánione to zakoĔcz

obliczenia.
W przeciwnym przypadku podstaw



k

k

i wró

ü do punktu 2°.

Metoda gradientu sprz

ĊĪonego:

E

ȟ

0

-

’

Q(x

1

)

x

^

x

2

ȟ

1

x

1

ȟ

0

=-

’

Q(x

0

)

Q(x)=const

x

0

x

2

x

1

Kolejne kroki algorytmu:

1° Wybierz punkt startowy

0

x

, podstaw

0

k

2° Oblicz gradient

 

k

Q x

’

i przyjmij kierunek poszukiwa

Ĕ

.

 

k

k

Q

’

ȟ

x

3° Minimalizuj funkcj

Ċ





k

k

O



x

ȟ

Q

w kierunku

wyznaczaj

ąc punkt

k

ȟ

1



k

x

.

Okre

Ğl nowy (sprzĊĪony) kierunek poszukiwaĔ:

, gdzie:





1

k

k

E





ȟ

1

1

k

k

Q





’

ȟ

x









 

 

1

1

1

2

k

k

k

Q

Q

Q

E







T

k

k

Q

ª

º

 ’

’

’

¬

¼

’

x

x

x

x

4° Je

Ğli kryterium zbieĪnoĞci





H



’

1

k

Q x

jest spe

ánione to zakoĔcz obliczenia.

W przeciwnym przypadku podstaw

1



k

k

i wró

ü do punktu 2°.

J.Stadnicki Optymalizacja

- 74 -

Metody rz

Ċdu drugiego

Metoda Newtona:

Jest uogólnieniem poznanej metody minimalizacji funkcji jednej zmiennej.

Rozwi

Ĕ funkcjĊ

w szereg Taylora w otoczeniu punktu

ograniczaj

ąc siĊ do

dwóch pierwszych wyrazów:

 

x

Q

 

k

x

 

  







 



1

2

k

T

k

k

k

k

Q

Q

Q

T

k

ª

º

’











¬

¼

x

x

x

x

x

x

x

x

x



H

x

Poniewa

Ī w metodzie Newtona stosujemy interpolacjĊ kwadratową, problem

minimalizacji funkcji

 

x

Q

w kierunku

mo

Īna rozwiązaü w sposób Ğcisáy.

k

ȟ

Podstawiaj

ąc:

, otrzymamy:

k

O



x

x

ȟ

k





 

 

 

 

*

*

0

k

k

T

k

k

T

k

k

kT

k

k

kT

k

k

dQ

Q

Q

d

O

O

O

O



’

ª

º

’



Ÿ



¬

¼

ª

º

¬

¼

x

ȟ

x

ȟ

x

ȟ

ȟ

H x

ȟ

ȟ

H x

ȟ

Mo

Īna w ten sposób ustaliü kolejne punkty wyznaczane przez algorytm:

1

k

k

k

O





x

x

ȟ

*

k

podstawiaj

ąc

*

O

otrzymamy

 

 

1

k

k

k

k

Q



’



ª

º

¬

¼

x

x

x

H x

Zadanie programowania nieliniowego z ograniczeniami

Znajd

Ĩ minimum

Q

dla

 

min

o

x



x

ĭ

, przy czym

jest niepustym zbiorem

dopuszczalnym zdefiniowanym za pomoc

ą ukáadu ograniczeĔ nierównoĞciowych

i (lub) równo

Ğciowych

ĭ

 

0

d

x

j

g

 

0

x

l

h

.

J.Stadnicki Optymalizacja

- 75 -

J.Stadnicki Optymalizacja

- 76 -

Algorytmy (metody) podstawowe

Nie korzystaj

ą z informacji wynikających z przebiegu obliczeĔ.

Zalety:
x prostota algorytmu,
x niewraĪliwoĞü algorytmu na ksztaát

funkcji celu i spójno

Ğü obszaru

dopuszczalnego,

x efektywnoĞü przy wystĊpowaniu

ekstremów lokalnych funkcji celu.

Wady:

x

du

Īy nakáad pracy , szybko

rosn

ący w miarĊ zwiĊkszania siĊ

wymiaru zadania (liczby
zmiennych decyzyjnych) oraz
liczno

Ğci zbioru dopuszczalnego.

Metoda systematycznego przeszukiwania:

Kolejne kroki algorytmu:

x

2

x

2

g

)

n

2

'

x

2

)

x

2

d

x

1

x

1

g

x

1

d

n

1

'

x

1

1° Szacujemy zakres zmian poszczególnych zmiennych decyzyjnych:

dla

Dzielimy go na

równych cz

ĊĞci, otrzymując siatkĊ o

oczkach, w których znajduj

ą siĊ punkty

.

Przyjmujemy

g

i

i

d

i

x

x

x

d

d



–



n

i

i

n

N

1

1

n

,

,

i

!

1

i

n

1



N

,

,

k

,

k

!

1

x

k

.

2° Obliczamy warto

Ğci

m

,

,

j

!

1

ogranicze

Ĕ

 

k

j

g x

w oczkach siatki.

J.Stadnicki Optymalizacja

- 75 -

3° Sprawdzamy czy ograniczenia s

ą speánione lub czy

N

k

d

. Dla

N

k

ko

Ĕczymy obliczenia.

Je

Īeli nie podstawiamy

1



k

k

i wracamy do punktu 2°.

4° Obliczamy

 

k

x

k

t

k

i

Q

.

Je

Īeli

i wracamy do punktu 2°.

 

 

 

min

min

min

1

,

1

ˆ

1

,

k

k

k

o Q

Q

k

k

Q

Q

to Q

Q

k

k

­



°

®

z



°¯

x

x

x

x

x ,

1

k



Uwaga:

Odleg

áoĞci miĊdzy oczkami siatki muszą byü mniejsze od wymaganej dokáadnoĞci

oblicze

Ĕ

H

.

Metoda poszukiwa

Ĕ losowych (Monte Carlo):

x Dla skrócenia czasu obliczeĔ nie przeszukuje siĊ punktów

k

x

le

Īących w

oczkach siatki lecz w sposób losowy generuje si

Ċ ciągi liczb

dla

i

, okre

Ğlające wspóárzĊdne punktów

g

i

k

i

d

i

x

x

d

d

x

n

,

,

!

1

k

x

.

x Liczba losowaĔ zaleĪy od przyjĊtego prawdopodobieĔstwa

K

i za

áoĪonej

dok

áadnoĞci

H

otrzymania rozwi

ązania.

x PrawdopodobieĔstwo

K

wylosowania w

N

próbach z dok

áadnoĞcią

H

punktu

ze zbioru

wynosi:

ĭ





N

H





1

1

K

.

x Zatem aby wylosowaü z prawdopodobieĔstwem

K

i dok

áadnoĞcią

H

punkt ze

zbioru

potrzeba minimum

ĭ

N

losowa

Ĕ.

















log 1

log 1

log 1

log 1

N

N

K

K

H

H





d



Ÿ

t



K

H

0,9

0,95

0,99

0,5

4

5

7

0,2

11

14

21

0,1

22

29

44

0,01

230

299

459

J.Stadnicki Optymalizacja

- 76 -

Algorytmy (metody) z pami

Ċcią

A. Metody po

Ğrednie:

1. zast

Ċpują zadanie programowania nieliniowego z ograniczeniami zadaniem

programowania nieliniowego bez ogranicze

Ĕ – metody funkcji kary,

2. zast

Ċpują zadanie programowania nieliniowego z ograniczeniami zadaniem

programowania liniowego – linearyzacja.

B. Metody bezpo

Ğrednie – zakáadają, Īe minimum leĪy na brzegu obszaru

dopuszczalnego i poszukuj

ą rozwiązania wzdáuĪ tego brzegu.

Metoda funkcji kary:

Rozwa

Īmy problem jednowymiarowy:

Zajd

Ĩ minimum:

Q

 

min

x

x

o

przy spe

ánieniu ograniczeĔ:

 

 

1

2

1

x

x

g

x

g

0

2

0

d



d

 x

Za przekroczenie obszaru dopuszczalnego na

áoĪymy na funkcjĊ celu karĊ liczbową

tzn. utworzymy zast

Ċpczą funkcjĊ celu

 

 

 

x

x

x

P

Q

Q

*



,

gdzie:

,

w praktyce

 

0

dla

P

dla



­

®

f

¯

x

ĭ

x

x

ĭ



 

0 dla

P

L dla



­

®



¯

x

ĭ

x

x

ĭ

,

(idealna funkcja kary)

L

– du

Īa liczba dodatnia.

’
L

’
L

Q(x)

)

1

Q

*

(x)

x

2

Q(x)

)

Q(x)

x

1

2

Uwaga:

Otrzymana zast

Ċpcza funkcja celu

 

x

*

Q

jest nieci

ągáa, zatem koncepcja nie

nadaje si

Ċ do praktyki numerycznej.

J.Stadnicki Optymalizacja

- 77 -

Metoda zewn

Ċtrznej funkcji kary:

Wprowad

Ĩmy funkcjĊ kary postaci:

 

 

>

@

^

`

¦

m

j

j

k

k

z

;

g

min

r

P

1

2

0

1

x

x

,

gdzie:

0

0

1



 o



!

!

f

o



k

k

k

k

k

r

,

r

r

,

r

.

Wtedy

 

 

 

 

 

>

@

^

`





¦

2

1

2

0

1

j

j

k

k

z

*

;

x

g

min

r

x

Q

P

Q

Q

x

x

x





>

@





>

@

^

`

2

2

0

2

0

1

1

;

x

min

;

x

min

r

x

k









Je

Īeli:

r

=1

r

=0,5

Q

*

(x)

Q

*

(x)

Q(x)

)

Q(x)

x

1

2

a)

x

(kara nie jest nak

áadana),

 

 

x

Q

x

Q

*

)



b)

 





2

1

1

1







x

r

x

x

Q

k

*

x

(kara jest nak

áadana),

c)

 





2

2

1

2

x

r

x

x

Q

x

k

*





!

(kara jest nak

áadana).

W punkcie minimum aktywne jest ograniczenie

 

0

1

1

d



x

x

g

, zatem zbli

Īając

si

Ċ do minimum od lewej strony mamy:

 





2

1

ˆ

0

1

ˆ

2

1

*

k

k

r

x

x

r

x

x

Q



Ÿ





w

w

,

czyli

 

 







1

0

ˆ

,

995

,

0

01

,

0

ˆ

,

75

,

0

5

,

0

ˆ

,

5

,

0

1

ˆ

3

2

1



f

x

x

x

x

.

Kolejne kroki algorytmu:

1° Wybierz punkt startowy

0

x

, podstaw

0

k

.

J.Stadnicki Optymalizacja

- 78 -

2° Startuj

ąc z punktu

k

x

rozwi

ązujemy zadanie programowania nieliniowego bez

ogranicze

Ĕ z zastĊpczą funkcją celu. Przyjmując

0

!

k

r

r

otrzymamy kolejne

przybli

Īone rozwiązanie zadania

 

k

k

r

xˆ

.

3° Je

Īeli dokáadnoĞü rozwiązania jest dostateczna – koĔczymy obliczenia.

W przeciwnym przypadku podstaw

1

1

1

!





c

gdzie

,

c

r

r

,

k

k

k

k

i

powró

ü do punktu 2°.

Uwaga:

Szybko

Ğü zbieĪnoĞci algorytmu zaleĪy od:

x przyjĊcia punktu startowego

0

x

i sta

áych

oraz ,

0

r

c

x zaleca siĊ dobraü

tak aby w punkcie startu warto

Ğci

0

r

 

0

x

Q

i

 

k

z

P x

0

by

áy

zbli

Īone,

x

przyjmuje si

Ċ od 4 do 10.

c

Otrzymane w kolejnych iteracjach rozwi

ązania poĞrednie nie naleĪą do zbioru

dopuszczalnego.

Aby to wyeliminowa

ü przesuwa siĊ granice obszaru dopuszczalnego na zewnątrz

przyjmuj

ąc:

, wtedy

 

 

*

g

g

G



x

x

j

j

j

j

G

– jest marginesem powi

Ċkszającym

zbiór dopuszczalny.

Metoda wewn

Ċtrznej funkcji kary:

r

=0,01

r

=0,25

Q

*

(x)

Q

*

(x)

Q(x)

)

Q(x)

x

1

2

Wprowad

Ĩmy funkcjĊ kary postaci:

 

 

¦



m

j

j

k

k

w

g

r

P

1

1

x

x

,

gdzie:

0

0

1



 o



!

!

f

o



k

k

k

k

k

r

,

r

r

,

r

Wtedy:

 

 

 

 

 





¦

2

1

1

j

j

k

k

w

*

x

g

r

x

Q

P

Q

Q

x

x

x

¸

¹

·

¨

©

§









2

1

1

1

x

x

r

x

k

.

Je

Īeli:

a)

uaktywnia si

Ċ ograniczenie



o 1

x

 

x

g

1

, wtedy:

 

x

r

x

x

*





#

1

Q

,

b)

uaktywnia si

Ċ ograniczenie



o 2

x

 

x

g

2

, wtedy:

 

2





#

x

r

x

x

*

Q

.

W punkcie minimum aktywne jest ograniczenie

 

0

1

1

d



x

x

g

, zatem zbli

Īając

si

Ċ do minimum od prawej strony mamy:

 





k

k

r

x

x

r

x

x

Q



Ÿ





#

w

w

1

ˆ

0

ˆ

1

1

2

*

,

czyli















1

0

ˆ

,

03

,

1

001

,

0

ˆ

,

1

,

1

01

,

0

ˆ

,

5

,

1

25

,

0

ˆ

3

2

1



f

x

x

x

x

.

Kolejne kroki algorytmu:

1° Wybierz punkt startowy

)



0

x

, podstaw

0

k

.

2° Startuj

ąc z punktu

k

x

rozwi

ązujemy zadanie programowania nieliniowego bez

ogranicze

Ĕ z zastĊpczą funkcją celu. Przyjmując

0

!

k

r

r

otrzymamy kolejne

przybli

Īone rozwiązanie zadania

 

k

k

r

xˆ

.

J.Stadnicki Optymalizacja

- 79 -

J.Stadnicki Optymalizacja

- 80 -

3° Je

Īeli dokáadnoĞü rozwiązania jest dostateczna – koĔczymy obliczenia.

W przeciwnym przypadku podstaw

1

1

1

!





c

gdzie

,

c

r

r

,

k

k

k

k

i

powró

ü do punktu 2°.

Uwagi:

x Otrzymane w kolejnych iteracjach rozwiązania poĞrednie naleĪą do zbioru

dopuszczalnego (punkt startowy musi le

Īeü wewnątrz obszaru dopuszczalnego!)

x Dla poprawy efektywnoĞci numerycznej (duĪe zmiany zastĊpczej funkcji celu dla

powoduj

ą trudnoĞci w znalezieniu minimum) algorytmu przesuwa siĊ

granice obszaru dopuszczalnego do wewn

ątrz przyjmując:

0

o

r

 

 

j

j

*

j

g

g

H



x

x

,

wtedy

j

H

– jest marginesem pomniejszaj

ącym zbiór dopuszczalny.

x Pozostaáe uwagi jak w metodzie zewnĊtrznej funkcji kary.

Metoda mieszanej wewn

Ċtrzno-zewnĊtrznej funkcji kary:

Poniewa

Ī czĊsto minimum leĪy na brzegu obszaru dopuszczalnego, dobrą

efektywno

Ğü numeryczną w poszukiwaniu minimum wykazuje algorytm mieszany

polegaj

ący na zbliĪaniu siĊ do minimum z zewnątrz metodą zewnĊtrznej funkcji kary

a od wewn

ątrz metoda wewnĊtrznej funkcji kary.

PROGRAMOWANIE WIELOKRYTERIALNE

Podczas poszukiwania rozwi

ązania optymalnego w wielu konkretnych

sytuacjach zachodzi potrzeba rozwi

ązania zadania z uwzglĊdnieniem wiĊcej niĪ

jednego kryterium. Ponadto pomi

Ċdzy kryteriami czĊsto wystĊpuje konflikt, tzn. Īe

poprawa jednego kryterium powoduje pogorszenie si

Ċ innego (innych)

kryteriów.

Zadanie optymalizacji, w którym formu

áuje siĊ wiĊcej niĪ jedno kryterium,

nazywamy programowaniem wielokryterialnym (optymalizacj

ą wielokryterialną,

polioptymalizacj

ą).

Zadanie programowania wielokryterialnego:

Znajd

Ĩ wektor

, który minimalizuje przyj

Ċty ukáad

p

kryteriów sk

áadowych

.



x

ĭ

l

dla

 

p

,

,

min

q

l

!

1

o

x

Rozwi

ązanie optymalne z uwagi na jedno kryterium to rozwiązanie

polioptymalne.

Zadania programowania wielokryterialnego w przeciwie

Ĕstwie do zadania

programowania jednokryterialnego nie da si

Ċ zdefiniowaü za pomocą relacji

porz

ądku liniowego.

Relacja porz

ądku liniowego:

Niech dana b

Ċdzie funkcja

o dziedzinie

i zakresie

,

okre

Ğlająca relacjĊ

(

a

poprzedza

b

) mi

Ċdzy punktami przestrzeni

.



2

1

x

,

x

f



2

R

2

R

b

a

E

2

R

Je

Īeli speánione są warunki:

1. je

Ğli

a

b

zachodzi

nie

to

b

a

b

a

;

E

z

š

,

2. je

Ğli

c

a

zachodzi

to

c

b

b

a

E

E

E

š

,

3. je

Ğli

a

b

b

a

zachodzi

to

b

a

E

E

›

z

to jest to relacja porz

ądku liniowego.

Np.:

y

x



– relacja mniejszo

Ğci,

y

x

!

– relacja wi

ĊkszoĞci,

y

x

d

– relacja niewi

Ċksze,

– relacja niemniejsze.

y

x

t

Teoria nie daje odpowiedzi jak w sposób bezpo

Ğredni rozwiązaü zadanie

programowania wielokryterialnego!

J.Stadnicki Optymalizacja

- 81 -

J.Stadnicki Optymalizacja

- 82 -

Sprowadzanie problemu do zadania programowania jednokryterialnego
(pseudopolioptymalizacja)

Metoda wa

Īonej funkcji celu:

Niech

>

takie,

Īe

@

T

p

,

,

U

U

!

1

0

t

l

U

oraz

0

z

ȡ

b

Ċdą wagami przypisanymi

poszczególnym kryteriom

.

 

x

l

q

Znajd

Ĩ wektor

x

, który minimalizuje zast

Ċpczą funkcjĊ celu:

, przy ograniczeniach

 

 

¦

o

p

l

l

l

T

*

min

q

Q

1

x

x

q

ȡ

U



x

ĭ

.

Wagi

l

U

dobiera si

Ċ w dwóch etapach:

1. normalizacja wag polegaj

ąca na przyjĊciu takich wartoĞci liczbowych

aby

iloczyny

by

áy liczbami tego samego rzĊdu wielkoĞci (poszczególne

kryteria

mog

ą wyraĪaü róĪne wielkoĞci fizyczne róĪniące siĊ rzĊdem

wielko

Ğci!),

1

l

U

 

x

l

l

q

1

U

l

q

2. okre

Ğlenie waĪnoĞci poszczególnych kryteriów

 

x

l

q

– udzia

áów kryteriów

 

x

l

q

w kryterium zbiorczym

. Dobrane wagi

powinny spe

ániaü warunek:

. Doboru wag dokonuje si

Ċ arbitralnie, czĊsto przy udziale zespoáu

ekspertów.

 

x

*

Q

2

l

U

¦

p

l

l

1

2

1

U

Przeniesienie zadania do przestrzeni kryteriów

Formu

áując poszczególne kryteria skáadowe

 

x

l

q

mo

Īemy kaĪdemu punktowi

przyporz

ądkowaü liczbĊ

b

Ċdącą wartoĞcią danego kryterium w tym punkcie.

x

l

q

Oznacza to,

Īe zadanie z przestrzeni zmiennych decyzyjnych

przenosimy do

przestrzeni celów

.

n

R

p

P

Uwaga:

Ró

Īne punkty w przestrzeni zmiennych decyzyjnych mogą mieü te same

warto

Ğci kryteriów, tzn., Īe w przestrzeni celów są jednym punktem.

Przesrze

Ĕ zmiennych decyzyjnych

Przestrze

Ĕ celów

n

R

p

P

)

p

)

[

q

1

1

(

x

1

1

, x

2

1

),

q

2

1

(

x

1

1

, x

2

1

)]

[

q

1

3

(

x

1

3

, x

2

3

),

q

2

3

(

x

1

3

, x

2

3

)]

q

1

(x)

[

q

1

2

(

x

1

2

, x

2

2

),

q

2

2

(

x

1

2

, x

2

2

)]

q

2

(x)

[

x

1

3

, x

2

3

]

[

x

1

2

, x

2

2

]

[

x

1

1

, x

2

1

]

x

2

x

1

Metoda punktu docelowego:

Za

áóĪmy, Īe znane jest rozwiązanie idealne w przestrzeni celów, tj. punkt, w

którym poszczególne kryteria sk

áadowe mają minimalne wartoĞci

>

@

T

*

p

*

*

q

,

,

q

!

1

q

.

Punkt ten nazywamy punktem docelowym.

Cz

Ċsto jest to punkt idealny niemoĪliwy do osiągniĊcia w rzeczywistoĞci.

x JeĪeli punkt docelowy

*

p



q

ĭ

to zadanie sprowadza si

Ċ do rozwiązania ukáadu

równa

Ĕ:

q

, którego rozwi

ązaniem jest punkt optymalny

b

Ċdący

rozwi

ązaniem zadania programowania wielokryterialnego.

 

*
l

l

q

x

ˆ

x

Uwaga:

Dla problemu nieliniowego rozwi

ązanie powyĪszego ukáadu równaĔ moĪe byü

trudne.

x JeĪeli punkt docelowy

*

p



q

ĭ

to zadanie sprowadza si

Ċ wyznaczenia punktu

le

Īącego najbliĪej w sensie przyjĊtej normy od punktu docelowego.

J.Stadnicki Optymalizacja

- 83 -

q

2

(x)

)

p

q – q

*

=

min

q

^

- punkt optymalny

q

1

(x)

q

*

- punkt docelowy

Rozwi

ązanie zadania programowania wielokryterialnego sprowadza siĊ do

minimalizacji metryki





min

d

*

o

 q

q

przy ograniczeniach

.

p



œ



q

ĭ

x

ĭ

Stosowane metryki:

x metryka Minkowskiego:





r

p

l

r

*
l

l

l

*

q

q

d

1

1

¸¸

¹

·

¨¨

©

§





¦

U

q

q

,

gdzie

l

U

– waga kryterium sk

áadowego (wyznaczona wg poprzednio omówionych

zasad),

x metryka Euklidesa: (dla

)

2

r









¦





p

l

*
l

l

l

*

q

q

d

1

2

U

q

q

,

wyra

Īa geometryczną dáugoĞü wektora

*

q

q



,

x metryka prostokątna: (dla

)

1

r





¦





p

l

*
l

l

l

*

q

q

d

1

U

q

q

,

x metryka geometryczna:





–





p

l

*
l

l

*

l

q

q

d

1

U

q

q

.

J.Stadnicki Optymalizacja

- 84 -

Rozwi

ązania Pareto-optymalne:

Rozwi

ązanie

nazywamy niezdominowanym, je

Īeli nie istnieje

*



x

ĭ



x

ĭ

takie,

Īe

 

 

*

l

q x

l

q x



.

Zbiór wszystkich rozwi

ązaĔ niezdominowanych nazywamy zbiorem

kompromisów (zbiorem Pareto).

Inaczej, dla punktów nale

Īących do zbioru kompromisów nie moĪna poprawiü

jednego z kryteriów sk

áadowych nie pogarszając któregoĞ z pozostaáych.

(-) pogorszenie kryterium

(+) poprawa kryterium

(-)

(+)

(+)

(-)

(+)

(+)

zbiór

kompromisów

)

q

q

1

(x)

q

2

(x)

W zadaniu minimalizacji

zbiór kompromisów to

fragment brzegu zbioru

(zbioru

dopuszczalnego

przekszta

áconego do

przestrzeni celów) „nie

zas

áoniĊty” od strony

q

ĭ

f



przez inna cz

ĊĞü

zbioru

ĭ

.

q

Wyboru punktu optymalnego ze zbioru kompromisów (punktu Pareto-optymalnego)
mo

Īna dokonaü za pomocą obu poznanych wczeĞniej metod.

J.Stadnicki Optymalizacja

- 85 -

Metoda wa

Īonej funkcji celu:

Zast

Ċpczą funkcjĊ celu

mo

Īemy potraktowaü jak

równanie parametryczne z

parametrem

Q

.

 

 

¦

o

p

l

l

l

T

*

min

q

Q

1

x

x

q

ȡ

U

*

q

2

(x)

)

q

A

B

Q

*

(

x

)

Zmieniaj

ąc wartoĞü parametru

znajdujemy punkt wspólny

funkcji i zbioru

.

q

ĭ

C

x

^

D

q

1

(x)

Dla problemu dwuwymiarowego wagi

1

U

i

2

U

okre

Ğlają nachylenie prostej

.





2

2

1

1

2

1

x

x

x

,

x

Q

*

U

U



Wada:

Nie mo

Īna osiągnąü punktów leĪących w „zgáĊbieniu” zbioru kompromisów (np.

punktu C).

q

*

(x)

D

C

B

A

x

^

)

q

q

1

(x)

q

2

(x)

Metoda punktu docelowego:

Poszukujemy punktu ze zbioru

kompromisów, który jest

najbli

Īszy w sencie przyjĊtej

normy od punktu docelowego

(rozwi

ązania idealnego).

J.Stadnicki Optymalizacja

- 86 -