Полный текст

Введение. Общество постоянно сталкивается с проблемой правильного принятия решений [1-4] в той или иной ситуации, и каждый стремится к такому решению, которое даст наилучший результат. В любой управленческой деятельности возникают конфликтные ситуации, в которых затрагиваются интересы двух или более сторон, например, взаимоотношения между покупателем и продавцом. Для правильного принятия решений в таких ситуациях применяется теория игр [5-9], которая представляет собой теоретические основы математических моделей принятия оптимальных решений в конфликтных ситуациях, носящих характер конкурентной борьбы, в которых одна сторона выигрывает за счет другой. Одним из разделов теории игр [10-12] являются биматричные игры, рассматриваемые в данной работе. 1. Биматричные игры. Основные понятия. Биматричной называется конечная игра двух лиц с ненулевой суммой, при этом интересы игроков не являются полностью противоположными [13-14]. Биматричная игра полностью определяется двумя матрицами А и В: ; , где матрица - это платежная матрица первого игрока, - платежная матрица второго игрока [15]. Первый игрок имеет стратегий, второй игрок - стратегий. Иногда биматричные игры записывают в виде одной матрицы. Пара cмешанных стратегий составляет ситуацию равновесия в биматричной игре тогда и только тогда, когда выполняются условия: (1) где - это вектор размера , все компоненты которого равны 1. Теорема (условия дополняющей нежесткости): все решения системы неравенств удовлетворяют следующим условиям [16]: (2) Приводим первые два неравенства системы (1) к каноническому виду: (3) где ; . Система (3) преобразуется к виду (4), а затем к (5): (4) (5) где ; ; ; . Заметим, что должны удовлетворять условиям (6), в которые преобразуется система (2): (6) где - дополнения для соответственно. Рассмотрим алгоритм Лемке для решения биматричной игры с заданными матрицами и размерностью . 1. По элементам матрицы находим константу , по элементам матрицы - по соответствующим формулам: ; . 2. Осуществляем переход от матриц А и B к матрицам А1 и , где ; ; E - матрица размерности , составленная из единиц. 3. Выбираем начальные базисы . Начальная симплекс-таблица имеет вид, как показано в табл. 1, где - это вектор размера , все компоненты которого равны 1; - единичные матрицы размерности и соответственно. Таблица 1 Начальная симплекс-таблица Базис q u v x y u -1m 0 0 A v -1n 0 BT 0 4. Вводим в базис переменную . По правилам симплекс-метода осуществляем пересчет таблицы и выбираем переменную, которая выходит из базиса. 5. Переменную, выведенную из базиса на предыдущем шаге, заменяем на ее дополнение. Пересчитываем таблицу по правилам симплекс-метода. Дополнением к переменной является , , и, наоборот; дополнением к переменной является , и наоборот. 6. Если в базисе вводимая переменная уже присутствует, то конец алгоритма. Иначе переходим к пункту 5 [17-18]. 2. Постановка задачи. В микрорайоне находятся два магазина А и B. Магазин B реализует только кондитерские изделия, а в магазине A ассортимент товаров более разнообразный, небольшую часть которого составляют кондитерские изделия. Сравнительная характеристика магазинов приведена в табл. 2. Таблица 2 Характеристика магазинов Магазин Магазин Площадь 50,0 кв. м 150,0 кв. м График работы с до с до Наценка 40 % 25 % Ассортимент (кондитерские изделия) 10 наименований 30 наименований Месторасположение Спальный район, рядом школа и детский сад Вблизи остановки, парковка для автомобилей Обслуживание % от продаж Оклад Количество продавцов 2 6 Для товароведов магазинов A и B поставлена задача - определить оптимальное количество ассортимента кондитерских изделий при многократных заказах товаров у одного поставщика, при реализации которых будет получена наибольшая средняя прибыль для каждого магазина. На основе мнения экспертов о приоритетах магазинов и их ассортименте, а также исходных данных по закупочным ценам товаров и величине наценки на них составляем платежные матрицы прибылей магазинов, сведенных в одну таблицу, фрагмент которой представлен в табл. 3. Таблица 3 Фрагмент таблицы прибылей магазинов В1 В2 В3 ⋯ В29 В30 А1 (0, 147) (42, -47) (-20, 23) ⋯ (-4; 4) (-113; 127) А2 (36, -41) (58, -66) (-4, 4) ⋯ (13; -15) (-96; 108) А3 (-6, 7) (0, 122) (-46, 52) ⋯ (-29; 33) (-138; 156) Окончание табл. 3 В1 В2 В3 ⋯ В29 В30 А4 (-3, 3) (19, -22) (-43, 48) ⋯ (-26; 29) (-134; 152) А5 (62, -70) (84, -95) (22, -25) ⋯ (39; -44) (-70; 79) А6 (-2, 2) (20, -23) (-42, 47) ⋯ (-25; 28) (-134; 151) А7 (68, -77) (90, -102) (28, -32) ⋯ (45; -51) (-64; 72) А8 (31, -35) (53, -60) (-9, 10) ⋯ (8; -9) (-101; 114) А9 (-49, 55) (-27, 30) (-89, 100) ⋯ (-72; 81) (-181; 204) А10 (12, -13) (34, -38) (-28, 32) ⋯ (-12; 13) (-120; 136) Заполнение матриц происходит, исходя из условия: при реализации одинаковой позиции товара магазин предположительно получит нулевую прибыль, а магазин получит максимальную прибыль, так как приоритет магазина , по мнению экспертов, ниже приоритета магазина . В табл. 3 прибыль выражена в условных единицах. 3. Нахождение оптимальных смешанных стратегий. Вычеркнув доминируемые стратегии [19] в исходных матрицах, в результате получаем сокращенные платежные матрицы, сведенные в одну таблицу (табл. 4). Таблица 4 Платежные матрицы В8 В23 В30 А2 (-13, 15) (-30, 34) (-96, 108) А5 (12, -14) (0, 222) (-70, 79) А7 (0, 203) (2, -2) (-64, 72) В данной игре нет равновесия в чистых стратегиях [20]. Будем искать равновесие в смешанных стратегиях с помощью алгоритма Лемке. Отняв 13 от всех выигрышей игрока А и 223 от всех выигрышей игрока В, получим эквивалентную игру со следующими матрицами выигрышей игроков: ; . Начальная симплекс-таблица для алгоритма Лемке приведена в табл. 5. Таблица 5 Начальная симплекс-таблица (шаг 0) Базис -1 1 0 0 0 0 0 0 0 0 -26 -43 -109 -1 0 1 0 0 0 0 0 0 0 -1 -13 -83 -1 0 0 1 0 0 0 0 0 0 -13 -11 -77 -1 0 0 0 1 0 0 -208 -237 -20 0 0 0 -1 0 0 0 0 1 0 -189 -1 -225 0 0 0 -1 0 0 0 0 0 1 -115 -144 -151 0 0 0 Вводим в базис переменную х1. Вычисляем отношения базисных значений к разрешающему столбцу (табл. 6). Таблица 6 Шаг 1 Б -1 1 0 0 0 0 0 0 0 0 -26 -43 -109 - -1 0 1 0 0 0 0 0 0 0 -1 -13 -83 - -1 0 0 1 0 0 0 0 0 0 -13 -11 -77 - -1 0 0 0 1 0 0 -208 -237 -20 0 0 0 0,005 -1 0 0 0 0 1 0 -189 -1 -225 0 0 0 0,005 -1 0 0 0 0 0 1 -115 -144 -151 0 0 0 0,008 Максимальное отношение находится в строке , которую объявляем ведущей. Выполняем операцию замещения и пересчет таблицы. Вводим в базис переменную (дополнение ). Вычисляем отношения (табл. 7). Таблица 7 Шаг 2 Б -1 1 0 0 0 0 0 0 0 0 -26 -43 -109 0,009 -1 0 1 0 0 0 0 0 0 0 -1 -13 -83 0,012 -1 0 0 1 0 0 0 0 0 0 -13 -11 -77 0,013 0 0 0 1 0 -1,81 0 23,45 253,1 0 0 0 - 0 0 0 0 1 -1,64 0 235,7 23,17 0 0 0 - 0 0 0 0 0 -0,01 1 1,25 1,313 0 0 0 - Максимальное отношение D находится в строке u3, которую объявляем ведущей. Выполняем операцию замещения и пересчет таблицы. Вводим в базис переменную x3 (дополнение u3). Вычисляем отношения D (табл. 8). Таблица 8 Шаг 3 Б 1 0 -1,42 0 0 0 0 0 0 -7,6 -27,43 0 - 0 1 -1,08 0 0 0 0 0 0 13,01 -1,143 0 - 0 0 -0,01 0 0 0 0 0 0 0,17 0,143 1 - 0 0 0 1 0 -1,81 0 23,45 253,1 0 0 0 0,003 0 0 0 0 1 -1,64 0 235,7 23,17 0 0 0 0,028 0 0 0 0 0 -0,01 1 1,25 1,313 0 0 0 0,007 Дальнейший пересчет таблиц осуществляется аналогично. В табл. 9 представлен 8-й шаг нахождения оптимального плана решаемой задачи. Таблица 9 Шаг 8 Б 1 -1,73 -1,87 0 0 0 0 0 0 0 0 89,1 0 0,07 -0,08 0 0 0 0 0 0 1 0 0,56 0 -0,08 0,006 0 0 0 0 0 0 1 6,34 0 0 0 0,00002 -0,004 0 0,836 0 1 0 0 0 0 0 0 -0,004 0,0004 0 0,807 1 0 0 0 0 0 0 -0,605 -0,617 1 127,5 0 0 0 0 Нужно вводить в базис переменную (дополнение ), но уже в базисе, следовательно, конец алгоритма. Построен дополняющедопустимый базис. Решение задачи: Найдем сумму элементов векторов и : и . Решив задачи алгоритмом Лемке, получаем решение биматричной игры в смешанных стратегиях: - оптимальная смешанная стратегия магазина ; - оптимальная смешанная стратегия магазина . С учетом доминируемых стратегий оптимальные смешанные стратегии магазинов и равны соответственно: ; Таким образом, магазин A, применяя оптимальные смешанные стратегии, получит дополнительную среднюю прибыль при продаже кондитерских изделий не менее условных единиц, а магазин - не менее условных единиц. Выводы. В работе даны основные понятия по теории биматричных игр, приведен алгоритм их решения в смешанных стратегиях. Сформулирована и решена задача нахождения оптимального количества ассортимента кондитерских изделий двух магазинов при заказе товара у одного поставщика, при реализации которого нужно получить наибольшую прибыль для каждого магазина. Мнение экспертов послужило основным условием для составления биматричной игры, при решении которой были найдены оптимальные смешанные стратегии реализации товаров по алгоритму Лемке.

Об авторах

И. А Седых

Липецкий государственный технический университет

А. И Ворфоломеева

Липецкий государственный технический университет

Список литературы

Статистика

Просмотры

Аннотация - 39

PDF (Russian) - 7

Ссылки

• Ссылки не определены.