Задачи массового обслуживания

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

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

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

При построении функции распределения вероятностей для длины очереди необходимо учесть ряд особенностей, присущих процессу образования очередей:

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

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

3. Последовательность обслуживания – дисциплина очереди. Дисциплина может определяться разными правилами обслуживания:

– «первым пришел – первым обслуживаешься»,

– «последним пришел – первым обслуживаешься»,

– случайный отбор заявок,

– отбор по критерию приоритетности.

4. Характер обслуживания и его длительность. Это – выход системы (обслуженные клиенты, загруженные автомашины и т.п.).

При решении задач, связанных с очередями, возможны две ситуации:

а) число заказов слишком велико; имеет место большое время ожидания (недостаточный объем обслуживающего оборудования);

б) поступает недостаточное число заказов; имеет место простой оборудования (избыток оборудования).

Необходимо найти оптимальное соотношение между потерями, вызванными простоем оборудования, и потерями из-за ожидания.

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

Модель 1.

Обозначим Р_n(t) – вероятность образования очереди из n заказов (включая и находящийся в обслуживании) к моменту времени t, l – средняя скорость появления заказов, m – средняя скорость обслуживания. Рассмотрим простейший поток заказов, характеризующийся тем, что для элементарного (малого) отрезка времени вероятности поступления (или обслуживания) одного заказа пропорциональны длине этого отрезка, а вероятности появления или обслуживания более одного заказа предполагаются пренебрежимо малыми. Тогда в частном случае, когда Р_n(t) не зависит от времени, задача решается легко. Этот случай называют предельным стационарным режимом, который существует при t ® ¥, когда l < m.

Предельная вероятность Р_n имеет четкий смысл: она показывает среднее относительное время наличия очереди длиной n. Например, если Р₀ = 1/2, то это означает, что в среднем половину времени очереди нет. Предельные вероятности постоянны:

Р_n = hⁿ(1 – h). (1)

Величина h = l /m называется интенсивностью потока заявок или интенсивностью нагрузки станции. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Найдем n – среднюю длину очереди.

n = l/(m – l ). (2)

Найдем t_w – среднее время ожидания обслуживания. Если средняя скорость обслуживания равна m, то среднее время обслуживания t_s=1/m, и, при средней скорости поступления заказов l, справедливо

t_w = 1/(m – l ) – 1/m. (3)

Пример 1. Пусть автомобили прибывают на моечную станцию со средней интенсивностью l = 5 автомобилей в час. Продолжительность выполнения работ в среднем равна 10 мин., т.е. m =60/10=6 а/ч. Поскольку h = l /m = 5/6 < 1, система может функционировать в стационарном режиме. Найдем среднее время ожидания обслуживания t_w = 1/(m –l)–1/m =1/(6–5)–1/6 =5/6 (50 мин), тогда среднее число автомобилей, ожидающих обслуживания, равно n_w=lt_w =25/6=4.17 ≈ 4. Если подготовить стоянку для ожидающих автомобилей на 4 места, то потеряем клиента, прибывшего сверх среднего количества. Поэтому для «разумного» обеспечения местами прибывающих на мойку автомобилей зададимся целью обеспечить одновременно стоянку, например, 80% клиентов. Это эквивалентно выполнению условия

Р₀ + Р₁ + Р₂ + …+ Р_w ≥ 0.8,

где w – подлежащее определению число стоянок. Используя (1)

(1 – h) + h(1 – h) +…+ h^w(1 – h) ≥ 0.8.

учитывая, что

(1 – h) + h(1 – h) +…+ h^w(1 – h) =(1 – h)(1 + h +…+ h^w) = 1 –h^w+1,

получаем h^w+1 ≤ 0.2 и окончательно w ≥ ln(0.2)/ln(5/6) – 1 = 7.8 ≈ 8.

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

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

Р₀ =1 – h ≈ 0.17.

Вероятности того, что на станции обслуживается ровно один автомобиль (или два – один обслуживается , второй ждет) равны соответственно:

Р₁ =h(1 – h) ≈ 0.139,

Р₂ =h ²(1 – h) ≈ 0.116.

Модель 2.

Рассмотрим случай ограниченной очереди, когда при наличии в системе N требований ни одна из дополнительных заявок на обслуживание не принимается либо сам клиент отказывается присоединиться к очереди из-за отсутствия места в блоке ожидания. Формулы для параметров такой системы:

Р_n = hⁿ(1 – h)/(1 – h^N+1), n ≤ N (4)

Р_n = 0, n > N.

Следует отметить, что в этой модели параметр h= l/m не обязательно должен быть меньше единицы, поскольку число допускаемых в систему требований ограничено, и для h = 1 Р_n =1/(N +1).

Выражение для среднего числа находящихся в системе заявок принимает следующий вид

n = þh(1 – (N+1)h^N + Nh^N+1 )/(1 – h)/(1 – h^N+1), для h ≠1, (5)

ü N/2, для h=1.

Поскольку вероятность того, что заказ не имеет возможности попасть в очередь, равняется Р_N , доля заказов, поступающих в систему, равняется 1 – Р_N. Отсюда характеристики системы имеют вид:

Для n_w – среднее число заказов, ожидающих обслуживания:

n_w = n – l(1 – Р_N )/m, (6)

для t_w – среднее время ожидания обслуживания:

t_w = n_w/l /(1 – Р_N ), (7)

Пример 2. Пусть в условиях примера 1 моечная станция располагает пятью местами для стоянки ожидающих автомобилей.

В данном примере N =5+1=6, h=5/6, а

Р_N =(5/6)⁶(1 – 5/6)/(1 – (5/6) ⁷) = 0.0774, N = 6.

Отсюда следует, что частота случаев, когда автомобиль не попадает на моечную станцию равняется lР_N =5*0.0774=0.387 автомобиля в час, т.е. при 12-часовом режиме работы моечная станция теряет за день 4,6 автомобиля. Применяя (5) – (7), получаем

n = (5/6)(1 – 7(5/6)⁶ + 6(5/6)⁷)/(1 – 5/6)/(1 – (5/6)⁷)= 2.29,

n_w =2.29 – 5(1 – 0.0774)/6=1.52,

t_w =1.52/5 /(1 – 0.0774)=0.33 часа( 20 мин.).

Таким образом, при введении ограничения на количество мест для стоянки (N =6), среднее время ожидания обслуживания сократилось на полчаса. Это было достигнуто за счет «потери» в среднем 4.6 автомобиля в день из-за недостаточности мест для стоянки. Вычислим вероятность того, что в системе обслуживаются 0,1 или 2 автомобиля:

Р₀ =(1 – 5/6)/(1 – (5/6) ⁷) = 0.231,

Р₁ =(5/6)(1 – 5/6)/(1 – (5/6) ⁷) = 0.193,

Р₂ =(5/6)²(1 – 5/6)/(1 – (5/6) ⁷) = 0.160.

Модель 3.

Пусть параллельно могут обслуживаться не более s клиентов. Такие модели называются многоканальными (s – число каналов обслуживания). Здесь l_n =l (n³0), m_n = nm при n £s , m_n = sm при n ³ s.

Для данной модели расчетные формулы (Эрланга) имеют вид:

Р_n = Р₀(l/m)ⁿ / n! (n £ s), (8)

Р_n = Р₀(l/m)ⁿ / s!/s^n-s (n ³ s), (9)

Р₀ = 1/(å^s-1(l/m)ⁿ/n! + (l/m)^s/s!/(1 –l/ms)). (10)

ⁿ⁼⁰

Для n_w – среднее число клиентов, ожидающих обслуживания:

n_w = Р₀(l/m)^s+1/(s–1)!/(s–l/m)², (11)

для общего числа клиентов, находящихся в системе, имеем

n = n_w + l/m, (12)

для t_w – среднее время ожидания обслуживания:

t_w = n_w/l. (13)

Вероятность обязательного пребывания в очереди равна вероятности занятости всех каналов обслуживания. Обозначим ее через W. Тогда

W= Р₀(l/m)^s/(s–1)!/(s–l/m). (14)

Известный интерес представляет вероятность того, что суммарное время обслуживания и его ожидания превзойдет заданную величину t. Обозначим эту вероятность через Р(>t).

Р(>t) = e^–mt(1 + (W/s)(1 – e^{–mst(1–l/ms–1/s)})/(1–l/ms–1/s)). (15)

Вычисления в соответствии с данной моделью могут оказаться весьма громоздкими, тогда используют приближенные методы. Например, при l/m « 1 можно принять Р₀»1 – l/m,

n_w »(l/m)^s+1/s²,

тогда как для значений l/m , близких к 1,

Р₀ » (s – l/m)(s – 1)! /s^s и n_w » (l/m)/(s – l/m).

Пример 3. Пусть на нашей любимой моечной станции только 3 площадки для мойки, а мест для ожидания неограниченное число. Пусть как и прежде l = 5 и m =6. Имеем l/m =0.833, s =3 и

Р₀ = 1/(0.833⁰/0!+0.833¹/1!+0.833²/2!+ 0.833³ /(3!(1 –0.833/3))) = 0.432,

n_w = 0.432*0.833⁴/2!/(3–0.833)² = 0.022,

t_w =0.022/5 = 0.0044 часа.(16 сек.)

Таким образом, при данных условиях 43.2% времени станция простаивает, среднее время ожидания обслуживания составляет 16 сек. С точки зрения клиента отлично, но простой оборудования влетает в копеечку. Кроме того, имеем:

Р₁ =0.40, Р₂ =0.15, Р₃ =0.04.

Вычислим параметры системы при 2 моечных площадках.

Р₀ = 1/(0.833⁰/0!+0.833¹/1!+ 0.833² /(2!(1 –0.833/2))) = 0.412,

n_w = 0.412*0.833³/1!/(2–0.833)² = 0.17,

t_w = 0.17/5 = 0.034 часа.(2 мин.)

Простой составляет 41.2% времени, среднее время ожидания 2 мин.

Сравним с результатами примера 1, где при наличии только одной моечной площадки простой составлял 17%, а среднее время ожидания 50 мин. В силу малого времени ожидания параметры W и Р(>t) в данном примере интереса не представляют.

Р₁ =0.34, Р₂ =0.14, Р₃ =0.06.

Модель 4.

Рассмотрим теперь модель, которая отличается от предыдущей только тем, что число мест для ожидания обслуживания ограничено величиной k. Здесь l_n =l при 0≤n < k+s и

l_n =0 при n ³ k+s; m_n = nm при n £ s , m_n = sm при s ≤ n ≤ s+k.

Формулы для характеристик модели имеют вид:

Р_n = Р₀(l/m)ⁿ / n! (n £ s), (16)

Р_n = Р₀(l/m)ⁿ / s!/s^n-s (s ≤ n ≤ s+k ), (17)

Р₀=1/(å^s-1(l/m)ⁿ/n! + (l/m)^s(1–(l/ms)^k+1)/s!/ (1–l/ms)), l/m≠s, (18)

ⁿ⁼⁰

Р₀=1/(å^s-1(l/m)ⁿ/n! + (l/m)^s(k+1)/s!), l/m=s, (19)

ⁿ⁼⁰

Для n_w – среднее число клиентов, ожидающих обслуживания:

n_w=Р₀(l/m)^s+1(1–(l/ms)^k–k(l/ms)^k(1–l/ms))/(s–1)!/(s–l/m)², l/m≠s, (20)

n_w=Р₀(l/m)^sk(k+1)/(2s!), l/m=s, (21)

для t_w – среднее время ожидания обслуживания:

t_w =n_w/l/(1– Р_k+s). (22)

Пример 4. Пусть в дополнение к последнему примеру наша моечная станция располагает двумя местами для ожидания обслуживания (k=2 и s=2). Тогда получим:

Р₀=1/(0.833⁰/0!+0.833/1!+0.833²(1–(0.833/2)²⁺¹)/2!/(1–0.833/2)) = 0.423,

n_w=0.423*0.833³(1–(0.833/2)²–2(0.833/2)²(1–0.833/2))/1!/(2–0.833)²=0.25,

