Main menu

Оптимизация на графах: потоки минимальной стоимости в транспортных сетях

Задача о потоке минимальной стоимости (Minimum Cost Flow Problem, MCFP) является объединяющей и фундаментальной проблемой сетевой оптимизации. Она обобщает несколько классических задач теории графов: задачу о кратчайшем пути, задачу о максимальном потоке, транспортную задачу и задачу о назначениях. Цель MCFP заключается в поиске наиболее дешевого способа пересылки заданного объема ресурса через транспортную сеть от источников к стокам, учитывая пропускные способности ребер графа и удельные стоимости транспортировки.

Подробнее

Метод множителей с чередующимися направлениями (ADMM) в распределенной оптимизации

В эпоху больших данных (Big Data) и машинного обучения традиционные методы оптимизации, требующие загрузки всей матрицы данных в оперативную память одного вычислительного узла, перестали справляться с нагрузкой. Метод множителей с чередующимися направлениями (Alternating Direction Method of Multipliers, ADMM) стал алгоритмическим спасением для распределенной выпуклой оптимизации. Он гармонично сочетает в себе способность к декомпозиции, свойственную методу двойственного восхождения, и высокую скорость сходимости метода дополненного лагранжиана, позволяя разбивать гигантские задачи на мелкие фрагменты, решаемые параллельно.

Подробнее

Роевой интеллект: оптимизация роем частиц (PSO) и алгоритм пчелиной колонии

Алгоритмы роевого интеллекта (Swarm Intelligence) представляют собой семейство метаэвристических методов глобальной непрерывной и дискретной оптимизации, вдохновленных коллективным поведением самоорганизующихся биологических систем. В отличие от классического математического программирования, где поиск экстремума опирается на строгую алгебру и градиенты, методы роевого интеллекта используют децентрализованное взаимодействие множества простых агентов. Оптимизация роем частиц (PSO) и алгоритм искусственной пчелиной колонии (ABC) являются флагманами этого подхода, демонстрируя превосходные результаты на мультимодальных и зашумленных ландшафтах.

Подробнее

Многоуровневое математическое программирование: двухуровневые модели и игры Штакельберга

Многоуровневое (в частности, двухуровневое) математическое программирование описывает сложный класс задач оптимизации, в которых целевая функция и ограничения содержат переменные, являющиеся оптимальным решением другой задачи оптимизации. Этот математический аппарат идеально подходит для моделирования иерархических систем принятия решений, где участники обладают асимметричными полномочиями. В экономике и теории игр такие задачи известны как модели Штакельберга, где существует «Лидер», делающий первый ход, и «Ведомый», реагирующий на действия Лидера.

Подробнее

Метод эллипсоидов: полиномиальная сложность в линейном программировании

Метод эллипсоидов, предложенный советским математиком Леонидом Хачияном в 1979 году, стал исторической вехой в математическом программировании. Этот алгоритм впервые строго доказал, что задачи линейного программирования могут быть решены за полиномиальное время. В отличие от классического симплекс-метода, который в худших сценариях (например, на кубе Клее-Минти) требует экспоненциального количества шагов, метод эллипсоидов гарантирует нахождение оптимума с оценкой сложности, зависящей только от размера входных данных, что навсегда изменило теоретический ландшафт теории алгоритмов и вычислительной сложности.

Подробнее

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

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

Подробнее

Метод последовательных приближений в нелинейной оптимизации

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

Подробнее

Задача о размещении объектов: теория и методы

Задача о размещении объектов (Facility Location Problem, FLP) является одной из важнейших задач в логистике и операционном планировании. Требуется выбрать точки на карте для размещения складов или заводов так, чтобы минимизировать суммарные транспортные расходы до клиентов и фиксированные затраты на открытие объектов. Это комбинаторная задача, сочетающая выбор дискретных точек с непрерывной оптимизацией транспортных потоков.

Подробнее

Эволюционные алгоритмы в решении задач оптимизации

Эволюционные алгоритмы (ЕА) — это методы стохастического поиска, имитирующие биологические процессы естественного отбора, кроссовера (скрещивания) и мутации. В задачах оптимизации, где классические градиентные методы терпят неудачу из-за недифференцируемости функции, наличия шума или сложности ландшафта, ЕА показывают поразительную живучесть и способность находить качественные решения.

Подробнее

Метод последовательного квадратичного программирования (SQP)

Метод последовательного квадратичного программирования (SQP) является одним из самых эффективных численных алгоритмов для решения задач нелинейного программирования с ограничениями. Алгоритм основывается на итеративной аппроксимации исходной задачи, где на каждом шаге решается квадратичная подзадача, которая локально моделирует поведение исходной нелинейной задачи.

Подробнее
Subscribe to this RSS feed

Соц. сети