2004 10 14 Optymalizacja wyklady

Akademia Techniczno-Humanistyczna
w Bielsku Białej
Katedra Mechaniki
i In ynierskich Metod Komputerowych
Dr hab. in . Jacek Stadnicki
prof. Akademii Techniczno - Humanistycznej
Optymalizacja
Bielsko Biała 2002
Spis tre ci - Ra-V
Komputerowe metody rozwi zywania zada
Formułowanie problemu optymalizacji ..............................1
programowania nieliniowego................................................63
Sformułowanie zadania ...........................................................2
Zadanie programowania nieliniowego bez ogranicze ............63
Etapy formułowania i rozwi zywania zadania optymalizacji .2
Metody rz du zerowego (bezgradientowe) funkcji jednej
Programowanie liniowe ........................................................3
zmiennej ..................................................................................64
Postać ogólna zagadnienie programowania liniowego............3
Metoda złotego podziału..........................................................64
Linowy model produkcji .........................................................4
Metoda Powella (interpolacji kwadratowej)............................65
Problem mieszanek, problem diety .........................................5
Metody rz du pierwszego (gradientowe) funkcji jednej
zmiennej ..................................................................................66
Wybór procesu technologicznego ...........................................6
Metoda siecznych ....................................................................67
Standardowe zagadnienie programowania liniowego .............7
Metody rz du drugiego funkcji jednej zmiennej .....................68
Sens geometryczny sprowadzania zadania ogólnego do
standardowego.........................................................................8
Metoda Newtona......................................................................68
Postać kanoniczna zadania programowania liniowego ...........9
Metody rz du zerowego (bezgradientowe) minimalizacji
funkcji wielu zmiennych..........................................................69
Metoda SYMPLEKS.............................................................10
Metody poszukiwa prostych ..................................................69
Zagadnienie transportowe..................................................17
Metoda Gaussa-Seidela ...........................................................69
Metoda najwi kszego przepływu ..........................................18
Metoda losowego przeszukiwania...........................................70
Algorytm cechowania............................................................19
Metody kierunków poprawy....................................................71
Pierwotne (prymalne) zadanie programowania liniowego....22
Metoda kierunków sprz onych Powella ................................71
Dualne zadanie programowania liniowego ...........................22
Metody rz du pierwszego (gradientowe) minimalizacji
Algorytm prymalno-dualny zadania transportowego ............24
funkcji wielu zmiennych..........................................................73
Zastosowania.........................................................................28
Metoda gradientu sprz onego ................................................74
Zadanie transportowo-produkcyjne.......................................29
Metody rz du drugiego............................................................75
Zadanie lokalizacji produkcji ................................................30
Metoda Newtona......................................................................75
Zadanie minimalizacji pustych przebiegów ..........................30
Zadanie programowania nieliniowego z ograniczeniami ........75
Optymalizacja na grafach...................................................33
Algorytmy (metody) podstawowe ...........................................76
Problem najkrótszej drogi .....................................................34
Metoda systematycznego przeszukiwania ...............................76
Algorytm Dijkstry .................................................................34
Metoda poszukiwa losowych (Monte Carlo).........................77
Problem komiwoja era..........................................................36
Algorytmy (metody) z pami ci ..............................................78
Algorytm podziału i ogranicze ............................................37
Metoda funkcji kary.................................................................78
Programowanie zero-jedynkowe........................................42
Metoda zewn trznej funkcji kary ............................................79
Zadanie programowania zero-jedynkowego .........................42
Metoda wewn trznej funkcji kary ...........................................81
Metoda filtru Balasa ..............................................................44
Metoda mieszanej wewn trzno-zewn trznej funkcji kary.......82
Programowanie całkowitoliczbowe....................................46
Programowanie wielokryterialne .........................................83
Zadanie programowania całkowitoliczbowego.....................46
Zadanie programowania wielokryterialnego ...........................83
Podstawowe odci cie Gomory ego .......................................48
Relacja porz dku liniowego: ...................................................83
Algorytm Gomory ego..........................................................51
Sprowadzanie problemu do zadania programowania
Programowanie nieliniowe .................................................52
jednokryterialnego (pseudopolioptymalizacja)........................84
Zadanie programowania nieliniowego bez ogranicze .........52
Metoda wa onej funkcji celu...................................................84
Zadanie programowania nieliniowego z ograniczeniami w
Przeniesienie zadania do przestrzeni kryteriów.......................84
postaci równo ci....................................................................56
Metoda punktu docelowego.....................................................85
Metoda mno ników Lagrange a............................................57
Rozwi zania Pareto-optymalne ...............................................87
Zadanie programowania nieliniowego z ograniczeniami w
Metoda wa onej funkcji celu...................................................88
postaci nierówno ci ...............................................................58
Metoda punktu docelowego.....................................................88
FORMUAOWANIE 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.
T
x = [x1 xi xN ] x " RN
T
�ł łł
�ł
x = x , , N śł
x
1
, n xn+1, ,x
śł
�łzmienne decyzyjne parametry dane
�ł �ł
oraz warunki ograniczaj ce zakresy zmienno ci wektora x .
Ograniczenia:
g (x1,...,xn )d" 0 ( j = 1,...,m)
1. nierówno ciowe:
j
hk (x1,...,xn)= 0 (k =1,...,q)
2. równo ciowe (funkcjonalne):
Zbiór punktów przestrzeni R n spełniaj cych przyj te ograniczenia nazywamy
zbiorem dopuszczalnym (zbiorem rozwi za dopuszczalnych, zbiorem decyzji
dopuszczalnych).
Ś �" Rn
Zbiór dopuszczalny:
Ś `" 0
Aby zadanie miało sens zbiór dopuszczalny nie mo e być zbiorem pustym
g4(x1,x2)e" 0
g4(x1,x2)e" 0
x2
x2
g1(x1,x2)e" 0
g1(x1,x2)e" 0
Ś
h1(x1,x2)= 0
Ś
g3(x1,x2)e" 0
g3(x1,x2)e" 0
x1
x1
g2(x1,x2)e" 0
g2(x1,x2)e" 0
Zbiór dopuszczalny dla problemu dwu- + jedno ograniczenie
wymiarowego równo ciowe
J.Stadnicki Optymalizacja 1
+ dwa ograniczenia równo ciowe
g4(x1,x2)e" 0
x2
g1(x1,x2)e" 0
Wnioski:
h2(x1,x2)= 0
Ś
1. ogranicze nierówno ciowych
h1(x1,x2)= 0
mo e być dowolnie du o bylyby
Ś `" 0
,
2. ogranicze równo ciowych mo e
g3(x1,x2)e" 0
być co najwy ej n-1,
x1
g2(x1,x2)e" 0
Aby ze zbioru dopuszczalnego wybrać punkt optymalny, definiujemy pewn funkcj
Q(x)
, która b dzie miar spełnienia przyj tych celów (funkcja celu, kryterium
jako ci).
Sformułowanie zadania:
T
x = [x1, ,xn]
Znajd taki wektor Ć , który nale c do obszaru dopuszczalnego
minimalizuje (maksymalizuje) funkcj celu.
( ) ( ) ( )
x "Ś : '" Q x d" Q x
" dla problemu maksymalizacji:
{}
x"Ś
( ) ( ) ( )
x "Ś : '" Q x e" Q x
" dla problemu minimalizacji:
{}
x"Ś
T
x = [x1,...,xn]
Wektor Ć Ć Ć b d cy rozwi zaniem powy szego zadania nazywamy
wektorem optymalnym.
Etapy formułowania i rozwi zywania zadania optymalizacji:
T
x = [x1, ,xn]
1� okre lić zmienne decyzyjne ,
Ś , x "Ś Ś `" 0
2� okre lić zbiór dopuszczalny i sprawdzić czy ,
Q x
3� utworzyć funkcj celu ( ),
x
4� znale ć wektor optymalny. Ć .
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:
c1 x1 a11 a1i a1n b1
�ł łł �ł łł �ł łł �ł łł
�ł śł �ł śł �ł śł �ł śł

�ł śł �ł śł �ł śł �ł śł
c = ci x = xi x e" 0 A = a a a b = bj
�ł śł �ł śł �ł śł �ł śł
j1 ji jn
�ł śł �ł śł �ł śł �ł śł

�ł śł �ł śł �ł śł �ł śł
�ł śł �ł śł �ł śł �ł śł
ami amn �ł
�łcn �ł �łxn �ł �łam1 �łbm �ł
m < n
wektor wektor zmiennych
m
funkcji zmiennych - liczba ogranicze
n
celu decyzyjnych - liczba zmiennych decyzyjnych
n
Q = cT x = xT c = xi funkcja celu (iloczyn skalarny wektorów c i x )
"c
i
i=1
Postać ogólna zagadnienie programowania liniowego:
Q = cT x
Znale ć minimum:
A�" x d" b przy czym x e" 0
przy warunkach:
inaczej:
Q = c1x1+...+cixi +...+cnxn min
gdy spełnione s :
J.Stadnicki Optymalizacja 3
a11x1 + + a1i xi + + a1n xn d" b1

a x1 + + a xi + + a xn d" bj
j1 ji jn
xi e" 0
przy czym

am1x1 + + ami xi + + amn xn d" bm
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:
aij - zu ycie rodka produkcji j na wytworzenie jednostki wyrobu i,
bj - dost pne zasoby rodka produkcji j,
ci - zysk jednostkowy ze sprzeda y wyrobu i,
xi - poszukiwana wielko ć produkcji wyrobu i.
Obszar dopuszczalny okre lony przez ograniczenia:
a11x1 + + a1ixi + + a1nxn d" b1

a x1 + + a xi + + a xn d" bj
j1 ji jn
i = 1,...,n j = 1,...,m

am1x1 + + amixi + + amnxn d" bm
oraz xi e" 0
Funkcja celu:
Q(x1, , xi, xn) = c1x1 + + cixi + + cnxn max
J.Stadnicki Optymalizacja 4
Np.
Firma produkuje dwa wyroby (W1, W2) za pomoc trzech maszyn (M1, M2, M3).
W1 W2
dzienny limit
8 6
M1 720
czasu pracy
Zu ycie czasu na jednostk wyrobu
8 16 M2 1280
[min]
[min]
12 8 M3 960
Zysk jednostkowy [zł] 12 10
Obliczyć wielko ć dziennej produkcji zapewniaj cej maksimum zysku.
8x1 + 6x2 d" 720
8x1 + 16x2 d" 1280
Q = 12x1 +10x2 max
12x1 + 8x2 d" 960
oraz xi e" 0
120
12x1+ 8x2 d" 720
8x1+ 6x2 d" 120
100
8x1+ 16x2 d" 1280
80
Punkt
optymalny
x2
60
(40,60)
Q=12x1+ 10x2 max
40 Obszar
dopuszczalny
20
0
0 20 40 60 80 100 120 140 160
x1
Problem mieszanek, problem diety
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 Cena [z ]
CSi Mn P
I 28 10 30 10 100
II 14 12 20 10 50
III 10 6 30 15 200
28x1 +14x2 +10x3 d" 14
10x1 +12x2 + 6x3 d" 8
Q = 100x1 + 50x2 + 200x3 min
30x1 + 20x2 + 30x3 e" 25
10x1 +10x2 +15x3 e" 12
oraz xi e" 0
Odp.: x1= 0,1, x2= 0,325, x3= 0,517, Q = 129,6 zł.
Wybór procesu technologicznego
Firma ma produkować j wyrobów w ilo ciach bj. Wykorzystuj c proces
technologiczny i z jednostkow intensywno ci (jeden raz) uzyskuje si produkty w
ilo ciach aij i ponosi koszty ci. 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
7x1 + 3x2 e" 2100 (300 kpl.� 7 szt./ kpl.)
oraz xi e" 0
x2 + 2x3 e" 1200 (300 kpl.� 4 szt./ kpl.)
Q(x1, x2, x3) = 0,3x1 + 0,6x2 + 0,2x3 min
Odp.: x1= 300, x2= 0, x3= 600, Q = 210
J.Stadnicki Optymalizacja 6
Standardowe zagadnienie programowania liniowego:
Q = cT x
Znale ć minimum:
A�" x =b przy czym x e" 0
przy warunkach:
OGÓLNE STANDARDOWE
d"
1. pełne ograniczenie nierówno ciowe typu :
a11x1+ +a1ixi + +a1nxn d" b1
Ka da z nierówno ci:
mo e być sprowadzona do równo ci, przez wprowadzenie zmiennej dopełniaj cej
xn+1 e" 0 a11x1 + + a1i xi + + a1nxn + xn+1 = b1
(sztucznej) :
e"
2. pełne ograniczenie nierówno ciowe typu :
a11x1+ +a1ixi + +a1nxn e" b1
Je eli nierówno ć miała zwrot przeciwny:
to przy sprowadzaniu do równo ci, sztuczn zmienn nale y odj ć:
a11x1 + + a1i xi + + a1nxn xn+1 = b1
3. pełne dwustronne ograniczenie nierówno ciowe:
1
b1 d" a11x1 + + a1i xi + + a1n xn d" b2
Ka d z dwustronnych nierówno ci:
1
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:
2x1 + x2 d" 2, x1 e" 0, x2 e" 0
x3
Po wprowadzeniu dodatkowej zmiennej otrzymamy trójk t ABC le cy w
przestrzeni trójwymiarowej:
2x1 + x2 + x3 2 = 0, x1 e" 0, x2 e" 0, x3 e" 0
J.Stadnicki Optymalizacja 7
x2
a) b)
x2
x2
B
2
2x1+x2=2
Ś
ŚŚ
Ś
A
x1=0
^
^
x
x
0
1 x1
x1
x1
x2=0
c)
x2
x2 x2
d)
^
2
B
x "
x3=0
x1=0
Ś
Ś
2x1+x2+x3=2
A
A
Ś
^
x
0
1 x1
2
x1 x1
x2=0
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:
(n m)
W ogólnym przypadku zbiór dopuszczalny jest wymiarowym wypukłym
n
wielo cianem le cym w przestrzeni -wymiarowej, który nazywamy sympleksem.
W przykładzie:
n = 3
zmienne decyzyjne,
m =1 n m = 3 1 = 2
ograniczenie, - 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
(n m)
Wierzchołki to takie punkty obszaru dopuszczalnego, w których zmiennych
xi
decyzyjnych ma warto ć zero, a reszta okre lona jest układem równa :
A�" x = b
xN
Zmienne, które przyrównujemy do zera nazywamy zmiennymi niebazowymi ,
xB
pozostałe zmienne nazywamy zmiennymi bazowymi .
zmienne bazowe
�łłł
�łxB łł
= x
Zatem: �łzmienne niebazoweśł
�łx śł
�ł�ł
�ł N �ł
Postać zadania programowania liniowego, w której wykonano powy sze
przekształcenia nosi nazw postaci kanonicznej.
Postać kanoniczna zadania programowania liniowego:
xi
Wybran zmienn układu równa :
a11x1 + + a1i xi + + a1n xn = b1

a x1 + + a xi + + a xn = bj
j1 ji jn

am1x1 + + ami xi + + amn xn = bm
mo na wyeliminować ze wszystkich równa z wyj tkiem równania j tego:
a
1� dziel c równanie j te przez ,
ji
aki xi
2� dziel c pozostałe równania przez współczynniki stoj ce przy ,
3� odejmuj c od ka dego z otrzymanych równa przekształcone równanie j te.
a11 a1n b1
x1 + + 1xi + + xn =
a1i a1i a1i
_
aj1 ajn bj
x1 + + 1xi + + xn =
aji aji aji
= = = =
�ł �ł �ł
a11 aj1 �ł a1n ajn �ł b1 bj �ł
�ł �łx1 + + 0xi + + �ł �łxn = �ł �ł

�ł �ł �ł
a1i aji �ł a1i aji �ł a1i aji �ł
�ł łł �ł �ł łł
łł

' ' '
a11 a1n b1
J.Stadnicki Optymalizacja 9
Dla wszystkich równa układu:
a11' x1 + + 0 �" xi + + a1n' xn = b1'

a ' x1 + + 1�" xi + + a ' xn = bj'
j1 jn

am1' x1 + + 0 �" xi + + amn' xn = bm'
xi
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.
1�" x1 + 0 �" x2 + + 0 �" xm + a1,m+1" xm+1 + + a1,n" xn = b1"
0 �" x1 + 1�" x2 + + 0 �" xm + a2,m+1" xm+1 + + a2,n" xn = b2"

0 �" x1 + 0 �" x2 + + 1�" xm + am,m+1" xm+1 + + am,n" xn = bm"
Metoda SYMPLEKS:
Zadanie:
Q = cT x
Znale ć minimum , przy warunkach:
A�" x =b x e" 0
(1)
Równanie (1) mo na sprowadzić do postaci kanonicznej i zapisać w postaci:
xB
�ł łł
B N �" = b
[]
(2)
�łx śł
�ł N �ł
gdzie:
xB
- wektor zmiennych bazowych,
xN
- wektor zmiennych niebazowych,
J.Stadnicki Optymalizacja 10
Wyznaczanie bazowego rozwi zania dopuszczalnego:
xN = 0
Je eli podstawimy za warto ci zmiennych niebazowych to rozwi zanie
równania (2) nazywa si rozwi zaniem bazowym.
B �" xB = b �" B-1
xB = B 1b
B
- rozwi zanie bazowe, nieosobliw macierz nazywamy baz .
xBe" 0
x
Je li ponadto , to mówimy, e 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
xN
.
cB
�ł łł
T T
Q = cB xB + cN xN gdzie c =
(3)
�łc śł
�ł N �ł
BxB + N xN = b �"B 1
(4)
xB + B 1N xN = B 1b
xB = B 1b B 1N xN
(5) wstawmy (5) do (3):
T T
Q = cB B 1b B 1N xN + cN xN
()
T T T
Q = cB B 1b + cN cB B 1N xN = q0 + pT xN
(6)
()
J.Stadnicki Optymalizacja 11
T T T
q0 = cB B 1b pT = cN cB B 1N
gdzie: (7) (8)
Równanie (6) wyra a funkcj celu za pomoc zmiennych niebazowych.
Mo liwe s trzy przypadki:
p > 0
1� wszystkie składowe wektora s dodatnie ,
Poniewa minimalizujmy funkcj celu, wprowadzenie odpowiadaj cych
p
N
składowym wektora kolumn macierzy do bazy zwi kszy (pogorszy)
xB
warto ć funkcji celu �!bazowe rozwi zanie dopuszczalne jest rozwi zaniem
x = xB
optymalnym zadania Ć .
p = 0
2� wszystkie składowe wektora s zerowe ,
Rozwi zanie jest niejednoznaczne, tzn. e mo na przej ć do innego wierzchołka
sympleksu baz zmiany warto ci funkcji celu.
pk < 0
3� wektor p posiada ujemn składow ,
ak
N
Wprowadzenie odpowiadaj cej jej kolumny macierzy do bazy zmniejszy
(poprawi) warto ć funkcji celu (tw. o poprawianiu).
p pk
Je eli w wektorze wyst puje wi cej ujemnych składowych , wybieramy
najmniejsz z nich.
T
pT = cT cB 1 N
z (8): N
B
T
T = cT B 1 �" B �! BT = cT
oznaczaj c:
B B
cB = BT pT = cT T N
(9) czyli (10)
N
p
- wektor mno ników sympleksowych, - wektor wzgl dny funkcji celu.
p pk
Ujemn składow wektora oznaczymy .
pk = cNk Tak < 0 dla m + 1 d" k d" n
Je eli:
ak
B
to kolumn wprowadzamy do bazy w nast pnej iteracji, a warto ć funkcji celu
Q
ulegnie zmniejszeniu.
J.Stadnicki Optymalizacja 12
Poprawa bazowego rozwi zania dopuszczalnego (wybór zmiennej bazowej
wyprowadzanej z bazy):
ak
B
Nale y teraz znale ć kolumn w bazie , w miejsce której wprowadzimy .
xB = B 1b B 1NxN
Z (5):
x0 = B 1b
oznaczaj c bie ce rozwi zanie bazowe przez , damy aby nowe
xB e" 0
bazowe rozwi zanie było dopuszczalne ( ):
xB = x0 B 1ak xNk e" 0 czyli by: xB = x0 y xNk e" 0
(11)
B 1ak = y �" B �! (12) ak = By �! y = B 1ak
gdzie:
y
przy czym otrzymuje si jako rozwi zanie układu (12).
y e" 0
Warto ć zmiennej bazowej mo na zmniejszyć je eli , w przeciwnym przypadku
zbiór dopuszczalny jest nieograniczony i funkcja celu mo e być zmniejszona do
" .
Baz opuszcza ta kolumna, dla której:
ńł �ł
x0i
� = min�ł żł
(13)
y0i
ół �ł
Przykład:
Q = 05x1 04x2
..
Zminimalizować: przy ograniczeniach:
x1 + 2x2 d" 24
ńł
�ł15x + x2 d" 18 x1,x2 e" 0
.
�ł
1
�ł
x1 d" 11
ół
1� Sprowadzamy zadanie ogólne do standardowego kanonicznego przez dodanie
x3, x4, x5 e" 0
do wektora x sztucznych zmiennych:
x1 + 2x2 + x3 = 24
ńł
�ł15x + x2 + x4 = 18
.
�ł
1
�ł
x1 + x5 = 11
ół
J.Stadnicki Optymalizacja 13
Powy szy układ po zamianie kolejno ci zmiennych jest postaci kanonicznej!
Mamy wi c:
x1
�ł łł
�łx śł
�ł 1 2 1 0 0łł �ł24łł
2
�ł śł
�ł15 �ł18śł
�łx3śł
A = . 1 0 1 0śł x = b = cT = 0.5 0.4 0 0 0
[]
�ł śł �ł śł
�łx śł
�ł �ł11śł
1 0 0 0 1śł
4
�ł �ł �ł �ł
�ł śł
�ł śł
�łx5 �ł
xN = 0
B
1� Rozpoczynamy obliczenia dla . Poniewa jest nieosobliwa, traktujemy
xB
j jako baz a jako rozwi zanie bazowe.
x3 1 0 0 0
�ł łł �ł łł �ł łł
�łx śł �ł0 �ł0śł
xB = B = 1 0śł B = B 1 = I cB =
4
�ł śł �ł śł �ł śł
�ł śł �ł śł �ł
�łx5�ł �ł0 0 1�ł �ł0śł
�ł
Rozwi zanie bazowe;
�ł24łł �ł24łł
�ł18śł
xBB = b �! xB = B 1b = I�ł18śł =
�ł śł �ł śł
�ł
�ł11śł �ł �ł
�ł �ł11śł
T T T
T = cB B 1 = cB I = cB = [0 0 0]
z (9):
z (10):
1 2łł
�ł
T
�ł1.5 1śł = 0.5 0.4]
pT = cN T N = [ 0.5 0.4] [0 0 0][
�ł śł
1 0�ł
�ł śł
�ł
p
2� Zgodnie z tw. o poprawianiu wybieramy ujemn składow wektora i
B B
wprowadzamy j do bazy . Poniewa -0.5 < -0.4, do bazy wprowadzamy
1
�ł łł
�ł15śł
x1 �! x1 = .
kolumn 1 macierzy N odpowiadaj c zmiennej .
�ł śł
�ł 1 śł
�ł �ł
Rozwi zujemy układ (12):
J.Stadnicki Optymalizacja 14
�ł 1 łł
�ł15śł
ak = B y �! y = B 1ak = B 1x1 = I x1 = x1 = .
�ł śł
�ł śł
1
�ł �ł
B
3� Wyznaczamy kolumn , która ma opu cić baz .
Z (13):
ńł �ł
xBi 24 18 11
�ł
min�ł żł = minńł = min{24 12 11}= 11 bo xB = B 1y
�ł żł
yi 1 1.5 1
ół �ł
ół �ł
x5
B
Zatem baz opuszcza kolumna 5 odpowiadaj ca zmiennej .
1 2 1 0 0
�ł łł
�ł15 1 0 1 0śł
.
�ł śł
�ł 1 0 0 0 1śł
�ł �ł
1 0 1
�ł łł
�ł0

B = 1 1.5śł , obliczamy
4� Nowa macierz bazowa:
�ł śł
�ł0 0 1 śł
�ł �ł
�ł1 0 1 łł
�ł0

B 1 = 1 1.5śł
�ł śł
�ł0 0 1 śł
�ł �ł
1 0 1 1 0 1
�ł łł �ł łł
�ł0 �ł0

B �" B 1 = 1 1.5śł �" 1 1.5śł = I
bo
�ł śł �ł śł
�ł0 0 1 śł �ł0 0 1 śł
�ł �ł �ł �ł
Nowe rozwi zanie bazowe:
1 0 1 24 1�" 24 + ( 1) �"11 13
�ł łł �ł łł �ł łł �ł łł
�ł0 �ł18śł �ł1�"18 + ( 1.5) �"11śł = �ł1.5śł
Ć
Ć
xB = B 1b = 1 1.5śł �" =
�ł śł �ł śł �ł śł �ł śł
�ł0 0 1 śł �ł11śł �ł 1�"11 śł �ł11śł
�ł �ł �ł �ł �ł �ł �ł �ł
Na tym ko czy si I iteracja. Nast pne wykonujemy wg tego samego algorytmu.
Warto ć funkcji celu:
J.Stadnicki Optymalizacja 15
0
�ł łł
�ł śł
0
�ł śł
Q0 = cT x = 05 04 0 0 0 �"= 0
.. �ł24śł
[]
" przed I iteracj :
�ł18śł
�ł śł
�ł
�ł11śł
�ł
11
�ł łł
�ł śł
0
�ł śł
11
QI = cT x = 0.5 0.4 0 0 0 �" =
�ł13śł
[]
" po I iteracji:
2
�ł15śł
.
�ł śł
�ł śł
0
�ł �ł
J.Stadnicki Optymalizacja 16
Zagadnienie transportowe
i=1
Dana jest sieć transportowa
skierowana.
j=1
R: wierzchołki dostawy: j=1,...,m
i=2
j=2
N: wierzchołki odbioru: i=1,...,n
i=3 Ka demu łukowi przyporz dkowany
jest jednostkowy koszt przewozu
j=m
c
.
ji
i=n
Zadanie transportowe:
x
Wyznaczyć macierz wielko ci przewozu , która minimalizuje całkowity koszt
{ }
ji
m n
Q =
transportu ""c x min , przy spełnieniu ogranicze :
ji ji
j =1 i =1
n
x d" a j = 1,..., m
( ) (poda wierzchołków dostawy nie mo e być
"
1�
ji j
i=1
przekroczona)
m
x e" bi (i = 1,..., n)
"
2� (popyt wierzchołków odbioru musi być zaspokojony)
ji
j=1
x e" 0
przy czym: .
ji
Zadanie ma rozwi zanie dopuszczalne
m n
a e" bi j = 1,..., m i = 1,..., n
() (poda wierzchołków dostawy
" "
gdy:
j
j=1 i=1
zaspokaja popyt wierzchołków odbioru).
m n
Przy czym je eli: 1� "a > "b , to jest to zadanie transportowe
j i
j=1 i=1
otwarte,
m n
2� "a = "b , to jest to zadanie transportowe zamkni te.
j i
j=1 i=1
J.Stadnicki Optymalizacja 17
m
"x = bi (i = 1,..., n)
Rozwi zanie jest optymalne gdy: ji (ł czna ilo ć
j =1
transportowanego dobra zaspokaja popyt).
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
k
zwan przepustowo ci .
ji
Przepływ w sieci N to takie przyporz dkowanie ka demu łukowi liczby rzeczywistej
takiej, e:
0 d" x d" k j =1,...,m i =1,..,n
1� (),
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
( j) (l )
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:
x
Znale ć najwi kszy przepływ tzn. wyznaczyć macierz , która maksymalizuje
{ }
ji
m n
Q =
form ""x , przy ograniczeniach:
ji
j =1 i =1
n
x d" a j = 1,..., m
(),
"
1�
ji j
i=1
m
x e" bi (i = 1,..., n)
x e" 0
"
2� przy czym: .
ji
ji
j=1
J.Stadnicki Optymalizacja 18
Algorytm cechowania
Zało enia:
" liczby w nawiasach kwadratowych oznaczaj :
�ł�ł
�łk ji, xji łł �! [ przepustowo ć, przep yw],
" wszystkie warto ci liczbowe s całkowite i nieujemne,
x = 0
" pocz tkowe przepływy wzdłu łuków wynosz .
ji
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.
x < k
A. je li ( j , l ) jest łukiem i (przep yw < przepustowo ci), to nadać
jl jl
�l = min � ,k xjl ,
{}
wierzchołkowi l cech (j , l), gdzie:
j jl
B. je li ( j , l ) jest łukiem to nadać wierzchołkowi l cech (j , - l),
�l = min � , xjl ,
{}
gdzie:
j
3. powtórz krok 2 a do ocechowania odpływu t lub stwierdzenia, e jest to
niemo liwe.
[3,0]
[2,0]
1 35
[1,0]
[5,0]
[1,0]
(-,")
s t
[4,0]
[1,0]
[4,0] [2,0]
4 6
2
J.Stadnicki Optymalizacja 19
1 ocechowanie:
wierz-
j l xjl kjl j xjl < kjl A. l=min{ j , kjl xjl } (j , l )
chołek
B. l=min{ j , xjl } (j ,- l )
1 (s , 5)
1 s 0 5 0 < 5
" min { " , 5 0 }
2 (s , 4)
2 s 0 4 0 < 4
" min { " , 4 0 }
4 (2 , 4)
4 2 0 4 4 0 < 4
min { 4 , 4 0 }
3 (1 , 3)
1 0 3 5 0 < 3 1 <3 �!
min { 5 , 3 0 }
3
(4 , 1)
3 (4 , 1)
4 0 1 4 0 < 1
min { 4 , 1 0 }
5 (3 , 1)
5 3 0 2 1 0 < 2
min { 1 , 2 0 }
6 (4 , 2)
6 4 0 2 4 0 < 2
min { 4 , 2 0 }
t (5 , 1)
5 0 1 1 0 < 1 1 =1 �!
min { 1 , 1 0 }
t
(5 , 1)
t (6 , 1)
6 0 1 2 0 < 1
min { 2, 1 0 }
(s,5)
(4,1) (3,1)
[3,0]
[2,0]
1 3 5
[1,0]
[5,0]
przepływ
[1,0]
(-,")
s (5, 1) t
poprzedni
wierzchołek
[4,0]
[1,0]
[4,0] [2,0]
4 6
2
(4,2)
(s,4) (2,4)
Procedura B zmiana przepływu:
[3,0]
[2,1]
1 35
[1,1]
[5,0]
[1,1]
s t
[4,1]
[1,0]
[4,1] [2,0]
4 6
2
J.Stadnicki Optymalizacja 20
2 ocechowanie:
wierz-
j l xjl kjl j xjl < kjl A. l=min{ j , kjl xjl } (j , l )
chołek
B. l=min{ j , xjl } (j ,- l )
1 (s , 5)
1 s 0 5 0 < 5
" min { " , 5 0 }
2 (s , 3)
2 s 1 4 1 < 4
" min { " , 4 1 }
3 (1 , 3)
3 1 0 3 5 0 < 3
min { 5 , 3 0 }
4 (2 , 3) -1 <3 �!
2 1 4 3 1< 4
min { 3 , 4 1 }
4
(3 , -1)
4 (3 , -1)
3 1 1 1 1 = 1
min { 1 , 1 }
5 (3 , 1)
5 3 1 2 3 1 < 2
min { 3 , 2 1 }
6 (4 , 1)
6 4 0 2 1 0 < 2
min { 1 , 2 0 }
t (5 , -1) -1 =wypływ
5 1 1 1 1 = 1
min { 1 , 1 }
t
z t �!
(6 , 1)
6 t 0 1 1 0 < 1
min { 1, 1 0 }
(6 , 1)
(s,5)
(1,3) (3,1)
[3,0]
[2,1]
1 3 5
[1,1]
[5,0]
[1,1]
(-,")
s (6, 1) t
[4,1]
[1,0]
[4,1] [2,0]
4 6
2
(4,1)
(s,3) (3,-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
[3,1]
[2,1]
1 35
[1,1]
[5,1]
przepływ=
1+1 =2
[1,-1]
[1,1]
s t
[4,1]
[1,1]
[4,1] [2,1]
4 6
2
3 ocechowanie: brak przej cia!
ko cowe rozwi zanie: xs2=xs1=x24=x13=x46=x35=x6t=x5t= 1
warto ć przepływu: f(t) = 1 +1 =2
Pierwotne (prymalne) zadanie programowania liniowego:
Q x = cT x min
x
Znale ć wektor , taki e: ( ) , przy ograniczeniach:
A x d" b
1�
2� x e" 0 x - zmienne prymalne,
Dualne zadanie programowania liniowego:
y P y = yT b max
Znale ć wektor , taki e: ( ) , przy ograniczeniach:
AT y e" c
1�
y e" 0 y - zmienne dualne (sprz one).
2�
Tw. o dualno ci:
Ć
x
1) Je eli jeden z problemów: dualny lub pierwotny ma rozwi zanie optymalne , to
w
i drugi je ma , przy czym warto ci obu zada s takie same
Ć
minQ(x)= max P(w)
.
2) Je eli jeden z problemów nie ma rozwi zania, ze wzgl du na nieograniczon
Q(x) " lub P(y) "
warto ć funkcji celu , 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
Ć
Ć w Q(x)= P(w)
x
dopuszczalnych i jest .
Przykład:
Zadanie pierwotne: Zadanie dualne:
Q x = 2x1 + 4x2 + x3 + x4 max P y = 4 y1 + 3y2 + 3y3 min
( ) ( )
y1 + 2 y2 e" 2
x1 + 3x2 + x4 d" 4
3y1 + y2 + y3 e" 4
2x1 + x2 d" 3
4 y3 e" 1
x2 + 4x3 + x4 d" 3
y1 + y3 e" 1
P = ybT max
Q = cT x min
AT y e" c �! yT A e" cT y e" 0
Ax d" b x e" 0
�łłłT T
�ł
yT B, N = yT B, yT N e" cT = , cN �ł
Ć [ ]
x = xB jest rozwi zaniem
Je eli
�ł�ł �łcB łł
y =
optymalnym to: Przyjmuj c: , (rozwi zanie
xB = B 1b (xN = 0)
optymalne zadania dualnego)
T B = cT
za (9) mamy:
B
T T T
pT = cN cB B 1N d" 0 yT B = T B = cB
T
yT N = T N e" cN
TT
cB B 1 N e" cN

T T T
�ł�ł �łcB �ł
T
�ł B, T N łł e" �ł , cN łł = cT
T
Q = cB xB

Zatem wektor jest dopuszczalny.
Q = P �!
Warto ci obu zada s równe.
T T
P = Tb = cB = cB xB
B 1b
xB
J.Stadnicki Optymalizacja 23
Algorytm prymalno-dualny zadania transportowego
m n
Q(x) =
x
""c x min
Znale ć macierz , tak e: przy ograniczeniach:
{ } ji ji
ji
j =1 i=1
n
x d" a j = 1,.., m
()
"
1�
ji j
i=1
m
x e" 0
"x e" bi (i = 1,..,n)
2� przy czym:
ji
ji
j=1
Warunek (1�) mo na zapisać w postaci:
n

(1�) "x e" a j
ji
i=1
m
2� "x e" bi
ji
j =1
Formułujemy zadanie dualne, zmienne wyst puj ce w (1�) i (2�) zast pimy
n m
u = vi =
uj vi
zmiennymi dualnymi i , takimi e: "x oraz "x
j ji ji
i=1 j =1
m n
P = a + bi max
Nowa funkcja celu: "u "v , przy ograniczeniach:
j j i
j =1 i=1
uj + vi d" c uj,vi e" 0 j =1,...,m i =1,...,n
3� przy czym: () ( )
ji
Algorytm:
u v
1� rozwi zać zadanie dualne dla dowolnych warto ci pocz tkowych i ,
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,
u v
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�.
J.Stadnicki Optymalizacja 24
Przykład:
Przyjmijmy dane liczbowe zadania transportowego:
i =1...4
30
�ł łł
15
�ł łł
3 7 3 4
�łłł
�ł śł
10
�ł5 7 2 6śł , �ł śł
�ł śł
c = cji = a = 30 , b =
{ }
�łśł
�ł śł
15
�ł śł
�łśł
55
�ł śł
�ł8 13 9 3�ł
�ł �ł �ł śł
45
�ł �ł
1� inicjalizacja zmiennych dualnych:
n m
u = vi =
"x , "x
j ji ji
i =1 j =1
vi = min cji , ji
u = 0 x = 0
{ }
pocz tkowo przyjmujemy: ,
j
T T
u = [0 0 0]v = [3 7 2 3]
,
Z 4� �!, e przepływy niezerowe ( xji >0 ) s mo liwe tylko wzdłu tych
c + u vi = 0
kraw dzi, dla których spełniony jest warunek .
ji j
12 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� korzystaj c z algorytmu cechowania, ocechować powstał sieć:
(s11,15)
(s,15
t1
[",0]
(s,15)
[30,0]
s1
[",0]
(s1,0)
[15,0]
t2 [10,0]
[",0]
(s,30)
(s2,10)
[30,0]
s2
s t
(-,")
[15,0]
[",0]
(s2,15)
t3
[55,0]
(s,55)
[45,0]
s3
[",0]
(s3,45)
t4
J.Stadnicki Optymalizacja 25
j
=1..3
Sieć po 1 ocechowaniu:
t1
[",15]
[30,15]
s1
[",0]
[15,15]
[10,10]
t2
[",10]
[30,25]
s2
s t
[15,15]
[",15]
t3
[55,45]
[45,45]
s3
[",45]
t4
m
Otrzymane rozwi zanie nie spełnia wszystkich warunków "x e" bi (wzdłu łuku
ji
j =1
t1t mo na powi kszyć przepływ).
3� zmiana przepływu:
Aby zwi kszyć przepływ trzeba utworzyć nowe łuki mi dzy nie ocechowanymi
wierzchołkami tj. s1 i t1.
J = { 2, 3 }
Zbiór ocechowanych wierzchołków sj : .
I ={1}
Zbiór nie ocechowanych wierzchołków ti : . (dopełnienie zbioru J)
� = min{c + u vi : j " J , i " I}
Niech : ,
ji j
5 + 0 3 = 2
ńł �ł
� = min�ł = 2
tzn.
ół8 + 0 3 = 5żł
�ł
4� zmiana zmiennych dualnych:
u , j " J
ńł vi , i " J
ńł
j
u
�łu + � , j " I vi �łv + � , i " I
Nowym rozwi zaniem dualnym jest: j = ,
=
j
ół i
ół
T T
u = [0 + 2 0 0] = [2 0 0]
czyli oraz
T
v = [3 + 2 7 2 3] = [5 7 2 3]T
Ta zmiana usuwa łuk s1 t2 i tworzy nowy s2t1.
J.Stadnicki Optymalizacja 26
t1
[",15]
[30,15]
s1
[",0]
[15,15]
[10,10]
t2
[",10]
[30,25]
s2
s t
[15,15]
[",15]
t3
[55,45]
[45,45]
s3
[",45]
t4
Dla nowej sieci powtarzamy post powanie od punktu 2�a do chwili spełnienia
m
ogranicze na popyt: "x e" bi .
ji
j =1
" W algorytmie na przemian zmieniamy rozwi zania prymalne i dualne (krok 1�).
" Ocechowuj c wierzchołki sieci d ymy do maksymalnego przepływu rozwi zania
m n
P = a + bi max
dualnego "u "v a tym samym znajdujemy sprz one
j j i
j =1 i=1
m n
Q(x) =
""c x min
rozwi zanie prymalne, które .
ji ji
j =1 i=1
" 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
m
"x e" bi , co oznacza e algorytm jest sko czony.
ji
j =1
" Zgodnie z tw. o dualno ci otrzymane rozwi zania zada prymalnego i dualnego
s optymalne.
J.Stadnicki Optymalizacja 27
Zastosowania:
Zadanie transportowe:
Producenci Rj jednorodnego produktu, z których ka dy ma zdolno ć produkcyjn aj
, zaopatruj Ni odbiorców, z których ka dy zgłasza zapotrzebowanie bi.
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 cji.
Wyznaczyć plan przewozu mi dzy dostawcami a odbiorcami tj. macierz przewozu
{ xji } minimalizuj cy całkowity koszt transportu.
Np.
Odbiorcy
Poda aj
Producenci
N1 N2 N3 N4
R1 50 40 50 20 70
R2 40 80 70 30 50
R3 60 40 70 80 80
40 60 50 50
Popyt bi
40
�ł łł
�ł50 40 50 20łł �ł70łł
�ł60śł
�ł40 80 70 30śł a = �ł50śł
�ł śł
c = {c }= b =
ji
�ł śł �ł śł
50
�ł śł
�ł śł �ł
�ł60 40 70 80�ł �ł80śł �ł50śł
�ł
�ł �ł
0 0 30 40
�ł łł
�ł40 0 0 10śł Q = 8000
Ć Ć
x ={x }=
Rozwi zanie:
ji
�ł śł
�ł 0 60 20 0 śł
�ł �ł
J.Stadnicki Optymalizacja 28
Zadanie transportowo-produkcyjne:
Producenci Rj jednorodnego produktu, z których ka dy ma zdolno ć produkcyjn aj
, zaopatruj Ni odbiorców, z których ka dy zgłasza zapotrzebowanie bi.
Zakłada si , e ł czne zapotrzebowanie przekraczaja ł czne zdolno ci produkcyjne.
Dane s jednostkowe koszty transportu od j-tego producenta do i-tego odbiorcy cji
oraz jednostkowe koszty produkcji j-tego producenta hj.
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.
" Wprowadzimy fikcyjnego odbiorc Nn+1 , który reprezentować b dzie nie
wykorzystane zdolno ci produkcyjne poszczególnych producentów i którego
zapotrzebowanie:
m n
bi+1 = j = 1 m, i = 1 n
"a "b
j i
j=1 i=1
tzn. ł czne zdolno ci produkcyjne ł czne zapotrzebowanie,
" Utworzymy macierz ł cznych kosztów transportu i produkcji:
k = h + c j = 1 m, i = 1 n
ji j ji
k = 0
przy czym
j ,m+1
tzn. e nie wykorzystanym zdolno ciom produkcyjnym odpowiadaj zerowe
koszty.
Np.
Odbiorcy
N1 N2 N3 N4 Odbiorca Poda
Producenci
aj
fikcyjny
N5
R1 50 40 50 20 0 70
R2 40 80 70 30 0 50
R3 60 40 70 80 0 80
40 60 50 80 30
Popyt bi
J.Stadnicki Optymalizacja 29
40
�ł łł
�ł60śł
�ł50 40 50 20 0łł �ł70łł
�ł śł
�ł40 80 70 30 0śł a = �ł50śł
c = {c }= b = 50
�ł śł
ji
�ł śł �ł śł
�ł50śł
�ł śł �ł
�ł60 40 70 80 0�ł �ł80śł
�ł
�ł śł
�ł
�ł
�ł80śł
0 10 50 40 0
�ł łł
�ł40 0 0 10 0 śł
Ć Ć
x ={x }= Q = 143600
Rozwi zanie:
ji
�ł śł
�ł 0 50 0 0 30śł
�ł �ł
Uwaga:
Ostatnia kolumna w macierzy { xji } 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 aj, popyt bi,
koszty transportu cji, koszty produkcji hj.
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 dji (j=i=1...n), znany jest równie przewóz
mi dzy punktami xji wyra ony liczb pełnych rodków transportu (np.
samochodów).
J.Stadnicki Optymalizacja 30
Dla ka dego punktu j mo na okre lić:
n
wj =
"x liczb rodków transportu potrzebn do wywiezienia towaru,
ji
i `"1
n
p =
"x liczb rodków transportu potrzebn do przywiezienia towaru.
j ji
i `"1
n n
p
Dla wszystkich n punktów "w ="
j j
j =1 j =1
lecz dla poszczególnego punktu wj nie musi być równe pj.
Zatem punkty w których wywóz jest wi kszy od przywozu (wj > pj) 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.
LMNOPRS
dji wj
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
S0 500
500 1000 2000 1000 1000 300 0 5800
pj
Dostawcami b d punkty dla których: pj > wj (przywóz > wywozu)
i odwrotnie odbiorcami punkty dla których: wj > pj (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
Poda aj
LMRS
N 10 40 200 100 20
O 100 20 30 150 18
P 150 30 80 70 16
10 20 14 10
Popyt bi
Zadanie rozwi zujemy jak zadanie transportowe.
10 10 0 0
�ł łł
�ł śł
Ć Ć
x ={x }= 0 4 14 0 Q = 2880
Rozwi zanie:
ji
�ł śł
�ł 0 6 0 10śł
�ł �ł
J.Stadnicki Optymalizacja 32
OPTYMALIZACJA NA GRAFACH
Grafem (nieskierowanym) G=( V, E ) nazywamy struktur składaj c si ze
sko czonego n - elementowego zbioru wierzchołków V={v1,...,vn} oraz
sko czonego zbioru m - elementowego zbioru kraw dzi E={e1,...,em} ł 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.
2
1
3
1 3
5
2 4 5
4
6
Graf Digraf
(nieskierowany) (graf skierowany)
Wierzchołki poł czone kraw dzi nazywamy przyległymi (s siednimi).
Ci g kraw dzi (vi, vi ) 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 ( ek1 ,..., ekp ) wyznaczonych przez ci g wierzchołków ( vi1 ,..., vip ) i takich, e
ek1=( vi0 ,..., vi1 ), ... , ekp=( vi(p-1) ,..., vip ).
Oznacza to, e droga prowadzi od vi0 (pocz tku drogi) do vip (ko ca drogi).
Liczb kraw dzi p nazywamy długo ci drogi.
Drog zawieraj c wszystkie kraw dzie grafu nazywamy drog Eulera.
J.Stadnicki Optymalizacja 33
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 ( vi0 = vip) 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 wij e" 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 34
Przykład:
s 1 2 3 4 t
[2]
Inicjalizacja 0
" " " " "
4 3
[2]
Iteracja 1 0 15 9
" " "
[7]
15
0 9
[9]
" " "
[4] Iteracja 2 0 13 11 9
" "
s [3]
[6]
t
13
0 11 9
" "
[15] [5]
Iteracja 3 0 13 11 9 18
"
[21]
1 2
[35]
18
0 13 11 9
"
[16]
Iteracja 4 0 13 48 11 9 18
48
0 13 11 9 18
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.
J.Stadnicki Optymalizacja 35
Problem wyznaczania najkrótszej drogi w grafie mo na sprowadzić do zadania
programowania zero-jedynkowego1 postaci:
Q(x)=
"w xij min
ij
Zminimalizować
(i, j)"E
1 dla i = s
ńł
xij
�ł
""x = �ł 0 dla i `" s,t
ij
Przy ograniczeniach
( j)"E (i)"E
�ł
ół 1 dla i = t
xij "{0, 1}
Przy czym
"x jest sum łuków wychodz cych z wierzchołka,
ij
Poniewa :
( j)"E
"x jest sum łuków wchodz cych do wierzchołka.
ij
(i)"E
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:
4 3
1. 1 2 3 4 1,
2. 1 4 3 2 1,
3. 1 2 4 3 1,
�!
4. 1 4 2 3 1,
5. 1 3 2 4 1,
1 2
6. 1 3 4 2 1.
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.
J.Stadnicki Optymalizacja 36
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! > 1017 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.
W = {wij}
Zdefiniujmy graf za pomoc macierzy wag:
wij= " - oznacza brak łuku mi dzy wierzchołkami,
wij `" wji - 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ł
(wij k)= k
" "wij
a rozwi zanie optymalne pozostanie optymalne.
(i, j)"E (i, j)"E
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 37
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
1 " 3 93 13 33 9
�ł łł
�ł
2 4 " 77 42 21 16śł
�ł śł
�ł śł
3 45 17 " 36 16 28
�ł śł
4
�ł39 90 80 " 56 7 śł
�ł28 46 88 33 " 25śł
5
�ł śł
6 3 88 18 46 92 "
�ł śł
�ł �ł
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)
1 2 3 4 5 6 1 2 3 4 5 6
a od elementów
1 " 0 75 2 30 6
�ł łł
1 " 0 90 10 30 6
�ł łł
kolumn:
�ł
2 0 " 58 30 17 12śł
�ł
�ł śł
2 0 " 73 38 17 12śł (3) : 15,
�ł śł
�ł śł
3 29 1 " 12 0 12
�ł śł
3 29 1 " 20 0 12
�ł śł
(4) : 8,
�ł śł 4 83 58 " 49 0
�ł32 śł
4 83 73 " 49 0
�ł32 śł
�ł śł
5 3 21 48 0 " 0
(15+8=23)
�ł śł
5 3 21 63 8 " 0
�ł śł
�ł śł
6 0 85 [0] 31 89 "
�ł śł
�ł �ł
6 0 85 15 43 89 "
�ł śł
�ł �ł
(LB=58+23=81)
w6,3 = 0 a
"w + "w max
i,3 6, j
Wybieramy jako łuk podziału łuk (6, 3) bo:
(i) ( j)
Jeden z otrzymanych podzbiorów nie b dzie zawierał łuku (6, 3), zatem: w6,3="
J.Stadnicki Optymalizacja 38
Wszystkie
LB=81
rozwi zania
Rozwi zania
Rozwi zania
LB=81
LB=129
z (6, 3)
bez (6, 3)
1 2 4 5 6 1 2 3 4 5 6
1 " 0 2 30 6
�łłł
1 " 0 75 48 = 27 2 30 6
�ł łł
�łśł
�ł
2 0 " 30 17 12
2 0 " 58 48 = 10 30 17 12śł
�łśł
�ł śł
3�ł29 1 12 0 " śł
�ł śł
3 29 1 " 12 0 12
�ł32
�ł
4 83 " 49 0śł 4 83 58 48 = 10 " 49 0 śł
[ ]śł
�ł
�ł32 śł
�łśł
5�ł 3 21 0 " 0
�ł śł
�ł 5 3 21 48 48 = 0 0 " 0
�ł śł
wybieramy łuk (6, 4), zatem: w4,6="
6 0 85 ["] 31 89 "
�ł śł
�ł �ł
Ó! Ó!
od wiersza (4) mo na odj ć 32 od kolumny (3) mo na odj ć 48
�! LB=81+32=113 �! LB= 81+48=129
Rozwi zania
LB=81
z (6, 3)
Rozwi zania z
Rozwi zania z
LB=81
LB=113
(6, 3) i (4, 6)
(6, 3) i bez (4, 6)
1 2 4 5 1 2 4 5 6
1 " 0 2 30
�ł łł 1 " 0 2 30 6
�ł łł
�ł
�ł
2 0 " 30 17śł
2 0 " 30 17 12śł
�ł śł
�ł śł
�ł śł
3 29 1 [12] 0 �ł śł
3 29 1 12 0 "
�ł śł
�ł śł
5 3 21 0 "
4 32 = 0 83 32 = 51 " 49 32 = 17 "
�ł �ł
�ł32 śł
�ł śł
5 3 21 0 " 0
�ł �ł
łuk (3, 4) trzeba odrzucić bo
rozwi zanie zawiera łuki (4, 6) i
(6, 3) �! wierzchołek (4) byłby
odwiedzany dwukrotnie.
Zatem: w3,4="
1 2 4 5
J.Stadnicki Optymalizacja 39
1 " 0 2 30
�ł łł
�ł
2 [0] " 30 17śł Do podziału wybieramy łuk (2, 1) co pozwala na odj ć 17 od
�ł śł
�ł śł
3 29 1 " 0 elementów (2) wiersza i 3 od elementów 1 kolumny.
�ł śł
LB=81+17+3=101
5 3 21 0 "
�ł �ł
Rozwi zania z
LB=81
(6, 3) i (4, 6)
Rozwi zania z
Rozwi zania z
LB=81
LB=101
(6, 3), (4, 6) i (2, 1)
(6, 3) i (4, 6) bez (2, 1)
2 4 5 1 2 4 5
Auk (1, 2) trzeba
1 " 0 2 30
1 [0] 2 30 �ł łł
�ł łł
odrzucić bo
�ł
�ł śł
2 " " 30 17 = 13 17 17 = 0śł
3 1 " 0
rozwi zanie zawiera �ł śł
�ł śł
śł
�ł " 0
5
�ł21 0 " śł łuk (2, 1) i wierzchołek 3 �ł29 3 = 26 1
�ł
�ł śł
(1) byłby odwiedzany
5 3 3 = 0 21 0 "
�ł �ł
dwukrotnie (cykl).
Zatem: w1,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
1 " 2 2 = 0 30 2 = 28 1 " [0] 28
�ł łł �ł łł
LB=84 LB=84
�ł śł �ł śł
3 1 1 = 0 " 0 3 1 " 0
�ł śł �ł śł
�ł śł �ł
5 " 5
�ł21 1 = 20 0 �ł �ł20 0 " śł
�ł
Do podziału wybieramy łuk (1, 4), od elementów
(1) wiersza mo na odj ć 28,
LB=84+28=112
J.Stadnicki Optymalizacja 40
Rozwi zania z
LB=84
(6, 3), (4, 6) i (2, 1)
Rozwi zania z
Rozwi zania z
LB=112
LB=84
(6, 3), (4, 6), (2, 1) i (1,4)
(6, 3), (4, 6) i (2, 1) bez (1, 4)
2 5 2 4 5
1 " " 28 28 = 0
3 " 0 �ł łł
�ł łł
�ł śł
�ł20
3 1 " 0
5 "śł
�ł �ł
�ł śł
�ł śł
5 "
Otrzymana macierz jest 2 stopnia.
�ł20 0 �ł
Ó!
Nie mamy mo liwo ci wyboru łuku do uzupełnienia dotychczasowej drogi
komiwoja era oba pozostałe łuki musz uzupełnić drog komiwoja era.
Ó!
1
Droga komiwoja era: (1, 4, 6, 3, 5, 2, 1)
LB=84+20+104
6 2
Ó!
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),
3
5
(4,6) i (2, 1).
1 2 4 5
4
Powtarzaj c post powanie
1 " 0 2 30
�ł łł
otrzymamy drugie rozwi zanie
�ł śł
2 " " 13 0
�ł śł
optymalne o warto ci LB=104
�ł śł
3 26 1 " 0
zawieraj ce łuki: (6, 3), (4, 6),
�ł śł
(5, 1) i (1, 4) bez (2, 1)
5 0 21 0 "
�ł �ł
1
Drog optymaln komiwoja era mo na uzupełnić
6 2
tylko łukami: (3, 2) i (2, 5).
Zatem znale li my dwa rozwi zania optymalne
zadania.
Uwaga:
3
5
W grafie o 6-ciu wierzchołkach istnieje 5!=120
dróg. Dla wyboru optymalnej drogi wyznaczyli my
13 rozwi za po rednich!
4
J.Stadnicki Optymalizacja 41
PROGRAMOWANIE ZERO-JEDYNKOWE
Zadanie programowania zero-jedynkowego
Q cT x
Znale ć minimum (maksimum):
A�" x b przy czym xi 0 lub xi 1, dla i 1,..,n
przy warunkach:
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):
x1 = A,B,C, x2 = 1,2 x3 = , , ,
w podanej kolejno ci.
x1x2 x3
Utwórzmy wszystkie mo liwe trójkowe poł czenia: .
A B C
A B C A B C
B1, B2
A1, A2 C1, C2
1 2
1 2 1 2
A1 A2 B1 B2 C1 C2
A1 , A1 , A1 , A1

Otrzymany porz dek nazywamy porz dkiem leksykograficznym.
J.Stadnicki Optymalizacja 42
Filtr:
Dodatkowe ograniczenie pozwalaj ce na odrzucenie niektórych wariantów
(rozwi za nieoptymalnych) zbioru z porz dkiem leksykograficznym.
Rozwa my przykład liczbowy:
Q x = 3x1 - 2x2 5x3 max
1) x1 2x2 - x3 2
ńł
�łx 4x2 x3 4
2)
�ł
1
x x2
x1,x2 ,x3 " 0,1
3) 3
1
�ł
�ł
4) 4x2 x3 6

Załó my, e znamy jedno z rozwi za dopuszczalnych zadania np.
T T
[x1,x2 ,x3] = [1,0,0] wtedy Q x = 3
Q x) 3
Je li przyjmiemy, e dla rozwi zania optymalnego , to 3 jest dolnym
Ć
Q x
oszacowaniem optymalnej warto ci ( ) .
Wniosek:
Mo na wprowadzić dodatkowe ograniczenie zwane filtrem:
0 3x1 - 2x2 5x3 3
Przegl d z filtrem:
Ograniczenie Czy zachodzi
x1,x2,x3 Q(x)
(0) (1) (2) (3) (4) (1)...(4) i (0)
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ć:
23� 5= 40 operacji oblicze lewych stron wyra e (0)...(5).
Zastosowanie filtru ograniczyło liczb operacji do 24.
J.Stadnicki Optymalizacja 43
Metoda filtru Balasa
Polega na przegl dzie rozwi za dopuszczalnych z wykorzystaniem ogranicze
filtruj cych.
Rozwa my ten sam przykład liczbowy:
Q x = 3x1 - 2x2 5x3 max
1) x1 2x2 - x3 2
ńł
�łx 4x2 x3 4
2)
�ł
1
x x2
x1,x2 ,x3 " 0,1
3) 3
1
�ł
�ł
4) 4x2 x3 6

xi
Zamieniamy kolejno ć zmiennych tak, aby odpowiadały rosn cej kolejno ci
ci Q x)
współczynników funkcji celu .
T
Poniewa : - 2 3 5 �! x = [x2 ,x1,x3
Istnieje rozwi zanie dopuszczalne:
T T
[x2 ,x1,x3] = [0,0,1] wtedy Q x = 5
Dodatkowe ograniczenie (filtr):
(0 ) - 2x2 3x1 5x3 5
Przegl d z filtrem i uporz dkowanymi zmiennymi:
Ograniczenie Czy zachodzi
x2,x1,x3 Q(x)
(0 ) (1) (2) (3) (4) (1)...(4) i (0 )
0,0,0 0 Nie
0,0,1 5 -1 1 0 1 Tak 5
Q x = 5
Wyznaczono rozwi zanie dopuszczalne, dla którego .
Wł czamy do listy dopuszczalnych wariantów punkt [0,1,0] i kontynuujemy przegl d.
Ograniczenie Czy zachodzi
x2,x1,x3 Q(x)
(0 ) (1) (2) (3) (4) (1)...(4) i (0 )
0,1,0 3 Nie
0,1,1 8 0 2 1 1 Tak 8
J.Stadnicki Optymalizacja 44
Q x = 8
Wyznaczono polepszone rozwi zanie dopuszczalne, dla którego .
Zatem otrzymujemy nowe ograniczenie filtruj ce:
(0 ) - 2x2 3x1 5x3 8
Wł czamy do listy dopuszczalnych wariantów punkt [1,1,0] i kontynuujemy przegl d.
Ograniczenie Czy zachodzi
x2,x1,x3 Q(x)
(0 ) (1) (2) (3) (4) (1)...(4) i (0 )
1,0,0 -2 Nie
1,0,1 3 Nie
1,1,0 1 Nie
1,1,1 6 Nie
Q x)
Dalsze polepszanie warto ci jest niemo liwe; rozwi zaniem optymalnym jest
T
x 0 1 1 Q x = 8
dla którego .
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 45
PROGRAMOWANIE CAAKOWITILICZBOWE
Zadanie programowania całkowitoliczbowego
Q cT x
Znale ć minimum (maksimum):
A�" x b przy czym xi xi 0
przy warunkach: s całkowite oraz
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.
a11x1+a12x2 b1
Q=c2x1+c2x2 max
x2
a21x1+a22x2 b2
x1
0
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 46
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.
p
y 0 y 2
Je li zmienna całkowita jest ograniczona, , to mo e być wyra ona
p
i
y =
xi = 0 lub 1 , i = 0,1,..., p
jako: "2 xi , gdzie: .
i=0
y p 1 xi
Tzn., e zmienna całkowita zostaje zast piona zmiennymi binarnymi .
y = 15 24 �! y = 20 �"1 21 �"1 22 �"1 23 �"1
Np. ,
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 47
Podstawowe odci cie Gomory ego
a11x1+a12x2 b1
Q=c2x1+c2x2 max
x2
a21x1+a22x2 b2
x1
0
Rozpatrzmy zadanie:
1) - x1 x2 1
2) 3x1 x2 4
Q = x1 x2 max
3) x1 , x2 0
4) x1 , x2 ca kowite
x2
4
(2)
W punkcie b d cym rozwi zaniem
(1)
3
zadania warto ci zmiennych
Q(3/4,7/4)=10/4 decyzyjnych nie s całkowite.
2
1
Q
-1 0 1 4
2 3
x1
J.Stadnicki Optymalizacja 48
Sprowad my zdanie do postaci standardowej:
1) - x1 x2 x3 = 1
2) 3x1 x2 x4 = 4
Q = x1 x2 max
3) x1, x2 , x3, x4 , 0
4) x1, x2 , x3, x4 ca kowite
x1 x2
Rozwi zuj c układ wzgl dem i otrzymamy:
3x3 x4
7
3 x3 x4
x2 = - -
x1
, .
4 4 4
4 4 4
Załó my, e współczynniki w równaniach (1), (2) s całkowite.
x1 x2
Wtedy, poniewa i s całkowite oraz prawe strony równa s całkowite,
x3 x4
to i te s całkowite.
Konstruujemy odci cie Gomory ego:
x3 x4
3
+ jest tak e całkowite.
x1
" Poniewa jest całkowite, to
4 4 4
3 x3 x4
x4 jest tak e całkowite, a zatem
x4
" Poniewa jest całkowite, to
4 4 4
3 x3 3x4

równie jest całkowite.
4 4 4
x3 x4 0
" Poniewa i najmniejsz mo liw warto ci poprzedniego wyra enia
jest 1.
x3 3x4 x3 3x4
31
+ e" 1 + e"
4 4 4 4 4 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.
x3 x4 x1 x2
Wyra aj c i poprzez i otrzymamy:
1 3 1
1+ x1 x2 + 4 3x1 x2 e" �! 8x1 4x2 e" 12 �! 2x1 + x2 3
4 4 4
J.Stadnicki Optymalizacja 49
Zadanie przyjmie postać:
(1) - x1 x2 x3 = 1
(2) 3x1 x2 x4 = 4
(3) x1, x2 , x3, x4 , x5 0
Q = x1 x2 max
(4) x1, x2 , x3, x4 , x5 ca kowite
(5) 2x1 x2 x5 = 3
x2
4
(2)
W punkcie b d cym rozwi zaniem
(1)
3
zadania warto ci zmiennych
decyzyjnych nie s całkowite.
Q(2/3,5/3)=7/3
2
(5)
Wniosek:
1
Q
Konstruujemy kolejn płaszczyzn
ci cia.
-1 0 1 4
2 3
x1
x3 x5
2
z(1) x2 = 1 x1 - x3 do (5) 2x1 1 x1 - x3 x5 = 3 x1 = -
3 3 3
2x3 x5
5
z(1) x1 = x2 x3 -1 do (5) 2x2 2x3 - 2 x2 x5 = 3 x2 = - -
3 3 3
x3 x5
2
- x5 e" 1 x3 2x5 e" 1
z(5) x5 = 3 - 2x1 - x2
3 3 3
1 x1
- x2 2 3 - 2x1 - x2 e" 1 1 x1 - x2 6 - 4x1 - 2x2 e" 1 -3x1 - 3x2 e" -6
) )
ostatecznie:
x1 + x2 2
J.Stadnicki Optymalizacja 50
Zadanie przyjmie postać:
1) - x1 x2 x3 = 1
2) 3x1 x2 x4 = 4
3) x1, x2 , x3, x4 , x5, x6 e" 0
Q = x1 x2 max
4) x1, x2 , x3, x4 , x5, x6 ca kowite
5) 2x1 x2 x5 = 3
6) x1 x2 x6 = 2
x2
4
(2)
W punkcie b d cym
3
(5)
(1)
rozwi zaniem zadania warto ci
Q(1,1)=2
zmiennych decyzyjnych s
2
całkowite.
(6)
1
Q
Punkt ten jest rozwi zaniem
zadania.
-1 0 1 4
2 3
x1
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
x " Rn
Je eli wektor zmiennych decyzyjnych , tzn. jego składowe s liczbami a nie
funkcjami, wtedy klasyfikacja problemu optymalizacji zale y od postaci funkcji celu
Q x gi(x)
( ) i funkcji ogranicze :
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
Q(x) = a + bT x + 0,5 xT A x
celu ma postać , gdzie: a stała, b wektor,
gi (x)
A macierz kwadratowa a ograniczenia s funkcjami liniowymi,
d) Problem programowania geometrycznego: wyst puje wówczas, gdy
funkcje celu i ograniczenia s uogólnionymi wielomianami pot gowymi z
L n
jli
f (x) = xia ,
rzeczywistymi wykładnikami pot g ajli: "c "
j jl
l =1 i =1
a111 a a121 a
np. f1(x) = c11x1 x2112 + c12x1 x2123
Zadanie programowania nieliniowego bez ogranicze
Rn
Zbiorem dopuszczalnym jest cała przestrze .
Metody analityczne
Minimalizacja funkcji bez ogranicze
Ć
x Q x
Rn
Punkt jest minimum lokalnym funkcji ( )w przestrzeni , je eli istnieje
Ć
Ć "x "U , Q(x)e" Q(x)
U �" Rn x
takie otwarte otoczenie punktu , e , przy
Ć
Q(x) > Q(x)
czym je eli nierówno ć jest ostra , to jest to cisłe minimum
lokalne.
Ć Q x
x Rn
Punkt jest minimum globalnym funkcji ( )w przestrzeni , je eli
Ć
"x " Rn , Q(x)e" Q(x)
, przy czym je eli nierówno ć jest ostra
Ć
Q(x)> Q(x)
, to jest to cisłe minimum globalne.
J.Stadnicki Optymalizacja - 52 -
Q(x)
Q x
Zało enie: ( )
minimum
globalne
okre lona w przestrzeni
Rn , jest klasy C2 (tzn. jest
ci gła wraz z drug
pochodn ).
minimu
m
x
Q x
Rozwijaj c ( ) w
x0
szereg Taylora w punkcie zachowuj c dwa pierwsze składniki (aproksymacja
liniowa):
Q(x) Q(x0)
Q(x)E" Q(x0)+ "TQ(x0)(x x0), �! = "TQ(x0)
x x0
�ł �ł
"Q(x),"Q(x), ,"Q(x)�ł
"TQ(x0 ) = �ł
Q x
gdzie: ( ),
�ł
"x1 "x2 "xn �ł x=x0 jest gradientem
�ł łł
"TQ(x0) Q x
mo na wykazać, e jest kierunkiem najszybszego wzrostu funkcji ( )
x0
w punkcie .
Je li x x0
Q(x) Q(x0) x x0
= 0 �! "TQ(x0) = 0 �! "TQ(x0)t(x0)= 0
lim lim
x x0 x x0
x x0 x x0
(iloczyn skalarny
wektorów)
gdzie:
t(x0) Q(x) = const
jest jednostkowym wektorem stycznym do warstwicy funkcji w
x0
punkcie .
J.Stadnicki Optymalizacja - 53 -
Q(x)
Wniosek:
x0
Gradient funkcji w punkcie jest
"Q(x0)
ortogonalny do wektora stycznego
do warstwicy funkcji
� x0
Q(x) = const
.
t(x0)
x1
x2
t(x0)
�
x
� x0
x-x0
x1
"Q(x0)
x0
Warunki konieczne i wystarczaj ce istnienia min (max) lokalnego w punkcie :
"Q(x) "Q(x) "Q(x)
gradQ(x) = + + + = 0
(1)
x=x0
"x1 "x2 "xn
2
" Q
> 0 (minimum)
x = x0
" xi " x
j
(i = 1,...,n) ( j = 1,...,n)
(2) 2 dla
" Q
< 0 (maksimum)
x = x0
" xi " x
j
Warunki (2) mo na zapisać w formie symetrycznej kwadratowej macierzy drugich
Q x
pochodnych zwanej hesjanem funkcji ( ):
J.Stadnicki Optymalizacja - 54 -
2 2 2
�ł łł
" Q " Q " Q

