Линейное программирование

Описание

На курсе слушатели познакомятся с основными понятиями линейного программирования (ЛП), изучат теоремы отделимости, линейной двойственности и обсудят полиномиальную разрешимость задачи ЛП с помощью метода эллипсоидов.

Большое внимание будет уделено связи ЛП с теорией целочисленного программирования, комбинаторикой и оптимизацией. Максим Бабенко расскажет о понятиях тотальной унимодулярности и тотальной двойственной целочисленности линейных программ, а также о том, как записывать подобные «хорошие» программы для большого количества комбинаторных задач.

В ходе курса предполагается дать обзор современных направлений полиэдральной комбинаторики. Будут кратко изложены основные элементы полуопределенного программирования (SDP) и его приложений к приближенным алгоритмам (например, задаче о максимальном разрезе).