Матричные игры и линейные программы как модели поведения

Двойственные задачи линейного программирования и рыночное равновесие

Рассмотрим задачу линейного программирования с ограничениями вида неравенств в следующей интерпретацииМногие другие интерпретации задач линейного программирования представлены, например, в известной книге: Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. М.: Наука, 1969.. Пусть некоторая фирма P1 располагает m видами сырья, используя которые, она может выпускать n типов продукции. Известны цены $$c_j \ge 0$$, $$1\le j\le n$$, по которым происходит реализация единицы продукции каждого j -го типа, составляющие вектор-столбец$$c = (c_1 \dots c_j \dots c_n)^T,$$ где верхний индекс T соответствует операции транспонирования. Известны также запасы $$b_i \le 0$$, $$1\le i\le m$$, сырья каждого вида, составляющие вектор-столбец$$B = (b_1\dots b_i \dots b_m)^T.$$ Наконец, задана матрица A коэффициентов aij, $$1\le i\le m$$, $$1\le j\le n$$, характеризующих количество сырья вида i, необходимое для производства единицы продукции типа j. Требуется определить плановые уровни wj, $$1\le j\le n$$, производства продукции каждого типа, обеспечивающие максимальный доход при заданных сырьевых ресурсах.

Если принять, что план производства описывается вектором-столбцом$$w = (w_1 \dots w_j \dots w_n)^T,$$ то условие его обеспеченности сырьевыми ресурсами можно описать с помощью неравенств$$a_{i1} w_1 + \ldots + a_{in} w_n \le b_i,\quad 1 \le i \le m,$$ которые можно свернуть в векторную запись вида$$Aw \le b.$$

Теперь поставленная задача выбора плана $$w^\ast$$, максимизирующего доход$$(c^T, w) = c_1 w_1 + \ldots + c_n w_n,$$ может быть представлена в форме следующей математической задачи:$$(c^T, w^\ast) = \max \{(c^T, w)\colon w \ge 0_n,\ Aw \le b\},$$ которую будем называть прямой задачей линейного программирования (с ограничениями типа неравенств).

Заметим, что указанный в (12.1) вектор-столбец 0n соответствует началу координат в пространстве Rn, а условие $$w \ge 0_n$$ эквивалентно координатным неравенствам $$w_j \ge 0$$, $$1 \le j\le n$$. В дальнейшем (там, где это не может вызвать сомнений) мы будем (для краткости записи) опускать нижний индекс при 0n, указывающий размерность пространства.

Примем, что фирма P1, помимо продажи своей продукции, может также продавать имеющиеся у нее запасы сырья по ценам, характеризуемым вектором-столбцом$$u = (u_1 \dots u_i \dots u_m)^T.$$ Такая продажа может быть экономически оправданной для фирмы P1, если средства, выручаемые от продажи сырья всех видов, которое необходимо для производства единицы продукции некоторого типа j, будут не меньше, чем выручка от продажи этой единицы продукции. Т.е. экономические мотивы для рассмотренной продажи сырья могут существовать лишь при выполнении неравенств$$a_{1j} u_1 + \ldots + a_{mj} u_m \ge c_{j}, \quad 1 \le j \le n,$$ которые можно свернуть в векторную запись вида$$A^T u \ge c.$$

Рынок, с которым взаимодействует фирма P1, продавая продукцию (или сырье), будем рассматривать как вторую (агрегированную) сторону в описываемой операции и обозначать P2. Естественно принять, что участники рынка, покупающие сырье, заинтересованы в уменьшении своих затрат. Поэтому их задачу можно описать как формирование вектора цен u*, удовлетворяющего условиям$$(b^T, u^\ast) = \min \{(b^T, u)\colon u \ge 0_m,\ A^T u \ge c\}.$$ Задачу (12.2), решаемую второй стороной и представляющую интересы рынка, будем называть двойственной задачей линейного программирования (с ограничениями вида неравенств).

Для двойственной пары задач (12.1), (12.2) линейного программирования справедлива теорема двойственности . Два разных доказательства этой теоремы содержатся в учебном пособии: Мухачева Э.А. Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука, 1987. См. также: Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998. Согласно этой теореме, если одна из задач (12.1) и (12.2) имеет решение, то и вторая задача имеет решение, причем в этом случае$$(c^T, w^\ast) = (b^T, u^\ast).$$

Величины, введенные при описании пары двойственных задач (12.1), (12.2), собраны (для наглядности) ниже.

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

Примем теперь, что производитель, выбрав некоторый план производства $$w \ge 0_n$$, может продавать на рынке не только произведенную продукцию, но и остатки сырья. Кроме того, он может закупать на рынке недостающее сырье. Продажа и закупка сырья происходит по одним и тем же ценам $$u \ge 0_m$$, которые формирует рынок. В такой постановке доход производителя, который мы будем рассматривать как критерий M(w,u) первой стороны, определяется выражением$$\begin{gathered} M(w,u) = \sum_{j=1}^n c_j w_j + \sum_{i=1}^m u_i\left(b_i - \sum_{j=1}^n a_{ij} w_j\right) =\\ = \sum_{i=1}^m u_i b_i + \sum_{j=1}^n w_j\left(c_j - \sum_{i=1}^m a_{ij} u_i\right)\!, \end{gathered}$$ или (в векторной форме)$$M(w, u)= (c^T, w) + (b^T u)- u^T Aw.$$ Если принять, что производитель имеет достаточное финансовое обеспечение, любой план производства $$w \ge 0_n$$ является допустимым. Допустим также и любой вектор $$u \ge 0_m$$, формируемый рынком, интересы которого противоположны интересам производителя, желающего максимизировать свой доход.

В результате получаем, что отношения сторон P1 и P2 характеризуются антагонистической игрой с ядром M(w,u) и множествами стратегий сторон, определяемыми соответственно условиями $$w \ge 0_n$$ и $$u \ge 0_m$$.

