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

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

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

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

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

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


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

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

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


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 відносно середини відрізка Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, являється другим золотим перерізом цього відрізка.

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


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


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


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


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

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

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

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

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

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


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


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

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

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


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


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

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

якщо Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та
					</div>
					<div class=Страницы: 1 2 3 4 5 6 7