Авторы: В.И. Бахтин, А.П. Ковалёнок, А.В. Лебедев, Ю.В. Лысенко.
Минск: БГУ, 2003 - 199 с.
В лекциях излагаются два раздела методов исследования операций: теория решения экстремальных задач на графах и теория некооперативных игр.
Адресуется студентам и аспирантам математических специальностей университета. Книга будет также полезна преподавателям и всем интересующимся системным анализом.Содержание.
Экстремальные задачи на графах.
Элементарные понятия, связанные с неориентированными графами.
Эйлеровы графы.
Деревья и их свойства.
Задача о построении остовного дерева минимального веса.
Элементарные понятия, связанные с ориентированными графами.
Задача о построении кратчайшего пути между двумя заданными вершинами. Алгоритм Дийкстры.
Задача о построении кратчайших путей между всеми парами вершин. Алгоритм Флойда.
Задача об "узких местах".
Задача коммивояжёра. Метод ветвей и границ. Алгоритм Литтла.
Сети. Потоки. Разрезы.
Потоки максимальной мощности и теорема Форда-Фалкерсона.
Построение максимальных потоков. Алгоритм Форда-Фалкерсона.
Задачи, сводящиеся к алгоритму Форда-Фалкерсона.
Потоки минимальной стоимости.
Алгоритм Басакера-Гоуэна.
Алгоритм Клейна.
Метод управления проектами. Сетевое планирование.
Литература к главе 1.
Введение.
Безкоалиционные (некооперативные) игры. Предпочтения и функции выигрыша.
Правила принятия решений. Согласованные стратегии. Теоремы о неподвижной точке.
Отношения предпочтения и оптимумы на множестве стратегий и исходов.
Игра двух лиц с нулевой суммой. Цена, несущественность, седловая точка.
Теорема фон Ноймана о минимаксе.
Теорема Нэша.
Матричные и биматричные игры.
Смешанные расширения конечных игр.
Смешанные расширения бесконечных игр.
Поиск равновесий в матричных играх.
Поиск равновесий по Нэшу в биматричных играх.
Игры в развёрнутой форме. Алгоритм Куна.
Литература к главе 2.
Предметный указатель.
