Metoda połowienia
Używamy, by policzyć minimum/maksimum funkcji jednej zmiennej (czyli tylko x). Możemy wykorzystać, gdy mamy możliwość policzenia tylko
niektórych punktów.
Pseudokod:
1. Otrzymujemy wzór f(x)=Ax^3+Bx^2+Cx+D lub podobny, oraz przedział lub (a;b). Mamy ustalone lub wymyślamy sobie pewne EPS
lub ilość iteracji.
2. L = b-a
3. x = (a+b)/2
m
4. x = a + 0.25 * L
1
5. x = b  0.25 * L
2
6. f = min{f(x ), f(x ), f(x )} // jeśli szukamy maksimum to wybieramy max
min 1 2 m
7. jeśli |x |2-x
1 min
8. jeśli f =f(x ) to a=x , b=x i idz
do kroku 2
min m 1 2
9. jeśli f =f(x ) to b=x i idz
do kroku 2
min 1 m
10. jeśli f =f(x ) to a=x i idz
do kroku 2
min 2 m
Przykład: Znajdz
minimum funkcji f(x) = 5x^2  12x  3 w przedziale <0;2>
Iteracja 1
Iteracja 3
a = 0
1
a = 1
3
b = 2
1
b = 1.5 // w poprzednim kroku fmin = f(x2) wiec b bez zmian
3
L = 2
1
L = 0.5
3
x = 1, f(1) = 5  12  3 = -10
m1
x = 1.25 f(1.25) = -10.1875
m
x = 0 + 0.25 * 2 = 0.5 f(0.5) = -7.75
11
x = 1 + 0.25 * 0.5 = 1.125 f(1.125) = -10.1719
13
x = 2  0.25 * 2 = 1.5 f(1.5) = -9.75
21
x = 1.5  0.25* 0.5 = 1.375 f(1.375) = -10.0469
23
Iteracja 2
a = 0.5 // bo w poprzednim kroku fmin = f(xm)
2 3-4 iteracje to zazwyczaj dość, można przyjąć, że minimum tej funkcji w tym przedziale to
b = 1.5 -10.1875 dla x = 1.25
2
L = 1
2
x = 1 f(1) = -10
m2
x = 0.5 + 0.25 * 1 = 0.75 f(0.75) = -9.1875
12
x = 1.5  0.25 * 1 = 1.25 f(1.25) = -10.1875
22
Metoda złotego podziału
Tak samo, jak przy połowieniu. Używamy do funkcji jednej zmiennej, korzystamy gdy nie wszystkie punkty są dostępne.
Pseudokod:
1. Otrzymujemy wzór f(x)=Ax^3 + Bx^2+Cx+D lub podobny, oraz przedział lub (a;b). Mamy ustalone lub wymyślamy sobie pewne EPS
lub ilość iteracji.
2. L = b-a
3. Alfa = b  0.618 * L
4. Beta = a + 0.618 * L
5. jeśli |beta-alfa|6. jeśli f(alfa) < f(beta) to b=betaP, beta=alfaP, alfa = b  0.618*L, L=b-a, przejdz
do kroku nr 5 // w przypadku szukania maksimum
odwracamy znak nierówności, duże P oznacza, że chodzi o wartość tej zmiennej z poprzedniej iteracji, jeśli zmienna nie jest podana to
zostaje jaka była
7. jeśli f(alfa) > f(beta) to a=alfaP, alfa=betaP, beta=a+0.618*L, L=b-a, przejdz
do kroku nr 5 // tutaj też odwracamy jeśli szukamy
maksimum
Przykład: Znajdz
minimum funkcji f(x) = 5x^2  12x  3 w przedziale <0;2>
Iteracja 1
a = 0
b = 2
L = 2
Alfa = 2  0.618 * L = 0.764, f(alfa) = -9.2495
Beta = 1.236, f(beta) = -10.1935
Iteracja 2
a = 0.764
b = 2
L = 1.236
Alfa = 1.236 f(alfa) = -10.1935
Beta = 1.5278 f(beta) = -9.6627
Iteracja 3
a = 0.764
b = 1.5278
L = 0.7638
alfa = 1.0557
beta = 1.236
4 iteracja
a = 1.0557
b = 1.5279
L = 0.4722
Alfa = 1.2361
Beta = 1.3475
3-4 iteracje to zazwyczaj dość, możemy przyjąć, że minimum to 1,2918 (w rzeczywistości 1,2000)
Metoda zmodyfikowanego połowienia
Wykorzystujemy, gdy musimy znalez
ć minimum/maksimum funkcji jednej zmiennej, kiedy to minimum znajduje się na samym krańcu
przedziału. Kolejne iteracje są niejako dla picu, żeby tylko zbliżać się do minimum.
Pseudokod:
1. Otrzymujemy punkt a, który wiemy, że jest minimum.
2. Jeśli punkt ten znajduje się na lewym krańcu przedziału to b = prawy kraniec. Jeśli na prawym to b = lewy kraniec.
3. Jeśli a to lewy kraniec, to d = (b-a)/4, b = b - d. Jeśli a to prawy kraniec, to d = (a-b)/4, b = b + d.
4. Powtarzamy 3 krok, aż uznamy, że dokładność jest zadowalająca.
Przykład:
Znalez
ć maksimum funkcji x^3  2x^2  2.
Wiadomo, że maksimum jest w punkcie x = 3, co widać z wykresu. Więc dążymy do tego punktu:
A = 3 B = -1 D = 1
A = 3 B = 0 D = 0,75
A = 3 B = 0,75 D = 0,5625
A = 3 B = 1,3125 D = 0,421875
Kolejne iteracje wyraz
nie pokazują, że lewy kraniec b zbiega do punktu a.
Metoda algebraiczna
Wykorzystujemy, gdy musimy znalez
ć maksimum lub minimum danej funkcji celu mając podane kilka ograniczeń w postaci nierówności zawarte
w klamrze.
Pseudokod:
1. Otrzymujemy funkcję celu typu F = Ax + By + C oraz ograniczenia w postaci nierówności zawarte w klamrze
2. Przekształcamy ograniczenia tak, aby każdy wyraz wolny (czyli liczba nie mająca x ani y przy sobie) był dodatni. Jeśli trzeba przemnażamy
nierówność przez -1.
3. Zamieniamy nierówności na równania, dodając jednocześnie po jednej zmiennej do każdego równania
4. Uwzględniamy dodatkowe zmienne w funkcji celu, dodając je z mnożnikiem 0
5. Rozwiązujemy kolejno układy równań biorąc kolejno 2 zmienne jako 0. Tworzy się w ten sposób pewna liczba kombinacji, gdyż musimy
sprawdzić wszystkie możliwe warianty 2 zmiennych.
6. Powstałe wyniki sprawdzamy, czy spełniają założenia  wszystkie zmienne muszą być nieujemne. Obliczamy dla powstałych liczb
wartość funkcji celu
7. Wybierają największą (w przypadku szukania maksimum) lub najmniejszą (w przypadku szukania minimum) wartość funkcji celu jako
wynik.
Przykład:
Znajdz
maksimum funkcji celu Z = 300x + 200y przy ograniczeniach 2x + 2y <= 10, 3x + 3y <= 24, 2x <= 8.
Wszystkie wyrazy wolne (10, 24, 8) są dodatnie, więc nie trzeba mnożyć niczego przez -1.
Zamieniamy nierówności na równania:
2x + y + a = 10 // a  pierwsza zmienna dodatkowa
3x + 3y + b = 24 // b  druga zmienna dodatkowa
2x + c = 8 // c  trzecia
Nowa funkcja celu: Z = 300x + 200y + 0a + 0b + 0c
Bierzemy kolejne kombinacje 2 zmiennych z 5 i zakładamy, że są one zerami:
x = y = 0
a = 10
b = 24
c = 8
Z = 300*0 + 200*0 + 0*10 + 0*24 + 0*8 = 0 rozwiÄ…zanie dopuszczalne
x = a = 0
y = 10
3y + b = 24, b = -6 rozwiÄ…zanie niedopuszczalne, b jest ujemne
c = 8
x = b = 0
y + a = 10, a = 2
3y = 24, y = 8
2x + c = 8, c = 8
Z = 300*0 + 200*8 + 0*2 + 0*0 + 0*8 = 1600
x = c = 0
y + a = 10
3y + b = 24
0 + 0 = 8 układ sprzeczny, rozwiązanie niedopuszczalne
y = a = 0
2x = 10, x = 5
3x + b = 24, b = 9
2x + c = 8, c = -2 rozwiÄ…zanie niedopuszczalne
y = b = 0 (& ) rozwiÄ…zanie niedopuszczalne
y = c = 0 (& ) Z = 1200
a = b = 0 (& ) x = 2, y = 6, a = 0, b = 0, c = 0, Z = 1800
a = c = 0 (& ) Z = 1600
b = c = 0 (& ) rozwiÄ…zanie niedopuszczalne
Odpowiedz
: Funkcja osiÄ…ga maksimum dla x = 2 i y = 6.
Metoda mnożników Lagrange dla równania
Wykorzystujemy gdy mamy jedno  konkretne ograniczenie (tzn. inne niż x > 0 x >=0 y > 0 y>= 0) w postaci równania.
Pseudokod:
1. Przerabiamy ograniczenie tak, aby po jednej ze stron mieć tylko 0. Przerzucamy na drugą stronę zmienne x i y.
2. Zapisujemy przerobione ograniczenie i ew. inne (x > 0 i y > 0) w jednej klamerce
3. Zapisujemy wzór: L = + ()
4. Liczymy kolejne pochodne cząstkowe z wyrażenia L po x, po y i po lambda.
5. Przyrównujemy otrzymane pochodne do zera i traktujemy jak układ równań. Rozwiązujemy go i otrzymujemy x, y, lambda.
6. Jeśli otrzymujemy kilka wyników to sprawdzamy wartości w otrzymanych punktach i wybieramy najmniejszy/największy.
Przykład:
Znalez
ć minimum funkcji f = x^2 + y^2 przy ograniczeniu x+y=1
Przerzucamy zmienne x i y w ograniczeniu: 1  x  y = 0
Tworzymy funkcje Lagrange: L = x^2 + y^2 + (1  x  y)
Liczymy pochodne czÄ…stkowe:
5Øß5Ø?Ü
( )2
= 5ØeÜ2 - (x2 ) = 2x - 
5Øß5ØeÜ
5Øß5Ø?Ü
( )2
= 5ØfÜ2 - (y2 ) = 2y - 
5Øß5ØfÜ
5Øß5Ø?Ü
= 1 - 5ØeÜ - 5ØfÜ // przepisujemy to co w nawiasie lambda
5Øß
Rozwiązujemy powstały układ równań:
2x   = 0
2y -  = 0
1-x-y = 0
Wynik:
x = y = ½
 = 1
Metoda mnożników Lagrange dla nierówności
Używamy, gdy mamy tylko jedno konkretne ograniczenie w postaci nierówności.
Pseudokod:
1. Przerzucamy zmienne w ograniczeniu na drugą stronę tak, by mieć 0 po jednej ze stron ograniczenia.
2. Zapisujemy x>=0 i y>=0.
3. Wypisujemy wszystkie założenia: pochodne cząstkowe po x i y <= 0, pochodna cząstkowa po lambda >= 0, pochodne cząstkowe
przemnożone odpowiednio przez x, y i lambda = 0.
4. Zapisujemy funkcję Lagrange: L = (x,y,lambda) = wzór z zadania + lambda(ograniczenie)
5. Liczymy pochodne czÄ…stkowe
6. Zapisujemy pochodne cząstkowe pomnożone odp. Przez x, y i lambda = wynik liczenia pochodnej razy x/y/lambda = 0.
7. Znajdujemy wszystkie możliwe rozwiązania niejako zgadując: cały czas podstawiamy sobie 0 za jedna bądz
dwie zmienne i próbujemy
rozwiązać układ. Wypisujemy wszystkie wyniki, które spełniają założenia zadania i założenia pochodnych.
8. Obliczamy wartości w otrzymanych wynikach i wybieramy najmniejszą/największą.
Przykład:
Znajdz
minimum funkcji (x-2)^2 + (2y-1) z ograniczeniem x + y <= 5.
x + y <= 5 Ä…ð 5  x  y >= 0
x >= 0
y >= 0
5Øß5Ø?Ü 5Øß5Ø?Ü 5Øß5Ø?Ü
d" 0 d" 0 e" 0
5Øß5ØeÜ 5Øß5ØfÜ 5Øß
5Øß5Ø?Ü 5Øß5Ø?Ü 5Øß5Ø?Ü
5ØeÜ = 0 5ØfÜ = 0  = 0
5Øß5ØeÜ 5Øß5ØfÜ 5Øß
L(x,y,) = (x-2)^2 + (2y-1) + (5-x-y)
5Øß5Ø?Ü
(( )2)2 ( )2
= 5ØeÜ - 2 - (x2 ) = 5ØeÜ2 - 45ØeÜ + 4 -  = 2x - 4 - 
5Øß5ØeÜ
5Øß5Ø?Ü
( )2 ( )
= 25ØfÜ - 1 -  y2 = 2 - 
5Øß5ØfÜ
5Øß5Ø?Ü
= 5 - 5ØeÜ - 5ØfÜ
5Øß
5Øß5Ø?Ü
( )
5ØeÜ = 5ØeÜ 2x - 4 -  = 0
5Øß5ØeÜ
5Øß5Ø?Ü
( )
5ØfÜ = 5ØfÜ 2 -  = 0
5Øß5ØfÜ
5Øß5Ø?Ü
( )
 =  5 - 5ØeÜ - 5ØfÜ = 0
5Øß
RozwiÄ…zania:
x = 0, y = 0,  = 0 f(0,0) = 4  1 = 3
x = 0, y = 5,  = 2 f(0,5) = 4 + 10  1 = 13
x = 2, y = 0,  = 0 f(2,0) = 0  1 = -1
x = 2, y = 3,  = 2 f(2,3) = 0 + 6  1 = 5
x = 5, y = 0,  = 2 f(5,0) = 9  1 = 8
Odpowiedz: Minimum tej funkcji w tym przedziale to punkt x = 2, y = 0.
Metoda Simpleks (tylko pierwsza tablica)
Używamy by znalez
ć minimum/maksimum funkcji gdy mamy kilka ograniczeń w klamerce.
Pseudokod:
1. Jeśli wyrazy wolne w ograniczeniach są ujemne to przemnażamy to ograniczenie przez -1.
2. Zamieniamy nierówności na równania dodając zmienne pomocnicze.
3. Zapisujemy równania w postaci macierzowej uwzględniając wszystkie zmienne w każdym równaniu.
4. Zapisujemy tablicę simpleksów w odpowiedni sposób, patrz przykład.
Przykład:
Zmaksymalizuj funkcjÄ™ F = 300x + 200y przy ograniczeniach 2x + y <= 10, 3x + 3y <= 24, 2x <= 8
Ograniczenia:
2x + y + a = 10
3x + 3y + b = 24
2x + c = 8
Ograniczenia w postaci macierzowej:
Z = 300x + 200y + 0a + 0b + 0c
2x + y + a + 0b + 0c = 10
3x + 3y + 0a + b + 0c = 24
2x + 0y + 0a + 0b + c = 8
a1 a2 a3 a4 a5
2 1 1 0 0 x1 10
A = 3 3 0 1 0 x2 B = 24
2 0 0 0 1 X = x3 8
x4
x5
Zadania egzaminacyjne
Jak rozwiązać?
Można wykorzystać podane na wykładzie zadanie. Wystarczy ładnie przerobić liczby i dobrać inną otoczkę słowną. Najłatwiej wykorzystać
metodÄ™ graficznÄ…. Rzeczone zadanie to:
Pewien zakład produkuje dwa typy płytek chodnikowych. Oba typy wymagają zużycia jednakowej ilości surowców (piasek,
woda, żwir, cement). Jeden typ jest barwny i do jego produkcji potrzebna jest farba. Wyprodukowanie 1 tony płytek barwnych
wymaga 2h pracy maszyn, 3h pracy ludzkiej i 2l barwnika. Produkcja tony płyt bezbarwnych wymaga 1h pracy maszyn, 3h pracy ludzkiej.
Zysk: płyty barwne 300 zł/t, płyty bezbarwne 200 zł/t. Dysponujemy 10h pracy urządzeń, 24h pracy ludzkiej i 8l barwnika. Ile
wyprodukować płyt i jakich aby osiągnąć maksymalny zysk.
Do pomocy należy wykorzystać program do metody graficznej z Matlaba.
RozwiÄ…zanie:
Wymyśl coś samodzielnie.
Jak rozwiązać?
Główny problem to dotarcie do okolic, gdzie wartości funkcji są różne od wszechobecnego zera. Nie jest jasne, czy można wykorzystać wiedzę z
rysunku, że punkt minimalny znajduje się w okolicy 0,0 (bądz
nim jest). Jeśli tak to można jasno ująć, że przemieszczamy się w okolicę środka
obszaru a następnie korzystamy z jednej z metod optymalizacji dla funkcji dwóch zmiennych. Warto napisać notatkę na początku rozwiązania,
że wiemy o co chodzi tylko nie wiemy jaką wiedzę mamy do dyspozycji (czy np. możemy założyć, że wzór funkcji jest znany czy nie).
Analogicznie słowa minimum, mniejszy itp. Zastępujemy maksimum, większy itp. Jeśli będziemy musieli znalez
ć maksimum funkcji.
RozwiÄ…zanie:
Korzystając z wykresu można szacować punkt minimalny na 0,0. W tym celu aby algorytm poszukujący  nie błądził po obszarach zmiennych
funkcji, gdzie wartości wszędzie wynoszą 0, jest on nakierowywany w stronę punktu 0,0 dopóki wartości są równe 0. Jeśli możemy uznać, że
znamy wzór funkcji lub mamy możliwość obliczenia bądz
oszacowania ostatnich argumentów zmiennych, gdzie funkcja ma wartości mniejsze
niż 0 to w algorytmie można by było założyć dążenie do tych zakresów aniżeli konkretnie do punktu 0,0.
Krok 1. Wybierz punkt startowy S i krok k.
Krok 2. Sprawdz
wartości funkcji w punktach P(x+krok,y) P(x-krok,y) P(x,y+krok) P(x,y-krok) gdzie P to punkt w którym obecnie jest algorytm a x
i y to jego współrzędne.
Krok 3. Jeśli wszystkie wartości wynoszą 0 to wybierz nowy punkt z podanych 4 w poprzednim kroku tak, aby poruszać się w stronę środka
zakresu wartości (czyli w stronę punktu 0,0) i powtórz krok 2.
Krok 4. Jeśli któraś z wartości jest różna od 0 to wybierz punkt o najmniejszej wartości z podanych. Jeśli wszystkie punkty mają wartości większe
bÄ…dz
równe niż punkt w którym obecnie jest algorytm to zakończ a punkt ten uznaj za minimum. W przeciwnym wypadku przejdz
do punktu 2.
Jak rozwiązać?
W pierwszej kolejności należy nawet byle jak narysować sobie wykres tej funkcji żeby widzieć jak ona wygląda oraz obliczyć wartości w
punktach krańcowych (tutaj -1 i 3) nawet jeśli nie należą one do przedziału. Możliwe jest, że funkcja osiągałaby minimum w którymś z nich, ale
jeśli nie należą do przedziału to znalezienie dokładnego minimum jest niemożliwe, można tylko osiągać coraz bliższą dokładność. Ponadto
wtedy klasyczne metody mogą dać złe wyniki:
Klasyczna metoda złotego podziału znajduje LOKALNE minimum a nie minimum z całego przedziału.
Metody złotego podziału używamy, jeśli bez cienia wątpliwości minimum znajduje się gdzieś w środku przedziału, np.:
Jeśli minimum może znajdować się na krańcach przedziału (a na zaliczeniu tak zapewne będzie) to korzystamy ze zmodyfikowanej metody
połowienia. Należy też zaznaczyć, że korzystamy z metod bezgradientowych, ponieważ nie mamy możliwości liczenia pochodnej w każdym
punkcie jeśli mamy dostępne tylko niektóre punkty.
RozwiÄ…zanie:
Wykorzystam zmieniony algorytm połowienia, ponieważ minimum funkcji znajduje się w punkcie -1, który nie należy do przedziału. W związku z
tym kolejne iteracje mogą tylko zwracać liczbę zbliżającą się do -1. Nie można użyć metod bezgradientowych, ponieważ nie mamy możliwości
liczenia pochodnej w każdym punkcie.
Wykres funkcji:
Wiadomo, że wartość minimalną funkcja osiągnęłaby w punkcie -1. Dążymy do niego poprzez kolejne iteracje:
A = -1 B = 3 D = 1
A = -1 B = 2 D = 0,75
A = -1 B = 1,25 D = 0,5625
A= -1 B = 0,6875 D = 0,421875
Widać wyraz
nie, że minimum zbiega do punktu  1.
Jak rozwiązać?
Mamy tylko jedno  konkretne ograniczenie (x+y <= 5), więc stosujemy metodę mnożników Lagrange dla nierówności.
RozwiÄ…zanie:
x + y <= 5, 5  x  y > = 0 // (x-2)^2 + (2y-1)
x >= 0
y >= 0
5Øß5Ø?Ü 5Øß5Ø?Ü 5Øß5Ø?Ü
d" 0 d" 0 e" 0
5Øß5ØeÜ 5Øß5ØfÜ 5Øß
5Øß5Ø?Ü 5Øß5Ø?Ü 5Øß5Ø?Ü
5ØeÜ = 0 5ØfÜ = 0  = 0
5Øß5ØeÜ 5Øß5ØfÜ 5Øß
L(x,y,) = (x-2)^2 + (2y-1) + (5-x-y)
5Øß5Ø?Ü
(( )2)2 ( )2
= 5ØeÜ - 2 - (x2 ) = 5ØeÜ2 - 45ØeÜ + 4 -  = 2x - 4 - 
5Øß5ØeÜ
5Øß5Ø?Ü
( )2 ( )
= 25ØfÜ - 1 -  y2 = 2 - 
5Øß5ØfÜ
5Øß5Ø?Ü
= 5 - 5ØeÜ - 5ØfÜ
5Øß
5Øß5Ø?Ü
( )
5ØeÜ = 5ØeÜ 2x - 4 -  = 0
5Øß5ØeÜ
5Øß5Ø?Ü
( )
5ØfÜ = 5ØfÜ 2 -  = 0
5Øß5ØfÜ
5Øß5Ø?Ü
( )
 =  5 - 5ØeÜ - 5ØfÜ = 0
