ГРАДІЄНТНИЙ МЕТОД ЧИСЛОВОЇ ОПТИМІЗАЦІЇ.. Методичні вказівки до лабораторної роботи з Математичні методи дослідження операцій. Робота № 400197

Перехід до торгівельного партнера Binance

ГРАДІЄНТНИЙ МЕТОД ЧИСЛОВОЇ ОПТИМІЗАЦІЇ.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Інститут комп’ютерних наук та інформаційних технологій

Факультет:

Не вказано

Кафедра:

Автоматизовані Системи Управління

Інформація про роботу

Рік:

2008

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Математичні методи дослідження операцій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 “ГРАДІЄНТНИЙ МЕТОД ЧИСЛОВОЇ ОПТИМІЗАЦІЇ ” з дисциплін “Математичні методи дослідження операцій” і “Методи оптимізації та дослідження операцій” для студентів базових напрямків “Комп’ютерні науки” та “Легка промисловість” стаціонарної і заочної форм навчання Затверджено на засіданні кафедри автоматизованих систем управління Протокол № 6 від 13 листопада 2008 року Львів – 2008 Методичні вказівки до лабораторної роботи № 6 з дисциплін “Математичні методи дослідження операцій” та “Методи оптимізації та дослідження операцій” для студентів базових напрямків “Комп’ютерні науки” і “Легка промисловість” стаціонарної і заочної форм навчання / Укл. Я.П. Романчук, А.М. Ковальчук. – Львів: Видавництво національного університету “Львівська політехніка”, 2003. – 8 с. Укладачі: Романчук Я.П., кад. фіз.-мат. наук, доц. Ковальчук А.М., ст. викладач. Відповідальна за випуск: Шпак З.Я. Рецензент: Вальковський В.О., д-р техн. наук, проф. ЛАБОРАТОРНА РОБОТА № 6 Тема: Градієнтний метод числової оптимізації. Мета роботи: Навчитися знаходити точку оптимуму функції багатьох змінних на основі використання ітераційного градієнтного методу. Завдання: Для вказаного індивідуального завдання побудувати блок-схему (алгоритм), реалізувати його на одній з мов програмування та відшукати оптимальний розв’язок задачі. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Лабораторна робота базується на лекційному матеріалі з курсів “Математичні методи дослідження операцій” (ММДО) і “Методи оптимізації та дослідження операцій” (МОДО), задачах, методах і алгоритмах, наведених у відповідних збірниках і довідниках. Градієнтні методи належать до наближених числових методів розв’язування задач нелінійного програмування, оскільки дають точний розв’язок за нескінченне і лише в окремих випадках за скінченне число кроків. З їх використанням можна розв’язувати будь-яку задачу нелінійного програмування, знаходячи, як правило, лише локальний екстремум. Тому застосування цих методів дає найбільший ефект для розв’язування задач випуклого програмування, де локальний екстремум є одночасно і глобальним. Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінної х відсутні. Пошук екстремального значення функції f(х) можна починати з будь-якого допустимого розв’язку, наприклад, з точки хk = (x1k; ...; хпk). Градієнтом f(x) функції f(х) в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто EMBED Equation.3 Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції f (х). Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої EMBED Equation.3. (1) де k – числовий параметр, від величини якого залежить довжина кроку переміщення EMBED Equation.3. Величина k, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції EMBED Equation.3 (2) Чергову точку хk+1 визначаємо після обчислення параметру k (для цього підставляємо значення k в формулу (1) на пошуковій траєкторії). В цій ( хk+1 ) точці знову знаходимо градієнт, а рух відбувається далі по прямій хk+2 = хk+1 + k+1f(xk+1) у напрямку нового градієнту f (xk+2) до точки хk+2, в якій досягається найбільше значення функції f(х) в цьому напрямку і т.д. Розв’язування триватиме доти, поки не буде досягнута точка х*, в якій градієнт функції дорівнює нулю. В цій точці х* цільова функція f (х*) і буде набувати максимального значення. ПРИКЛАДИ Приклад 1. Нехай потрібно визначити точку максимуму функції EMBED Equation.3, коли процес розв’язування розпочинається з точки x0 = (4;4). Розв’язування. Знайдемо частинні похідні функції f(x) EMBED Equation.3; EMBED Equation.3. Градієнт функції в точці х0 буде EMBED Equation.3. Перемістимось з точки х0 вздовж градієнту  f(x0) в нову точку х1: х1 = (4; 4) + 0 (–6; 4) = (4 – 6 0; 4 – 4 0). Градієнт функції в точці х1 дорівнює f(x1) = [2 – 2 (4 – 60); 4 – 2 (4 – 40)] = (– 6 +120; – 4 + 80). З необхідної умови екстремуму одержуємо рівняння EMBED Equation.3, звідки EMBED Equation.3= 0,5. ОскількиEMBED Equation.3, то знайдене значення x0 є точкою максимуму функції f (x0). Визначимо наступну точку на пошуковій траєкторії х1 = (4 – 6·0,5; 4 – 4·0,5) = (1; 2) і f (x0) = (2 – 2·1; 4 – 2·2) = (0; 0). Звідси робимо висновок про те, що х1 = (1; 2) є точкою, в якій цільова функція досягає максимального значення f (х1) = 2·1+ 4·2 – 1– 4 = 5 (в початковій точці f (х0) = – 8). На мал. 1 наведена графічна інтерпретація даної задачі. Мал. 1. Тепер розглянемо випадок розв’язування задачі нелінійного програмування з обмеженнями. Припустимо, що задача полягає в наступному: необхідно знайти максимум функції f(х) за обмежень EMBED Equation.3, EMBED Equation.3, (3) EMBED Equation.3 ,EMBED Equation.3. Крім того, будемо вважати, що функція f(х) є ввігнутою диференційовною функцією. При розв’язуванні подібних задач трапляються два випадки: 1) цільова функція має єдиний екстремум, і він знаходиться всередині області допустимих розв’язків. Тоді процес розв’язування задачі (пошук оптимальної точки х*) нічим не відрізняється від уже розглянутого; 2) цільова функція набуває свого екстремального значення в точці, що знаходиться на границі допустимої області. В цьому випадку послідовність розв’язування задачі наступна. Якщо початкова точка хk лежить всередині допустимої області (всі обмеження виконуються як строгі нерівності), то переміщуватися потрібно в напрямку градієнту. Але координати чергової точки EMBED Equation.3 повинні задовольняти обмеженням (3), тобто повинні виконуватись нерівності EMBED Equation.3 EMBED Equation.3 (4) Розв’язуючи систему (4) лінійних нерівностей, знаходимо проміжок EMBED Equation.3 допустимих значень параметру EMBED Equation.3, при яких точка x1 буде належати допустимій області. Значення EMBED Equation.3, яке одержується в результаті розв’язування рівняння (2) EMBED Equation.3, повинно належати проміжку EMBED Equation.3. Якщо значення EMBED Equation.3 виходить за межі проміжку, то за EMBED Equation.3 приймається EMBED Equation.3. При цьому чергова точка пошукової траєкторії опиняється на граничній гіперплощині, що відповідає нерівності системи (4), виходячи з якої при розв’язанні системи отримано значення EMBED Equation.3. Якщо початкова точка хk лежить на граничній гіперплощині (або чергова точка пошукової траєкторії опинилась на граничній траєкторії), то напрямок переміщення визначається із розв’язку наступної допоміжної задачі математичного програмування: EMBED Equation.3 (5) EMBED Equation.3 (6) для тих і, при яких EMBED Equation.3, (7) EMBED Equation.3, (8) де EMBED Equation.3; EMBED Equation.3. Умова (7) визначає належність точки хk границі допустимої області. Умова (6) означає те, що переміщення з точки хk по вектору rk буде відбуватися всередину допустимої області або по її границі, а умова (8) необхідна для обмеження величини rk. Для наступної точки пошукової траєкторії EMBED Equation.3 знаходиться значення параметра EMBED Equation.3. При цьому використовується необхідна умова екстремуму: EMBED Equation.3. Процес розв’язування припиняється при досягненні точкиEMBED Equation.3, в якій EMBED Equation.3. Приклад 2. Максимізувати EMBED Equation.3 за таких обмежень EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Оптимізаційний пошук починається з точки х0 = (1; 0,5). Розв’язування. Точка x0 = (1; 0,5) лежить всередині допустимої області й f(х0) = 1,75. За напрямок переміщення в наступну точку x1 приймаємо напрямок градієнту EMBED Equation.3. Градієнт у точці х0 дорівнює EMBED Equation.3. Виходячи з цього, можна записати координати наступної точки EMBED Equation.3. Визначимо проміжок допустимих значений для параметру EMBED Equation.3, при яких точка x1 буде належати допустимій області. В цьому випадку система нерівностей (4) має вигляд EMBED Equation.3 З розв’язку цієї системи знаходимо проміжок EMBED Equation.3. Розв’язавши рівняння EMBED Equation.3, визначимо значення параметру EMBED Equation.3, при якому приріст функції EMBED Equation.3досягає найбільшої величини. Але значення EMBED Equation.3не належить проміжкуEMBED Equation.3, тому приймаємо EMBED Equation.3. Нова точка x1 = (1,36; 0,95) знаходиться на граничній прямій, яка визначається другим обмеженням–нерівністю (тою нерівністю, якій відповідає значення EMBED Equation.3). В точці x1 значення функціїEMBED Equation.3. Оскільки точка х1 лежить на граничній прямій, то напрямок переміщення в наступну точку х2 визначаємо за вектором r1 (рух в напрямку градієнта виводить з допустимої області). Для визначення координат вектора r1 запишемо допоміжну задачу (5) – (8): максимізувати EMBED Equation.3 за обмежень EMBED Equation.3; EMBED Equation.3. Система рівнянь цієї задачі має два розв’язки: (0,5568;– 0,8352) і (– 0,5568; 0,8352). Підставляючи ці розв’язки у функцію EMBED Equation.3, одержуємо, що максимальне значення функції EMBED Equation.3 і досягається при (– 0,5568; 0,8352), тобто переміщуватися з х1 треба вздовж вектору r1 = (– 0,5568; 0,8352) по другій граничній прямій (мал. 2). Координати наступної точки х2 дорівнюють EMBED Equation.3, а градієнт EMBED Equation.3. Знову визначаємо проміжок допустимих значень параметра EMBED Equation.3, при яких точка х2 буде належати допустимій області. До системи обмежень, які повинна задовольняти точка х2, не увійде друге обмеження, оскільки ця точка лежить на граничній прямій, визначеній цим обмеженням. Розв’язуючи дану систему, знаходимо проміжок EMBED Equation.3. З використанням необхідної умови екстремуму EMBED Equation.3 отримуємо EMBED Equation.3 Але значення EMBED Equation.3 не належить проміжку EMBED Equation.3, тому покладаємо EMBED Equation.3. Нова точка х2 = (0,8; 1,8) лежить на перетині двох граничних прямих, які відповідають першій і другій нерівностям системи обмежень. У цій точці функція набуває значення EMBED Equation.3. Визначимо напрямок переміщення з точки х2 – вектор r2 = (r21; r22): максимізувати EMBED Equation.3 за обмежень EMBED Equation.3; EMBED Equation.3. Система рівнянь задачі має розв’язок r2 = (0; 0). Підставляючи одержаний розв’язок у функцію T, дістаємо, що максимум T = 0, а це означає те, що х2 є точкою максимуму цільової функції в допустимій області, тобто х2 = х* і max f (х*) = 12,68. Як видно з мал. 2, лінія рівня f(х)дотикається до границі допустимої області в точці х2. Мал. 2 ВАРІАНТИ ІНДИВІДУАЛЬНИХ ЗАВДАНЬ Розв’язати градієнтним методом задачі нелінійного програмування, починаючи оптимізаційний процес з вказаної точки х0 й супроводжуючи розв’язок графічною ілюстрацією. 1. EMBED Equation.3 EMBED Equation.3 2. EMBED Equation.3;. EMBED Equation.3 3. EMBED Equation.3 4. EMBED Equation.3 ;. EMBED Equation.3 5. EMBED Equation.3 6. EMBED Equation.3; 7. EMBED Equation.3 EMBED Equation.3 8. EMBED Equation.3 EMBED Equation.3 9. EMBED Equation.3 EMBED Equation.3 10. EMBED Equation.3 EMBED Equation.3 11. EMBED Equation.3;EMBED Equation.3. 12. EMBED Equation.3 EMBED Equation.3 13. EMBED Equation.3 ; . 14. EMBED Equation.3 15. EMBED Equation.3; 16. EMBED Equation.3 EMBED Equation.3 17. EMBED Equation.3 EMBED Equation.3 18. EMBED Equation.3 EMBED Equation.3 19. EMBED Equation.3 EMBED Equation.3 21. EMBED Equation.3 EMBED Equation.3 22. EMBED Equation.3 EMBED Equation.3 23. EMBED Equation.3 EMBED Equation.3 24. EMBED Equation.3;EMBED Equation.3. 25. EMBED Equation.3 , EMBED Equation.3 26. EMBED Equation.3 , EMBED Equation.3. 27. EMBED Equation.3 , EMBED Equation.3 28. EMBED Equation.3; 29. EMBED Equation.3 EMBED Equation.3 СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ 1. Зайченко Ю.П. Дослідження операцій. Підручник. – К.: ЗАТ “ВІПОЛ”. – 2000. – 688 с. 2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: навч.-метод. посібн. для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с. 3. Кузнецов А.В., Новикова Г.И., Холод Н.И. Сборник задач по математическому программированию. – Минск: Вышейша школа, 1975. – 270 с.

Методичні вказівки до лабораторної роботи Математичні методи дослідження операцій

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись