290 291

290 Programowanie wypukłe i kwadratowe

Rysunek 6.3

290 Programowanie wypukłe i kwadratowe

W literaturze światowej pojęcia funkcji wklęsłej i wypukłej definiuje się zgodnie z ich potocznym rozumieniem. Zauważmy przy tym, że funkcje wypukłe i wklęsłe są ze sobą blisko związane, dlatego też omawiana rozbieżność terminologiczna nie ma żadnego istotnego znaczenia.

Zadanie programowania wypukłego może być skutecznie rozwiązane dzięki wykorzystaniu pewnych własności funkcji wklęsłych i wypukłych. Jedna z nich pozwala w sposób jednoznaczny stwierdzić, że jeżeli znajdziemy ekstremum lokalne funkcji wypukłej (lub funkcji wklęsłej), to jest to jednocześnie ekstremum globalne. Inną ważną własnością programowania wypukłego jest możliwość sformułowania równoważnego temu zadaniu układu warunków, nazywanych warunkami Kuhna-Tuckera. Rozwiązanie tego układu (często łatwiejsze niż. rozwiązanie wyjściowego zadania programowania wypukłego) pozwala jednocześnie określić rozwiązanie optymalne tego zadania.

Szczególnym przypadkiem zadania programowania wypukłego jest zadanie programowania kwadratowego. W zadaniu tym funkcja celu jest kwadratowa, natomiast wszystkie warunki ograniczające są liniowe. Definicja tego zadania wskazuje na jego bliskie związki z programowaniem liniowym. Można je wykorzystać przy rozwiązywaniu układu warunków Kuhna-Tuckera. Formułując te warunki, otrzymamy układ liniowy, uzupełniony zależnościami zachodzącymi między związanymi ze sobą parami zmiennych. Pozwala to w trakcie rozwiązywania tego układu liniowego wykorzystać zmodyfikowaną metodę simpleks, uwzględniającą te dodatkowe powiązania.

W niniejszym rozdziale zajmiemy się zadaniami programowania wypukłego. Pokażemy graficzny sposób rozwiązywania zadań, w których występują dwie zmienne decyzyjne, a także sposób otrzymania rozwiązania przy wykorzystaniu układu warunków Kuhna-Tuckera i geometryczną interpretację postępowania zastosowanego w rozwiązywanym zadaniu. Rozpatrując zadania wielowymiarowe, skupimy się na zadaniu programowania kwadratowego i pokażemy możliwość jego rozwiązania za pomocą metody WoIfe’a. Pozwala ona wykorzystać zmodyfikowany sposób postępowania simpleksowego do rozwiązania układu warunków Kuhna-Tuckera.

Zadanie programowania kwadratowego było przedmiotem dużego zainteresowania naukowców niemalże od początku rozwoju badań operacyjnych ze względu na możliwość jego wykorzystania w problemie poszukiwania optymalnego portfela akcji. W zadaniu tym minimalizujemy ryzyko portfela (mierzone za pomocą funkcji kwadratowej) przy liniowych warunkach ograniczających, opisujących udziały poszczególnych walorów w portfelu, oraz założoną minimalną oczekiwaną stopę zysku z portfela. W końcowej części rozdziału pokażemy przykład formułowania i rozwiązania takiego zadania za pomocą programu KWADRAT.EXE. Program ten pozwala również na rozwiązanie innych zadań programowania kwadratowego, przedstawionych w tym rozdziale, oraz zadań o charakterze problemowym i numerycznym, zamieszczonych na dołączonym CD-ROM-ie.

6.2. Zadanie programowania wypukłego

6.2.1. Zbiory i funkcje wypukłe

Mówimy, że zbiór W jest wypukły, jeżeli dla dowolnych dwóch elementów x, y £ W oraz dla dowolnej liczby X z przedziału [0, 11 zachodzi związek:

(6.1)

Xx + (1 -X)y 6 W.

Warunek (6.1) jest spełniony w przestrzeni dwuwymiarowej wówczas, gdy wraz z dowolnymi dwoma punktami x, y do zbioru W należą wszystkie punkty odcinka o końcach x i y. Przykłady zbiorów wypukłych oraz zbioru niewypukłego w tej przestrzeni ilustruje rys. 6.4.

Rysunek 6.4

Zbiory wypukłe

Zbiór niewypukły

Funkcja / której dziedziną jest zbiór wypukły W, jest wypukła, jeżeli dla dowolnych dwóch argumentów x, y e W i dla dowolnej liczby X z przedziału [0, 1] zachodzi związek:

/(Xx-t-(1 -X)y) < X/(x) + (1 —X)f(y).

Funkcja /jest wklęsła, jeżeli funkcja -/jest wypukła.