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

Линейное программирование (ЛП) возникло в 40-х годах прошлого века как один из разделов теории оптимизации. Довольно быстро оно стало популярным методом для решения задач экономики и планирования, в которых переменные принимают вещественные значения. В ряде случаев удавалось также приспособить ЛП и для дискретных задач, но систематическое изучение приложений ЛП к комбинаторике началось лишь несколько десятилетий спустя. Одним из пионеров в этой области, несомненно, является Джек Эдмондс, чьи работы по полиэдральной комбинаторике радикально расширили наши познания о связи комбинаторных и линейных задач.

Настоящий курс преследует несколько целей.

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

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

В курсе предполагается дать обзор современных направлений полиэдральной комбинаторики. Мы обсудим понятие субмодулярности и его связи с теорией матроидов. В качестве примера будет разобрана задача о субмодулярном потоке, и на её основе получены многочисленные следствия, как совершенно элементарные (вроде теоремы Форда-Фалкерсона или Дилворта), так и более содержательные (например, теорема Нэша-Вильямса о наличии k-связной направленной ориентации у всякого 2k-связного ненаправленного графа).

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

Страница лекции на сайте Computer Science Club