Метод Франка – Вулфа

1. Определить исходное допустимое решение задачи .

2. Найти градиент функции в точке исходного допустимого решения .

3. Построить линейную функцию

и найти оптимальное решение , при котором ее значение максимально при заданных в задаче ограничениях.

4. Составить выражение для нового допустимого решения

и подставить в целевую функцию задачи

5. Определить шаг вычислений как стационарную точку функции из условия . Полученное значение есть шаг вычислений.

6. Вычислить новое допустимое решение

7. Вычислить значение .

8. Проверить выполнение условия

Если оно выполняется, оптимальное решение найдено, если нет, то переходим к шагу 2.

Пример.

Решение.

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

2. В качестве исходного допустимого решения выберем точку , а в качестве критерия оценки качества получаемого решения неравенство , где .

1-я итерация

1. В точке найдем градиент функции , тогда необходимо решить задачу максимизации

при условии

Решаем эту задачу симплекс – методом.

Каноническая задача

Оптимальное решение

2. Составим новое допустимое решение

Подставим в целевую функцию, получим

Тогда новое допустимое решение , значение функции в этой точке .

3. , следовательно, переходим к следующей итерации.

2-ая итерация

1. В точке найдем градиент функции , тогда необходимо решить задачу максимизации

при условии

Решаем эту задачу симплекс – методом.

Каноническая задача

Оптимальное решение

2. Составим новое допустимое решение

Подставим в целевую функцию, получим

Тогда новое допустимое решение , значение функции в этой точке .

3. , следовательно, переходим к следующей итерации.

3-я итерация

1. В точке найдем градиент функции , тогда необходимо решить задачу максимизации

при условии

Решаем эту задачу симплекс – методом.

Каноническая задача

Оптимальное решение

2. Составим новое допустимое решение

Подставим в целевую функцию, получим

Тогда новое допустимое решение , значение функции в этой точке .

3. , следовательно, вычисления закончены. Искомое решение .