5Øß
RozwiÄ…zania:
x = 0, y = 0,  = 0 f(0,0) = 4  1 = 3
x = 0, y = 5,  = 2 f(0,5) = 4 + 10  1 = 13
x = 2, y = 0,  = 0 f(2,0) = 0  1 = -1
x = 2, y = 3,  = 2 f(2,3) = 0 + 6  1 = 5
x = 5, y = 0,  = 2 f(5,0) = 9  1 = 8
Odpowiedz: Maksimum tej funkcji w tym przedziale to punkt x = 0, y = 5.
Jak rozwiązać?
Należy zwrócić uwagę na jeden ujemny wyraz wolny. Mnożymy wyrażenie przez -1, reszta idzie wg schematu.
RozwiÄ…zanie:
2x + y + a = 12
5x  3x + b = 15
x  2y  c = 1 // najpierw dodajemy dodatkowÄ… zmiennÄ… a potem przez -1. Dlatego przy c jest minus.
Z = 2x + y + 0a + 0b + 0c
2x + y + a + 0b + 0c = 12
5x  3x + 0a + b + 0c = 15
x  2y + 0a + 0b  c = 1
a1 a2 a3 a4 a5 x1
A = 2 1 1 0 0 x2 12
5 -3 0 1 0 X = x3 B = 15
1 -2 0 0 -1 x4 1
x5