[ Pobierz całość w formacie PDF ]
1. »1 = »2 = »3 = »4 = 0.
Ponieważ warunki (8.30)-(8.33) są spełnione, pozostaje rozwiązać układ równań złożony z (8.28) oraz
(8.29) czyli
8x1 - 6x2 = -25
-6x1 + 10x2 = 40
co daje punkt
4
-
22
x =
85
22
który jednakże nie spełnia warunków Kuhna-Tuckera, gdyż jest sprzeczny np. z (8.36). Daje nam to
jednak informację, gdzie znajduje się minimum funkcji bez ograniczeń. Dlatego kolejne rozpatrywane
przypadki powinny weryfikować istnienie punktu optymalnego na którymś z ograniczeń będącym jak
najbliżej znalezionego minimum bez ograniczeń (jest to rozumowanie heurystyczne, jednakże dla prostych
przypadków sprawdzające się bardzo dobrze).
2. »1 > 0, »2 = 0, »3 > 0, »4 = 0.
Ponownie widać, że równania (8.31) oraz (8.33) są spełnione automatycznie. Pozostaje rozwiązać nastę-
pujący układ równań
8x1 - 6x2 + »1 - »3 = -25
-6x1 + 10x2 + »1 = 40
x1 + x2 - 1 = 0
-x1 = 0
Aatwo otrzymujemy, że x1 = 0. Stąd x2 = 1. Pozostaje rozwiązać
-6 + »1 - »3 = -25
10 + »1 = 40
61
Stąd otrzymujemy następujące rozwiązanie dla tego przypadku
îø ùø îø ùø
x1 0
ïøx2úø ïø úø
1
ïø úø ïø úø
=
ðø»1ûø ðø30ûø
»4 49
które speÅ‚nia warunki Kuhna-Tuckera (»i 0 oraz ograniczenia w tym punkcie sÄ… speÅ‚nione).
Z tego, że funkcja jest wypukła wnioskujemy, że znaleziony punkt jest rozwiązaniem ZPN
Odpowiedz
RozwiÄ…zaniem zadania jest punkt
x =
Æ
1
dla którego funkcja celu przyjmuje wartość
f(x) = -35
Æ
Przykład 8.2.3.
Rozwiązać następujące zagadnienie programowania nieliniowego
1
min f(x) = -x1 + x2 - x3 + x2 - x2 + x2
1 2 3
x"R3 2
przy ograniczeniach:
x1 -2x2 +x3 2
4x1 2x2 4
RozwiÄ…zanie
Zadanie to jest zadaniem minimalizacji w przestrzeni R3, a więc nie można wykonać rysunku pomocniczego.
Należy to zadanie rozwiązać wykorzystując wyłącznie metodę analityczną. Warto również zauważyć, że funkcja
nie jest funkcją wypukłą, toteż konieczne jest znalezienie wszystkich punktów spełniających warunki Kuhna-
Tuckera i wybranie spośród nich tego, dla którego wartość funkcji celu jest najmniejsza.
Zapiszmy funkcjÄ™ Lagrange a dla tego zadania
1
L(x, ») = -x1 + x2 - x3 + x2 - x2 + x2 + »1 (x1 - 2x2 + x3 - 2) + »2 (4x1 + 2x2 - 4)
1 2 3
2
Zapiszmy warunki Kuhna-Tuckera dla zadania
"L
= -1 + x1 + »1 + 4»2 = 0 (8.39)
"x1
"L
= 1 - x2 - 2»1 + 2»2 = 0 (8.40)
"x2
"L
= -1 + x3 + »1 = 0 (8.41)
"x3
»1(x1 - 2x2 + x3 - 2) = 0 (8.42)
»2 (4x1 + 2x2 - 4) = 0 (8.43)
g1(x) = x1 - 2x2 + x3 - 2 0 (8.44)
g2(x) = 4x1 + 2x2 - 4 0 (8.45)
»1, »2 0 (8.46)
Rozpatrujemy kolejne przypadki w celu znalezienia punktów spełniających równania (8.39)-(8.46).
1. »1 = »2 = 0.
Z powyższego założenia równania (8.42) oraz (8.43) są spełnione. Pozostaje rozwiązać układ równań
złożony z (8.39)-(8.41), które przyjmą następującą postać
-1 + x1 = 0
1 - x2 = 0
-1 + x3 = 0
62
co daje punkt xT = 1 -1 0 , który nie spełnia warunków Kuhna-Tuckera, bo jest sprzeczny np z
nierównością (8.44).
2. »1 = 0, »2 > 0.
Tym razem automatycznie spełnione jest równanie (8.42). Dostajemy układ złożony z równań (8.39)-
(8.41) oraz równania (8.43), co daje nam
-1 + x1 + 4»2 = 0
1 - x2 + 2»2 = 0
-1 + x3 = 0
4x1 + 2x2 - 4 = 0
1 4 1
którego 1 spełniający warunki Kuhna-Tuckera.
3 3 6
rozwiÄ…zaniem jest punkt xT »2 =
Uwaga!
Pomimo tego, że znaleziony punkt spełnia warunki Kuhna-Tuckera, nie oznacza to, że jest on
optymalny. Niewypukłość funkcji nie pozwala na zastosowanie warunku dostatecznego i tym samym
nie możemy wnioskować o optymalności znalezionego punktu. Należy obliczyć wartość funkcji celu w
tymże punkcie i porównać ją z wartościami innych punktów (o ile znajdziemy takowe) spełniających
warunki Kuhna-Tuckera.
1
Funkcja celu dla znalezionego punktu przyjmuje wartość f(x) = - .
3
3. »1 > 0, »2 = 0.
Z założenia spełnione jest równanie (8.43). Ponownie dostajemy układ równań wynikający tym razem z
(8.39)-(8.41) oraz (8.42) postaci
-1 + x1 + »1 = 0
1 - x2 - 2»1 = 0
-1 + x3 + »1 = 0
x1 - 2x2 + x3 - 2 = 0
którego rozwiÄ…zaniem jest punkt xT »1 = 0 -1 0 1 również speÅ‚niajÄ…cy warunki Kuhna-
3
Tuckera. Wartość funkcji celu w tym punkcie wynosi f(x) = - .
2
4. »1 > 0, »2 > 0.
Tym razem żadne z równań nie jest automatycznie spełnione z założenia. Dostajemy układ pięciu równań
złożonych z (8.39)-(8.43), który jest następujący
-1 + x1 + »1 + 4»2 = 0
1 - x2 - 2»1 + 2»2 = 0
-1 + x3 + »1 = 0
x1 - 2x2 + x3 - 2 = 0
4x1 + 2x2 - 4 = 0
12 2 6 5 3
RozwiÄ…zaniem powyższego ukÅ‚adu jest punkt xT »1 »2 = - - , który nie
11 11 11 11 22
spełnia warunków Kuhna-Tuckera (nie spełnia warunku (8.46)).
Odpowiedz
RozwiÄ…zaniem zadania jest punkt
îø ùø
ïø-1úø
ïø úø
x =
Æ
ðø ûø
1
dla którego funkcja celu przyjmuje wartość
3
f(x) = -
Æ
2
63
wiczenia 9
Zadanie maksymalnego przepływu i
minimalnego przekroju
Zadanie maksymalnego przepływu polega na znalezieniu jak największego przepływu w sieci reprezentowanej
przez graf. Graf taki może symbolizować różne sieci występujące w praktyce. Każda gałąz ma ograniczony
maksymalny przepływ. Najlepiej zadanie maksymalnego przepływu odnosi się do rozwiązania problemu mak-
symalnego przepływu w sieci rur o różnych przekrojach (czyli o różnym maksymalnym przepływie). Można
również odnosić zadanie maksymalnego przepływu do zadań znalezienia maksymalnej przepustowości samo-
chodów przez sieć komunikacyjną dróg etc.
9.1 Sieć
W obu zadaniach rozpatrywana jest pewna sieć (domyślnie przepływowa) dana w postaci grafu. W rozpa-
trywanych zadaniach Å‚uki tego grafu sÄ… nieskierowane. Typowe oznaczenia stosowane do reprezentacji sieci
zostało pokazane na rysunku 9.1. Każdy z wierzchołków ma swoją etykietę (najczęściej literę), natomiast każ-
(x,f)
S T
Rysunek 9.1: Fragment grafu sieci przepływowej - połączenie dwóch wierzchołków i oznaczenie
da z krawędzi grafu opisana jest dwoma cyframi podawanymi jako para uporządkowana obok tejże krawędzi.
Pierwsza liczba x jest aktualnym przepływem na danej krawędzi, natomiast druga wartość f jest maksymalnym
przepływem w tej krawędzi. Gdy przepływ jest niezerowy, konieczne jest narysowanie kierunku tego przepływu.
Wyróżniamy trzy rodzaje wierzchołków
" Wierzchołki pośrednie - wierzchołki, dla których suma przepływów wchodzących równa jest przepływom
wychodzącym z tego wierzchołka,
" Wierzchołki zródłowe - wierzchołki dla których łączące się z nimi gałęzie są jedynie gałęziami odpływo-
wymi, [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl aikidobyd.xlx.pl
1. »1 = »2 = »3 = »4 = 0.
Ponieważ warunki (8.30)-(8.33) są spełnione, pozostaje rozwiązać układ równań złożony z (8.28) oraz
(8.29) czyli
8x1 - 6x2 = -25
-6x1 + 10x2 = 40
co daje punkt
4
-
22
x =
85
22
który jednakże nie spełnia warunków Kuhna-Tuckera, gdyż jest sprzeczny np. z (8.36). Daje nam to
jednak informację, gdzie znajduje się minimum funkcji bez ograniczeń. Dlatego kolejne rozpatrywane
przypadki powinny weryfikować istnienie punktu optymalnego na którymś z ograniczeń będącym jak
najbliżej znalezionego minimum bez ograniczeń (jest to rozumowanie heurystyczne, jednakże dla prostych
przypadków sprawdzające się bardzo dobrze).
2. »1 > 0, »2 = 0, »3 > 0, »4 = 0.
Ponownie widać, że równania (8.31) oraz (8.33) są spełnione automatycznie. Pozostaje rozwiązać nastę-
pujący układ równań
8x1 - 6x2 + »1 - »3 = -25
-6x1 + 10x2 + »1 = 40
x1 + x2 - 1 = 0
-x1 = 0
Aatwo otrzymujemy, że x1 = 0. Stąd x2 = 1. Pozostaje rozwiązać
-6 + »1 - »3 = -25
10 + »1 = 40
61
Stąd otrzymujemy następujące rozwiązanie dla tego przypadku
îø ùø îø ùø
x1 0
ïøx2úø ïø úø
1
ïø úø ïø úø
=
ðø»1ûø ðø30ûø
»4 49
które speÅ‚nia warunki Kuhna-Tuckera (»i 0 oraz ograniczenia w tym punkcie sÄ… speÅ‚nione).
Z tego, że funkcja jest wypukła wnioskujemy, że znaleziony punkt jest rozwiązaniem ZPN
Odpowiedz
RozwiÄ…zaniem zadania jest punkt
x =
Æ
1
dla którego funkcja celu przyjmuje wartość
f(x) = -35
Æ
Przykład 8.2.3.
Rozwiązać następujące zagadnienie programowania nieliniowego
1
min f(x) = -x1 + x2 - x3 + x2 - x2 + x2
1 2 3
x"R3 2
przy ograniczeniach:
x1 -2x2 +x3 2
4x1 2x2 4
RozwiÄ…zanie
Zadanie to jest zadaniem minimalizacji w przestrzeni R3, a więc nie można wykonać rysunku pomocniczego.
Należy to zadanie rozwiązać wykorzystując wyłącznie metodę analityczną. Warto również zauważyć, że funkcja
nie jest funkcją wypukłą, toteż konieczne jest znalezienie wszystkich punktów spełniających warunki Kuhna-
Tuckera i wybranie spośród nich tego, dla którego wartość funkcji celu jest najmniejsza.
Zapiszmy funkcjÄ™ Lagrange a dla tego zadania
1
L(x, ») = -x1 + x2 - x3 + x2 - x2 + x2 + »1 (x1 - 2x2 + x3 - 2) + »2 (4x1 + 2x2 - 4)
1 2 3
2
Zapiszmy warunki Kuhna-Tuckera dla zadania
"L
= -1 + x1 + »1 + 4»2 = 0 (8.39)
"x1
"L
= 1 - x2 - 2»1 + 2»2 = 0 (8.40)
"x2
"L
= -1 + x3 + »1 = 0 (8.41)
"x3
»1(x1 - 2x2 + x3 - 2) = 0 (8.42)
»2 (4x1 + 2x2 - 4) = 0 (8.43)
g1(x) = x1 - 2x2 + x3 - 2 0 (8.44)
g2(x) = 4x1 + 2x2 - 4 0 (8.45)
»1, »2 0 (8.46)
Rozpatrujemy kolejne przypadki w celu znalezienia punktów spełniających równania (8.39)-(8.46).
1. »1 = »2 = 0.
Z powyższego założenia równania (8.42) oraz (8.43) są spełnione. Pozostaje rozwiązać układ równań
złożony z (8.39)-(8.41), które przyjmą następującą postać
-1 + x1 = 0
1 - x2 = 0
-1 + x3 = 0
62
co daje punkt xT = 1 -1 0 , który nie spełnia warunków Kuhna-Tuckera, bo jest sprzeczny np z
nierównością (8.44).
2. »1 = 0, »2 > 0.
Tym razem automatycznie spełnione jest równanie (8.42). Dostajemy układ złożony z równań (8.39)-
(8.41) oraz równania (8.43), co daje nam
-1 + x1 + 4»2 = 0
1 - x2 + 2»2 = 0
-1 + x3 = 0
4x1 + 2x2 - 4 = 0
1 4 1
którego 1 spełniający warunki Kuhna-Tuckera.
3 3 6
rozwiÄ…zaniem jest punkt xT »2 =
Uwaga!
Pomimo tego, że znaleziony punkt spełnia warunki Kuhna-Tuckera, nie oznacza to, że jest on
optymalny. Niewypukłość funkcji nie pozwala na zastosowanie warunku dostatecznego i tym samym
nie możemy wnioskować o optymalności znalezionego punktu. Należy obliczyć wartość funkcji celu w
tymże punkcie i porównać ją z wartościami innych punktów (o ile znajdziemy takowe) spełniających
warunki Kuhna-Tuckera.
1
Funkcja celu dla znalezionego punktu przyjmuje wartość f(x) = - .
3
3. »1 > 0, »2 = 0.
Z założenia spełnione jest równanie (8.43). Ponownie dostajemy układ równań wynikający tym razem z
(8.39)-(8.41) oraz (8.42) postaci
-1 + x1 + »1 = 0
1 - x2 - 2»1 = 0
-1 + x3 + »1 = 0
x1 - 2x2 + x3 - 2 = 0
którego rozwiÄ…zaniem jest punkt xT »1 = 0 -1 0 1 również speÅ‚niajÄ…cy warunki Kuhna-
3
Tuckera. Wartość funkcji celu w tym punkcie wynosi f(x) = - .
2
4. »1 > 0, »2 > 0.
Tym razem żadne z równań nie jest automatycznie spełnione z założenia. Dostajemy układ pięciu równań
złożonych z (8.39)-(8.43), który jest następujący
-1 + x1 + »1 + 4»2 = 0
1 - x2 - 2»1 + 2»2 = 0
-1 + x3 + »1 = 0
x1 - 2x2 + x3 - 2 = 0
4x1 + 2x2 - 4 = 0
12 2 6 5 3
RozwiÄ…zaniem powyższego ukÅ‚adu jest punkt xT »1 »2 = - - , który nie
11 11 11 11 22
spełnia warunków Kuhna-Tuckera (nie spełnia warunku (8.46)).
Odpowiedz
RozwiÄ…zaniem zadania jest punkt
îø ùø
ïø-1úø
ïø úø
x =
Æ
ðø ûø
1
dla którego funkcja celu przyjmuje wartość
3
f(x) = -
Æ
2
63
wiczenia 9
Zadanie maksymalnego przepływu i
minimalnego przekroju
Zadanie maksymalnego przepływu polega na znalezieniu jak największego przepływu w sieci reprezentowanej
przez graf. Graf taki może symbolizować różne sieci występujące w praktyce. Każda gałąz ma ograniczony
maksymalny przepływ. Najlepiej zadanie maksymalnego przepływu odnosi się do rozwiązania problemu mak-
symalnego przepływu w sieci rur o różnych przekrojach (czyli o różnym maksymalnym przepływie). Można
również odnosić zadanie maksymalnego przepływu do zadań znalezienia maksymalnej przepustowości samo-
chodów przez sieć komunikacyjną dróg etc.
9.1 Sieć
W obu zadaniach rozpatrywana jest pewna sieć (domyślnie przepływowa) dana w postaci grafu. W rozpa-
trywanych zadaniach Å‚uki tego grafu sÄ… nieskierowane. Typowe oznaczenia stosowane do reprezentacji sieci
zostało pokazane na rysunku 9.1. Każdy z wierzchołków ma swoją etykietę (najczęściej literę), natomiast każ-
(x,f)
S T
Rysunek 9.1: Fragment grafu sieci przepływowej - połączenie dwóch wierzchołków i oznaczenie
da z krawędzi grafu opisana jest dwoma cyframi podawanymi jako para uporządkowana obok tejże krawędzi.
Pierwsza liczba x jest aktualnym przepływem na danej krawędzi, natomiast druga wartość f jest maksymalnym
przepływem w tej krawędzi. Gdy przepływ jest niezerowy, konieczne jest narysowanie kierunku tego przepływu.
Wyróżniamy trzy rodzaje wierzchołków
" Wierzchołki pośrednie - wierzchołki, dla których suma przepływów wchodzących równa jest przepływom
wychodzącym z tego wierzchołka,
" Wierzchołki zródłowe - wierzchołki dla których łączące się z nimi gałęzie są jedynie gałęziami odpływo-
wymi, [ Pobierz całość w formacie PDF ]