Рязанська

ВИЩА повітряно-десантного командного

двічі Червонопрапорного училища

ІМЕНІ генерала армії Маргелова В.Ф.

Кафедра вищої математики та теоретичної механіки

Курсова робота

ЗАВДАННЯ ОПТИМІЗАЦІЇ

Виконав курсант: Валуйкін Олександр Володимирович

4 взводу роти 8

Керівник роботи: Щукіна Наталія Василівна

Рязань - 2001 р.

ЗМІСТ

Вступ ........................................... .................................................. ..................................... 3

§ 1. ПОСТАНОВКА ЗАДАЧ ОПТИМІЗАЦІЇ ............................................... ....................... 5

§ 2 Задача лінійного програмування ....................................... ................. 7

§ 3 АНАЛІТИЧНИЙ МЕТОД ОПТИМІЗАЦІЇ ....................................... .................... 13

ВИСНОВОК ........................................... .................................................. ............................ 15

ЛІТЕРАТУРА ........................................... .................................................. .............................. 16 Введення

Кожна людина час від часу опиняється в ситуації, коли досягнення певного результату може бути здійснено не єдиним способом. У таких випадках доводиться відшукувати найкращий спосіб. Однак у різних ситуаціях найкращими можуть бути зовсім різні рішення. Все залежить від обраного або заданого критерію. На практиці виявляється, що в більшості випадків поняття «найкращий» може бути виражена кількісними критеріями - мінімум витрат, мінімум часу, максимум прибутку і т.д. Тому можлива постановка математичних задач відшукання оптимального (optimum - найкращий) результату, тому що принципових відмінностей у відшуканні найменшого чи найбільшого значення немає. Задачі на відшукання оптимального рішення називаються завданнями оптимізації. Оптимальний результат, як правило, знаходиться не відразу, а в результаті процесу, що називається процесом оптимізації. Застосовувані в процесі оптимізації методи отримали назва методів оптимізації. Щоб вирішити практичне завдання треба перевести її на математичний мова, тобто скласти її математичну модель.

Математична модель являє собою струнку і глибоку сукупність знань про математичних моделях зі своїми проблемами, з власними шляхами розвитку, зумовленими внутрішніми і зовнішніми причинами і завданнями. Математика дає зручні і плідні способи опису найрізноманітніших явищ реального світу і тим самим виконує в цьому сенсі функцію мови. Цю роль математики чудово усвідомлював Галілей, який сказав: «Філософія написана в грандіозної книзі - Всесвіту, яка відкрита нашому пильному погляду. Але зрозуміти цю книгу може лише той, хто навчився розуміти її мову і знаки, якими вона викладена. Написана ж вона на мові математики ».

Отже, математика - це область людського знання, в якій вивчаються математичні моделі.

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

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

У курсової роботі з методів оптимізації пропонується дві задачі: задача лінійного програмування та спільне завдання оптимізації, яке вирішується аналітичним методом. § 1. ПОСТАНОВКА ЗАДАЧ ОПТИМІЗАЦІЇ

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

Найкращі у певному сенсі вирішення завдань прийнято називати оптимальними. Без використання принципів оптимізації в даний час не вирішується жодна більш-менш складна проблема. При постановці і вирішенні задач оптимізації виникають два питання: що і як оптимізувати?

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

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

Складовою частиною методів оптимізації є лінійне програмування. § 2 Задача лінійного програмування

Вперше постановка задачі лінійного програмування у вигляді пропозиції щодо складання оптимального плану перевезень; що дозволяє мінімізувати сумарною кілометраж, була дана в роботі радянського економіста А. Н. Толстого в 1930 році.

Систематичні дослідження задач лінійного програмування та розробка спільних методів їх вирішення отримали подальший розвиток у роботах російських математиків Л. В. Канторовича, В. С. Немчинова та інших математиків та економістів. Також методів лінійного програмування присвячено багато робіт зарубіжних і перш за все американських вчених.

Задача лінійного програмування полягає в наступному: максимізувати (мінімізувати) лінійну функцію

, де

при обмеженнях

(*)

причому всі

Зауваження. Нерівності можуть бути й протилежного змісту. Множенням відповідних нерівностей на (-1) можна завжди отримати систему виду (*).

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

Отже, треба максимізувати функцію і задовольняє системі обмежень.

Звернемося до одного з нерівностей системи обмежень.

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

Зауваження 2. Якщо , то простіше взяти точку (0; 0) .

Умови точність також визначають півплощини відповідно з граничними прямими . Будемо вважати, що система нерівностей спільно, тоді півплощини, перетинаючись, утворюють спільну частину, яка є опуклим множиною і являє собою сукупність точок, координати яких є вирішенням даної системи - це безліч припустимих рішень. Сукупність цих точок (рішень) називається багатокутників рішень. Він може бути точкою, променем, багатокутника, необмеженої багатокутною областю. Таким чином, задача лінійного програмування полягає в знаходженні такої точки багатокутника рішень, в якій цільова функція приймає максимальне (мінімальне) значення. Ця точка існує тоді, коли багатокутник рішень не зруйнований, а на ньому цільова функція обмежена зверху (знизу). За зазначених умовах в одній з вершин багатокутника рішень цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо пряму (де h - деяка постійна). Найчастіше береться пряма . Залишається з'ясувати напрямок руху даної прямої. Цей напрямок визначається градієнтом (антіградіентом) цільової функції

Вектор в кожній точці перпендикулярній прямий , тому значення f буде зростати при переміщенні прямий в напрямку градієнта (спадати в напрямку антіградіента). Для цього паралельно прямий проводимо прямі, зміщуючись в напрямку градієнта (антіградіента).

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

Отже, знаходження рішення задачі лінійного програмування геометричним методом включає наступні етапи:

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

2. Знаходять півплощини, що визначаються кожним з обмежень задачі.

3. Знаходять багатокутник рішень.

4. Будують вектор .

5. Будують пряму .

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

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

Приклад 1. Два великих військових з'єднання і до нового місця дислокації перевозяться по залізниці. Для їхнього навантаження виділяються три станції , з різними можливостями. Перевезення з'єднань здійснюється з дотриманням таких обмежень:

1. Кількість перевезених частин у з'єднанні одно 6, а в < img src = "http://localhost/uploads/posts/2009-10/1255896846_Zadachi_optimizacii_30.gif" alt = "" width = "23" height = "25" /> -9.

2. Кожна станція може прийняти певну кількість частин: .

3. На навантаження однієї частини станції витрачають різний час (у добі), яка вказана в таблиці.        З'єднання         Станція навантаження                                                        3,0   4,5         4,0   6,5         2,5   3,5     

Визначити оптимальний варіант розподілу частин по станціях навантаження, виходячи з мінімуму сумарних витрат часу на завантаження.

Рішення.

Рішення штабів з'єднань полягає у розподілі частин по станціях навантаження. Позначимо через число частин i-го з'єднання (i = 1,2) на j-ої станції (j = 1, 2, 3).

Ми можемо записати:

кількість частин з'єднань на станціях навантаження відповідно.

- кількість частин з'єднання на місцях навантаження.

- кількість частин з'єднання на місцях навантаження.

Загальна сума витрат часу (в добі) на навантаження є

У цьому завданні 6 змінних, але ми можемо звести до двох.

Нехай

Тоді

Цільова функція має вигляд

Отже, треба знайти при обмеженнях: