16.Сведение игры m×n к двойственным задачам лп

Содержание

• 1.Экономико-математическая модель транспортных задач
• 2.Общая формулировка тз
• 3.Теор. (о ранге сис-мы ограниченной закр. Тз) и следствие из нее. Открытая тз
• 4.Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
• 5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
• 6.Понятие об игровых моделях
• 7.Классификация игр.
• 8.Формальное представление игр
• 10.Фундаментальное неравенство для цен антагонистических игр
• 11.Седловая точка. Теорема о седловой точке
• 12.Понятие смешанной стратегии, чистой стратегии, активной стратегии
• 13.Теорема об активной стратегии. Решение игры 2×2 (формулы)
• 14.Графический метод решения игры 2×2
• 15.Доминирующие стратегии, заведомо невыгодные стратегии, упрощение игр.
• 16.Сведение игры m×n к двойственным задачам лп
• 17.Игры с природой: постановка задачи, матрица рисков.
• 18.Критерий принятия решений в условиях риска (Байеса I и II). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
• 19.Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
• 20.Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица. Показатель оптимизма.
• 21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
• 22.Принцип оптимальности и уравнения Беллмана
• 23. Задача о распределении средств между n предприятиями (основные уравнения).
• 25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
• 2 6. Планарные и плоские графы. Изоморфные графы. Полные графы.
• 27. Эйлеровы графы. Крит. Сущ-я эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
• 28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
• 29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
• 30.Комбинаторная постановка задачи коммивояжера.
• 31. Постан-ка зад. Коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
• 32. Постановка задачи коммивояжера на языке теории графов.
• 33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
• 34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
• 35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.