Wykład 1

1. Sformułowanie problemu optymalizacyjnego

\(\(\(
\)\(Z\ książki\ \ Practical\ Optimization\ \(Methods : 
        With\ Mathematica\ Applications\ \(by : M . A . Bhatti\)\), 
    M . Asghar\ Bhatti\)\)\)

Przykład 1.1 (Zagadnienie transportowe)

Przedsiębiorstwo dostarcza towary spożywcze do dużego sklepu spożywczego. Sklep zgłasza zapotrzebowanie na co najmniej 150 (m^3) mrożonek i 130 (m^3) świeżych produktów. Przedsiębiorstwo dysponuje dwoma typami samochodów, z których każdy ma powierzchnią chłodniczą i powierzchnią do przewozu świeżych produktów. Pojemności obu typów samochodów (w (m^3)) i zużycie paliwa (w litrach) na dojazd do sklepu podane są w tabelce:

({{., pow . chłod . , \(pow . świeża\), zużycie}, {Typ I, 15, 25, 300}, {Typ II, 15, 10, 200}})

Ile samochodów należy użyć, aby zapewnić dostawę produktów przy minimalnych kosztach?

Przykład 2.1 (Portfel akcji)

Obserwujemy zyski (średnie zyski) w % z akcji (Subscript[A, 1]), (Subscript[A, 2]),  ... , (Subscript[A, r]) w t okresach czasu. Chcemy skonstruować portfel z tych akcji w taki sposób, aby średni zysk wyniósł co najmniej p % przy minimalizacji ryzyka dużych strat. Rozwiązać to zagadnienie dla przykładu:

({{miesiąc, styc, luty, marz, średnia}, {AKCJE 1, 10, 8, -3, 5}, {AKCJE 2, 6, 8, 4, 6}, {AKCJE 3, 4, 5, 6, 5}, {AKCJE 4, 9, 8, -5, 4}})

Składniki zadania optymalizacyjnego

Aby sformułować zadanie optymalizacyjne należy :
	1) wybrać zmienne, występujące w zadaniu
		w przykładzie 1.1 zmiennymi są: liczba samochodów typu I ((Subscript[x, 1])) i liczba samochodów typu II ((Subscript[x, 2]));
		w przykładzie 2.1 zmiennymi są frakcje akcji w portfelu ((Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, r]))

2) określić funkcję celu, która wyraża wielkość, którą chcemy minimalizować (maksymalizować)
		w przykładzie 1.1 funkcja celu wyraża zużycie paliwa;
		w przykładzie 2.1 funkcja celu opisuje ryzyko dużych strat

3) podać ograniczenia typu nierówności
		w przykładzie 1.1 ograniczeniami  typu nierówności są: warunki określajace minimalne wielkości dostawy mrożonek i świeżych 		produktów i nieujemność liczby samochodów I i II typu;
		w przykładzie 2.1 oprócz nieujemności zmiennych występuje warunek na osiągnięcie zysku co najmniej p  %

4) podać ograniczenia typu równości
		w przykładzie 1.1 takie ograniczenia nie występują
		 w przykładzie 2.1 suma frakcji musi być równa 1 (w portfelu są wyłącznie akcje spośród wymienionych rodzajów)

Obszar, spełniający wszystkie ograniczenia i mieszczący się w dziedzinie funkcji celu nazywamy obszarem dopuszczalnym.

Zapiszemy treść obu  przykładów w postaci zadań optymalizacyjnych.

Przykład 1.1 (c.d.)

Zmienne: (Subscript[x, 1])- liczba samochodów typu I,  (Subscript[x, 2])- liczba samochodów typu II; zmienne powinny przyjmować wartości całkowite;
Funkcja celu: f((Subscript[x, 1]), (Subscript[x, 2])) = 300  (Subscript[x, 1]) + 200  (Subscript[x, 2]), f = min!;
Ograniczenia typu nierówności:    15 (Subscript[x, 1]) + 15  (Subscript[x, 2]) ≥ 
        150, (dostawa mrożonek)
					25 (Subscript[x, 1]) + 10  (Subscript[x, 2]) ≥ 
        130, (dostawa produktów świeżych)
					(Subscript[x, 1]) ≥ 0,  (Subscript[x, 2]) ≥ 0

Przykład 2.1 (c.d.)

Zmienne: (Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, r]) - frakcje akcji w portfelu. Oznaczmy x=((((Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, r])))^T)
Funkcja celu:

W tym przypadku określenie funkcji celu będzie wymagało pewnych rachunków. Zapiszmy dane o zyskach z akcji w postaci macierzy A:

(({{(Subscript[a, 11]), (Subscript[a, 12]), ..., (Subscript[a, 1  t])}, {(Subscript[a, 21]), (Subscript[a, 22]), ..., (Subscript[a, 2  t])}, {..., ..., ..., ...}, {(Subscript[a, r1]), (Subscript[a, r2]), ..., (Subscript[a, rt])}})),

