Элементы теории игр и исследование операций

Разбить на страницы

Показывать лекцию целиком

Элементы теории игр и исследование операций

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

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

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

числу n участвующих в игре игроков;

взаимоотношению игроков в процессе игры;

количеству стратегий игры;

результату игры (сумме выигрыша, проигрыша);

виду критерия (функции) выигрышей и др.

Стратегия игры ( игрока ) - это система правил, однозначно определяющих выбор поведения игрока при каждом ходе игры в зависимости от текущей ситуации. Матричная игра - парная игра с нулевой суммой (где один может выиграть столько, сколько проиграет другой игрок) и с конечным числом стратегий. Матрица выигрышей (платежей) конфликтной игры - это матрица X вида$$X(m\times n) = \begin{Vmatrix} x_{11} x_{12} \dotsc x_{1n} \cr x_{21} x_{22} \dotsc x_{2n} \cr \hdotsfor{4} \cr x_{m1} x_{m2} \dotsc x_{mn} \cr \end{Vmatrix}$$ где m - число стратегий игрока номер 1, n - число стратегий игрока номер 2, x_ij - полезность или выигрыш игрока 1 в любой ситуации (i,j), когда игрок 1 придерживается стратегии номер i, а игрок номер 2 - стратегии номер j. Если игрок 1 выберет стратегию номер $$k\in \{1, 2, \dotsc, m\}$$, то игрок 2 должен выбрать стратегию номер $$j\in \{1, 2,\dotsc, n\}$$ так, чтобы выигрыш игрока 1 был не меньше минимального из всех возможных в этом случае x_kj. Поэтому игрок 1 будет выбирать свою стратегию k так, чтобы этот минимальный выигрыш был бы наибольшим, то есть чтобы выполнялось (максминное) условие вида$$m_k = \min_j \{x_{kj}\} = \max_i \min_j \{x_{ij}\}.$$

При этой стратегии игрок 1 при любом поведении игрока 2 обеспечивает себе выигрыш не меньше, чем m, то есть выполнено условие: $$x_{kj}\ge m_k$$ для всех j=1,2,..., n. Аналогично можно построить (минимаксную) стратегию игрока номер 2:$$M_p=\max _i \{x_{jp}\} = \min _j max _i \{x_{ij}\}.$$

При любых действиях игрока 1, игрок 2 проигрывает ему не более Mp, то есть выполнено условие: $$x_{ip}\le M_p$$ для всех i=1, 2, ..., m. Задача первого игрока - максимизировать свой выигрыш, а задача второго - минимизировать свой проигрыш, и наоборот. Эти задачи взаимосвязаны (двойственны по отношению друг к другу).

Пример. Дана матрица игры вида$$X(2\times 4) = \begin{Vmatrix} 2 7 6 10 \cr 8 4 9 5 \end{Vmatrix}$$ Определим максминную (то есть максимум из минимумов) и минимаксную (то есть минимум из максимумов) стратегии для этой матрицы игры. Максминная стратегия (m₁,m₂)=(2, 4). Максимальный проигрыш равен 4. Минимаксная стратегия (M₁, M₂, M₃, M₄)=(8, 7, 9, 10). Минимальный выигрыш будет равен 7 (единиц измерения выигрыша, например, 7 тысяч руб.).

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

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

Рассмотрим задачу управления прибылью X(t) (в руб., например) некоторого предприятия, которая может быть описана обыкновенным дифференциальным уравнением следующего вида:$$\frac {dX}{dt} = aX-bX^2,$$ где a>0 - постоянный коэффициент роста прибыли, b>0 - постоянный коэффициент снижения прибыли. Это известное логистическое уравнение. Его решение имеет вид$$X(t) = \frac {aX_0\exp (at)}{a+bX_0 (\exp(at)-1)},$$ где X₀=X(t₀) - величина прибыли в начальный момент времени t=t₀.

(Оно вычисляется, например, заменой вида X=1/Y и последующим решением получаемого линейного уравнения; можно также разделить переменные и проинтегрировать уравнение как уравнение с разделяющимися переменными).

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

Легко видеть, что$$\lim\limits_{n\to \infty} X(t) = \frac ab,$$ то есть величина прибыли не возрастает беспредельно, а всегда ограничена.

Отношение $$\frac {a}{b}$$ - это максимальная прибыльность предприятия, прибыль "насыщения".

В связи с этим возникает следующая задача: определить величины получаемой на каждом временном шаге (на некоторой временной сетке) прибыли при условии, чтобы за предыдущий фиксированный отрезок времени [0,T], они были бы максимальны.

Разобьем отрезок [0,T] на n равных частей с шагом h=T/n. Будем считать, что величина прибыли на шаге i (i=1,2,...,n) равна G_i=u_iX_i, где числовой параметр $$u_i\in [0,1]$$ выбирается на каждом шаге. Это возможные проценты прибыли (от прибыли, в долях) для заданного состояния X_i. Обычно так и бывает на практике.

Сформулируем данную задачу как классическую задачу оптимального управления: необходимо максимизировать функцию цели вида$$J(X,u) = \sum^{n-1}_{i=0} U_{iXi} + X_n,$$ где величина прибыли на шаге i+1 определятся рекуррентными уравнениями вида$$X_{i+1} = \frac {a(1-u_i)X_i \exp(ah)}{a+b(1-u_i) X_i(\exp(ah)-1)}, \qquad i=0{,}1,\dotsc,n-1$$ и ограничениями вида $$X_i \le f(t_i)$$, где$$f(t_1) = \frac {aX_0 \exp(at_i)}{a+bX_0(\exp(at_i)-1)}; \quad u_i\in [0,1], \quad X(t_0)=X_0.$$

Отметим, что целевая функция представляет собой сумму (то есть является аддитивной), а состояние X_i+1, в которое перешла система, зависит от данного состояния X_i и U_i, но не зависит от того, каким образом система перешла в состояние X_i, то есть выполняется условие отсутствия последствия. Выполнение этих двух условий (гипотез) гарантирует нам справедливость известного принципа оптимальности Беллмана для данной задачи, и, следовательно, для его решения мы можем воспользоваться классическим методом динамического программирования. Изложим его суть применительно к рассматриваемой задаче.

Введем следующие обозначения: P_n - сумма прибыли за n шагов, S_n - максимальный доход, получаемый за n шагов при переходе системы из начального состояния X₀ в конечное состояние X_n, u=(u₀, u₁, ... , u_n) ; S_n-k - максимальный доход, получаемый при переходе из любого состояния X_k в конечное состояние X_n на оставшихся n-k шагах. Тогда можно записать следующее условие:$$S_{n-k} = \max _{u\in [0{,}1]} [S_{n-k-1} + P_{k+1}] , \quad k=0{,}1,2,\dotsc, n-1.$$

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

Можно записать, что P=P_n-1+X_n, где X_n, согласно формуле выше, определяется так:$$X_n = \frac {a(1-u_{n-1}X_{n-1} \exp(ah)}{a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1)}.$$

Если система уже находится в состоянии X_n-1, то единственная возможность, которая есть в нашем распоряжении, - это так выбрать U_n-1 на n-1 шаге (то есть для перехода к состоянию X_n ), чтобы максимизировать функцию вида$$X_{n-1}u_{n-1} + \frac {a(1-u_{n-1}X_{n-1} \exp(ah)}{a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1)}.$$

Введем следующее обозначение:$$S_{n-1} (X_{n-1}) = \max_{u_{n-1}} \bigl[X_{n-1}u_{n-1} + \frac {a(1-u_{n-1}X_{n-1} \exp(ah)}{a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1)}. \bigr].$$

Это равенство определяет некоторую функцию состояния X_n-1. Величина, равная P= P_n-2 + S_n-1 (X_n-1) задает то максимальное значение функции P, которое может быть достигнуто, если бы система прошла оптимально через точки X₀, X₁,..., X_n-1.

Решим описанным способом поставленную задачу. Как сказано выше, для этого надо построить последовательность функций $$S_n, S_{n-1},\dotsc, S_0$$ и найти управляющие параметры U_n-1, U_n-2, ..., U₀. Для этого используются рекуррентные соотношения вида$$S_i(X_i) = \max _{U_i}[X_{iUi} +S_{i+1} (f(X_i, U_i))],$$ при i=1, 2, ..., n-1 ; при этом S_n=X_n.

Итак, пусть S_n=X_n. Теперь находим S_n-1:$$S_{n-1}(X_{n-1}) = \max_{u_{n-1}} \Bigl[X_{n-1}u_{n-1} + \frac {a(1-u_{n-1}X_{n-1} \exp(ah)}{a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1)}. \Bigr].$$

Для нахождения максимума функции S_n-1(X_n-1) по переменной $$U_{n-1}\in [0;1]$$ находим производную выражения, находящегося в скобках функции по неизвестной U_n-1 и приравниваем ее к нулю (вспомним необходимое условие экстремума функции одной переменной):$$X_{n-1} + \frac {-aX_{n-1}\exp(a+b(1-u_{n-1})X_{n-1}(\exp(ah)-1))} {(a+b(1-u_{n-1})X_{n-1}(\exp(ah)-1))^2} + \\[3pt] + \frac {bX_{n-1}(\exp(ah)-1) a(1-u_{n-1})\exp(ah) } {(a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1))^2 } =0.$$

После упрощения этого выражения (приведение подобных членов и простые алгебраические преобразования) получаем$$X_{n-1} - \frac {aX_{n-1}\exp(ah)}{a+b(1-u_{n-1}) X_{n-1} (\exp(ah) -1) } =0.$$

Отсюда получаем соотношение вида$$a+b(1-u_{n-1}) X_{n-1} (\exp(ah)-1) = a\exp (ah/2).$$

Из этого уравнения находим неизвестный параметр управления U_n-1, при котором функция S_n-1(X_n-1) принимает максимальное значение. Это значение равно $$U_{n-1} = 1- \frac {a}{bX_{n-1}(\exp(ah/2)+1}$$.

Аналогично можно найти все остальные неизвестные параметры U_n-2, ..., U₀. Тогда задача полностью решена.

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

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

Конечным результатом любой задачи принятия решений является решение.

Принятие решения - это выбор одного варианта из некоторого множества рассматриваемых допустимых вариантов. Обычно их число конечно, а каждый вариант выбора определяет некоторый результат (экономический эффект, прибыль, выигрыш, полезность, надёжность и т.д.), допускающий количественную оценку. Такой результат обычно называется полезностью решения. Иначе говоря, отыскивается вариант с наибольшим значением результата. Возможен и подход с минимизацией противоположной оценки, например, отрицательной величины полезности. Часто на практике встречается ситуация, когда каждому варианту решения соответствует единственный результат, хотя возможны и другие случаи, например, когда каждому варианту i и условию j, характеризующему полезность, соответствует результат решения x_ij. Таким образом, можно говорить о матрице решений |x_ij|, i=1,2,..., m ; j=1,2,..., m. Чтобы оценить решение, необходимо уметь оценивать все его последствия. Существуют различные подходы для такой оценки. Например, если решения альтернативные, то можно последствия каждого из них характеризовать суммой его наибольшего и наименьшего результатов, максимумом из возможных таких сумм, максимумом из максимумов по всем вариантам (оптимистическая позиция выбора), максимумом из среднего арифметического (нейтральная позиция выбора), максимумом из минимума (пессимистическая позиция) и другими критериями.

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

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

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

Формализуемые решения принимаются на основе соответствующих математических методов (алгоритмов). Математическая модель задачи оптимизации формализуемого решения включает следующие элементы:

задаваемую оптимизируемую целевую функцию (критерий управляемости): $$\Phi =F(x_1,x_2,\dotsc,x_n)$$, где x_i, i=1,2,...,n - параметры, учитываемые при принятии решения (отражающие ресурсы принятия решений);

условия, отражающие ограниченность ресурсов и действий лица принимающего решение (ЛПР): g_i(x_j)<a_i, k_i(x_j)=b_i ; c_j<x_j<d_i, i=1,2,...,m ; j=1,2,..., n.

Непременное требование для решения задачи оптимизации - n>m.

В зависимости от критерия эффективности, стратегий и факторов управления выбирается тот или иной метод (алгоритм) оптимизации.

Общая процедура принятия решений может состоять из следующих этапов:

анализ проблемы и среды (цели принятия решения, их приоритеты, глубина и ограничения рассмотрения, элементы, связи, ресурсы среды, критерии оценки);

постановка задачи (определение спецификаций задачи, альтернатив и критериев выбора решения);

выбор ( адаптация, разработка ) метода решения задачи ;

выбор ( адаптация, разработка ) метода оценки решения ;

решение задачи (математическая и компьютерная обработка данных, имитационные и экспертные оценки, уточнение и модификация, если это необходимо);

анализ и интерпретация результатов.

Выбор решения - заключительный и наиболее ответственный этап процесса. В реальных задачах принятия решений, к началу этапа выбора еще сохраняется большая неопределенность, поэтому сразу осуществить выбор единственного решения из множества допустимых практически очень сложно. Поэтому используется принцип последовательного уменьшения неопределенности, который заключается в последовательном трёхэтапном (обычно) сужении множества решений. На первом этапе исходное множество альтернативных решений Y сужается (используя ограничения на ресурсы) до множества приемлемых или допустимых решений $$Y1\subseteq Y$$. На втором этапе множество допустимых решений Y₁ сужается (учитывая критерий оптимальности) до множества эффективных решений $$Y_2\subseteq Y_1$$. На третьем этапе осуществляется выбор (на основе критерия выбора и дополнительной информации, в том числе и экспертной) единственного решения $$Y^*\in Y_2$$.

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

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

Страницы: