467
Градієнтний метод числової оптимізації задач нелінійного програмування
Лабораторная работа
Информатика, кибернетика и программирование
Застосування градієнтного методу, коли обмеження на область зміни змінних х відсутні. Застосування градієнтного методу, коли наявні обмеження на область зміни змінних х. ознайомлення з градієнтним методом числової оптимізації, набуття навиків розв’язку та аналізу задач нелінійного програмування градієнтним методом.
Украинкский
2013-01-06
1.16 MB
131 чел.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
із лабораторної роботи №13
«Градієнтний метод числової оптимізації задач нелінійного програмування»
з дисципліни
“Математичні методи дослідження операцій”
Виконав:
студент групи КН 22
Приступа Олег
Прийняв:
старший викладач Балич Б.І.
Львів 2012
Мета роботи: ознайомлення з градієнтним методом числової оптимізації, набуття навиків розвязку та аналізу задач нелінійного програмування градієнтним методом.
Градієнтні методи належать до наближених числових методів розвязування задач нелінійного програмування, оскільки дають точний розвязок за нескінченне і лише в окремих випадках за скінченне число кроків. З їх використанням можна розвязувати будь-яку задачу нелінійного програмування, знаходячи, як правило, лише локальний екстремум. Тому застосування цих методів дає найбільший ефект для розвязування задач випуклого програмування, де локальний екстремум є одночасно і глобальним.
Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінних х відсутні. Пошук екстремального значення функції f(х) можна починати з будь-якого допустимого розвязку, наприклад, з точки хk = (x1k; ...; хпk).
Градієнтом f(x) функції f(х) в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто
Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції f (х).
Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої
. (1)
де k числовий параметр, від величини якого залежить довжина кроку переміщення . Величина k, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції
(2)
Чергову точку хk+1 визначаємо після обчислення параметру k (для цього підставляємо значення k в формулу (1) на пошуковій траєкторії). В цій ( хk+1 ) точці знову знаходимо градієнт, а рух відбувається далі по прямій хk+2 = хk+1 + k+1f(xk+1) у напрямку нового градієнту f (xk+2) до точки хk+2, в якій досягається найбільше значення функції f(х) в цьому напрямку і т.д. Розвязування триватиме доти, поки не буде досягнута точка х*, в якій градієнт функції дорівнює нулю. В цій точці х* цільова функція f(х*) і буде набувати максимального значення.
Приклад 1. Нехай потрібно визначити точку максимуму функції , коли процес розвязування розпочинається з точки x0 = (4;4).
Розвязування. Знайдемо частинні похідні функції f(x)
; .
Градієнт функції в точці х0 буде
.
Перемістимось з точки х0 вздовж градієнту f(х0) в нову точку х1:
х1 = x0 + λ0 f (х0) = (4; 4) + 0 (6; 4) = (4 6 0; 4 4 0).
Градієнт функції в точці х1 дорівнює
f (х1) = [2 2 (4 60); 4 2 (4 40)] = ( 6 +120; 4 + 80).
З необхідної умови екстремуму одержуємо рівняння
,
звідки = 0,5.
Оскільки , то знайдене значення х1 є точкою максимуму функції f (х1).
х1 = (4 6·0,5; 4 4·0,5) = (1; 2)
та градієнт f (х1) в цій точці х1 f (х1) = (2 2·1; 4 2·2) = (0; 0).
Оскільки градієнт f (x1) має нульові координати, робимо висновок про те, що х1 = (1; 2) є точкою, в якій цільова функція досягає максимального значення f(х1) = 2·1+ 4·2 1 4 = 5 ( в початковій точці f(x0) = 8 ).
На мал. 1 наведена графічна інтерпретація даної задачі.
Мал. 1.
Тепер розглянемо випадок розвязування задачі нелінійного програмування з обмеженнями. Припустимо, що задача полягає в наступному: необхідно знайти максимум функції f(х) за обмежень
, , (3)
,.
Крім того, будемо вважати, що функція f(х) є ввігнутою диференційованою функцією.
При розвязуванні подібних задач трапляються два випадки:
1) цільова функція має єдиний екстремум, і він знаходиться всередині області допустимих розвязків. Тоді процес розвязування задачі (пошук оптимальної точки х*) нічим не відрізняється від уже розглянутого;
2) цільова функція набуває свого екстремального значення в точці, що знаходиться на границі допустимої області. В цьому випадку послідовність розвязування задачі наступна. Якщо початкова точка хk лежить всередині допустимої області (всі обмеження виконуються як строгі нерівності), то переміщуватися потрібно в напрямку градієнту. Але координати чергової точки повинні задовольняти обмеженням (3), тобто повинні виконуватись нерівності
(4)
Розвязуючи систему (4) лінійних нерівностей, знаходимо проміжок допустимих значень параметру , при яких точка x1 буде належати допустимій області. Значення , яке одержується в результаті розвязування рівняння (2)
,
повинно належати проміжку . Якщо значення виходить за межі проміжку, то за приймається . При цьому чергова точка пошукової траєкторії опиняється на граничній гіперплощині, що відповідає нерівності системи (4), виходячи з якої при розвязанні системи отримано значення .
Якщо початкова точка хk лежить на граничній гіперплощині (або чергова точка пошукової траєкторії опинилась на граничній траєкторії), то напрямок переміщення визначається із розвязку наступної допоміжної задачі математичного програмування:
(5)
(6)
для тих і, при яких
, (7)
, (8)
де ; .
Умова (7) визначає належність точки хk границі допустимої області. Умова (6) означає те, що переміщення з точки хk по вектору rk буде відбуватися всередину допустимої області або по її границі, а умова (8) необхідна для обмеження величини rk. Для наступної точки пошукової траєкторії
знаходиться значення параметра . При цьому використовується необхідна умова екстремуму:
.
Процес розвязування припиняється при досягненні точки, в якій
.
Приклад 2. Максимізувати за таких обмежень
,
Оптимізаційний пошук почати з точки x0 = (1; 0,5).
Розвязування. Точка x0 = (1; 0,5) лежить всередині допустимої області, значення функції в точці x0 f(x0) = 8,75. За напрямок переміщення в наступну точку x1 приймаємо напрямок градієнту в точці x0 = (1; 0,5).
Градієнт у точці х0 дорівнює . Виходячи з цього, можна записати координати наступної точки
.
Визначимо проміжок допустимих значений для параметру , при яких точка x1 буде належати допустимій області. В цьому випадку система нерівностей (4) має вигляд
З розвязку цієї системи знаходимо проміжок . Розвязавши рівняння
,
визначимо значення параметру , при якому приріст функції досягає найбільшої величини. Але значення не належить проміжку, тому приймаємо .
Нова точка x1 = (1,36; 0,95) знаходиться на граничній прямій, яка визначається другим обмеженнямнерівністю (тією нерівністю, якій відповідає значення ). В точці x1 значення функції. Оскільки точка х1 лежить на граничній прямій, то напрямок переміщення в наступну точку х2 визначаємо за вектором r1 (рух в напрямку градієнта виводить з допустимої області). Для визначення координат вектора r1 запишемо допоміжну задачу (5) (8):
максимізувати
за обмежень
;
.
Система рівнянь цієї задачі має два розвязки: (0,5568;0,8352) і (0,5568; 0,8352). Підставляючи ці розвязки у функцію , одержуємо, що максимальне значення функції і досягається при (0,5568; 0,8352), тобто переміщуватися з х1 треба вздовж вектору r1 = (0,5568; 0,8352) по другій граничній прямій (мал. 2). Координати наступної точки х2 дорівнюють
,
а градієнт
.
Знову визначаємо проміжок допустимих значень параметра , при яких точка х2 буде належати допустимій області.
До системи обмежень, які повинна задовольняти точка х2, не увійде друге обмеження, оскільки ця точка лежить на граничній прямій, визначеній цим обмеженням. Розвязуючи дану систему, знаходимо проміжок
.
З використанням необхідної умови екстремуму
отримуємо . Але значення не належить проміжку , тому приймаємо . Нова точка х2 = (1,36-0,557х1.01; 0,95+0,835х1,01)=(0,8; 1,8) лежить на перетині двох граничних прямих, які відповідають першій і другій нерівностям системи обмежень. У цій точці функція набуває значення
.
Визначимо напрямок переміщення з точки х2 вектор r2 = (r21; r22):
максимізувати
за обмежень
;
.
Система рівнянь задачі має розвязок r2 = (0; 0). Підставляючи одержаний розвязок у функцію T, дістаємо, що максимум T = 0, а це означає те, що х2 є точкою максимуму цільової функції в допустимій області, тобто х2 = х* і max f (х*) = 12,68. Як видно з мал. 2, лінія рівня f(х)дотикається до границі допустимої області в точці х2.
Мал. 2
Номер завдання відповідає порядковому номеру студента в деканатському журналі старости.
Індивідуальне завдання:
Варіант 20
Розвязування задачі аналітично |
||||||||||||||||||||||||||||||||||||||
Блок схема алгоритму:
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Gradient { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { gradient(); }
double[] x1= new double[1000]; double[] x2 = new double[1000]; double err = 0.0001; double ak = 0.05; double func(double x1, double x2) { return 4*x1*x1 + x2*x2 - 4*x1 + 2*x2; } double funcdx1(double x1, double x2) { return 8*x1 - 4; } double funcdx2(double x1 ,double x2) { return 2*x2 + 2; } void gradient() { double xpr1 = 0, xpr2 = 0, funpro = 0; int i = 0; double xnt1 = double.Parse(textBox1.Text); double xnt2 = double.Parse(textBox2.Text); richTextBox1.Text = "№ " + "\t X1 " + "\t X2 " + "\t F( X1; X2)" + "\n"; do { i++; xnt1 = xpr1-ak*funcdx1(xpr1, xpr2); xnt2 = xpr2-ak*funcdx2(xpr1, xpr2); funpro = funcdx1(xnt1, xnt2)+funcdx2(xnt1, xnt2); xpr1 = xnt1; xpr2 = xnt2; richTextBox1.Text += i.ToString("") + " " + xnt1.ToString("0.000000") + " " + xnt2.ToString("0.000000") + " " + func(xnt1, xnt2).ToString("0.000000") + "\n";
} while( Math.Abs(funpro) > err); label6.Text = "Minimum in: ( " + xnt1.ToString("0.00") + " ; " + xnt2.ToString("0.00") + " )"+ "\n F(x1,x2)= " + func(xnt1, xnt2).ToString("0.00"); } private void вихідToolStripMenuItem_Click(object sender, EventArgs e) { this.Close(); } private void проПрограмуToolStripMenuItem_Click(object sender, EventArgs e) { AboutBox1 a = new AboutBox1(); a.Show(); } } } |
Форма Form1.cs
Форма AboutBox1.cs
Реалізація:
1. Барінський А.Ф. і ін. Математичне програмування та дослідження операцій. Л.: Інтелект- Захід, 2008. 588с.: іл.
2. Барінський А.Ф. і ін. Математичне програмування. Л.: Інтелект-Захід, 2004. 448с.: іл.
3. Зайченко Ю.П. Дослідження операцій. К.: ДМК Пресс, 2006. 576с.: іл.
4. Долженков В.А., Колесников Ю.В. Microsoft Excel 2000. СПб.: БХВ-Петербург, 2001. 1088с.
5. Кудрявцев Е.М. Mathcad 2000 Pro. М.: ДМК Пресс, 2001. 576с.
6. Таха Хэмди А. Введение в исследование операций, 6-е издание: Пер. с англ. М.: Издательский дом «Вильямс», 2001. 912с.: ил.
7. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. К.: КНЕУ, 2003. 452 с.
Висновок: на цій лабораторній роботі я ознайомився з градієнтним методом числової оптимізації, набув навиків розвязку та аналізу задач нелінійного програмування градієнтним методом та розробив конкурентоспроможну програму оптимізації градієнтним способом.
А также другие работы, которые могут Вас заинтересовать | |||
83544. | Поняття та правовий режим прилеглої зони | 36.05 KB | |
Сстановлює що прилегла зона не може пролягати далі ніж на 12 морських миль від вихідної лінії від якої відміряється ширина територіального моря проте Конвенція з морського права 1982 р. містить положення що прилегла зона не може пролягати за межі 24 морських миль від цієї лінії Розвитком інституту прилеглої зони стала практика встановлення прибережними державами за межами свого територіального морязон виключного рибальства. Ширина морських зон виключного рибальства в практиці держав різниться. | |||
83545. | Виключна економічна зона та її правовий режим | 33.18 KB | |
Ширина виключної економічної зони не повинна перевищувати 200 морських миль що відраховуються від вихідних ліній від яких відмірюється ширина територіального моря. Прибережна держава в межах виключної економічної зони має суверенні права на розвідку розробку і збереження природних ресурсів як живих так і неживих що знаходяться у її водах на морському дні або його надрах. Прибережна держава в межах своєї виключної економічної зони користується не тільки економічними повноваженнями але й юрисдикцією щодо створення і використання штучних... | |||
83546. | Континентальний шельф і його правовий режим. Межі континентального шельфу. Делімітація континентального шельфу | 36.65 KB | |
Межі континентального шельфу. Делімітація континентального шельфу Відповідно до Конвенції ООН з морського права 1982 р. Підводна околиця материка включає продовження континентального масиву прибережної держави що знаходиться під водоюі складається з поверхні і надр шельфу схилу і підйому. внутрішнім кордоном континентального шельфу є зовнішня межа територіального моря лінії на відстані 12 морських миль від вихідної лінії. | |||
83547. | Відкрите море І його правовий режим. Свободи відкритого моря | 37.48 KB | |
Свободи відкритого моря За зовнішньою межею територіального моря знаходяться простори морів і океанів які не входять до складу територіальних вод будьякої держави і утворюють відкрите море. відкрите море визначено як усі частини моря які не входять ані до територіального моря ані до внутрішніх вод будьякої держави. встановила що положення Частини VII Відкрите море застосовуються до всіх частин моряякі не входять ані до виключної економічної зони ані до територіальною моря або внутрішніх вод будьякої держави ані до архіпелажних... | |||
83548. | Правовий статус Міжнародного району морського дна. Використання ресурсів Міжнародного району морського дна. Міжнародний орган з морського дна | 35.92 KB | |
Використання ресурсів Міжнародного району морського дна. Міжнародний орган з морського дна Морське дно за межами континентального шельфу і економічної зони є територією з міжнародним режимом і утворює міжнародний район морського дна далі Район. 1 Конвенції ООН з морського права 1982 р. | |||
83549. | Поняття і види міжнародних проток. Правовий статус і режим міжнародних проток | 36.7 KB | |
Берега протоки можуть належати одній державі або двом чи більше державам. Якщо ширина протоки перевищує подвійну ширину територіального моря прибережної держави або держав на тій частини протоки що знаходиться поза межами територіального моря діє принцип свободи судноплавства. Якщо ж ширина протоки не є більшою ніж подвійна ширина територіального моря міжнародноправовий статус протоки є подібним до статусу територіального моря так звані територіальні протоки. Традиційно на підставі звичаєвої норми міжнародного морського права в водах... | |||
83550. | Правовий режим Чорноморських проток | 36.39 KB | |
Відносно проходу через протоки військових кораблів Конвенція встановила ряд загальних положень: обов\'язкове повідомлення про прохід обмеження кількості та тоннажу кораблів що проходять через протоки та ін. Конвенція проводить чітку різницю між проходом через протоки кораблів чорноморських та нечорноморських держав. Чорноморським державам дозволяється проводити через протоки кораблі будьякого тоннажу а також підводні човни. | |||
83551. | Правовий режим міжнародних каналів. Режим Суецького каналу | 37.45 KB | |
Режим Суецького каналу Міжнародні канали це штучні морські шляхи що поєднують морські простори та використовуються для інтересів морського судноплавства. Особливістю правового режиму міжнародних каналів є те що вони будучи частиною території державивласника каналу підпадають під дію відповідних міжнародних договорів що істотно обмежують правомочність даної держави. До принципів правового режиму міжнародних каналів відносяться: повага суверенних прав власника каналу і невтручання в його внутрішні справи; свобода судноплавства по каналу... | |||
83552. | Поняття міжнародно-правової відповідальності | 38.1 KB | |
Комісія міжнародного права ООН визначила зміст міжнародної відповідальності як ті наслідки які те або інше міжнароднопротиправне діяння може мати відповідно до норм міжнародного права в різних випадках наприклад наслідки діяння в плані відшкодування збитків та відповідних санкцій 1. У науці міжнародного права під міжнародноправовою відповідальністю розуміють конкретні негативні юридичні наслідки що настають для суб\'єкта міжнародного права в результаті порушення ним міжнародноправового зобов\'язання. У цілому можна зазначити що поняття... | |||