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