ПРОГРАММА
Курса лекций «Математические методы и модели исследования операций»
III семестр.
I. Введение. (2/4).
История вопроса, общая характеристика проблематики. Примеры простейших экономических ситуаций, приводящих к задачам математического программирования: задача о рационе, задача экономного раскроя, транспортная задача. Общая схема модёлирования. Задача о контракте.
II. Элементы теории линейного программирования. (6/6).
Различные формы постановки задачи. Двойственная задача, правила ее написания. Лемма о неравенстве значений целевых функций пары двойственных задач. Признак оптимальности (условия дополняющей нежесткости). Геометрическая интерпретация задачи и признака оптимальности в пространстве исходных переменных.
Выпуклые множества. Крайние точки. Выпуклость множества допустимых решений; Признак крайней точки допустимого множества. Теорема о существовании оптимального решения среди крайних точек.
III. Метод последовательного улучшения. (8/8).
Понятия базисного множества и базисного решения. Допустимые и двойственно допустимые базисы. Общая схема метода последовательного улучшения. Конкретизация для прямой и двойственной задачи в канонической несимметричной форме. Получение начального решения: Симплекс-метод и его модификация, связь с общей схемой метола последовательного улучшения. Геометрическая интерпретация. Проблема вырожденности'.
IV. Геометрия двойственности. (6/4).
Геометрические объекты в евклидовом пространстве (луч, конус, коническая и выпуклая оболочки множества, конечнопорожденный конус). Отделимость выпуклых множеств. Лемма Фаркаша. Теорема двойственности для задач линейного программирования. Геометрическая интерпретация прямой и двойственной задачи. Двойственные переменные как объективно обусловленные оценки Ингредиентов.
V. Анализ чувствительности в линейном программировании. (4/4).
Параметрическое линейное программирование. Алгоритм для исследования задачи с параметром в целевой функции. Характер зависимости оптимального значения критерия от параметра. Задачи с параметром в правой части ограничений.
VI. Применение двойственности в теории игр. (4/2)
Матричные игры. Решение игры и седловые точки. Разрешимость игры в смешанных стратегиях (Теорема Неймана). Итеративный метод Брауна-Робинсон. Кооперативная игра, связь с задачей о контракте. Понятие ядра и критерий его непустоты (теорема Бондаревой).
VII. Нелинейное программирование. (8/6).
Общая задача нелинейного программирования. Локальный и глобальный оптимум. Понятие субградиента. Субдифференциал. Связь с задачей линейного программирования с изменяющимися правыми частями. Задача выпуклого программирования. Функция Лагранжа. Сопоставление с классической задачей условной оптимизации. Дифференциальная форма признака оптимальности. Связь оптимальных решений с седловыми точками функции Лагранжа. (Теорема Куна-Таккера).
Литература
1) ёв. Введение в математическое программирование.
2) С. Гасс. Линейное программирование.
3) . Математическое программирование.
4) , . Введение в теорию линейного и выпуклого программирования.
5) . Математическое программирование.
6) . Линейное программирование.
7) . Сборник задач по математическому программированию.
8) . Сборник задач по линейному программированию.
9) Дж. Данциг. Линейное программирование, его обобщения и применения.
10) . Экономический расчет наилучшего использования ресурсов.
