Міністерство освіти і науки, молоді та спорту України Національний Технічний Університет України «Київський Політехнічний Інститут» Навчально-науковий комплекс
«Інститут прикладного системного аналізу» Кафедра системного проектування
«МЕТОДИ ОПТИМІЗАЦІЇ»
Методичні вказівки до виконання лабораторних робіт для студентів напряму підготовки 6.050101 «Комп'ютерні науки», спеціальностей 8.05010102 «Інформаційні технології проектування» та 8.05010103 «Системне проектування» денної та заочної форм навчання
Склали: доц. БОБІН ВІКТОР ВАСИЛЬОВИЧ доц. ЛАДОГУБЕЦЬ ВОЛОДИМИР ВАСИЛЬОВИЧ
доц. ФІНОГЕНОВ ОЛЕКСІЙ ДМИТРОВИЧ
Київ - 2011 р.
Методи оптимізації : Методичні вказівки до виконання лабораторних робіт для студентів напряму підготовки 6.050101 «Комп'ютерні науки», спеціальностей 8.05010102 «Інформаційні технології проектування» та 8.05010103 «Системне проектування» денної та заочної форм навчання / Укл. В.В. Бобін, В.В. Ладогубець, О.Д. Фіногенов. – К. : НТУУ «КПІ», 2011 р. – 128 c.
Рекомендовано Методичною радою НТУУ «КПІ»
(Протокол № 5 від 19.01.2012 р.)
Укладачі: Бобін Віктор Васильович, канд. техн. наук, Ладогубець Володимир Васильович, канд. техн. наук, Фіногенов Олексій Дмитрович, канд. техн. наук
Відповідальний редактор: А.І. Петренко, д.т.н., проф..
Рецензент: В.П. Денисюк, д.ф.-м.н., проф..
ЗМІСТ |
|
ВСТУП.................................................................................................................. |
4 |
ЛАБОРАТОРНА РОБОТА № 1. Чисельне визначення градієнту цільової |
|
функції.................................................................................................................. |
6 |
ЛАБОРАТОРНА РОБОТА № 2. Чисельне визначення елементів матриці |
|
Гессе цільової функції ...................................................................................... |
17 |
ЛАБОРАТОРНА РОБОТА № 3. Дослідження цільової функції за |
|
допомогою ліній однакового рівня.................................................................. |
22 |
ЛАБОРАТОРНА РОБОТА № 4. Дослідження цільової функції за |
|
допомогою поверхонь....................................................................................... |
28 |
ЛАБОРАТОРНА РОБОТА № 5. Дослідження методів одномірного пошуку |
|
............................................................................................................................. |
32 |
ЛАБОРАТОРНА РОБОТА № 6. Алгоритми знаходження інтервалу |
|
невизначеності................................................................................................... |
46 |
ЛАБОРАТОРНА РОБОТА № 7. Використання методів одномірного |
|
пошуку для вирішення практичних задач ...................................................... |
51 |
ЛАБОРАТОРНА РОБОТА № 8. Використання методів безумовної |
|
багатопараметричної оптимізації для вирішення практичних задач........... |
60 |
ЛАБОРАТОРНА РОБОТА № 9. Використання методів нелінійного |
|
програмування для вирішення практичних задач.......................................... |
75 |
ДОДАТОК А. Опис вхідної мови та видів аналізу NetALLTED ................. |
90 |
ДОДАТОК Б. Ряди номіналів резисторів..................................................... |
124 |
СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ.......................................... |
127 |
3
ВСТУП
Дисципліна «Методи оптимізації» належить до циклу професійно орієнтованих дисциплін і базується на знанні дисциплін: «Математичний аналіз», «Алгебра та геометрія», «Дискретна математика», «Чисельні методи». Матеріал курсу використовується як самостійно так і у курсах «Моделювання складних систем» та «Проектування автоматизованих інформаційних систем». Програми, що розроблені при виконанні 1,2,5 та 6-ої лабораторних роботах, є складовими частинами програми, що розробляється при виконанні РГР або курсового проекту.
Метою дисципліни є вивчення класичних методів та сучасних чисельних методів оптимізації для розв'язування широкого спектру задач оптимізації. Матеріал курсу покликаний прищеплювати студентам знання та вміння вирішувати задачі оптимізації проектно-конструкторських розробок та прийняття рішень методами обчислювальної математики.
Внаслідок вивчення предмету студенти повинні:
знати: провідні особливості методів оптимізації, умови їх використання, можливості адаптації до конкретних задач;
вміти: проаналізувати поставлену задачу, обрати найбільш ефективний для її розв’язку метод, реалізувати обраний метод та отримати практичні результати.
мати навички проектування пристроїв за заданими критеріями оптимальності.
Лабораторні роботи орієнтовані на студентів-бакалаврів із спеціальності 6.050101 «Комп'ютерні науки». Роботи мають дослідницький характер. Для полегшення підготування студентів до лабораторних робіт у методичних вказівках наведено необхідні
4
довідникові дані і матеріали та розібрано приклади, розглянуто методику підготування завдання для взаємодії з пакетом NetALLTED. Вважається за необхідне наявність у студентів знань з обчислювальної та дискретної математики, з теорії електронних кіл та з питань аналогової та цифрової схемотехніки тощо [1-7]. Бажано також, щоб лабораторні роботи стимулювали подальше поглиблене вивчення студентами теоретичного матеріалу [8-17] та сприяли оволодінню українською науково-технічною термінологією [7-10].
5
ЛАБОРАТОРНА РОБОТА № 1.
ЧИСЕЛЬНЕ ВИЗНАЧЕННЯ ГРАДІЄНТУ ЦІЛЬОВОЇ ФУНКЦІЇ
1 Мета роботи
Ознайомитись з методами обчислення на ЕОМ частинних похідних функцій (зокрема градієнту цільової функції (ЦФ)) та факторами, що впливають на похибку обчислень.
2 Короткі теоретичні відомості
Градієнт – це вектор частинних похідних, що вказує у напрямок
найбільшого зросту функції. |
|
|
|
|
|
|||||||||||
Якщо f (x) |
- цільова |
функція, де x = [x1, x2 ,..., xn ]T - n-мірний |
вектор |
|||||||||||||
змінних, то скорочене розкладання у ряд Тейлора в околиці точки |
x має |
|||||||||||||||
вигляд: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x + h)≈ f (x)+ gT (x)h + |
1 |
hT H (x)h +... |
(1.1) |
|||||||
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
де |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
,..., ∂f (x) |
T |
|
|
- градієнт цільової функції; |
|
|||||
g(x) = ∂f (x) , ∂f (x) |
|
|
|
|
||||||||||||
|
∂x |
|
∂x |
∂x |
|
|
|
|
|
|
|
|
||||
|
1 |
|
2 |
|
n |
|
|
|
|
|
|
|
||||
h = [h1,h2 |
,...,hn ]T |
|
|
|
|
|
|
|
- вектор прирощення змінних; |
|
||||||
|
∂ 2 f (x) |
................. |
∂ 2 f (x) |
|
|
|
|
|||||||||
|
∂x ∂x |
∂x ∂x |
|
|
- матриця других похідних (матриця |
|||||||||||
|
|
|
1 |
1 |
|
|
|
|
1 |
|
n |
|
||||
H (x) = .................................... |
|
|
|
Гессе). |
|
|||||||||||
|
∂ |
2 |
f (x) |
|
|
∂ |
2 |
|
|
|
|
|
||||
|
|
................. |
|
f (x) |
|
|
|
|
||||||||
|
∂x |
|
∂x |
∂x |
∂x |
|
|
|
|
|
|
|||||
n |
|
|
|
|
|
|
|
|||||||||
|
|
|
1 |
|
|
|
|
n |
|
n |
|
|
|
|
||
6
При обчисленні градієнту на ЕОМ для визначення похідних використовують методи правих, лівих та центральних кінцевих різниць.
Метод правої кінцевої різниці
Розглянемо на прикладі функції однієї змінної f (x) її розкладання у ряд Тейлора «праворуч» від точки x :
f (x + h) ≈ f (x) + hf ′(x) + |
h2 |
f ′′(x) + |
h3 |
f ′′′(x) +... + |
hn |
(n) |
|
(1.2) |
|
|
|
|
f |
|
(x) |
||||
2! |
3! |
n! |
|
||||||
Якщо обмежитись лінійною апроксимацією, тобто першими двома членами розкладу (1.2), а саме:
f (x + h) ≈ |
′ |
(1.3) |
f (x) + hf (x) |
то з (1.3) отримаємо формулу правої кінцевої різниці для обчислення першої похідної:
′ |
f (x + h) − f (x) |
(1.4) |
|
f (x) ≈ |
|
||
h |
|||
|
|
Методична похибка цієї формули має порядок h[Ο(h)].
Метод лівої кінцевої різниці
Скорочене розкладання у ряд Тейлора функції f (x) «ліворуч» від точки x має вигляд:
7
2 |
3 |
n |
|
f (x − h) ≈ f (x) − hf ′(x) + h2! |
f ′′(x) − h3! |
f ′′′(x) +... + (−1)n hn! f (n) (x) |
(1.5) |
Аналогічно до (1.3), обмежившись лінійною апроксимацією функції f (x) :
f (x − h) ≈ |
′ |
(1.6) |
f (x) − hf (x) |
отримаємо з (1.6) формулу к лівої кінцевої різниці для обчислення першої похідної:
′ |
f (x) − f (x − h) |
(1.7) |
|
f (x) ≈ |
|
||
h |
|||
|
|
Методична похибка цієї формули також має порядок h[Ο(h)].
! |
Суттєвим недоліком методів правої та лівої кінцевих різниць є |
|||||||||
значна |
похибка обчислень. Розглянемо значення похибки на |
|||||||||
|
наступному прикладі: |
|||||||||
|
1) f (x) = x3 , |
|
|
x =1, |
h = 0.1. |
|||||
|
Аналітичний розрахунок похідної: |
|||||||||
|
′ |
= (x |
3 |
) |
′ |
= 3x |
2 |
|
|
= 3 |
|
|
|
||||||||
|
f (x)x=1 |
|
|
|
|
x=1 |
||||
|
|
|
|
|
|
|
|
|
|
|
Розрахунок за формулою лівої кінцевої різниці:
f ′(x)x=1,h=0.1 = |
f (x) − f (x − h) |
|
|
= |
f (1) − f (1−0.1) |
= |
13 −0.93 |
= |
1−0.729 |
= 2.71 |
|
|
|||||||||
h |
|
x=1,h=0.1 |
0.1 |
0.1 |
0.1 |
|||||
|
|
|
|
|
|
Розрахунок за формулою правої кінцевої різниці:
f ′(x)x=1,h=0.1 = |
f (x + h) |
− f (x) |
|
|
= |
f (1+ 0.1) − f (1) |
= |
1.13 − |
13 |
= |
1.331−1 |
= 3.31 |
|
||||||||||||
h |
|
|
x=1,h=0.1 |
0.1 |
0.1 |
|
0.1 |
|||||
|
|
|
|
|
|
|
|
Як видно із результатів розрахунків, значення градієнту, що отримані за
8
допомогою методів лівої та правої кінцевих різниць значно відрізняються від дійсного. Варто відмітити, що метод лівої кінцевої різниці дав значення менше за дійсне, а правої більше. Тому, вочевидь, є цікавим поєднати результати обох методів, щоб отримати середнє значення, яке буде мати меншу похибку.
Метод центральної кінцевої різниці Головна ідея методу – поєднання методів лівої та правої кінцевих
різниць. Значення градієнту за методом центральної кінцевої різниці обчислюється, як середнє арифметичне значень градієнту за методами лівої та правої кінцевих різниць:
′ |
fл′(x) + fп′(x) |
(1.8) |
|
f (x) ≈ |
|
||
2 |
|||
|
|
де fл′(x) - значення градієнту за методом лівої кінцевої різниці (1.7), fп′(x) -
значення градієнту за методом правої кінцевої різниці (1.4).
Для методу правої кінцевої різниці візьмемо перші чотири члени розкладу у ряд Тейлора (1.2):
f (x + h) ≈ f (x) + hf ′(x) + h2 f ′′(x) + h3 f ′′′(x) 2! 3!
Звідси знайдемо значення градієнту:
|
|
h2 |
|
′′ |
h3 |
|
′′′ |
|
|
f (x + h) − f (x) − |
2! f |
3! f |
|
||||
fп′(x) = |
(x) − |
(x) |
(1.9) |
|||||
|
h |
|
|
|
||||
|
|
|
|
|
|
|
||
9
Аналогічно для методу лівої кінцевої різниці:
|
|
h2 |
|
′′ |
h3 |
|
′′′ |
|
|
f (x) − f (x + h) + |
2! f |
3! f |
|
||||
fл′(x) = |
(x) − |
(x) |
(1.10) |
|||||
|
h |
|
|
|
||||
|
|
|
|
|
|
|
||
Підставивши (9) та (10) в (8), отримаємо:
fЦ′ (x) = |
fл′(x) + fп′(x) |
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x) − f (x − h) + |
h2 |
′′ |
|
h3 |
′′′ |
|
|
|
h2 |
′′ |
h3 |
′′′ |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
= |
2! f (x) − |
3! f (x) + f (x + h) − f (x) |
− 2! f (x) − |
3! f (x) |
= |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
2h |
|
|
|
|
|
|
|
|
|
|
|
|
|
2h3 |
′′′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x + h) − f (x − h) − |
3! |
|
|
|
|
f (x + h) − f (x − h) |
|
h2 |
|
|
|
|
||||||
|
f (x) |
|
|
|
|
|
|
|
|||||||||||
= |
|
|
|
|
|
|
|
|
|
= |
|
|
− |
6 f ′′′(x) |
|
|
|
||
|
2h |
|
|
|
|
|
|
|
|
2h |
|
|
|
||||||
Залишаючи для розрахунку лише обчислення значень функції, отримаємо формулу для обчислення градієнту за методом центральних різниць:
fЦ′ (x) ≈ |
f (x − h) − f (x + h) |
(1.11) |
|
2h |
|||
|
|
Методична похибка цієї формули має порядок h2 [Ο(h2 )].
Примітка!
Обчислимо значення градієнту за допомогою методу «центральних» кінцевих різниць для попереднього прикладу
f (x) = x3 , x =1, h = 0.1.
10
f ′(x)x=1,h=0.1 = |
f (x + h) − f (x − h) |
|
|
= |
f (1+ 0.1) − f (1−0.1) |
= |
1.13 −0.93 |
= |
|
|
|||||||
2h |
|
x=1,h=0.1 |
2 0.1 |
0.2 |
||||
|
|
|
|
|
= 1.331−0.729 = 3.01 0.2
Таблиця 1.1 – Результати розрахунку градієнту
|
|
|
|
Аналітичний |
|
|
Методи кінцевої різниці |
||||||||||||||||
|
|
|
|
|
|
|
метод |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
лівої |
|
|
правої |
|
|
центральної |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Значення |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
2.71 |
|
|
3.31 |
|
|
|
3.01 |
|
|
градієнту |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Абсолютна |
|
|
|
|
0 |
|
|
|
|
|
|
0.29 |
|
|
0.31 |
|
|
|
0.01 |
|||
|
похибка |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Відносна |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
9.67 |
|
|
10.33 |
|
|
|
0.33 |
|
|
похибка, % |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Варто відмітити, що алгоритми обчислення похідних на ЕОМ |
||||||||||||||||||||||
|
належать |
до |
класу |
нестійких. Взявши до уваги, що |
значення функцій |
||||||||||||||||||
|
f (x + h) |
і |
f (x − h) |
обчислюються з інструментальними похибками ε1 і |
|||||||||||||||||||
|
ε2 відповідно, одержимо: |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
~ |
|
|
|
|
|
|
f (x + h) + ε1 − f (x − h) − ε2 |
|
ε1 − ε2 |
, |
||||||||
|
|
|
|
|
|
|
f |
′(x) ≈ |
|
|
|
|
|
|
= f ′(x) + |
2h |
|
||||||
|
|
|
|
|
|
|
|
2h |
|
|
|
||||||||||||
|
тобто похибка |
|
|
ε1 − ε2 |
|
|
≤ |
2ε |
= |
ε |
прямує до нескінченності, якщо h → 0 . |
||||||||||||
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
2h |
|
|
|
2h |
h |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Це |
входить |
у |
протиріччя з |
методичною похибкою. Тому при |
||||||||||||||||||
реалізації на ЕОМ алгоритмів обчислення похідних функцій (і перших і других) при виборі значення прирощення h треба знаходити компроміс.
11