Исследуем вопрос о существовании равновесного поведения сторон, т.е. вопрос о существовании пары стратегий (w*,u*), являющейся седловой точкой ядра M(w,u). Оценим величину дохода производителя, гарантируемую выбором плана $$w\ge 0_n$$. Согласно (12.4),$$\min_{u \ge 0} M(w,u) = \left\{ \begin{aligned} (c^T, w), (\forall i =1\dots m)\ \sum_{j=1}^n a_{ij} w_j \le b_i,\\ \ -\infty, (\exists i,\, 1 \le i \le m)\ \sum_{j=1}^n a_{ij} w_j > b_i. \end{aligned} \right.$$ Действительно, при выполнении условия $$Aw\le b$$ выбор вектора u=0m минимизирует доход M(w,u), поскольку вынуждает производителя отдавать излишки сырья по нулевым ценам. В случае, когда реализация принятого производителем плана $$w \ge 0_n$$ требует покупки недостающего сырья вида i, вторая сторона может неограниченно уменьшать доход P1 путем увеличения цены ui на дефицитное (для P1 ) i -е сырье. Следовательно,$$\max_{w \ge 0} \min_{u \ge 0} M(w,u) = \max \left\{ (c^T, w) \colon w \ge 0_n,\, Aw \ge b \right\}\!.$$ Т.е. производитель может максимизировать гарантированный доход, если откажется от закупок недостающего сырья и ограничится имеющимися запасами. В состав этих запасов могут входить и те объемы, на поставку которых заблаговременно заключены соответствующие контрактыНеобходимость заблаговременного обеспечения производства сырьем и комплектующими (например, на договорной основе) является обстоятельством, хорошо известным в практике рыночной деятельности.. Таким образом, максиминная стратегия стороны P1 (если такая стратегия существует) является решением w* прямой задачи линейного программирования; ср. (12.1) и (12.6).

Теперь оценим возможные максимальные затраты второй стороны P2, соответствующие некоторому вектору $$u \ge 0_m$$ цен за сырье. Согласно (12.4),$$\min_{w \ge 0} M(w,u) = \left\{ \begin{aligned} (b^T, u), (\forall j =1\dots n)\ \sum_{i=1}^m a_{ij} u_i \le c_j,\\ \ +\infty, (\exists j,\, 1 \le j \le n)\ \sum_{i=1}^m a_{ij} u_i > c_j. \end{aligned} \right.$$ Действительно, при выполнении условия $$A^T u \ge c$$ выбор плана w=0n (т.е. отказ от производства продукции) максимизирует доход M(w,u) первой стороны (или затраты второй стороны). В этом случае продажа сырья дает не меньший доход, чем продажа продукции, произведенной из этого сырья.

Допустим, что доход от продажи продукции некоторого типа j превышает затраты на приобретение сырья, необходимого для производства единицы этой продукции. Тогда производитель может неограниченно увеличивать свой доход, закупая сырье в ассортименте, необходимом для производства продукции типа j. Заметим, что это рассуждение предполагает наличие у производителя необходимых оборотных средств (или возможность использования кредитов). Таким образом (при указанных условиях),$$\min_{u \ge 0} \max_{w \ge 0} M(w,u) = \min \left\{ (b^T, u) \colon u \ge 0_m,\, A^T u \ge c \right\}\!.$$ Т.е. вторая сторона может минимизировать свои возможные максимальные затраты, если установит такие цены на сырье, что производитель откажется от производства. При этом минимаксная стратегия стороны P2 (если такая стратегия существует) является решением u* двойственной задачи линейного программирования; ср. (12.2) и (12.7).

Теперь из (12.1)-(12.3) вытекает, что$$(c^T, w^\ast) = \max_{w \ge 0} \min_{u \ge 0} M(w,u) = \min_{u \ge 0} \max_{w \ge 0} M(w,u) = (b^T, u^\ast).$$ Следовательно, если хотя бы одна из пары (12.1), (12.2) двойственных задач линейного программирования имеет решение, то функция M(w,u) имеет седловую точку (см. теорему о необходимых и достаточных условиях существования седловой точки ядра в лекции 6), т.е.$$(\forall w \ge 0_n) (\forall u \ge 0_m)\ M(w, u^\ast) \le M(w^\ast, u^\ast) \ge M(w^\ast, u),$$ $$M(w^\ast, u^\ast) = (c^T, w^\ast) = (b^T, u^\ast).$$ Таким образом, мы установили, что пара двойственных задач линейного программирования определяет равновесную ситуацию (w*,u*) на рассмотренном выше рынке.

Сведение решения матричной игры к решению пары двойственных задач линейного программирования

Подставляя (12.5) в (12.8) и учитывая (12.9), устанавливаем справедливость следующих неравенств:$$(\forall w \ge 0_n) (\forall u \ge 0_m)\quad (c^T, w) - u^{\ast T}A w \le 0 \le (b^T, u) - u^T Aw^\ast.$$

Приняв, что цены на продукцию всех типов и запасы сырья всех видов являются единичными, т.е.$$c_j = 1,\ 1 \le j \le n,\qquad b_i=1,\ 1 \le i \le m,$$ приводим (12.10) к виду:$$(w_1 + \ldots w_n) - u^{\ast T} Aw \le 0 \le (u_1 + \ldots u_m) - u^T A w^\ast.$$ Введя нормированные переменные$$\begin{gathered} x_i = u_i / (u_1 + \ldots u_m),\quad 1 \le i \le m,\\ y_j = w_j / (w_1 + \ldots w_m),\quad 1 \le j \le n, \end{gathered}$$ и составленные из них векторы-столбцы$$x = (x_1 \dots x_m)^T,\qquad y = (y_1\dots y_n)^T,$$ перепишем (12.12) как$$1 - u^{\ast T} Ay \le 0 \le 1 - x^T A w^\ast,$$ или$$x^T A w^\ast \le 1 \le u^{\ast T} A y.$$ При этом предполагается, что суммы из знаменателей правых частей равенств в (12.13) являются положительными. Это допущение не противоречит условиям $$w \ge 0_n$$, $$u \ge 0_m$$ из (12.10). Таким образом,$$\begin{gathered} x_i \ge 0,\ 1 \le i \le m,\qquad x_1 + \ldots + x_m = 1,\\ y_j \ge 0,\ 1 \le j \le n,\qquad y_1 + \ldots + y_n = 1, \end{gathered}$$ или (11.15))$$x \in S_m,\quad y \in S_n.$$

Предположим, что общее значение минимакса и максимина ядра, указанное в (12.9), является положительным. Обозначим обратное ему число через v, т.е.$$\begin{gathered} (c^T, w^\ast) = w_1^\ast + \ldots + w_n^\ast = v^{-1} > 0,\\ (b^T, u^\ast) = u_1^\ast + \ldots + u_n^\ast = v^{-1} > 0. \end{gathered}$$ Заметим, что эти записи учитывают также условия (12.11). Теперь из (12.13) и (12.16) следует, что$$\begin{gathered} x_i^\ast = u_i^\ast / (u_1^\ast + \ldots + u_m^\ast) = v u_i^\ast,\qquad 1 \le i \le m,\\ y_j^\ast = w_j^\ast / (w_1^\ast + \ldots + w_m^\ast) = v w_j^\ast,\qquad 1 \le j \le n. \end{gathered}$$

Умножая (12.14) на положительное число v, используя обозначения (12.17) и учитывая (12.15), выводим справедливость отношений$$(\forall x \in S_m)(\forall y \in S_n) \quad x^T Ay^\ast\le v\le x^{\ast T}Ay,$$ $$v = x^{\ast T} A y^\ast.$$

Из (11.19) и (12.18), (12.19) следует, что пара (x*,y*) является равновесной (по Нэшу) в смешанном расширении конечной антагонистической игры с матрицей A. При этом введенное выше положительное число v оказывается ценой этой игры в смешанных стратегиях.

Рассмотрим произвольную $$m\times n$$ матрицу A с коэффициентами aij, $$1\le i\le m$$, $$1\le j \le n$$, и сопоставим ей вспомогательную $$m\times n$$ матрицу C с положительными коэффициентами$$c_{ij} = a_{ij} + a > 0,\quad 1 \le i \le m,\ 1 \le j \le n,$$ $$a > |\min\{a_{ij}\colon 1 \le i \le m,\ 1 \le j \le n\}| \ge 0.\notag$$ Линейная программа вида (12.1) при единичных коэффициентах из (12.11) заведомо имеет решение. Действительно, условия $$Cw\le b$$, имеющие вид$$c_{i1} w_1 + \ldots + c_{in} w_n \le 1,\ 1 \le i \le m,\qquad w_j \ge 0,\ 1 \le j \le n,$$ определяют непустую область в Rn, поскольку вектор w=0n удовлетворяет этим условиям. В указанной области линейная форма (cT,w) оказывается ограниченной сверху, ибо, согласно (12.21),$$w_1 + \ldots + w_n \le 1/c_{i1} + \ldots 1/c_{in},\ 1 \le i \le m.$$ Таким образом, для линейной программы с матрицей $$C$$ неравенства вида (12.8) и вытекающие из них отношения$$\begin{gathered} (\forall x \in S_m) (\forall y \in S_n) \quad x^T C y^\ast \le v_c \le x^{\ast T}Cy,\\ v_c = x^{\ast T} C y^\ast, \end{gathered}$$ аналогичные утверждениям (12.18), (12.19), являются справедливыми при любой заданной матрице A.

Лемма 2.2. Антагонистическая игра с ядром (11.18), соответствующим произвольной $$m\times n$$ матрице $$A$$ и связанная с ней антагонистическая игра с ядром$$M_c (x,y) = x^T Cy,$$ соответствующим вспомогательной матрице C из (10.20), имеют одно и то же множество ситуаций равновесия. При этом$$v_c = v + a,$$ где vc есть цена смешанного расширения игры с матрицей C, а v - цена смешанного расширения игры с матрицей A.

Доказательство. Как следует из (11.15), (11.18) и (12.20), (12.22)$$M_c (x,y) = \sum_{i=1}^m \sum_{j=1}^n (a_{ij} + a) x_i y_j = \sum_{i=1}^m \sum_{j=1}^n a_{ij} x_i y_j + a = M(x,y) + a,$$ где M(x,y) есть ядро смешанного расширения антагонистической игры с матрицей A. При этом$$M(x,y) = M_c(x,y) - a.$$ Следовательно, справедливость отношений$$(\forall x \in S_m) (\forall y \in S_n)\ M_c (x,y^\ast) \le M_c (x^\ast, y^\ast) \le M_c (x^\ast, y)$$ для игры с матрицей C влечет справедливость аналогичных отношений (11.19) для игры с матрицей A, ибо последние выводятся из (12.24) путем вычитания числа a из всех частей содержащихся в (12.24) неравенств. Доказательство леммы завершается выводом равенства$$v_c = M_c(x^\ast, y^\ast) = M (x^\ast, y^\ast) + a = v + a,$$ вытекающего из (12.23).

Итак, мы установили, что при любой $$m\times n$$ матрице A смешанное расширение антагонистической игры с вспомогательной матрицей C из (12.20) всегда имеет равновесное решение (x*,y*), которое является равновесным решением также и для исходной антагонистической игры. Таким образом, мы установили справедливость следующей теоремы.

Теорема 2.3. Матричная игра с произвольной $$m\times n$$ матрицей A всегда имеет ситуацию равновесия (по Нэшу) в смешанных стратегиях $$x^\ast \in S_m$$, $$y^\ast \in S_n$$, которые могут быть определены из решения (u*,w*) следующей пары двойственных задач линейного программирования$$\begin{gathered} u_1 + \ldots + u_m \to \min\\ u_1 \ge 0,\ldots, u_m \ge 0,\\ (a_{1j} \!+\! a) u_1 \!+\! \ldots \!+\! (a_{mj} \!+\! a)u_m \ge 1,\\ 1 \le j \le n, \end{gathered}\quad \begin{gathered} w_1 + \ldots + w_n \to \max\\ w_1 \ge 0\dots w_n \ge 0,\\ (a_{i1} \!+\! a)w_1 \!+\! \ldots \!+\! (a_{in} \!+\! a)w_n \le 1\\ 1 \le i \le m, \end{gathered}$$ где a из (12.20). При этом$$\begin{gathered} x^\ast = v u^\ast,\quad y^\ast = v w^\ast,\\ v = (u_1^\ast + \ldots + u_m^\ast)^{-1} = (w_1^\ast + \ldots w_n^\ast)^{-1}. \end{gathered}$$

Пример 2.7. Рассмотрим численный пример, которому соответствуют рассмотренные выше матрицы:$$A = \begin{vmatrix} 2 -3 4\\ -3 4 -5\\ 4 -5 6 \end{vmatrix}\qquad C = \begin{vmatrix} 7 2 9\\ 2 9 0\\ 9 0 11 \end{vmatrix}$$ Заметим, что вторая матрица соответствует значению a=5.

Первая из двух линейных программ, указанных в условиях теоремы, имеет вид:$$\begin{gathered} u_1 + u_2 + u_3 \to \min,\\ u_1 \ge 0,\ u_2 \ge 0,\ u_3 \ge 0,\\ 7u_1 + 2 u_2 + 9 u_3 \ge 1,\\ 2 u_1 + 9u_2 \ge 1,\\ 9u_1 + 11 u_3 \ge 1, \end{gathered}$$ и ей соответствует решение$$u^\ast = \left(\frac{1}{20}, \frac{1}{10}, \frac{1}{20}\right)\!, \quad v_c = 5,$$ найденное симплекс- методомСм., например, учебное пособие: Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.. Следовательно,$$x^\ast = \left(\frac{1}{4},\frac{1}{2},\frac{1}{4}\right)\!, \quad v = v_c - a = 0.$$