�ł
" x2 " x1 " x2 " x1 " xn śł
1
�ł śł
2 2 2
�ł śł
" Q " Q " Q
�ł" x2 " x1 " x2 x2 " xn śł
H(x0) =
"
2
�ł śł

�ł śł
2 2 2
�ł " Q " Q " Q śł
�ł" xn " x1 " xn " x2 xn " xn śł
"
�ł �ł
x = x0
H(x0)
Warunki (2) s spełnione, je li hesjan jest okre lony dodatnio (minimum) lub
xT [H]x
ujemnie (maksimum), tzn. jest wi ksze (mniejsze) od zera.
H(x0)
W przypadku gdy =0 nale y badać wy sze pochodne.
x0
Je eli spełnione s tylko warunki (1) punkt jest tzw. punktem stacjonarnym
(maksimum lub minimum lub punktem siodłowym).
Typy punktów stacjonarnych:
maksimum
50
0
45
-5
40
-10
35
-15
30
-20
f(x,y) 25
f(x,y) -25
20
-30
15
-35
10
-40
5
7.5
-45
0
5
7.5
-50
-7.5 2.5 5
-5
-7.5
0 2.5
-2.5
-5
0
-2.5
y
0
-2.5
x
minimum
-2.5
-5 y
2.5
0
x
-5
5 -7.5 2.5
7.5 5 -7.5
7.5
siodło
60
50
40
30
20
10
0
f(x,y)
-10
-20
-30
-40
-50 7.5
-60
5
-7.5
2.5
-5
0
-2.5
-2.5
y
0
x
-5
2.5
5 -7.5
7.5
J.Stadnicki Optymalizacja - 55 -
Zadanie programowania nieliniowego z ograniczeniami w postaci równo ci
�" R2 :
( )
Rozwa my problem dwuwymiarowy
Q(x1,x2)
Dana jest funkcja celu klasy C2, zbiór dopuszczalny okre lony jest przez
g1(x1,x2) = 0 Q(x1,x2)
ograniczenie równo ciowe . Znajd minimum funkcji celu .
x2 = h(x1)
Z ograniczenia równo ciowego mo na wi c z niego wyliczyć np. .
Q(x1,x2) = Q(x1,h(x1))
,
Q(x1,x2) �! grad(Q) = grad(Q(x1,h(x1))) = 0
ma minimum (warunek
konieczny)
"Q "Q dx2
grad(Q)= 0 �! + = 0
(3.1)
"x1 "x2 dx1
g1(x1,x2) = 0
Podobnie dla ograniczenia
"g1 "g1 dx2
+ = 0
(3.2)
"x1 "x2 dx1
Z układu równa (3.1) (3.2) mo na wyliczyć:
"Q "g1
dx2 "x1 dx2 "x1 "Q "g1
= , = zatem je li `" 0 i `" 0 to
dx1 "Q dx1 "g1 "x2 "x2
"x2 "x2
"Q "g1 "Q "Q
"Q "g1
ńł
+ = 0
�ł
"x1 "x1 "x1 "x2
�ł "x1 "x1
= �! = = �!
�ł
(3.3)
"Q "g1
"Q "g1 "g1 "g1
�ł
+ = 0
�ł
"x2
"x2 "x2 "x1 "x2
ół"x2
Równania (3.3) wyra aj warunki konieczne istnienia minimum funkcji:
L(x1,x2 ,)= Q(x1,x2)+ g1( x1,x2 )
- funkcja Lagrange a,
J.Stadnicki Optymalizacja - 56 -
"L
= g1(x1,x2)= 0

bo , - mno nik Lagrange a,
"
Wniosek:
Q(x1,x2)
Pierwotny dwuwymiarowy problem minimalizacji funkcji z ograniczeniem
g1(x1,x2)= 0
równo ciowym został zast pione trójwymiarowym problemem
L(x1,x2 ,)
minimalizacji zast pczej funkcji 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
Q x
Dana jest funkcja celu ( ) klasy C1. Zbiór dopuszczalny utworzony jest przez
ograniczenia równo ciowe (funkcjonalne).
={x : g (x)= 0; j = 1,...,m; m < n}; �" Rn
(4)
j
m
gdzie: - liczba ogranicze funkcjonalnych,
n - liczba zmiennych decyzyjnych.
g (x)
Funkcje s równie klasy C1.
j
Utwórzmy funkcj :
L(x, )= Q(x)+ 1g1(x)+ g2(x)+ ...+ gm(x)
(5)
2 m
gdzie: = [1 ,..., ]T - wektor mno ników Lagrange a.
2 m
L(x, )
Warunkiem koniecznym istnienia ekstremum lokalnego funkcji , przy
zało eniu e jest ona klasy C1 jest:
" L(x, )
ńł
= 0 i = 1,...,n
�ł
" xi
�ł
�ł" L(x, )
(6)
�ł = 0 j = 1,...,m
"
�ł
j
ół
n + m x
Rozwi zuj c układ (6) równa znajdujemy punkty i , w których zeruje
si gradient a zatem punkty w których mog istnieć lokalne extrema funkcji celu.
J.Stadnicki Optymalizacja - 57 -
Zadanie programowania nieliniowego z ograniczeniami w postaci nierówno ci
Zbiory i funkcje wypukłe
x1,x2 "
Zbiór �" Rn jest wypukły, je eli dla ka dej pary punktów odcinek
ł cz cy te punkty nale y do tego zbioru.
zbiór wypukły
zbiór nie
x2
x2
kł
x2
x2
x1
x1
x1
x1
f
f
funkcja ci le wypukła
funkcja ci le wkl sła
x1
x2
x1
x1
x1
x2
f
f
funkcja wypukła
funkcja wkl sła
x1
x2 x2
x1
x1 x1
J.Stadnicki Optymalizacja - 58 -
f : Rn R

Funkcja okre lona na zbiorze wypukłym jest wypukła je eli
nadgrafik nad wykresem funkcji jest zbiorem wypukłym.
Własno ci funkcji wypukłej:
"f
x1,x2 " f (x2) f (x1)e" (x2 x1),
1� dla dowolnych
"x1
H[( f (x))]e" 0 x
2� hesjan dla wszystkich ,

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:
g (x)d" 0, j = 1,2,...,m1
j
g (x) = 0, j = m1 +1,m1 + 2,...,m okre la zbiór wypukły wtedy i tylko wtedy gdy:
j
g (x) dla j = 1,2,...,m1
funkcje s funkcjami wypukłymi, a pozostałe funkcje
j
g (x) dla j = m1 + 1,m1 + 2,...,m
s funkcjami liniowymi.
j
Problem, w którym funkcja celu jest wypukła i zbiór dopuszczalny jest wypukły,
nazywamy problemem programowania wypukłego.
�" R2 :
( )
Rozwa my problem dwuwymiarowy
Q(x1,x2)
Dana jest funkcja celu klasy C1, zbiór dopuszczalny okre lony jest przez
g (x1 ,x2 ) d" 0, j = 1,2,3
ograniczenia nierówno ciowe . Znajd minimum funkcji
j
Q(x1,x2)
celu .
J.Stadnicki Optymalizacja - 59 -
Utwórzmy funkcj Lagrange a:
3
L(x, )= Q(x)+ 1g1(x)+ g2(x)+ g3(x)= Q(x)+
" g (x)
2 3 j j
j =1
Q(x) = const
Ć
Ć
x2 Q(x) = const Q(x) = const
Ć
x2
x2
g1(x) = 0
x
Ć
g1(x) = 0
x g1(x) = 0
Ć
x
Ć
Ś
Ś
Ś
g2(x) = 0
g2(x) = 0
g2(x) = 0
g3(x) = 0 g3(x) = 0
g3(x) = 0
x1
x1 x1
c)
a)
b)
Q x
x
a) ( ) ma minimum w punkcie le cym wewn trz ,
Ć
"Q
grad(Q) = 0 �! = 0
g (x) < 0, j = 1,2,3
Ć
oraz
x = x x = x
Ć Ć
j
"x
j
3
"g
"L "Q
j
(6.1) = + = 0 je li j = 0, j = 1,2,3
x = x x = x "
Ć Ć j x = x
Ć
"x "x "x
j j j =1 j
g (x) d" 0 g (x) = 0
Ć x Ć
Warunek jest aktywny w punkcie , je eli .
Ć
j j
g (x) d" 0 g (x) < 0
Ć x Ć
Warunek jest nieaktywny w punkcie , je eli .
Ć
j j
g1(x) = 0, g2(x) < 0, g3(x) < 0,
b) Ć Ć Ć
x
Zatem w dostatecznie małym otoczeniu zadanie jest równowa ne problemowi
Ć
optymalizacji z ograniczeniem równo ciowym.
3
"g
"Q "g1 "L "Q
j
Z równa (3.3) = 1 x= x �! = + = 0
Ć x= x x= x j x= x
Ć Ć " Ć
"x1 x= x "x1 Ć "x "x "x
j j j
j=1
je li 1 > 0,2 = 3 = 0
g1(x) = 0, g2(x) = 0, g3(x) < 0,
c) Ć Ć Ć
x
Zatem w dostatecznie małym otoczeniu zadanie jest równowa ne problemowi
Ć
optymalizacji z dwoma ograniczeniami równo ciowymi.
J.Stadnicki Optymalizacja - 60 -
3
"g
"Q "g1 "g2 "L "Q
j
= 1 x = x 2 �! = + = 0
Ć Ć Ć Ć " j x= x
Ć
x = x x= x
"x1 x= x "x1 Ć "x2 x= x "x "x "x
j j j
j =1
je li 1 > 0,2 > 0,3 = 0
Podsumujmy przypadki a), b), c):
j = 1,2,3 j e" 0
Zawsze dla , ponadto:
g (x) < 0
Ć
1� je eli (warunek nieaktywny) to odpowiedni mno nik Lagrange a jest
j
j = 0
równy zero ,
g (x) = 0
Ć
2� je eli (warunek aktywny) to odpowiedni mno nik Lagrange a jest
j
j > 0
dodatni ,
x
Punkt jest rozwi zaniem zadania, gdy spełnia wszystkie ograniczenia:
Ć
�ł �ł
"L
�ł �ł
g (x) d" 0 �! d" 0
Ć
j
Ć
�ł �ł
"j x = x , (6.2)
�ł łł
�ł �ł
"L
�ł �ł
Ć
warunki 1� i 2� oznaczaj : g (x) = 0 �! = 0 (6.3)
Ć
j j j x = x
�ł �ł
"
j
�ł łł
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 - 61 -
ńł�ł "L �ł
�ł�ł �ł x=x = 0 i = 1,...,n
Ć
"xi
�ł łł
�ł
�ł
�ł
"L
�ł�ł �ł
Ć
�ł�ł "j �ł x=x d" 0 �ł
�ł �ł
�ł
�ł�ł łł
�ł
�ł
"L
�ł �ł �ł �ł
�ł �ł= 0�ł j = 1,...,m
j Ć
�ł
�ł �ł
(7)
"j x=x żł
�ł łł �ł
�ł
�ł
�łj e" 0
�ł
�ł
�ł
�ł
�ł
�ł
ół
Warunki (7) nazywane s warunkami Khuna-Tuckera.
J.Stadnicki Optymalizacja - 62 -
KOMPUTEROWE METODY ROZWI ZYWANIA ZADA PROGRAMOWANIA
NIELINIOWEGO
Rz d algorytmu optymalizacji rozumiemy jako stopie pochodnych
minimalizowanej funkcji celu wykorzystywany w algorytmie.
" Algorytmy (metody) rz du zerowego (bezgradientowe) korzystaj tylko z
warto ci funkcji celu.
" Algorytmy (metody) rz du pierwszego (gradientowe) korzystaj z
pochodnych rz du pierwszego funkcji celu.
" Algorytmy (metody) rz du drugiego korzystaj z pochodnych rz du drugiego
(hesjanu) funkcji celu.
x
Kryterium zako czenia oblicze jest najcz ciej badanie zmian wektora oraz
Q(x)
funkcji celu . Je eli zmiany te s mniejsze od przyj tej dokładno ci , to
ko czymy obliczenia.
Algorytm optymalizacji jest zbie ny, je eli istnieje i nale y do zbioru
xi
dopuszczalnego granica kolejnych punktów otrzymanych w jego wyniku:
Ć
i
limx = x ,
i "
i
przy czym je eli jest sko czone, to mówimy o sko czonej zbie no ci
algorytmu.
q e" 1
Je eli algorytm jest zbie ny, to liczb , dla której istnieje sko czona granica
Ć
xi+1 x
rq
= rq , gdzie: jest współczynnikiem zbie no ci,
lim
q
Ć
xi x
i "
nazywamy rz dem zbie no ci algorytmu.
1 to mówimy o zbie no ci liniowej,
ńł
q =
�ł
Je eli
ół2 to mówimy o zbie no ci kwadratowej,
Zadanie programowania nieliniowego bez ogranicze
Q(x) min x " Rn Q(x)
Znajd minimum dla , przy czym jest klasy C1.
J.Stadnicki Optymalizacja - 63 -
Metody rz du zerowego (bezgradientowe) funkcji jednej zmiennej
Metoda złotego podziału
a1 a2
a1 > a2 =
Dla
a2
a a1 , zatem
a1
a1
= 0,5( 5 1)E" 0,618,
a a
a2
= 0,5(3 5)E" 0,382,
a
Krok wst pny:
" Wyznacz przedział, w którym lokalne minimum musi istnieć.
Q(x) xi " x
" Oblicz warto ci funkcji dla kolejnych o stałym odst pie .
xi 1,xi ,xi+1 Q(xi 1)> Q(xi) oraz Q(xi+1)> Q(xi)
Je eli dla kolejnych zachodzi ,
(xi 1,xi +1) Q(x)
to w przedziale musi znajdować si minimum funkcji .
(xi 1,xi +1) jako ,xp).
(xl
" Oznaczmy przedział
Q(x)
Q(x2k)> Q(x1k)
Q(x2k)
Q(x1k)
xl=xlk xp=xpk
x1k=pkt. lewy x2k=pkt. prawy x
Kolejne kroki algorytmu:
k = 1 xlk = xl xk = xp
1� Przyjmij .
p
xk xlk < �
2� Je eli to zako cz algorytm.
p
W przeciwnym przypadku wyznacz punkty wewn trzne:
k k
x1 = xlk + 0,382 (xk xlk) x2 = xlk + 0,618(xk xlk)
pkt. lewy: , pkt. prawy:
p p
i oblicz warto ci funkcji celu w tych punktach.
J.Stadnicki Optymalizacja - 64 -
k k
Q(x1 )> Q(x2)�!
3� Je eli Q(pkt-u lewego) > Q(pkt-u prawego) odrzuć przedział
k
xlk ,x1 ) xlk ,xk ), podstawiaj c:
(tzn. lew cz ć
p
k
xlk = x1 =
k = k +1
pkt. lewy, i wróć do punktu 2�.
k
(x2 ,xk (tzn. praw cz ć
W przeciwnym przypadku odrzuć przedział
p
xlk ,xk ), podstawiaj c: p k pkt. prawy,
xk = x2 =
k = k +1
i wróć do punktu
p
2�.
Metoda Powella (interpolacji kwadratowej)
x1,x2 ,x3
Przez trzy kolejne punkty mo na poprowadzić parabol o równaniu:
~
Q(x)= Q(x1)(x x2)(x x3) (x x1)(x x3) (x x1)(x x2)
+ Q(x2) + Q(x3)
(x1 x2)(x1 x3) (x2 x1)(x2 x3) (x3 x1)(x3 x2)
~
dQ
posiadaj cej ekstremum w punkcie (x = xm)= 0:
dx
2 2 2 2 2 2
Q(x1)(x2 x3)+ Q(x2)(x3 x1 )+ Q(x3)(x1 x2)
xm =
2[Q(x1)(x2 x3)+ Q(x2)(x3 x1)+ Q(x3)(x1 x2)]
Kolejne kroki algorytmu:
k = 0 xk "xk
1� Podstaw , przyjmij punkt startowy i krok ,
xk+1 = xk + "xk Q(xk +1)
2� W punkcie oblicz warto ć .
Q(xk +1)d" Q(xk)
"xk+1 = 2"xk
3� Je eli to podstaw i powróć do kroku 2�
k = k +1
przyjmuj c .
W przeciwnym przypadku
Q(xk +1 + 0.5"xk)
oblicz .
Q(x)
~
Q(x) Otrzymamy trzy
Q(x)
równoodległe punkty
i
xi ,xi+1,xi+2
przez które
mo emy poprowadzić
i+2
xmin
i+1
xm
Ć
Q(x)
parabol .
xk
xk+1 xk+2
2 x
J.Stadnicki Optymalizacja - 65 - x
xk
k
Uwaga:
Q(xk +1)> Q(xk)
Je eli w pierwszej iteracji w kroku 3� to odwracamy kierunek
poszukiwa .
xm x1 = xi , x2 = xi+1, x3 = xi+2 ,
4� Obliczamy warto ć przyjmuj c:
x3 x2 = x2 x1 = "x
xm xi 1 < � xmin E" xm
5� Je eli , to obliczenia ko czymy przyjmuj c.
W przeciwnym przypadku powtarzamy algorytm od punktu 2� zmniejszaj c krok z
xm
xi+1
punktu lub .
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 - 66 -
Metoda siecznych:
xl ,x
Q(x)
Dany jest przedział , w którym funkcja celu ma minimum.
p
Q (x)
P
xm2=xl3
xm1=xl2
Q (xp)
xm0=xl1

xl
xp
x
Q (xl)
L
Kolejne kroki algorytmu:
k = 0
1� Przyjmij i oblicz współrz dn punktu przeci cia odcinka LP z osi x.
Q'(xk ) Q'(xlk) Q'(xk ) Q'(xlk)xk Q'(xk )xlk
p p p p
k
tgą = xm = xk =
p
xk xlk tgą Q'(xlk) Q'(xk )
p p
k
k
Q'(xm) < �
Q'(xm)
2� Oblicz i sprawd czy . Je li tak to zako cz obliczenia.
k k k
Q'(xm)Q'(xk )> 0 xk +1 = xm Q'(xk +1)= Q'(xm)
3� Je eli to podstaw .
p p p
k k
xlk +1 = xm Q'(xlk +1)= Q'(xm)
W przeciwnym przypadku .
k = k +1
Podstaw i powróć do punktu 1�.
J.Stadnicki Optymalizacja - 67 -
Metody rz du drugiego funkcji jednej zmiennej
Metoda Newtona
Q(x)
Wymaga obliczenia drugiej pochodnej funkcji celu , która dodatkowo musi być
Q(x)
ci gła( klasy C2).
Kolejne kroki algorytmu:
k = 0
1� Podstaw .
xk Q(x)
2� W otoczeniu punktu startowego rozwi funkcj celu w szereg Taylora
ograniczaj c si do składnika z drug pochodn :
2
Q(x)E" Q(xk)+ Q'(xk)(x xk)+ 0,5Q"(xk)(x xk)
3� Przyrównuj c pierwsz pochodn otrzymanego wyra enia do zera, wyznacz
punkt, w którym ma ono minimum (punkt startowy do nast pnej iteracji):
Q' (xk)
k k
Q' (x) E" Q' (xk)+ Q" (xk)(xm xk)= 0 �! xm = xk
Q"(xk )
Uwaga:
Q"(xk)> 0
Zatem algorytm jest zbie ny tylko wtedy, gdy
k
xm xk < �
4� Je eli to zako cz obliczenia.
k
xk +1 = xm k = k +1
W przeciwnym przypadku podstaw i powróć do punktu 2�.
Q(x)
x
xm2
xm1
xm0
x0
J.Stadnicki Optymalizacja - 68 -
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:
Q(x)
Funkcja celu jest minimalizowana wzdłu kolejnych kierunków bazy
1, 2 , , n
ortogonalnych (wzajemnie prostopadłych) wersorów współrz dnych
kartezja skich. Wersory w trakcie oblicze pozostaj niezmienne.
Q(x)=const
Q(x)
x2
x21=x1
x21
�2 x0
x11
x1
�i
�1 xk *
Kolejne kroki algorytmu:
k = 0 i = 1 xik = x0
x0
1� Przyjmij punkt startowy , podstaw .
i xk
*
2� W kierunku wersora znajd odległo ć od punktu w jakiej funkcja celu
i
Q(x)
ma minimum.
Zadanie polega wi c na minimalizacji funkcji jednej zmiennej:
Q(xik + i)= Q() min
i mo e być rozwi zane jedn z metod omówionych poprzednio po przyj ciu
�i
warto ci oznaczaj cej wymagan dokładno ć rozwi zania zadania dla
kierunku i.
J.Stadnicki Optymalizacja - 69 -
xik xik 1
k = i *
3� Przyjmij wyznacz punkt le cy w odległo ci od w kierunku i.
i = i +1
Podstaw .
i < n
Je eli powróć do punktu 2�.
k
x0 = xik
i = 0
4� Przyjmij nowy punkt startowy oraz podstaw .
k k 1
x0 x0 > �0 to powróć do punktu 2�.
Je eli
W przeciwnym przypadku zako cz obliczenia.
Uwaga:
Metoda mało efektywna, gdy warstwice funkcji celu s długimi w skimi krzywymi.
Metoda losowego przeszukiwania
x0 {xk}
Losujemy punkt startowy , a nast pnie tworzymy taki ci g punktów takich,
e:
k+1 k
Ć
Q x0 e" Q x1 e" e" Q xk e" e" Q x
( )
( ) ( ) ( ) x = x + k
, przy czym ,
k
gdzie jest pewnym na ogół losowym przyrostem zmiennej decyzyjnej.
jednostkowy wektor losowy
Q(x)=const
(promie sfery)
x2
x2
�
x3
x3
1
0
x1
x2
x1
x0
x1
r
Kolejne kroki algorytmu:
x0
1� Wylosuj punkt startowy , ustal promie sfery r oraz liczb losowa N,
k = 0
podstaw .
xk
2� Z punktu wylosuj N punktów na powierzchni sfery o promieniu r .
J.Stadnicki Optymalizacja - 70 -
Q(xk)< Q(xk 1) xik Ć
3� Je eli , to spo ród wylosowanych punktów wybierz taki xik ,
Ć
Q xik < Q xik dla i = 1,..., n,
( ) ( )
w którym warto ć funkcji celu jest najmniejsza ,
Ć
zast p nim punkt xk = xik i powróć do punktu 2�.
Ć
W przeciwnym przypadku zako cz obliczenia i przyjmij x = xk . W odległo ci
xk
mniejszej od r od 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:
" Rn , dla
Q(x) xk
Kierunkami poprawy funkcji w punkcie nazywamy wektory
0 > 0
których istnieje takie,
Q xk + < Q xk .
"(0,0) () ( )
e dla ka dego , zachodzi
j
i
Kierunki (wektory) i nazywamy sprz onymi wzgl dem kwadratowej
j
iT H = 0 dla i `" j
[ ]
[H]
dodatnio okre lonej macierzy , je eli .
Wniosek:
H = I
[ ] [ ]
Je eli ( I macierz jednostkowa) to otrzymamy kierunki ortogonalne.
Metoda kierunków sprz onych Powella:
Tw.

x0
Je eli startuj c z punktu pocz tkowego w kierunku minimum funkcji
Q(x) xa x1 `" x0
kwadratowej osi gamy w punkcie , a startuj c z innego punktu w

xb Q(xb)< Q(xa)
tym samym kierunku minimum osi gamy w punkcie , to przy
(xa xb) [H]
kierunek jest sprz ony wzgl dem hesjanu .
J.Stadnicki Optymalizacja - 71 -
Dla problemu dwuwymiarowego,
x1
w którym warstwice funkcji celu
x2

[H]= [I]
s kołowe , a kierunki
sprz one s ortogonalne.
Minimum (0,0) osi gamy w
drugim kroku algorytmu!
x0

xa- xb
x1
xb xa
Q(x)=const
x2
x30=x1
11 ^
x
x30-x10
x11
x31=x2
21
21 22
x0
x30
x21
20
20
x20
20 x10 10
10
x1
Kolejne kroki algorytmu:
x0 k = 0
1� Wybierz punkt startowy , podstaw oraz przyjmij n liniowo niezale nych
k

i
wersorów (najcz ciej s to wersory kartezja skiego układu współrz dnych).
Q xk + ik dla kolejnych kierunków bazy
( )
2� Wykonaj minimalizacj funkcji
k

i
gdzie i=n,1,2,...,n-1, przyjmuj c minimum kolejnej minimalizacji jako
po redni punkt startowy nast pnej.
J.Stadnicki Optymalizacja - 72 -
k
xn+1
xk +1
3� Ostatni z otrzymanych punktów przyjmij jako nowy punkt startowy .
xk+1 xk < �
Je eli to zako cz obliczenia.
k k
xn+1 x1
k
n+1 =
4� Wyznacz kierunek sprz ony
k k
xn+1 x1 i wprowad go do bazy, tzn.
k
ik+1 = n+1 .
zamie pierwszy kierunek bazy kierunkiem sprz onym
k k
k
n n+1
xn+1
Wyznacz kolejny punkt na przeci ciu kierunków i .
k = k +1
Podstaw i wróć do punktu 2�.
Metody rz du pierwszego (gradientowe) minimalizacji funkcji wielu zmiennych
Metoda najszybszego spadku:
x2 Q(x)=const
1=-"Q(x0)
Kierunek przeciwny do
x1
gradientu
k
= "Q xk jest
( )
x3
kierunkiem poszukiwa .
^
x2 x
2=-"Q(x2)
x0
x1
0=-"Q(x0)
Kolejne kroki algorytmu:
x0 k = 0
1� Wybierz punkt startowy , podstaw
k
= "Q xk .
( )
"Q(xk)
2� Oblicz gradient i przyjmij kierunek poszukiwa
k
k
Q xk +
( )
xk +1
3� Minimalizuj funkcj w kierunku wyznaczaj c punkt .
"Q(xk)�""Q(xk +1)d" �
4� Je li kryterium zbie no ci jest spełnione to zako cz
obliczenia.
k = k +1
W przeciwnym przypadku podstaw i wróć do punktu 2�.
J.Stadnicki Optymalizacja - 73 -
Metoda gradientu sprz onego:
x2 Q(x)=const
0
�
1

x1
-"Q(x1)
x2
^
x
x0
x1
0=-"Q(x0)
Kolejne kroki algorytmu:
x0 k = 0
1� Wybierz punkt startowy , podstaw
k
"Q(xk) = "Q xk
2� Oblicz gradient i przyjmij kierunek poszukiwa ( ) .
k
k
Q xk +
( )
xk +1
3� Minimalizuj funkcj w kierunku wyznaczaj c punkt .
Okre l nowy (sprz ony) kierunek poszukiwa :
"TQ xk+1 �ł"Q xk+1 "Q xk �ł
( )( ) ( )łł
�ł
k+1
= "Q xk+1 + �k+1 k , gdzie: �k+1 =
( ) 2
"Q xk
( )
"Q(xk +1) < �
4� Je li kryterium zbie no ci jest spełnione to zako cz obliczenia.
k = k +1
W przeciwnym przypadku podstaw i wróć do punktu 2�.
J.Stadnicki Optymalizacja - 74 -
Metody rz du drugiego
Metoda Newtona:
Jest uogólnieniem poznanej metody minimalizacji funkcji jednej zmiennej.
Q(x) xk
Rozwi funkcj w szereg Taylora w otoczeniu punktu ograniczaj c si do
dwóch pierwszych wyrazów:
T

�ł
Q x = Q xk + "TQ xk x xk + x xk �łH xk x xk �ł
( )
( ) ( ) ( )1 () ( )()łł
2
Poniewa w metodzie Newtona stosujemy interpolacj kwadratow , problem
k

Q(x)
minimalizacji funkcji w kierunku mo na rozwi zać w sposób cisły.
x = xk + k , otrzymamy:
Podstawiaj c:
k k
dQ xk + "TQ xk
() ( )
k kT
�łH xk �ł k = 0 �! * = kT
="TQ xk + *
( ) ( )łł
�ł
d �łH xk �ł k

( )łł
�ł
Mo na w ten sposób ustalić kolejne punkty wyznaczane przez algorytm:
"Q xk
( )
k
xk +1 = xk
xk+1 = xk + *k
*
podstawiaj c otrzymamy
�łH xk �ł
( )łł
�ł
Zadanie programowania nieliniowego z ograniczeniami
x "
Q(x) min
Znajd minimum dla , przy czym jest niepustym zbiorem
dopuszczalnym zdefiniowanym za pomoc układu ogranicze nierówno ciowych
g (x) d" 0 hl(x)= 0
i (lub) równo ciowych .
j
J.Stadnicki Optymalizacja - 75 -
Algorytmy (metody) podstawowe
Nie korzystaj z informacji wynikaj cych z przebiegu oblicze .
Zalety:
Wady:
" prostota algorytmu,
" du y nakład pracy , szybko
" niewra liwo ć algorytmu na kształt
rosn cy w miar zwi kszania si
funkcji celu i spójno ć obszaru
wymiaru zadania (liczby
dopuszczalnego,
zmiennych decyzyjnych) oraz
" efektywno ć przy wyst powaniu
liczno ci zbioru dopuszczalnego.
ekstremów lokalnych funkcji celu.
Metoda systematycznego przeszukiwania:
x2
x2g
Ś
n2"x2
Ś
x2d
x1g x1
x1d
n1"x1
Kolejne kroki algorytmu:
1� Szacujemy zakres zmian poszczególnych zmiennych decyzyjnych:
xid d" xi d" xig i = 1, ,n
dla
ni
Dzielimy go na równych cz ci, otrzymuj c siatk o
n
N =
xk , k = 1, ,N
"(n +1) oczkach, w których znajduj si punkty .
i
i=1
k =1
Przyjmujemy .
g (xk )
j = 1, ,m
2� Obliczamy warto ci ogranicze w oczkach siatki.
j
J.Stadnicki Optymalizacja - 76 -
k d" N k = N
3� Sprawdzamy czy ograniczenia s spełnione lub czy . Dla
ko czymy obliczenia.
k = k +1
Je eli nie podstawiamy i wracamy do punktu 2�.
Q(xk)
4� Obliczamy .
ńłk = 1 to Qmin = Q xk , k = k +1
( )
�ł
�ł
Je eli
( ) ( )Ć
�łk `" 1 i Q xk < Qmin to Qmin = Q xk , x = xk , k = k +1
ół
i wracamy do punktu 2�.
Uwaga:
Odległo ci mi dzy oczkami siatki musz być mniejsze od wymaganej dokładno ci
oblicze �.
Metoda poszukiwa losowych (Monte Carlo):
xk
" Dla skrócenia czasu oblicze nie przeszukuje si punktów le cych w
xid d" xik d" xig
oczkach siatki lecz w sposób losowy generuje si ci gi liczb
i = 1, ,n xk
dla , okre laj ce współrz dne punktów .
�
" Liczba losowa zale y od przyj tego prawdopodobie stwa i zało onej
�
dokładno ci otrzymania rozwi zania.
� N �
" Prawdopodobie stwo wylosowania w próbach z dokładno ci punktu
N
� = 1 (1 � )

ze zbioru wynosi: .
� �
" Zatem aby wylosować z prawdopodobie stwem i dokładno ci punkt ze
N
zbioru potrzeba minimum losowa .
log 1 �
( )
log 1 � d" N log 1 � �! N e"
( ) ( )
log 1 �
( )
�
�
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 - 75 -
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:
Q(x) = x min
Zajd minimum: przy spełnieniu ogranicze :
g1(x) = 1 x d" 0
g2(x) = x 2 d" 0
Za przekroczenie obszaru dopuszczalnego nało ymy na funkcj celu kar liczbow
Q*(x)= Q(x)+ P(x)
tzn. utworzymy zast pcz funkcj celu ,
0 dla x " 0 dla x "
ńł ńł
P x = P x =
( ) ( )
�ł �łL dla x " ,
gdzie:
ół" dla x " , w praktyce ół
(idealna funkcja kary) L du a liczba dodatnia.
"
"
L
Ś Ś
L
Q(x) Q*(x)
Q(x) Q(x)
x x
12 1 2
Uwaga:
Q*(x)
Otrzymana zast pcza funkcja celu jest nieci gła, zatem koncepcja nie
nadaje si do praktyki numerycznej.
J.Stadnicki Optymalizacja - 76 -
Metoda zewn trznej funkcji kary:
m
1
2
Pzk (x)= {min[g (x); 0] }
Wprowad my funkcj kary postaci: " ,
j
rk j =1
rk > 0, rk > rk +1, rk k "

0
gdzie: .
2
1
2
Q*(x)= Q(x)+ Pzk (x)= Q(x)+ {min[g (x); 0] }=
Wtedy "
j
rk j =1
1
2
2
= x + {min[(x 1);0] + min[(2 x);0] }
rk
Je eli:
Q*(x)
x "Ś Q*(x)= Q(x)
a)
Q(x) r=0,5
(kara nie jest nakładana),
r=1
Q*(x)
1
2
x <1 Q*(x)= x + (x 1)
b)
rk
(kara jest nakładana),
1
2
Q(x)
x > 2 Q*(x)= x + (2 x)
c)
Ś
rk
(kara jest nakładana).
x
12
g1(x) = 1 x d" 0
W punkcie minimum aktywne jest ograniczenie , zatem zbli aj c
si do minimum od lewej strony mamy:
"Q*(x)= 1 + (x 1) = 0 �! x = 1 rk
2
Ć Ć
,
"x rk 2
Ć Ć Ć Ć
x1(1) = 0,5, x2(0,5) = 0,75, x3(0,01) = 0,995, x"(0) = 1
czyli .
Kolejne kroki algorytmu:
x0 k = 0
1� Wybierz punkt startowy , podstaw .
J.Stadnicki Optymalizacja - 77 -
xk
2� Startuj c z punktu rozwi zujemy zadanie programowania nieliniowego bez
r = rk > 0
ogranicze z zast pcz funkcj celu. Przyjmuj c otrzymamy kolejne
Ć
xk (rk ).
przybli one rozwi zanie zadania
3� Je eli dokładno ć rozwi zania jest dostateczna ko czymy obliczenia.
rk
k = k +1, rk+1 = , gdzie c > 1 i
W przeciwnym przypadku podstaw
c
powróć do punktu 2�.
Uwaga:
Szybko ć zbie no ci algorytmu zale y od:
r0
x0 c
" przyj cia punktu startowego i stałych oraz ,
r0 Q(x0) Pz0(xk)
" zaleca si dobrać tak aby w punkcie startu warto ci i były
zbli one,
c
" przyjmuje si od 4 do 10.
Otrzymane w kolejnych iteracjach rozwi zania po rednie nie nale do zbioru
dopuszczalnego.
Aby to wyeliminować przesuwa si granice obszaru dopuszczalnego na zewn trz
g* (x) = g (x)+ � �
przyjmuj c: , wtedy jest marginesem powi kszaj cym
j j j j
zbiór dopuszczalny.
J.Stadnicki Optymalizacja - 78 -
Metoda wewn trznej funkcji kary:
r=0,25 Q*(x)
r=0,01
Q(x)
Wprowad my funkcj kary postaci:
m
1
Q*(x)
k
Pw (x) = rk
"
g (x),
j =1
j
Q(x)
gdzie:
Ś
rk > 0, rk > rk +1, rk k "

0
x
12
2
1
1 1
�ł
k
Q*(x)= Q(x)+ Pw (x)= Q(x) rk =
x + rk �ł +
�ł �ł
Wtedy: " .
g (x)
�ł1 x x 2 łł
j =1
j
Je eli:
r
Q*(x) E" x
g1(x)
x 1+
a) uaktywnia si ograniczenie , wtedy: ,
1 x
r
Q*(x)E" x
g2(x)
x 2
b) uaktywnia si ograniczenie , wtedy: .
x 2
g1(x) = 1 x d" 0
W punkcie minimum aktywne jest ograniczenie , zatem zbli aj c
si do minimum od prawej strony mamy:
"Q*(x)E" 1 rk
Ć
= 0 �! x = 1 + rk ,
2
"x Ć
(1 x)
Ć Ć Ć Ć
x1(0,25) = 1,5, x2(0,01) = 1,1, x3(0,001) = 1,03, x"(0) = 1.
czyli
Kolejne kroki algorytmu:
x0 "Ś k = 0
1� Wybierz punkt startowy , podstaw .
xk
2� Startuj c z punktu rozwi zujemy zadanie programowania nieliniowego bez
r = rk > 0
ogranicze z zast pcz funkcj celu. Przyjmuj c otrzymamy kolejne
Ć
xk (rk ).
przybli one rozwi zanie zadania
J.Stadnicki Optymalizacja - 79 -
3� Je eli dokładno ć rozwi zania jest dostateczna ko czymy obliczenia.
rk
k = k +1, rk+1 = , gdzie c > 1 i
W przeciwnym przypadku podstaw
c
powróć do punktu 2�.
Uwagi:
" Otrzymane w kolejnych iteracjach rozwi zania po rednie nale do zbioru
dopuszczalnego (punkt startowy musi le eć wewn trz obszaru dopuszczalnego!)
" Dla poprawy efektywno ci numerycznej (du e zmiany zast pczej funkcji celu dla
r 0
powoduj trudno ci w znalezieniu minimum) algorytmu przesuwa si
g*(x)= g (x)+ �
granice obszaru dopuszczalnego do wewn trz przyjmuj c: ,
j j j
�
wtedy jest marginesem pomniejszaj cym zbiór dopuszczalny.
j
" 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.
J.Stadnicki Optymalizacja - 80 -
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:
x "
Znajd wektor , który minimalizuje przyj ty układ p kryteriów składowych
ql (x) min dla l = 1, , p
.
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:
f (x1,x2 )
R2 R2
Niech dana b dzie funkcja o dziedzinie i zakresie ,
a b R2
okre laj ca relacj (a poprzedza b) mi dzy punktami przestrzeni .
Je eli spełnione s warunki:
a b '" a `" b to nie zachodzi b a
1. je li ,
a b '" b c to zachodzi a c
2. je li ,
a `" b to zachodzi a b (" b a
3. je li
to jest to relacja porz dku liniowego.
Np.:
x < y x > y
relacja mniejszo ci, relacja wi kszo ci,
x d" y x e" y
relacja niewi ksze, relacja niemniejsze.
Teoria nie daje odpowiedzi jak w sposób bezpo redni rozwi zać zadanie
programowania wielokryterialnego!
J.Stadnicki Optymalizacja - 81 -
Sprowadzanie problemu do zadania programowania jednokryterialnego
(pseudopolioptymalizacja)
Metoda wa onej funkcji celu:
T
[�1, ,� ]
�l e" 0 `" 0
Niech takie, e oraz b d wagami przypisanymi
p
ql(x)
poszczególnym kryteriom .
Znajd wektor x , który minimalizuje zast pcz funkcj celu:
p
Q* = T q(x)=
x "
"� ql(x) min , przy ograniczeniach .
l
l =1
�l
Wagi dobiera si w dwóch etapach:
1
�l
1. normalizacja wag polegaj ca na przyj ciu takich warto ci liczbowych aby
1
�l ql(x)
iloczyny były liczbami tego samego rz du wielko ci (poszczególne
ql
kryteria mog wyra ać ró ne wielko ci fizyczne ró ni ce si rz dem
wielko ci!),
ql(x) ql(x)
2. okre lenie wa no ci poszczególnych kryteriów udziałów kryteriów
Q*(x) �l2
w kryterium zbiorczym . Dobrane wagi powinny spełniać warunek:
p
2
"� = 1. Doboru wag dokonuje si arbitralnie, cz sto przy udziale zespołu
l
l=1
ekspertów.
Przeniesienie zadania do przestrzeni kryteriów
ql(x)
Formułuj c poszczególne kryteria składowe mo emy ka demu punktowi
ql
x
przyporz dkować liczb b d c warto ci danego kryterium w tym punkcie.
Rn
Oznacza to, e zadanie z przestrzeni zmiennych decyzyjnych przenosimy do
p
P
przestrzeni celów .
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.
J.Stadnicki Optymalizacja - 82 -
p
Przesrze zmiennych decyzyjnych Rn Przestrze celów P
q2(x)
x2
Śp
Ś
[q12(x12, x22), q22(x12, x22)]
[x12, x22]
[x13, x23]
[q13(x13, x23), q23(x13, x23)]
[x11, x21]
[q11(x11, x21), q21(x11, x21)]
x1
q1(x)
Metoda punktu docelowego:
Załó my, e znane jest rozwi zanie idealne w przestrzeni celów, tj. punkt, w
* T
q* =[q1 , ,q* ]
którym poszczególne kryteria składowe maj minimalne warto ci .
p
Punkt ten nazywamy punktem docelowym.
Cz sto jest to punkt idealny niemo liwy do osi gni cia w rzeczywisto ci.
q* " p to zadanie sprowadza si do rozwi zania układu
" Je eli punkt docelowy
Ć
ql (x) = q* x
równa : , którego rozwi zaniem jest punkt optymalny b d cy
l
rozwi zaniem zadania programowania wielokryterialnego.
Uwaga:
Dla problemu nieliniowego rozwi zanie powy szego układu równa mo e być
trudne.
q* " p to zadanie sprowadza si wyznaczenia punktu
" Je eli punkt docelowy
le cego najbli ej w sensie przyj tej normy od punktu docelowego.
J.Stadnicki Optymalizacja - 83 -
q2(x)
Śp
q q*=min
^
q - punkt optymalny
q1(x)
q*- punkt docelowy
Rozwi zanie zadania programowania wielokryterialnego sprowadza si do
q " p �! x "
d(q q*) min
minimalizacji metryki przy ograniczeniach .
Stosowane metryki:
1
p
r
�ł �łr
�ł
d(q q*)=
" metryka Minkowskiego: "� ql q* �ł ,
l l
�ł �ł
l =1
�ł łł
�l
gdzie waga kryterium składowego (wyznaczona wg poprzednio omówionych
zasad),
p
2
d(q q*)= (ql l
" metryka Euklidesa: (dla r = 2 ) "� q*) ,
l
l =1
q q* ,
wyra a geometryczn długo ć wektora
p
d(q q*)=
r = 1
" metryka prostok tna: (dla ) "� ql q* ,
l l
l =1
p
�l
d(q q*)= ql q* .
" metryka geometryczna: "
l
l =1
J.Stadnicki Optymalizacja - 84 -
Rozwi zania Pareto-optymalne:
x* " x "
Rozwi zanie nazywamy niezdominowanym, je eli nie istnieje
ql (x)< ql(x*)
takie, e .
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.
W zadaniu minimalizacji
zbiór kompromisów to
q2(x)
(+) poprawa kryterium
Śq
fragment brzegu zbioru
(-) pogorszenie kryterium
q (zbioru
(+)
zbiór
dopuszczalnego
(+)
kompromisów
przekształconego do
(-)
(+)
przestrzeni celów) nie
(+)
zasłoni ty od strony
(-)
" przez inna cz ć
q
q1(x)
zbioru .
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
p
q2(x) Q* = T q(x)=
"� ql(x) min
l
l =1
Śq
mo emy potraktować jak
A
równanie parametryczne z
B
Q*
parametrem .
Q*(x)
Zmieniaj c warto ć parametru
C
znajdujemy punkt wspólny
^
x
q
funkcji i zbioru .
D
q1(x)
�1 �2
Dla problemu dwuwymiarowego wagi i okre laj nachylenie prostej
Q*(x1,x2)= �1x1 + �2x2
.
Wada:
Nie mo na osi gn ć punktów le cych w zgł bieniu zbioru kompromisów (np.
punktu C).
Metoda punktu docelowego:
q2(x)
Poszukujemy punktu ze zbioru
Śq
kompromisów, który jest
A
najbli szy w sencie przyj tej
B
normy od punktu docelowego
(rozwi zania idealnego).
C
^
x
q*(x)
D
q1(x)
J.Stadnicki Optymalizacja - 86 -

Wyszukiwarka

Podobne podstrony:
III wykład 20 10 14 NAUKA ADM
Egzamin Teoria Wykład 01 (10) 14 (15) v 0 12 63 BETA
wyklad 10 14 12 2010
apka 20 10 14 lol
10 14 91
10 14
10 mechanika budowli wykład 10 rozwiazywanie?lek wieloprzeslowych statycznie niewyzn
Matematyka dyskretna 2004 10 Grafy skierowane
10 (14)
Cenckiewicz S , 2013 10 14 DoRz 38, Tajemnica śmierci współpracownika Wałęsy
2004 10?lipse i Java–program do obliczania sum kontrolnych [Programowanie]
TI 99 10 14 T pl(1)

więcej podobnych podstron