7.6. Загальна класифікація задач нелінійного програмування

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

Універсального методу розв’язання нелінійних екстремальних задач не існує, тому що вони надзвичайно різноманітні. Також пояснення цього слід шукати і в тому, що математична модель задач НП у загальному випадку не є випуклою, а кількість крайніх точок ОДР нескінченна. Тому методи нелінійного програмування і розробляються під класи задач:

Контрольні запитання

1. Що є предметом вивчення нелінійного програмування?

2. Чим лінійні математичні моделі відрізняються від нелінійних?

2. Чим випукла область припустимих рішень відрізняється від вогнутої?

3. У чому зміст основних теорем нелінійного програмування?

4. У чому суть класичного методу визначення безумовного екстремуму?

5. Для яких типів задач застосовуються правило множників Лагранжа та узагальнене правило Лагранжа? У чому їхня суть?

6. У чому відмінність умови Куна-Таккера від інших методів?

7. Що означає «сепарабельне» програмування?

8. Наведіть загальну класифікацію задач нелінійного програмування.

9. Наведіть приклади практичного використання задач НП.

8. Розв’язання багатокритеріальних задач

8.1. Основні визначення та моделі багатокритеріальних задач

Багатокритеріальні задачі – це клас задач, які мають не одну, а множину (вектор) цільових функцій z(z₁, z₂, …z_n):

;

;

…

;

…

.

До варіантів розв’язання багатокритеріальних задач можна віднести метод лінійної згортки та метод поступок.

Метод лінійної згортки полягає в зведенні множини цільових функцій до однієї цільової функції за допомогою коефіцієнтів:

.

Ідея методу така.

1. Розрахунок _i (змінних Лагранжа) за допомогою ранжування кожної цільової функції (зважування).

2. Зведення всіх цільових функцій z_i до однієї одиниці вимірювання (якщо f – стільці, то  – гроші).

3. Зведення всіх цільових функцій z_i до одного знака (множенням правої або лівої частини на -1).

М етод поступок полягає в існуванні ієрархії цільових функцій:

де – важливіше.

Ідея методу полягає в розробці укрупненого алгоритму, в якому задача розв’язується згідно з ієрархією критеріїв. Спершу задача розв’язується за найвищим критерієм z₂. Результат підставляється в наступний блок і розв’язок відбувається за наступним менш важливим критерієм z₃. Далі аналогічно аж до z_n. Процес Error: Reference source not foundобчислення z може бути як послідовним, так і зацикленим.

Розглянемо приклад роботи серверу передачі даних (клієнт-банк):

;

;

;

;

,

де m – кількість сеансів;

x_ij – чи відправлено сеансом i файл j;

c_j – розмір файла j;

b_i – розмір сеансу i;

Примітка. Адитивний алгоритм уже розглянуто в п. 4.4.

Розв’язання задачі методом лінійної згортки не підходить, тому що модель неможливо звести до єдиної одиниці вимірювання (лінійного пакунка). Отже, проведемо декомпозицію моделі, де x^* – це залишкова множина з нерозподілених j-файлів, причому множина де x_ij = 0.