Xreferat.com » Рефераты по математике » Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

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

Отже можемо застосувати метод Ньютона. Послідовність точок, яка прямує до точки мінімуму функції Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування згідно цього методу знаходиться за формулою: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, де Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування - обернена матриця Гессе.


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.


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

Знайдемо градієнт цільової функції:Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняі обчислимо його в точці Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

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

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

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

Широке застосування цього методу обумовлено тим, що в напряму антиградієнту — Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування похідна функції за напрямом досягає найменшого значення.

Алгоритм методу найшвидшого спуску:

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

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

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

Перевіряємо умову зупинки, а саме: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування. Якщо умова виконана, то покладаємо Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування і зупиняємо обчислення, якщо ні, то переходимо до наступного кроку.

Покладаємо, що Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування і переходимо до кроку 2.

Тепер перейдемо безпосередньо до нашого прикладу.

Оберемо спочатку точність обчислень Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування. За початкове наближення як і в методі Ньютона візьмемо точку Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування. З аналізу, проведеного в методі Ньютона, маємо що цільова функція є опуклою і неперервно диференційованою в Rn, отже даний метод застосовувати можна.

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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.


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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


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

Перевіряємо умову зупинки:

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

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняМетоди розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

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

Перевіряємо умову зупинки:

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняотже шукаємо наступне наближення:

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Отже можемо тепер знайти координати точки Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

Обчислимо значення цільової функції в цій точці: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняПеревіряємо умову зупинки:

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняотже шукаємо наступне наближення:

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Отже можемо тепер знайти координати точки Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

Обчислимо значення цільової функції в цій точці: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмуванняПеревіряємо умову зупинки:

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, тобто умову зупинки виконано. Отже Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

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

Розв’язання задачі умовної оптимізації за допомогою методу Франка-Вулфа і методу штрафних функції


4. Розв’яжемо задачу умовної оптимізації


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


методом Франка-Вулфа

Функція Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування являється вгнутою так як представляє собою суму лінійної функції (її можна розглядати як вгнуту) і квадратичної форми, яка являється від’ємно визначеною і тому також являється вгнутою. Перевіримо завдяки матриці Гессе від’ємну визначеність функції Методи розв’язування одновимірних та багатовимірних
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: