Тема 2.1. Загальна задача нелінійного програмування

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

(2.1.1)

та приводить до екстремуму функції

. (2.1.2)

При цьому припускається, що функції g_i та f відомі. Як правило, на деякі змінні х₁ … х_n накладаються умови не-від’ємності. Крім того, обмеження може бути умова цілочисельності розв’язку для ряду змінних.

Якщо

(2.1.3)

і

(2.1.4)

де a_ij та C_j – відомі константи, то при умові не-від’ємності розв’язку отримуємо задачу лінійного програмування. Будь-яку іншу задачу математичного програмування, яка не задовольняє умови (2.1.3) і (2.1.4), домовимось вважати нелінійною.

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

Розглянемо часткові випадки, коли цільова функція сепарабельна (є сумою n функцій f_j(x_j)) або квадратична.

Метод множників Лагранжа. Нехай задана задача математичного програмування: максимізувати функцію Z = f (х₁ … х_n) при обмеженнях g_i(х₁ … х_n) = 0,  і = 1…m. Обмеження в задачі задані рівняннями, тому для її розв’язування можна скористатись класичним методом відшукання умовного екстремуму функцій кількох змінних. При цьому припускаємо, що функції g_i(х_j) та f(х_j) неперервні разом зі своїми першими частинними похідними. Для розв’язання задачі складемо функцію

, (2.1.5)

визначимо частинні похідні , і прирівняємо їх до нуля. В результаті отримаємо систему рівнянь

(2.1.6)

Функція (2.1.5) називається функцією Лагранжа, а числа _і – множниками Лагранжа. Якщо функція Z = f(x_j) має в точці екстремум, то існує такий вектор , що точка є розв’язком системи (2.1.6). Отже, розв’язуючи систему (6.6), отримуємо множину точок, в яких функція Z може мати екстремальні значення. При цьому невідомим є спосіб визначення глобального мінімуму чи максимуму. Однак, якщо розв’язки системи знайдені, то для визначення глобального максимуму чи мінімуму достатньо знайти значення функції у відповідних точках.

Метод множників Лагранжа має обмежене застосування, оскільки система (2.1.6), як правило, має декілька розв’язків.

Теоретично, метод Лагранжа можна застосовувати й тоді, коли деякі обмеження мають вигляд нерівностей, а їх розв’язки мають бути не-від’ємними. Вводячи додаткові змінні, обмеження-нерівності можна перетворити у рівняння, причому на додаткові змінні накладають умову не-від’ємності. Функція Z = f(x_j) може мати екстремальні значення як на межі області, так і у внутрішній точці.

Опукле програмування. Оскільки в подальшому будуть використовуватись так звані опуклі й увігнуті функції, наведемо ряд означень. Нехай задано n-вимірний лінійний простір Rⁿ. Функція , задана на опуклій множині X  Rⁿ, називається опуклою, якщо для довільних двох точок і з множини Х і довільного числа 0    1 виконується співвідношення

. (2.1.7)

Функція , задана на опуклій множині Х, називається увігнутою, якщо для довільних двох точок і з множини Х і довільного числа 0    1 виконується співвідношення

. (2.1.8)

Якщо – опукла функція, то – – увігнута функція і навпаки.

Розглянемо деякі властивості опуклих та увігнутих функцій.

Терема 1. Нехай – опукла функція, задана на замкнутій опуклій множині X  Rⁿ; тоді довільний локальний мінімум на Х є також і глобальним.

Наслідок 1. Якщо глобальний мінімум досягається в двох різних точках, то він досягається і в довільній точці відрізка, що з’єднує ці точки.

Наслідок 2. Якщо – строго опукла функція, то її глобальний мінімум на опуклій множині Х досягається в єдиній точці.

Теорема 2. Нехай – опукла функція, задана на опуклій множині X, і, крім того, вона неперервна разом зі своїми частковими похідними першого порядку у всіх внутрішніх точках Х. Нехай – точка, в якій . Тоді в точці досягається локальний мінімум, що співпадає з глобальним мінімумом.

Теорема Куна-Таккера. Теорема Куна-Таккера займає центральне місце в теорії нелінійного програмування.

Нехай задана задача нелінійного програмування: знайти максимальне значення Z = f(x_j) при обмеженнях

, (2.1.9)

. (2.1.10)

Складемо функцію Лагранжа для даної задачі

. (2.1.11)

Якщо виконується умова регулярності (існує хоча б одна точка , для якої для всіх і), то має місце теорема:

Вектор тоді й тільки тоді є оптимальним розв’язком задачі (6.9), коли існує такий вектор , що при   0 і   0 для всіх   0 і   0

. (2.1.12)

Точка ( , ) називається сідловою точкою для F(X,), а теорема – теоремою Куна-Таккера або теоремою про сідлову точку.