§4. Нелінійне програмування Градієнт функції

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

або .

Довжина (норма, модуль) градієнта дорівнює .

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

Рис.16

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

Якщо функція диференційована в точці , тоді градієнтом функції в точці називається n-вимірний вектор з координатами

Всі властивості градієнта зберігаються і в n-вимірному просторі.

Вектор (- ) називають антиградієнтом. Він вказує напрям найшвидшого спадання функції.

Опуклі множини та функції

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

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

Функція визначена на опуклій множині G, називається опуклою (див. рис. 17), якщо для будь-яких точок та і справедлива нерівність

. (4.1)

Якщо

, (4.2)

То функція називається угнутою (див. рис. 18).

Якщо в співвідношеннях (4.1), (4.2) для мають місце строгі нерівності, тоді функція називається строго опуклою (строго угнутою). Геометрична інтерпретація для двовимірного простору така:

Рис.17	Рис.18

Невід’ємна лінійна комбінація опуклих на деякій опуклій множині G функцій, тобто функція теж буде опуклою.

Властивості опуклих функцій

1. Якщо - опукла функція при усіх , тоді опуклою буде й множина розв’язків системи .

Аналогічна властивість має місце і для угнутих функцій.

Зауваження. Множина розв’язків системи нерівностей

(4.3)

або (4.4)

опукла, якщо в нерівностях (4.3) - опуклі функції, а в нерівностях (4.4) - угнуті функції.

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

3. Локальний мінімум опуклої функції , яка визначена на опуклій множині G, збігається з її глобальним мінімумом на цій множині.

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

Задача математичного програмування

в якій цільова функція (4.5), або обмеження (4.6), або те і інше нелінійні, називається нелінійною.

Задачі нелінійного програмування з двома змінними можна, як і у випадку лінійного програмування, розв’язувати графічно, а саме: вважаючи , ми отримуємо рівняння сім’ї ліній рівня функції f; кожному фіксованому значенню параметра С відповідає певна лінія сім’ї.

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

Приклад. В області D, яка визначається системою нерівностей

визначити точку , в якій функція приймає:

а) найменше значення; б) найбільше значення, якщо:

1) ;

2)

Розв’язання.

П

Рис.19

обудуємо область D (рис.19). Це буде множина точок, які належать трикутнику АВС [7].

1.а)

Сім’єю ліній рівня функції f буде сім’я концентричних кіл

із загальним центром в точці Е(8,1).

Лінія рівня, для якої буде дотикатися в точці F границі АС області D.

Обчислимо координати точки F дотику, для чого складемо рівняння прямої EF, перпендикулярної до АС.

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

В нашому випадку, рівняння EF має вигляд

або .

Далі обчислимо координати точки F, як точки перетину прямих АС та EF

Таким чином, розв’язок задачі 1.а) такий:

, .

1.б)

Точка перетину області D з лінією рівня функції f, яка відповідає , міститься у вершині В області D і має координати

Таким чином, розв’язок задачі (б) має вигляд:

, .

2.а)

В цьому випадку центр ліній рівня функції розташований всередині області D- це точка К(7,6). Очевидно, що найменше значення функції , яке дорівнює нулю, вона має в точці К, тобто

, .

2.б)

Найбільшого значення функція f досягає в точці А на межі області D. Знайдемо координати точки А:

Таким чином, розв’язок задачі 2б має вигляд:

, .

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