Модель очереди ожидания и линейное программирование

Введение

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

Очередь ожидания может быть смоделирована как случайный процесс, в котором случайная величина определяется как количество транзакций в системе в данный момент времени; набор значений, которые может принимать эта переменная, равен {0, 1, 2,.,,, N \, и каждому из них соответствует вероятность возникновения.

задача

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

Структура системы очереди

Одноканальная очередь ожидания

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

Модель очереди ожидания и линейное программирование

Распределение прибывших

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

/ = Среднее или среднее количество вхождений за интервал

е = 2,17828

X = количество повторов в интервале

Модель очереди ожидания и линейное программирование

Время обслуживания - это время, которое клиент тратит на установку после запуска службы.

Экспоненциальное распределение вероятностей можно использовать для определения вероятности того, что время обслуживания меньше или равно времени t.

е = 2,17828

μ = среднее количество единиц, которые могут быть обслужены за период

Модель очереди ожидания и линейное программирование

Дисциплина очереди

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

Первый пришел первый обслужен

Последний вошел, первый вышел

Внимание прежде всего наивысший приоритет

Работа в устойчивом состоянии

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

Одноканальные модели линии ожидания с пуассоновскими поступлениями и экспоненциальным временем обслуживания

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

Назначение формул - показать, как может быть предоставлена информация об эксплуатационных характеристиках очереди.

Модель очереди ожидания и линейное программирование

Как можно улучшить работу очереди?

Рабочие характеристики для системы со средней скоростью обслуживания увеличены до μ = 1,25 клиента в минуту.

Модель очереди ожидания и линейное программирование

Экономический анализ очередей

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

Cw = стоимость ожидания за период для каждой единицы

L = среднее количество единиц в системе

Cs = стоимость обслуживания за период для каждого канала

K = количество каналов

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

Модель очереди ожидания и линейное программирование

Линейное программирование

Введение

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

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

Для систем с большим количеством переменных процедура не так проста, и они решаются вызовом

Симплексный метод (разработан американским математиком Дж. Б. Данцигом в 1951 г.).

Недавно (1984 г.) индийский математик, основанный в Соединенных Штатах, Наренда Кармаркар, нашел алгоритм, названный алгоритмом Кармаркара, который в некоторых случаях быстрее симплексного метода. Проблемы этого типа, в которые вмешивается большое количество переменных, реализуются на компьютерах.

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

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

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

Аналогичным образом линейное программирование широко используется в микроэкономике и бизнес-администрировании, чтобы максимизировать доходы или минимизировать затраты производственной системы. Некоторые примеры: смешивание продуктов питания, управление запасами, управление портфелем и финансами, распределение человеческих и машинных ресурсов, планирование рекламных кампаний и т. Д.

Другие являются:

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

Шаги по решению задачи линейного программирования

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

Пример линейного программирования

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

У производителя есть 750 м хлопчатобумажной ткани и 1000 м полиэфирной ткани. Для каждой штаны требуется 1 м хлопка и 2 м полиэстера. На каждую куртку понадобится 1,5 м хлопка и 1 м полиэстера.

Стоимость брюк - 50 евро, пиджака - 40 евро.

Какое количество брюк и курток производитель должен поставить в магазины, чтобы они достигли максимальных продаж?

1 Выбор неизвестных.

x = количество штанов

y = количество курток

2 Целевая функция.

f (x, y) = 50x + 40y