Page 30 - 4168

Таке визначення опуклості справедливе також і для функ-
цій з декількома змінними (xf ) = f (x 1 , x 2 ,...x n ) . У цьому випа-

дку кожна точка являє собою n-мірний вектор x з координа-
тами x , x ,... x .
n
1
2
Крім вимоги опуклості цільової функції опукле програму-
вання вимагає також, щоб область допустимих розв’язків була
опукла. Область буде опуклою, якщо разом з кожними 2-ма
точками області їй належить і весь відрізок, який їх з’єднує.
Якщо опукла цільова функція задана в опуклій області допус-
тимих розв’язків, то маємо задачу опуклого програмування.
Методів розв’язання нелінійних задач існує багато:
- графічний метод;
- градієнтний метод;
- метод покоординатного спуску;
- метод найшвидшого спуску;
- метод проектування градієнту;
- метод невизначених множників Лагранжа;
- метод Ньютона.
Графічний метод
Графічне розв’язання задачі НП можливе лише за наяв-
ності однієї, двох та трьох змінних. Випадку однієї змінної
задача розв’язується на прямій, для двох – на площині, для
трьох у просторі.

Алгоритм розв’язку задачі графічним методом:
1 Перетворимо нерівності-обмеження у рівності для побудови
графічних кривих.
2 На основі обмежень на площині (для двох змінних), або у
просторі (для трьох змінних) будуємо область допустимих
розв’язків (ОДР).
3 З усієї множини точок нам потрібна лише одна – у якій ці-
льова функція набуває найбільшого (найменшого) значення.
Вибираємо довільну точку ОДР і підставляємо її координа-
ти в цільову функцію. Визначаємо z 0 і будуємо її проекцію
на ОДР.
4 Визначаємо напрям покращення цільової функції у порів-
нянні з z 0. Для цього вибираємо довільну точку ОДР по
один бік від z 0, обчислюємо значення z 1 і порівнюємо з z 0.

30