27. Метод гілок і границь.

Загальна ідея – пошук max та min f(x) на множині допустимих значень x, де f(x) та x мають довільну природу

В основу метода гілок і границь покладено той факт, що для отримання розв’язку задачі оптимізації на деякій допустимій множині можна розбити дану множину на підмножини, знайти розв’язок задачі на кожній з підмножин і у якості відповіді взяти найкращий з отриманих розв’язків, у відповідності з критерієм якості задачі (найбільшим чи найменшим значенням цільової функції). Розвиваючи описану ідею можна прийти до висновку, що замість знаходження точного розв’язку задачі на підмножині (що може бути надзвичайно складно) можна знаходити лише його оцінку, а потім уточнювати її шляхом подрібнення складових підмножин. Іншою особливістю методу є можливість відкидання так званих «безперспективних» підмножин, тобто підмножин, на яких гарантовано не може бути розв’язку вихідної задачі. Фізично метод складається з двох процедур: процедура розгалуження та процедура знаходження оцінок(границь)/процедура обмеження

28. Розв’язання задач методом гілок і границь.

Алгоритм гілок та границь працює за наступною схемою:

Крок 0. Початкове розбиття допустимої множини на декілька підмножин і обрахунок

для кожної з них оцінок зверху і знизу мінімального значення цільової функції.

Крок 1. Визначення рекордної підмножини шляхом відшукання найменшої серед

оцінок знизу на підмножинах.

Крок 2. Перевірка умови зупинки алгоритму шляхом порівняння різниці між оцінками

. Якщо точність досягнута, то перехід до кроку 6.зверху і знизу на черговій рекордній підмножині з заданою точністю

Крок 3. Розбиття рекордної підмножини на нові підмножини, і обчислення оцінок

мінімального значення цільової функції на кожній з отриманих підмножин.

Крок 4. Визначення найменшої оцінки зверху на підмножинах і відкидання тих

підмножин, у яких оцінки знизу будуть більшими за отриману найменшу оцінку зверху.

Крок 5. Перехід до кроку 1.
Крок 6. В якості відповіді можна взяти центр ваги поточної рекордної підмножини.

Метод гілок і границь є одним із найбільш популярних і ефективних методів неперервної та дискретної глобальної оптимізації. Критичність вдалого алгоритму розгалуження. В разі невдалого вибору метод приводить до фактичного повного перебору S без відсікань Не існує універсального загального алгоритму оцінки. оскільки різновидів методу надзвичайно багато то і класифікують їх подвійно - за процедурами розгалуження та оцінки.

29. Загальна постановка задачі нелінійного програмування.

Для розв’язування задач нелінійного програмування не існує універсального методу, тобто до них необхідно застосовувати широке коло різних методів і обчислювальних алгоритмів. Вони в основному базуються на застосуванні диференційного числення і залежать від конкретної постановки задачі та форми економіко-математичної моделі.

Методи розв’язування задач нелінійного програмування бувають прямі та непрямі. За допомогою прямих методів знаходження оптимальних планів здійснюють у напрямку найшвидшого збільшення (зменшення) значення цільової функції. Типовим представником цієї групи методів є градієнтні. Методика застосування непрямих методів передбачає зведення задачі до такої, оптимум якої слід знаходити простішими методами. Серед непрямих найкраще розробленими є методи розв’язування задач квадратичного та сепарабельного програмування.

Найпростішими для розв’язування є задачі нелінійного програмування, в яких система обмежень складається лише з рівнянь.

30. Метод множників Лагранжа

Метод невизначених множників або метод невизначених множників Лагранжа - метод знаходження умовного оптимуму, запропонований італійським математиком Жозефом-Луї Лагранжем. Метод дозволяє звести задачу на відшукання умовного оптимуму до задачі на знаходження безумовного оптимуму.

31. Розв’язання задач методом Лагранжа

Задача

Знайти прямокутник із найбільшою площею при заданому периметрі p.

Розв'язок

Позначимо сторони прямокутника x та y. Потрібно знайти максимум фунції

S = xy

при умові

2x + 2y = p.

Вводимо множник Лагранжа λ і шукаємо безумовний оптимум функції

F(x,y,λ) = xy − λ(2x + 2y − p)

Беручи похідні отримуємо систему рівнянь