ЧИСЕЛЬНІ МЕТОДИ
Чисельні методи розв’язування задач оптимізації
методичні вказівки до лабораторної роботи № 9
для студентів напряму 6.050101 „Комп’ютерні науки”
Методичні вказівки обговорені та схвалені на засіданні Науково-методичної ради інституту комп’ютерних наук та інформаційних технологій Національного університету «Львівська політехніка». Протокол № ____ від _______________2017
Укладачі: Висоцька В.А., к.т.н., доцент кафедри ІСМ
Методичні вказівки до лабораторних робіт з дисципліни «Чисельні методи» для студентів напряму 6.050101 „Комп’ютерні науки” /Укл.: В.А.Висоцька.
Лабораторна робота № 9
на тему " Чисельні методи розв’язування задач оптимізації "
Мета роботи: вивчити основні поняття чисельних методів розв’язування задач оптимізації
Короткі теоретичні відомості
В техніці, економіці та природничих науках, як і в інших областях, часто виникають задачі оптимізації складної сукупності обладнання, операцій, ланцюгів або процесів. Потрібно мінімізувати або максимізувати деяку функцію, яка називається цільовою функцією. Вона може характеризувати ціну, вагу, загальну ефективність або дещо подібне при визначених обмеженнях. Подібні задачі оптимізації, сформульовані математично, можуть бути об’єднані під загальною назвою задача нелінійного програмування; методи рішення таких задач лежать в основі нелінійного програмування. В самому широкому розумінні задача нелінійного програмування полягає в пошуку екстремуму цільової функції при заданих обмеженнях у вигляді рівностей і (або) нерівностей. Обмеження можуть бути лінійними і (або) нелінійними. Однак, загально прийнятою є більш вузька постановка загальної задачі нелінійного програмування, в якій виключаються з розгляду наступні часткові випадки:
а) змінні можуть приймати тільки цілочисельні значення (нелінійне цілочисельне програмування);
б) обмеження містять як параметр час (оптимальне управління, динамічна оптимізація).
Змінні задачі можуть бути конструктивними параметрами, показниками регулятора, показами вимірювальних приладів, тощо, тоді як цільова функція може представляти собою вартість, вагу, річний прибуток тощо, а обмеження – технічні вимоги, умови роботи, пропускна здатність або фактори безпеки, притаманні даному процесу. Як часткові випадки нелінійного програмування можуть розглядатись задачі лінійного та квадратичного програмування. Розгляд тільки математичної постановки задачі нелінійного програмування не дозволяє виявити всі фактори, від яких залежить оптимізація реального процесу. Доцільним є розглядати взаємозв’язок фізичної задачі та її математичної постановки.
9.1. Загальна постановка задачі оптимізації
9.1.1. Визначення цільової функції
Задача оптимізації – задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції. У задачах математичного програмування з одним критерієм потрібно визначити значення цільовий функція, що відповідає, наприклад, мінімальним витратам або максимальному прибуткові. Однак, небагато подумавши, ми практично в будь-якій реальній ситуації знайдемо кілька мет, що суперечать один одному. Покажемо, наскільки широкий діапазон проблем, що можуть бути адекватно сформульовані як багатокритеріальні, і які характеристики варто використовувати як критерії.
- Планування очищення нафти
- min {витрати},
- min {кількість імпортованої сирої нафти},
- min {кількість сировини з високим змістом сірки},
- min {відхилення від заданого складу},
- min {згоряння газів}.
- Планування виробництва
- мах {сумарний чистий доход},
- мах {мінімальний чистий доход за будь-який період},
- min {число невиконаних замовлень},
- min {понаднормовий час},
- min {запаси готової продукції}.
- Вибір портфеля цінних паперів
- мах {доход},
- min {ризик},
- мах {дивіденди},
- min {відхилення від бажаного рівня розмаїтості паперів}.
- Складання кошторису капіталовкладень
- мах {наявність засобів},
- min {попит на капітальні вкладення},
- min {щорічні експлуатаційні витрати},
- max {інвестиції в проекти, зв’язані з охороною навколишнього середовища},
- max {інвестиція в проекти в заданому регіоні},
- max {інвестиції в проекти по заданій товарній спеціалізації}.
- Керування лісовим господарством
- max {стійкий врожай деревини},
- max {людино-дні відпочинку в лісі},
- max {людино-дні полювання в лісі},
- max {ареал поширення дике тварин},
- max {число місяців випасу домашнього тварин},
- min {перевищення бюджету}.
- Керування попусками водоймищ
- max {вигоди від рекреації на водоймище № 1},
- max {вигоди від зарегулювання стоку нижче водоймища № 1},
- max {кількість енергії, вироблюваної в басейні ріки},
- min {недопоставки води на комунальні нестатки в басейні ріки},
- max {вигоди від рекреації на водоймище № 2},
- max {прибуток від зрошення земель нижче водоймища № 2}.
- Формування ревізійної служби у фірмі
- max {доход},
- min {ріст чисельності персоналу служби},
- min {зменшення чисельності персоналу служби},
- min {надлишкові понаднормові},
- min {недовикористання кваліфікації кадрів},
- max {час, відведений на професійний ріст}.
- Транспортування
- min {вартість},
- min {середній час доставки вантажів пріоритетним клієнтам},
- max {виробництво за заданою технологією},
- min {витрата палива}.
- Виготовлення суміші для сосисок, копченої ковбаси і салямі
- min {вартість},
- min {жирність},
- min {відхилення від необхідного кольору},
- max {протеїн},
- min {відхилення від необхідного змісту вологи},
- min {відхилення від необхідної пропорції свинини і яловичини}.
Таким чином, для ефективного рішення кожної з даних задач необхідно в першу чергу побудувати многокритериальную математичну модель, що потім потрібно оптимизировать, попередньо вибравши найбільш підходящий для цей метод.
Необхідність використання ПК пояснюється складністю тих задач, які розв’язуються. Для знаходження оптимального рішення використовують різні методи оптимізації, які в загальному випадку можна розділити на наступні класи: аналітичні, числові, графічні, експериментальні і ін. Математичне програмування включає в себе лінійне, нелінійне, ди-намічне, стохастичне і ін. програмування. Як частковий випадок, розглянуто в даній роботі нелінійне програмування, постановка за-дачі якого подано нижче. Воно має справу з оптимізацією нелінійних функцій при лінійних і (або) нелінійних обмеженнях. Типовими областями його застосування є прогнозування, планування промислового виробництва, управління ресурсами, контроль якості продукції, проектування технологічних ліній (процесів), облік і планування капіталовкладень. Поки що не існує загального методу рішення нелінійних задач оптимізації. Нелінійне програмування при вирішенні задач включає в себе елементи експериментування. Його розвиток до сих пір зводився до пропонування часткових алгоритмів, їх програмування, перевірки результатів застосування цих алгоритмів в конкретних задачах, які представляють практичний інтерес, і побудова кращих алгоритмів на основі набутого досвіду.
Визначати стратегію поведінки і приймати рішення нам постійно доводиться в повсякденному житті. Ці питання постають як перед окремими людьми, так і цілими колективами, організаціями, підприємствами (ми вживатимо термін “складні системи”), які у своїй діяльності повинні брати до уваги різні обставини, що можуть вплинути на досягнення мети. Для прийняття прийняття більшості рішень на побутовому рівні науковий підхід не є вкрай необхідний, тут людині достатньо керуватися досвідом і здоровим глуздом. Але для прийняття відповідних рішень, особливо коли потрібно передбачити вплив багатьох чинників або ціна помилки може виявитися надто високою, наукове обгрунтування діяльності стає не тільки бажаним, а й необхідним. Нас цікавитимуть математичні методи, які застосовуються для планування діяльності, прийняття рішень і оцінки ефективності функціонування складних систем. Хоча поодинокі випадки розробок і застосувань подібних методів зустрічалися в працях вчених минулого (наприклад, Й. Бернуллі, Л. Ейлера, Ж. Л. Лагранжа), проте лише у 30-40-х роках ХХ століття дослідження у сфері прийняття рішень оформилися в окремий науковий напрямок, який дістав назву “дослідження операцій”.
9.1.2. Формальне визначення задачі оптимізації
Нехай задано деяку множину X із n-вимірного евклідового простору і функцію f(x), визначену на X. Необхідно знайти точки мінімуму значень функції f(x) на X. Або:
f(x) → min, x Î X. (9.1)
Тут f(x) – цільова функція, X – допустима множина, кожна точка x цієї множини – допустима точка задачі. Також, задачу оптимізації можна сформулювати як пошук максимуму (максимумів) цільової функції:
f(x) → max, x Î X. (9.2)
Ця задача еквівалентна попередній задачі мінімізації цільової функції зі знаком мінус, в тому сенсі, що множини їхніх розв’язків збігаються.
Розв’язки задачі можна розділити на дві множини:
- глобальні (глобального мінімуму), це такі допустимі точки x*, в яких цільова функція має найменше значення на всій допустимій області:
f(x*) ≤ f(x), " x Î X; (9.3)
- локальні (локального мінімуму), це такі допустимі точки x*, в яких цільова функція приймає найменше значення в деякому околі:
f(x*) ≤ f(x), " x Î X ∩ Uε(x*), (9.4)
де – куля радіусу ε в центрі x*.
9.1.3. Класифікація задач оптимізації
- Задача безумовної оптимізації – задача оптимізації, допустимою множиною якої є весь евклідів простір (Rn):
, . Одним із методів розв’язання задач оптимізації є метод найшвидшого спуску.
- Задача умовної оптимізації – задача оптимізації, допустима множина X якої є власною підмножиною Rn. Способи розв’язку задач умовної оптимізації значною мірою залежать від того, як задається допустима множина.
- Задача математичного програмування (або задача з рівностями та нерівностями) – задача умовної оптимізації, допустима множина якої має вигляд:
Формально задача математичного програмування записується так:
Обмеження gi називаються функціональними обмеженнями, а x Î P – прямим.
- Задача опуклого програмування – задача оптимізації, цільова функція та допустима множина якої – опуклі:
f(x) → min, x Î X. (9.8)
де f(x) – опукла функція, X – опукла множина.
- Чисельні методи оптимізації
- Багатокритеріальна оптимізація або програмування (англ. Multi-objective optimization) – це процес одночасної оптимізації двох або більше конфліктуючих цільових функцій в заданій області визначення. Задача багатокритеріальної оптимізації зустрічаються в багатьох галузях науки та техніки.
На практиці задачі, що не мають невизначеностей, скоріше є вийнятком, ніж правилом. Поряд з розглянутими вище існує ще один важливий вид невизначеності – невизначеність мети, яка виявляється у наявності декількох, в більшості випадків незбіжних аспектів оцінки якості того чи іншого рішення з множини припустимих. В формальному вигляді аспекти оцінки якості відображаються за допомогою множини критеріїв. Таким чином виникає багатокритерійна задача дослідження операцій, загальний вигляд якої наступний: . Знайти розв’язок, який одночасно був би найкращим за всіма критеріями, неможливо, тому що в загальному випадку покращення значення одного з критеріїв приводить до його погіршення.
Приклади. Купівля автомобілю. Важливими критеріями в цьому випадку є питомі витрати пального, максимальна швидкість, комфортність, прохідність, зовнішній вигляд, вартість, ґарантія, наявність сервісного обслуговування, ціна, і звичайно, придбати авто, яке б водночас витрачало найменше пального, було б при цьому найдешевшим, найкомфортнішим та найшвидшим неможливо. Вибір місця зупинки для мандрівників у горах. Важливими критеріями є наявність джерела або річки, наявність палива, можливість купання, наявність комарів, близькість до населених пунктів, відсутність хижих звірів. Одним з найбільш розповсюджених способів є приведення множини критеріїв до одного глобального та розв’язування класичної однокритерійної задачі. Однак застосування цього підходу має суттєві вади, і однією з них є те, що отриманий розв’язок для деяких специфічних задач може навіть не належати до множини Парето-оптимальних. Методи згортання критеріїв приводять первісну задачу до однокритерійної задачі такого вигляду: . Найбільш вживаними є:
- Лінійна згортка:
Згортка нормованих критеріїв:
В цих методах — вагові коефіцієнти критеріїв, які повинні відображати їх важливість, — мінімальне та максимальне значення і-го критерію.
Основною проблемою цих методів є проблема виявлення точних значень вагових коефіцієнтів – ця процедура в більшості випадків є суб’єктивною. Окрім того, коефіцієнти в методі лінійної згортання повинні бути розмірними величинами, тому що критерії в більшості випадків мають різну розмірність. З метою позбавлення від цього недоліку в згортці нормованих критеріїв окремі критерії спочатку нормуються (нормовані критерії є безрозмірними та змінюються в інтервалі від 0 до 1). Але внаслідок такого “вдосконалення” зважуються нормовані критерії, які не мають змістовного навантаження, і тому об’єктивне визначення вагових коефіцієнтів ще більш ускладнюється. Як казав один з фахівців в галузі ДО – довільність (що викликана багатокритерійністю) переноситься в іншу інстанцію (визначення значень вагових коефіцієнтів).
Інший підхід до розв’язання проблеми багатокритерійності - аксіоматичний, що полягає в формулюванні множини аксіом з наступним формальним виведенням виду функції корисності (глобального критерію), за допомогою якого й здійснюватиметься остаточний вибір. У цьому випадку виявляються всі обмеження, які побічно накладаються при еврістичному застосуванні того чи іншого методу. Виявляється, що лінійна згортка обґрунтована при достатньо жорстких умовах, які в багатьох випадках не виконуються.
(Для ознайомлення з повним текстом статті необхідно залогінитись)