и t_w =0.25/5/(1– Р₂₊₂)= 0.25/5/(1 – 0.423*0.833⁴ /2!/2²)=0.05 час.

Для двух каналов обслуживания входной поток заказов очень слабый, изменим его, пусть l=12, тогда l/m=2= s и мы имеем

Р₀=1/(2⁰/0! +2/1!+2²(2+1)/2!)= 0.111,

n_w=0.111*2²*2*3/(2*2!)=0.67, t_w=0.67/12/(1–Р₂₊₂)=0.67/12/(1–0.111*2⁴/2!/2²)=0.07 ч.

При таком входном потоке простой оборудования составляет 11.1%, а среднее время ожидания обслуживания 0.07*60= 4.3 мин.

Рассмотрим более крупный пример, на котором нагляднее иллюстрируются формулы моделей 3 и 4.

Пример 5.

Вариант 1. Имеем моечную станцию с 4 рабочими площадками для мойки и с неограниченным количеством мест для ожидания. Пусть l=20 автомобилей в час, время обслуживания одного автомобиля 11.5 мин. (m=60/11.5=5.217), тогда l/m=20/5.217=3.83 и s=4. Используем 10.21:

Р₀ = 1/(3.83⁰/0!+3.83/1!+3.83²/2!+3.83³/3!+3.83⁴/4!/(1–3.83/4))=0.0042.

Из (12)–(13) получаем среднее время ожидания :

t_w =0.0042*3.83⁵/3!/(4–3.83)²/20= 1 час.

Вероятность обязательного пребывания в очереди(14):

W= 0.0042*3.83⁴/3!/(4–3.83)=0.886.

Найдем вероятность того, что суммарное время обслуживания и ожидания превзойдет величину t=0.5 (30 мин.). Применим (15):

Р(>0.5) =e^–5.217/2(1+0.886/4)(1–e^{–5.217*4/2(1–3.83/4–1/4)})/(1–3.83/4–1/4))=0.7.

Таким образом, 88.6% клиентов обязательно проходят через очередь, причем 70% находятся в ней более получаса (правда, включая время обслуживания).

Вариант 2. Добавим к варианту 1 ограничение на количество мест для ожидания. Пусть k=16, тогда из (18) находим сначала

Р₀=1/(1+3.83+3.83²/2!+3.83³/3!+3.83⁴(1–(3.83/4)¹⁷)/4!/(1–3.83/4))=0.00759

и, следовательно, из (10.30) получаем

n_w=0.00759*3.83⁵(1–(3.83/4)¹⁶–16(3.83/4)¹⁶(1–3.83/4))/3!/(4–3.83)²=5.82.

Поскольку Р₂₀=3.83²⁰*0.00759/4!/4¹⁶=0.03397, используя (22), имеем для среднего времени ожидания обслуживания:

t_w =5.82/20/(1–0.03397) =0.301 часа.(18 мин.)

Сравнивая варианты 1 и 2, видим, что при ограничении мест для ожидания, продолжительность ожидания сокращается более чем в три раза, причем это достигается ценой потери около 3.4% потенциальных клиентов (Р₂₀=0.03397).

Прикладные аспекты теории массового обслуживания.

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

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

Для определения оптимального значения μ построим стоимостную модель на основе одноканальных моделей (1 – 2).

Пусть с₁ – затраты на обслуживание одного заказа, отнесенные к единице времени, с₂ – обусловленные вынужденным ожиданием экономические потери в единицу времени в расчете на один заказ, тогда С(μ) =с₁μ + с₂n – суммарные затраты в единицу времени, минимизация которых даст нам оптимальное значение μ*.

Например, для модели 1, применяя (2), имеем

С(μ) = с₁μ + с₂λ/(μ – λ), откуда, приравнивая к нулю первую производную, получаем

μ* = λ + √с₂λ/ с₁.

В случае модели 2 величина N рассматривается тоже как переменная, оптимальное значение которой (вместе с μ) определяется путем минимизации С(μ,N) = с₁μ + с₂n+ с₃N + с₄ λP_N, где с₃– затраты на оборудование одного места в блоке ожидания, с₄ –экономические потери, связанные с потерей потенциального клиента (приведены к единице времени). Подставляя (4)–(7), получим довольно сложное уравнение, для решения которого необходимо прибегать к соответствующим численным методам.

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

С(s) = с₁s + с₂n(s),

где с₁ – отнесенные к единице времени затраты на функционирование одного обслуживающего канала, с₂ – как и выше, затраты, связанные с ожиданием. Тогда оптимальное значение s* находится из условия

n(s*) – n(s*+1) ≤ с₁/с₂ ≤ n(s*–1) – n(s*).

Пример 6. Пусть автомашины поступают на мойку в соответствии с пуассоновским распределением вероятностей со средним числом λ=17.5 автомобилей в час. Каждое оборудованное моечное место способно удовлетворить в среднем μ=10 автомобилей в час. Затраты, связанные с добавлением одного моечного места, оцениваются в с₁=6 руб. в час. Пусть потери из-за ожидания составляют с₂=30 руб. в час. Вычислим по формулам (11) и (12) Р₀ и n для разных значений s и результаты поместим в таблицу 1.

Таблица 1

s	Р0	n	n(s*–1) – n(s*)
		∞	–
	0.067	5.745	∞
	0.156	0.468	5.28
	0.170	0.092	0.376
	0.173	0.019	0.073
	0.174	0.004	0.015

Следует обратить внимание на то, что n(1)= ∞, так как λ > μ.

Поскольку с₁/с₂ = 6/30 = 0.2, имеем

n(4) – n(5) = 0.073 ≤ 0.2 ≤ 0.375 = n(3) – n(4).

Следовательно, оптимальное количество моечных мест s*=4.

Можно учесть еще потери, связанные с простоями моечного оборудования, для этого необходимо по формуле (19) найти вероятности того, что обслуживаются ровно n (n=0,1,2,…< s) автомашин.

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

Согласно методу Монте–Карло перебирают (с помощью ЭВМ) все возможные состояния системы с различной интенсивностью и разными законами распределения вероятностей входного и выходного потоков. В результате многократного искусственного воссоздания работы системы рассчитывают характеристики обслуживания, как если бы они были получены при наблюдении над реальным потоком клиентов. Для сложных систем обслуживания метод статистического моделирования оказывается проще аналитического.

Состязательные задачи

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

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

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

Игра с нулевой суммой – это такая игра, в которой сумма выигрышей участников равна нулю.

Стратегия – это установленный игроком метод выбора решения при каждом ходе в течение игры.

Будем рассматривать конечную игру, то есть игру с конечным числом ходов и конечным числом стратегий.

Платежная матрица – это таблица, которая определяет, какие платежи должны быть сделаны после завершения игры.

Рассмотрим игру двух лиц с нулевой суммой.

Обозначим игроков А и В, и пусть А имеет m вариантов хода, а В имеет n вариантов. Пусть игра заключается в том, что игроки делают по одному ходу и А выигрывает у В сумму a_ij, если А выбрал вариант i (i=1,2,…,m), а В выбрал вариант j (j=1,2,…,n). Тогда платежная матрица для игрока А имеет вид:

a₁₁ a₁₂ …a_1n

A = [a_ij ] = a₂₁ a₂₂ …a_2n

………..

a_m1 a_m2…a_mn

Платежную матрицу для игрока В нет необходимости рассматривать самостоятельно, так как В = – А.

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

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

Рассмотрим применение данного критерия на примере. –2 –4

Пусть задана платежная матрица, определяющая выигрыш игрока А. А= –1 3

Если игрок А выбирает первую стратегию, его выигрыш будет не меньше 1 2

miní–2, –4ý=–4 независимо от поведения игрока В. При выборе игроком А второй стратегии гарантированный выигрыш будет равен miní–1,3ý=–1, и, наконец, если он выберет третью стратегию, гарантированный выигрыш будет равен miní1,2ý= 1. Тогда игрок А, выбирая третью стратегию, максимизирует свой минимальный выигрыш. Его значение равно mахí–4, –1,1ý=1. Выбранная игроком А стратегия называется максиминной стратегией, а соответствующее ей значение выигрыша – максиминным (нижним) значением игры.

