Система массового обслуживания с тремя узлами и с различным числом обслуживания приборов в узлах

Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет имени Франциска Скорины»

Математический факультет

Кафедра экономической кибернетики и теории вероятностей

Курсовой проект

Система массового обслуживания с тремя узлами и с различным числом обслуживания приборов в узлах

Исполнитель:

студент группы ЭК-41 Козакевич Н.А.

Научный руководитель:

Ассистент кафедры ЭК и ТВ Дудовская Ю.Е.

Гомель 2011



Введение

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

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

Системы массового обслуживания описываются заданием:

1. входящего потока заявок;

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

3. числа обслуживающих приборов (линий);

4. дисциплины обслуживания, организации очереди и процесса обслуживания.

В данном курсовом проекте рассматриваются системы массового обслуживания для которых:

1) входящий поток заявок является пуассоновским;

2) в системе три обслуживающих узла.

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



1. Марковские системы массового обслуживания

1.1 Теоретические сведения

К марковским системам относятся системы, поведение которых в момент времени t может быть описано марковским процессом . В частности, сюда относятся все системы вида M/M/n/N, где . Действительно, пусть обозначает число заявок в системе в момент t. Вероятностное распределение после момента t определяются:

1) числом заявок в системе в момент t;

2) моментами поступления заявок после момента t;

3) моментами окончаний обслуживания заявок после момента t.

В силу того, что входной поток простейший, моменты поступления заявок после момента t не зависят от предыстории системы до момента t. Аналогично, поскольку времена обслуживания показательно распределены, из-за “отсутствия памяти” у показательного распределения моменты окончания обслуживания заявок после момента t не зависят от предыстории системы до момента t. Поэтому вероятностное поведение после момента t зависит только от и не зависит от поведения до момента t. Значит марковский процесс с конечным или счетным числом состояний. Поэтому для нахождения зависящих от времени вероятностей состояний следует решить систему уравнений Колмогорова для безусловных вероятностей. Если интерес представляет стационарные вероятности, то следует решить систему уравнений равновесия. Для получения уравнений Колмогорова используется предельный переход при t, который называется t -методом.



1.2 Марковские сети массового обслуживания

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

Под состоянием сети в момент времени t будем понимать вектор:

(1.1)

где - число заявок в i-ой СМО (на обслуживание и в очереди).

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

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

1.3 Нахождение стационарных вероятностей состояний открытой марковской сети массового обслуживания

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

(1.2)

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

(1.3)

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

Предположим, что существует стационарное распределение

,(1.4)

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



(1.5)

Здесь

Для упрощения системы (1.5) введем величины так, что есть полная интенсивность поступления заявок в системы . Интенсивность состоит из интенсивности потока заявок, поступающих извне , и интенсивности поступления заявок в систему от других СМО, в том числе и от самой системы . Поэтому

(1.6)

Из (1.6) получим

(1.7)

Соотношение (1.6) иногда называют законом сохранения потока заявок. Оно говорит о том, что интенсивность входящего потока заявок в i-тую СМО, i=1,...,n, в стационарном режиме равна интенсивности входящего потока заявок из этой системы.

Теорема 1. (Джексона) Стационарное распределение может быть найдено в виде:



.(1.8)



2. Марковский случай

2.1 Описание модели

Рисунок 2.1 Сеть массового обслуживания с тремя узлами

2.2 Сеть массового обслуживания

Дана открытая марковская сеть массового обслуживания, состоящая из трех подсистем. Состояние сети в момент времени t определяется вектором

(2.1)

где число заявок в i-ой подсистеме в момент времени t. Входящий поток является пуассоновским потоком с параметром . Времена обслуживания заявок в i-ой системе массового обслуживания распределены по показательному закону с параметром µ.

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

2.3 Расчет основных характеристик для первого узла

Рассмотрим первый узел нашей системы (рис 2.2). Данная система массового обслуживания представляет собой линейную систему с ожиданием, в которой времена обслуживания заявок на одном приборе имеет показательное распределение с параметром µ (система M|M|1).

Рисунок 2.2 СМО с одним каналом обслуживания

Построим граф перехода данной системы (рис ---), найдем стационарное распределение.

Рисунок 2.3 Граф перехода для системы M|M|1



Уравнения равновесия принимают вид

(2.2)

Уравнение равновесия для вертикальных сечений:

.(2.3)

Выражаем из уравнения (2.3) :

(2.4)

Поскольку - распределение вероятностей, то , откуда .

Среднее число заявок в системе в стационарном режиме:

(2.5)

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

	1	0
P		1-с



Поэтому . Получили ещё одну интерпретацию коэффициента загрузки как среднего числа заявок на приборе в стационарной системе. Среднее число заявок в очереди в стационарном режиме

.(2.6)

2.4 Расчет основных характеристик для второго узла

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

Рисунок 2.4 СМО с двумя каналами обслуживания

Построим граф перехода данной системы (рис. 2.5), найдем стационарное распределение.

Рисунок 2.5 Граф перехода для системы M|M|2

Уравнения равновесия примут вид



(2.7)

Уравнение равновесия для вертикальных сечений:

(2.8)

Выражаем из первого уравнения системы (2.8) при k ? 2 :

(2.9)

Выражаем из второго уравнения системы (2.8) при k >2 :

(2.10)

Определим стационарные вероятности

(2.11)

Вероятность того, что заняты все приборы

(2.12)



Составим ряд распределения. Он будет иметь следующий вид:

	0	1	2

Среднее число занятых приборов

(2.13)

Найдем среднее число заявок в очереди. Для этого составим следующий ряд распределения:

з	0	1	…	k	…
			…		…

Среднее число заявок в очереди

(2.14)

Среднее число заявок в системе :

(2.15)

2.5 Расчет основных характеристик для второго узла

трехузловой марковский сеть эргодичность

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

Рисунок 2.6 СМО с тремя каналами обслуживания

Построим граф перехода данной системы (рис. 2.7), найдем стационарное распределение.

Рисунок 2.7 Граф перехода для системы M|M|3

Уравнения равновесия примут вид

(2.16)

Уравнение равновесия для вертикальных сечений:

(2.17)

Выражаем из первого уравнения системы (2.17) при k ? 3 :



(2.18)

Выражаем из второго уравнения системы (2.17) при k >3 :

(2.19)

Определим стационарные вероятности исходя из формул (2.18) и (2.19)

(2.20)

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

(2.21)

Составим ряд распределения. Он будет иметь следующий вид:

	0	1	2	3

Среднее число занятых приборов

(2.22)



Найдем среднее число заявок в очереди. Для этого составим следующий ряд распределения:

з	0	1	…	k	…
			…		…

Среднее число заявок в очереди

(2.23)

Среднее число заявок в системе :

(2.24)

2.6 Уравнения равновесия

Предположим, что существует стационарное распределение . Составим уравнение равновесия. Пусть

, ,

тогда уравнения равновесия примут следующий вид

(2.25)

2.7 Нахождение стационарных вероятностей

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

,(2.26)

- вероятность поступления заявок в i-ую подсистему. Таким образом нам необходимо найти . Для этого воспользуемся соотношением (1.6) из раздела 1.4. В результате мы получим следующую систему

Матрица перехода имеет вид

.

Тогда получим



, , .

Исходя из этого имеем

? ,

? ,

? .

=

Стационарные распределения найдены.

2.8 Условия эргодичности

Для исследования эргодичности применим эргодическую теорему Фостера.

Теорема (Эргодическая теорема Фостера).

Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений

(2.27)



имеет нетривиальное решение () такое, что .

При этом существует единственное стационарное распределение, которое совпадает с эргодическим.

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

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

.

Тогда получим,

,

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

.(2.28)

Уравнение (2.28) и есть искомое условие эргодичности. Если это условие будет выполнятся, то будет существовать единственное стационарное распределение, совпадающее с эргодическим.



3. Сеть магазинов "Пятый элемент" по продажам бытовой техники

Рассмотрим в данном курсовом проекте СМО на примере работы сети магазинов «Пятый элемент» в Гомельской области. В городе Лельчицы работает магазин с одним прибором обслуживания. В городе Речица работает магазин с двумя приборами обслуживания, а в городе Добруш работает магазин с тремя приборами обслуживания. Требуется проанализировать работу сети в целом.

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

Результат работы первого магазина представлен на рисунке (3.1).

Рисунок 3.1 - Основные характеристики для системы с одним каналом обслуживания

Результаты анализа работы второго магазина сети представлен на рисунке (3.2).



Рисунок 3.2 - Основные характеристики для системы с двумя каналами обслуживания

Результаты анализа работы третьего магазина сети представлен на рисунке (3.3).

Рисунок 3.3 - Основные характеристики для системы с тремя каналами обслуживания



По выше рассчитанным данным мы можем провести анализ работы всей сети магазинов «Пятый элемент» в целом (рис. 3.4).

Рисунок 3.4 - Основные характеристики работы трехузловой сети



Заключение

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



Список использованных источников

1 Дроздов, Н. Д. Алгоритмы кибернетики [Текст] : учеб. пособие для вузов / Н. Д. Дроздов, 2002. - 94 с.

2 Жерновский, Ю. В. Марковские модели массового обслуживания [Текст] : учеб. пособие для физ. - мат. специальностей вузов, 2007. - 154 с.

3 Кремер, Н. Ш. Теория вероятностей и математическая статистика [Текст] : учеб. для вузов / Н. Ш. Кремер, - 2-е изд., перераб. и доп. - ЮНИТИ-ДАНА , 2004. - 573 с.

4Малинковский, Ю. В. Гомельский государственный университет имени Ф. Скорины. Лекции по теории массового обслуживания [Текст] : науч. изд. / Ю. В. Малинковский: ГГУ им. Ф. Скорины, 2005. - 184 с.



Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, StdCtrls, Menus, XPMan, Buttons;

type

TForm1 = class(TForm)

Button1: TButton;

Edit1: TEdit;

MainMenu1: TMainMenu;

N1: TMenuItem;

XPManifest1: TXPManifest;

N3: TMenuItem;

N4: TMenuItem;

Edit2: TEdit;

Label2: TLabel;

Label3: TLabel;

Button2: TButton;

Button3: TButton;

Panel1: TPanel;

Label17: TLabel;

Label19: TLabel;

Label20: TLabel;

Label21: TLabel;

Label12: TLabel;

Label13: TLabel;

Label14: TLabel;

Label15: TLabel;

Panel2: TPanel;

Panel3: TPanel;

Button4: TButton;

Panel4: TPanel;

Label1: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

Label10: TLabel;

Label11: TLabel;

Label16: TLabel;

Label18: TLabel;

Label22: TLabel;

Label23: TLabel;

Label24: TLabel;

Label25: TLabel;

Label26: TLabel;

Label27: TLabel;

Label28: TLabel;

Label29: TLabel;

Label30: TLabel;

Label31: TLabel;

Label32: TLabel;

Label33: TLabel;

Label34: TLabel;

Label35: TLabel;

Label36: TLabel;

Label37: TLabel;

Label38: TLabel;

Label39: TLabel;

Label40: TLabel;

BitBtn1: TBitBtn;

procedure Button1Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

public

{Public declarations}

end;

var

Form1: TForm1;

a,b,c,x1,x2,x3,t1,t2,t3,v1,v2,v3:real;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

l,m,r1,a,x1,t1,v1:real;

begin

if not(Edit1.Text='')then

l:=strtofloat(Edit1.Text);

m:=strtofloat(edit2.tExt);

r1:=(l*2.041)/m;

