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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

55
Алгоритм метода секущих плос- костей
Шаг 1. Задать
0
x
(не обязательно допустимое),
ε
(точность попадания в
допустимую область).
Шаг 2.Положить },1,))(()(:{,1
000
1
mibxxxfxfxk
i
T
ii
=≤−∇+=Ω=
Шаг 3. Найти
k
x
- решение задачи линейного программирования
k
T
x
cx
Ω∈
→ max
Шаг 4. Если ε≤−∀
i
k
i
bxfi )(: , то останов
k
x
x
=
*
Шаг 5. Положить
})(:,))(()(:{
1 i
k
ii
Tkk
i
k
ikk
bxfibxxxfxfx >≤−∇+∩Ω=Ω
+
;
k=k+1 . Перейти к шагу 3.
Пример 1. Решить методом секущих плоскостей задачу
0,
928.0)(
12)(
max)(
2
1
2
2
12
2
211
21
≥
≤+=
−≤+−=
+
=
xx
xxxf
xxxf
xxx
ϕ
Решение. Выберем )4,5(
0
=x . Вычислим )2;2()(
21
xxf
−
=
∇
,
)2;6.1()(
12
xxf
=
∇
. Тогда 1682)4;5)(8;2(6)(
21211
−+−=−−−+≈ xxxxxf
T
2028)4;5)(2;8(28)(
21212
−+=−−+≈ xxxxxf
T
Решим графически задачу линейного
программирования
0,
2928
1582
max
21
1
21
21
21
≥
Ω
≤+
≤+−
+
xx
xx
xx
xx
Ее решением является точка
)62.2;97.2(
1
=x . Однако в этой точке
нарушаются первое и второе
ограничение, причем величина
невязок достаточно велика, поэтому
строим отсекающие плоскости :
9)62.2;97.2)(2;75.4(3.12
15)62.2;97.2)(24.5;2(92.0
21
21
≤−−+
≤−−−+
T
T
xx
xx
Добавляем эти ограничения к задаче линейного программирования и
находим следующее
решение
)05.2;52.2(
2
=x , которое уже является
•
1
x
•
•
x*
ϕ
∇
x
2
                                                  55

  Алгоритм метода секущих плос-                                         костей
Шаг 1. Задать x 0 (не обязательно допустимое), ε (точность попадания в
допустимую область).
Шаг 2.Положить k =1, Ω1 ={x : f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T ≤bi , i =1, m}
Шаг 3. Найти x k - решение задачи линейного программирования
                                cx T → max
                                   x ∈Ω k
Шаг 4. Если ∀i : f i ( x k ) −bi ≤ε , то останов x* =x k
Шаг 5. Положить
       Ω k +1 =Ω k ∩ {x : f i ( x k ) +∇ f i ( x k )( x −x k ) T ≤bi , i : f i ( x k ) >bi } ;
       k=k+1 . Перейти к шагу 3.
Пример 1. Решить методом секущих плоскостей задачу
                               ϕ ( x) =x1 +x2 → max
                                     f1 ( x) =−2 x1 +x22 ≤−1
                                     f 2 ( x) =0.8 x12 +2 x2 ≤9
                                     x1 , x2 ≥0
Решение. Выберем x 0 =(5,4) . Вычислим ∇ f 1 ( x) =(−2; 2 x 2 ) ,
∇ f 2 ( x) =(1.6 x1 ; 2) . Тогда f1 ( x ) ≈6 +(−2;8)( x1 −5; x 2 −4) T =−2 x1 +8 x 2 −16

              f 2 ( x ) ≈ 28 + ( 8 ; 2 )( x 1 − 5 ; x 2 − 4 ) T = 8 x 1 + 2 x 2 − 20
                                                    Решим графически задачу линейного
                                                    программирования
                                                                x1 +x2 → max
                                                                −2 x1 +8 x2 ≤15�
                                                                                 � Ω1
                                                                8 x1 +2 x2 ≤29 �
                          x1
                      •                                       x1 , x2 ≥0
                     x2                            Ее решением является точка
                   •
                   •                               x 1 =( 2.97;2.62) . Однако в этой точке
                  x*                               нарушаются первое и второе
  ∇ϕ                                               ограничение, причем величина
                                                   невязок достаточно велика, поэтому
                                                   строим отсекающие плоскости:

                               0.92 +( −2; 5.24)( x1 −2.97; x 2 −2.62) T ≤15
                    12.3 +(4.75; 2)( x1 −2.97; x 2 −2.62) T ≤9
     Добавляем эти ограничения к задаче линейного программирования и
находим следующее решение x 2 =( 2.52; 2.05) , которое уже является

Страницы