Игрок В хочет минимизировать свой проигрыш. Выбрав первую стратегию, он может проиграть не более чем mахí–2, –1,1ý=1 независимо от выбора своего противника. При второй стратегии проигрыш составит не более mахí–4,3,2ý=3. Игрок В выберет тогда первую стратегию, для которой проигрыш составит miní1,3ý=1. Эта стратегия называется минимаксной, а соответствующее ей значение проигрыша игрока В – минимаксным (верхним) значением игры.

В математических обозначениях «максимин для А» выражается mах_i min_j a_ij, аналогично, «минимакс для В» есть min_j mах_i a_ij, причем, очевидно, имеет место mах_i min_j a_ij £ min_j mах_i a_ij. В случае, когда имеет место равенство, т.е. mах_i min_j a_ij = min_j mах_i a_ij =а_i0j0, соответствующие чистые стратегии (i₀ для игрока А и j₀ для В) будут оптимальными, а про игру говорят, что она имеет седловую точку. Тогда а_i0j0 является значением игры. Легко видеть, что игра имеет седловую точку тогда и только тогда, когда в платежной матрице имеется элемент а_i0j0, наименьший для всех элементов своей строки i₀ и наибольший для всех элементов своего столбца j₀.

При отсутствии седловой точки невозможно получить оптимальное решение, пользуясь чистыми стратегиями. В этом случае для получения решения игры будем пользоваться смешанными стратегиями, которые заключаются в применении чистых стратегий с некоторыми частотами (вероятностями). Пусть р₁,р₂,..,р_m и q₁,q₂,..,q_n – наборы вероятностей, с которыми игроки А и В соответственно выбирают свои чистые стратегии. Естественно

å_i^m₌₁р_i =å_jⁿ₌₁q_j =1, р_i , q_j ≥0 для всех i и j.

Если игрок А выбирает свои чистые стратегии с вероятностями р_i, то его ожидаемый выигрыш должен составить

a₁₁р₁+ a₂₁р₂+…+ a_m1р_m ,

при ответном выборе игроком В своей первой чистой стратегии,

a₁₂р₁+ a₂₂р₂+…+ a_m2р_m ,

при ответном выборе игроком В своей второй чистой стратегии, и т.д.

a_1nр₁+ a_2nр₂+…+ a_mnр_m

при выборе игроком В n-й чистой стратегии. С другой стороны, если игрок В выбирает свои чистые стратегии с вероятностями q_j, то его ожидаемый проигрыш должен составить

a₁₁q₁+ a₁₂q₂+…+ a_1nq_n ,

если игрок A выберет свою первую чистую стратегию,

a₂₁q₁+ a₂₂q₂+…+ a_2nq_n,

если игрок A выберет свою вторую чистую стратегию и

a_m1q₁+ a_m2q₂+…+ a_mnq_n,

при выборе игроком A m-й чистой стратегии.

Если игрок А выбрал стратегию (р₁,р₂,..,р_m) и при этом игрок В выбрал (q₁,q₂,..,q_n), то ожидаемый выигрыш игрока А (он же проигрыш игрока В) составит

g=å_i^m₌₁å_jⁿ₌₁a_ijр_iq_j.

Тогда игрок А при выборе р_i стремится максимизировать свой наименьший ожидаемый выигрыш по столбцам, тогда как игрок В выбирает q_j с целью минимизировать наибольший ожидаемый проигрыш по строкам. Справедлива теорема фон.Неймана, которую мы примем без доказательств, утверждающая, что для любой конечной игры существуют оптимальные стратегии игроков А (р₁*,р₂*,..,р_m*) и В (q₁*,q₂*,..,q_n*), при этом максимум наименьшего ожидаемого выигрыша игрока А совпадает с минимумом наибольшего ожидаемого проигрыша игрока В (обозначим это значение игры через g). Таким образом, математическую модель конечной игры для игрока А можно представить в следующем виде:

Найти такие р_i ≥0, для которых выполняются соотношения

