7.4. Правило доминирования

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

Рассмотрим платежную матрицу .

В матрице P i-я строка

не больше строки s этой матрицы

если одновременно выполняются следующие n неравенств:

, , …, . (7.19)

Строку s называют доминирующей, а строку i доминируемой. При этом говорят также, что s-я строка доминирует i-ю строку или что стратегия A_s игрока А доминирует стратегию A_i.

Игрок А поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые строки. Если в матрице P одна из строк (s) доминирует другую строку (i), то число строк в платежной матрице можно уменьшить путем отбрасывания доминируемой строки (i).

В матрице P j-й столбец

не меньше столбца r этой матрицы

если одновременно выполняются следующие m неравенств:

, , …, . (7.20)

Столбец r называют доминирующим, а столбец j доминируемым.

При этом говорят также, что столбец r доминирует столбец j или что стратегия B_r игрока B доминирует стратегию B_j.

Игрок B поступит разумно, если будет избегать стратегий, которым в матрице игры соответствуют доминируемые столбцы. Если в матрице P один столбцов (r) доминирует другой столбец (j), то число столбцов в матрице P можно уменьшить путем отбрасывания доминируемого столбца (j).

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

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

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

7.5. Геометрический (графический) метод решения игр 2хn (метод нижней огибающей)

Е

7.6. Геометрический (графический) метод решения игр mх2 (метод верхней огибающей)

Е

7.7. Геометрический (графический) метод решения игр 2х2

Е

11. Задачи динамического программирования

11.1. Общая постановка задачи динамического программирования

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

Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.

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

Общая постановка задачи динамического программирования.

Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s₀ в состояние s_n. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений.

Обозначим через X_k управленческое решение на k-м шаге (k=1, 2, …, n). Переменные X_k удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (X_k может быть числом, точкой в n-мерном пространстве или качественным признаком).

Пусть X=(X₁, X₂, …, X_n) – управление, переводящее систему S из состояния s₀ в состояние s_n. Обозначим через s_k состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы s_k в конце k-го шага зависит только от предшествующего состояния s_k-1 и управленческого решения на k-ом шаге X_k (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:

. (11.1)

Таким образом, получаем последовательность состояний s₀, s₁, …, s_k-1, s_k, …, s_n-1, s_n. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом:

Пусть показатель эффективности k-го шага выражается некоторой функцией:

, (11.2)

а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией:

, (11.3)

или

. (11.4)

Тогда задача пошаговой оптимизации (задача динамического программирования) формулируется следующим образом: определить такое допустимое управление Х, переводящее систему S из состояния s₀ в состояние s_n, при котором целевая функция Z принимает наибольшее (наименьшее) значение.

Задача динамического программирования обладает следующими особенностями:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-ом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).

4. Состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления X_k («отсутствие последствия»).

5. На каждом шаге управление X_k зависит от конечного числа управляющих переменных, а состояние s_k – от конечного числа параметров.