Programowanie kwadratowe - Matlab


Programowanie kwadratowe jest szczególnym przypadkiem zadania programowanie liniowego. Do rozwiązywania zadań stosuje się tak zwane metody zbiorów aktywnych. Ich działanie jest podobne do działania metody Simplex. Metoda ta polega na włączaniu i usuwaniu ograniczeń ze zbiorów ograniczeń aktywnych (zbiór ograniczeń, na których krawędziach leży rozpatrywany punkt).

W Matlabie do rozwiązywania zadań programowania kwadratowego służy funkcja quadprog.

Ogólna forma funkcji:

[x,fval,exiflag,output,lambda] = quadprog(H, f, A, b, Aeq, beq, lb, ub, x0, options)

Argumenty wejściowe:

H macierz stałych współczynników funkcji celu (powinna być dodatnio określona)
f wektor kolumnowy stałych współczynników funkcji celu
A macierz ograniczeń liniowych nierównościowych
b kolumnowy wektor współczynników ograniczeń liniowych nierównościowych
Aeq macierz ograniczeń liniowych równościowych
beq kolumnowy wektor współczynników ograniczeń liniowych równościowych
x0 punkt startowy poszukiwań
options struktura opcji w algorytmie wyszukiwania

Argumenty wyjściowe:

x wektor zmiennych
fval wartość funkcji celu w punkcie minimum
exitflag informacja obliczeniowa
output decyduje o ilości informacji wyświetlanej na ekranie
lambda wartości współczynników Lagrange'a w punkcie optymalnym

Standardowa postać programowanie kwadratowego wygląda następująco:
min {c1x1 + c2x2 + ... + h1x12 + h12x1x2 + ... + h2x22 + h23x2x3 + ....}
gdzie:


Zadanie 1

Znaleźć rozwiązanie zadania programowania kwadratowego.

f(x) = 0.5x12 + x22 - x1x2 - 2x1 - 6x2 --> min
x1 + x2 <= 2
-x1 + 2x2 <= 2
2x1 + x2 <= 3
x1 >= 0, x2 >= 0

Zadanie 2

Znaleźć rozwiązanie zadania programowania kwadratowego.

f(x) = 0.5x12 + 3x1 + 4x2 --> min
x1 + 3x2 >= 15
2x1 + 5x2 <= 100
3x1 +4x2 <= 80
x1 >= 0, x2 >= 0

Zadanie 3

Znaleźć rozwiązanie zadania programowania kwadratowego.

f(x) = x12 + x1x2 + 2x22 + 2x32 + 2x2x3 + 4x1 + 6x2 + 12x3--> min

x1 + x2 + x3 >= 6
-x1 - x2 + 2x3 >= 2

x1 >= 0, x2 >= 0, x3 >= 0

Zadanie 4

Znajdź minimum funkcji kwadratowej

f(x) = x12 + x22
x1 + 2x2 >= 2
x1 <= 2
x2 <= 2