- •ВСТУП
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Алгоритм обчислення градієнту цільової функції
- •4 Завдання
- •6 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Завдання
- •5 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Завдання
- •5 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Завдання
- •5 Контрольні запитання
- •ЛАБОРАТОРНА РОБОТА № 5. ДОСЛІДЖЕННЯ МЕТОДІВ ОДНОМІРНОГО ПОШУКУ
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Алгоритм пошуку методом золотого перетину
- •4 Завдання
- •6 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Завдання
- •5 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Вирішення задачі за допомогою пакету NetALLTED
- •4 Завдання
- •6 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Вирішення задачі за допомогою пакету NetALLTED
- •4 Завдання
- •6 Контрольні запитання
- •1 Мета роботи
- •2 Короткі теоретичні відомості
- •3 Вирішення задачі за допомогою пакету NetALLTED
- •4 Завдання
- •6 Контрольні запитання
- •А.1 Опис вхідної мови NetALLTED
- •А.1.1.1 Алфавіт вхідної мови
- •А.1.1.2 Лексичний склад вхідної мови
- •А.1.1.3 Ідентифікатори та ключові слова
- •А.1.1.4. Імена
- •А.1.1.5. Числа
- •А.1.1.6 Коментарі
- •А.1.1.7 Структура вхідного потоку даних
- •А.2 Аналіз статичних режимів (DC-метод)
- •А.3 Оптимізація
- •А.4.1 Аналіз чутливості (SA)
- •А.4.2 Аналіз найгіршого випадку
- •А.5 Призначення оптимальних допусків
- •А.5.1 Запуск процедури
- •СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
ЛАБОРАТОРНА РОБОТА № 9. ВИКОРИСТАННЯ МЕТОДІВ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ ДЛЯ
ВИРІШЕННЯ ПРАКТИЧНИХ ЗАДАЧ
1 Мета роботи
Ознайомитись з використанням методів нелінійного програмування з обмеженнями для вирішення практичних задач в галузі електроніки.
2 Короткі теоретичні відомості
До задач нелінійного програмування зводиться багато практичних задач, зокрема задача призначення оптимальних допусків, яка в загальному випадку, формулюється як:
|
|
|
|
|
|
|
n |
1 |
|
|
|
|
|
|
|
|
|
|
|
min ∑ |
|
|
|
(9.1) |
|||
|
|
2ti |
|
|
|||||||||
|
|
|
|
|
|
t |
i=1 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
при умовах |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
||||
|
|
∑ |
|
Sij |
|
ti − d j + 0.5g 2j |
= 0, j =1(1)m |
|
|
|
|||
|
|
|
|
|
|
|
|||||||
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
де d j – задані |
припустимі відхилення |
j -ї вихідної |
характеристики; |
||||||||||
g =[g1 ,..., gm ]T |
– вектор додаткових змінних, що перетворює обмеження |
||||||||||||
типу нерівностей до обмежень у вигляді рівностей; |
Sij – елемент матриці |
||||||||||||
чутливості; |
ti – |
значення оптимального |
допуску |
на |
i -й елемент; |
n – |
|||||||
кількість варійованих змінних; m – кількість вихідних характеристик, |
на |
||||||||||||
які накладаються обмеження. |
|
|
|
|
|
|
|
||||||
75
Розглянемо алгоритм вирішення задачі (9.1) за допомогою одного з варіантів модифікованого методу множників Лагранжа. Використовуючи цей підхід, координати нової робочої точки розраховуються як:
|
t(k +1) = t(k ) +λ(k)оп t(k ) |
(9.2) |
де λ(k)оп – розмір кроку, а |
|
|
|
t(k ) = −[Ftt(k ) ]−1 [Φ′t (k ) + N (μ(k ) + μ(k ) )] |
(9.3) |
В (9.3) |
N – представляє собою якобіан обмежень задачі (9.1); μ(k ) |
та μ(k ) – |
вектор |
множників Лагранжа та його прирости; Φ′t (k ) – вектор |
похідних |
Φ(x,t) ; |
Ftt(k ) – матриця других похідних лагранжіана задачі (9.1), який має |
|
вигляд:
n |
1 |
m |
|
n |
|
|
|
2 |
|
|
|
|
|
|
|||||||||
L(t, μ, g) = ∑ |
|
+ ∑μj |
∑ |
|
S ji |
|
ti − d j + 0.5g j |
. |
(9.4) |
||
2ti |
|||||||||||
i=1 |
j=1 |
i=1 |
|
|
|
|
|
|
|||
Визначимо значення всіх складових правої частини виразу (9.3).
|
|
|
|
|
|
|
|
−1 |
|
|
|
|
|
1 |
|
1 |
T |
|||||||
Для Лагранжіана (9.4) |
|
|
|
[Ftt(k ) ] |
= diag 3 (t(k ) ), |
Φ′t (k ) = − |
,...,− |
|
, а |
|||||||||||||||
2 |
2 |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2t |
|
2t |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
||||
матриця N має вигляд |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
S |
|
|
|
L |
|
|
S |
m1 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
N = |
|
|
M |
|
|
|
L |
M |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
S |
|
|
|
L |
|
S |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
1n |
|
|
|
|
|
|
|
|
mn |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
76
Значення елементів матриці N не залежать від змінних t, μ, g і
залишаються постійними впродовж усього процесу пошуку оптимальних значень t* .
Для визначення значень μ(k ) |
запишемо умови Куна-Таккера задачі |
|||||
(9.1) |
|
|
|
|
|
|
Φ′t + Nμ = 0 |
|
|
|
|
||
|
|
|
|
(9.5) |
||
G +0.5diag(g)g = 0 |
||||||
|
|
|
|
|
||
diag(g)μ = 0 |
|
|||||
Де |
|
|
|
|
||
n |
S1i |
|
n |
Smi |
|
T |
G = ∑ |
ti −d1 ,K,∑ |
ti −dm |
||||
i=1 |
|
|
i=1 |
|
||
Вирішивши (9.5) методом Ньютона прийдемо до системи рівнянь
[Ftt(k ) ]−1 |
t(k ) |
+ N |
μ(k ) = −(Φ′t (k ) + Nμ(k ) ) |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
g (k ) = −G − 0.5diag(g (k ) )g (k ) |
(9.6) |
||||||||
N T t(k ) + diag(g (k ) ) |
||||||||||||||||
|
(k ) |
) |
g |
(k ) |
+ diag(g |
(k ) |
) |
μ |
(k ) |
= −diag(g |
(k ) |
) |
|
|||
diag(μ |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З (9.6) витікає |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
μ(k ) = A−1diag(μ(k ) )(Z +diag(g (k ) )g (k ) ) |
|
(9.7) |
||||||||||||||
gi(k ) = |
|
− g |
(k ) (μ(k ) + |
|
μ |
(k ) ) |
, |
i =1(1)m |
|
(9.8) |
||||||
|
|
|
i |
i |
|
|
i |
|
|
|||||||
|
|
|
|
(k ) |
|
|
|
|
|
|||||||
|
|
|
|
|
|
μ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
77 |
|
|
|
|
де
A = −diag(μ(k ) )N T [Ftt(k ) ]−1 N − diag 2 (g (k ) )
Z = −G −0.5diag(g (k ) )g (k ) + N T [Ftt(k ) ]−1 Φi(k ) |
+ N T [Ftt(k ) ]−1 Nμ(k ) |
||
При практичних обрахунках значення |
μ(k ) |
доцільно визначати не за (9.7), |
|
а вирішенням лінійної системи рівнянь виду |
|
||
A μ(k ) = Z′ |
|
|
(9.9) |
де |
|
|
|
Z′ = diag(μ(k ) )(Z + diag(g(k ) )g(k ) ) |
|
||
Якщо gi(k ) ≠ 0 і μi(k ) ≠ 0 , i =1(1)m , то |
система рівнянь |
(9.9) завжди має |
|
розв’язок, т.я. при таких умовах матриця A не може бути особливою. |
|||
Визначив таким чином значення t(k ) , μ(k ) , g(k ) |
і використав (9.2), |
||
можливо оцінити значення t(k+1) . При цьому величина λ(k)оп обчислюється вирішенням задачі
λ(k)оп |
= argmin L(t(k) +α t(k) , μ(k) +α μ(k) ,g(k) +α g (k) ) |
(9.10) |
|
α |
|
Таким чином задача (9.10) може бути вирішена за допомогою стандартних методів пошуку мінімуму однопараметричних функцій.
В якості критеріїв скінчення пошуку вирішення задачі (9.1) використовуються наступні співвідношення:
78