рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Задачи теории игр и линейное программирование.

Задачи теории игр и линейное программирование. - раздел Программирование, Методические указания и задания Математическое программирование Если Имеется Несколько Сторон (Лиц), Каждая Из Которых Принимает Некоторое Ре...

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

Пусть имеется два игрока, один из которых может выбрать тую стратегию из m своих возможных, а второй - тую стратегию из n своих возможных. В результате первый игрок выигрывает величину а второй ее проигрывает. Из чисел составим матрицу:

.

Строки матрицы соответствуют стратегиям первого игрока, а столбцы – стратегиям второго. Эти стратегии называются чистыми.

Определение 1. Матрица А называется платежной матрицей игры.

Определение 2. Число называется нижней ценой игры, а число называется верхней ценой игры.

Определение 3.Если , то число v называется ценой игры.

Игра, для которой , называется игрой с седловой точкой.

Если игра, заданная матрицей, не имеет седловой точки, то для нахождения ее решения используются смешанные стратегии.

Определение 4.Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.

Из определения 4 следует, что сумма компонент указанного вектора равно единице, а сами компоненты не отрицательны. Обычно смешанную стратегию первого игрока обозначают как вектор , а смешанную стратегию второго – как вектор ., где , , , .

Если - оптимальная стратегия первого игрока, а - оптимальная стратегия второго игрока, то число

называется ценой игры.

Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры.

Приведем примеры решения игр , и .

Пример 4. Найти решение игры, заданной матрицей и дать геометрическую интерпретацию этого решения.

Решение. Прежде всего проверим наличие седловой точки у данной матрицы. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5).Значит, нижняя цена игры , а нижняя цена игры . Так как , то решением игры являются смешанные оптимальные стратегии, а цена игры заключена в пределах .

Предположим, что для игрока А стратегия задается вектором . Тогда при применении игроком В чистой стратегии или игрок А получит средний выигрыш, равный цене игры, т.е.

Помимо этих двух уравнений, добавляем уравнение связи . Решая полученную систему трех уравнений с тремя неизвестными, найдем , , .

Найдем теперь оптимальную стратегию для игрока В. Пусть для него стратегия задается вектором . Тогда

(1)

Решая полученную систему, найдем , .

Следовательно, решением игры являются смешанные стратегии , , а цена игры .

Дадим геометрическую интерпретацию данной игры. Для этого на плоскости введем систему координат и на оси отложим отрезок единичной длины , каждой точке которого поставим в соответствие некоторую смешанную стратегию (РИС.3).

– Конец работы –

Эта тема принадлежит разделу:

Методические указания и задания Математическое программирование

К изучению раздела курса прикладной математики... Математическое программирование... для студентов экономических специальностей заочной и дневной форм обучения...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Задачи теории игр и линейное программирование.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с целеобразованием и анализом целей и функций; задачи разработки и

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ.
Нахождение решения задачи ЛП (1) – (2) на основе ее геометрической интерпретации [5] включает следующие этапы: 1. Строят прямые, уравнения которых получаются в результате замены в ограниче

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННЫХ ЗАДАЧ.
Если число переменных прямой и двойственной задачи, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи ЛП, можно легко найти решение данной пары задач. При этом и

Симплексный метод.
Симплексный метод является универсальным методом решения задач линейного программирования. Его алгоритм в той или иной интерпретации содержится практически во всех учебниках и учебных пособиях по э

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги