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

2020/2021

Статус: Дисциплина общефакультетского пула

Кто читает: Факультет математики

Где читается: Факультет математики

Когда читается: 3, 4 модуль

Преподаватели: Колесников Александр Викторович

Язык: русский

Кредиты: 6

Контактные часы: 72

Полная версия программы учебной дисциплины

Аннотация

Линейное программирование — раздел теории оптимизации, изучающих специальный класс задач — нахождение экстремумов линейных функций на выпуклых множествах (как конечномерных, так и бесконечномерных). Линейное программирование зародилось как прикладная дисциплина, с приложениями (в первую очередь) к экономике, но оно имеет глубокие связи со многими задачами анализа, геометрии, дискретной математики, а также численными методами и алгоритмами. ПРЕДВАРИТЕЛЬНАЯ ПОДГОТОВКА: математический анализ и линейная алгебра в объёме первого курса.

Цель освоения дисциплины

Настоящий курс представляет собой введение в линейное программирование и ставит своей целью осветить многообразие связей и приложений линейного программирования.

Планируемые результаты обучения

Осваивает и понимает многообразие связей и приложений линейного программирования

Содержание учебной дисциплины

Линейное программирование.
Постановка задачи и базовые свойства. Классические задачи линейного программирования (задача о диете, транспортная задача и др.).
Элементы теории выпуклых многогранников.
Метод исключения Фурье-Моцкина. Основная теорема о многогранниках.
Элементы выпуклого анализа.
Лемма Фаркаша, теорема Хелли, теорема Каратеодори, теорема об отделимости
Двойственность в линейном программировании.
Крайние точки выпуклых множеств.
Теорема Бирхгофа о бистохастических матрицах.
Теорема о минимаксе
Другие приложения минимакса.
Двудольные графы (теоремы Кёнига, Холла). Игры с нулевой суммой.
Симплекс-метод
Другие алгоритмы
Обзор других алгоритмов линейного программирования
Транспортные потоки в сетях.
Теорема Форда–Фалькерсона
Целочисленное линейное программирование.
Общая теорема о минимаксе (в бесконечномерных пространствах)
Непрерывная транспортная задача.
Метрика Канторовича–Рубинштейна

Элементы контроля

решение 3х листков с задачами
Двухчасовая контрольная работа из 5 задач

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.4 * Двухчасовая контрольная работа из 5 задач + 0.6 * решение 3х листков с задачами

Программа дисциплины