ЧАСТЬ 3. ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Составители: д.ф.-м.н., профессор Петросян Л.А., к.ф.-м.н., доцент Зенкевич Н.А.

Учебная литература.

1.Петросян Л.А.,Зенкевич Н.А. Теория игр. - М.: изд-ва ВШ и "Книжный дом "Университет", 1998.- 300 с.

2.Таха Х. Введение в исследование операций.Т.1,2. - М.: Мир, 1985. - 560 с.

3.Вагнер Г. Основы исследования операций.Т.1-3. - М.: Мир, 1972-1973. - 632 с.

4.Форд Л.,Фалкерсон Д. Потоки в сетях.- М.: Мир, 1966. - 230 с.

5.Гейл Д. Теория линейных экономических моделей.- М.: Мир, 1969.- 342 с.

6.Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1972. - 410 с.

7.Тироль Ж. Теория организации промышленности.Т.1,2.(Перевод с англ. под ред. Гальперина А.С. и Зенкевича Н.А.) - СПб:
изд-во "Экономическая школа", 2000.- 876 с.

8.Харшаньи Дж.,Зельтен Р. Общая теория выбора равновесия в играх.(Перевод с англ. под ред. Зенкевича Н.А.) - СПб: изд-во
"Экономическая школа", 2001.- 415 с.

9.Петросян Л.А.,Гарнаев А.Ю. Игры поиска. - СПб: изд-во СПбГУ, 1992. - 216 с.

10.Петросян Л.А.,Кузютин Д.В. Игры в развёрнутой форме. - СПб: изд-во СПбГУ, 2001. - 218 с.

Глава 1. Линейное программирование.

1.1. Постановка задач линейного программирования(ЗЛП).
1.2. Основные математические предположения,формализация задачи.
1.3. Различные формы записи ЗЛП.Эквивалентные формулировки.
1.4. Допустимые и оптимальные решения.
1.5. Понятие базисного решения.Лемма.
1.6. Нахождение базисного решения.Симплексная таблица.
1.7. Допустимое базисное решение.Теорема о существовании.
1.8. Алгоритм прямого симплекс-метода.
1.9. Начальное базисное решение.Двухразовый симплекс-метод.
1.10. Прямая и двойственная задачи линейного программирования.
1.11. Двойственный симплекс-метод.
1.12. Теорема двойственности.
1.13. Теорема равновесия.

Глава 2.Матричные игры

2.1. Понятие матричной игры.
2.2. Понятие равновесия и седловой точки.
2.3. Решение в чистых стратегиях.
2.4. Смешанное расширение матричной игры.
2.5. Свойства ситуации равновесия.
2.6. Теорема о доминировании в матричных играх.
2.7. Графоаналитический метод решения матричных игр.
2.8. Метод Брауна-Робинсона.
2.9. Основная теорема матричных игр.
2.10. Алгоритм нахождения оптимальных стратегий.

Глава 3.Целочисленное программирование

3.1. Потоки в сетях.
3.2. Теорема о максимальном потоке.Алгоритм нахождения максимального потока и минимального сечения в сети.
3.3. Формулировка транспортной задачи(Т-задача).Способы задания Т-задачи.Разрешимость.
3.4. Условие баланса.
3.5. Нахождение начального опорного плана.Приближённый метод Фогеля.
3.6. Алгоритм метода потенциалов и его обоснование.
3.7. Простая задача о назначениях.
3.8. Задача об оптимальных назначениях.
3.9. Метод ветвей и границ.Алгоритм.
3.10. Решение задачи коммивояжёра.

Глава 4. Нелинейное программирование.

4.1. Постановка задачи нелинейного программирования.Примеры.
4.2. Множество возможных направлений.Свойства.
4.3. Свойства оптимальных решений.Активные ограничения.Условие регулярности.
4.4. Лемма Фаркаша.Теорема Куна-Таккера(необходимость).
4.5. Условия Куна-Таккера для ограничений типа равенств и смешанных ограничений.
4.6. Достаточность условий Куна-Таккера для вогнутых функций.
4.7. Метод возможных направлений(метод линеаризации для задачи с линейными ограничениями).
4.8. Оптимальный портфель ценных бумаг.
5.1. Динамическое программирование.Примеры решения задач.
5.2. Уравнение Беллмана для детерминированного многошагового процесса принятия решений.
5.3. Решение задачи дискретного оптимального быстродействия.
5.4. Непрерывная задача быстродействия.
5.5. Динамическое программирование и принцип максимума Понтрягина.
5.6. Пример на принцип максимума.

Глава 6.Неантагонистические игры.

6.1.Примеры неантагонистических игр в нормальной форме.
6.2. Равновесие по Нэшу, оптимальность по Парето.
6.3. Смешанное расширение игры многих лиц.
6.4. Существование равновесия в смешанных стратегиях для биматричной игры.
6.5. Игры в форме характеристической функции.Доминирование дележей.
6.6. Ядро кооперативной игры.Вектор Шепли.
6.7. Примеры построения характеристических функций и ядра.
6.8. Игра в развёрнутой форме и примеры.
6.9. Существование абсолютного равновесия по Нэшу в игре с полной информацией.
6.10. Равновесие по Нэшу в стратегиях наказания.Основная теорема.Примеры.