Градиентные методы решения ЗНЛП

1. Градиентные методы решения ЗНЛП

2.

Различают два класса данных методов: барьерные и штрафные.
Барьерные - запрещено выходить за ОДЗ.
Штрафные - позволяет периодически выходить за ОДЗ, но включают
штрафные функции, которые возвращают в ОДЗ.

3.

Метод Франка-Вульфа (барьерный метод)
f ( x ,...x ) max (1)
n 1 n
ai j x j bi (i 1,m) (2)
j 1
(3)
x 0 ( j 1,n)
j
(k )
(k )
(k )
f
(
X
)
f
(
X
)
f
(
X
)
(
k
)
f ( X
;
;...;
x1
x2
xn
(k )
(k )
(k )
f (X )
f (X
f (X )
z
x
x ...
x max
1
2
n
x1
x2
xn
(4)
ЗЛП: (4) max (2) (3)
Пусть точка Z k – решение ЗЛП:
X
(k 1)
X
0 1
k
(k )
(Z
k
(k )
X
(k )
)

4.

f ( x(k 1) )
0.
k
k 1) f ( x k )
Если f ( x
, где
- точность решения, то задача решена.
В противном случае, переходим к новой итерации.

5.

Пример:
f 2x 4x x 2 2x 2 max (1)
1
2 1
2
x 2 x 8,
1
2
2 x x 12,
2
1
(2)
x , x 0.
1 2
(3)
Решение. Найдем градиент функции:
f
f f
(2 2 x ;4 4 x ),
;
1
2
x x
2
1
и в качестве исходного допустимого решения задачи возьмем точку
X (0) (0,0).
z 2 x 4 x max
1
2
ЗЛП: (4) (2) (3)
z (0) (0,4)
(4)
x
(1)
x
(0)
( z
0
(0)
x
(1)
x 0 (0 0) 0
1
0
(1)
x 0 (4 0) 4
2
0
0
(0)
)

6.

(1)
) 2 0 4 4 02 2(4 )2 16 32 2
0
0
0
0
f 16 64 0
(1)
x (0;1)
0
0
(0)
f ( x ) 0
16 1
0 0,25
f ( x(1) ) 2
64 4
f (x
z 2 x max
1
(4)
(2) (1)
(1) (1)
ЗЛП: x x 1( z x )
x(1) .... x (2) ....
1
1
Следующая итерация:
x
(3)
f (x
f (x
(0,99528; 0,96321)
(3)
(3)
) 2,9937
) f ( x
(2)
) 0,0029 0,01

7.

Метод штрафных функций
f ( x ,...x ) max
1 n
g ( x ,...x ) b (i 1,m)
i 1 n i
x 0 ( j 1,n)
j
Вводим новую функцию: F f ( x1,x2,...,xn ) H ( x1,x2,...,xn ).
H – штрафная функция:
m
H ( x ,x ,...,x ) g ( x ,x ,...,x ),
i 1 2
n i 1 2
n
i 1
0, если b g ( x ,x ,...,x ) 0
i i 1 2
n
где ( x ,x ,...,x )
i 1 2
n i , если bi gi ( x1,x2 ,...,xn ) 0
Координаты следующей точки:
(
k
)
(
k
)
(k ) f ( X ) m gi ( X )
(
k
1
)
x
max 0;x
j
i x
j
x
i 1
j
k
В методе Эрроу-Гурвица: (k ) max 0; (k 1) g ( x(k 1) ) .
i
i
i

8.

Метод наискорейшего спуска
X 0, X1, ..., X k , X k 1 ,...
X k 1 X k l
(l l ,...,l ) f - если на max
1
n
(l l ,...,l ) f - если на min
1 n
g ( x ,..., x ) b (i 1,m)
i 1
n
i
Z Z ( X
) Z ( X )
k 1
k
z max(max)
z min(min)
X k 1 X k Z ( X k ) ( 0)
- (max)
X k 1 X k Z ( X k ) ( 0)
- (min)

9.

Z
0,
Z ( X k 1 ) Z ( X k ) Z ( X k 1 ) Z ( X k )
Z ( X k 1 ) Z ( X k )
...
x1
x1
x2
x2
xn
xn
Z ( X k 1 ) Z ( X k ) 0
Если ОДЗ линейна:
n
aij x j bi
j 1
n
(k 1)
(i 1,m), тогда a x
b (на границе).
ij j
i
j 1
n
(k )
aij ( x j l j ) bi
j 1
n
(k )
aij x j aijl j bi
j 1
n
(k )
b a x
i
ij j
j 1
n
aijl j
j 1

10.

Метод кусочно-линейной аппроксимации
Функция f ( x1,..., xn ) называется сепарабельной, если она может быть
представлена в виде суммы функций, каждая из которых зависит только от
одной переменной.
z f ( x ,..., x ) f j ( x ) max
1
n
j
n
f ( x ,..., x ) f ( x )
1
n
j j
j 1
gij ( x j ) bi
z x 2 x 2 ln x 25 x 13x
1 2
1
2
1
f ( x ) x 2 ln x 25 13x
1 1 1
1
1
f x2 x
2 2 2
(i 1,m)
x 0 ( j 1,n)
j
h(x)
h(x)
h
k 1
h
k
x1
xk
xk 1
xr a
x

11.

h( x) h
x x
k
k
h
h
x
x
k 1 k
k 1 k
(1 )h
h( x) h
k
1
k,
x x
(1 ) x
k 1
k
x x
x
k k k 1 k 1
h( x) h
h
k k k 1 k 1
1
k
k 1
k
,
k 1
k k 1
0 1
1
0
r
x x
k k
k 0
r
h( x) k hk
k 0
- параметрическое
уравнение отрезка
r
k 1, k 0 (k 1,r )
k 0

12.

n
F€ f j ( x j )
j 1
n ^
gij ( x j ) bi (i 1,m)
j 1
^
x 0 ( j 1,n)
j
^
f
f j (x j )
rj
k 0
^
kj
kj
rj
gij ( x )
j
k 0
f kj f j ( xk );
g kij g ij ( xk );
rj
x j kj xkj
k 0
kj
g kij

13.

r
n j
F f
kj kj
j 1k 0
r
n j
g kij kj bi
j 1k 0
r
(i 1,m)
j
kj 1 ( j 1,n) kj 0 k , j
k 0

14.

Пример:
F x x2 6 x 9 min
2 1
1
2 x 3x 24
1
2
x 2 x 15
2
1
3x 2 x 24
2
1
x 4
2
x , x 0
1 2
f ( x ) x 2 6 x 9
1 1
1
1
f ( x ) x
2 2 2
x [0,8]
1
x 0, x 1, x 0, x 2, x 3, x 4, x 5, x 6, x 7, x 8.
01
11
01
21
31
41
51
61
71
81
x k1 0
1
2
3
4
5
6
7
f1 ( xk1 ) -9
-4
-1
0
-1
-4
-9
-16 -25
Решение:
8
f ( x ) 9 4 4 9 16 25
1 1
01 11 21 41
51
61
71
81
x 0 1 2 3 4 5 6 7 8
1
01 11
21
31
41
51
61
71
81
F f (x ) f (x )
1 1 2 2

15.

Пример:
F 9 4 4 9 16 25 x2 max
01
11 21 41
51
61
71
81
2 4 6 8 10 12 14 16 x2 x3 24
11
21
31
41
51
61
71
81
11 2 21 3 31 4 41 5 51 6 61 7 71 8 81 2 x2 x4 15
3 6 9 12 15 18 21 24 2 x2 x5 24
11
21
31
41
51
61
71
81
x2 x6 4
01 11 21 31 41 51 61 71 81 1
x2 , x3 , x4 , x5 , x6 0,
k 0,(k 1,...8)
^
x1* 3, x2* 4, Fmax 4