Градиентные методы решения ЗНЛП

Различают два класса данных методов: барьерные и штрафные.
Барьерные - запрещено выходить

Метод Франка-Вульфа (барьерный метод)

(1)

(2)

(4)

(3)

ЗЛП: (4)

Пусть точка

– решение ЗЛП:

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

Пример:

(1)

(2)

(3)

Решение. Найдем градиент функции:

и в качестве исходного допустимого решения задачи

(4)

ЗЛП:

Следующая итерация:

Метод штрафных функций

Вводим новую функцию:

H – штрафная функция:

В методе Эрроу-Гурвица:

Метод наискорейшего спуска

- если на max

- если на min

- (max)

-

(на границе).

, тогда

Если ОДЗ линейна:

Метод кусочно-линейной аппроксимации

Функция

называется сепарабельной, если она может быть

параметрическое
уравнение отрезка

Пример:

Решение: