Міністерство освіти і науки України
Полтавський національний технічний університет імені ЮріяКондратюка
Факультет інформаційно-телекомунікаційних технологій та систем
Кафедра прикладної математики, інформатики і математичногомоделювання
КУРСОВА РОБОТА
з дисципліни «Методи оптимізації і дослідження операцій»
на тему: «Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задачлінійного цілочислового програмування»
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,тобто />. При цьомуможливі два випадки:
1. />, в цьому випадкуновий відрізок буде рівним /> і />. На цьому відрізку зновуобираються дві точки />
2. />, тоді новийвідрізок будуть становити: />. На новому відрізкутакож обираються дві точки />
І в першому і в другому випадках розраховується лише однанова точка (друга відома). В новій точці обчислюється значення функції і зновувідбувається порівняння в двох точках, і в залежності від цього обираєтьсяновий відрізок. Процедура виконується до тих пір, доки не буде виконуватисьумова />, де /> - точність пошуку.
Розглянемо також метод Фібоначчі для розв’язування одновимірнихзадач. Цей метод названий так зважаючи на появу при пошуку проміжків унімрдальностічисел Фібоначчі і використовується, якщо кількість ітерації обмежена. Сутьметоду в тому, що на кожному кроці точка наступного обчислення обираєтьсясиметрично відносно середини відрізка локалізації до точки, що лежить всерединіцього відрізку, уже проведеного обчислення. Тобто в процесі пошуку інтервалу (x1; x3) з точкою х2, вже лежачою в цьомуінтервалі, наступна точка х4 завжди вибирається так,що х3–х4 =х2–х1 або х4-х1 =х3-x2, тобто x4=х1-х2+х3.
/>
Алгоритм методу Фібоначчі поляга в наступному:
1) задаються початкові границі відрізку />і />, точність обчислень />.
2) розраховуються початкові точки ділення:
/>
/> - це число ізпослідовності Фібоначчі, яке знаходиться з умови />, Таким чиномвизначається також число ітерацій n. В точках /> знаходять значенняцільової функції: />.
3) покладають />. Тоді
· якщо />, то />, />.
· інакше />, />.
4) якщо n=1, то /> і зупиняються. Значенняцільової функції в цій точці і буде мінімумом функції. Інакше повертаються до3-го кроку.
Відмітимо, що на кожному кроці методу Фібоначчі точка, щолежить середині відрізку локалізації, ділить його у відношенні двох послідовнихчисел Фібоначчі.
2. Визначення найменшого значення функції назаданому відрізку за допомогою методів одновимірної оптимізації
Визначимонайменше значення функції /> на відрізку /> з точністю />, використовуючи
· метод дихотомії:
Розіб’ємовідрізок /> навпіл івізьмемо дві симетричні відносно центру точки /> такі, що />, де /> і відкинемо ту з точок,до якої ближче виявилась одна з двох знову поставлених точок з максимальнимзначенням.
/>
Обчислюємозначення функції /> в цих точках:
/>
Оскільки/>, то нові межівідрізка /> і />. В цьому звуженому проміжку зновурозраховуємо дві точки, симетричні відносно його середини і значення функції в цихточках. Процедура буде продовжуватись до тих пір, поки не буде виконуватисьумова />.
Внашому випадку />. Тому знову розраховуємодві точки:
/>
/>
Оскільки/> то нові межівідрізка /> і />. Перевіряємо умовузупинки: />. Отжепродовжуємо процедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Отжепродовжуємо процедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Продовжуємопроцедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Отжепродовжуємо процедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Отжепродовжуємо процедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Отжепродовжуємо процедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Продовжуємопроцедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Продовжуємопроцедуру.
/> /> нові межі відрізка />, />. Перевіряємо умовузупинки: />. Продовжуємопроцедуру.
/>
/> нові межівідрізка />, />.
Перевіряємоумову зупинки: />. Отже в якості точки локальногомінімуму можна наближено прийняти середину відрізку />. Тоді мінімальнезначення вихідної функції буде рівним:
/>.
· метод золотого перерізу
Напершій ітерації відрізок /> ділимо двомасиметричними відносно центра точками за формулами:
/>
Обчислюємозначення функції в цих точках:
/>
Тойіз кінців відрізка, до якого серед знову поставлених точок ближче опинилась та,значення функції в якій максимальне, відкидаємо. Тобто, оскільки />, то покладаємо, що /> />. Тепер обчислюємозначення функції в нових точках:
/>
Такяк і в методі дихотомії процедура буде продовжуватись до тих пір, поки не будевиконуватись умова />. Отже перевіримо умовузупинки:
/>. Тому зновуаналогічно шукаємо нові межі відрізка. Оскільки /> маємо:
/> Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/>
Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/>
Зновуперевіряємо умову зупинки: />, отже продовжуємопроцедуру.
/>
Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/>
Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/>
Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, тому продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />, отже продовжуємопроцедуру.
/> Перевіряємоумову зупинки: />. Отже за точку локальногомінімуму можна взяти середину відрізку />. При цьому мінімальнезначення вихідної функції буде рівним:
/>.
Метод дихотомії побудований таким чином, що кожний наступнийінтервал невизначеності менше попереднього. Як бачимо, в порівнянні з методомзолотого перерізу цей метод сходиться значно швидше (тобто через меншукількість кроків отримуємо інтервал невизначеності заданої довжини, що містить />(в методі дихотомії мизробили 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, нові межівідрізка -/>.
/>
Оскільки/>, толокальний мінімум досягається в точці />. При цьому мінімальне значеннявихідної функції буде рівним: />. Отже мінімальне значенняфункції, знайдене методом дихотомії, методом золотого перерізу і методомФібоначчі співпадають. Однак найбільше ітерацій було зроблено при розв’заннізадачі методом Фібоначчі.
3. Розв’язання задачі мінімізації за допомогою методу Ньютона іметоду найшвидшого спуску
Розв’яжемозадачу мінімізації для функції />, використовуючи методНьютона. Це метод другого порядку, який використовує похіднупершого і другого порядку від цільової функції.
Першніж розв’язувати дану задачу, з’ясуємо чи має вона точку локального мінімуму. Дляцього побудуємо матрицю Гессе.
Знайдемочастинні похідні першого і другого порядку від функції />:
/>
Отжематриця Гессе матиме вигляд:
/>. А оскількиголовні мінори додатні: />, то матриця Гесседодатно визначена. Тобто достатні умови існування локального мінімуму виконані.
Такяк цільова функція є опуклою, тобто це задача опуклого програмування, а функція/> є неперервнодиференційованою в Rn, то якщо точка /> є точкою локального екстремуму,то вона буде і точкою глобального екстремуму для цієї задачі.
Отжеможемо застосувати метод Ньютона. Послідовність точок, яка прямує до точкимінімуму функції /> згідно цього методу знаходитьсяза формулою: />, де /> - оберненаматриця Гессе.
/>.
Обиремов допустимій області задачі довільну точку – початкове наближення. Нехай цебуде точка />.
Знайдемоградієнт цільової функції:/>і обчислимо його в точці />: />.
Знайдемонаступне наближення до оптимального розв’язку вихідної задачі: /> і обчислимо градієнтцільової функції в цій точці: />. Рівність градієнта цільовоїфункції нулю є необхідною умовою існування екстремуму функції багатьох змінних.Тобто оптимальний розв’язок задачі />, причому />.
Теперрозв’яжемо задачу мінімізації для функції />, використовуючи методнайшвидшого спуску. Цей метод відноситься до градієнтних методів.
Заданим методом будується послідовність точок />, яка прямує дооптимального розв’язку задачі — />. Від точки /> до точки /> рухаються в напряміградієнта цільової функції, обчисленого в точці />.
Широкезастосування цього методу обумовлено тим, що в напряму антиградієнту — /> похідна функціїза напрямом досягає найменшого значення.
Алгоритмметоду найшвидшого спуску:
1. Обираємо довільну початкову точку />, яка називається початковимнаближенням розв’язку задачі />, і покладаємо, що /> При цьомуфункція /> вважаєтьсяопуклою і неперервно диференційованою в />. Також обираємо точністьобчислень />.
2. Обчислюємо градієнт цільової функції />. Якщо />, то покладаємо /> і зупиняємо обчислення,інакше — переходимо до кроку 3.
3. Шукаємо наступне наближення за формулою: /> — для задачі мінімізації, а длязадачі максимізації: />. Число /> - параметр, який називаєтьсядовжиною кроку в точці />. Його обирають довільно, однакзазвичай, параметр /> обирається з умови, щоб в точці /> спостерігалосямаксимальне зменшення (збільшення) цільової функції />.
4. Перевіряємо умову зупинки, а саме: />. Якщо умова виконана, топокладаємо /> ізупиняємо обчислення, якщо ні, то переходимо до наступного кроку.
5. Покладаємо, що /> і переходимо до кроку 2.
Теперперейдемо безпосередньо до нашого прикладу.
Оберемоспочатку точність обчислень />. За початкове наближенняяк і в методі Ньютона візьмемо точку />. З аналізу, проведеного в методіНьютона, маємо що цільова функція є опуклою і неперервно диференційованою в Rn, отже данийметод застосовувати можна.
Зметоду Ньютона маємо, що градієнт цільової функції в точці /> буде рівним />. Оскільки />, то шукаємонаступне наближення розв’язку вихідної задачі:
/>.
Знайдемо/>: />. Оскільки /> обирається з умови, щобв точці /> спостерігалосямаксимальне зменшення />, знайдемо похідну відцільової функції в точці /> і прирівняємо її до нуля.
/>
Отжеможемо тепер знайти координати точки />: />. Обчислимо значення цільовоїфункції в цій точці: />.
Перевіряємоумову зупинки:
/>отже шукаємонаступне наближення аналогічним чином.
/>/>
/>
/>
Отжеможемо тепер знайти координати точки />: />Обчислимо значення цільовоїфункції в цій точці: />.
Перевіряємоумову зупинки:
/>отже шукаємонаступне наближення:
/>
/>
/>
/>
Отже можемотепер знайти координати точки />: />.
Обчислимозначення цільової функції в цій точці: />Перевіряємо умовузупинки:
/>отже шукаємонаступне наближення:
/>
/>
/>
/>
Отже можемотепер знайти координати точки />: />.
Обчислимозначення цільової функції в цій точці: />Перевіряємо умовузупинки:
/>, тобто умовузупинки виконано. Отже />.
Як бачимо, розв’язки задачі, знайдені обома методами майжеоднакові, але при цьому метод Ньютона дав результат вже на першому кроці ( навідміну від методу найшвидшого спуску, де довелося робити 4 ітерації). Цепов’язано з тим, що цільова функція є квадратичною, а отже напрям спуску /> завждиспівпадає з напрямом в точку мінімуму />. Тобто основна перевага методуНьютона — швидка збіжність, однак при цьому суттєвим недоліком є залежністьзбіжності від початкового наближення />. Крім того у випадку неквадратичної цільової функції трудомісткість ітерації методом Ньютона можевиявитись дуже великою за рахунок необхідності обчислення матриці другихпохідних мінімізуємої функції, що потребує затрат великої кількості часу.
Розв’язання задачі умовної оптимізації за допомогою методуФранка-Вулфа і методу штрафних функції
4. Розв’яжемо задачу умовної оптимізації
/>
a. методом Франка-Вулфа
Функція/> являєтьсявгнутою так як представляє собою суму лінійної функції (її можна розглядати яквгнуту) і квадратичної форми, яка являється від’ємно визначеною і тому такожявляється вгнутою. Перевіримо завдяки матриці Гессе від’ємну визначеністьфункції />. Для цьогоспочатку знайдемо частинні похідні першого і другого порядку від функції />:
/>
Отжематриця Гессе матиме вигляд:
/>
Головні мінори :/>оскільки в ряді /> знаки чергуються, то данаматриця є від’ємно визначеною, я отже функція /> - вгнута.
Система обмежень задачі включає тільки лінійні нерівності,які утворюють опуклу множину, отже дана задача є задачею опуклогопрограмування.
Задачу такого типу можна розв’язувати методом Франка-Вулфа.Цей метод відноситься до групи градієнтних методів.
Розглянемо задачу:
/>
Алгоритм методу Франка-Вулфа:
1. Спочатку в допустимій області задачі обирають довільну точку />. Це можна зробити,наприклад, за допомогою методу штучного базису. Також обирають точністьобчислень />. Покладають />
2. Знаходять в цій точці градієнт цільової функції />.
3. Будують функцію /> і розв’язують задачумаксимізації для функції /> в області 2-3, тобтотаку задачу:
/>
Нехай/> -оптимальний розв’язок задачі 4,2,3.
4. Шукаємо наступне наближення за формулою: />, де /> - крок в точці. Його обираютьдовільно, однак краще його вибрати так, щоб /> при такому значенні /> мала найбільшезначення. Для цього з формул 5 знаходять вираз координат вектора /> через />: /> і підставляють цейвираз у функцію />. Потім розв’язують систему />. За /> вибирають найменший зкоренів цього рівняння. Якщо цей корінь більше одиниці, то />.
5. Перевіряють критерії зупинки: />, />. Якщо дані умови виконались, топокладають /> ізупиняють обчислення, якщо ні, то переходимо до наступного кроку.
6. Покладають, що /> і переходять до кроку 2.
Теперперейдемо безпосередньо до нашої задачі. За початкове наближення дооптимального плану задачі обираємо точку />, а обчислення будемо проводити зточністю />, />. Градієнт цільовоїфункції в точці />/>.
Розв’яжемоза допомогою симплекс методу задачу:
/>
оптимізаційнийодновимірний мінімізація дихотомія ньютон
і Базис Сб В 4 2
А1
А2
А3
А4 1
А3 21 3 7 1 2
А4 1 1 -1 1 3
— 4 -2 1
А3 18 10 1 -3 2
А1 4 1 1 -1 1 3
8 -6 4 1
А2 2 9/5 1 1/10 -3/10 2
А1 4 14/5 1 1/10 7/10 3 74/5 3/5 11/5
Позначимочерез /> оптимальнийрозв’язок даної задачі. Отже />. Знайдемо новий допустимийрозв’язок вихідної задачі за формулою 5:
/>
/>
/>
Знайдемо похідну цієї функції по /> і прирівняємо її до нуля:
/>, отжепокладаємо />=1, таким чином />. Знайдемозначення цільової функції в цій точці і перевіримо умови зупинки:
/>
/>.
Отжезнаходимо нове наближення оптимального плану вихідної задачі аналогічним чином.Покладаємо, що />. Градієнт цільової функції вточці /> будерівним:
/>.
Знаходимоза допомогою симплекс-методу максимум функції
/> і Базис Сб В 3 6/5
А1
А2
А3
А4 1
А3 21 3 7 1 2
А4 1 1 -1 1 3
— 3 -6/5 1
А3 18 10 1 -3 2
А1 3 1 1 -1 1 3
3 -21/5 3 1
А2 6/5 9/5 1 1/10 -3/10 2
А1 3 14/5 1 1/10 7/10 3 264/5 21/50 87/50
Позначимочерез /> оптимальнийрозв’язок даної задачі. Отже />. Визначимо тепер />:
/>
/>
/>
/>. Тобтокритерій зупинки виконано. Отже /> являється оптимальним розв’язкомвихідної задачі, тобто />.
b. метод штрафних функцій
Цейметод відноситься до групи непрямих методів розв’язання задач нелінійногопрограмування виду:
/>
Вінзводить задачу з обмеженнями в послідовність задач безумовної оптимізаціїдеяких допоміжних функції. Останні отримуються шляхом модифікації цільовоїфункції за допомогою функій-обмежень таким чином, щоб обмеження в явномувигляді в задачі оптимізації не фігурували. Це забезпечує можливістьзастосування методів безумовної оптимізації. В загальному випадку допоміжнафункція має вигляд: />, де функція /> визначається з обмеженьвихідної задачі і називається штрафною функцією. Необхідно, щоб при порушенніобмеження вона “штрафувала” функцію Z, тобто збільшувала її значення. В такомувипадку Z буде знаходитися всередині області обмежень. Штрафну функцію можнабудувати різними способами. Розглянемо один з варіантів, коли />, де />, /> — параметр штрафноїфункції.
Далірозв’язують задачу мінімізації для функції />, використовуючи один з відомихметодів безумовної оптимізації. Будемо розв’язувати задачу мінімізації для /> градієнтнимметодом зі сталим кроком. Тоді алгоритм розв’язування задачі буде таким:
1. Обирається точність обчислень, а в якості початкової точки /> берутьдовільну точку, яка належить допустимій множині задачі. Також зазначається крок/> іпокладають />.
2. Знаходять />. Якщо точка /> належить допустиміймножині задачі, то коефіцієнти /> будуть рівними нулю, якщо ж неналежать, то вибираємо параметри /> так, щоб точка /> належаладопустимій множині.
3. Перевіряють чи виконується умова />. Якщо не виконується, топереходять до наступного кроку, якщо виконується, то />.
4. Покладають, що /> і переходять до кроку 2.
Перейдемотепер безпосередньо до нашої задачі. Так як ми розглянули алгоритм методуштрафних функцій для випадку пошуку мінімуму функції, то перейдемо від задачімаксимізації до задачі мінімізації:
/>
Запишемоштрафну функцію: />і розв’яжемо тепер задачумінімізації для цієї функції.
/>
Заточність обчислень оберемо /> , а крок />, а початкову точку візьмемо такуж як ми брали у методі Франка-Вулфа, тобто />. Отже
/>
/>;
/>.
Тобто/>,/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі:
/>
Обчислимозначення штрафної функції в цій точці: />. Перевіримо критерійзупинки: />,отже тепер по аналогії шукаємо наступне наближення до оптимального розв’язку.
/>
/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі:
/>
Обчислимозначення штрафної функції в цій точці: />. Тепер перевіримокритерій зупинки: />, отже шукаємо наступне наближеннядо оптимального розв’язку.
/>
/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі.
Обчислимозначення штрафної функції в цій точці: />.
Теперперевіримо критерій зупинки:
/>, отже шукаємонаступне наближення до оптимального розв’язку.
/>
/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі.
Обчислимозначення штрафної функції в цій точці: />.
Теперперевіримо критерій зупинки:
/>, отже шукаємонаступне наближення до оптимального розв’язку.
/>
/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі.
Обчислимозначення штрафної функції в цій точці: />.
Теперперевіримо критерій зупинки:
/>, отже шукаємонаступне наближення до оптимального розв’язку.
/>
/>
Точка/> належитьдопустимій множині задачі, оскільки задовольняє обмеженням задачі.
Обчислимозначення штрафної функції в цій точці: />.
Теперперевіримо критерій зупинки:
/>, отже шукаємонаступне наближення до оптимального розв’язку.
/>
/>
Точка/> не належитьдопустимій множині задачі, оскільки не виконується друге обмеженням задачі (/>), отжепараметр /> відміннийвід нуля. Оберемо його так, щоб друге обмеження задачі виконувалося.
/>
/>
Здругого обмеження задачі маємо:
/>
Отжев якості параметру /> візьмемо />. Тоді />
/>
Точка/> належитьдопустимій множині задачі. Обчислимо значення штрафної функції в цій точці: />.
І такдалі продовжується процес пошуку нового наближення до розв’язку задачі.
Якбачимо, метод штрафних функцій сходиться значно повільніше, ніж методФранка-Вулфа. Це може бути пов’язано з тим, що початкове наближення знаходитьсядалеко від мінімуму функції, або ж необхідно обрати більший крок.
5. Розв’язання задачі цілочислового програмування
Розв’яжемозадачу цілочислового програмування
/>
а) графічно:
Оскількичисло невідомих задачі дорівнює двом, рішення можна знайти, використовуючигеометричну інтерпретацію заадчі. Для цього, насамперед, побудуємо багатокутникрішення задачі, що складає у визначенні максимальне значення лінійної функції(1) при виконанні умов (2) і (3) (мал. 1). Координати всіх точок побудованогобагатокутника рішення ОАВС задовольняють систему лінійних нерівностей 2-3. Разом з тим умові (4), тобто умовіцілочисельності змінних, задовольняють координати лише 20 точок, відзначених намал. 1.
Щоб знайти точку, координати якої визначають рішення вихідноїзадачі, замінимо багатокутник ОАВС багатокутником, щоміститьусі припустимі точки з цілочисловими координатами і таким, що координати кожноїз вершин є цілими числами. Виходить, якщо знайти точку максимуму функції (1) наотриманому багатокутнику, то координати цієї точки і визначатьоптимальний план задачі.
Для цього побудуємо вектор /> =(4; 1) – градієнт цільовоїфункції і перпендикуляр до неї – лінію рівня цільової функції, тобто лінію, вточках якої цільова функція приймає одне й те ж значення. Побудовану прямупересуваємо в напрямку вектора /> доти, поки вона не пройдечерез останню загальну точку її з даним багатокутником. Координати цієї точки івизначають оптимальний план, а значення цільової функції в ній є максимальним.
/>
Уданому випадку шуканою є точка Е(2;3), у якій цільова функція приймаємаксимальне значення />. Отже, координати точки Евизначають оптимальний план задачі 1 — 4.
б) методом Гоморі:
Для рішення задачі цілочислового програмування методом Гоморіспочатку визначимо симплекс-методом оптимальний план задачі 1 —3 без умовицілочисельностісті змінних: і Базис Сб В 4 1
А1
А2
А3
А4 1
А3 9 3 1 1 2
А4 6 3 -2 1 3
— 4 -1 1
А3 3 3 1 -1 2
А1 4 2 1 -2/3 1/3 3
8 -11/3 4/3 1
А2 1 1 1 1/3 -1/3 2
А1 4 8/3 1 2/9 1/9 3 35/3 11/9 1/9
Тобто оптимальний план буде мати вигляд: />, при цьому />. Отримане рішення єоптимальним для задачі лінійного програмування, але недопустимим для задачілінійного цілочислового програмування, оскільки змінна /> приймає дробовезначення. Тому будуємо додаткове обмеження для змінної />, яке є правильнимвідтинанням, використовуючи перший алгоритм Гоморі: />. Тобто з останньоїсимплекс-таблиці матимемо:
/>
Умову 5 записуємо в канонічній формі: /> і приєднуємо до останньоїсимплекс-таблиці 3-ім рядком, при цьому рядок оцінок не зміниться. Теперрішення задачі, утвореної в результаті приєднання додаткового обмеження, знаходимоза допомогою двоїстого симплекс-методу. і Базис Сб В 4 1
А1
А2
А3
А4
А5 1
А2 1 1 1 1/3 -1/3 2
А1 4 8/3 1 2/9 1/9 3
А5 -6 -2 -1 1 4
35/3 11/9 1
А2 1 3 1 1 -1/3 2
А1 4 2 1 1/9 3
А4 6 2 1 -1 4
11 1 1/9
З останньої симплекс-таблиці видно, що вихідна задачацілочислового програмування має оптимальний план Х* = (2; 3). При цьомуплані значення цільової функції дорівнює: />.
в ) методом Ленг і Дойг
Як і у випадку знаходження розв’язку задачі цілочисловогопрограмування за допомогою методу Гоморі, спочатку визначаємо симплекс-методомоптимальний план задачі (1) —(3) без умови цілочисельності змінних. Зпопереднього пункту маємо оптимальне для задачі лінійного програмування (1-3): />, при цьому />.
Оскільки оптимальне рішення задачі лінійного програмування 1-3 незадовольняє умові цілочисельності, метод Ленг і Дойг заміняє простір рішеньзадачі лінійного програмування так, що в кінцевому результаті отримуємо рішеннязадачі цілочислового лінійного програмування. Для цього спочатку обираємозмінну, значення якої не є цілочисловим, тобто />. Область /> простору допустимихрішень задачі лінійного програмування не містить цілочислових значень змінної />, тому вона може бутивиключена із розгляду, як безперспективна. Це еквівалентно заміні вихідноїзадачі лінійного програмування 1-3 двома новими задачами лінійногопрограмування, котрі визначаються наступним чином:
а) задача 1:
/>
б) задача 2:
/>
Нові обмеження виключають одна одну, тому задачу 1 і задачу 2необхідно розглядати як незалежні задачі лінійного програмування. Оптимальнерішення задачі цілочислового програмування знаходиться або в просторідопустимих рішень задачі 1, або задачі 2. Отже обидві звдачі необхіднорозв’язати.
Спочатку розв’яжемо задачу 1. Для цього спочатку з останньоїсимплекс-таблиці задачі 1-3 змінну /> виразимо через небазисніневідомі:
/>
Тепер нове додаткове обмеження /> запишемо в канонічнійформі і допишемо його до останньої симплекс-таблиці задачі 1-3:
/>
Отже за допомогою двоїстого симплекс-методу можемо розв’язатизадачу 1: і Базис Сб В 4 1
А1
А2
А3
А4
А5 1
А2 1 1 1 1/3 -1/3 2
А1 4 8/3 1 2/9 1/9 3
А5 -2/3 -2/9 -1/9 1 4
35/3 11/9 1
А2 1 3 1 1 -3 2
А1 4 2 1 1 3
А4 6 2 1 -9 4
11 1 1
Оптимальним розв’язком задачі 1 буде />, а максимальне значенняцільової функції відповідно — />. Оптимальне рішеннязадачі 1 задовольняє умову 5, тобто умову цілочисленості.
В цій ситуації ми не можемо оцінити якість рішення, отриманого прирозгляді задачі 1, оскільки розв’язок задачі 2 може привести до кращогоцілочисельного розв’язку(з більшим значенням цільової функції). Поки що миможемо лише сказати, що значення /> являється нижньоюграницею максимального значення цільової функції вихідної задачі 1-4.
При значенні нижньої границі /> розглянемо задачу 2.Аналогічно до задачі 1 маємо:
/> і Базис Сб В 4 1
А1
А2
А3
А4
А6 1
А2 1 1 1 1/3 -1/3 2
А1 4 8/3 1 2/9 1/9 3
А5 -1/3 2/9 1/9 1 4
35/3 11/9
Оскільки для b=-1/3 в рядку, що йому відповідає немає від’ємнихчисел, то задача 2 розв’язку не має.
Отже оптимальним рішенням задачі лінійного цілочисловогопрограмування являється нижня границя, а саме />, при цьому значенняцільової функції />.
Як бачимо, розв’язки, отримані трьома способами однакові.
6. Вихідний код програми
Нижче приведемо код програми для знаходження мінімуму фіункції задопомогою методу золотого перерізу і методу Фібоначчі, реалізований в С++.Результат виконання програми виводить в окремий текстовий документ Solution.txt.
· Метод золотого перерізу
// zoloto.cpp: Defines the entry point for the consoleapplication.
//
#include «stdafx.h»
#include
#include
#include
using namespace std;
double g[5]={0};
double a,b;
double E=0;
void Inputkoef()
{
for (int i=0;i
{
cout
cin>>g[i];
}
}
void Inputotrez()
{
cout
cin>>a;
cout
cin>>b;
cout
cin>>E;
}
double f(double x)
{
return(g[0]*pow(x,4)+g[1]*pow(x,3)+g[2]*pow(x,2)+g[3]*x+g[4]);
}
double f(double);
ofstream Out;
int main(int argc, char* argv[])
{
coutmin»
Inputkoef();
Inputotrez();
double x,xk,yk,k;
k=0;
xk=a+((3-pow(5,0.5))/2)*(b-a);
yk=a+b-xk;
Out.open(«Solution.txt»);
cout
Out
cout
Out
do
{
cout
Out
if(f(xk)
{
b=yk;
yk=xk;
xk=a+b-xk;
}
else if(f(xk)>f(yk))
{
a=xk;
xk=yk;
yk=a+b-yk;
}
k++;
}
while (abs(b-a)>E);
cout
Out
x=(a+b)/2;
cout
Out
Out.close();
return 0;
}
Результат виконання програми при введенні даних, щовідповідать завданню цієї курсової роботи:
/>
· Метод Фібоначчі
// fib.cpp: Defines the entry point for the consoleapplication.
//
#include «stdafx.h»
#include
#include
#include
using namespace std;
double PoslidovnistFib(double);
double g[5]={0};
double a,b;
double E=0;
void Inputkoef()
{
for (int i=0;i
{
cout
cin>>g[i];
}
}
void Inputotrez()
{
cout
cin>>a;
cout
cin>>b;
cout
cin>>E;
}
double f(double);
double f(double x)
{
return(g[0]*pow(x,4)+g[1]*pow(x,3)+g[2]*pow(x,2)+g[3]*x+g[4]);
};
ofstream Out;
int main(int argc, char* argv[])
{
coutmin»
Inputkoef();
Inputotrez();
int d,k=0,p=0;
double eps,x,y,N=-1,kk=1.0;
eps = 0.00001 ;
Out.open(«Solution.txt»);
cout
Out
double L0=b-a;
do
{
N++;
}
while (PoslidovnistFib(N)
cout
Out
cout
Out
x=a+(PoslidovnistFib(N-2)/PoslidovnistFib(N))*(b-a);
y=a+(PoslidovnistFib(N-1)/PoslidovnistFib(N))*(b-a);
cout
Out
do
{
if (f(x)
{
b=y;
y=x;
x=a+(PoslidovnistFib(N-k-3)/PoslidovnistFib(N-k-1))*(b-a);
}
else if (f(x)>f(y))
{
a=x;
x=y;
y=a+(PoslidovnistFib(N-k-2)/PoslidovnistFib(N-k-1))*(b-a);
};
k++;
cout
Out
}
while(k!=N-3);
k = 0;
cout
Out
do
{
cout
Out
k++;
}
while(k!=N-3);
y=x+eps;
if (f(x)
{
b=y;
}
if (f(x)>f(y))
{
a=x;
};
x = (b+a)/2;
cout
Out
Out.close();
return 0;
}
double PoslidovnistFib(double n)
{
double f0,fk,p;
f0=1;
fk=1;
for(int i=2;i
{
p=fk;
fk=fk+f0;
f0=p;
}
if (n
{
fk=1;
}
return fk;
};
Результат виконання рограми:
Solutionof Fibonachi method:
N =17
kabXkYkF(Xk)F(Yk)
0020.7639321.23607-50.8575-59.9845
10.76393221.236071.52786-59.9845-53.5866
20.7639321.527861.055731.23607-58.9696-59.9845
31.055731.527861.236071.34752-59.9845-58.8184
41.055731.347521.167181.23607-59.998-59.9845
51.055731.236071.124611.16718-59.7535-59.998
61.124611.236071.167181.1935-59.998-60.0537
71.167181.236071.19351.20975-60.0537-60.0508
81.167181.209751.183441.1935-60.0411-60.0537
91.183441.209751.19351.19969-60.0537-60.056
101.19351.209751.199691.20356-60.056-60.0553
111.19351.203561.197371.19969-60.0556-60.056
121.197371.203561.199691.20124-60.056-60.0559
131.197371.201241.198921.19969-60.0559-60.056
141.198921.201241.199691.20046-60.056-60.056
Fi(N)= 004112A8
k =0Fi(N-k-1) = 1597Fi(N-k-2) = 987Fi(N-k-3) = 610
k =1Fi(N-k-1) = 987Fi(N-k-2) = 610Fi(N-k-3) = 377
k =2Fi(N-k-1) = 610Fi(N-k-2) = 377Fi(N-k-3) = 233
k =3Fi(N-k-1) = 377Fi(N-k-2) = 233Fi(N-k-3) = 144
k =4Fi(N-k-1) = 233Fi(N-k-2) = 144Fi(N-k-3) = 89
k =5Fi(N-k-1) = 144Fi(N-k-2) = 89Fi(N-k-3) = 55
k =6Fi(N-k-1) = 89Fi(N-k-2) = 55Fi(N-k-3) = 34
k =7Fi(N-k-1) = 55Fi(N-k-2) = 34Fi(N-k-3) = 21
k =8Fi(N-k-1) = 34Fi(N-k-2) = 21Fi(N-k-3) = 13
k =9Fi(N-k-1) = 21Fi(N-k-2) = 13Fi(N-k-3) = 8
k =10Fi(N-k-1) = 13Fi(N-k-2) = 8Fi(N-k-3) = 5
k =11Fi(N-k-1) = 8Fi(N-k-2) = 5Fi(N-k-3) = 3
k =12Fi(N-k-1) = 5Fi(N-k-2) = 3Fi(N-k-3) = 2
k =13Fi(N-k-1) = 3Fi(N-k-2) = 2Fi(N-k-3) = 1
x =1.20046f(x) = -60.056
Список використаної літератури
1. Таха, Хемди А. Введение в исследование операций, 7-е издание.:Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 912с.: ил. – Парал. тит.англ.
2. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации:учеб. пособие-2-ое изд.-М.: ФИЗМАТЛИТ, 2005
3. Н.И. Глебов, Ю.А. Кочетов, А.В. Плясунов. Методыоптимизации: учебное пособие. — Новосибирск: Новосибирский государственныйуниверситет, 2000. – 105 с.
4. Васильев Ф.П. Методы оптимизации. – М.: Издательство «ФакториалПресс», 2002. – 824 с.
5. Волков И.К., Загоруйко Е.А. Исследование операций-М.: МГТУ им. Н.Э.Баумана, 2000
6. Бейко И.В. и др.Методы и алгоритмы решения задач оптимизации. К: Высш.шк., 1983. – 513с
7. Ю. А. Кочетов, А.В.Плясунов. Методы оптимизации: учебное пособие. — Новосибирск: Новосибирскийгосударственный университет, 2000. – 105 с.