Завдання оптимізації

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.


Нажми чтобы узнать.
скачати

Рязанська

ВИЩА ПОВІТРЯНО-десантного командного

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

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

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

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

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

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

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, а в -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 змінних, але ми можемо звести до двох.

Нехай Завдання оптимізації

Тоді Завдання оптимізації

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

Завдання оптимізації

Отже, треба знайти Завдання оптимізації при обмеженнях:

Завдання оптимізації

яка вирішується графічно

Візьмемо пряму Завдання оптимізації і почнемо будувати паралельні їй у напрямку антіградіента, де Завдання оптимізації .

Завдання оптимізації


Остання вершина багатокутника рішень є точка С, одержувана перетином прямих (1) і (4). Вирішуючи, отримаємо С (1, 5).

Отже, оптимальні значення будуть наступними: Завдання оптимізації , А загальні витрати часу (доби).


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

Нехай дана цільова функція Завдання оптимізації .

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

Завдання оптимізації Приклад 2. Визначити оптимальний за часом маршрут висування танкового підрозділу з пункту А в пункт F, якщо допустима швидкість руху танків до дороги Завдання оптимізації , По дорозі, за дорогою Завдання оптимізації . Видалення від дорозі пункту А одно, пункту F Завдання оптимізації . Відстань між точками В і Е дорівнює L = 90 км.

Складемо математичну модель, тобто знайдемо функцію мети. Нас цікавить час. Час висунення з пункту А в пункт F.

Завдання оптимізації

ВС = х км; DE = y км; АС = Завдання оптимізації

CD = L - x - y; DF = Завдання оптимізації

Завдання оптимізації

Складемо функцію мети, яка залежить від двох змінних

Знайдемо критичні точки

Завдання оптимізації

За даних умов Завдання оптимізації

Знайдемо значення t при отриманих x і y

Завдання оптимізації

При обчисленні значення t на кордоні, значення виходять більше, ніж 4,24 години. Отже, оптимальне рішення буде при

х = 6,9 км, у = 24 км,.

Завдання оптимізації

ВИСНОВОК

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

В даний час новітні досягнення математики і сучасної обчислювальної техніки знаходять все більш широке застосування як в економічних дослідженнях і плануванні, так і у вирішенні військових тактичних завдань. Цьому сприяє розвиток таких розділів математики як математичне програмування, теорія ігор, теорія масового обслуговування, а також бурхливий розвиток швидкодіючої електронно-обчислювальної техніки. Вже накопичений великий досвід постановки та вирішення економічних і тактичних завдань за допомогою математичних методів. Особливо успішно розвиваються методи оптимального управління. Яскравим прикладом застосування сучасних математичних методів є війна Америки з Іраком і «Буря в пустелі». Там швидко розвивається економіка і виробництво, де широко використовуються математичні методи.

ЛІТЕРАТУРА

1. Тихонов О. М., Костомаров Л. П. Вступні лекції з прикладної математики. М., Наука, 1984.

2. Кудрявцев Е. М. Дослідження операцій в задачах, алгоритмах і програмах. М., Наука, 1982.

3. Кузнєцов Ю. М., Кузубов В. І., Волощеноко А. В. Математичне програмування. М., Вища школа, 1980.

4. Ільїн В. А., Позняк Е. Г. Основи математичного аналізу. М., Наука, 1979.


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
34.3кб. | скачати


Схожі роботи:
Деякі завдання оптимізації в економіці
Завдання оптимізації взаємодії людини і живої природи стратегія майбутнього
Вправа - завдання - тестове завдання точки перетину
Вправа завдання тестове завдання точки перетину
Методи синтезу та оптимізації
Методи оптимізації господарства
Метод оптимізації синхросигналу
Психологічні основи оптимізації
Дослідження методів оптимізації
© Усі права захищені
написати до нас
Рейтинг@Mail.ru