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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

49
7. Точка
1
x
принадлежит границе
допустимого множества, второе
ограничение задачи является активным для этой точки , поэтому
{
}
2xI
1
= )( .
8. Составим вспомогательную задачу для определения вектора
1
y :
min→−−
1
2
1
1
y1y6
0y2y
1
2
1
1
≤+
1y1
1
1
≤≤−
1y1
1
2
≤≤− .
Решая графически (симплексным методом) данную задачу линейного
программирования, найдем
−=
3
1
3
2
y
1
, .
9. Определяя
1
α
из соотношения
22
1
2
1
3
1
3
3
2
2
9
2
3
−−+
−
≤
≤
= αα
α
α
α
α
:
minarg
,
получим
2
3
1
=α
.
10. Найдем
()
12
3
1
3
2
2
3
2
3
1x
2
,,, =
−+
=
.
Продолжая данный процесс в качестве точки
3
x
, получим точку
=
2
1
2
5
x
3
,
. Вектор
(
)
00y
3
, = , поэтому
3
x
x
=
*
.
Метод возможных направлений используется также для решения задач
нелинейного программирования более общего вида.
Метод возможных направлений Зойтендейка
Рассмотрим задачу выпуклого программирования вида
min
→
x
f
gxjm
j
(),,≤=01,
где
f
x
и
gx
j
()
- выпуклые дифференцируемые функции. В данном случае
допустимое множество выпукло, поэтому в любой допустимой точке
существует возможное направление
y
. Для того, чтобы в данной задаче
направление
y
было возможным и подходящим в точке
x
, достаточно , чтобы
оно удовлетворяло системе неравенств
∇<fxy
T
()0
(1) 
                                           49
            1
7. Точка x принадлежит границе      допустимого множества, второе
   ограничение задачи является активным для этой точки, поэтому
   I ( x 1 ) ={2}.
8. Составим вспомогательную задачу для определения вектора y 1 :
                                −6 y 11 −1 y 21 → min
                                     y 11 +2 y 21 ≤0
                                     −1 ≤ y 11 ≤1
                              −1 ≤ y 21 ≤1 .
  Решая графически (симплексным методом) данную задачу                линейного
                                   � 2 1�
    программирования, найдем y 1 =� ,− � .
                                    � 3 3�
9. Определяя α 1 из соотношения
                                                   2             2
                                         � 2 �           � 1   1�
                  α 1 = arg min � α −3 �               +� − α − � ,
                          �            3� 3    �          � 3  2�
                            ��     α ≤
                       α:�             2
                               � α ≤9
                                ��     2
                 3
  получим α 1 = .
                 2
                   � 3� 3 � 2 1�
10. Найдем x 2 =� 1, � + � ,− � =(2,1).
                    � 2� 2 � 3 3�
         Продолжая данный процесс в качестве точки x 3 , получим точку
      � 5 1�
x 3 =� , � . Вектор y 3 =(0,0 ), поэтому x * =x 3 .
       � 2 2�
Метод возможных направлений используется также для решения задач
нелинейного программирования более общего вида.
           Метод возможных направлений Зойтендейка
Рассмотрим задачу выпуклого программирования вида
                                           f ( x) → min
                                     g j ( x ) ≤0, j =1, m ,
где f ( x ) и g j ( x ) - выпуклые дифференцируемые функции. В данном случае
допустимое множество выпукло, поэтому в любой допустимой точке
существует возможное направление y . Для того, чтобы в данной задаче
направление y было возможным и подходящим в точке x , достаточно, чтобы
оно удовлетворяло системе неравенств
                                    ∇ f ( x ) y T <0                      (1)

Страницы