Представление информации о сети

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

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

В основе решения лежат 5 основных алгоритмов: READ, ORIGS,ORIG,TERMS,

TERM.

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

1) INITIAL- считывается количество узлов, вводится свободный узел,  все внешние фиксированные потоки полагаются равными нулю

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

Если свободный внешний поток равен 0, то шаг 2 повторяется, иначе вводится свободная дуга и заносятся данные об этой дуге в список дуг.

3) ARC -считываются данные о дуге. Если встречается конец списка, то переходим на пункт 4, иначе заносим данные о дуге в список дуг и повторяем шаг 3.

4) EXIT- располагаем данные в каждой дуге в порядке, соответствующем

списку P_t.

 5. Задачи в условиях известного закона распределения неизвестных факторов

(Теория массового обслуживания)

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

1) очередь покупателей у касс магазина

2) колонна автомобилей перед светофором

3) больные в очереди на прием к врачу

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

5) самолеты, ожидающие разрешения на взлет

6) ожидающие публикации рукописные материалы в издательстве.

Общим у этих случаев является необходимость ожидать обслуживания. Феномен ожидания является следствием вероятностного характера возникновения потребностей в обслуживании и разброса показателей обслуживающих систем. Ни время возникновения потребности в обслуживании, ни продолжительность обслуживания  поступившего в обслуживающую систему клиента заранее не известны. Цель изучения режима функционирования обслуживающей системы при существенном факторе случайности состоит в том, чтобы взять под контроль количественные показатели функционирования СМО.( например среднего времени пребывания в очереди, времени простоя обслуживающей системы из-за отсутствия заявок на обслуживание). Эти параметры являются взаимоисключающими, так как чем дольше ожидание, тем меньше простой и наоборот. Рассматриваемые модели основаны на теории вероятности и теории случайных процессов.

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

1) обеспечить максимальное удовлетворение требований,

2) обеспечить минимальные затраты материальных средств и минимальные сроки.

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

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

2) структура обслуживающей системы (параллельность обработки, многофазность, последовательность)

3) допустимая вместимость блока ожидания или допустимая длина очереди

4) характер требования (невозможность ожидания свободного прибора или возможность)

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

Время поступления заявок и их количество являются случайными величинами и представляют случайные процессы, которые описываются некоторой функцией X(t) , определяющей количество требований нуждающихся в обслуживании за промежуток времени [0,t]. Для любого момента t это количество является целым числом, поэтому функция является целочисленной. Она определена, если для любых t₁,t₂,...t_n можно указать число требований на данный момент. Полная характеристика случайной величины дается законом распределения вероятностей. Для полного определения потока требований достаточно знать вероятность того, что за промежуток времени t_i поступит k_i  требований. Если эта вероятность будет определена для группы целых положительных чисел k₁,k₂,...k_n   t₁,t₂,...t_n, то поток может быть описан математически. Обозначим вероятность того, что за t_i  поступит ровно k_i  требований (i=0,1,...n) через

P{x(t₁)=k₁,x(t₂)=k₂,...x(t_n)=k_n}.

Вероятность того, что за промежуток времени [0,t] поступит ровно k (k=0,1,...n) требований обозначим через F(t,k)=P{x(t)=k}.

Следовательно, вероятность того, что в течение дня в мастерскую будет поступать ежечасно 5 требований запишется в виде

F(1,2,3,4,5,6,7;5,10,15,20,25,30,35)=P{x(1)=5;x(2)=10;...x(7)=35}.

С помощью функции F(t₁,t₂,...t_n;k₁,k₂,...k_n) можно описать любой поток требований, однако конкретный вид этой функции редко известен.

Изучение потоков начинают с простейших случаев, которые получаются при наложении на поток следующих упрощающих предположений

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

P{x(t)=k}=P{x(t+a)-x(a)=k}   (1)

где k=0,1,...n.

Иная формулировка: вероятность наступления события (поступления в ОС требования или выбытия из системы обслуженного клиента в интервале [t, t+h] зависит лишь от величины h, т.е. вероятность не зависит ни от количества событий, имевших место до момента t, ни от положения момента t на оси времени.

2) Вероятность реализации события на бесконечно малом временном отрезке h больше нуля, но меньше единицы

3) свойство отсутствия памяти (последействия): поток требований называется без последействия, если число требований поступивших в систему после некоторого произвольного момента времени t₁ не зависит от количества требований, поступивших в систему до момента времени t₁. Математически это означает, что закон распределения случайной величины x(t_i+a)-x(a) (i=0,1,..n) при  t_i>0 и любом a>0 не зависит от значений величины x(t) при t<a. В этом случае условная вероятность поступления k требований за промежуток времени (a,a+t)  при предположении, что количество требований, поступивших в систему до момента а, будет любым, совпадает с безусловной вероятностью этого события. Если обозначить через        

