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

Продолжение темы 3. Задачи линейного программирования 3.9. Транспортная задача Постановка транспортной задачи общего вида. Постановка транспортной задачи общего вида: «Имеется т пунктов отправления («поставщиков») и п пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены: ai – объемы производства i-го поставщика, i = 1, …, т; вj – спрос j-го потребителя, j = 1,…,п; и сij – стоимость перевозки одной единицы продукции из пункта Ai – i-го поставщика, в пункт Вj – j-го потребителя. Для наглядности данные представлены в виде таблицы стоимостей перевозок (табл. 3.17). Таблица 3.17 Потребители Поставщики В1 В2 … Вn запасы А1 С11 C12 C1n а1 А2 С21 C22 C2n а2 … Am Cm1 Cm2 Cmn аm Потребности в1 в2 вn Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными». Под планом перевозок, естественно, понимают объем перевозок, т. е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести т · п штук переменных хij, i = 1,…, п, j = 1, …, т, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных и будет планом, который необходимо найти, исходя из постановки задачи. Ограничения задачи примут вид: – условие минимизации суммарных транспортных расходов; – ограничения по запасам; (3.11) – ограничения по потребностям; – условие неотрицательности. Для разрешимости задачи 3.11 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков: . Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (3.12): – условие сбалансированности. (3.12) Решение закрытых транспортных задач (ЗТЗ). В силу ограничений (3.12), ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику, а именно: каждая переменная хij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути, является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности. Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (3.12). Система линейных уравнений, состоящая из т + п уравнений с тп неизвестными. Можно доказать, что линейно независимых уравнений в системе (3.12) т + п – 1, ввиду условия сбалансированности, т. е. базисных переменных должно быть т + п – 1. Итак, в качестве плана будем представлять себе таблицу размера т ∙ п, в которой должно быть занято т + п – 1 клеток, отвечающих базисным переменным xij. Построение первоначального опорного плана по правилу наименьшей стоимости Рассматриваем матрицу (таблицу) транспортных расходов, стоимостей, данную изначально в качестве условия задачи. Выбираем клетку с минимальной ценой перевозки (клетка с номером i, j) и помещаем в эту клетку наименьшее из чисел . Затем исключаем из рассмотрения строку, соответствующую поставщику (если аi меньшее), или столбец, соответствующий потребителю (если вj меньшее). Исключение строки означает, что запасы i-го потребителя удовлетворены. Из оставшейся таблицы снова выбираем наименьшую стоимость, и т. д. продолжаем до тех пор, пока все запасы не исчерпаны, а потребности не удовлетворены. Проверьте, что сумма чисел в каждой строке получившейся таблицы равна аi, а сумма чисел в каждом столбце равна вj, что и требовалось. Число занятых клеток должно равняться т + п – 1, в противном случае, если занятых клеток меньше, чем т + п – 1, дополним таблицу необходимым количеством нулей (нулевых перевозок) и будем считать эти клетки с нулями занятыми так, чтобы общее количество занятых клеток равнялось равно т + п – 1. Нули поставим в клетки, соответствующие минимальной стоимости. Рассмотрим пример построения первоначального опорного плана. Задача. Пусть имеется четыре поставщика некоторой продукции и пять потребителей. Стоимости перевозок от i-го поставщика к j-му потребителю, а также потребности потребителей и возможности поставщиков заданы таблицей 3.18. Таблица 3.18 В1 В2 В3 В4 В5 запасы А1 21 19 11 12 12 24 А2 26 29 14 1 26 12 А3 39 1 22 8 25 18 А4 53 23 40 26 28 16 потребности 11 13 26 10 10 60=60 Ттранспортная задача является закрытой, т. к. 24 + 12 + 18 + 16 = 11 + 13 + 26 + 10 + 10 (потребности равны запасам). В распределительной таблице стоимости перевозок располагаются в правом верхнем углу клеток. В центр клеток помещаем числа, соответствующие первоначальному опорному плану перевозок. Минимальная стоимость перевозки – это число 1, оно встречается на двух местах, с номерами (2, 4) и (3, 2). Выберем любое, к примеру (2, 4), и поместим туда наименьшее из чисел 10 и 12, т. е. 10. Потребности потребителя В4 удовлетворены. вычеркнем четвертый столбец из рассмотрения (табл. 3.19). Таблица 3.19 В1 В2 В3 В4 В5 запасы А1 21 19 11 12 12 24 А2 26 29 14 10 1 26 12 А3 39 1 22 0 8 25 18 А4 53 23 40 26 28 16 потребности 11 13 26 10 10 В таблице 3.19 минимальный по стоимости элемент равен 1 на месте (3, 2). Записываем в эту клетку число 13 как наименьшее из чисел 13 и 18 и вычеркиваем второй столбец. потребности В2 удовлетворены (табл. 3.20). Таблица 3.20 В1 В2 В3 В4 В5 Запасы А1 21 19 2411 12 12 24 А2 26 29 214 101 26 12 А3 39 131 22 0 8 5 25 18 А4 1153 23 40 26 5 28 16 потребности 11 13 26 10 10 Следующее минимальное число по стоимости в таблице после двух вычеркиваний – это число 11 на месте (1, 3). Выписываем в клетку 24 и вычеркиваем первую строку. запасы у поставщика А1 исчерпаны. Остальные клетки заполним аналогично. Проверим, что сумма чисел построчно и по столбцам совпадает с возможностями и потребностями. Число занятых клеток, соответствующих базисным переменным хij опорного плана, обязано равняться 4 + 5 – 1 = 8 = т + п – 1. Первоначальный план соответствует таблице 3.20. Метод потенциалов. При построении плана задача заключается в нахождении оптимального плана, удовлетворяющего ограничениям задачи. Эту задачу решает метод потенциалов, предложенный в 1949 г. советскими учеными Л. В. Канторовичем и М. К. Гавуриным. Теорема. Если для некоторого опорного плана Х = транспортной задачи можно подобрать систему из m + n чисел u1, u2, …, um, v1, v2, … vn, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия: 1) для всех (3.11) 2) для всех (3.12) где – матрица стоимостей перевозок. I шаг (вычисление потенциалов). Условие (3.11) представляет собой систему из (m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы. Проведем эти вычисления, записывая найденные потенциалы в дополнительно зарезервированные столбец и строку (табл. 3.21). Таблица 3.21 В1 В2 В3 В4 В5 запасы vj А1 21 19 2411 12 12 24 40 А2 26 29 214 101 26 12 43 А3 39 131 22 0 8 5 25 18 50 А4 1153 23 40 26 5 28 16 53 потребности 11 13 26 10 10 ui –49 –29 –42 –25 Проводя вычисления, смотрим только на занятые клетки (в силу условия 3.11) и на числа, стоящие в правом верхнем углу – стоимости перевозок. Пусть u1 = 0, найдем v4 = 53 (0 + v4 = 53), затем u5 = –25 (–25 + 53 = 28). После v3 = 50 (v3 + u5 = 25). Затем можем найти u2 =  –49 (u2 + 50 = 1), после u4 = –42 (u4 + 50 = 8). Найдем v2 = 43 (u4 + v2) = 1 и, наконец, u3 = –29 (u3 + 43 = 14) и v1 = 40 (u3 + v1 = 11). Все потенциалы ui, vj найдены. II шаг (проверка плана на оптимальность). Для проверки плана на оптимальность необходимо проверить условие (3.12). Для занятых клеток это условие выполняется, именно на них достигается равенство. Остается посчитать суммы ui + vj для свободных клеток. Если ui + vj ≤ сij , то, по теореме, план является оптимальным и задача решена. Таблица 3.22 В1 В2 В3 В4 В5 запасы vj А1 40>21 –9<19 2411=11 –2<12 15>12 24 40 А2 43>26 –6<29 214=14 101=1 18<26 12 43 А3 50<39 131=1 21<22 08=8 525=25 18 50 А4 1153=53 4<23 14<40 11<26 528=28 16 53 потребности 11 13 26 10 10 ui –49 –29 –42 –25 Первоначальный опорный план не оптимален, условие (3.12) нарушено в клетках (1, 1), (1, 5), (2, 1), (3, 1) (табл. 3.22). III ШАГ (улучшение плана). Для проведения операции улучшения плана нам понадобится понятие цикла. Определение. Циклом будем называть набор клеток матрицы перевозок, в котором две и ровно две соседние клетки расположены в одной строке или в одном столбце, и первая и последняя клетки набора лежат тоже в одной строке или столбце. Графически цикл представляет собой ломаную, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену. С понятием цикла связаны важные свойства планов: 1) допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла; 2) если имеем опорный план, то для каждой свободной клетки можно образовать единственный цикл, содержащий данную клетку и некоторые из занятых. Улучшение плана производится по следующей схеме. В подчеркнутых клетках табл. 3.22 находим клетку с наибольшей разностью ui + vj – cij, т. е. где условие (3.12) нарушается максимально. Затем для этой клетки, согласно утверждению 2, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке. Имеем таблицу 3.23. Таблица 3.23 В1 В2 В3 В4 В5 запасы А1 40>21 + –9<19 11=11 – 24 –2<12 15>12 24 А2 43>26 –6<29 14=14 + 2 1=1 – 10 18<26 12 А3 50>39 131=1 21<22 + 08=8 – 525=25 18 А4 11 53=53– 4<23 14<40 11<26 + 528=28 16 потребности 11 13 26 10 10 Начиная с клетки (1, 1), где условие (3.12) нарушено максимально, строим цикл. Клетку (1, 1) помечаем знаком «+». Цикл единственен, у нас все занятые клетки вошли в цикл, но это необязательно. Рассмотрим элементы плана хij, расположенные в клетках со знаком «–» : х13 = 24, х24 = 10, х35 = 5, х41 = 11, выберем из них наименьший х35 = 5, обозначим Δ = 5. Строим новый план хн по правилу: для клеток с «–», для клеток с « + », для клеток, не входящих в цикл. Новый план записываем в таблицу 3.24. Клетка в которой разность хij – Δ равна 0, у нас (3, 5), теперь будет свободной. Проверьте, что число занятых клеток по-прежнему равно 8. Таблица 3.24 В1 В2 В3 В4 В5 запасы А1 521 19 1911 12 12 24 А2 26 29 714 51 26 12 А3 39 131 22 58 25 18 А4 653 23 40 26 1028 16 потребности 11 13 26 10 10 Полученный план будет удовлетворять прежним ограничениям, т. к. сдвиг перевозки происходит по циклу, а значит не нарушает суммарную перевозку по столбцу и по строке. Общая же стоимость перевозок уменьшается на число, равное (ui + vj – cij) · Δ, где Δ – объем перевозок, перемещаемый по циклу, у нас эта величина равна 5 · (40 – 21) = 5 · 19 = 95. Действительно, для плана Х общая суммарная стоимость перевозки равнялась ·24 + 14 · 2 + 1 · 10 + 1 · 13 + 8 · 0 + 5 · 25 + 53 · 11 + 5 · + 28 = 1 163. Для нового плана Хн: = 5 · 21 + 19 · 11 + 7 · 14 + 5 · 1 + 13 · 1 + 5 · 8 + 6 · 53 + + 10 · 28 = 1 068. Итак, мы построили новый, «лучший», план, шаг III закончен. И теперь переходим к следующей итерации: строим систему неравенств, проверяем план на оптимальность, улучшаем, если план не оптимален. Для нашей задачи проведем дальнейшее решение. Проводя аналогичные рассуждения находим новую систему потенциалов (табл. 3.27), проверяем на оптимальность, убеждаемся, что полученный план оптимален. Таблица 3.27 В1 В2 В3 В4 В5 vj A1 1121 –10<19 1311 –3<12 –1<12 21 A2 24<26 –7<29 1214 0<1 2<26 24 A3 32<39 131 22 = 22 58 10<25 32 A4 50<53 19<23 140 526 1028 50 ui 31 –10 –24 –22 –62 Итак, предложенный таблицей 3.27 план перевозок является оптимальным, при этом суммарная стоимость перевозок равна: = 11 · 21 + 13 · 11 + 12 · 14 + 13 · 1 + 5 · 8 + 1 · 40 + 5 · 26 + 10 · 28 = 1 045. Действительно, после второй итерации стоимость перевозок уменьшилась на величину (30 – 26) · 5 = 20. после третьей – (43 – 40) · 1 = 3, т. е. 1 068 – 23 = = 1045, что мы и имеем. Задача решена. Замечание. Если транспортная задача является задачей открытого типа, в которой условие баланса не выполняется, а именно сумма запасов больше суммы потребностей, то решить такую задачу можно по предложенной схеме методом потенциалов, введя дополнительного потребителя, с потребностью равной разности балансов и нулевыми стоимостями перевозок от каждого поставщика к этому потребителю. 4. Экономико-математические методы и модели теории игр В теории игр рассматриваются задачи принятия решений в ситуациях с двумя участниками, каждый из которых имеет свои интересы и обладает возможностями применять для достижения своих целей разнообразные действия. В отличие от задач линейного программирования, значение целевой функции для каждого из субъектов зависит также от решений, принимаемых другим участником. 4.1. Математические модели теории игр Ситуация, в которой эффективность принимаемого одной стороной решения зависит от действий другой стороны, называется конфликтной. Конфликт всегда связан с определенного рода разногласиями (это не обязательно антагонистическое противоречие). Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину, и наоборот. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. Например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Каждый из них имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны). Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. Игра – это математическая модель реальной конфликтной ситуации. Стороны, участвующие в конфликте, называются игроками. Исход конфликта называется выигрышем. Правила игры – это система условий, определяющая варианты действий игроков; объем информации каждого игрока о поведении партнеров; выигрыш, к которому приводит каждая совокупность действий. Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. Игроки обозначаются A и B . Игра называется антагонистической (с нулевой суммой), если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из вариантов действий, предусмотренных правилами, называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из вариантов действий (например, в шахматах). Случайный ход – это случайно выбранное действие (например, бросание игральной кости). Мы будем рассматривать только личные ходы. Стратегия игрока – это совокупность правил, определяющих поведение игрока при каждом личном ходе. Обычно в процессе игры на каждом этапе игрок выбирает ход в зависимости от конкретной ситуации. Возможно также, что все решения приняты игроком заранее (т. е. игрок выбрал определенную стратегию). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае. Цель теории игр – разработать методы для определения оптимальной стратегии каждого игрока. Стратегия игрока называется оптимальной, если она обеспечивает этому игроку при многократном повторении игры максимально возможный средний выигрыш (или минимально возможный средний проигрыш независимо от поведения противника). Пример 1. Каждый из игроков, A или B , может записать, независимо от другого, цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то A выигрывает количество очков, равное разности между цифрами. Если разность меньше 0, выигрывает B. Если разность равна 0 – ничья. У игрока A три стратегии (варианта действия): = 1 (записать 1), = 2, = 3, у игрока тоже три стратегии: , , . B A = 1 = 2 = 3 = 1 -1 -2 = 2 1 -1 = 3 2 1 Задача игрока A – максимизировать свой выигрыш. Задача игрока B – минимизировать свой проигрыш, т. е. минимизировать выигрыш A. Это парная игра с нулевой суммой. 4.2. Платежная матрица Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Предположим, что игрок A имеет m стратегий (обозначим их А1, А2, …, ), а игрок B (противник) – n стратегий (). Такая игра называется игрой размерности m х n. Пусть игрок A выбрал одну из своих возможных стратегий . Игрок B, не зная результата выбора игрока A, выбрал стратегию . Для каждой пары стратегий (, ) определен платеж второго игрока первому, т. е. выигрыш игрока A. Выигрышем игрока B будет соответственно (–). Никакой дискриминации по отношению ко второму игроку здесь нет, т. к. величины могут быть и отрицательны, тогда – > 0. Например, = –2 – выигрыш A, – = 2 – выигрыш B. Такая игра называется матричной; матрица, составленная из чисел , называется платежной. В примере 1 платежная матрица имеет вид . Строки этой матрицы соответствуют стратегиям игрока A, а столбцы – стратегиям игрока B. Общий вид такой матрицы B A B1 B2 … Bj … Bn A1 a11 a12 … a1j … a1n A2 a21 a22 … a2j … a2n … … Ai ai1 ai2 … aij … ain … … … … … … … Am am1 am2 … amj … amn 4.3. Нижняя и верхняя цена игры Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его , запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем , т. е. i – минимальный выигрыш при применении стратегии Ai. В примере 1: 1 = min {0, –1, –2} = –2; 2 = min {1, 0, –1} = –1; 3 = min {0, –1, –2} = 0. Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой i максимально. Обозначим . Это гарантированный выигрыш, который может обеспечить себе игрок A, т. е. ; этот выигрыш называется нижней ценой игры или максимином. Стратегия Ai, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш при любом поведении игрока B. В примере 1 . Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A. Выбирая стратегию B1, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим . Аналогично при выборе стратегии Bj максимально возможный выигрыш A – ; запишем эти числа в добавочной строке. Чтобы уменьшить выигрыш A, надо из чисел выбрать наименьшее . Число называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем ). Стратегия игрока B, обеспечивающая выигрыш , называется его минимаксной стратегией. В примере 1: ; ; ; . Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет. B A B1 B2 B3 A1 –1 –2 –2 A2 1 –1 –1 A3 2 1 2 1 Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. Можно доказать, что , т. е. . В примере 1 . Если , т. е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий (Ai, Bj). В примере 1 игра имеет седловую точку (А3, B3). В этом случае число называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0. Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью. Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т. к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия. Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1, А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолета В3 вооружением А1 равна 0,8 и т. д., т. е. элемент aij платежной матрицы – вероятность поражения самолета Вj вооружением Аi. Платежная матрица имеет вид: В А Вид самолета В1 В2 В3 Тип вооружения А1 0,5 0,6 0,8 А2 0,9 0,7 0,8 А3 0,7 0,5 0,6 Решить игру, т. е. найти нижнюю и верхнюю цену игры и оптимальные стратегии. Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке. В А В1 В2 В3 А1 0,5 0,6 0,8 0,5 А2 0,9 0,7 0,8 0,7 А3 0,7 0,5 0,6 0,5 0,9 0,7 0,8 0,7 0,7 В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7. Ответ: = 0,7. Оптимальные стратегии – А2 и В2. 4.4. Решение игр в смешанных стратегиях Если игра имеет седловую точку, то ее решение находится по принципу минимакса: нужно использовать чистые стратегии, указываемые седловой точкой. Рассмотрим игру, не имеющую седловой точки, т. е. . Для игрока А естественно желание увеличить выигрыш, а для В – уменьшить проигрыш. Для этого применяется сложная стратегия, состоящая в случайном применении нескольких чистых стратегий с определенными частотами. Такая сложная стратегия называется смешанной. Смешанной стратегией игрока A называется применение чистых стратегий А1, А2, …, Аi, …, Аm с вероятностями р1, р2, …, рi, …, рm, причем . Смешанные стратегии игрока A записываются в виде матрицы или в виде вектора рi, …, . Аналогично смешанная стратегия или , где . Чистая стратегия Аi – частный случай смешанной, она задается матрицей . Для каждой пары смешанных стратегий определяется платежная функция – математическое ожидание выигрыша игрока А при использовании игроками соответственно стратегий и : . Соображения принципа осторожности применительно к смешанным стратегиям подсказывают, что игрок A должен выбирать свою стратегию так, чтобы максимизировать функцию , а игрок B – минимизировать функцию . При этом нижняя цена игры (максимин), верхняя цена игры (минимакс). Основная теорема матричных игр – теорема фон Неймана. В матричной игре существует такая пара смешанных стратегий, что значения минимакса и максимина совпадают. Их общее значение называется ценой игры , стратегии и называются оптимальными. Стратегии игроков, входящие в их оптимальные смешанные стратегии с ненулевой вероятностью, называются активными. Большое практическое значение имеет теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры, если второй игрок не выходит за пределы своих активных стратегий. Эта теорема указывает способ нахождения оптимальных стратегий при отсутствии седловой точки. Рассмотрим игру размера 2 х 2, которая является простейшим случаем конечной игры. Пусть игра задана платежной матрицей , и седловая точка отсутствует. Требуется найти оптимальные смешанные стратегии игроков и , а также цену игры . По теореме об активных стратегиях: если игрок A будет применять свою оптимальную смешанную стратегию, то его выигрыш будет равен цене игры независимо от действий игрока В. Игрок А будет применять стратегию А1 с вероятностью р1 и стратегию А2 с вероятностью р2. Если игрок B применяет стратегию В1, то средний выигрыш игрока A равен . Если же игрок B применит стратегию В2, то средний выигрыш A будет также равен : . Учитывая , получим систему уравнений из которой находим , и . Аналогично из системы находим . 4.5. Геометрическая интерпретация игры 2 х 2 Пусть игра задана платежной матрицей . По оси абсцисс отложим единичный отрезок А1 А2, где точка А1 (0, 0) изображает стратегию А1, А2 (1, 0) – стратегию А2, а каждая промежуточная точка SA этого отрезка изображает смешанную стратегию первого игрока , где – расстояние от точки до , – расстояние от точки до . Выигрыш игрока A будем откладывать на вертикальных отрезках. Случай 1. Если игрок B применит стратегию В1, то выигрыш игрока A при стратегии А1 равен а11, поэтому на оси ординат отложим отрезок А1 В1 = а11. При применении игроком A стратегии А2 выигрыш равен а21, отложим этот отрезок на перпендикуляре из точки А2, обозначим полученную точку В1'. Ордината любой точки М1 отрезка В1В1′ равна среднему выигрышу игрока A при применении смешанной стратегии (действительно, этот выигрыш равен математическому ожиданию случайной величины, т. е. ). Запишем уравнение прямой В1В1′: , т. е. , тогда при получим . Случай 2. Если игрок B применяет стратегию В2, то аналогично откладываем отрезки а12 и а22 и получаем отрезок В2В2′. Ордината любой точки М2 отрезка В2В2′ – выигрыш игрока A, если A применяет смешанную стратегию , а B – стратегию В2. Построим нижнюю границу выигрыша игрока А – ломаную В1NВ2′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р1, р2). Аналогично находится оптимальная стратегия игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А2NА1′ и брать точку N с наименьшей ординатой. Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. .