Линейная оптимизация

Курс посвящен теории и методам решения задач линейной оптимизации. Изучаются математические основы: выпуклые множества и многогранники, теорема об экстремальных точках, двойственность и условия оптимальности. Обсуждаются алгоритмы: симплекс-метод с модификациями (инициализация искусственными переменными, двухфазная схема, двойственный симплекс, анализ вырождения и правило Блэнда для предотвращения циклов), методы внутренней точки. Рассматриваются результаты о полиномиальной разрешимости (метод эллипсоидов Хачияна, метод Кармаркара) и их реализация для разреженных данных.

Изучаются специальные структуры и крупные задачи: сетевые модели, транспортные задачи с алгоритмами (максимальный поток/минимальный разрез), техники препроцессинга и факторизации. Обсуждаются основы декомпозиции (Данциг–Вулф). Практика включает моделирование и эксперименты в программных пакетах (открытых и коммерческих решателях ЛП), сравнение методов и анализ результатов. Требуются знания линейной алгебры и математического анализа; полезны навыки программирования.

Мероприятие проводится при финансовой поддержке Минобрнауки России, грант на создание и развитие МЦМУ «Санкт-Петербургский международный математический институт имени Леонарда Эйлера» соглашение № 075–15–2025–344.