- •1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.
- •2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.
- •3. Система линейных алгебраических уравнений (слау). Метод Гаусса. Пример.
- •4. Матрицы.
- •5. Обратная матрица.
- •6. Неопределенная система лау. Базисные.
- •7. Множества. Выпуклые линейные комбинации.
- •8. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.
- •9. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
- •10. Теорема об экстремальном значении целевой функции.
- •13. Нахождение исходного опорного решения.
- •14. Симплексный метод.
- •16. Приращение целевой функции
- •17, 18. Критерии оптимальности
- •19. Метод невязок.
- •20. Двойственные задачи.
- •24. Теоремы двойственности. Основное неравенство двойственности.
- •28. Теорема о ранге матрицы коэффициентов тз
- •29. Нахождение исходного опорного решения транспортной задачи
- •30. Переход к новому опорному решению тз
- •32. Метод потенциалов.
- •33. Теорема об эквивалентных преобразованиях матрицы затрат.
- •35. Оценка свободной клетки.
- •36. Критерий оптимальности. Переход к оценочной матрице.
- •37.Открытая модель транспортной задачи.
- •38. Распределительный метод
- •39. Постановка задачи цп.
- •40.Метод Гомори.
- •41. Понятие об игровых моделях
- •42. Приведение экономических задач к теоретико-игровой форме.
- •43. Парная конечная игра. Платежная матрица. Maxmin/minmax стратегии.
42. Приведение экономических задач к теоретико-игровой форме.
Пусть имеется два игрока, один из которых может выбрать i-стратегию из m возможных (i=1,m), а второй, не зная выбор первого – j стратегию из n возможных (j=1,n). В результате игрок 1 выигрывает величину aij, а второй игрок проигрывает эту же величину. Ясно, что игрок 1 стремится максимизировать эту величину, а игрок 2 – минимизировать.
Составим матрицу А.
-
(
a11 a12 … a1n
)
A=(aij)=
a21 a22 … a2n
…
am1 am2 … amn
Строки этой матрицы соответствуют стратегиям 1 игрока. Столбцы соответствуют стратегиям второго игрока. Эти стратегии называются чистыми, а матрица А платежной матрицей или матрицей игры. Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размерности m x n. Если такая матрица составлена, то говорят, что игра приведена к матричной форме. К этой форме можно привести любую конечную парную игру. Поэтому такие игры называют матричными.
43. Парная конечная игра. Платежная матрица. Maxmin/minmax стратегии.
Пусть имеется два игрока, один из которых может выбрать i-стратегию из m возможных (i=1,m), а второй, не зная выбор первого – j стратегию из n возможных (j=1,n). В результате 1 игрок выигрывает величину aij, а второй игрок проигрывает эту же величину.
Составим матрицу А.
-
(
a11 a12 … a1n
)
A=(aij)=
a21 a22 … a2n
…
am1 am2 … amn
Строки этой матрицы соответствуют стратегиям 1 игрока. Столбцы соответствуют стратегиям второго игрока. Эти стратегии называются чистыми, а матрица А платежной матрицей или матрицей игры. Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размерности m x n.
α=max(min aij) |
i j |
– нижняя цена игры или максимин, а соответствующая ему стратегия (строка) называется максиминной. Принцип максимина: нужно выбрать такую стратегию, чтобы при наихудшем поведении противника получить максимальный выигрыш.
β=min(max aij) |
|
j i |
|
- верхняя цена игры или минимакс, а соответствующая ему стратегия (столбец) называется минимаксной.
Теорема 1. Нижняя цена игры всегда не превосходит верхней цены игры, т.е α≤β
Доказательство: Для любых индексов i и j справедливы соотношения:
αi=min aij ≤ aij ≤ max aij = βj |
j=1,n i=1.m |
α=max aij≤βj |
i=1.m |