Когда целевая функция имеет сложный, мультимодальный ландшафт с множеством локальных минимумов, градиентные методы оказываются бесполезными. В таких случаях на помощь приходят методы глобальной оптимизации, основанные на случайном поиске. Они не гарантируют нахождение глобального минимума за конечное время, но обладают высокой вероятностью попадания в "бассейн притяжения" глобального оптимума.
Метод последовательных приближений охватывает широкий класс итерационных алгоритмов, в которых решение задачи находится как предел последовательности, сходящейся к оптимальному значению. К ним относятся методы простой итерации, методы Ньютона, градиентные методы. Основная задача — обеспечить сходимость алгоритма и оценить скорость достижения заданной точности.
Задача о размещении объектов (Facility Location Problem, FLP) является одной из важнейших задач в логистике и операционном планировании. Требуется выбрать точки на карте для размещения складов или заводов так, чтобы минимизировать суммарные транспортные расходы до клиентов и фиксированные затраты на открытие объектов. Это комбинаторная задача, сочетающая выбор дискретных точек с непрерывной оптимизацией транспортных потоков.
Эволюционные алгоритмы (ЕА) — это методы стохастического поиска, имитирующие биологические процессы естественного отбора, кроссовера (скрещивания) и мутации. В задачах оптимизации, где классические градиентные методы терпят неудачу из-за недифференцируемости функции, наличия шума или сложности ландшафта, ЕА показывают поразительную живучесть и способность находить качественные решения.
Метод последовательного квадратичного программирования (SQP) является одним из самых эффективных численных алгоритмов для решения задач нелинейного программирования с ограничениями. Алгоритм основывается на итеративной аппроксимации исходной задачи, где на каждом шаге решается квадратичная подзадача, которая локально моделирует поведение исходной нелинейной задачи.
Задача о раскрое (Cutting Stock Problem) является классической производственной задачей, цель которой — нарезать заготовки заданных размеров из исходных листов или рулонов так, чтобы минимизировать суммарные отходы. Это задача целочисленного линейного программирования с потенциально огромным числом вариантов раскроя, что требует использования специальных методов генерации столбцов.
Имитация отжига (Simulated Annealing) — это метаэвристический алгоритм оптимизации, вдохновленный процессом медленного охлаждения металлов для достижения их кристаллической структуры с минимальной энергией. В математическом программировании метод используется для поиска глобального минимума сложных функций, где локальные методы (градиентный спуск) неизбежно застревают в локальных ловушках.
Метод множителей Лагранжа — это мощный математический метод нахождения локальных экстремумов функции при наличии ограничений в форме равенств. Метод трансформирует задачу поиска максимума или минимума функции $f(x)$ при условиях $g(x) = 0$ в поиск безусловного экстремума функции Лагранжа $L(x, lambda) = f(x) - lambda cdot g(x)$. Эта концепция стала фундаментом для теории двойственности и алгоритмов нелинейного программирования.
В реальных бизнес-задачах редко существует только один критерий оптимальности. Чаще всего приходится балансировать между противоречивыми целями: минимизацией затрат и максимизацией качества, или снижением времени выполнения и увеличением надежности. Теория мультиобъектной оптимизации занимается поиском не одного решения, а множества компромиссных вариантов, называемых множеством Парето.
Метод отсекающих плоскостей Ральфа Гомори стал прорывом в решении задач целочисленного линейного программирования в конце 50-х годов XX века. В отличие от метода ветвей и границ, который разделяет задачу на подзадачи, метод Гомори итеративно добавляет новые линейные ограничения (отсечения), которые "отрезают" нецелочисленные вершины области допустимых решений, не исключая при этом целочисленные точки.
