Автоматизированное проектирование. Норенков И.П. - 105 стр.

UptoLike

ВУЗ: 

МГТУ им. Баумана | Москва

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

Рубрика: 

N
k+1
= N
k
+ A
k
T
B
k
,
где
A
k
= dX
k
dX
k
T
/(dX
T
dg
k
),
B
k
= N
k
dg
k
dg
k
T
N
k
T
/(dg
k
T
N
k
dg
k
).
Поэтому
k k
N
k+1
= E +
∑
A
i
—
∑
B
i
.
i=0 i=0
Можно показать, что A
i
стремится к K
-1
, (
i —
к E при k→ n, где n — размерность пространства управляемых пара-
метров. Спустя n шагов, нужно снова начинать с N
n+1
= E.
#.4B645+/1. <,D49+> T7,-8./</:. В задачах безусловной оптимизации необходимые условия
представляют собой равенство нулю градиента целевой функции
grad F(X) = 0.
В общей задаче математического программирования (4.1) необходимые условия экстремума, на-
зываемые условиями Куна-Таккера, формулируются следующим образом:
Для того чтобы точка Q была экстремальной точк ой выпуклой задачи математического програм-
мирования (ЗМП), необходимо наличие неотрицательных коэффициентов u
i
, таких, что
u
i
ϕ
i
(Q) = 0, i = 1,2,...m; (4.17)
и при этом соблюдались ограничения задачи, а также выполнялось условие
m L
grad F(Q) +
∑
u
i
grad ϕ
i
(Q) +
∑
a
j
ψ
j
(Q) = 0, (4.18)
i=W j=W
где m — число ограничений типа неравенств, L — то же равенств, коэффициенты a
j
> 0.
За приведенной абстрактной формулировкой условий скрывается достаточно просто понимае-
мый геометрический смысл. Действительно, рассмотрим сначала случай с ограничениями только ти-
па неравенств. Если максимум находится внутри допустимой области R, то, выбирая все u
i
= 0, доби-
ваемся выполнения (4.17); е сли же то чка максимума Q лежит на границе области R, то, как видно из
левой части рис. 4.9, эту точку всегда соответствующим подбором неотрицательных u
i
можно помес-
тить внутрь оболочки, натянутой на градиенты целевой функции F(X) и функций-ограничений ϕ
i
(X).
Наоборот, если точка не является экс-
тремальной, то (4.17) нельзя выпол-
нить при любом выборе положитель-
ных коэффициентов u
i
(см. правую
часть рис. 4.9, где рассматриваемая
точка N лежит вне выпуклой оболочки,
натянутой на градиенты). Учет ограни-
чений типа равенств очевиден, если до-
бавляется последняя из указанных в
(4.18) сумма.
E
.-451 34+,7: <,D49016 T7,-8./</49. Широко известен метод множителей Лагранжа, ори-
ентированный на поиск экстремума при наличии ограничений типа равенств
ψ
(X) = 0, т.е. на реше-
ние задачи
extr F(X), (4.19)
X∈R
где R = { X |
ψ
(X) = 0 }.
Cуть метода заключается в преобразовании задачи условной оптимизации (4.19) в задачу безус-
ловной оптимизации с помощью образования новой целевой функции
L
Ф(N,V) = F(X) +
∑
λ
i
ψ
i
(X),
i=W
%!#*%!#&F*:,$* $I*:+*
F*)&* :&)#*'! +($*,#)KH (*L*)&M
5@!"! 4
&.+.)$(*),$" . ! "#$%!#&'&($"!))$* +($*,#&($"!)&*
105
%+,. 4.9. К пояснению условий Куна-Таккера
 5@!"! 4                                  %!#*%!#&F*:,$*        $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

          Nk+1= Nk + Ak TBk,
где
          Ak = dXk dXk T / (dXTdgk),
          Bk= Nk dgk dgkT NkT / (dgkTNk dgk).
Поэтому
                       k              k
          Nk+1 = E +∑ Ai — ∑ Bi.
                     i=0       i=0
      Можно показать, что Ai стремится к K-1, (i — к E при k→ n, где n — размерность пространства управляемых пара-
метров. Спустя n шагов, нужно снова начинать с Nn+1 = E.
     #.4B645+/1. <,D49+> T7,-8./ 0.
      За приведенной абстрактной формулировкой условий скрывается достаточно просто понимае-
мый геометрический смысл. Действительно, рассмотрим сначала случай с ограничениями только ти-
па неравенств. Если максимум находится внутри допустимой области R, то, выбирая все ui = 0, доби-
ваемся выполнения (4.17); если же точка максимума Q лежит на границе области R, то, как видно из
левой части рис. 4.9, эту точку всегда соответствующим подбором неотрицательных ui можно помес-
тить внутрь оболочки, натянутой на градиенты целевой функции F(X) и функций-ограничений ϕi(X).
Наоборот, если точка не является экс-
тремальной, то (4.17) нельзя выпол-
нить при любом выборе положитель-
ных коэффициентов ui (см. правую
часть рис. 4.9, где рассматриваемая
точка N лежит вне выпуклой оболочки,
натянутой на градиенты). Учет ограни-
чений типа равенств очевиден, если до-
бавляется последняя из указанных в
(4.18) сумма.                                      %+,. 4.9. К пояснению условий Куна-Таккера
      E.-451 34+,7: <,D49016 T7,-8./

Страницы