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

2.2 Автоматное моделирование входящего потока

Для автоматного описания входящих потоков задается автоматное время. В качестве единицы автоматного времени может быть любая единица реального времени: секунда, минута, час сутки, год и т.д. или другая составная единица: 10 минут, 5 дней и т.п. Эта единица выбирается настолько малой, чтобы ее можно было бы измерять случайные интервалы потока ?ti в виде целочисленных или близких к ним величин. Т.е. такими, чтобы после округления значения измеренных интервалов ?ti мало бы отличались от исходных.

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

Пусть состояние a(t) автомата А в момент автоматного времени t означает тот промежуток времени, который остался до момента поступления следующей заявки. Тогда, если в какой-то момент времени эта величина была больше единицы (a(t)>1), то через единицу времени она уменьшится на единицу, т.е. будет a(t+1)=a(t)-1. Если a(t)=1, то через единицу времени произойдет поступление в систему заявки, а величина промежутка до поступления очередной заявки будет сгенерирована автоматом как случайное число ?t, т.е.

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

2.3 Автоматное моделирование систем обслуживания

Наряду с автоматом, генерирующим входящий поток, А рассмотрим автомат, генерирующий время обслуживания, В.

Пусть состояния a(t) автомата А обозначают остаточное время поступления заявки в систему обслуживания, а состояния b(t) автомата В обозначают остаточное время обслуживания очередной заявки.

Когда осталась одна единица времени обслуживания очередной заявки или обслуживающий аппарат свободен (а=0), а в следующий такт, когда предыдущая заявка покинет систему и появится новая заявка (х=1) автомат В должен генерировать новый случайный интервал обслуживания ?t для новой заявки. При этом будет выработан выходной сигнал у=1. Когда обслуживающий аппарат может принять заявку, а ее в следующий такт не будет (х=0)-остаточное время принимается равным 0 и вырабатывается выходной сигнал равный 1. Когда обслуживающий аппарат может принять заявку, а ее в следующий такт не будет, т.е. накопитель свободен, будет выработан выходной сигнал y=0.

2.4 Детерминированный автомат

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

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

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

Выходной сигнал этого автомата равен d, он совпадает с текущим внутренним состоянием D.

Запишем блок-схему функционирования СМО с накопителем:

Блок 1

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

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

Блок 2

Блок 3

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

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

В этой блок-схеме в Блоке 2 с помощью символов max и min записаны логические скобки изменения емкости накопителя «не менее» 0 и «не более» М. Выходной сигнал х формирует накопление заявок, которые в обязательном порядке проходят через накопитель. В операторе 3.2 проверка логического условия окончания обслуживания и наличия очередной заявки организована не с помощью выходного сигнала х, как в предыдущем примере, а с помощью выходного сигнала d, детерминированного автомата. Если в накопителе есть хотя бы одна заявка (d>0) и обслуживающий аппарат в следующем такте свободен (b?1), то автомат В вырабатывает для поступающей из накопителя заявки интервал обслуживания ?ф. Выдает сигнал у=1, и одновременно уменьшает емкость накопителя на одну единицу.

2.5 Автоматы индикаторы

Автоматы индикаторы относятся к детерминированным автоматам, они предназначены для «внешнего» обслуживания системы. С помощью индикаторов формируются выходные характеристики системы. Эти числовые характеристики как правило имеют статистическую природу и получаются на основе использования вероятностных законов больших чисел.

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

3. Программная реализация

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

3.1 Описание исходной информации

СМОЗ характеризуется следующими параметрами:

н - частота обращения одного автосамосвала под погрузки в единицу времени;

м - производительность погрузчика (экскаватора);

N - число экскаваторов, арендуемых у автотранспортного предприятия по цене Сп(т) за каждый погрузчик в единицу времени;

K - число автосамосвалов арендуемых у автотранспортного предприятия по цене Са(т) за каждый автосамосвал в единицу времени.

Следует подчеркнуть, что в этом случае все экскаваторы одинаковы и имеют одну и туже производительность (м);

3.2 Метод решения задачи

Рассмотрим графическую схему перевозочных работ в виде графа сети автоматов (рис 2):

Рисунок 2 - Граф сети автоматов

Автоматы, формирующие обслуживание автомашин

В связи с тем, что все машины имеют одинаковую оборачиваемость, то в этом случае можно сформировать поток, поступающих на погрузку машин в виде переменного входящего потока с плотностями Кн, (К-1)н, …, 2н, н, где числа К, K-1, …, 2, 1 обозначают число машин, находящихся в пути в данную единицу автоматного времени.

Это число L можно определить в каждую единицу автоматного времени с помощью формулы:

n

L= K-b- ? yi , где

i=1

К - общее число автомашин,

b - число автомашин в накопителе,

n

? yi - число автомашин стоящих под загрузкой,

i=1

yi - двоичный выходящий сигнал от Сi -го автомата (0,1):

0 - когда погрузчик свободен;

1 - когда погрузчик занят, или получает очередную машину под погрузку.

Рассмотрим таблицу условных функциональных переходов (ТУФП).

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

