Programowanie kwadratowe we wspomaganiu decyzji

Celem niniejszej pracy jest prezentacja teoretycznych i aplikacyjnych aspektów problematyki programowania kwadratowego ze szczególnym podkreśleniem możliwości praktycznego wykorzystania tych metod i ich implementacji komputerowej. Zaznaczony został przy tym wkład własny autorów niniejszego opracowania w tę problematykę. Niniejsza praca składa się z pięciu rozdziałów. W rozdziale pierwszym zostały zamieszczone preliminaria, do których zaliczono zagadnienia związane z określeniem zbiorów i funkcji wypukłych oraz wklęsłych. W rozdziale drugim zaprezentowano metody programowania kwadratowego wykorzystujące metodę simpleks. Ukazano również metodę Wolfe’a, przedstawiając przy tym różne pojawiające się sytuacje. Opisana została też możliwość wykorzystania oprogramowania dydaktycznego, dotyczącego metody Wolfe’a. Rozdział trzeci poświęcony jest implementacji komputerowej wybranych algorytmów wypukłego zadania programowania kwadratowego. Dalsze rozdziały pracy mają charakter aplikacyjny. Rozdział czwarty to zastosowanie metod programowania kwadratowego w wyborze portfela akcji w ujęciu teorii portfelowej. Zastosowania programowania kwadratowego w zarządzaniu przedsiębiorstwem zostały przedstawione w rozdziale piątym.

Spis treści

Wstęp 9 1. Preliminaria 11 1.1. Zbiory wypukłe i funkcje wypukłe (wklęsłe) 11 1.1.1. Zbiory wypukłe 11 1.1.2. Funkcje wypukłe i wklęsłe 16 1.1.3. Funkcja liniowa i funkcja kwadratowa 17 1.1.4. Funkcje wypukłe (wklęsłe) różniczkowalne 19 1.2. Programowanie liniowe 20 1.2.1. Sformułowanie i własności zadania programowania liniowego 20 1.2.2. Prymalna metoda simpleks 26 1.2.3. Zmienne sztuczne 29 1.2.4. Alternatywne rozwiązania bazowe 31 1.3. Programowanie wypukłe 32 1.3.1. Sformułowanie zadania programowania nieliniowego, wypukłego i kwadratowego 32 1.3.2. Twierdzenie Kuhna?Tuckera 33 2. Warunki Kuhna?Tuckera w rozwiązywaniu zadań programowania kwadratowego 39 2.1. Zadanie programowania kwadratowego 39 2.1.1. Rozwiązywanie zadań programowania kwadratowego metodami elementarnymi 39 2.1.2. Warunki Kuhna?Tuckera dla zadania programowania kwadratowego 43 2.1.3. Interpretacja geometryczna w przypadku dwuwymiarowym 44 2.2. Metoda Beale’a 47 2.2.1. Opis metody 47 2.2.2. Przykład ilustrujący metodę Beale’a 51 2.3. Metoda Wolfe’a 54 2.3.1. Opis metody 54 2.3.2. Opis programu KWADRAT.EXE 58 2.3.3. Wykorzystanie programu KWADRAT.EXE do rozwiązywania zadań programowania kwadratowego 61 3. Wykorzystanie pakietu R do rozwiązywania zadań programowania kwadratowego 74 3.1. Instalacja pakietu R 74 3.1.1. Instalacja wersji bazowej 74 3.1.2. Przykład instalacji dodatkowego pakietu 82 3.2. Zadanie testowe 86 3.2.1. Sformułowanie zadania testowego z wykorzystaniem macierzy Hilberta 86 3.2.2. Implementacja zadania testowego w pakiecie R 87 3.3. Numeryczne rozwiązywanie ZPK 93 3.3.1. Metoda punktu wewnętrznego 93 3.3.2. Rozwiązywanie ZPK z wykorzystaniem metody punktu wewnętrznego 94 3.3.3. Implementacje ZPK z wykorzystaniem metody punktu wewnętrznego w pakiecie R 109 3.3.3.1. Wykorzystanie pakietu Kernlab 109 3.3.3.2. Wykorzystanie pakietu Pakiet LowRankQP 112 3.4. Algorytm Goldfarba?Idnaniego 115 3.4.1. Opis algorytmu 115 3.4.2. Implementacja w pakiecie R (QuadProg) 120 3.5. Metoda sekwencyjnego programowania kwadratowego 122 3.5.1. Opis metody 122 3.5.2. Implementacje SQP w pakiecie R 124 3.5.2.1. Wykorzystanie pakietu Pakiet NlcOptim (SQP) 124 3.5.2.2. Wykorzystanie pakietu Pakiet nloptr 126 4. Zastosowanie metod programowania kwadratowego w wyborze portfela akcji 130 4.1. Portfele akcji 130 4.1.1. Charakterystyki portfela akcji 130 4.1.2. Modele wyboru optymalnego portfela akcji 132 4.2. Portfele narożne 133 4.2.1. Definicja sąsiednich portfeli narożnych 133 4.2.2. Opis algorytmu wyznaczania portfeli narożnych 134 4.2.3. Wyznaczanie portfela efektywnego z wykorzystaniem zbioru portfeli narożnych 140 4.3. Implementacja algorytmu wyznaczania zbioru portfeli narożnych w pakiecie SAS 140 4.3.1. Opis implementacji 140 4.3.2. Kod programu 141 4.4. Przykłady wyznaczania i wykorzystania zbioru portfeli narożnych 145 4.4.1. Wyznaczanie zbioru portfeli narożnych na podstawie algorytm 145 4.4.2. Interpretacja graficzna zbioru portfeli narożnych 150 4.4.3. Portfel efektywny o zadanej stopie zysku 151 4.4.4. Wyznaczanie zbioru portfeli narożnych akcji notowanych na GPW w Warszawie z wykorzystaniem pakietu SAS 151 5. Zastosowania programowania kwadratowego w zarządzaniu przedsiębiorstwem 154 5.1. Podział funduszu inwestycyjnego 154 5.1.1. Sformułowanie problemu 154 5.1.2. Przykłady obliczeniowe 155 5.2. Planowanie kampanii produkcyjnej w cukrowniach 160 5.2.1. Sformułowanie problemu 160 5.2.2. Przykłady obliczeniowe 162 5.3. Opracowanie planu restrukturyzacji przedsiębiorstwa wielozakładowego 167 5.3.1. Sformułowanie problemu 167 5.3.2. Przykład obliczeniowy 168 5.4. Planowanie kampanii reklamowej 169 5.4.1. Sformułowanie problemu 169 5.4.2. Przykłady obliczeniowe 170 Literatura 175