Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Линейное программирование
Весна 2011, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

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

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

Видео лекций: https://www.lektorium.tv/course/22810?id=22810

Дата и время Название Место Материалы
16 апреля
17:20–18:55
Лекция 1, лекция ПОМИ РАН видеофайлы
16 апреля
19:05–20:40
Лекция 2, лекция ПОМИ РАН видеофайлы
17 апреля
11:15–12:50
Лекция 3, лекция ПОМИ РАН видео
17 апреля
13:00–17:35
Лекция 4, лекция ПОМИ РАН видеофайлы
17 апреля
15:35–17:10
Лекция 5, лекция ПОМИ РАН видеофайлы
23 апреля
17:20–18:55
Лекция 6, лекция ПОМИ РАН видеофайлы
23 апреля
19:15–20:50
Лекция 7, лекция ПОМИ РАН видеофайлы
24 апреля
11:15–12:50
Лекция 8, лекция ПОМИ РАН видеофайлы
24 апреля
13:00–14:35
Лекция 9, лекция ПОМИ РАН видеофайлы
24 апреля
15:35–17:10
Лекция 10, лекция ПОМИ РАН видеофайлы