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

Рязанська

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

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

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

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

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

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

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

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.