р₁+р₂+…+р_m=1,

a₁₁р₁+ a₂₁р₂+…+ a_m1р_m ≥ g,

a₁₂р₁+ a₂₂р₂+…+ a_m2р_m ≥ g, (1)

……………………. ……

a_1nр₁+ a_2nр₂+…+ a_mnр_m≥ g,

и функция Z=g принимает максимальное значение.

Упростим полученную задачу, разделив все ограничения (1) на значение игры g > 0 и положив х_i =р_i /g для всех i. (Проведение аналогичных рассуждений для случая g ≤ 0 предоставляется читателю). В силу того, что

max g =min 1/g = min(р₁/g+р₂/g+…+р_m/g) = min(x₁+x₂+…+x_m)

задача принимает вид

минимизировать Z= x₁+x₂+…+x_m

при ограничениях

a₁₁x₁+ a₂₁x₂+…+ a_m1x_m ≥ 1,

a₁₂x₁+ a₂₂x₂+…+ a_m2x_m ≥ 1, (2)

……………………. ……

a_1nx₁+ a_2nx₂+…+ a_mnx_m≥ 1,

x₁, x₂,…,x_m ≥ 0.

Мы получили задачу линейного программирования. Решая ее (например, симплекс–методом), находим оптимальное решение x₁*, x₂*,…,x_m*, откуда, разделив на Z*= x₁*+x₂*+…+x_m*, получаем оптимальную стратегию для игрока А (р₁*,р₂*,..,р_m*), которая заключается в применении i-й чистой стратегии с частотой р_i*.

Для игрока В получаем задачу линейного программирования:

максимизировать W= y₁+y₂+…+y_n

при ограничениях

a₁₁y₁+ a₁₂y₂+…+ a_1ny_n ≤ 1,

a₂₁y₁+ a₂₂y₂+…+ a_2ny_n ≤ 1, (3)

……………………. ……

a_m1y₁+ a_m2y₂+…+ a_mny_n≤ 1,

y₁, y₂,…,y_n ≥ 0,

где W=1/g, y_j = q_j /g, j=1,2,…,n.

Отметим, что задача (3) является двойственной к задаче (2). Тем самым оптимальное решение одной из задач автоматически дает оптимальное решение другой задачи.

Проиллюстрируем использование рассмотренных методов при описании и решении некоторых конкурентных задач.

Пример 1. Пусть ежедневный спрос на булочки в магазине задается следующим распределением вероятностей:

спрос
Вероятность спроса	0.20	0.25	0.30	0.15	0.10

Магазин закупает булочки по 2.5 руб. и продает по 4.9 руб. за штуку. Если булочка не продана в тот же день, то она реализовывается по 1.5 руб. Какое наибольшее число булочек необходимо заказывать ежедневно, если величина заказа может принимать одно из возможных значений спроса?

Прибыль от продажи «свежей» булочки составляет 4.9–2.5=2.4 руб.

Потеря от продажи «черствой» составляет 2.5–1.5=1 руб.

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

Заказ маг-на	Возможный ежедневный спрос	Ожид. приб.
	240-50
	240-100	360-50				369.5
	240-150	360-100	480-50
	240-200	360-150	480-100	600-50

На пересечении строки с некоторым объемом заказа и столбца с возможным спросом находится элемент a_ij – ожидаемая прибыль магазина в этой ситуации. В последней колонке вычислена ожидаемая (средняя) прибыль в случае распределения вероятностей спроса в соответствии с условиями примера. Например, для третьей строки имеем 140*0.2+310*0.25+480*0.3+480*0.15+480*0.1=369.5. Кстати, выбор этой стратегии (ежедневный заказ – 200 булочек) и будет оптимальным, т.к. обеспечивает максимальную прибыль.

Пример 2. Рассмотрим схожую с предыдущей задачу управления запасами. Пусть спрос на некоторое изделие описывается следующим рядом распределения вероятностей:

Спрос
Вероятность спроса	0.10	0.15	0.40	0.15	0.10	0.10

Определить уровень запасов, при котором вероятность полного истощения запасов не превышает 0.45. Определ<