4.7. Приведение матричной игры к злп

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

Обозначим через и оптимальные смешенные стратегии игроков А и В. Стратегия игрока А гарантирует ему выигрыш не меньше v, все зависимости от выбора стратегии игроком В. Это можно записать так:

Причем , ().

Аналогично стратегия игрока В гарантирует ему проигрыш не больше v, независимо от выбора стратегии игроком А.

Причем , ().

Разделим обе части неравенств на положительное число v (обе системы) и произведем замену: ,(,). Получим:

Причем , ().

Причем , ().

Целевая функция для первой системы будет иметь вид:

.

Для второй системы:

.

Решив пару двойственных задач, можно определить выигрыш:

.

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

1. Составляют пару двойственных задач линейного программирования, эквивалентных данной матричной игре.

2. Определяют оптимальные планы пары двойственных задач.

3. Используя соотношение между планами двойственных задач и оптимальными стратегиями и ценой игры.

Пример: Найти решение игры, определяемой матрицей:

Решение.

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

Прямая задача.

при

Двойственная задача:

при

Решив задачи, получим: и. Следовательно цена игры:, а оптимальные стратегии игроков:и.

4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания

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

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

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

Системы массового значения делятся на типы по ряду признаков.

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

Классификация 1.1. Системы массового обслуживания с очередью делятся на разные виды, в зависимости от того, как организована очередь. Ограничения могут быть на длину очереди, на время ожидания ("системы массового обслуживания с нетерпеливыми заявками"). При анализе систем должна также учитываться и "дисциплина обслуживания": заявки могут обслуживаться в порядке поступления (первой пришла, первой обслуживается), либо в случайном порядке. Нередко встречается, так называемое обслуживание с приоритетом – некоторые заявки обслуживаются вне очереди. Приоритет может быть относительным (когда начатое обслуживание доводится до конца, а заявка с более высоким авторитетом имеет лишь право на лучшее место в очереди) и абсолютным (заявка с более высоким приоритетом вытесняет заявку с меньшим).

Классификация 2. Системы с многофазовым обслуживанием. Это системы, где обслуживание состоит из нескольких фаз.

Классификация 3. Открытие и закрытые системы массового обслуживания. В открытой системы массового обслуживания характеристики потока заявок не зависят ото того, в каком состоянии сама система. В замкнутой системе – зависят.

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