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

Подождите немного. Документ загружается.

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

ПОЛТАВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

ІМЕНІ ЮРІЯ КОНДРАТЮКА

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

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

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

з дисципліни

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

на тему:

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

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

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

301-ЕІ. 20 06165 КР

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

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

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

Розробила

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

Клюєва А. Ю.

Полтава 2009

Зміст

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

а) Метод дихотомії...............................................................................................4

б) Метод золотого перерізу.................................................................................4

в) Метод Фібоначчі..............................................................................................5

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

допомогою методів одновимірної опимізації.......................................................6

а) Метод дихотомії...............................................................................................6

б) Метод золотого перетину...............................................................................9

в) Метод Фібоначчі............................................................................................12

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

найшвидшого спуску............................................................................................15

а) Метод Ньютона..............................................................................................15

б) Метод найшвидшого спуску.........................................................................17

4. Розв’язання задачі умовної оптимізації за допомогою методу

Франка-Вулфа і методу штрафних функції.......................................................20

а) Метод Франка-Вулфа....................................................................................20

б) Метод штрафних функцій.............................................................................24

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

а) Графічно..........................................................................................................28

б) Метод Гоморі.................................................................................................28

в) Метод Ленг і Дойг.........................................................................................30

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

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

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

задач

Розглянемо детально методи розв’язування одновимірних задач, а

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

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

, в якій

цільова функція

)(

приймає максимальне або мінімальне значення. Часто в

постановках задач може бути заданий відрізок

],[ ba

, в якому знаходиться

оптимальне рішення.

Функція

)(xf

має локальний мінімум в точці

, якщо при

довільному

0



існує окіл

],[



 xx

такий, що для всіх значень

цьому околі

)()(

xfxf 

. Функція

)(xf

має глобальний мінімум в точці

якщо для всіх х справедлива рівність

)()(

xfxf 

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

)(xf

має локальний максимум в точці

, якщо

при довільному

0



існує окіл

],[



 xx

такий, що для всіх значень

цьому околі

)()(

xfxf 

. Функція

)(xf

має глобальний мінімум в точці

якщо для всіх х справедлива рівність

)()(

xfxf 

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

в пошуку умов, яким вони повинні задовольняти. Необхідною умовою

екстремуму в точці

являється рівність нулю першої похідної (теорема

Ферма), тобто вимагається розв’язати рівняння:

0)( 



. Даному рівнянню

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

функції, тому приведена умова є лише необхідною умовою, але не

достатньою.

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

других похідних в точках, що задовольняють рівняння

0)( 



. При цьому

доведено, що мінімуму функції відповідає додатне значення другої похідної,

тобто

0)(





, а максимуму – від’ємне, тобто

0)(





. Однак, якщо друга

похідна дорівнює 0, ситуація залишається невизначеною і необхідно

досліджувати вищі похідні. При цьому якщо перша вища похідна не рівна

нулю має парний порядок, то екстремум існує, в іншому випадку – ні.

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

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

)(xf

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

],[ ba

якщо:

 точка

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

],[ ba

;

 для довільних двох точок відрізка х

і х

, взятих по одну сторону

від точки мінімуму, точці х

більш близькій до точки мінімуму

відповідає менше значення функції, тобто при

xxx 

або при

xxx 

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

)()(

xfxf 

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

)(xf

на відрізку

],[ ba

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

Якщо функція

)(xf

двічі диференційована на відрізку

],[ ba

0)(





в будь-якій точці цього відрізка, то

)(xf

- унімодальна функція на

відрізку

],[ ba

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

0)(





визначає множину точок, на якій

функція являється опуклою вниз. Умова ж

0)(





визначає опуклу вгору

функцію, яка на відрізку

],[ ba

має максимум і також являється

унімодальною.

Метод половинного ділення, який також називається методом

дихотомії, являється процедурою послідовного пошуку мінімуму фунуції.

Нехай визначено відрізок

],[

, якому належить точка локального

мінімуму х, і функція

)(xf

являється унімодальною на цьому відрізку. Далі

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

розташовані симетрично на відстані

0



від середини відрізка:









;







Константа



повинна бути меншою допустимої кінцевої довжини

відрізка, Δk= b

- a

> 0.

Потім обчислюють значення функції в цих точках y

=f(x

) і y

=f(x

) і в

залежності від їх співвідношення нові межі відрізка унімодальності [a

, b

]

будуть наступні:

• y

< y

, a

і b

;

• y

> y

, a

і b

;

• y

= y

, a

і b

= x

В цьому звуженому проміжку [a

, b

] знову розраховуються дві точки

(1)

і х

(1)

, симетричні відносно його середини і значення функції в цих точках.

Процедура буде продовжуватись до тих пір, поки не буде виконуватись

умова Δk = b

-a

≤ ε, де ε – точність пошуку, і тоді в якості точки локального

мінімуму можна наближено прийняти середину відрізку





Назва методу половинного ділення мотивована тим, що якщо

величина ε достатньо мала, то довжина відрізка унімодальності (b – a)

зменшується майже вдвічі.

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

оптимізації є метод золотого перерізу.

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

являється

золотим перерізом відрізка

],[ ba

, якщо відношення довжини b-a всього

відрізка до довжини b-х

більшої частини дорівнює відношенню довжини

більшої до довжини х

-а меншої частини, тобто х

– золотий переріз, якщо

справедлива рівність:







. Аналогічно, точка х

симетрична точці х

відносно середини відрізка

],[ ba

, являється другим золотим перерізом цього

відрізка.

Відмітимо властивість золотого перерізу: точка х

одночасно

являється золотим перерізом відрізка

],[

, а друга точка х

– золотим

перерізом відрізка

],[

Суть методу золотого перерізу заклечається в наступному. Спочатку

на вихідному відрізку

],[

знаходяться точки х

і х

по наступним

формулам:

);(

);()1(

0001

abkax





...618,0k

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

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

і х

, тобто

)()(

2211

xfyixfy 

. При цьому можливі два випадки:

yy 

, в цьому випадку новий відрізок буде рівним

aa 

xb 

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

.)1(),()1()1(

121111

xxabkax 

yy 

, тоді новий відрізок будуть становити:

0111

bbixa 

. На

новому відрізку також обираються дві точки

.)()1(,)1(

111221

abkaxxx 

І в першому і в другому випадках розраховується лише одна нова

точка (друга відома). В новій точці обчислюється значення функції і знову

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

новий відрізок. Процедура виконується до тих пір, доки не буде

виконуватись умова



 )(

, де



- точність пошуку.

Розглянемо також метод Фібоначчі для розв’язування одновимірних

задач . Цей метод названий так зважаючи на появу при пошуку проміжків

унімрдальності чисел Фібоначчі і використовується, якщо кількість ітерації

обмежена . Суть методу в тому, що на кожному кроці точка наступного

обчислення обирається симетрично відносно середини відрізка локалізації до

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

Тобто в процесі пошуку інтервалу (x1; x3) з точкою х2, вже лежачою в

цьому інтервалі, наступна точка х4 завжди вибирається так, що х3–х4 =

х2–х1 або х4-х1 = х3-x2, тобто x4=х1-х2+х3.

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

1) задаються початкові границі відрізку

, точність обчислень



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

- це число із послідовності Фібоначчі, яке знаходиться з умови

b a







, Таким чином визначається також число ітерацій n. В точках

1 2

,x x

знаходять значення цільової функції: .

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

 якщо , то ,

 

2 1 1 1

,y y y f x 

 інакше ,

 

1 2 2 2

,y y y f x 

4) якщо n=1, то і зупиняються. Значення цільової функції в

цій точці і буде мінімумом функції. Інакше повертаються до 3-го кроку.

Відмітимо, що на кожному кроці методу Фібоначчі точка, що лежить

середині відрізку локалізації, ділить його у відношенні двох послідовних

чисел Фібоначчі.

II. Визначення найменшого значення функції на

заданому відрізку за допомогою методів одновимірної

оптимізації

Визначимо найменше значення функції

1964085)(

234

 xxxxxF

на

відрізку

]2,0[

з точністю

001,0



, використовуючи



метод дихотомії:

Розіб’ємо відрізок

]2,0[

навпіл і візьмемо дві симетричні відносно

центру точки

xix

такі, що











;

, де







і відкинемо ту

з точок, до якої ближче виявилась одна з двох знову поставлених точок з

максимальним значенням.

.0005,10005,010005,0

;9995,00005,01

001,0























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

)(xF

в цих точках:

.01,5810005,1960005,1400005,180005,15)0005,1()(

;99,5719995,0969995,0409995,089995,05)9995,0()(

234



FxF

Оскільки

)()(

xFxF 

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

9995,0

xa

bb

. В

цьому звуженому проміжку знову розраховуємо дві точки, симетричні

відносно його середини і значення функції в цих точках. Процедура буде

продовжуватись до тих пір, поки не буде виконуватись умова



 ab

В нашому випадку

001,00005,19995,02 

. Тому знову розраховуємо

дві точки:

;50025,10005,049975,10005,0

29995,0

;49925,10005,049975,10005,0

29995,0













.6781,54150025,19650025,14050025,1850025,15)50025,1()(

;7156,54149925,19649925,14049925,1849925,15)49925,1()(

234



FxF

Оскільки

)()(

xFxF 

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

9995,0a

50025,1

xb

Перевіряємо умову зупинки:

001,050075,09995,050025,1 

. Отже

продовжуємо процедуру.

.6781,54125038,19625038,14025038,1825038,15)25038,1()(

;7156,54124938,19624938,14024938,1824938,15)24938,1()(

;25038,10005,0

50025,19995,0

;24938,10005,0

50025,19995,0

234















FxF

 )()(

xFxF

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

9995,0a

25038,1

xb

. Перевіряємо

умову зупинки:

001,025088,09995,025038,1 

. Отже продовжуємо

процедуру.

.7601,59112544,19612544,14012544,1812544,15)12544,1()(

;7522,59112444,19612444,14012444,1812444,15)12444,1()(

;12544,10005,0

25038,19995,0

;12444,10005,0

25038,19995,0

234















FxF

 )()(

xFxF

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

12444,1

xa

25038,1b

. Перевіряємо

умову зупинки:

001,012594,012444,125038,1 

. Продовжуємо процедуру.

.0481,60)18791,1()(

;0467,60118691,19618691,14018691,1818691,15)18691,1()(

;18791,10005,0

25038,112444,1

;18691,10005,0

25038,112444,1

234

















FxF

 )()(

xFxF

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

18691,1

xa

25038,1b

. Перевіряємо

умову зупинки:

001,006347,018691,125038,1 

. Отже продовжуємо

процедуру.

.0359,60)21915,1()(

;038,601218115,196218115,140218115,18218115,15)218115,1()(

;21915,10005,0

25038,118691,1

;218115,10005,0

25038,118691,1

234

















FxF

 )()(

xFxF

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

18691,1a

21915,1

xb

. Перевіряємо

умову зупинки:

001,003224,018691,121915,1 

. Отже продовжуємо

процедуру.

.0553,60)20353,1()(

;0557,60120253,19620253,14020253,1820253,15)20253,1()(

;20353,10005,0

21915,118691,1

;20253,10005,0

21915,118691,1

234

















FxF

 )()(

xFxF

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

18691,1a

20353,1

xb

. Перевіряємо

умову зупинки:

001,001662,018691,120353,1 

. Отже продовжуємо

процедуру.

.055,60)19572,1()(

;0545,60119472,19619472,14019472,1819472,15)19472,1()(

;19572,10005,0

20353,118691,1

;19472,10005,0

20353,118691,1

234

















FxF

 )()(

xFxF

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

19472,1

xa

20353,1b

. Перевіряємо

умову зупинки:

001,000881,019472,120353,1 

. Продовжуємо процедуру.

.056,60)19963,1()(

;0559,60119863,19619863,14019863,1819863,15)19863,1()(

;19963,10005,0

20353,119472,1

;19863,10005,0

20353,119472,1

234

















FxF

 )()(

xFxF

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

19863,1

xa

20353,1b

. Перевіряємо

умову зупинки:

001,00049,019863,120353,1 

. Продовжуємо

процедуру.

.0559,60)20158,1()(

;056,60120058,19620058,14020058,1820058,15)20058,1()(

;20158,10005,0

20353,119863,1

;20058,10005,0

20353,119863,1

234

















FxF

 )()(

xFxF

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

19863,1a

20158,1

xb

. Перевіряємо

умову зупинки:

001,000295,019863,120158,1 

. Продовжуємо процедуру.

.056,60)20061,1()(

;056,60)19961,1()(

;20061,10005,0

20158,119863,1

;19961,10005,0

20158,119863,1















FxF

 )()(

xFxF

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

19961,1

xa

20061,1

xb

Перевіряємо умову зупинки:



 001,019961,120061,1

. Отже в якості

точки локального мінімуму можна наближено прийняти середину відрізку

200,120011,1

20061,119961,1











. Тоді мінімальне значення вихідної

функції буде рівним:

056,60120011,19620011,14020011,1820011,15)(

234*

min

 xFF



метод золотого перерізу

На першій ітерації відрізок

]2;0[

ділимо двома симетричними

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

.236,1618,0)02(0)(

;764,0618,0)02(2)(







abax

abbx

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

.9847,59)236,1()(

;8602,501764,096764,040764,08764,05)764,0()(

234





FxF

Той із кінців відрізка, до якого серед знову поставлених точок ближче

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

оскільки

)()(

xFxF 

, то покладаємо, що

,236,1,764,0

211

 xxxa

52785,1618,0)764,02(764,0)(





abax

. Тепер обчислюємо значення

функції в нових точках:

.5873,53152785,19652785,14052785,1852785,15)52785,1()(

;9847,59)236,1()()(

234





FxF

FxFxF

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

поки не буде виконуватись умова



 ab

. Отже перевіримо умову зупинки:

001,0236,1764,02 



. Тому знову аналогічно шукаємо нові межі

відрізка. Оскільки

)()(

xFxF 

маємо:

.9705,58105579,19605579,14005579,1805579,15)05579,1()(

;9847,59)236,1()()(

;05579,1618,0)764,052785,1(52785,1)(;236,1;52785,1

234

1122







FxF

FxFxF

abbxxxxb



Перевіряємо умову зупинки:

001,076385,0764,052785,1 

, тому

продовжуємо процедуру.

.8184,58134752,19634752,14034752,1834752,15)34752,1()(

;9847,59)236,1()()(

;34752,1

618,0)05579,152785,1(05579,1;236,1;05579,1)()(

234

221121









FxF

FxFxF

xxxxaxFxF

Перевіряємо умову зупинки:

001,047206,005579,152785,1 

, тому

продовжуємо процедуру.

.9981,59116723,19616723,14016723,1816723,15)16723,1()(

;9847,59)236,1()()(

;16723,1618,0

)05579,134752,1(34752,1)(;236,1;34752,1)()(

234

112221









FxF

FxFxF

abbxxxxbxFxF



Знову перевіряємо умову зупинки:

001,029173,005579,134752,1 

, отже

продовжуємо процедуру.

.7537,59112463,19612463,14012463,1812463,15)12463,1()(

;9981,59)16723,1()()(

;12463,1618,0

)05579,1236,1(236,1)(;16723,1;236,1)()(

234

112221









FxF

FxFxF

abbxxxxbxFxF



Перевіряємо умову зупинки:

001,018021,005579,1236,1 

, тому

продовжуємо процедуру.

.0537,60119346,19619346,14019346,1819346,15)19346,1()(

;9981,59)16723,1()()(

;19346,1

618,0)12463,1236,1(12463,1;16723,1;12463,1)()(

234

221121









FxF

FxFxF

xxxxaxFxF

Перевіряємо умову зупинки:

001,011137,012463,1236,1 

, отже

продовжуємо процедуру.

.0508,60120973,19620973,14020973,1820973,15)20973,1()(

;0537,60)19346,1()()(

;20973,1

618,0)16723,1236,1(16723,1;19346,1;16723,1)()(

234

221121









FxF

FxFxF

xxxxaxFxF

Перевіряємо умову зупинки:

001,006877,016723,1236,1 

, отже

продовжуємо процедуру.

.0412,60118347,19618347,14018347,1818347,15)18347,1()(

;0537,60)19346,1()()(

;18347,1

618,0)16723,120973,1(20973,1;19346,1;20973,1)()(

234

112221









FxF

FxFxF

xxxxbxFxF

Перевіряємо умову зупинки:

001,00425,016723,120973,1 

, тому

продовжуємо процедуру.

.056,6011997,1961997,1401997,181997,15)1997,1()(

;0537,60)19346,1()()(

;1997,1

618,0)18347,120973,1(18347,1;19346,1;18347,1)()(

234

221121









FxF

FxFxF

xxxxaxFxF

Перевіряємо умову зупинки:

001,002626,018347,120973,1 

, отже

продовжуємо процедуру.

.0553,60120351,19620351,14020351,1820351,15)20351,1()(

;056,60)1997,1()()(

;20351,1

618,0)19346,120973,1(19346,1;1997,1;19346,1)()(

234

221121









FxF

FxFxF

xxxxaxFxF

Перевіряємо умову зупинки:

001,001627,019346,120973,1 

, отже

продовжуємо процедуру.