13 521
правка
Изменения
→Исследование операций, теория игр
== Исследование операций, теория игр ==
Источники — во-первых, книжка две книжки по тиграм ('''т'''еории '''игр''') А. А. Васин, В. В. Морозов «Теория игр Васина и модели математической экономики»Морозова: # {{Скачать|А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu}}# {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu|главы «Теория принятия решений» книжки «Дополнительные главы теории операций»}} (только 5-я глава).
=== Антагонистические игры. Матричные игры, теорема о минимаксе ===
=== Принцип гарантированного результата. Минимаксные задачи ===
* В базовой книжке Васина и Морозова нетИз книжки 2.
* Можно почитать http://www.intuit.ru/department/algorithms/opres/2/.
* '''Опр.''' оптимальная стратегия (в предположении пессимизма) (так Гермейер стратегии сравнивал); ε-оптимальная стратегия, абсолютно оптимальная стратегия.
=== Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход ===
* Из книжки 2.
* Многокритериальная оптимизация — как выбрать стратегию, если критериев качества несколько?
* Опт. по Парето = «не улучшишь хотя бы один критерий».
* Опт. по Слейтеру = «не улучшишь все критерии разом».
* Лексикографический подход — упорядочиваем их по важности и ORDER BY.
=== Кооперативные игры (''с''-ядро, вектор Шепли) ===
* Игроки делят выручку.
* '''Опр.''' коалиции, хар.функция, супераддитивная, игра, игра с постоянной суммой, вектор дележа, эквив. игры (масштаб-сдвиг), 0-1 редуц. форма игры.
* Индивидуальная разумность — выручку в коалиции не меньше, чем индивидуальная игрока.
* Групповая разумность — выручка любой подкоалиации не меньше, чем её индивидуальная.
* '''Ядро''' (c-ядро) — дележи, удовлетворяющие групповой разумности.
* '''Вектор Шепли''' — состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.
=== Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера) ===
* Из книжки 2.
* Задача 1: максимизируем минимум эффекта по всем пунктам.
* '''Т.''' (пр. ур. Гермейера) оптимальное решение существует и единственно — идея: вначале распределяем ресурсы по наиболее слабым пунктам так, чтобы эффекта им досталось поровну.
* Задача 2: максимизируем сумму эффекта по всем пунктам.
* '''Т.''' (критерий Гросса) аналог уравнивания для производных.
=== Иерархические игры ===
* '''Опр.''' иерархической игры (есть обмен информацией о стратегиях).
* Г<sub>1</sub>: x → y(x) — Y знает стратегию X.
* Г<sub>2</sub>: f(y) → y(f(y)) → x=f(y).
* Г<sub>3</sub>: f<sub>1</sub>(g(x)) → g(x) → x=f(g(x)).
* '''Т.''' (Гермейера). В Г<sub>2</sub> гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.
=== Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача) ===
* В книжках нет.
* Можно почитать [[rupedia:Теорема Форда — Фалкерсона]], [[rupedia:Транспортная задача]], [[rupedia:Алгоритм Дейкстры]].
* '''Опр.''' транспортная сеть, поток, сечение графа, величина сечения.
* '''Т.''' (Ф-Ф, очевидная — «пропускная способность определяется слабым звеном») максимальный поток между истоком и стоком равен величине минимального сечения.
* Решение транспортной задачи [[rupedia:Транспортная задача#Решение с помощью теории графов|аналогично]] Ф-Ф.
* Поиск кратчайшего пути — динамическое программирование, [[rupedia:Алгоритм Дейкстры|алгоритм Дейкстры (жадный)]].
== Оптимальное управление ==
