Алгоритм метода потенциалов. 5 страница

Значит, функция монотонно возрастает от 0 до 1. И любая прямая , где , пересекает график функции в единственной точке, абсциссу которой мы и принимаем за . Таким образом, уравнение (30) всегда имеет одно и только одно решение.

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

принадлежит интервалу , и наоборот. Значит: . Т.к. равномерно распределена в , то

, а это как раз и означает, что случайная величина , являющаяся корнем уравнения (30) имеет плотность вероятностей .

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

Вычислим математическое ожидание:

После интегрирования по частям, получим:

.

Параметр есть интенсивность потока заявок.

Формулу для розыгрыша получим из уравнения (30), которое в данном случае запишется так: .

Вычислив интеграл, стоящий слева, получим соотношение . Отсюда, выражая , получим:

Т.к. величина распределена также как и , следовательно, формулу (33) можно записать в виде:

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

Начальные параметры:

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

Мной были проведены контрольные замеры времени обработки заявок, поступающих в данную СМО. Чтобы приступить к исследованию, необходимо установить по этим замерам закон распределения времени обработки заявок.

Таблица 6.1 – Группировка заявок по времени обработки

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

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

1) Найти по заданному эмпирическому распределению выборочную среднюю . Для этого, каждый i – й интервал заменяем его серединой и составляем последовательность равноотстоящих вариант и соответствующих им частот.

2) Принять в качестве оценки параметра λ показательного распределения величину, обратную выборочной средней:

3) Найти вероятности попадания X в частичные интервалы по формуле:

4) Вычислить теоретические частоты:

,

где - объем выборки

5) Сравнить эмпирические и теоретические частоты с помощью критерия Пирсона, приняв число степеней свободы , где S – число интервалов первоначальной выборки.

Таблица 6.2 – Группировка заявок по времени обработки с усредненным временным интервалом

Найдем выборочную среднюю:

2) Примем в качестве оценки параметра λ экспоненциального распределения величину, равную . Тогда:

()

3) Найдем вероятности попадания X в каждый из интервалов по формуле:

Для первого интервала:

Для второго интервала:

Для третьего интервала:

Для четвертого интервала:

Для пятого интервала:

Для шестого интервала:

Для седьмого интервала:

Для восьмого интервала:

4) Вычислим теоретические частоты:

Результаты вычислений заносим в таблицу. Сравниваем эмпирические и теоретические частоты с помощью критерия Пирсона.

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

Таблица 6.3 – Результаты вычислений

i
		0, 285	34, 77	-12, 77	163, 073	4, 690
		0, 204	24, 888	0, 112	0, 013	0, 001
		0, 146	17, 812	5, 188	26, 915	1, 511
		0, 104	12, 688	3, 312	10, 969	0, 865
		0, 075	9, 15	4, 85	23, 523	2, 571
		0, 053	6, 466	3, 534	12, 489	1, 932
		0, 038	4, 636	3, 364	11, 316	2, 441
		0, 027	3, 294	0, 706	0, 498	0, 151

Т.к. , то нет оснований отвергнуть гипотезу о распределении X по показательному закону. Другими словами, данные наблюдений согласуются с этой гипотезой.

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

Граф данной системы:

Рисунок – Граф состояний исследуемой СМО

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

(1)

Для состояния S₀:

Следовательно:

Для состояния S₁:

Следовательно:

С учетом того, что :

Аналогично получаем уравнения для остальных состояний системы. В результате получим систему уравнений:

Решение этой системы будет иметь вид:

; ; ; ; ;

; .

Или, с учетом (1):

; ; ; ; ; ;

.

Коэффициент загруженности СМО:

С учетом этого предельные вероятности перепишем в виде:

Наивероятнейшее состояние – оба канала СМО заняты и заняты все места в очереди.

Вероятность образования очереди:

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

Относительная пропускная способность равна:

Вероятность того, что вновь поступившая заявка будет обслужена, равна 0, 529

Абсолютная пропускная способность:

СМО обслуживает в среднем 0, 13225 заявок в минуту.

Среднее число заявок, находящихся в очереди:

Среднее число заявок в очереди близко к максимальной длине очереди.

Среднее число заявок, обслуживаемых в СМО, может быть записано в виде:

В среднем все каналы СМО постоянно заняты.

Среднее число заявок, находящихся в СМО:

Для открытых СМО справедливы формулы Литтла:

Среднее время пребывания заявки с СМО:

Среднее время пребывания заявки в очереди:

Наиболее вероятное состояние данной СМО – занятость всех каналов и мест в очереди. Приблизительно половина всех поступающих заявок покидают СМО необслуженными. Приблизительно 66, 5% времени ожидания приходиться на ожидание в очереди. Оба канала постоянно заняты. Все это говорит о том, что в целом данная схема СМО неудовлетворительна.

Чтобы снизить загрузку каналов, сократить время ожидания в очереди и снизить вероятность отказа необходимо увеличить число каналов и ввести систему приоритетов для заявок. Число каналов целесообразно увеличить до 4. Также необходимо сменить дисциплину обслуживания с FIFO на систему с приоритетами. Все заявки теперь будут иметь принадлежность к одному из двух приоритетных классов. Заявки I класса имеют относительный приоритет по отношению к заявкам II класса. Для расчета основных показателей этой видоизмененной СМО целесообразно применить какой-либо из методов имитационного моделирования. Была написана программа на языке Visual Basic, реализующая метод Монте-Карло.

Пользователю при работе с программой необходимо задать основные параметры СМО, такие как интенсивности потоков, количество каналов, приоритетных классов, мест в очереди (если количество мест в очереди равно нулю, то СМО с отказами), а также временной интервал модуляции и количество испытаний. Программа преобразовывает сгенерированные случайные числа по формуле (34), таким образом, пользователь получает последовательность временных интервалов , распределенных показательно. Затем отбирается заявка с минимальным , и ставится в очередь, согласно ее приоритету. За это же время происходит перерасчет очереди и каналов. Затем эта операция повторяется до окончания времени модуляции, задаваемого изначально. В теле программы присутствуют счетчики, на основании показаний которых и формируются основные показатели СМО. Если для увеличения точности было задано несколько испытаний, то в качестве конечных результатов принимается оценка за серию опытов. Программа получилась достаточно универсальной, с ее помощью могут быть исследованы СМО с любым количеством приоритетных классов, либо вообще без приоритетов. Для проверки корректности работы алгоритма, в него были введены исходные данные классической СМО, исследуемой в разделе 7. Программа смоделировала результат близкий к тому, который был получен с помощью методов теории массового обслуживания (см. приложение Б). Погрешность, возникшая в ходе имитационного моделирования, может быть объяснена тем, что проведено недостаточное количество испытаний. Результаты, полученные с помощью программы для СМО с двумя приоритетными классами и увеличенным числом каналов, показывают целесообразность этих изменений (см. приложение В). Высший приоритет был присвоен более «быстрым» заявкам, что позволяет быстро обследовать короткие задания. Сокращается средняя длина очереди в системе, а соответственно минимизируется средство для организации очереди. В качестве основного недостатка данной организации можно выделить то, что «долгие» заявки находятся в очереди длительно время или вообще получают отказ. Введенные приоритеты могут быть переназначены после оценки полезности того или иного типа заявок для СМО.

Тема 14

. Понятие и сущность сетевого планирования и управления.

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются для оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. В 1956 году М. Уолкер из фирмы Дюпон, исследуя возможности использования более эффективного использования принадлежащей фирме вычислительной машины Univac, обледенил свои усилия с Д. Келли из группы планирования капитального строительства. В результате был создан Метод Критического Пути – МКП (или CPM – Critical Path Method).

Параллельно и независимо в военно – морских силах США был создан метод анализа и оценки программ PERT (Program Evaluation and Review Technique). Этот метод был разработан корпорацией Локхид для разработки ракетной системы Поларис, объединяющего около 3800 основных подрядчиков и 60000 операций. В результате применения метода работы были закончены на два года раньше срока, а метод был засекречен.

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

Построения сетевого графика.

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

На график нанесены работы и события. Каждое событие характеризует завершение или начало работы, а работа означает действие, которое нужно совершить, чтобы перейти от предшествующего события к последующему. События на графике обозначаются кружками, а работы — стрелками, показывающими связь между событиями (возможен и другой вариант: работы изображаются кружками, а связи между ними стрелками). Работа должна быть конкретной, четко описанной и иметь ответственного исполнителя; продолжительность её измеряется количеством дней, недель, декад и др., наносимых над стрелкой. Временные оценки даются ответственными исполнителями соответствующих работ. Все работы в графике ведут к конечному событию — цели планирования

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

По своей физической природе работы можно рассматривать как:

- действие: изготовление деталей, заливка фундамента, составление заявки на материа­лы, наблюдение и изучение конъюнктуры рынка;

- процесс: старение отливок, выдерживание вина в бочках, травление плат;

- ожидание: ожидание поставки комплектующих, пролеживание детали в
очереди к станку, ожидание результатов проверок.

По количеству затрачиваемого времени работа может быть:

- действительной, т.е. требующей затрат времени;

- фиктивной, не требующей затрат времени и представляющей связь

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

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

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

Таким образом, начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для идентификации конкретной работы используют код работы (i, j), состоящий из номеров начального (i-ro) и конечного (j-го) событий, например (2, 4); 3-8; 9, 10. работа i, j

На этапе структурного планирования взаимосвязь работ и событий

изображаются с помощью сетевого графика, где работы изображаются

стрелками, которые соединяют вершины, изображающие события. Работы,

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

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

При построении сетевого графика необходимо следовать следующим правилам:

■ длина стрелки не зависит от времени выполнения работы;

§ стрелка не обязательно должна представлять прямолинейный отрезок;

■ для действительных работ используются сплошные, а для фиктивных пунктирные стрелки;

§ каждая операция должна быть представлена только одной стрелкой;

§ не должно быть параллельных работ между одними и теми же событиями, для избежания такой ситуации используют фиктивные работы;

/\

следует избегать пересечения стрелок;

§ не должно быть стрелок, направленных справа налево;

■ номер начального события должен быть меньше номера конечного события;

§ не должно быть висячих событий, кроме исходного;