• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2019/2020

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

Статус: Дисциплина общефакультетского пула
Когда читается: 1, 2 модуль
Язык: русский
Кредиты: 6

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

Аннотация

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

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

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

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

  • Осваивает и понимает многообразие связей и приложений линейного программирования
Содержание учебной дисциплины

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

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

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

  • неблокирующий решение 3х листков с задачами
  • неблокирующий Двухчасовая контрольная работа из 5 задач
Промежуточная аттестация

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

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

Список литературы

Рекомендуемая основная литература

  • Лунгу К.Н. - Линейное программирование. Руководство к решению задач - Издательство "Физматлит" - 2009 - 132с. - ISBN: 978-5-9221-1029-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2253

Рекомендуемая дополнительная литература

  • Трухан А.А., Ковтуненко В.Г. - Линейная алгебра и линейное программирование: учебное пособие - Издательство "Лань" - 2018 - 316с. - ISBN: 978-5-8114-2744-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/99214