Початкові відомості про задачі оптимізації

ЛЕКЦІЯ № 2

ОСНОВИ ТЕОРІЇ ОПТИМІЗАЦІЇ

Початкові відомості про задачі оптимізації

Поняття оптимальності, як і поняття процесу оптимізації, займає провідне місце не тільки в інженерній справі, економіці, менеджменті, бізнесі, воно також застосовується при вирішенні багатьох задач в соціальних, біологічних, хімічних та інших науках. Термін "оптимальний" найчастіше трактують як сприятливий, максимальний (мінімальний), найбільш ефективний тощо. Кожна людина майже щоденно, не завжди усвідомлюючи це, розв’язує задачу: як отримати найбільший ефект, маючи обмежені ресурси.

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

Розглянемо приклад, який пов’язує задачі прийняття рішень з оптимізацією. Припустимо, що при розробці моделі автомобіля нас цікавлять два показника: ціна автомобіля та максимальна швидкість, з якою він має рухатися (рис. 1). Маємо можливість вибирати потужність двигуна, кузов, варіанти окремих агрегатів, при цьому кожному фіксованому набору компонент буде відповідати ціна та максимальна швидкість автомобіля, яку можна досягти. Визначимо множини X – набори агрегатів авто, S – один стан середовища, Z – конкретні моделі автомобіля, V – максимальна швидкість, C – ціна. Ставиться задача максимізувати швидкість та мінімізувати ціну.

Наведений приклад призводить проектантів до розв’язання задачі оптимізації. Методи оптимізації дозволяють вибрати найкращий варіант виробу із усіх можливих варіантів.

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

Застосування терміну "програмування" обумовлюється почасти історичним непорозумінням, почасти неточним перекладом з англійської мови, в якій слово "programming" означає планування, складання планів або програм. Зрозуміло, що цей термін відображає тісний зв’язок, який існує між математичною постановкою задачі та її економічною інтерпретацією. Тому найменування "Математичне програмування" пов’язане з тим, що метою розв’язання задач є вибір оптимальної програми дій.

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

Останніми роками методам оптимізації приділяється значна увага, в результаті був розроблений цілий ряд високоефективних алгоритмів, які дозволяють знайти оптимальний варіант виробу за допомогою ЕОМ. Сучасна комп'ютерна техніка більш успішно справляється з подібними задачами, хоча при цьому доводиться використовувати складні методи і програми. Вони мають загальну назву "методи комп'ютерної оптимізації".

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

Розглядаючи деяку довільну систему, що описується m рівняннями з n невідомими, можна виділити три основних типи задач. Якщо m = n, задачу називають алгебраїчною. Така задача зазвичай має одне рішення. Якщо m > n, то задача є перевизначеною і, як правило, не має рішення. Нарешті, при m < n задача є недовизначеною і має безліч рішень. На практиці саме з такими задачами найчастіше доводиться мати справи. В подібних ситуаціях при формулюванні умов для вибору оптимального варіанту допомагає інтуїція того, хто розв’язує ту чи іншу практичну задачу, особливо ту, яка пов’язана з прийняттям рішення.

Перш ніж приступити до обговорення питань оптимізації розглянемо ряд визначень.

Параметри, що оптимізуються. Цим терміном позначають незалежні змінні параметри, які повністю і однозначно визначають задачу, що розв’язується. В якості параметрів, що оптимізуються, можуть бути взяті будь-які основні чи похідні величини, які застосовуються для кількісного опису виробу, процесу тощо. Кількість таких параметрів характеризує ступінь складності конкретної задачі, що розв’язується. Зазвичай кількість параметрів, що оптимізуються, позначається літерою n, а самі параметри літерою х з відповідними індексами. Таким чином, n параметрів, що оптимізуються в конкретній задачі будемо позначати як

х ₁, х ₂, х ₃, …, х_n.

Критерій оптимальності (цільова функція). Це математичний вираз задачі, що розв’язується, значення якого необхідно зробити максимальним або мінімальним. Цільова функція дозволяє кількісно порівнювати альтернативні рішення. З математичної точки зору цільова функція описує деяку (n + 1)-вимірну поверхню. Її значення визначається параметрами, що оптимізуються:

М = М (х ₁, х ₂, х ₃, …, х_n).

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

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

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

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

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

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

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