T.Trzaskalik, Optymalizacja kwadratowa
1
Programowanie kwadratowe
Programowanie kwadratowe
T.Trzaskalik
Wprowadzenie
do badań operacyjnych
z komputerem
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
2
Ekstrema globalne i lokalne
Ekstrema globalne i lokalne
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
3
Zbiory
Zbiory
wypukłe
wypukłe
C
y
x
∈
∀ ,
]
1
,
0
[
∈
∀
λ
C
y
x
∈
−
+
)
1
(
λ
λ
Zbiory wypukłe
Zbiór niewypukły
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
4
Funkcje wypukłe
Funkcje wypukłe
(
(
1)
1)
kształt
wypukły
kształt
wklęsły
6/
funkcja wypukła
funkcja wklęsła
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
5
Funkcje wypukłe (2)
Funkcje wypukłe (2)
Funkcja liniowa:
Funkcja liniowa:
∑
=
+
=
+
=
n
j
j
j
T
q
x
p
q
x
p
x
1
)
(
α
Forma kwadratowa:
Forma kwadratowa:
∑∑
=
=
=
=
n
i
n
j
j
i
ij
T
x
x
c
Cx
x
x
1
1
)
(
β
Twierdzenie 6.1:
Twierdzenie 6.1:
Forma kwadratowa jest funkcja wypukłą (wklęsłą) wtedy i tylko wtedy,
gdy macierz formy C jest nieujemnie (niedodatnio) określona.
)
(
)
1
(
)
(
)
)
1
(
(
]
1
,
0
[
,
,
y
f
x
f
y
x
f
W
y
x
λ
λ
λ
λ
λ
−
+
≤
−
+
∈
∀
∈
∀
Funkcja wypukła:
Funkcja wypukła:
Funkcja wklęsła:
Funkcja wklęsła:
f wklęsła ⇔ –f wypukła
6/
Definicje
Definicje
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
6
Funkcje wypukłe (3)
Funkcje wypukłe (3)
Funkcja kwadratowa:
Funkcja kwadratowa:
Cx
x
x
p
x
H
T
T
−
=
)
(
6/
Twierdzenie 6.2:
Twierdzenie 6.2:
Funkcja f mająca pochodne cząstkowe drugiego rzędu w zbiorze
wypukłym, otwartym W jest wypukła (wklęsła) w tym zbiorze wtedy i
tylko wtedy, gdy dla każdego x ∈ W macierz drugich pochodnych
funkcji
jest macierzą nieujemnie (niedodatnio) określoną.
∂
∂
∂
j
i
x
x
H
2
T.Trzaskalik, Optymalizacja kwadratowa
2
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
7
Zadanie programowania wypukłego (1)
Zadanie programowania wypukłego (1)
=
)
(
..........
)
(
)
(
1
x
g
x
g
x
g
m
→ max
)
(x
f
≥
≥
0
)
(
.....
..........
0
)
(
1
x
g
x
g
m
0
)
(
max
)
(
≥
→
x
g
x
f
6/
Powyższe zadanie jest zadaniem programowania wypukłego jeżeli
f i wszystkie g
i
są funkcjami wklęsłymi.
Sformułowanie zadania
Sformułowanie zadania
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
8
x
2
x
1
O
A (0, )
2
2
B ( , 0)
2
2
Zadanie programowania wypukłego (2)
Zadanie programowania wypukłego (2)
0
)
(
0
)
(
0
8
)
(
2
3
1
2
2
2
2
1
1
≥
=
≥
=
≥
−
−
=
x
x
g
x
x
g
x
x
x
g
)
(
2
1
+
=
x
x
x
f
Przykład 6.1
Przykład 6.1
P (2, 2)
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
9
Funkcja
Funkcja
Lagrange’a
Lagrange’a
∑
+
=
m
i
i
n
m
n
x
g
y
x
x
f
y
y
x
x
L
=
i
1
1
1
1
1
)
n
x
,...,
(
)
,...,
(
)
,...,
,
,...,
(
=
m
y
y
y
1
]
,...,
[
+
=
x
yg
x
f
y
x
L
)
(
)
(
)
,
(
→
x
g
x
f
≥ 0
)
(
max
)
(
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
10
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(1)
(1)
Warunek 1
0
)
,
(
=
∇
y
x
L
x
Warunek 2
0
)
(
=
x
yg
Warunek 3
0
)
(
≥
x
g
Warunek 4
0
≥
y
∂
∂
∂
∂
=
∇
n
x
x
y
x
L
x
y
x
L
y
x
L
)
,
(
,...,
)
,
(
)
,
(
1
Warunek Slatera
Twierdzenie 6.3:
Problem programowania wypukłego i problem Kuhna-Tuckera
opisane warunkami 1 - 4 są sobie równoważne.
6/
Sformułowanie warunków
Sformułowanie warunków
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
11
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(2)
(2)
2
3
1
2
2
2
2
1
1
2
1
3
2
1
2
1
)
8
(
)
,
,
,
,
(
x
y
x
y
x
x
y
x
x
y
y
y
x
x
L
+
+
−
−
+
+
=
Warunek 1:
Przykład 6.1
Przykład 6.1
0
)
(
0
)
(
0
8
)
(
)
(
2
3
1
2
2
2
2
1
1
2
1
≥
=
≥
=
≥
−
−
=
+
=
x
x
g
x
x
g
x
x
x
g
x
x
x
f
Warunek 2:
0
2
1
0
2
1
3
2
1
2
2
1
1
1
=
+
−
=
∂
∂
=
+
−
=
∂
∂
y
x
y
x
L
y
x
y
x
L
0
)
8
(
2
3
1
2
2
2
2
1
1
=
+
+
−
−
x
y
x
y
x
x
y
6/
Warunek 3:
0
)
(
0
)
(
0
8
)
(
2
3
1
2
2
2
2
1
1
≥
=
≥
=
≥
−
−
=
x
x
g
x
x
g
x
x
x
g
Warunek 4:
0
,
0
,
0
3
2
1
≥
≥
≥
y
y
y
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
12
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(3)
(3)
Podzbiór 1
Podzbiór 1
0
0
0
3
2
1
>
>
>
g
g
g
x
2
x
1
O
B
A
x
1
0
0
0
3
2
1
>
=
>
g
g
g
x
2
O
B
A
Podzbiór 3
Podzbiór 3
0
0
0
3
2
1
=
>
>
g
g
g
x
2
x
1
O
B
A
Podzbiór 4
Podzbiór 4
6/
Podzbiór 2
Podzbiór 2
0
0
0
3
2
1
>
>
=
g
g
g
x
2
x
1
O
B
A
Podział zbioru rozwiązań dopuszczalnych na podzbiory
Podział zbioru rozwiązań dopuszczalnych na podzbiory
T.Trzaskalik, Optymalizacja kwadratowa
3
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
13
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(4)
(4)
Podzbiór 5
Podzbiór 5
0
0
0
3
2
1
>
=
=
g
g
g
x
2
x
1
O
B
A
6/
0
0
0
3
2
1
=
=
=
g
g
g
Podzbiór 8
Podzbiór 8
Zbiór pusty
Zbiór pusty
Podzbiór 6
Podzbiór 6
0
0
0
3
2
1
=
>
=
g
g
g
x
2
x
1
O
B
A
0
0
0
3
2
1
=
=
>
g
g
g
Podzbiór 7
Podzbiór 7
x
2
x
1
O
B
A
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
14
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(5)
(5)
Warunek 1
Warunek 1
0
2
1
0
2
1
3
2
1
2
2
1
1
1
=
+
−
=
∂
∂
=
+
−
=
∂
∂
y
x
y
x
L
y
x
y
x
L
Warunek 2
Warunek 2
0
)
8
(
2
3
1
2
2
2
2
1
1
=
+
+
−
−
x
y
x
y
x
x
y
Warunek 3
Warunek 3
0
)
(
0
)
(
0
4
)
(
2
3
1
2
2
2
2
1
1
≥
=
≥
=
≥
−
−
=
x
x
g
x
x
g
x
x
x
g
Warunek 4
Warunek 4
0
,
0
,
0
3
2
1
≥
≥
≥
y
y
y
Podzbiór 1
Podzbiór 1
0
,
0
,
0
3
2
1
>
>
>
g
g
g
z warunku 2 wynika, że
0
,
0
,
0
3
2
1
=
=
=
y
y
y
Wstawiamy te wartości do warunku 1
0
0
0
2
1
1
=
+
⋅
⋅
−
x
czyli: 1 = 0 -
sprzeczność
6/
0
0
0
2
1
2
=
+
⋅
⋅
−
x
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
15
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
(6)
(6)
Warunek 1
Warunek 1
0
2
1
0
2
1
3
2
1
2
2
1
1
1
=
+
−
=
∂
∂
=
+
−
=
∂
∂
y
x
y
x
L
y
x
y
x
L
Warunek 2
Warunek 2
0
)
8
(
2
3
1
2
2
2
2
1
1
=
+
+
−
−
x
y
x
y
x
x
y
Warunek 3
Warunek 3
0
)
(
0
)
(
4
)
(
2
3
1
2
2
2
2
1
1
≥
=
≥
=
−
−
=
x
x
g
x
x
g
x
x
x
g
Warunek 4
Warunek 4
0
,
0
,
0
3
2
1
≥
≥
≥
y
y
y
Podzbiór 2
Podzbiór 2
0
,
0
,
0
3
2
1
>
>
=
g
g
g
z warunku 2 wynika, że
0
,
0
3
2
=
=
y
y
Wstawiamy te wartości do warunku 1
0
0
2
1
1
1
=
+
−
x
y
x
1
= 2, x
2
= 2, y
1
= 0,25, y
2
= 0, y
3
= 0
6/
0
0
2
1
2
1
=
+
−
x
y
1
2
1
1
2
1
,
2
1
y
x
y
x
=
=
( ) ( )
0
2
1
2
1
8
2
1
2
1
=
−
−
y
y
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
16
Zadanie programowania
Zadanie programowania
kwadratowego
kwadratowego
określona
nieujemnie
macierz
−
C
6/
0
≥
≤
x
b
Ax
max
→
− Cx
x
x
p
T
T
0
,
9
10
2
max
4
10
25
10
)
,
(
2
1
2
1
2
1
2
1
2
2
2
1
2
1
2
1
≥
≤
+
≤
+
→
−
−
−
+
=
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
Przykład 6.2.
Przykład 6.2.
,
25
10
=
p
,
1
2
2
10
=
C
=
2
1
x
x
x
,
9
10
=
b
Sformułowanie zadania
Sformułowanie zadania
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
17
Metoda
Metoda
Wolfe’a
Wolfe’a
(1)
(1)
max
4
10
25
10
)
(
2
1
2
2
2
1
2
1
→
−
−
−
+
=
x
x
x
x
x
x
x
f
[
]
d
d
y
y
y
y
y
2
1
2
1
,
,
,
=
=
)
,
,
,
,
,
(
2
1
2
1
2
1
d
d
y
y
y
y
x
x
L
6/
+
−
−
−
+
2
2
2
1
2
1
2
1
4
10
25
10
x
x
x
x
x
x
2
2
1
1
x
y
x
y
d
d
+
+
)
9
(
2
1
2
x
x
y
−
−
+
)
2
10
(
2
1
1
x
x
y
−
−
+
x
1
+ 2x
2
≤ 10
x
1
+ x
2
≤ 9
x
1
≥ 0
x
2
≥ 0
→
→
→
→
g
1
(x) = 10 – x
1
– 2x
2
≥ 0
g
2
(x) = 9 – x
1
– x
2
≥ 0
g
3
(x) = x
1
≥ 0
g
4
(x) = x
2
≥ 0
Przekształcenie warunków ograniczających
Przekształcenie warunków ograniczających
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
18
Warunek 1
Warunek 2
Warunek 3
Warunek 4
25
2
2
4
10
4
20
2
2
1
2
1
1
2
1
2
1
=
−
+
+
+
=
−
+
+
+
d
d
y
y
y
x
x
y
y
y
x
x
y
1
x
1
d
+ y
2
x
2
d
+ y
1
d
x
1
+ y
2
d
x
2
= 0
x
1
+ 2x
2
+ x
1
d
= 10
x
1
+ x
2
+ x
2
d
= 9
x
1
≥ 0
x
2
≥ 0
y
1
≥ 0, y
2
≥ 0, y
1
d
≥ 0, y
2
d
≥ 0
Metoda
Metoda
Wolfe’a
Wolfe’a
(2)
(2)
Warunki
Warunki
Kuhna
Kuhna
-
-
Tuckera
Tuckera
6/
T.Trzaskalik, Optymalizacja kwadratowa
4
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
19
Zadanie zastępcze
Zadanie zastępcze
Pominięty warunek:
Pary zmiennych komplementarnych:
w
1
+ w
2
→ min
x
1
+ 2x
2
+ x
1
d
= 10
x
1
+ x
2
+ x
2
d
= 9
20x
1
+ 4x
2
+ y
1
+ y
2
– y
1
d
+w
1
= 10
4x
1
+ 2x
2
+ 2y
1
+ y
2
– y
2
d
+ w
2
= 25
x
1
, x
2
, x
1
d
, x
2
d
, y
1
, y
2
, y
1
d
, y
2
d
, w
1
, w
2
≥ 0
y
1
i x
1
d
y
2
i x
2
d
y
1
d
i x
1
y
2
d
i x
2
y
1
x
1
d
+ y
2
x
2
d
+ y
1
d
x
1
+ y
2
d
x
2
= 0
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
20
Przebieg obliczeń (1)
Przebieg obliczeń (1)
25
9
10
b
1
1
0
0
0
0
0
0
0
cx→min
1
0
-1
0
1
2
0
0
2
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
2
0
0
1
1
-2
-3
0
0
-6
c
j
-z
j
1
w
2
0
x
2
d
0
x
1
d
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
0
4
10
0
1
0
-1
1
1
0
0
4
1
w
1
20
1
1
-24
x
1
c
B
Baza
Iteracja 1
Iteracja 1
6/
0
4
20
1
1
-24
x
1
10
0
1
0
-1
1
1
0
0
4
1
w
1
20
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
21
Przebieg obliczeń (2)
Przebieg obliczeń (2)
23
8,5
9,5
b
1
1
0
0
0
0
0
0
0
0
cx→min
1
-0,2
-1
0,2
0,8
1,8
0
0
1,2
0
0
-0,05
0
0,05
-0,05
-0,05
1
0
0,8
0
0
-0,05
0
0,05
-0,05
-0,05
0
1
1,8
0
0
1,2
1
-0,2
-0,8
-1,8
0
0
-1,2
0
c
j
-z
j
1
w
2
0,5
0
0,05
0
-0,05
0,05
0,05
0
0
0,2
1
0
x
1
0
0
x
1
d
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
Iteracja 2
Iteracja 2
6/
0
1,8
0,05
-0,05
-0,05
-1,8
y
1
0
1,2
0,2
0,8
1,8
-1,2
x
2
0,5
0
0,05
0
-0,05
0,05
0,05
0
0
0,2
1
0
x
1
x
2
d
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
22
Przebieg obliczeń (3)
Przebieg obliczeń (3)
20
2,5
6,5
5
b
1
1
0
0
0
0
0
0
0
0
cx→min
1
-0,5
-1
0,5
0,5
1,5
0
0
0
-6
0
0,25
0
-0,25
0,25
0,25
0
0
1
5
0
-0,25
0
0,25
-0,25
-0,25
1
0
0
-4
0
-0,25
0
0,5
-0,5
-0,5
0
1
0
-9
0
1,5
1
-0,5
-0,5
-1,5
0
0
0
6
c
j
-z
j
1
w
2
0
x
2
0
x
2
d
0
x
1
d
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
Iteracja 3
Iteracja 3
6/
0
1,5
0,25
-0,25
-0,5
-1,5
y
1
0
0,5
0,25
-0,25
-0,5
-0,5
y
2
0
0,5
-0,25
0,25
0,5
-0,5
y
1
d
5
0
-0,25
0
0,5
-0,5
-0,5
0
1
0
-9
0
x
1
d
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
23
Przebieg obliczeń (4)
Przebieg obliczeń (4)
15
5
4
10
b
1
1
0
0
0
0
0
0
0
0
cx→min
1
0
-1
0
1
2
0
-1
0
3
0
0
0
0
0
0
0
0
1
0,5
0
0
0
0
0
0
1
-0,5
0
0,5
0
-1
0
1
-1
-1
0
2
0
-18
0
1
1
0
-1
-2
0
1
0
-3
c
j
-z
j
1
w
2
0
x
2
0
x
2
d
0
y
1
d
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
Iteracja 4
Iteracja 4
6/
0
3
0,5
0,5
-18
-3
x
1
0
2
0
0
-1
-2
y
1
15
1
0
-1
0
1
2
0
-1
0
3
1
w
2
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
24
Przebieg obliczeń (5)
Przebieg obliczeń (5)
7,5
5
4
17,5
b
1
1
0
0
0
0
0
0
0
0
cx→min
0,5
0
-0,5
0
0,5
1
0
-0,5
0
1,5
0
0
0
0
0
0
0
0,5
1
0,5
0
0
0
0
0
0
1
-0,5
0
0,5
0,5
-1
-0,5
1
-0,5
0
0
1,5
0
-16,5
1
1
0
0
0
0
0
0
0
0
c
j
-z
j
1
y
2
0
x
2
0
x
2
d
0
y
1
d
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
Iteracja 5
Iteracja 5
6/
Z twierdzenia Kuhna-Tuckera:
x
1
= 0, x
2
= 5 - rozwiązanie optymalne wyjściowego zadania
programowania kwadratowego
T.Trzaskalik, Optymalizacja kwadratowa
5
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
25
Zmienna sztuczna typu
Zmienna sztuczna typu
v
v
(1)
(1)
f
(x
1
,x
2
) = 10x
1
+ 25x
2
– 10x
1
2
– x
2
2
– 4x
1
x
2
→ max
x
1
+ 2x
2
≤ 10
–x
1
– x
2
≤ –9
x
1
≥ 0
x
2
≥ 0
Przykład 6.3
Przykład 6.3
Zadanie zastępcze
Zadanie zastępcze
v
1
+ w
1
+ w
2
→ min
x
1
+ 2x
2
+ x
1
d
= 10
x
1
+ x
2
– x
2
d
+ v
1
= 9
20x
1
+ 4x
2
+ y
1
− y
2
− y
1
d
+ w
1
= 10
4x
1
+ 2x
2
+ 2y
1
− y
2
− y
2
d
+ w
2
= 25
x
1
, x
2
, x
1
d
, x
2
d
, y
1
, y
2
, y
1
d
, y
2
d
, v
1
, w
1
, w
2
≥0
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
26
Zmienna sztuczna typu
Zmienna sztuczna typu
v
v
(
(
2)
2)
Iteracja 5
Iteracja 5
4
17,5
7,5
5
b
1
1
0
0
0
0
0
0
0
0
cx→min
0
0
0
0
0
0
-1
-0,5
0
0,5
0,5
-1
-0,5
1
0,5
0
0
1,5
0
-16,5
0,5
0
-0,5
0
-0,5
1
0
-0,5
0
1,5
0
0
0
0
0
0
0
0,5
1
0,5
1
1
0
0
0
0
1
0,5
0
-0,5
c
j
-z
j
1
v
1
0
y
1
d
0
y
1
0
x
2
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
1
1
0
0
0
0
v
1
6/
0
0,5
-16,5
1,5
0,5
-0,5
x
1
0
0
0,5
-0,5
0
0
y
2
17,5
0,5
-1
-0,5
1
0,5
0
0
1,5
0
-16,5
0
y
1
d
0
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
27
Zmienna sztuczna typu
Zmienna sztuczna typu
v
v
(3)
(3)
Iteracja 6
Iteracja 6
4
35
25
5
b
1
1
0
0
0
0
0
0
0
0
cx→min
0
0
0
0
0
0
-1
-0,5
0
0,5
1
-2
-1
2
1
0
0
3
0
-33
1
-1
-1
1
0
1
0
1
0
-15
0
0
0
0
0
0
0
0,5
1
0,5
1
1
0
0
0
0
1
0,5
0
-0,5
c
j
-z
j
1
v
1
0
y
2
0
y
1
0
x
2
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
1
1
0
0
0
0
v
1
6/
0
0,5
-33
-15
0,5
-0,5
x
1
4
0
0
0
0
0
0
-1
-0,5
0
0,5
1
v
1
1
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
28
Iteracja 7
Iteracja 7
8
299
145
1
b
1
1
0
0
0
0
0
0
0
0
cx→min
0
0
0
0
0
0
-2
-1
0
1
1
-2
-1
2
1
0
-66
-30
0
0
1
-1
-1
1
0
1
-30
-14
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
c
j
-z
j
0
x
1
0
y
2
0
y
1
0
x
2
w
2
w
1
y
2
d
y
1
d
y
2
y
1
x
2
d
x
1
d
x
2
x
1
c
B
Baza
1
2
66
30
-1
0
v
1
Zmienna sztuczna typu
Zmienna sztuczna typu
v
v
(4)
(4)
6/
Z twierdzenia Kuhna-Tuckera:
x
1
= 8, x
2
= 1 - rozwiązanie optymalne wyjściowego zadania
programowania kwadratowego
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
29
f
(x
1
,x
2
) = 10x
1
– 25x
2
– 10x
1
2
– x
2
2
– 4x
1
x
2
→ max
x
1
+ 2x
2
≤ 10
–x
1
– x
2
≤ –9
x
1
≥ 0
x
2
≥ 0
Przykład 6.4
Przykład 6.4
Zadanie zastępcze
Zadanie zastępcze
v
1
+ w
1
→ min
x
1
+ 2x
2
+ x
1
d
= 10
x
1
+ x
2
– x
2
d
+ v
1
= 9
20x
1
+ 4x
2
+ y
1
− y
2
− y
1
d
+ w
1
= 10
−4x
1
− 2x
2
− 2y
1
+ y
2
+ y
2
d
= 25
x
1
, x
2
, x
1
d
, x
2
d
, y
1
, y
2
, y
1
d
, y
2
d
, v
1
, w
1
≥0
Przypadek
Przypadek
ogólny
ogólny
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
30
Algorytm
Algorytm
Wolfe’a
Wolfe’a
1.
1.
Zapisanie warunków Kuhna-Tuckera
2.
2.
Zapisanie zadania zastępczego:
a) zmienne sztuczne typu w,
b) zmienne sztuczne typu v,
3.
3.
Rozwiązanie zadania zastępczego:
a) wybór zmiennej kandydującej do bazy,
b) sprawdzenie, czy wybór zmiennej kandydującej był właściwy,
c) wybór zmiennej usuwanej z bazy,
d) badanie niesprzeczności zadania.
6/
4.
4.
Odczytanie rozwiązania zadania wyjściowego.
T.Trzaskalik, Optymalizacja kwadratowa
6
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
31
Optymalny portfel akcji (1)
Optymalny portfel akcji (1)
Stopa zysku
z i-tej akcji w okresie t
(t = 1, ..., T)
( )
( )
(
)
(
)
1
1
−
−
−
=
t
i
P
t
i
P
t
i
P
t
i
R
Oczekiwana stopa zysku
z i-tej akcji
( )
∑
=
=
T
t
i
i
t
R
T
R
2
1
Udziały akcji w portfelu
0
x
,
1
x
i
n
1
i
i
≥
=
∑
=
Oczekiwana stopa zysku
portfela akcji
∑
=
=
n
i
i
i
p
x
R
R
1
6/
Określić taki skład portfela, złożonego z akcji n spółek, by zminimalizować
ryzyko portfela, przy założonym z góry poziomie oczekiwanego zysku.
Sformułowanie problemu
Sformułowanie problemu
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
32
Optymalny portfel akcji (2)
Optymalny portfel akcji (2)
Ryzyko (wariancja)
portfela
Odchylenie standardowe
stopy zysku
Współczynnik korelacji
Zmodyfikowany wzór na
wariancję portfela
∑∑
=
=
=
n
i
n
j
ij
j
i
j
i
p
r
S
S
x
x
v
1
1
( )
(
)
∑
=
−
=
T
t
i
i
i
R
t
R
T
S
1
2
1
( )
(
) ( )
(
)
(
)
j
i
j
i
j
i
T
t
j
j
i
i
ij
S
S
R
R
S
S
R
t
R
R
t
R
T
r
,
cov
1
1
=
−
−
=
∑
=
∑∑
=
=
=
n
i
n
j
j
i
j
i
p
R
R
x
x
v
1
1
)
,
cov(
6/
Sformułowanie problemu (c.d.)
Sformułowanie problemu (c.d.)
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
33
Optymalny portfel akcji (3)
Optymalny portfel akcji (3)
min
1
1
→
∑∑
=
=
ij
n
i
n
j
j
i
v
x
x
0
1
R
x
R
n
i
i
i
≥
∑
=
∑
=
=
n
i
i
x
1
1
x
i
≥ 0 dla i = 1, ..., n
V
– macierz wariancji i kowariancji (V = [cov(R
i
, R
j
)]),
6/
O
T
x
–
x
T
Vx
→ max
Rx
≥
≥≥
≥
R
O
1
T
x
=
1
x
≥
≥≥
≥
0
[
]
,
,...,
1
n
R
R
=
R
1
=
1
:
1
O
,
0
:
0
=
x
,
:
1
=
n
x
x
Sformułowanie problemu (c.d.)
Sformułowanie problemu (c.d.)
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
34
Optymalny portfel akcji (4)
Optymalny portfel akcji (4)
73.50
31.00
270.50
19.15
64.00
72.10
29.10
269.50
18.50
65.00
71.40
31.30
270.00
17.95
65.10
72.20
32.80
268.00
18.50
67.10
72.40
32.90
265.00
18.60
67.60
72.30
33.30
263.50
17.20
66.20
74.00
34.00
267.00
17.30
64.30
73.90
34.50
265.00
17.20
64.30
75.30
34.30
270.50
17.70
65.70
71.50
32.70
272.00
16.90
66.60
68.80
33.00
285.00
16.50
64.20
68.10
29.80
286.00
16.00
59.40
68.30
28.90
286.00
16.00
61.90
69.00
29.00
281.00
15.50
61.90
70.00
28.70
283.50
15.50
61.00
69.00
29.80
290.00
15.20
58.30
68.00
31.40
274.50
15.25
54.60
65.70
29.30
270.00
15.50
52.30
66.50
27.80
275.50
15.50
51.00
66.00
27.20
283.00
15.75
52.00
67.50
26.90
273.00
15.20
53.60
Spółka 5
Spółka 4
Spółka 3
Spółka 2
Spółka 1
Notowania
1.94
6.53
0.37
3.51
-1.54
0.98
-7.03
-0.19
3.06
-0.15
-1.11
-4.57
0.75
-2.97
-2.98
-0.28
-0.30
1.13
-0.54
-0.74
0.14
-1.20
0.57
8.14
2.11
-2.30
-2.06
-1.31
-0.58
2.95
0.14
-1.45
0.75
0.58
0.00
-1.86
0.58
-2.03
-2.82
-2.13
5.31
4.89
-0.55
4.73
-1.35
3.92
-0.91
-4.56
2.42
3.74
1.03
10.74
-0.35
3.13
8.08
-0.29
3.11
0.00
0.00
-4.04
-1.01
-0.34
1.78
3.23
0.00
-1.43
1.05
-0.88
0.00
1.48
1.45
-3.69
-2.24
1.97
4.63
1.47
-5.10
5.65
-0.33
6.78
3.50
7.17
1.67
-1.61
4.40
-1.20
5.40
-2.00
0.00
2.55
0.76
2.21
-2.65
-1.59
-1.92
-2.22
1.12
3.66
3.62
-2.99
Sp
ó
łka 5
Spółka 4
Spółka 3
Spółka 2
Spółka 1
Oczekiwane stopy zysku z akcji w okresie t w %
6/
Przykład 6.4
Przykład 6.4
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
35
Optymalny portfel akcji (5)
Optymalny portfel akcji (5)
0.45
0.81
-0.02
1.20
R
i
Spółka 5
Spółka 4
Spółka 3
Spółka 2
0.94
Spółka 1
Oczekiwane stopy zysku z akcji w %
Oczekiwane stopy zysku z akcji w %
6/
2.0254
Spółka 5
1.6619
Spółka 4
0.1232
Spółka 3
1.1701
Spółka 2
11.4312
Spółka 1
4.3189
2.2824
-0.6307
1.7056
2.2824
20.2858
-1.3094
1.1374
-0.6307
-1.3094
5.1598
0.4983
1.7056
1.1374
0.4983
7.7723
2.0254
1.6619
0.1232
1.1701
Spółka 5
Spółka 4
Spółka 3
Spółka 2
Spółka 1
Macierz wariancji
Macierz wariancji
-
-
kowariancji st
kowariancji st
ó
ó
p zysku
p zysku
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
36
Optymalny portfel akcji (
Optymalny portfel akcji (
6)
6)
Cel
Cel
Znalezienie portfela akcji minimalizującego ryzyko o zadanej
oczekiwanej stopie zwrotu.
Zmienne decyzyjne
Zmienne decyzyjne
x
1
– udział w portfelu akcji spółki 1,
x
2
– udział w portfelu akcji spółki 2,
x
3
– udział w portfelu akcji spółki 3,
x
4
– udział w portfelu akcji spółki 4,
x
5
– udział w portfelu akcji spółki 5,
6/
T.Trzaskalik, Optymalizacja kwadratowa
7
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
37
Optymalny portfel akcji (
Optymalny portfel akcji (
7)
7)
Funkcja celu
Funkcja celu
f
(x
1
, x
2
, x
3
, x
4
, x
5
) = [x
1
, x
2
, x
3
, x
4
, x
5
] ⋅
V
⋅ [x
1
, x
2
, x
3
, x
4
, x
5
]
T
min
Ograniczenia
Ograniczenia
4.3189
2.2824
-0.6307
1.7056
2.0254
2.2824
20.2858
-1.3094
1.1374
1.6619
-0.6307
-1.3094
5.1598
0.4983
0.1232
1.7056
1.1374
0.4983
7.7723
1.1701
2.0254
1.6619
0.1232
1.1701
11.4312
V
=
oczekiwany zysk z portfela ma być większy od 1%, czyli:
0,94x
1
+ 1,20x
2
– 0,02x
3
+ 0,81x
4
+ 0,45x
5
≥ 1
6/
udziały akcji w portfelu sumują się do jedności:
x
1
+ x
2
+ x
3
+ x
4
+ x
5
= 1
warunki nieujemności:
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
38
Optymalny portfel akcji (
Optymalny portfel akcji (
8)
8)
max
3189
,
4
2824
,
2
6307
,
0
7056
,
1
0254
,
2
2824
,
2
2858
,
20
3094
,
1
1374
,
1
6619
,
1
6307
,
0
3094
,
1
1598
,
5
4983
,
0
1232
,
0
7056
,
1
1374
,
1
4983
,
0
7723
,
7
1701
,
1
0254
,
2
6619
,
1
1232
,
0
1701
,
1
4312
,
11
]
,
,
,
,
[
)
,
,
,
,
(
5
4
3
2
1
5
4
3
2
1
5
4
3
2
1
→
−
−
−
−
−
=
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
przy warunkach ograniczających:
6/
–0,94x
1
– 1,20x
2
+ 0,02 x
3
– 0,81x
4
– 0,45x
5
≤ –1
x
1
+ x
2
+ x
3
+ x
4
+ x
5
≤ 1
–x
1
–
x
2
–
x
3
–
x
4
–
x
5
≤ –1
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0
Rozwinięta postać zadania
Rozwinięta postać zadania
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
39
Optymalny portfel akcji (
Optymalny portfel akcji (
9)
9)
Rozwiązanie optymalne
Rozwiązanie optymalne
Interpretacja rozwiązania
Interpretacja rozwiązania
x
1
= 0,2468
x
2
= 0,5391
x
3
= 0,0285
x
4
= 0,1060
x
5
= 0,0797
6/
Optymalny portfel, dla którego stopa oczekiwanego zysku jest nie
mniejsza niż 1% będzie się składał (w ujęciu wartościowym) w 24,68%
z akcji spółki 1, w 53,91% z akcji spółki 2, w 2,85% z akcji spółki 3, w
10,6% z akcji spółki 4 i w 7,97% akcji spółki 5. Ryzyko takiego portfela
wynosi
41
,
1
2 ≈
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
40
Optymalizacja portfela akcji jako problem dwukryterialny (1)
Optymalizacja portfela akcji jako problem dwukryterialny (1)
Przykład 6.4
Przykład 6.4
Cel
Cel
Szukamy takiego portfela akcji, dla którego ryzyko jest minimalne, a
oczekiwany zysk portfela – maksymalny.
Zmienne decyzyjne
Zmienne decyzyjne
x
1
– udział w portfelu akcji spółki 1,
x
2
– udział w portfelu akcji spółki 2,
x
3
– udział w portfelu akcji spółki 3,
x
4
– udział w portfelu akcji spółki 4,
x
5
– udział w portfelu akcji spółki 5,
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
41
Funkcje celu
Funkcje celu
Maksymalizacja oczekiwanej stopy zysku portfela:
0,94x
1
+ 1,2x
2
– 0,02x
3
+ 0,81x
4
+ 0,45x
5
→ max
Minimalizacja ryzyka portfela
min
]
,
,
,
,
[
3189
,
4
2824
,
2
6307
,
0
7056
,
1
0254
,
2
2824
,
2
2858
,
20
3094
,
1
1374
,
1
6619
,
1
6307
,
0
3094
,
1
1598
,
5
4983
,
0
1232
,
0
7056
,
1
1374
,
1
4983
,
0
7723
,
7
1701
,
1
0254
,
2
6619
,
1
1232
,
0
1701
,
1
4312
,
11
]
,
,
,
,
[
5
4
3
2
1
5
4
3
2
1
→
−
−
−
−
T
x
x
x
x
x
x
x
x
x
x
Optymalizacja portfela akcji jako problem dwukryterialny (2)
Optymalizacja portfela akcji jako problem dwukryterialny (2)
6/
x
1
+ x
2
+ x
3
+ x
4
+ x
5
= 1
Ograniczenia
Ograniczenia
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
42
–0,94x
1
– 1,20x
2
+ 0,02x
3
– 0,81x
4
– 0,45x
5
≤ –R
0
min
]
,
,
,
,
[
3189
,
4
2824
,
2
6307
,
0
7056
,
1
0254
,
2
2824
,
2
2858
,
20
3094
,
1
1374
,
1
6619
,
1
6307
,
0
3094
,
1
1598
,
5
4983
,
0
1232
,
0
7056
,
1
1374
,
1
4983
,
0
7723
,
7
1701
,
1
0254
,
2
6619
,
1
1232
,
0
1701
,
1
4312
,
11
]
,
,
,
,
[
5
4
3
2
1
5
4
3
2
1
→
−
−
−
−
T
x
x
x
x
x
x
x
x
x
x
Funkcja
Funkcja
celu
celu
Ograniczenia
Ograniczenia
Metoda satysfakcjonujących poziomów kryteriów (1)
Metoda satysfakcjonujących poziomów kryteriów (1)
6/
x
1
+ x
2
+ x
3
+ x
4
+ x
5
≤ 1
–x
1
–
x
2
–
x
3
–
x
4
–
x
5
≤ –1
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0
T.Trzaskalik, Optymalizacja kwadratowa
8
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
43
0.3668
0.0615
0.3959
0.1071
0.0687
1.34
0.4
P
10
0.3190
0.0689
0.3347
0.1791
0.0984
1.36
0.5
P
9
0.2711
0.0763
0.2734
0.2511
0.1280
1.43
0.6
P
8
0.2233
0.0837
0.2122
0.3231
0.1577
1.53
0.7
P
7
0.1754
0.0911
0.1510
0.3951
0.1874
1.67
0.8
P
6
0.1275
0.0986
0.0897
0.4671
0.2171
1.83
0.9
P
5
0.0797
0.1060
0.0285
0.5391
0.2468
2.00
1.0
P
4
0
0.0879
0
0.6594
0.2527
2.20
1.1
P
3
0
0.0054
0
0.8104
0.1841
2.42
1.15
P
2
0
0
0
1
0
2.79
1.2
P
1
x
5
x
4
x
3
x
2
x
1
V
p
R
0
Lp
Parametry portfeli wyznaczonych dla założonych wartości R
0
Metoda satysfakcjonujących poziomów kryteriów (2)
Metoda satysfakcjonujących poziomów kryteriów (2)
Wyniki obliczeń
Wyniki obliczeń
6/
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
44
Metoda satysfakcjonujących poziomów kryteriów (3)
Metoda satysfakcjonujących poziomów kryteriów (3)
Granica efektywna
Granica efektywna
6/
y
1
y
2
1
1,5
2
2,5
3
0,2
0,4
0,6
0,8
1
1,2
1,4
ryzyko portfela
o
cz
ek
iw
an
a
st
o
p
a
zy
sk
u
z
p
o
rt
fe
la
w
%
y
1
–3
–2,5
–2
–1,5
–1
y
2
0,4
0,6
0,8
1
1,2
1,4
ryzyko portfela × –1
o
cz
ek
iw
a
n
a
st
o
p
a
z
ys
k
u
z
p
o
rt
fe
la
w
%
y
1
y
2
1
1,5
2
2,5
3
0,2
0,4
0,6
0,8
1
1,2
1,4
ryzyko portfela
o
cz
ek
iw
an
a
st
o
p
a
z
ys
k
u
z
p
o
rt
fe
la
w
%
T.Trzaskalik: Wprowadzenie do
badań operacyjnych z komputerem
45
Podsumowanie
Podsumowanie
6/
Słowa kluczowe
Pora na relaks
Pora na relaks
• Zadanie programowania nieliniowego
• Ekstrema globalne i lokalne
• Zbiory wypukłe
• Funkcje wklęsłe i wypukłe
• Zadanie programowania wypukłego
• Warunki Kuhna - Tuckera
• Zadanie programowania kwadratowego
• Algorytm Wolfe’a
• Funkcja Lagrange’a
• Zadanie zastępcze
• Zmienne sztuczne typu w i u
• Optymalny portfel akcji
• Zadanie Markowitza
!!!
Dwie następne strony (8-9) są autorstwa M.Miszczyńskiego !!!
T.Trzaskalik, Optymalizacja kwadratowa
9
!!!
Dwie ostatnie strony (8-9) są autorstwa M.Miszczyńskiego !!!
Jak bezpiecznie powiększyć fundusze na Półmetek ?
Tradycją braci studenckiej jest bal zwany Półmetkiem. Pewna grupa studentów dość niemrawo
zabierała się za organizację takiego balu. Może nawet nie mieli ochoty na ten bal. Jednakże jeden z
wykładowców dał im wyraźnie do zrozumienia, że łamanie wielowiekowej tradycji nie może mieć miejsca.
To przesądziło, że wspomniana grupa raźniej zabrała się za sprawy organizacyjne.
W celu zwiększenia swoich możliwości w finansowaniu takiej imprezy postanowili zainwestować
posiadany kapitał na giełdzie w akcje dwóch znanych browarów: Pianka i Kapsel. Zebrali informacje o
kursach akcji obu spółek w kolejnych 26 tygodniach (średnie notowania dla tygodnia).
kursy akcji
nr
notowania
Pianka Kapsel
1
348
334
2
305
370
3
312
389
4
339
389
5
347
420
6
359
418
7
385
441
8
422
445
9
421
433
10
390
424
11
411
416
12
454
433
13
481
432
14
496
417
15
547
453
16
542
485
17
521
501
18
518
519
19
558
522
20
598
559
21
600
590
22
598
594
23
624
601
24
642
598
25
645
633
26
685
657
Kolejny problem przed jakim stanęli wiązał
się z podziałem posiadanego kapitału pomiędzy
akcje obu spółek (jaka ma być struktura kapitałowa
ich portfela ?). Było dla nich oczywistym, że muszą
użyć portfela o minimalnym ryzyku (brać studencka
ma na ogół ograniczone fundusze; chociaż patrząc
na parking ...). Portfel taki można wyznaczyć m. in.
budując i rozwiązując klasyczny model Markovitz’a.
Słyszeli o takim modelu na jednym z wykładów. Jak
to jednak bywa nie bardzo pamiętali już jak taki
model wygląda (zgodnie z zasadą niemałej części
braci studenckiej: „zdane i zapomniane”).
Przypomnijmy zatem model Markovitz’a.
Znajdź udział kapitałowy (
j
x
) każdej spółki w
portfelu z akcjami n spółek o oczekiwanych stopach
zwrotu (
j
R
) w każdej tak, aby oczekiwana stopa
zwrotu z portfela nie była mniejsza niż
0
R
oraz
ryzyko portfela (mierzone wariancjami i
kowariancjami stóp zwrotu
ij
cov ) było minimalne.
,n
...
,
,
j
x
x
R
x
R
x
x
z
j
n
j
j
n
j
j
j
n
i
n
j
j
ij
i
2
1
0
1
min
cov
1
1
0
1
1
=
≥
=
≥
→
=
∑
∑
∑ ∑
=
=
=
=
T.Trzaskalik, Optymalizacja kwadratowa
10
„Półmetkowicze” przyjęli 2%-owy oczekiwany zysk z portfela (
0
R =0,02). Należy teraz policzyć
pozostałe parametry modelu Markovitz’a i ustalić skład portfela o najmniejszym ryzyku.
Model „półmetkowiczów” ma postać:
[
]
0
,
0
1
02
,
0
__________
__________
min
__________
__________
__________
__________
2
1
2
1
2
1
2
1
2
1
≥
≥
=
+
≥
+
→
=
x
x
x
x
x
x
x
x
x
x
z
Wyszukiwarka
Podobne podstrony:
Sterowanie optymalne z kwadratowym wskaźnikiem jakości
Nierówności kwadratowe
Optymalizacja LP
Postać kanoniczna funkcji kwadratowej
Zasady ergonomii w optymalizacji czynności roboczych
optymalizacja fak
Podstawy Optymalizacji, simplex
Test HI kwadrat
model optymalizacyjny
Kwadrans przed Przenajświętszym
BO WYK2 Program liniowe optymalizacja
Logistyka i optymalizacja kosztow w handlu internetowym
PRACA PRZEJŚCIOWA OPTYMALIZACJA PROCESÓW ENERGETYCZNYCH POPRZEZ ZASOTOWANIE NOWOCZESNYCH ALGORYTMÓW
ITIL Podstawy W2 Budowa i optymalizacja procesów i serwisów ITIL
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
więcej podobnych podstron