Розділ 10     Методи оптимізації і планування.

 

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

 

10.1     Класична постановка задачі оптимізації

 

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

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

 

10.2.     Класифікація задач оптимізації

 

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

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

Класифікацію цих задач наведено на рисунку 5.1.

До цього треба додати деякий коментар:

1.  Якщо існує декілька цільових функцій, то має місце задача векторної оптимізації.

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

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

4.  Математичне програмування об’єднує задачі нелінійного програмування (цільова функція в загальному випадку нелінійна), стохастичного програмування (параметри – випадкова величина, а цільова функція – випадкова функція), динамічного програмування (оптимізація багатокрокових процесів пошуку рішення).

5.  Якщо параметри, що керуються, приймають тільки дискретні значення, то виникає задача дискретної оптимізації, а якщо – цілі числа, то – задача цілочислового програмування.

6.  У випадку, коли цільова функція опукла, та область, де задані , теж опукла, то має місце задача опуклого програмування. Якщо цільова функція та умови лінійні-лінійного (кусково-лінійного) програмування; цільова функція квадратична, а умови лінійні-квадратичного програмування; цільова функція та умови – лінійні комбінації функцій однієї змінної – сепарабельного програмування; цільова функція та умови подані у вигляді поліномів – геометричного програмування.

 

10.3     Багатокритеріальна оптимізація

 

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

Рисунок 5.1 – Класифікація задач оптимізації

 

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

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

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