- •1.Проблемные ситуации и их классификация
- •6. Задача о наилучшем использовании ресурсов
- •7.Задача о распределения персонала (о назначения)
- •8. Транспортная задача открытого и закрытого типа
- •9. Задача о движении автобусов
- •10. Математическая модель задачи линейного программирования
- •11.Формы записи задачи линейного программирования
- •14.Отыскание исходного опорного базиса
- •15.Переход от одного опорного решения к другому
- •12.Линейное векторное пространство. Линейная зависимость векторов. Ранг.
- •13.Понятие базиса системы. Базисное и опорное решение системы.
- •16.Каноническая форма задачи линейного программирования
- •17. Приведение задачи линейного программирования к канонической форме
- •18. Геометрический смысл задачи линейного программирования
- •19. Свойства решений задачи линейного программирования (без док)
- •24. Основная идея симплекс-метода решения злп и ее теоретическое обоснование
- •25. Теорема о возможности улучшения опорного решения задачи лп
- •26. Условие применимости симплекс-метода и теорема о неограниченности целевой функции на одз
- •27. Структура симплекс таблицы
- •28. Алгоритм симплексного метода решения злп
- •29. Контроль за правильностью решения злп симплекс-методом
- •30. Понятие о вырождении. Причины зацикливания в симплекс-методе
- •31. Понятие двойственности в линейном программировании. Правила построения двойственных задач
- •32.Леммы и теоремы двойственности (без док)
- •33. Применение двойственных задач
- •34. Связь между решениями прямой и двойственной задачи на примере пары симметричных задач
- •35.Экономическая интерпретация двойственных задач (на примере). Экономический смысл 1-ой теоремы двойственности
- •36. Оптимальные двойственные оценки и их смысл в задаче об использовании ресурсов.
- •37. Анализ моделей на устойчивость и чувствительность
- •38. Метод искусственного базиса
- •39. Основные понятия теории игр
- •40. Антагонистические игры, седловая точка
- •41. Чистые и смешанные стратегии матричных игр с нулевой суммой, платежная функция
- •42. Теорема о необходимом и достаточном условии существования решения антагонистической игры
- •43. Правила упрощения матричной игры
- •44. Решение матричной игры 2x2
- •45. Геометрическое решение матричной игры Mx2, 2xN
- •46. Приведение матричной игры к задаче линейного программирования
- •47. Статистические игры. Критерии для принятия решений
- •48.Общая постановка задачи нелинейного программирования
- •49. Геометрическая интерпретация задачи нелинейного программирования
- •50. Геометрический способ решения задачи нелинейного программирования
- •51.Глобальный (абсолютный) и локальный экстремум функции
- •52.Условный экстремум функции
- •53. Метод неопределенных множителей Лагранжа.
- •54. Определение выпуклой и вогнутой функции
- •55. Общая постановка задачи выпуклого программирования. Теорема о существовании решения задачи вп (формулировка)
- •56. Седловая точка функции Лагранжа
- •57. Теорема Куна-Таккера
- •58.Основная идея градиентных методов решения знлп
- •59.Метод Франка –Вульфа
- •60. Метод штрафных функций
- •61. Метод наискорейшего спуска
- •62. Определение сепарабельной функции
- •63. Кусочно-линейная аппроксимация
- •64. Задача целочисленного программирования, методы ее решения
- •65. Задача дробно-линейного программирования, геометрическая интерпретация и метод решения
- •66. Постановка задачи параметрического программирования и принципы ее решения
- •67. Постановка задачи динамического программирования
- •68. Задачи, приводящие к задаче динамического программирования
- •69. Принцип оптимальности Беллмана
- •70. Связь проблемы выбора с задачами лп, нлп, игр
43. Правила упрощения матричной игры
Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры. Задача решения игры, если ее матрица не содержит седловой точки, тем сложнее, чем больше значения m и n. Сократить размерность матрицы можно, исключая дублирующие и заведомо невыгодные доминирующие стратегии.
Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в платежной матрице, т. е. матрица содержит одинаковые строки (столбцы). Если все элементы i-й строки матрицы меньше соответствующих элементов k-й строки, то i-я стратегия для игрока А называется доминирующей. Если же элементы r-го столбца матрицы не меньше соответствующих элементов j-го столбца, то для игрока B стратегия Br — доминирующая.
Таким образом, при решении игры m×n следует:
a) проверить, не содержит ли матрица седловой точки;
б) если седловой точки нет, то нужно сравнить между собой элементы строк и столбцов для исключения дублирующих и доминирующих стратегий.
44. Решение матричной игры 2x2
Матрица А игры имеет вид
А=
.
Если седловой точки нет, то решением игры являются смешанные стратегии U=(u1, u2), Z=(z1,z2).
Согласно основной теореме теории игр, применение оптимальной стратегии U=(u1, u2) обеспечивает для игрока А получение выигрыша v при любых стратегиях игрока В. Оптимальная стратегия для игрока В также смешанная. Поэтому, если игрок А применяет свою оптимальную стратегию, то при этом игрок В может использовать одну из чистых стратегий, величина выигрыша игрока А останется неизменной. Запишем систему уравнений
Так как u1+u2=1, то решение таково:
u1=
,
u2=
.
(4.3)
Подставляя значения u1 и u2 в одно из уравнений (2.1), получаем
v=
.
(4.4)
Составляя аналогичную систему уравнений, можно найти оптимальную стратегию для игрока В:
z1= , z2= (4.5)
45. Геометрическое решение матричной игры Mx2, 2xN
Используя геометрическую интерпретацию, можно найти решение игр, заданных матрицей 2n. Каждой из n стратегий игрока В соответствует прямая. Построив эти прямые, находят нижнюю границу выигрыша. Точка К, лежащая на нижней границе, для которой величина выигрыша наибольшая, определяет цену игры и ее решение. При этом определяется активные стратегии игрока В (соответствующие им прямые пересекаются в точке К): из геометрических соображений можно найти значения zj, соответствующие активным стратегиям игрока В.
Аналогично может быть решена игра с матрицей m2, только в этом случае строят верхнюю границу выигрыша и на ней определяют минимум.
46. Приведение матричной игры к задаче линейного программирования
чтобы найти решение данной игры, определяемой матрицей А, нужно составить пару двойственных задач и найти их решение.
процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы:
1. Составляют пару двойственных задач линейного программирования, эквивалентных матричной игре.
2. Определяют оптимальные планы пары двойственных задач.
3. Используя соотношение между планами пары двойственных задач и оптимальными стратегиями и ценой игры, находят решение игры.
