Programowanie wypukłe i kwadratowe
8 n| optym^’1)' Port^e' akci‘
Ze względu na to, że mamy p2 < 0, w czwartym warunku ograniczającym nie % trzeba wprowadzać zmiennej sztucznej vv2> gdyż zmienną bazową jest y2. Widzimy więc, że pojawienie się w wektorze p współczynnika o wartości niedodatniej pozwala na ograniczenie liczby zmiennych sztucznych typu w.
Rozwiązujemy zadanie zastępcze, wykorzystując algorytm Wolfe’a. Rozwiązanie optymalne zadania zastępczego otrzymujemy w piątej iteracji. Optymalna wartość funkcji celu w zadaniu zastępczym wynosi 0. Odczytujemy rozwiązanie optymalne zadania wyjściowego:
X| =8, x2— 1.
Optymalna wartość funkcji celu jest równa -618.
Rozwiązując zadanie programowania kwadratowego metodą Wolfc’a, możemy wyróżnić następujące kroki:
1. Zapisanie warunków Kuhna-Tuckera.
2. Zapisanie zadania zastępczego.
a) Niech n oznacza liczbę zmiennych decyzyjnych zadania wyjściowego. Jeżeli dla j= 1, ..., n, p <0, to do warunku zadania zastępczego otrzymanego w wyniku różniczkowania funkcji Lagrange’a względem zmiennej x2 dodajemy zmienną sztuczną typu w. Jeżeli mamy pj^O, to zmienną bazową w pierwszym rozwiązaniu dopuszczalnym jest dla tego warunku zmienna yj.
b) Niech m oznacza liczbę warunków ograniczających zadania wyjściowego. Jeżeli dla ;=1, .... m mamy to wtedy do lewej strony
warunku ograniczającego dodajemy zmienną bilansującą, która jest zmienną bazową w pierwszym dopuszczalnym rozwiązaniu bazowym. Jeżeli b, < 0, to od lewej strony /-tego warunku ograniczającego odejmujemy zmienną bilansującą, przekształcając ten warunek do postaci równości; aby uzyskać pierwsze bazowe rozwiązanie dopuszczalne, do lewej strony takiego warunku ograniczającego dodajemy zmienną sztuczną typu v.
3. Kolejne iteracje.
Algorytm obliczeniowy jest rozszerzeniem algorytmu prymalnej metody simpleks dla zadania minimalizacji. W kolejnych iteracjach: a) Analizujemy wartości współczynników optymalności dla aktualnie rozpatrywanego rozwiązania bazowego. W przypadku, gdy istnieje przynajmniej jeden niedodatni wskaźnik optymalności dla zmiennej nieba-zowej, wybieramy jako zmienną kandydującą do bazy zmienną z najmniejszą wartością współczynnika optymalności.
b) Sprawdzamy, czy wybór zmiennej kandydującej do bazy był właściwy. Wybór jest właściwy, o ile w rozpatrywanej bazie nie ma zmiennej komplementarnej do wprowadzanej zmiennej. Jeżeli zmienna komplementarna jest w bazie, trzeba jeszcze sprawdzić, czy w wyniku wykonywanego przekształcenia zmienna ta opuści bazę. Niedopuszczalne jest, aby zmienna bazowa i zmienna do niej komplementarna znalazły się jednocześnie w bazie3. O ile taka sytuacja miałaby wystąpić, należy zmienić zmienną kandydującą do bazy, biorąc zmienną z kolejnym najmniejszym współczynnikiem optymalności.
c) Wybieramy zmienną usuwaną z bazy. Reguła wyboru zmiennej wychodzącej z bazy jest taka sama jak w prymalnej metodzie simpleks.
d) Oceniamy, czy na podstawie otrzymanego rozwiązania optymalnego zadania zastępczego można odczytać rozwiązanie optymalne zadania wyjściowego. Będzie tak wówczas, gdy w ostatnim rozpatrywanym rozwiązaniu zadania zastępczego wszystkie zmienne sztuczne przyjmą wartość 0. Jeżeli warunek ten nie jest spełniony, zadanie wyjściowe jest sprzeczne.
Jedną z metod konstrukcji optymalnego portfela akcji jest podejście zaproponowane przez H. Markowitza. Polega ono na określeniu takiego składu portfela, złożonego z akcji n spółek, który minimalizuje ryzyko portfela przy założonym z góry poziomie oczekiwanego zysku.
Podstawowym założeniem teorii Markowitza jest to, że kursy akcji cechują się pewną inercją, w związku z tym na podstawie zachowania się cen w N okresach w przeszłości można przewidywać ich zachowanie się w przyszłości. Dlatego leż jako oczekiwaną stopę zysku z akcji proponuje się przyjąć średnią stopę zysku, wyznaczoną na podstawie pewnej liczby okresów z przeszłości, natomiast jako miarę ryzyka przyjmuje się odchylenie standardowe stopy zysku.
* Warunki komplcmentamości byłyby spełnione również wówczas, gdyby w bazie znalazły się równocześnie rozpatrywana zmienna i zmienna do niej komplementarna, przy czym jedna z nich z wartością równą zeru. Ponieważ jednak w następnych iteracjach moglibyśmy w ten sposób stworzyć sytuację, że obie te zmienne — pozostając zmiennymi bazowymi — przyjęłyby wartości dodatnie (co naruszyłoby warunki komplemcntarności), możliwość ta nic jest dalej brana pod uwagę.