6 семестр

1.       

 Название дисциплины

Информационные технологии.
Основы линейного программирования

2.       

 Курс обучения, специальность

3,

1-31 03 09 Компьютерная математика и системный анализ

3.       

 Семестр обучения

6

4.       

 Количество кредитов

2

5.       

 Ф.И.О. лектора

Доцент Лаврова Ольга Анатольевна, к.ф.-м.н.

6.       

 Цели изучения дисциплины

Формирование теоретических знаний и практических навыков решения задач выпуклого и линейного программирования.

В результате изучения студент должен уметь

—         строить экстремальные задачи на выпуклых множествах конечномерного пространства при наличии ограничений в виде равенств и неравенств;

—         решать задачи линейного и выпуклого программирования с применением полиномиальных методов.

7.       

 Пререквизиты

Математический анализ. Алгебра и теория чисел. Геометрия. Компьютерная математика. Методы оптимизации. Численные методы

8.       

 Содержание дисциплины

1.  Геометрия задач линейного программирования.   Теорема о декомпозиции полиэдра. Связь внутреннего представления полиэдра с задачей линейного программирования. Характеристический конус. Политоп. Пространство линейности. Грань. Фасета. Минимальная грань. Вершина. Экстремальный луч. Экстремальная точка. Геометрическое описание симплекс-алгоритма.

2.  Полиномиальные методы решения задач выпуклого программирования.  Метод эллипсоидов. Алгоритм двоичного поиска для последовательности задач о разрешимости. Алгоритмическое представление выпуклого тела. Теоретическая сложность метода эллипсоидов. Метод внутренней точки. Внутреннее скалярное произведение. Конкордантная функция в качестве функции-барьера. Функция-барьер для полиэдрических множеств. Теоретическая сложность метода внутренней точки.

9.       

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

1.  Материалы к курсу «Einfürung in die Mathematische Optimierung», проф. Кайбель, Магдебургский университет, Германия 2013/14: видео-лекции на немецком языке, слайды к лекциям, практические задания.

2.  Р. Рокафеллар, Выпуклый анализ: Пер. с англ. – М.: Мир, 1973.

3.  A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006.

4.  A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.

5.  А. Схрейвер, Теория линейного и целочисленного программирования: в 2-х т.: Пер. с англ. – М.: Мир, 1991.

6.  J. Matousek, B. Gärtner, Using and Understanding Linear Programming, Springer, 2006.

7.  V. Chvatal, Linear Programming, Freeman, 1983.

8.  M. Grötschel, L. Lovàsz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988

10.   

 Методы преподавания

Лекции, практические занятия

11.   

 Язык обучения

Русский, немецкий

12.   

 Условия (требования),  текущий контроль

Контрольные работы.

Зачет по дисциплине проходит в устной форме

13.   

Формат текущей аттестации

Зачет