14. Optymalizacja

Zrobić trzeba jedno z poniższych (jako minimum)

1. Zaprogramować metodę złotego podziału szukającą minimum funkcji (bez ograniczeń), według opisu jak poniżej dla funkcji postaci

   $$y= f(x) = \begin{cases}(x-5)*(x-10)-60 & x<0\\(x-5)*(x-10) & x\ge 0\end{cases}$$

   (funkcja celowo jest nieciągła). Wygląda jakoś tak:

   

2. Zastosować dostępną w MATLABie aplikację do optymalizacji w trybie

   • problem based

     i/lub

   • solver based

   do znalezienia minimum powyższej funkcji.

   1. Bez ograniczeń
   2. Z ograniczeniami (uwzględniającymi lub nie) punkt o współrzędnej $x=0$.

   Nieciągłość celowo dobrana wrednie…

3. Zapoznać się z funkcją linprog() i użyć jej do rozwiązania opisanego poniżej problemu przewozu towarów…

4. Zamiast używania funkcji linprog prostsze może okazać się użycie aplikacji optymalizacji (w trybie problem based) — wystarczy wpisać funkcję celu i dwa ograniczenia.

5. W tym przypadku można też zażądać rozwiązania całkowitoliczbowego (na „pakę” ładujemy całą paletę towaru (100 kg)).

6. W trybie problem based łatwo będzie zmieniać poszczególne parametry (funkcji celu, na przykład), żeby zobaczyć kiedy przesyłka będzie bardziej zrównoważona…

Metoda złotego podziału

Zakładamy, że odcinkami ciągła funkcja funkcja $f(x)$ określona dla $a \le x \le b$ ma tylko jedno minimum lokalne. Chcemy stworzyć algorytm, który będzie generował ciąg liczb zbieżny do tego minimum.

Wyliczamy wartości funkcji na końcach przedziału oraz w dwu punktach wewnętrznych $x_1$ i $x_2$, porównamy wszystkie (4) wartości funkcji i wybierzemy najmniejszą z nich. Dla skupienia uwagi niech będzie to punkt $x_1$. Mamy trzy przedziały $[a, x_1]$, $[x_1, x_2]$ oraz $[x_2, b]$. Jasne jest, że możemy odrzucić przedział $[x_2, b]$. (Czemu!?)

Dalsza procedura polega na tym, żeby na odcinku $[a, x_2]$ wybrać kolejne dwa wewnętrzne punkty, wyznaczyć w nich wartości funkcji i procedurę powtórzyć…

Warto jednak uwzględnić fakt, że mamy już wyliczone wartości funkcji w trzech punktach: $a$, $x_1$ i $x_2$ – warto więc tak wybrać czwarty punkt aby wykorzystać wszystko to co już mamy.

Kolejny punkt tak dodajemy, aby kolejny (krótszy) odcinek podzielony był w sposób ,,podobny" do wyjściowego. Powinny być spełnione następujące zależności:

$$b - x_2 = x_1 - a, \qquad \displaystyle\frac{x_1 - a}{b - a} = \frac{x_2 - x_1}{x_2 - a}$$

Rozwiązanie jest następujące:

$$\displaystyle\frac{b - x_2}{b - a} = \frac{x_1 - a}{b - a} = \xi, \qquad \xi = \frac{2}{3+\sqrt{5}} \approx 0{,}38$$

W każdej iteracji długość odcinka skraca się $1-\xi \approx 0{,}62$ raza; zatem po $n$ wyliczeniach wartości funkcji, długość wynikowego odcinek wynosi $(1 - \xi)^{n-3}$ początkowej długości. Gdy $n \to \infty$ długość odcinka zmierza do zera co gwarantuje zbieżność metody…

Dla ujednolicenia przyjmiemy $a = x_0$, $b = x_1$; na pierwszym kroku wyliczamy: $$x_2 = x_0 + \xi(x_1 - x_0), \qquad x_3 = x_1 - \xi(x_1 - x_0).$$ Po wyliczeniu wartości funkcji i wybraniu minimum – odrzucony może być punkt z dowolnym indeksem… Może to sprawiać problem.

Jeżeli na pewnym etapie mamy cztery punkty $x_i$, $x_j$, $x_k$, $x_l$ (któreś z nich są końcami przedziału). Załóżmy, że w punkcie $x_i$ funkcja $f$ osiąga minimalną wartość. Odrzucamy ten punkt, który jest najbardziej oddalony od $x_i$ (Czemu takie działanie jest uprawnione? I w jakich warunkach?). Niech będzie to punkt $x_l$. Trzy pozostałe punkty szeregujemy w kolejności: $$x_k < x_i < x_j.$$ Kolejny (wewnętrzny punkt) wyznaczamy ze wzoru: $$x=x_j + x_k - x_i$$ (Czy na pewno spełnia on wymagania złotego podziału?)

Obliczenia kończymy gdy $$|x_j - x_k| < \delta$$

Programowanie liniowe

Programowanie liniowe to szczególny przypadek poszukiwania minimum/maksimum. Funkcja celu jest liniowa, na przykład postaci: $$f(x) = \displaystyle\sum_{i=1}^N f_i x_i$$ gdzie $f$ to wektor współczynników funkcji, a $x$ wektor zmiennych niezależnych.

Ponieważ natura funkcji liniowej jest taka, że jest to funkcja monotoniczna (albo maleje, albo rośnie¹ wraz ze wzrostem wartości składowej $x_i$) — może przyjąć dowolnie wielkie lub dowolnie małe wartości. Minimalizacja/maksymalizacja nie mają sensu.

Zadanie zaczyna mieć sens, gdy wprowadzimy ograniczenia na zmienne. Najprostszy przypadek to ograniczenia w postaci zestawu nierówności: $$Ax\le b$$ ($A$ to jakaś macierz) ale nierówności mogą mieć znacznie bardziej skomplikowaną postać: $$A_\text{eq} x = b_\text{eq}$$ ($A_\text{eq}$ to pewna macierz, a $b_\text{eq}$ — wektor).

W MATLABie problem rozwiązuje funkcja linprog. Zadanie może mieć wiele różnych postaci, najprostsze to $Ax\le b$. Aby problem rozwiązać:

 x = linprog(f,A,b)

Zadanie z ograniczeniami nierównościowymi i równościowymi:

 x = linprog(f,A,b,Aeq,beq)

Aeq to macierz $A_\text{eq}$, a beq to wektor $b_\text{eq}$.

Znaleźć mamy maksimum funkcji $cx$ przy ograniczeniach $Ax=b$ i $x\ge0$. $A$ jest macierzą $m \times n$, rząd macieryz $A = m$, i $b\ge 0$ ($b$, $x$, $c$ to wektory odpowiednich rozmiarów).

Ćwiczenie

Właściciel ciężarówki może przewieźć z miejscowości A do B cukier, mąkę i chipsy. W ciężarówce mieści się towar o objętości co najwyżej 7000 litrów i wadze co najwyżej 5 ton. 100 kg (umówmy się, że jest to paleta) cukru zajmuje objętość 150 litrów, 100 kg mąki 200 litrów, natomiast 100 kg chipsów zajmuje objętość 400 litrów. Zysk od przewozu poszczególnych towarów jest następujący:

• za 100 kg cukru 8 zł,

• za 100 kg mąki 10 zł,

• za 100 kg chipsów 25 zł.

Ile cukru, mąki i chipsów powinien załadować właściciel ciężarówki aby zmaksymalizować swój zysk? Matematyczny model tak postawionego zadania jest następujący: Oznaczmy przez:

• $x_1$ – ilość cukru,

• $x_2$ – ilość mąki,

• $x_3$ – ilość chipsów

(za każdym razem w setkach kilogramów). Skoro ciężarówka może zabrać co najwyżej 5 ton towarów, musi zachodzić nierówność:

$$x_1 + x_2 + x_3 \leq 50$$

Z kolei ograniczenie objętości wyraża się wzorem

$$1{,}50 x_1 + 2{,}00 x_2 + 4{,}00 x_3 \leq 70$$

Zysk właściciela wynosi (funkcja celu):

$$z= 8x_1 + 10 x_2 + 25 x_3$$

$x_1, x_2$ i $x_3$ muszą być oczywiście nieujemne. Po uproszczeniach otrzymamy więc problem programowania matematycznego: