Линейное программирование
Курс Хит![](https://www.lektorium.tv/sites/lektorium.tv/files/courses/1304797447_22810_Lineynoe_programmirovanie_10_metadata.flv_snapshot_08.38_%5B2011.05.07_23.43.18%5D.jpg)
Линейное программирование (ЛП) возникло в 40-х годах прошлого века как один из разделов теории оптимизации. Довольно быстро оно стало популярным методом для решения задач экономики и планирования, в которых переменные принимают вещественные значения. В ряде случаев удавалось также приспособить ЛП и для дискретных задач, но систематическое изучение приложений ЛП к комбинаторике началось лишь несколько десятилетий спустя. Одним из пионеров в этой области, несомненно, является Джек Эдмондс, чьи работы по полиэдральной комбинаторике радикально расширили наши познания о связи комбинаторных и линейных задач.
Настоящий курс преследует несколько целей.
Во-первых, мы познакомимся с основными понятиями ЛП, изучим теоремы отделимости, линейной двойственности и обсудим полиномиальную разрешимость задачи ЛП с помощью метода эллипсоидов.
Во-вторых, с самого начала большое внимание будет уделяться связи ЛП с теорией целочисленного программирования, комбинаторикой и оптимизацией. Мы рассмотрим понятия тотальной унимодулярности и тотальной двойственной целочисленности линейных программ, а также выясним, как записывать подобные "хорошие" программы для большого количества комбинаторных задач.
В курсе предполагается дать обзор современных направлений полиэдральной комбинаторики. Мы обсудим понятие субмодулярности и его связи с теорией матроидов. В качестве примера будет разобрана задача о субмодулярном потоке, и на её основе получены многочисленные следствия, как совершенно элементарные (вроде теоремы Форда-Фалкерсона или Дилворта), так и более содержательные (например, теорема Нэша-Вильямса о наличии k-связной направленной ориентации у всякого 2k-связного ненаправленного графа).
Наконец, будут кратко изложены основные элементы полуопределенного программирования (SDP) и его приложений к приближенным алгоритмам (например, задаче о максимальном разрезе).
Страница лекции на сайте Computer Science Club