Метод отсекающих плоскостей Ральфа Гомори стал прорывом в решении задач целочисленного линейного программирования в конце 50-х годов XX века. В отличие от метода ветвей и границ, который разделяет задачу на подзадачи, метод Гомори итеративно добавляет новые линейные ограничения (отсечения), которые "отрезают" нецелочисленные вершины области допустимых решений, не исключая при этом целочисленные точки.
Транспортная задача — это классическая модель линейного программирования, направленная на оптимизацию перевозки однородного груза из пунктов производства в пункты потребления с минимальными затратами. Несмотря на свою простоту, задача является фундаментальным инструментом для управления цепочками поставок и планирования работы распределительных систем, обеспечивая оптимальное использование имеющихся транспортных мощностей.
Задача о максимальном потоке (Maximum Flow Problem) является одной из важнейших задач в теории сетевых потоков. Дана транспортная сеть, где для каждого ребра установлена пропускная способность. Задача заключается в определении такого потока из источника в сток, чтобы суммарный объем переданного ресурса был максимальным, не нарушая при этом ограничений пропускной способности.
Задача о нахождении минимального остовного дерева (Minimum Spanning Tree, MST) является фундаментальной задачей теории графов с огромным количеством прикладных приложений. Остовным деревом связного неориентированного графа называется подграф, включающий все вершины графа и образующий дерево. Минимальное остовное дерево — это то, для которого сумма весов ребер минимальна.
Метод декомпозиции Бендерса является одним из наиболее мощных алгоритмов для решения задач математического программирования с большой размерностью и особой блочной структурой. Суть метода заключается в разделении сложной задачи на две иерархические составляющие: главную задачу, определяющую переменные первого уровня, и подчиненную задачу, решающую вопросы распределения ресурсов при зафиксированных значениях первого уровня.
В современном менеджменте принятие решений редко происходит в условиях полной определенности. Большинство задач управления, таких как планирование инвестиционного портфеля или логистическая маршрутизация, требуют учета стохастических факторов. Сценарный подход к стохастической оптимизации позволяет трансформировать непредсказуемость внешней среды в структурированный набор альтернатив, обеспечивая принятие робастных решений.
Дробно-линейное программирование — это задача оптимизации, где целевая функция представляет собой отношение двух линейных функций, а ограничения остаются линейными. Подобные задачи часто возникают в экономике, когда необходимо максимизировать эффективность (например, отношение прибыли к затратам) при линейных ресурсных ограничениях. Несмотря на нелинейный вид функции, задача может быть сведена к линейному программированию.
Выпуклое программирование — это наиболее изученный и важный класс задач нелинейного программирования. Основная особенность состоит в том, что целевая функция является выпуклой, а допустимое множество — выпуклым множеством. Для таких задач любое локальное оптимальное решение является также глобальным, что позволяет использовать эффективные методы поиска экстремума с гарантией достижения оптимального результата.
Методы штрафных и барьерных функций предназначены для сведения задач оптимизации с ограничениями к последовательности задач безусловной оптимизации. Идея заключается в добавлении к целевой функции штрафа за нарушение ограничений или барьера, предотвращающего выход за допустимую область. Это позволяет использовать стандартные алгоритмы поиска экстремума для решения широкого круга инженерных и экономических задач.
Геометрическое программирование — это специальный класс задач нелинейного программирования, имеющий дело с оптимизацией целевых функций и ограничений, представимых в виде многочленов или мономов. Хотя название может вводить в заблуждение, метод напрямую связан с геометрическими неравенствами, такими как неравенство о средних. Геометрическое программирование эффективно для инженерного проектирования, где параметры моделей часто связаны степенными зависимостями.