Если ?t>1 то ?t=?t-1

x=0

n

Если ?t=1 то L= K-b- ? yi ?t =[(-60/нL)Ln(Rand(0,1))]

i=1

x=1

b=max[0,min(b+x,K)]

Цикл I=1?N

Если ?фi>1 то ?фi =?фi-1

yi=1

Если ?фi<=1 и b=0 то ?фi=0

yi=0

Если ?фi<=1 и b=>1 то b=b-1

?ф=[(-60/м)Ln(Rand(0,1))]

yi=1

В качестве инструктора необходимо рассмотреть двумерный массив

0 1 ….. K

PS

P0 P1 ….. Pk

c помощью которого можно получить параметры системы: среднее число свободных автомашин СА и среднее число свободных экскаваторов СЕ.

Массив PS в процедуре имитационного моделирования формируется путем накопления автоматных единиц в карманах состояний S1, S2, … , Sk.

Чтобы послать очередную единицу в карман состояния нужно сформировать цикл I от 0 до K, а перед этим определить число L, т.е. число автомашин, находящихся в данную единицу автоматного времени в пути; и тот номер кармана I, который совпадает с K-L получит эту единицу

k

L= b+ ? yi ; r=K-L

i=1

Цикл I=0?K

Если I=r то WP[2,I]=WP[2,J]+1

Иначе цикл продолжить до K

Конец цикла

Если G число тактов автоматного времени, то, чтобы получить распределение вероятностей во второй строке массива WP, необходимо сформировать следующий цикл:

Цикл I=0?K

WS[2,I]= WS[2,I]/G

Конец цикла

Число свободных экскаваторов определяется по формуле:

СЕ=NP0+(N-1)P1+… 1Pn-1

Число свободных автопогрузчиков определяется по формуле:

CA=1Pn+2Pn+1+… (K-N)Pk

На основании проведенного анализа работы СМОЗ можно построить структурный граф имитационной модели, наглядно отображающий элементы системы и связи между ними (рис 3).

Рисунок 3 - Структурный граф имитационной модели

На рисунке использованы следующие обозначения:

Avt1, … , Avtk - автомашины;

QAvt - очередь автомашин, ожидающих погрузку;

Pogr1, … , Pogrn -погрузочные механизмы;

QPogr- очередь погрузочного механизма.

3.3 Машинное представление

Главное окно программы:

Рисунок 4 - Окно программы

Заключение

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

Имитационное моделирование как раз реализует сюжет эволюции системы при реальном взаимодействии ее с внешней средой.

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

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

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

К достоинствам метода имитационного моделирования могут быть отнесены:

* проведение ИЭ над ММ системы, для которой натурный эксперимент не осуществим по этическим соображениям или эксперимент связан с опасностью для жизни, или он дорог, или из-за того, что эксперимент нельзя провести с прошлым;

* решение задач, аналитические методы для которых неприменимы, например, в случае непрерывно - дискретных факторов, случайных воздействий, нелинейных характеристик элементов системы и т.п.;

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

* сокращение сроков и поиск проектных решений, которые являются оптимальными по некоторым критериям оценка эффективности;

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

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

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

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

Список литературы

1. В.С. Иозайтис, Ю.А. Львов Экономико-математическое моделирование производственных систем. - М.: В.Ш., 1991.

2. Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: В.Ш., 1998.

Приложение А

unit CMO_U;

interface

uses

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

Dialogs, StdCtrls, Math, Grids;

type

TForm1 = class(TForm)

Button1: TButton;

StringGrid1: TStringGrid;

Label17: TLabel;

Label18: TLabel;

Label19: TLabel;

Label21: TLabel;

Label22: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

n: array[1..6] of integer;

K: array[1..2,0..9] of real;

G,x,i,r: integer;

a,b: integer;

y1,y2,y3,y4,y5,y6:integer;

begin

a:=1;

b:=0;

r:=0;

for i:=1 to 6 do

n[i]:=1;

for i:=0 to 9 do

K[1,i]:=0;

for G:=1 to 1000 do begin

if a>1 then begin

a:=a-1;

x:=0;

end{if a};

if a=1 then begin

x:=1;

a:= Round(-(60/20.7)*Ln(Random));

if a=0 then a:= Round(-(60/20.7)*Ln(Random));

end{if a};

//Накопитель

b:=max(0,min(2,(b+x)));

//Аппараты

for i:=1 to 6 do begin

if n[i]>1 then begin

n[i]:=n[i]-1;

if i=1 then y1:=0;

if i=2 then y2:=0;

if i=3 then y3:=0;

if i=4 then y4:=0;

if i=5 then y5:=0;

if i=6 then y6:=0;

end{if};

if (n[i]<=1) AND (b>=0) then begin

n[i]:=Round(-(60/3.98)*Ln(Random));

if n[i]=0 then n[i]:= Round(-(60/3.98)*Ln(Random));

if i=1 then y1:=1;

if i=2 then y2:=1;

if i=3 then y3:=1;

if i=4 then y4:=1;

if i=5 then y5:=1;

if i=6 then y6:=1;

b:=b-1;

end{if};

if (n[i]<=1) AND (b=0) then begin n[i]:=0;

if i=1 then y1:=1;

if i=2 then y2:=1;

if i=3 then y3:=1;

if i=4 then y4:=1;

if i=5 then y5:=1;

if i=6 then y6:=1;

end{if}; end{for i};

r:= b+(1-y1)+(1-y2)+(1-y3)+(1-y4)+(1-y5)+(1-y6);

for i:=0 to 9 do begin

if i=r then

K[1,i]:=K[1,i]+1;

end{for};

for i:=0 to 9 do

StringGrid1.Cells[1,i]:= FormatFloat('0.0000',K[1,i]/1000);

end{for G}; end;

procedure TForm1.FormCreate(Sender: TObject);

var i: integer;

begin

Randomize; for i:=0 to 9 do StringGrid1.Cells[0,i]:= 'P'+IntToStr(i); end; end.

Приложение Б

unit Server_U;

{$WARN SYMBOL_PLATFORM OFF}

interface

uses

Windows, ActiveX, Classes, ComObj, Server_P_TLB, StdVcl, Variants;

type

TServer = class(TTypedComObject, IServer)

private

my,v: integer;

protected

function Get_my: Integer; stdcall;

function Get_v: Integer; stdcall;

procedure Set_my(Value: Integer); stdcall;

procedure Set_v(Value: Integer); stdcall;

function SysMasObs(n, c: Integer): OleVariant; stdcall;

end;

implementation

uses ComServ;

function TServer.Get_my: Integer;

begin

Result:= my;

end;

function TServer.Get_v: Integer;

begin

Result:= v;

end;

procedure TServer.Set_my(Value: Integer);

begin

my:= Value;

end;

procedure TServer.Set_v(Value: Integer);

begin

v:= Value;

end;

function TServer.SysMasObs(n, c: Integer): OleVariant;

var

WP:array of array of double;

A:array of array of integer;

G:array of integer;

k,ii,j,b,i:integer;

begin

Randomize;

A:=nil; G:=nil; WP:=nil;

SetLength(A,c);

SetLength(G,n);

SetLength(A[0],c);

SetLength(A[1],c);

SetLength(WP,2,c+1);

// Заполнение матрицы самосвалов

for i:=1 to c do begin

a[0,i-1]:=trunc((-60/v)*ln(random))+1;

end;

// Заполнение матрицы экскаваторов (все свободны)

for i:=1 to n do

g[i-1]:=0;

b:=0;//количество свободных машин в системе

for ii:= 1 to 100000 do begin

// Условия для матрицы А самосвалы

for i:=1 to c do begin

//если самосвал свободен

if(a[0,i-1]=0) and (a[1,i-1]=0) then begin

//ищем свободный экскаватор

for k:= 1 to n do begin

if g[k-1]=0 then begin

g[k-1]:=trunc((-60/my)*ln(random))+1; //экскаватор работает

a[1,i-1]:=k; //какой экскаватор нагружает самосвал

Break;

end;

end;

end;

//если самосвал освобождается

if (a[0,i-1]=1) then begin

a[0,i-1]:=0;

b:=b+1;

//ищем свободный экскаватор

for k:=1 to n do begin

if g[k-1]=0 then begin

g[k-1]:= trunc((-60/my)*ln(random))+1;

a[1,i-1]:=k; //какой экскаватор нагружает самосвал

Break;

end;

end;

end;

//если самосвал работает

if a[0,i-1]>1 then a[0,i-1]:=a[0,i-1]-1;//продолжает работать

end;

wp[0,b]:=wp[0,b]+1;//матрица вероятностей СМО

// Условия для матрицы G экскаваторы

for i:=1 to n do begin

//если экскаватор свободен и если самосвалы заняты

if (g[i-1]<1) and (b=0) then begin

//ищем самосвал, который в данный момент освобождается

for j:= 1 to c do begin

if a[1,j-1]=1 then begin

a[1,j-1]:=0;

a[0,j-1]:=trunc((-60/v)*ln(random))+1;//самосвал едет к экскаватору

end;

end;

end;

//если экскаватор свободен и есть свободные самосвалы

if (g[i-1]<=1) and (b>0) then begin

for j:=1 to c do begin

//ищем какой самосвал свободен

if a[1,j-1]=i then begin

a[1,j-1]:=0;

a[0,j-1]:=trunc((-60/v)*ln(random))+1;

g[i-1]:=0;

b:=b-1;

end;

end;

end;

//если экскаватор работает

if g[i-1]>1 then begin

g[i-1]:=g[i-1]-1;// экскаватор продолжает работать

end;

end;

end;

Result := VarArrayCreate([0,1,0,c+1],varDouble);//матрица для хранения результата вычисления

//Из матрицы WP результат помещаем в матрицу Result

for i:=0 to c do begin

Result[0,i]:= WP[0,i];

end;

end;

initialization

TTypedComObjectFactory.Create(ComServer, TServer, Class_Server,

ciMultiInstance, tmApartment);

end.

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