gdzie element (Subscript[a, ij])oznacza zyski z akcji "AKCJA i" w okresie j. Oznaczmy przez m wektor wartości średnich dla akcji za analizowany okres. Łatwo wyrazić m poprzez A: m = (1/t) A((Subscript[𝕀, t])^T) , gdzie (Subscript[𝕀, t]) jest wektorem, składającym się z t jedynek.

Zauważmy, że liczba (Subscript[x, 1]) (Subscript[a, 11]) + (Subscript[x, 2]) 
              (Subscript[a, 21]) +  ...  + (Subscript[x, r]) (Subscript[a, r1]) jest oczekiwanym zyskiem przy zastosowaniu portfela x w pierwszym okresie. Podobnie, liczba (Subscript[x, 1]) (Subscript[a, 12]) + (Subscript[x, 2]) 
              (Subscript[a, 22]) +  ...  + (Subscript[x, r]) (Subscript[a, r2]) jest oczekiwanym zyskiem przy zastosowaniu portfela x w drugim okresie. Wektor (A^T) x wyraża więc oczekiwane zyski, jakie uzyskiwano w poprzednich t okresach.Gdyby portfel x był stabilny to oczekiwane zyski byłyby stałe w czasie i były równe (Subscript[𝕀, t]) (m^T) x. Miarą niestabilności porfela może być kwadrat odległości między tymi wektorami, czyli \(TraditionalForm\`\(\(||\)\(\(A\^T\) 
            x - \(𝕀\_t\) \(m\^T\) x\)\( || \^2\)\)\). Po prostych przekształceniach wyrażenie to jest równe t (x^T) C x, gdzie \(TraditionalForm\`C = \(1\/t\) \((A - 
              m𝕀\_t\^T)\) \((A\^T - \(𝕀\_t\) m\^T)\)\) jest macierzą kowariancji dla danych w macierzy A.Funkcję celu, którą będziemy minimalizować, jest więc wyrażenie f(x) = t (x^T) C x.

Ograniczenia typu nierówności:    (m^T) x ≥ p, (warunek na minimalny zysk)
					(Subscript[x, 1]) ≥ 0,  
      (Subscript[x, 2]) ≥ 
        0,   ...  , (Subscript[x, r])≥0 (ograniczenia zakresu)
Ograniczena typu równości:  	(Subscript[x, 1]) + (Subscript[x, 2]) +  ...  + (Subscript[x, r]) = 1 (warunek zupełności portfela)

W naszym konkretnym przykładzie liczbowym mamy:

m=(((({{5, 6, 5, 4}})))^T),       C=(1/3)(({{98, 22, 3, 109}, {22, 8, -2, 26}, {3, -2, 2, -13}, {109, 26, -13, 122}})).

Zadanie optymalizacyjne będzie postaci
				f(x) = 3 (x^T) C x = 
                  98 ((Subscript[x, 1])^2) + 44  (Subscript[x, 1]) (Subscript[x, 2])+6  (Subscript[x, 1]) (Subscript[x, 3])+218  (Subscript[x, 1]) (Subscript[x, 4])+
                                                   +8 
              ((Subscript[x, 2])^2)-4  (Subscript[x, 2]) (Subscript[x, 3])+52  (Subscript[x, 2]) (Subscript[x, 4])+
                                                                    +2 ((Subscript[x, 3])^2)-26  (Subscript[x, 3]) (Subscript[x, 4])+
                                                                                    +122 ((Subscript[x, 4])^2)=min!

przy ograniczeniach:
   				5  (Subscript[x, 1]) + 6  (Subscript[x, 2]) + 5  (Subscript[x, 3]) + 
          4  (Subscript[x, 4]) ≥ 5,
   				(Subscript[x, 1]) ≥ 0, (Subscript[x, 2]) ≥ 0, 
      (Subscript[x, 3]) ≥ 0, (Subscript[x, 4]) ≥ 0, 
   				(Subscript[x, 1]) + (Subscript[x, 2]) + (Subscript[x, 3]) + (Subscript[x, 4]) = 1

Standardowa postać zadania optymalizacyjnego

Aby uniknąć wieloznaczności warunków w różnych zadaniach optymalizacyjnych, stosuje się standardowy zapis zadania optymalizacyjnego

min f(x)
(Subscript[g, i])(x) ≤ 0,  i = 1, 2,  ... , 
      m (ograniczeniaLE)
(Subscript[h, j])(x) = 0, j = 
        1,2,...,p  (ograniczenia EQ) 
(Subscript[x, kL])≤(Subscript[x, k])≤(Subscript[x, kU]), k = 1,2,...,n (zakres)

Uwaga 1:Czasami łączy się nierówności zakresu i ograniczeń LE.
Uwaga 2: Powinno być p < n. 
	    Jeśli  p > n to więcej ograniczeń,  niż zmiennych,
	      jeśli p = n to mamy do czynienia z układem równań n równań z n niewiadomymi i nie jest to istotne zadanie optymalizacyjne
Uwaga 3: Zagadnienie na maksimum f(x) daje się sformułować jako zagadnienie minimum funkcji -f(x):
	   f((Subscript[x, 0])) ≥ f(x) iff  - 
          f((Subscript[x, 0])) ≤  -f(x)   ,
	   Podobnie, nierówności ≥ można zamienić na ≤, mnożąc obie strony  przez -1.
	   Po prawej stronie nierówności/równości  można wprowadzić 0, przenosząc wszystko na lewą stronę.

Graficzne rozwiązanie zadania optymalizacyjnego.

Zadanie, zawierające dwie zmienne można w przybliżeniu rozwiązać graficznie. Rysujemy obszary dopuszczalne oraz poziomice funkcji celu. Staramy się zgadnąć położenie minimum na podstawie obserwacji izolinii.

Przykład 1.1 (c.d.)

Funkcje (Subscript[g, 1])i (Subscript[g, 2]) są liniowymi ograniczeniami typu nierówność. Obszar dopuszczalny jest przekrojem dwóch hiperpłaszczyzn. Na rysunku strona niezacieniona jest hiperpłaszczyzną dopuszczalną.Funkcja celu jest liniowa, więc poziomice są równoległymi prostymi.

Jak widać z rysunku, poziomica, odpowiadająca minimum funkcji celu zawarta jest między prostymi 300  (Subscript[x, 1]) + 200  (Subscript[x, 2]) = 1620 i 300  (Subscript[x, 1]) + 200  (Subscript[x, 2]) = 2500. Poziomica ta musi przechodzić przez wierzchołek kąta, utworzonego przez proste (Subscript[g, 1]) = 15 (Subscript[x, 1]) + 15 (Subscript[x, 2]) = 150 i (Subscript[g, 2]) = 25 (Subscript[x, 1]) + 10 (Subscript[x, 2]) = 130. Ten punkt przecięcia ma współrzędne (całkowite!) (Subscript[x, 1]) = 2 i (Subscript[x, 2]) = 8, co daje rozwiazanie naszego zadania. Wartość minimalna funkcji celu wynosi 2200.◼

2. Optymalizacja bez ograniczeń

O optymalizacji bez ograniczeń mówimy, gdy zbiór ograniczeń (typu LE i EQ) jest pusty. Zadanie optymalizacyjne przybierze prostą postać: f(x) = min! Przypomnimy warunki konieczne i dostateczne istnienia minimum gładkiej funkcji bez ograniczeń.

2.1 Rozkład Taylora

2.1.1 Rozkład Taylora funkcji jednej zmiennej

Twierdzenie. Dla funkcji jednej zmiennej, mającej w otoczeniu punktu \(TraditionalForm\`x\&_\) pochodną rzędu k + 1 zachodzi, dla x z otoczenia \(TraditionalForm\`x\&_\), tożsamość:
\(TraditionalForm\`f(
          x) = \(f(x\&_) + 
              f' \((x\&_)\) \((x - x\&_)\) + \(1\/2\) 
                f'' \((x\&_)\) \((x - x\&_)\)\^2 +  ... \) + \(1\/\(k!\)\) \(\(f\^\((k)\)\)(
              x\&_)\) \((x - x\&_)\)\^k + \(1\/\(\((k + 
                      1)\)!\)\) \(\(f\^\((k + 1)\)\)(
              x\_0)\) \((x - x\&_)\)\^\(k + 1\)\)
Punkt (Subscript[x, 0]) leży między x a \(TraditionalForm\`x\&_\).

Przykład 2.1

Rozkład Taylora jest dobry jedynie w otoczeniu punktu wokół którego rozwijamy szereg. Rozwińmy funkcję f(x) = (x^2) cos(x) w otoczeniu punktu (π/4) z dokładnością do wyrazów 1 i 2 stopnia. Pochodne pierwszego i drugiego stopnia wynoszą:

f'[x] = 2 x Cos[x] - (x^2) Sin[x], f''[x] = 
      2 Cos[x] - (x^2) Cos[x] - 4 x Sin[x]

Rozwinięcie Taylora pierwszego i drugiego stopnia w otoczeniu punktu (π/4) ma postać:

(Subscript[t, 1])[x] = 
      0.436179 + 
        0.6745417220621617` (-0.7853981633974483` + 
              x)
(Subscript[t, 2])[x] = 
      0.436179 + 
        0.6745417220621617` (-0.7853981633974483` + x) - 
        0.621703459591759` (((-0.7853981633974483` + x))^2)

■