ТЕМА 9. НЕЛІНІЙНІ ОПТИМІЗАЦІЙНІ МОДЕЛІ ЕКОНОМІЧНИХ СИСТЕМ.

1.   Задача нелінійного програмування.

2.   Геометрична інтерпретація задачі нелінійного програмування.

3.   Лінеаризація нелінійних процесів.

4.   Опукле програмування.

5.   Квадратичне програмування.

1.     Задача нелінійного програмування.

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

(9.1)

за умов

, (), (9.2)

, . (9.3)

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

2.     Геометрична інтерпретація задачі нелінійного програмування.

Геометрично цільова функція (9.1) визначає деяку поверхню, обмеження (9.2)-(9.3) визначають допустиму підмножину n-вимірного евклідового простору.

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

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

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

3.     Лінеаризація нелінійних процесів.

Часто задачу нелінійного програмування зводять до лінійного вигляду, що призводить до значних похибок. Лінеаризація нелінійних процесів є досить складним математичним завданням. Зведення нелінійної задачі до лінійної дає змогу отримати симплексним методом розв’язок, близький до розв’язку початкової нелінійної задачі. Однак при побудові наближених лінійних задач можна отримати надто грубий розв’язок, непридатний для використання.

4.     Опукле програмування.

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

Нехай задано n-вимірний лінійний простір Rⁿ. Функція , що задана на опуклій множині , називається опуклою, якщо для будь-яких двох точок та з множини X і будь-якого виконується співвідношення:

. (9.4)

Якщо нерівність строга і виконується для , то функція називається строго опуклою.

Функція , задана на опуклій множині , називається угнутою, якщо для будь-яких двох точок та з множини X і будь-якого виконується співвідношення:

. (9.5)

Якщо нерівність строга і виконується для , то функція називається строго угнутою.

Розглянемо загальний вигляд задачі опуклого програмування.

, (9.6)

, (9.7)

, (9.8)

де , – угнуті функції.

Якщо позначити , , тоді і маємо еквівалентну задачу для опуклих функції:

; (9.9)

; (9.10)

, (9.11)

де , – опуклі функції.

Оскільки задачі еквівалентні, далі розглядатимемо задачу (9.6)-(9.8).

Множина допустимих планів, що визначається системою (9.7), є опуклою.

Точка локального максимуму (мінімуму) задачі опуклого програмування (9.6)-(9.8) є одночасно її глобальним максимумом (мінімумом).

Таким чином, якщо визначено точку локального екстремуму задачі опуклого програмування, це означає, що знайдено точку глобального максимуму (мінімуму).

5.     Квадратичне програмування.

Окремим випадком задач опуклого програмування є задачі квадратичного програмування.

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

; (9.12)

; (9.13)

. (9.14)

Квадратична функція n змінних називається квадратичною формою і може бути подана у вигляді:

, (9.15)

де ;

;

.

Зазначимо, що матриця С симетрична:

(). (9.16)

Квадратична форма називається від’ємно визначеною, якщо для всіх Х, крім Х = 0, значення  < 0 (якщо , то маємо від’ємно напіввизначену квадратичну форму), у протилежному випадку є додатньо визначеною (якщо , то маємо додатньо напіввизначену квадратичну форму).

Квадратична форма називається невизначеною, якщо вона додатна для одних значень Х і від’ємна для інших.

Вид квадратичної форми можна визначити, використовуючи вектор характеристичних коренів (власних значень) матриці С:

. (9.17)

Вектор характеристичних коренів матриці С є вектором, кожна компонента якого задовольняє систему рівнянь виду:

. (9.18)

Система має ненульовий розв’язок, якщо:

. (9.19)

Таке рівняння називається характеристичним рівнянням матриці С і має коренів, які утворюють вектор :

. (9.20)

Від’ємно визначена квадратична форма є угнутою, а додатна – опуклою.

Рекомендована література: [1; 2; 4; 5; 9; 10; 11].