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

приобрести
Курсова робота - Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
скачать (1444.5 kb.)
Доступные файлы (1):
n1.doc1445kb.19.09.2012 22:02скачать

n1.doc

  1   2


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

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

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

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

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


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

з дисципліни

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

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

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

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


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

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

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

Розробила

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

Клюєва А. Ю.

Полтава 2009




Зміст


Полтава 2009 2

Зміст 2

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


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

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

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

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

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

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

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

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

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

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

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

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

;

.

Константа повинна бути меншою допустимої кінцевої довжини відрізка, ?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 ? ?, де ? – точність пошуку, і тоді в якості точки локального мінімуму можна наближено прийняти середину відрізку .

Назва методу половинного ділення мотивована тим, що якщо величина ? достатньо мала, то довжина відрізка унімодальності (ba) зменшується майже вдвічі.
Наступним методом знаходження екстремуму для задач одновимірної оптимізації є метод золотого перерізу.

Термін “золотий переріз” ввів Леорандо да Вінчі. Точка х1 являється золотим перерізом відрізка , якщо відношення довжини b-a всього відрізка до довжини b1 більшої частини дорівнює відношенню довжини більшої до довжини х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-го кроку.

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


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

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



Обчислюємо значення функції в цих точках:



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

В нашому випадку . Тому знову розраховуємо дві точки:





Оскільки то нові межі відрізка і . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.



нові межі відрізка , .

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

.



На першій ітерації відрізок ділимо двома симетричними відносно центра точками за формулами:



Обчислюємо значення функції в цих точках:



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



Так як і в методі дихотомії процедура буде продовжуватись до тих пір, поки не буде виконуватись умова . Отже перевіримо умову зупинки:

. Тому знову аналогічно шукаємо нові межі відрізка. Оскільки маємо:

Перевіряємо умову зупинки: , тому продовжуємо процедуру.



Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Знову перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.



Перевіряємо умову зупинки: , отже продовжуємо процедуру.



Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

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

.

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

Спочатку згенеруємо послідовність чисел Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … . Початкові обрахунки проводяться в точках: , де - число Фібоначчі, яке обирається з умови , тобто в нашому випадку це 18-те число Фібоначчі: . Ці точки розташовані симетрично відносно середини відрізку . На кожному кроці точка наступного обрахунку обирається симетрично відносно середини відрізка локалізації до точки уже проведеного обрахунку, що лежить на цьому відрізку. В силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена і дорівнює N=18. Отже можемо знайти початкові точки ділення:

. Далі обчислюємо значення функції в цих точках:



Оскільки , то покладаємо, що N=N-1=18-1=17. Нові межі відрізка тепер будуть рівними . Знаходимо нові точки ділення: . Значення функції в цих точках:



Оскільки N=16, нові межі відрізка -.



Оскільки N=15, нові межі відрізка -.



Оскільки N=14, нові межі відрізка -.



Оскільки N=13, нові межі відрізка -.



Оскільки N=12, нові межі відрізка -.



Оскільки N=11, нові межі відрізка -.



Оскільки N=10, нові межі відрізка -.



Оскільки N=9, нові межі відрізка -.



Оскільки N=8, нові межі відрізка -.



Оскільки N=7, нові межі відрізка -.



Оскільки N=6, нові межі відрізка -.



Оскільки N=5, нові межі відрізка -.



Оскільки N=4, нові межі відрізка -.



Оскільки N=3, нові межі відрізка -.



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

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации