Математические методы оптимизации задач в исследовании операций

Задача оптимизации состоит из переменных решения $x$, целевой функции $f(x)$ и ограничений:

${\min }_{x}f(x),g_i(x)\le 0,h_j(x)=0$

Метод выбирают по структуре задачи, а не по привычке.

Метод	Когда подходит	Типичный пример
линейное программирование	линейная цель и ограничения, непрерывные переменные	распределение ресурса
целочисленное и смешанное программирование	выбор дискретен	назначение задач, расписание
нелинейная оптимизация	есть нелинейные зависимости	настройка параметров
динамическое программирование	задача раскладывается на перекрывающиеся подзадачи	управление запасом, маршрут
графовые алгоритмы	структура — сеть	кратчайший путь, максимальный поток
стохастическая оптимизация	часть параметров случайна	планирование при неизвестном спросе
робастная оптимизация	важен результат при неблагоприятных параметрах	запас мощности
эвристики и метаэвристики	точный поиск слишком дорог	крупная комбинаторная задача

Симплекс-метод — алгоритм решения линейной задачи, а не отдельный класс постановок. Градиентный спуск — семейство алгоритмов для дифференцируемой цели, но он может прийти в локальный минимум.

Перед запуском решателя

1. Проверить единицы измерения и масштабы коэффициентов.
2. Убедиться, что допустимая область не пуста.
3. Отделить жёсткие ограничения от штрафов.
4. Оценить, обязано ли решение быть целочисленным.
5. Задать базовый вариант для сравнения.
6. Провести анализ чувствительности.

После решения

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

Для графовой постановки см. алгоритм Дейкстры, для нескольких критериев — Оптимизация сложных систем.

Самопроверка

• Когда непрерывное решение нельзя просто округлить?
• Чем ограничение отличается от штрафа?
• Почему локальный минимум может быть приемлемым инженерным результатом?