183753 (584785), страница 7
Текст из файла (страница 7)
1. Произошло или нет событие А?
2. Какое из событий А1, А2, ..., Аk произошло?
3. Какое значение приняла случайная величина Х?
4. Какую совокупность значений приняла система случайных величин Х1, Х2, ..., Хk?
Любая реализация случайного явления методом Монте-Карло строится из цепочки единичных жребиев, перемежающихся с обычными расчетами. Ими учитывается влияние исхода жребия на дальнейший ход событий (в частности на условия, в которых будет разыгран следующий жребий).
Единичный жребий может быть разыгран разными способами, но есть один стандартный механизм, с помощью которого можно осуществить любую разновидность жребия. А именно, для каждой из них достаточно уметь получать случайное число R, все значения которого от 0 до 1 равновероятны (т.е. обладают одинаковой плотностью вероятности).
Условно назовем величиной R "случайное число от 0 до 1". С помощью такого числа можно разыграть любой из четырех видов единичного жребия.
Тема 10. Методы теории массового обслуживания
1. Основные понятия теории массового обслуживания.
2. Постановка задачи теории очередей.
3. Подходы решения задач теории очередей.
Краткое содержание темы
Практическая деятельность человека тесно связана с различного рода системами массового обслуживания. В области экономики - это банковское обслуживание, пользование объектами торговли и услугами сферы обслуживания и многие другие виды экономической деятельности.
Любая система массового обслуживания может включать в себя следующие элементы:
Входящий поток требований или заявок на обслуживание. Этот элемент является основным. Изучение входящего потока требований и его описание необходимо при организации любой системы массового обслуживания.
Очередь. В тех случаях, когда поступающие в систему массового обслуживания требования не могут быть удовлетворены немедленно, возникает очередь. В такой ситуации интерес может представлять длина этой очереди, порядок, по которому ожидающие требования направляются на обслуживание (как говорят, дисциплина очереди), время ожидания.
В отдельных случаях систем массового обслуживания очереди не допускаются, т.е. требование, заставшее систему занятой, не обслуживается (получает отказ).
Обслуживающее устройство. Этот элемент присутствует в любой системе массового обслуживания. От характеристик и параметров, способов организации обслуживающего устройства зависят не только время, необходимое на обслуживание одного требования, но и длина очереди и время ожидания.
Выходящий поток обслуженных требований. Этот элемент может оказаться очень важным в тех случаях, когда выходящий поток обслуженных требований является входящим для другой системы массового обслуживания.
Как правило, число требований на входе системы массового обслуживания за какой-либо промежуток времени и время обслуживания одного требования являются случайными величинами. Функционирование системы массового обслуживания в таком случае представляет собой случайный процесс, и методы исследования таких систем используют имитационное моделирование. Однако понять сущность задач и методов теории массового обслуживания можно на примерах детерминированных моделей систем массового обслуживания и прежде всего моделей теории очередей.
Основными компонентами модели очереди являются:
-
описание входящего потока требований;
-
описание способа, которым выполняется обслуживание (т.е. описание дисциплины обслуживания);
-
описание дисциплины очереди (т.е. каким образом из очереди выбираются клиенты на обслуживание: “первый пришел - первый обслужен”, “последний пришел - первый обслужен”, “по указанным приоритетам” и т.п.).
При конструировании модели очереди первоочередной задачей является символическое представление основных компонент, после чего изучаются соотношения между ними.
Принципиальными характеристиками очереди являются:
-
длина очереди в различные моменты времени;
-
общая продолжительность нахождения требования в системе обслуживания (т.е. время, потраченное на ожидание в очереди, плюс собственное время обслуживания);
-
время, в течение которого обслуживающее устройство было свободно.
Основной целью исследования систем массового обслуживания является установление равновесия между допустимыми нагрузками обслуживающего устройства, ограниченной пропускной способностью системы и раздражением клиента, с одной стороны, и допустимой стоимостью обслуживающих точек, с другой.
Рассмотрим систему массового обслуживания, имеющую один источник требований, проходящих через единственное обслуживающее устройство. Пусть имеют место следующие предположения:
1. Требования поступают через одинаковые интервалы времени. Каждый интервал имеет длину a единиц.
2. Требования обслуживаются за одинаковые интервалы времени, каждый интервал имеет длину b единиц. При этом, как только закончится обслуживание одного требования, обслуживающее устройство готово к обслуживанию следующего требования.
3. Дисциплина очереди устанавливается по правилу “Первый пришел - первый обслуживается”. Другими словами, ожидающие требования образуют очередь, и, когда обслуживающее устройство освободится, на обслуживание поступает требование, имеющее большее время ожидания.
Определим длину очереди как общее число требований, находящихся на обслуживании и ожидающих в очереди. Представим сформулированную задачу в виде следующей схемы:
Поведение системы зависит от того, как связаны между собой величины a и b. Возможны три случая: 1) b > a; 2) b = a; 3) b < a. Рассмотрим каждый из этих случаев.
1) Случай b > a. Это значит, что скорость обслуживания 1/b меньше, чем скорость поступления требований 1/a, т.е. требования обслуживаются и покидают систему медленнее, чем прибывают. Следовательно, в этом случае будет образовываться очередь и она будет постоянно возрастать.
2) Случай b = a. Если в очереди нет требований, то первое поступившее требование сразу начнет обслуживаться. Его обслуживание закончится в тот же самый момент, в который поступит на обслуживание следующее требование. Следовательно, требований, ожидающих обслуживания, не будет.
Если же первоначально имеется очередь, то ее длина будет оставаться постоянной.
3) Случай b < a. Это значит, что скорость обслуживания больше, чем скорость поступления требований. Следовательно, какое бы ни было начальное число ожидающих обслуживания требований, длина очереди будет сокращаться до 1 или 0.
Пусть в начале процесса число требований в очереди r 2 (если первоначально есть только одно требование (r = 1), то оно будет обслужено прежде, чем поступят на обслуживание следующие требования, и очередь будет пустой).
В общем случае, пусть имеем r требований, стоящих в очереди перед началом обслуживания. Тогда число требований (N), поступивших после начала процесса обслуживания до тех пор, пока сохраняется очередь, можно определить по формуле:
, (10.1)
где обозначение [x] означает целую часть числа x. Действительно, очередь будет отсутствовать, если через обслуживающее устройство полностью пройдет N+r требований. Для этого потребуется (N+r)b единиц времени. За это время на обслуживание поступит N требований, так что к поступлению (N+1)-го требования обслуживающее устройство будет свободно и готово обслужить его сразу без всякой очереди. Но (N+1)-е требование поступит на обслуживание через (N+1)a единиц времени, при этом будет выполнено соотношение:
.
Отсюда,
. (10.2)
Докажем, что в полученном соотношении N больше правой части не более чем на 1. Действительно, первое стоящее в очереди требование будет уже обслужено, а первое вновь поступающее на обслуживание требование еще не появится в очереди (a > b). Поэтому справедливо соотношение:
aN 
(N+r-1)b или 
.
Таким образом, если к правой части соотношения добавим 1, то оно будет тождественно равно правой части соотношения . То есть прибавление 1 к правой части соотношения приводит его к соотношению – смысл неравенства меняется на противоположный. Это и требовалось доказать.
Очевидным является то, что N есть целое число. Следовательно, если от правой части в соотношении (10.2) взять целую часть и добавить к ней 1, то, исходя из предыдущих рассуждений, получим для вычисления N выражение (10.1).
Аналогичными рассуждениями и используя (10.1) можно найти, что для вычисления времени, которое необходимо для обслуживания всех ожидающих требований, справедлива формула:
. (10.3)
В теории очередей важной функцией является функция времени ожидания обслуживания. Обозначим ее через W(t). Определим W(t) как время, которое необходимо затратить на ожидание обслуживания требования, поступившего в момент времени t (считаем, что t = 0 соответствует началу процесса обслуживания).
Определим формулу для W(t). Легко видеть, что требование, поступившее на обслуживание в момент t T-b (величина T определяется с использованием формулы (10.3)), найдет систему обслуживания пустой или только что освободившейся. Такому требованию не придется стоять в очереди. Требование, поступившее в момент времени tT-b, найдет впереди себя 
требований, стоящих в очереди, причем первое из них в этот же момент поступит на обслуживающее устройство. Эта величина получается следующим образом:
(начальная (число требований, обслужен- (число поступ-
очередь) - ных к моменту времени t) + лений)
r - 
+ 
.
Таким образом, время ожидания W(t) для рассматриваемого требования может быть выражено формулой:
. (10.4)
Рассмотрим i-е требование в начальной очереди (0
Обобщая полученные результаты относительно функции W(t), получим для нее следующее выражение:
,
где i - номер i-го требования в начальной очереди; требования поступают в моменты времени a, 2a, ...; b = na (n = 1, 2, ...).
Тема 11. Управление запасами
1. Понятие задачи управления запасами.
2. Основная задача управления запасами.
3. Управление запасами в условиях производственных поставок.
4. Управление запасами в условиях дефицита.
Краткое содержание темы
Класс задач по управлению запасами является достаточно специфичным как по разнообразию постановки задач, так и по методам их решения. Здесь успешно применяются методы линейного и динамического программирования, методы теории массового обслуживания и многие другие. В данном разделе рассматриваются простые методы математического анализа для решения задач управления запасами.
Предприятия в процессе своей деятельности делают различные запасы. Запасы - это совокупность предметов (товаров), представляющих собой временно неиспользуемые экономические ресурсы.
Причины создания запасов могут быть различными.
Если в нужный момент производства необходимые материалы или товары не поступают от поставщиков и их нет на складе в запасе (т.е. имеет место дефицит), процесс производства может задержаться или совсем остановиться. Однако, если запасы достаточно велики, то возрастает плата за них и за их хранение.
Таким образом, возникает задача управления запасами, т.е. необходимо выбрать некоторое компромиссное решение по созданию запасов или выработать стратегию управления запасами.
Основные типы принимаемых решений по управлению запасами следующие:
1. Определить какое, количество товара должно быть в запасе.
2. Определить, в какое время необходимо производить пополнение запасов.
В настоящее время существует множество подходов к решению подобного рода задач.
Рассмотрим три простейшие математические модели, включающие:
а) основную модель управления запасами - определение оптимального размера партии;
б) модель производственных поставок;
в) модель, учитывающую штрафы.
Итак, предмет изучения - количество запаса на складе и время t, для которого рассматривается этот запас, т.е. исследуется функция = f(t), соответствующая величине запаса в момент времени t. График такой функции называется графиком изменения запаса.
По поводу изменения функции запасов сделаем следующие предположения:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
