Теория управления
Общий курс
Составитель: к. ф.-м. н. Е.А. Губар
Тема 1. Линейное программирование
- Постановка задачи линейного программирования. Примеры линейных задач оптимизации.
- Основные математические предположения, формализация задачи. Теоремы об альтернативе.
- Стандартная задача линейного программирования. Экономическая интерпретация.
- Прямая и двойственная задачи линейного программирования.
- Допустимые и оптимальные решения.
- Критерий оптимальности.
- Базисные решения системы линейных уравнений.
- Существование неотрицательных базисных решений системы линейных уравнений.
- Геометрическая интерпретация базисного решения.
- Теорема двойственности.
- Каноническая теорема равновесия.
- Существование неотрицательного базисного решения.
- Задача линейного программирования в канонической форме. Эквивалентность стандартной и канонической задачи.
- Симплексный метод решения задачи линейного программирования. Интерпретация.
- Обоснование симплекс-метода.
- Нахождение базисного решения. Симплексная таблица.
- Алгоритм прямого симплекс-метода.
- Двухфазовый симплекс-метод.
- Двойственный симплекс-метод.
Тема 2. Матричные игры
- Определение матричной игры. Минимаксные и максминные стратегии. Ситуация равновесия в чистых стратегиях. Необходимое и достаточное условие существования равновесия в чистых стратегиях. Примеры.
- Смешанные стратегии. Существование ситуации равновесия в смешанных стратегиях. Примеры.
- Свойства оптимальных смешанных стратегий.
- Доминирование. Теоремы о доминировании в матричных играх.
- Методы решения матричных игр. Сведение игры к задаче линейного программирования. Графоаналитический метод решения матричных игр. Метод Брауна-Робинсон.
Тема 3. Неантагонистические игры
- Определение неантагонистической игры. Примеры неантагонистических игр в нормальной форме.
- Равновесие по Нэшу. Примеры.
- Оптимальность по Парето. Примеры.
- Смешанное расширение игры многих лиц. Теорема существования равновесия по Нэшу в смешанных стратегиях в конечных играх.
- Определение игры в развернутой форме.
- Игры с полной информацией. Примеры.
- Существование равновесия по Нэшу в играх с полной информацией.
- Определение абсолютного равновесия. Теорема о существовании абсолютного равновесия
- Равновесие по Нэшу в стратегиях наказания. Построение равновесия в стратегиях наказания. Примеры.
- Примеры игр с неполной информацией.
- Кооперативная теория игр. Игры в форме характеристической функции. Свойства характеристической функции.
- Доминирование дележей.
- Принципы оптимальности в кооперативных играх: С-ядро, НМ-решение, векторы Шепли и Банзафа.
- Построение характеристических функций и вектора Шепли на примере иерархической игры.
Тема 4. Целочисленное программирование
- Потоки в сетях.
- Теорема о максимальном потоке. Алгоритм нахождения максимального потока и минимального сечения в сети.
- Формулировка транспортной задачи. Способы задания транспортной задачи. Разрешимость.
- Условие баланса.
- Нахождение начального опорного плана. Метод минимального элемента. Приближённый метод Фогеля.
- Алгоритм метода потенциалов и его обоснование.
- Простая задача о назначениях.
- Задача об оптимальных назначениях.
- Метод ветвей и границ. Алгоритм для решения задачи целочисленного программирования.
- Метод ветвей и границ для решения задачи коммивояжёра.
Литература
Основная литература
- Оуэн Г. Теория игр. Пер. с англ. - М.: Вузовская книга, 2004. - 216 с.: ил.
- Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. - М.: изд-ва ВШ и Книжный дом Университет, 1998. - 300 с.
- Н.А. Зенкевич, Е.А. Губар. "Практикум по исследованию операций."
- Таха Х. Введение в исследование операций. Издание 7-ое - М., Вильямс, 2005. - 912 с.
Дополнительная литература
- Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие. Изд-во: Инфра-М, 2003 г.
- Вагнер Г. Основы исследования операций . Т.1-3. - М.: Мир, 1973. - 632 с.
- Васин А.А. Морозов В.В. Теория игр и модели математической экономики (учебное пособие). - М.: МАКС Пресс, 2005г.-272 с.
- Вентцель Е. С. Исследование операций. Задачи, принципы, методология. Учебное пособие для вузов. Изд-во: Дрофа, 2006 г.
- Гейл Д. Теория линейных экономических моделей. - М.: Мир, 1969. - 342 с.
- Данилов Н.Н. Курс математической экономики. Новосибирск. Изд-во СО РАН, 2002 . - 444 с.
- Зайченко Ю. П., Шумилова С. А. Исследование операций. Сборник задач. Киев : Вища школа. Изд-во Киевского ун-та, 1984. - 224 с.
- Кремер Н.Ш., Путко Б.А., Тришин И.М. и др. Исследование операций в экономике. Учебное пособие для вузов. Изд-во: Юнити, 2005 г, 407 стр.
- Кузнецов Б. Т. Математические методы и модели исследования операций. Изд-во: Юнити-Дана, 2005 г.
- Печерский С.Л. Яновская Е.Б. Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европейского ун-та в Санкт-Петербурге, 2004. - 459 с.
- Протасов И. Д. Теория игр и исследование операций. Изд-во: Гелиос АРВ, 2006 г. 368 с.
- Розен В. В. Математические модели принятия решений в экономике. Изд-ва: Университет, Высшая школа, 2002 г., 288 с.
- Романовский И. В. Дискретный анализ. - СПб.: "Невский диалект", 1999. - 254 с.
- Ху Т. Целочисленное программирование и потоки в сетях - М.: Мир, 1974.
- Шикин Е. В. Исследование операций. Учебник. Изд-во: ВЕЛБИ, Проспект, 2006 г, 280 с.
- Ширяев В.И. Исследование операций и численные методы оптимизации - 2 изд. Изд-во: КомКнига, 2006 г, 216