Вопросы для самоконтроля

В чем состоит суть задач целочисленной оптимизации?
Какие задачи называются частично целочисленными?
Почему метод полного перебора неэффективен при решении задач ЦЛП?
Как формируются логические условия при постановке задач ЦЛП?
Как производится формирование зависимых условий в процессе постановки задач ЦЛП?

Тема 13. Игровые модели теории принятия решений Основные понятия и определения

Неопределенность. Количественная неопределенность. Информационная неопределенность. Стоимостная неопределенность. Профессиональная неопределенность. Ограничительная неопределенность. Неопределенность внешней среды. Риск. Задачи природной неопределенности. Задачи в условиях конкуренции. Игры. Теория игр. Стратегия игры. Парные игры. Бескоалиционные игры. Коалиционные игры. Игры с нулевой суммой. Игры с ненулевой суммой. Матричные игры. Биматричные игры. Одноходовые игры. Многоходовые игры. Платежная матрица. Максимин. Минимакс. Принцип минимакса. Нижняя цена игры. Верхняя цена игры. Чистая цена игры. Оптимальные чистые стратегии. Игры без седловых точек. Смешанные стратегии.

13.1 Теория игр как раздел теории принятия решений. Матричные игры с нулевой суммой

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

Неопределенность означает отсутствие, неполноту информации об объекте или процессе, либо неуверенность в ее достоверности.

Существуют различные виды неопределенности, например:

количественная, связанная со значительным числом объектов или элементов системы;
информационная, вызванная недостатком информации или ее неточностью по каким-либо причинам;
стоимостная - из-за слишком высокой платы за определенность;
профессиональная вследствие недостаточной компетентности ЛПР (например, неспособности учесть требуемое число влияющих факторов);
ограничительная (например, из-за недостатка времени);
внешней среды, связанная с непредсказуемой реакцией среды или конкурента на реализацию принятого решения.

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

Для ситуации риска можно оценить вероятность того или иного варианта развития событий.

Пример для иллюстрации различия между ситуациями риска и неопределенности. В условиях риска доход от реализации единицы продукции является случайной величиной, точное значение которой неизвестно, но описывается с помощью известной функции распределения.

В условиях неопределенности функция распределения неизвестна.

При решении задач в условиях неопределенности возникают две ситуации. При первой сама система препятствует принятию решений (задачи “природной неопределенности” – например, задача производства сельскохозяйственной продукции при неизвестных погодных условиях). Здесь природа может рассматриваться как “доброжелательный противник”, т.к. она не преследует целей, противоположных целям человека.

Для второй ситуации характерна конкуренция, когда каждый участник стремится выиграть у конкурента. Для таких конфликтных ситуаций характерно, что эффективность решений каждой стороны существенно зависит от действий другой. Например, при определении объема выпуска продукции на одном предприятии нельзя не учитывать размеров выпуска аналогичной продукции на других предприятиях.

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

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

Игра характеризуется некоторым набором правил, которые устанавливают:

выбор образа действия игроков на каждом этапе игры;
информацию, которой обладает каждый игрок;
плату для каждого игрока после завершения любого этапа игры.

Стратегией игры называется совокупность правил, определяющих поведение игрока на протяжении игры. Стратегии определяют результаты или платежи в игре; при этом каждый игрок имеет некоторое множество (конечное или бесконечное) возможных стратегий.

Классификация игр возможна по разным признакам.

А) По количеству игроков. Если игроков всего двое, или игроки объединяются в две группы, преследующие противоположные цели, то имеет место парная игра.

Б) В зависимости от взаимоотношений участников различают бескоалиционные (участники не имеют права заключать соглашения) и коалиционные игры (иногда используются термины некооперативные и кооперативные игры соответственно).

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

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

Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется после одного хода каждого игрока) и многоходовые (выигрыш распределяется после нескольких ходов).

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

Мы ограничимся рассмотрением парных матричных игр с нулевой суммой, в которых результаты задаются матрицей, строки и столбцы которой соответствуют стратегиям 1-го и 2-го игроков соответственно, а элементы - выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры.

Матричные игры с нулевой суммой

Если игрок I имеет стратегий, а игрок II - стратегий, то игра называется матричной игрой размерности .

Пусть игрок I выбрал одну из своих возможных стратегий , а игрок II, не зная результата выбора игрока I, - стратегию . Выигрыши игрока I и игрока II для данных стратегий удовлетворяют соотношению ; т.е. если ввести обозначение , то .

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