Нелинейное программирование. Задача с ограничениями-неравенствами
Выбери формат для чтения
Загружаем конспект в формате docx
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Лекция. Нелинейное программирование. Задача с ограничениями-неравенствами
Постановка задачи:
(1)
Геометрическая интерпретация
Решается задача
(1)
(2)
Будем использовать алгоритм Франка-Вулфа
Структура алгоритма Франка-Вулфа
Начальный этап
Задать
Задать – начальное приближение
Вычислить градиент:
Шаг1. Составить вспомогательную функцию:
Решить задачу ЛП:
(3)
-решение задачи (3).
Шаг 2. Искать приближение
к решению задачи (1),(2) в виде:
(4)
гдеесть решение задачи:
(если получим , то полагаем )
вычисляем
вычисляем
Шаг3.
Проверяем выполнение критерия останова.
Если критерий останова выполняется, то полагаем
Решение найдено.
Иначе, полагаем , переходим к шагу 1.
Задача 1
(1)
(2)
- точное решение (1),(2).
(3)
Метод Франка-Вулфа
Начальный этап.
Выбираем - начальное приближение
Вычислить градиент:
Шаг 1.
Составить вспомогательную функцию:
Решить задачу линейного программирования:
(4)
где D задано в виде (2).
Решаем задачу (4),(2) геометрически.
Решением задачи (4),(2) является точка
Шаг 2. Ищем приближение задачи (1),(2):
(5)
гдеесть решение задачи:
(6)
Решаем задачу (6).
полагаем
Следовательно:
что соответствует точке А на множестве D.
Шаг 3. Составить вспомогательную функцию:
Решить задачу линейного программирования.
(7)
где D задано в виде (2).
Решаем задачу (7),(2) геометрически.
Решением задачи (7),(2) является точка, что соответствует вершине В на множестве D.
Шаг 4. Ищем приближение задачи (1),(2):
(8)
где есть решение задачи:
(9)
Шаг 5. Составить вспомогательную функцию:
Решить задачу:
(10)
где D задано в виде (2).
т.е. решение улучшить нельзя.
Следовательно: – точка решения задачи (1),(2).
Задача 2.
(1)
(2)
Начальный этап.
Выбираем - начальное приближение;
Шаг 1. Решаем задачу:
(3)
где D задано в виде (2).
точка пересечения
Для этого решаем систему уравнений:
Шаг 2.
Решаем задачу:
(4)
Следовательно:
Шаг 3. Сформируем вспомогательную функцию:
Решаем задачу:
(5)
Шаг 4. Вычисляем:
Вычисление продолжаются до тех пор, пока не выполнится критерий останова алгоритм.
Критерий останова:
(6)
(7)
