1   2   3   4
Ім'я файлу: kursova-robota-metodi-rozvyazuvannya-odnovimrnih-ta-bagatovimrni
Розширення: doc
Розмір: 1445кб.
Дата: 15.05.2020
скачати

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

Полтавський національний технічний університет

імені Юрія Кондратюка

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

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


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

з дисципліни

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

«Методи розв’язування одновимірних та багатовимірних

нелінійних оптимізаційних задач та задач лінійного

цілочислового програмування »


301-ЕІ. 20 06165 КР
Керівник роботи

кандидат фіз.-мат. наук

Радченко Г. О.

Розробила

студентка гр. 301-ЕІ

Клюєва А. Ю.

Полтава 2009




Зміст


Полтава 2009 1

Зміст 2

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



    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 відносно середини відрізка , являється другим золотим перерізом цього відрізка.
Відмітимо властивість золотого перерізу: точка х1одночасно являється золотим перерізом відрізка , а друга точка х2 – золотим перерізом відрізка .



Суть методу золотого перерізу заклечається в наступному. Спочатку на вихідному відрізку знаходяться точки х1 і х2 по наступним формулам:



- коефіцієнт зжимання.

Потім обчислюють значення функції в точках х1 і х2, тобто . При цьому можливі два випадки:

  1. , в цьому випадку новий відрізок буде рівним і . На цьому відрізку знову обираються дві точки




  1. , тоді новий відрізок будуть становити: . На новому відрізку також обираються дві точки

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

Розглянемо також метод Фібоначчі для розв’язування одновимірних задач . Цей метод названий так зважаючи на появу при пошуку проміжків унімрдальності чисел Фібоначчі і використовується, якщо кількість ітерації обмежена . Суть методу в тому, що на кожному кроці точка наступного обчислення обирається симетрично відносно середини відрізка локалізації до точки, що лежить всередині цього відрізку, уже проведеного обчислення. Тобто в процесі пошуку інтервалу (x1; x3) з точкою х2, вже лежачою в цьому інтервалі, наступна точка х4 завжди вибирається так, що х3–х4 = х2–х1 або х4-х1 = х3-x2, тобто x4=х1-х2+х3.


Алгоритм методу Фібоначчі поляга в наступному:

  1. задаються початкові границі відрізку і , точність обчислень .

  2. розраховуються початкові точки ділення:



- це число із послідовності Фібоначчі, яке знаходиться з умови , Таким чином визначається також число ітерацій n. В точках знаходять значення цільової функції: .

  1. покладають . Тоді

    • якщо , то , .

    • інакше , .

  2. якщо n=1, то і зупиняються. Значення цільової функції в цій точці і буде мінімумом функції. Інакше повертаються до 3-го кроку.

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


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

Визначимо найменше значення функції на відрізку з точністю , використовуючи
© Усі права захищені
написати до нас