Методы оптимизации. Азарнова Т.В - 51 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

53
)
,
(
)
(
4
y
2
8
x
2
x
f
−
−
=
Ω
),(),,(
min
03l03x
00
== , ),,( 03x
0
1
α = где
)0,3(
1
0
minarg
0
α
α
α
f
≤≤
=
.
Запишем задачу одномерной оптимизации
1
0
min)43(
2
≤≤
→−
α
α
Решением этой задачи будет ),(,
min
03xx1
01
0
=== тогдаα
Итерация 2
),()( 42xf
1
−−=∇
. Рассмотрим задачу
Ω
→−−=∇ min42)(
21
1
xxxxf
T
Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (0,2).
Выберем одну из них, например, =
1
x
min
(2,1). Тогда
),(),(),( 110312
0
l −=−=
,
),(
11
2
3x αα −= . Запишем задачу одномерной оптимизации
1
0
min)2()1(
22
≤≤
→−+−−
α
αα
Решением этой задачи будет )/,/(,/ 2125x21
2
0
== тогдаα
Итерация 3.
),()( 33xf
2
−−=∇
. Рассмотрим задачу
Ω
→−−=∇ min33)(
21
2
xxxxf
T
Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (3,0).
Выберем одну из них, например, =
2
x
min
(3,0). Тогда
)/,/()/,/(),( 2121212503
2
l −=−=
.
)
2
2
1
,
2
2
5
(
22
2
α
α
−+ = x
.
Запишем задачу одномерной оптимизации
1
0
min)()(
2
2
3
2
2
2
3
2
≤
≤
→++−
α
αα
Решением этой задачи будет )2/1,2/5( xтогда,0
23
2
=== xα . Останов.
Получено оптимальное решение х*=
)
2
/
1
,
2
/
5
(
.
Метод секущих плоскостей
Данный метод применяется для решения задач выпуклого
программирования с линейной целевой функцией :
.x*
Итерация 1.
),()( 48xf
0
−−=∇ . Рассмотрим задачу
линейного программирования
Ω
→−−=∇ min48)(
21
0
xxxxf
T
Решив ее графически , получаем
.
1
x
x
0
. 
                                                    53
                ∇ f ( x) =( 2 x −8, 2 y −4)
                                                    Итерация 1.
        Ω                                     ∇ f ( x 0 ) =(−8, −4 ) . Рассмотрим задачу
                                              линейного программирования
                           .   x*                       ∇ f ( x 0 ) x T =−8 x1 −4 x2 → min
 .
x0                              .   x1
                                              Решив ее графически, получаем
                                                                                    Ω


       0
     x min =(3,0 ), l 0 =(3,0 ) , x 1 =(3α 0 , 0 ), где α 0 =arg min f (3α ,0) .
                                                              0≤α ≤1
     Запишем задачу одномерной оптимизации
                                         (3α −4) 2 → min
                                     0 ≤α ≤1
 Решением этой задачи будет α 0 =1, тогда x 1 = x min       0
                                                               =(3,0 )
                                       Итерация 2
 ∇ f ( x 1 ) =( −2, −4 ) . Рассмотрим задачу ∇ f ( x 1 ) x T =−2 x1 −4 x 2 → min
                                                                                     Ω
 Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (0,2).
                                  1
 Выберем одну из них, например, x min =(2,1). Тогда l 0 =(2,1) −(3,0) =(−1,1) ,
     x 2 =(3 −α1 , α1 ) . Запишем задачу одномерной оптимизации
          ( −α −1) 2 +(α −2) 2 → min
          0 ≤α ≤1
 Решением этой задачи будет α 0 =1 / 2 , тогда x 2 =( 5 / 2,1 / 2 )
                                     Итерация 3.
 ∇ f ( x ) =( −3, −3) . Рассмотрим задачу ∇ f ( x 2 ) x T =−3 x1 −3 x 2 → min
        2
                                                                                     Ω
 Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (3,0).
                                              2
 Выберем одну из них, например, x min           =(3,0). Тогда
  l 2 =(3,0) −(5 / 2,1 / 2) =(1 / 2,−1 / 2) .
               α       α
     x 2 =( 52 + 22 , 12 − 22 ) .
     Запишем задачу одномерной оптимизации
                                  ( α2 − 32 ) 2 +( α2 + 32 ) 2 → min
                            0 ≤α ≤1
 Решением этой задачи будет α 2 =0, тогда x 3 =x 2 =(5 / 2,1 / 2) . Останов.
 Получено оптимальное решение х*= (5 / 2,1 / 2) .

                                    Метод секущих плоскостей
 Данный метод применяется           для решения                            задач     выпуклого
 программирования с линейной целевой функцией :

Страницы