МІНІСТЕРСТВО освіти и науки України
Полтавський національний технічний університет імені Юрія Кондратюка
Факультет інформаційно-телекомунікаційніх технологій та систем
Кафедра прікладної математики, інформатики и математичного моделювання
Курсова робота
з дісціпліні В«Методи оптімізації и Дослідження операційВ»
на тему: В«Методи розв'язування одновімірніх та багатовімірніх нелінійніх оптімізаційніх завдань та завдань лінійного цілочіслового програмування В»
301-ЕІ. 20 06165 КР
Керівник роботи
кандидат фіз.-мат. Наук Радченко Г.О.
розроб
студентка гр. 301-ЕІ Клюєва А.Ю.
Полтава 2009
Зміст
1. Методи розв'язування одновімірніх оптімізаційніх завдань
2. Визначення найменшого Значення функції на завданні відрізку за допомог методів одновімірної оптімізації
3. Розв'язання Задачі мінімізації за допомог методу Ньютона и методом найшвідшого спуску
4. Розв'язання Задачі умовної оптімізації за допомог методу Франка-Вулфа и метод штрафних функції
5. Розв'язання Задачі цілочіслового програмування
6. Вихідний код програм
Список використаної літератури
1. Методи розв'язування одновімірніх оптімізаційніх завдань
Розглянемо детально методи розв'язування одновімірніх завдань, а саме: метод діхотомії, метод золотого перерізу и метод Фібоніччі.
Одновімірна оптімізація полягає в знаходженні точки, в якій цільова
функція пріймає максимальне або мінімальне значення. Часто в постановках задач Може буті завдань відрізок, в якому знаходится оптимальні Рішення.
Функція має локальний мінімум в точці, ЯКЩО при довільному існує окіл такий, Що для Всіх Значення в цьому околі. Функція має глобальний мінімум в точці, ЯКЩО Для всіх х справедлива рівність.
Відповідно функція має локальний максимум в точці, ЯКЩО при довільному існує окіл такий, Що для Всіх Значення в цьому околі. Функція має глобальний мінімум в точці, ЯКЩО Для всіх х справедлива рівність.
Класичний підхід до Задачі знаходження екстремумів функції полягає в пошуках умів, Якиме смороду повінні задовольняти. Необхідною умів екстремум в точці являється рівність нулю Першої похідної (теорема Ферма), тобто вімагається розв'язати рівняння:. Даного рівнянню задовольняють Як локальні та глобальні екстремум, так и точки перегіну функції, тому наведена Умова є Ліше необхідною умів, альо НЕ достатності.
З метою Отримання достатніх умов вімагається обчислення значень інших похідніх в точках, Що задовольняють рівняння. При цьому доведено, Що мінімуму функції відповідає додатне Значення Другої похідної, тобто, а максимуму - від'ємне, тобто. Однак, ЯКЩО друга похідна дорівнює 0, Ситуація залішається невизначенності и необхідно досліджуваті віщі похідні. При цьому ЯКЩО перша вища похідна НЕ Рівна нулю має парні порядок, то екстремум існує, в іншому випадка - ні.
Дамо визначення унімодальної функції при Поиск мінімуму.
неперервно функція назівається унімодальною на відрізку ЯКЩО:
В· точка локального мінімуму функції належиться відрізку;
В· для довільніх двох точок відрізка х1 и х2 , взятих по одну сторону від точки мінімуму, точці х1 більш блізькій до точки мінімуму відповідає менше Значення функції, тобто при або при справедлива нерівність.
достатності Умова унімодальності функції на відрізку грунтується на наступній теоремі:
ЯКЩО функція двічі діференційована на відрізку и в будь-якій точці цього відрізка, то - унімодальна функція на відрізку.
Відмітімо, Що Умова візначає множини точок, на якій функція являється опуклою вниз. Умова ж візначає опуклу вгору функцію, Яка на відрізку має максимум и кож являється унімодальною.
Метод половинного ділення , Який кож назівається методом діхотомії , являється процедурою послідовного Поиск мінімуму фунуції. Нехай Визначіть відрізок, якому належиться точка локального мінімуму х , и функція являється унімодальною на цьому відрізку. Далі для звуження проміжку унімодальності вікорістовуються Дві точки І, розташовані симетрично на відстані від середини відрізка:
;
.
Константа винна буті Менша допустімої кінцевої довжина відрізка, О” k = bk - ak > 0.
Потім обчислюють Значення функції в ціх точках y 1 = f ( x 1) i y 2 = f ( x 2) i в залежності від їх співвідношення Нові Межі відрізка унімодальності [ a 1, b 1] будуть наступні:
• y 1 < y 2, a 1 = a 0 и b 1 = x 2;
• y 1> y 2, a 1 = x 1 і b 1 = b 0;
• y 1 = y 2, a 1 = x 1 і b 1 = x 2.
У цьому звуженому проміжку [ a 1, b 1] Знову розраховуються Дві точки х1 (1) и х2 (1) , сіметрічні відносно Його середина І Значення функції в ціх точках. Процедура буде продовжуватісь до тихий пір, Поки не буде віконуватісь Умова О” k = bk - ak ≤ Оµ , де Оµ - точність Поиск, и тоді в ЯКОСТІ точки локального мінімуму можна набліжено прийнятя середину відрізку.
Назва методу половинного ділення мотівована тім, Що ЯКЩО величина Оµ достатності мала, то довжина відрізка унімодальності ( b - a ) зменшується Майже вдвічі.
Наступний методом знаходження екстремум для задач одновімірної оптімізації є метод золотого перерізу .
Термін "золотий переріз" ввів Леорандо да Вінчі. Точка х1 являється золотим перерізом відрізка, ЯКЩО відношення довжина b - a Всього відрізка до довжина b -х1 більшої частин дорівнює відношенню довжина більшої до довжина х1-а меншої частині, тобто х1 - золотий переріз, ЯКЩО справедлива рівність:. Аналогічно, точка х2 симетрично точці х1 відносно середини відрізка, являється іншим золотим перерізом цього відрізка.
Відмітімо властівість золотого перерізу: точка х1 одночасно являється золотим перерізом відрізка, а друга точка х2 - золотим перерізом відрізка.
Суть методу золотого перерізу заклечається в Наступний. Спочатку на віхідному відрізку знаходяться точки х1 и х2 по Наступний формулами:
- коефіцієнт зжимання.
Потім обчислюють Значення функції в точках х1 и х2 , тобто. При цьому можліві два випадка:
1. , В цьому випадка новий відрізок буде рівнім і. На цьому відрізку Знову обіраються Дві точки
2. , Тоді новий відрізок Будуть становіті:. На новому відрізку кож обіраються Дві точки
І в Першому и в іншому випадка розраховується Ліше одна нова точка (друга відома). У новій точці обчіслюється Значення функції І знову відбувається порівняння в двох точках, и в залежності від цього обірається новий відрізок. Процедура віконується до тихий пір, доки не буде віконуватісь Умова, де - точність Поиск.
Розглянемо кож метод Фібоначчі для розв'язування одновімірніх задач. Цей метод назв так зважаючі на З'явилася при Поиск проміжків унімрдальності чисел Фібоначчі и вікорістовується, ЯКЩО кількість ітерації обмежен. Суть методу в тому, Що на шкірному кроці точка Наступний обчислення обірається симетрично відносно середини відрізка локалізації до точки, Що лежить всередіні цього відрізку, вже проведеного обчислення. Тобто в процесі Поиск інтервалу (x1; x3) з точкою х2, Вже ле...
