Методы оптимизации: семинар 10

ФКН НИУ ВШЭ

2022-2023

Маминов А.Д.

Условная оптимизация: вычислительные методы

Условный экстремум: постановка задачи

3

Общая стратегия поиска

• Методы последовательной безусловной минимизации
• Метод штрафов
• Метод барьеров
• Метод множителей
• Метод точных штрафных функций
• Методы возможных направлений
• Метод проекции градиентов
• Метод Зойтендейка

4

Метод штрафов

5

Метод штрафов

6

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

7

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

8

Метод проекции градиентов (равенства)

9

Метод проекции градиентов (равенства)

10

Линейное программирование

Линейное программирование

• Задача линейного программирования – частный случай задачи оптимизации с ограничениями.
• Ограничения – только линейные.
• Могут быть и равенства, и неравенства.
• Цель – найти точку, которая минимизирует целевую функцию и удовлетворяет всем ограничениям.
• Целевая функция также линейная.
• Будем называть точку допустимой, если она удовлетворяет всем ограничениям.

Линейное программирование

Пример задачи ЛП

Пример задачи ЛП

Пример задачи ЛП

Стратегия решения

• Кажется, что допустимых точек может быть слишком много, чтобы перебрать их за разумное время.
• Однако можно перебрать лишь конечное число из них.

Метод Данцига (симплекс-метод)

(1)

Метод Данцига (симплекс-метод)

Метод Данцига (симплекс-метод)

(2)

Метод Данцига (симплекс-метод)

(3)

Метод Данцига (симплекс-метод)

(т.1)

Метод Данцига (симплекс-метод)

Метод Данцига (симплекс-метод)

Метод Данцига (симплекс-метод) (резюме)

• Алгоритм решения канонической задачи:
• 1. Начальное базисное решение:
• Записать исходную каноническую задачу в форме (1),(2) или (3).
• Выделить базисные переменные, входящие только в одно уравнение системы (2) или (3) с коэффициентом 1, а в другие – с коэффициентом 0; выделить свободные переменные (все, кроме базисных).
• Найти начальное базисное решение, полагая свободные переменные равными нулю.
• 2. Заполнить таблицу (1).
• 3. Вычислить относительные оценки и записать их в таблицу.�// РЕМАРКА: Для базисных переменных оценки равны нулю.

Метод Данцига (симплекс-метод) (резюме)

Метод Данцига (симплекс-метод) (резюме)

Метод Данцига (симплекс-метод) (резюме)

Решение основной задачи

(4)

Решение основной задачи

(4’)