2. Классификация задач принятия решений.

• По количеству игроков: парные игры и игры n игроков

• По количеству стратегий: конечные и бесконечные

• По характеру взаимоотношений: бескоалиционные(не имеют права образовывать коалиции), коалиционные, кооперативные(коалиции определены заранее).

• По характеру выигрышей: антагонистические(игры с нулевой суммой - выигрыш партии равен нулю),неантогонистические(игры с ненулевой суммой- выигрыш партии не равен нулю)

• По количеству ходов: одношаговые и многошаговые. Многошаговые делятся на позиционные,стохастические, дифференциальные. Позиционные игры-несколько игроков делают несколько последовательных ходов. Если в игре производятся ходы, приводящие к выбору определенных позиций, причем имеется определенная вероятность возврата на предшествующую позицию, такая игра называется Стохастической. Если в многошаговой игре допускается делать ходы непрерывно и действия игроков описываются дифференциальными уравнениями, такая игра называется дифференциальной

• В зависимости от состояния информации: игры с полной(каждому игроку известно какие выборы сделаны игроками ранее) и неполной информацией(Не все известно).

• По виду функций выигрыша: матричные(конечная игра двух игроков с нулевой суммой, в которой выигрыш одного игрока равен проигрышу другого), биматричные(конечная игра двух игроков с ненулевой суммой, в которой выигрыш каждого игрока сосредоточены в матрице игр данного игрока), непрерывные(функция выигрыша каждого игрока является непрерывной в зависимости от стратегий).

3. Принятие решений. Типы задач, критериев и общая схема решения. Общие группы методов решения многокритериальных задач принятия решений.

Microsoft Word - Глава_2.doc (ifmo.ru)

4. Методы равномерной оптимальности, справедливого компромисса, свертывания критериев (аддитивный критерий), главного критерия, идеальной точки и последовательных уступок в условиях полной определенности.

Метод равномерной оптимизации, Метод справедливого компромисса, Метод свертывания критериев - Оценка конкурентоспособности предприятий (организаций). (studref.com)

Методы последовательной оптимизации - Документ (gigabaza.ru) - главного критерия

Метод идеальной точки, Вопросы и задания для самоконтроля - Менеджмент: методы принятия управленческих решений (studme.org) - идеальной точки

Московский финансово-промышленный униврситет «Синергия» (e-biblio.ru) - кратко про всё

5. Нормализация критериев в условиях полной определенности. Принципы максимальной эффективности и минимизации рисков.

В условиях полной определенности — Студопедия (studopedia.ru)

6. Постановка задач линейного программирования. Примеры, различные формы задач и подходы решения.

Линейное программирование. Задача линейного программирования (ЗЛП) и методы ее решения. Общий и канонический вид. Примеры решения задач онлайн (100task.ru)

7. Множества решений неравенств, уравнений и их систем в задачах линейного программирования. Допустимые решения. Допустимые базисные решения.

Основные теоремы линейного программирования (lektsii.org)

8. Сведения из теории выпуклых множеств. Выпуклые множества в n-мерном пространстве.

2. Выпуклые множества в n – мерном пространстве и допустимые базисные решения злп (studfile.net)

9. Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи.

Основные теоремы линейного программирования (lektsii.org)

10. Геометрический метод решения задачи линейного программирования m х n. Пример для задачи m x 2 (на максимум и минимум).

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ (narod.ru)

Графоаналитический (графический) способ решения задач линейного программирования обычно используется для решения задач с двумя переменными, когда ограничения выражены неравенствами, а также задач, которые могут быть сведены к таким задачам.

Пусть задача линейного программирования имеет вид:

L = c1*x1 + c2*x2 → max(min) (2.1)

{ 𝑎11𝑥1 + 𝑎𝑎12𝑥𝑥2 ≤ (≥)𝑏1,

{ … … … … … …

{ 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 ≤ (≥)𝑏𝑚, (2.2)

Где с1, с2, аi1, аi2, bi - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, или минимизируется.

Каждое из неравенств (2.2) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми i i bi a 1 x1 + a 2 x2 = ; i=1,…,m. В том случае, если система неравенств (2.2) совместна, допустимая область решений задачи есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называют многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Множеством допустимых решений для данной частной задачи может быть:

• пустая область;

• выпуклый многоугольник, включая вырожденные случаи - отрезок и единственную точку;

• выпуклая многоугольная неограниченная область, включая вырожденные случаи - луч и прямую.

Практическая реализация решения задачи линейного программирования (2.1) – (2.2) на основе ее геометрической интерпретации включает следующие этапы:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.2) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений. Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедливо, то выбирается альтернативная полуплоскость.

3. Определить многоугольник решений как пересечение найденных полуплоскостей.

4. Построить градиент целевой функции, т.е. вектор ( ) ( , ) 1 2 grad L = с с , координатами которого служат коэффициенты целевой функции L. Этот вектор определяет направление наискорейшего возрастания целевой функции.

5. Построить ряд линий уровня целевой функции L, т.е. прямых, перпендикулярных градиенту L. При этом построение линий уровня следует вести в направлении градиента, если решается задача на максимум, и в противоположном направлении (в направлении «антиградиента»), если решается задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз касаются допустимого множества.

11. Аналитический метод решения задачи линейного программирования m x n (симплекс-метод). Для задач на максимум и минимум.

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ (narod.ru)

12. Симплекс-таблицы в симплекс-методе для задач на максимум и минимум.

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ (narod.ru)

13. Метод искусственного базиса в симплекс-методе.

Онлайн решение Метод искусственного базиса

14. Двойственные задачи линейного программирования. Теоремы двойственности. (Во вкладках посмотреть)

15. Антагонистические матричные игры. Примеры игр: игра в монету, поиск, игра полковника Блотто и др. Максимин и минимакс. Выигрыши двух игроков. (Из колобашкина)

16. Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков. (Из колобашкина)

17. Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков в игре. Теорема Дж. фон Неймана о ситуации равновесия. (Из колобашкина)

18. Аналитическое решение игры 2×2. Геометрическое решение игры 2×2. Взять из кр 2 зад

19. Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр.

20. Свойства оптимальных смешанных стратегий в матричной игре.

21. Графический метод решения матричной игры (2×m). взять 3 зад из кр

22. Графический метод решения матричной игры (nx2). взять 3 зад из кр

23. Активные (существенные) стратегии игроков. Теоремы об активных стратегиях.

24. Принцип доминирования стратегий двух игроков, Теоремы о доминируемых стратегиях.

25. Вполне смешанная игра. Решение матричной игры nxn методом обратной матрицы.

26. Сведение матричной игры пхт к двойственной задаче линейного программирования. Общий подход. Методика решения матричной игры nxm симплекс-методом.

27. Неантагонистические игры. Биматричные игры. Постановка задачи. Функции выигрышей.

28. Примеры биматричных игр: дилемма узников, семейный спор, перекресток, ястребы-голуби и др.

29. Принципы доминирования в биматричных играх. Пример для матриц размера 3×3. Наилучшие стратегии игроков.

30. Ситуация равновесия по Нэшу в биматричной игре произвольной размерности. Свойства ситуаций равновесия. Теорема Дж. Нэша.

31. Ситуация равновесия по Нэшу в биматричной игре 2×2. Поиск смешанных стратегий для двух игроков.

32. Графическая интерпретация решения в биматричной игре 2×2 по Нэшу. Сильно равновесные стратегии.

33. Оптимальность по Парето. Поиск оптимальных стратегий по Парето в биматричной игре 2×2. Множество Парето. Точка утопии.

34. Пример поиска оптимальных стратегий по Парето в играх «дилемма узников» и «семейный спор».

35. Принятие решений в условиях неопределенности. Статистические методы принятия решений. Виды неопределенностей.

36. Принятие решений в статистических играх в условиях полной определенности. Статистические методы принятия решений. Критерии Вальда, Сэвиджа, Гурвица, MM-критерий.

37. Принятие решений в статистических играх в условиях неопределенности. Статистические методы принятия решений. Критерии Байеса, Лапласа, Ходжа- Лемана.

38. Планирование эксперимента в статистических играх в условиях неопределенности.

39. Позиционные игры. Дерево решений. Позиционные игры с полной и неполной информацией. Информационное множество.

40. Нормализация позиционной игры. Привести общий пример для двухходовой позиционной игры с полной информацией.

41. Сведение позиционной игры к матричной в условиях неполной информации. На примере двухходовых и трехходовых игр.

42. Сведение позиционных игр к матричным и биматричным в условиях полной информации о стратегиях противника.

43. Позиционные игры со случайными ходами.