p_k(t)=P{x(t)=k}, где k=0,1,...n

 вероятность того, что за промежуток времени [0,t] при t>0 поступит ровно k требований, то оказывается что стационарный поток без последействия может быть полностью охарактеризован системой функций p_k(t)  при k=0,1,...,n и t>0.

4) свойство ординарности потока: поток называется ординарным, если в любой момент времени может поступить только одно требование. В ординарных потоках почти невозможно появление нескольких требований в одно и то же время. Если обозначить через U(t) вероятность появления двух и более требований за промежуток времени [0,t], то свойство ординарности потока может быть записано в виде

lim U(t)/t=0 при t-->0 или U(t)=O(t) при tà0,

где О(t) -бесконечно малая величина более высокого порядка чем t.

Формулировка Таха: На бесконечно малом временном отрезке h реализуется не более одного события.

Рассмотрим вероятности p_k(t)с точки зрения этих предположений о потоке. Свойство 1  означает ,что события являются равновероятными и статистически независимыми. Следовательно, можно утверждать, что для k=0  p₀(t+h)=p₀(t)*p₀(h).

В силу свойства 2 для бесконечно малого интервала h имеем 0<p₀(h)<1. Решение этого уравнения имеет вид  p₀(h)=e^-at,t>=0,где a -положительная постоянная. Ниже будет показано, что a следует интерпретировать как частоту наступления событий (число событий в единицу времени), под которыми понимается либо поступление требования в систему МО, либо выбытие требования из ОС после процедуры обслуживания. Для достаточно малой, но не равной нулю величины h имеем

p₀(h)=e^-ah=1-ah+(ah)²/2!-(ah)³/3!+...=1-ah.

В силу свойства 3 получим p₁(h)=1-p₀(h)=ah.

Это означает, что вероятность реализации в интервале h события прямо пропорциональна h. Процесс, описываемый функцией p_n(t), является рандомизированным в том смысле, что длина интервала времени, в течение которого наступает каждое последующее событие, не зависит от времени, которое потребовалось для реализации предшествующего события. В теории вероятности функция f(t) определена как плотность вероятности того, что длина интервала времени между последовательными наступлениями случайного события равняется t(t>=0), а F(t)=òf(x)dx есть функция распределения t. В соответствии с положениями теории вероятностей можно утверждать, что если Т - интервал времени, прошедшего после реализации последнего из наблюдавшихся событий, то

   Р{ интервал времени между моментами      =         P{ в течение Т событие не

    реализации случайного события не менее Т}           реализуется}.

В математической записи это выглядит

P{t>=T}=p₀(T).

Поскольку f(t) есть плотность вероятности того, что интервал времени между последовательными реализациями случайного события равняется t, а p₀(T)=e^-aT, то

òf(t)dt=e^-at.

То есть с учетом определения F(T) имеем 1-F(T)=e^-aT (T>0). Дифференцируя по Т , получаем

f(t)=ae^-aT (T>0),

т.е. экспоненциальное распределение. Таким образом, можно сделать следующие выводы:

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

2) для экспоненциального распределения вероятностей математическое ожидание случайной величины Т равно

       Е{T}=1/a (ед. времени)

и представляет собой среднее значение временных интервалов между моментами последовательных реализаций, т.о. 1/Е{T}=a (событие/ед. времени) есть частота генерации события (число событий в ед. времен). По этой причине выше отмечалось, что величина a есть количество требований, отнесенных к единице времени.

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

P{t>T+S|t>S}=P{t>T},

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

P{t>T+S|t>S}=P{t>T+S,t>S}/P{t>S}=P{t>T+S}/P{t>S}=e^-a(T+S)/e^-aS=e^-aT=P{t>T}

Это свойство называется отсутствием памяти и оно иллюстрирует факт, что описываемый вероятностями  p_n(t) процесс является совершенно случайным. По определению p_n(t) есть вероятность реализации n событий в интервале времени, равном t, длины временных интервалов между последовательными реализациями событий распределены по закону f(T)=ae^-aT, где a - средняя частота реализации событий. Распределение величины n на временном отрезке является пуассоновским. Таким образом, если интервал времен между последовательными поступлениями требований в обслуживающей системе распределены экспоненциально, то количество поступлений требований в систему характеризуется пуассоновским распределением и наоборот.