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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
−
)( xf
i
непрер.
непрер. диффер.
непрер. дифференц . диффер. ),( m0i
=
диффер. ),( m0i
=
, ),( m0i
=
),( m0i
=
Ω - регул.
Ω
∈
0
x
Теорема 6. (Теорема Куна-Таккера для задач с линейными ограничениями ).
Пусть (1) является задачей выпуклого программирования, а функция )( xf
0
является непрерывно дифференцируемой. Для того, чтобы точка
x
0
была
решением задачи (1) в случае, когда все ограничения линейны , необходимо
и достаточно , чтобы существовал вектор
yyR
m00
0≥∈,,
такой что точка
mn
RyRxyx ∈∈≥
0000
,,0),( была седловой точкой функции Лагранжа.
Пример 1. Найти решение задачи
0xx
2xxxf
xxxf
21
21
2
2
2
10
1
≥
−≤−−=
→−−=
,
,)(
max)(
Решение. Так как функция
)( xf
0
в задаче является выпуклой (вверх ) и
непрерывно дифференцируемой , воспользуемся теоремами 6 и 3.
Запишем функцию Лагранжа данной задачи
0yxx
xx2yxxyx
1
2
1
211
2
2
2
1
≥
++−+−−=Φ
,,
),(),(
Выпишем условия экстремума этой задачи .
,0)2(
),(
,0)2(
),(
)
02
),(
,02
),(
)
2121
1
1111
1
12
2
11
1
=+−=
Φ
=+−=
Φ
≤+−=
Φ
≤+−=
Φ
xyxx
x
yx
xyxx
x
yx
b
yx
x
yx
yx
x
yx
a
∂
∂
∂
∂
∂
∂
,0)2(
),(
)
,02
),(
)
1211
1
21
1
=++−=
Φ
≥++−=
Φ
yxxy
y
yx
d
xx
y
yx
c
∂
∂
∂
Такая система решается следующим образом: решается система равенств b) и
d), а затем полученные точки подставляются в неравенства а), с) и условия
неотрицательности и проверяются .
Итак, решим систему
Условия Ф . Джона
В точке (x
0
,y
0
)
≥
0
выполняются
условия a)-d)
теоремы 3.
                                            18
   f i (x) −    непрер.                          непрер.    диффер.
  непрер.      дифференц.                                      диффер.            (i =0, m)
 диффер.       (i =0, m) ,                                     (i =0, m)
(i =0, m)       Ω - регул.


  Условия Ф. Джона                                                 В точке (x0,y0) ≥ 0
                                                                     выполняются
                                                                     условия a)-d)
                                          x 0 ∈Ω
                                                                      теоремы 3.

Теорема 6. (Теорема Куна-Таккера для задач с линейными ограничениями).
Пусть (1) является задачей выпуклого программирования, а функция f 0 (x)
является непрерывно дифференцируемой. Для того, чтобы точка x 0 была
решением задачи (1) в случае, когда все ограничения линейны, необходимо
и достаточно, чтобы существовал вектор y 0 ≥0, y 0 ∈R m , такой что точка
( x 0 , y 0 ) ≥0, x 0 ∈R n , y 0 ∈R m была седловой точкой функции Лагранжа.
Пример 1. Найти решение задачи
                                     f 0 ( x) =−x12 −x 22 → max
                                f 1 ( x) =−x1 −x 2 ≤−2,
                       x1 , x 2 ≥0
Решение. Так как функция f 0 (x) в задаче является выпуклой (вверх) и
непрерывно дифференцируемой, воспользуемся теоремами 6 и 3.
Запишем функцию Лагранжа данной задачи
                     Φ ( x, y ) =−x12 −x 22 + y 1 ( −2 +x1 +x 2 ),
                      x1 , x 2 , y 1 ≥0
Выпишем условия экстремума этой задачи.
   ∂Φ( x, y )                   ∂Φ( x, y )
a)            =−2 x1 + y1 ≤0,              =−2 x 2 + y1 ≤0
     ∂x1                           ∂x 2
   ∂Φ( x, y )                             ∂Φ( x, y )
b)            x1 =(−2 x1 + y1 ) x1 =0,               x1 =(−2 x 2 + y1 ) x 2 =0,
     ∂x1                                    ∂x1
   ∂Φ( x, y )
c)            =−2 +x1 +x 2 ≥0,
     ∂y1
   ∂Φ( x, y )
d)            y1 =(−2 +x1 +x 2 ) y1 =0,
      ∂y1
Такая система решается следующим образом: решается система равенств b) и
d), а затем полученные точки подставляются в неравенства а), с) и условия
неотрицательности и проверяются.
Итак, решим систему

Страницы