label4.Caption:=FloatToStr(r1);

a:=1-r1;

x1:=r1/(1-r1);

t1:=r1*r1/(1-r1);

v1:=r1;

label12.Caption:=FloatToStr(a) ;

label13.Caption:=FloatToStr(x1);

label14.Caption:=FloatToStr(v1) ;

label15.Caption:=FloatToStr(t1) ;

Panel1.visible:=true;

end;

procedure TForm1.Button2Click(Sender: TObject);

Var

l,m,r2,b,x2,t2,v2:real;

begin

if not(Edit1.Text='')then

l:=strtofloat(Edit1.Text);

m:=strtofloat(edit2.tExt);

r2:=(l*2.16)/m;

label10.Caption:=FloatToStr(r2);

b:=1/(1+r2+r2*r2/2+r2*r2*r2/(4-2*r2));

t2:=b*r2*r2*r2/((4-2*r2)*(2-r2));

v2:=b*(2*r2+2*r2*r2-r2*r2*r2)/(2-r2);

x2:=t2+v2;

label11.Caption:=FloatToStr(b) ;

label16.Caption:=FloatToStr(x2);

label18.Caption:=FloatToStr(v2) ;

label22.Caption:=FloatToStr(t2) ;

Panel2.visible:=true;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

close;

end;

procedure TForm1.Button3Click(Sender: TObject);

var

t1, t2, r1, r2, b, l,m,r3,c,x3,t3,v3:real;

begin

if not(Edit1.Text='')then

l:=strtofloat(Edit1.Text);

m:=strtofloat(edit2.tExt);

r3:=(l*2.817)/m;

label28.Caption:=FloatToStr(r3);

c:=1/(1+r3+r3*r3/2+r3*r3*r3/6+r3*r3*r3*r3/(18-6*r3));

t3:=c*r3*r3*r3*r3/((54-18*r3)*(3-r3));

v3:=c*(r3+r3*r3+r3*r3*r3/2+r3*r3*r3/(6-2*r3));

x3:=t3+v3;

label29.Caption:=FloatToStr(c) ;

label30.Caption:=FloatToStr(x3);

label31.Caption:=FloatToStr(v3) ;

label32.Caption:=FloatToStr(t3) ;

Panel3.visible:=true;

end;

procedure TForm1.Button4Click(Sender: TObject);

var

t1, t2, t3, r1, a, c, r2, r3 ,b,v1,v2, v3, x1, x2,x3, p,x,t,v,l,m:real;

begin

if not(Edit1.Text='')then

l:=strtofloat(Edit1.Text);

m:=strtofloat(edit2.tExt);

r1:=(l*2.041)/m;

r2:=(l*2.16)/m;

r3:=(l*2.817)/m;

c:=1/(1+r3+r3*r3/2+r3*r3*r3/6+r3*r3*r3*r3/(18-6*r3));

b:=1/(1+r2+r2*r2/2+r2*r2*r2/(4-2*r2));

t1:=r1*r1/(1-r1);

t2:=b*r2*r2*r2/((4-2*r2)*(2-r2));

t3:=c*r3*r3*r3*r3/((54-18*r3)*(3-r3));

v3:=c*(r3+r3*r3+r3*r3*r3/2+r3*r3*r3/(6-2*r3));

x3:=t3+v3;

v2:=b*(2*r2+2*r2*r2-r2*r2*r2)/(2-r2);

x2:=t2+v2;

a:=1-r1;

x1:=r1/(1-r1);

//t1:=r1*r1/(1-r1);

v1:=r1;

p:=a+b+c;

t:=t1+t2+t3;

v:=v1+v2+v3;

x:=x1+x2+x3;

label37.Caption:=FloatToStr(p) ;

label38.Caption:=FloatToStr(x);

label39.Caption:=FloatToStr(v) ;

label40.Caption:=FloatToStr(t) ;

Panel4.visible:=true;

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

begin

close;

end.

Размещено на Allbest.ru