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

Міністерство освіти і науки України

Полтавський національний технічний університетімені Юрія Кондратюка

Факультет інформаційно-телекомунікаційних технологій та систем

Кафедра прикладної математики, інформатики і математичного моделювання

КУРСОВА РОБОТА

з дисципліни «Методи оптимізації і дослідження операцій»

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

301-ЕІ. 20 06165КР

Керівник роботи

кандидат фіз.-мат. НаукРадченко Г.О.

Розробила

студентка гр. 301-ЕІКлюєва А.Ю.

Полтава 2009

Зміст

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

2. Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації

3. Розв’язання задачі мінімізації за допомогою методу Ньютона і методу найшвидшого спуску

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

5. Розв’язання задачі цілочислового програмування

6. Вихідний код програм

Список використаної літератури

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

Розглянемо детально методи розв’язування одновимірних задач, а саме: метод дихотомії, метод золотого перерізу і метод Фібоніччі.

Одновимірна оптимізація полягає в знаходженні точки

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

Функція

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

Відповідно функція

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

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

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

З метою отримання достатніх умов вимагається обчислення значень других похідних в точках, що задовольняють рівняння

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

Дамо визначення унімодальної функції при пошуку мінімуму.

Неперервна функція

називається унімодальною на відрізку якщо:

· точка

локального мінімуму функції належить відрізку ;

· для довільних двох точок відрізка х1 і х2, взятих по одну сторону від точки мінімуму, точці х1 більш близькій до точки мінімуму відповідає менше значення функції, тобто при

або при справедлива нерівність .

Достатня умова унімодальності функції

на відрізку ґрунтується на наступній теоремі:

Якщо функція

двічі диференційована на відрізку і в будь-якій точці цього відрізка, то - унімодальна функція на відрізку .

Відмітимо, що умова

визначає множину точок, на якій функція являється опуклою вниз. Умова ж визначає опуклу вгору функцію, яка на відрізку має максимум і також являється унімодальною.

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

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

;

.

Константа

повинна бути меншою допустимої кінцевої довжини відрізка, Δk= bk- ak> 0.

Потім обчислюють значення функції в цих точкахy1=f(x1) і y2=f(x2) і в залежності від їх співвідношення нові межі відрізка унімодальності [a1, b1] будуть наступні:

• y1 < y2, a1=a0 іb1=x2 ;

• y1 > y2, a1=x1 іb1=b0 ;

• y1 = y2, a1=x1 іb1= x2 .

В цьому звуженому проміжку [a1, b1] знову розраховуються дві точки х1(1) іх2(1), симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова Δk = bk-ak ≤ ε, де ε – точність пошуку, і тоді в якості точки локального мінімуму можна наближено прийняти середину відрізку

.

Назва методу половинного ділення мотивована тим, що якщо величина εдостатньо мала, то довжина відрізка унімодальності (b – a) зменшується майже вдвічі.

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

Термін “золотий переріз” ввів Леорандо да Вінчі. Точка х1 являється золотим перерізом відрізка

, якщо відношення довжини b-a всього відрізка до довжини b-х1 більшої частини дорівнює відношенню довжини більшої до довжини х1-а меншої частини, тобто х1 – золотий переріз, якщо справедлива рівність: . Аналогічно, точка х2 симетрична точці х1 відносно середини відрізка , являється другим золотим перерізом цього відрізка.