Учебное пособие 800529

Парное сравнение. При ранжировании надо сравнивать сразу все объекты, то есть иметь представление о всей предметной дистанции. Это непросто. Более простую задачу составляет сравнение двух соседних объектов, между которыми возможно либо отношение строгого порядка, либо эквивалентности (см. шкалу Т.Саати). Строится матрица парных сравнений, которая отражает не упорядоченность всех объектов, а только упорядоченность пар. У матрицы находится собственный вектор, который эту рыхлость попарного сравнения ужесточает. Более подробно об этом сказано при изложении метода анализа иерархий ниже, в п.4.5.

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

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

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

261

В ходе любого процесса изменяются свойства каких-то объектов. Свойство объекта - это совокупность его определенных характеристик. Говорят, что объект находится в каком-то состоянии, если он имеет определенные значения конкретных характеристик. Изменение значений этих характеристик приводит к изменению состояния объекта. Связанная формально цепочка состояний и есть формальная модель любого процесса. Так, в основном, и поступают при моделировании динамических процессов оценивания эффективности.

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

В этом случае основная характеристика динамики процесса – вероятность перехода в конечное состояние cℓ в зависимости от времени вычисляется достаточно просто. Формально это определяется так.

Для каждого состояния записывается уравнение А.Н.Колмогорова:

262

при начальных условиях:

t=0, Р1=1, Р2=Р3=…=Рℓ=0.

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

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

Модель оптимизации отличается от модели оценивания эффективности принципиально, ибо в ней моделируются предпочтения лица, принимающего решения (ЛПР), а в модели оценивания эффективности моделируется процесс воздействия средств на тракт утечки (среду воздействия). При этом оптимизация идет по составу средств, по их количеству и по порядку использования (управления). А предпочтения ЛПР рассматриваются по: величине эффективности средства, комплекса, подсистемы; затратам на применение средств, комплексов, подсистем; величине ресурса средств; побочным эффектам их применения.

Совокупные связи (отношения) указанных предпочтений формулируются в виде оптимизационной задачи. Оптимизация обычно проводится в интересах достижения max эффективности при заданных затратах или min затрат при заданной эффективно-

263

сти. Тогда облик комплекса, подсистемы формально записывается так:

S(x,y) = arg max Эф( x, y )

при ограничениях x X доп ; y Yзад , где х – управляемые переменные,

у – неуправляемые переменные.

Если y рассматривается конфликтно, то есть со своим поведением, то задача формулируется так:

S(x,y) = arg max min Эф( x, y )

при ограничениях

x О X доп ; y = рациональная стратегия соперника,

стремящаяся к min Эф(х).

Задача оптимизации формально относится к классу задач математического анализа по поиску экстремума функции, который соответствует равенству нулю первой производной. Но есть одно "но"! Экстремум в математическом анализе ищется для функции без ограничений, а у нас они есть. А наличие ограничений приводит к тому, что экстремум размещается на границе зоны, где производной не существует. Поэтому задачи оптимизации, т.е. экстремизации при наличии ограничений, решаются в специальной ветви прикладной математики – математическом программировании (не путать с программированием, т.е. составлением программ для ЭВМ).

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

Эф( x, y ) и ограничения линейны, т.е. функции от неизвестной

первой степени. В противном случае – нелинейное программирование. Эти задачи принципиально сложнее линейных.

264

4.5.Математическое моделирование систем массового обслуживания

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

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

Поэтому характеристиками (показателями) эффективности СМО могут быть:

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

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

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

среднее время ожидания в очереди; закон распределения времени ожидания;

среднее количество заявок, находящихся в очереди; закон распределения числа заявок в очереди; средний доход, приносимый СМО в единицу времени.

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

265

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

Простота модели СМО обеспечивается только при реализации марковского подхода. Его суть состоит в следующем.

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

4.5.1. Классификация СМО

По дисциплине обслуживания, как самой главной функциональной характеристике СМО, все системы разделяются на:

системы с отказами (телефонная сеть); системы с ожиданием (очередью).

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

Важнейшую роль для модели СМО имеет вид входного потока заявок. Поэтому с его основными характеристиками следует познакомиться.

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

266

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

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

При пуассоновском потоке интервалы времени t между событиями (заявками) распределены по показательному (экспоненциальному) закону

f (t)= l e- l t ,

где λ – интенсивность потока.

Показательный закон имеет замечательное свойство, определившее его фундаментальную роль в моделях СМО. Оно следующее: если после очередного события прошло некоторое время τ, то закон распределения оставшейся части промежутка времени Q = T - t остаѐтся неизменным, то есть показательным. То есть события, распределѐнные по показательному распределению, являются максимально независимыми. Это свойство показательного распределения широко используется в моделировании СМО, в которых входной поток и поток обслуживания распределены по показательному распределению.

4.5.2. Одноканальная СМО с отказами

Это простейшая модель, наглядная для понимания и изучения. Пример еѐ – однопроводная (безчастотного уплотнения) телефонная связь.

267

Интенсивность поступления заявок, в общем случае, зависит от времени l = l (t). Обслуживание заявки продолжается в течение

случайного времени Тоб, распределѐнного, как и входной поток, по показательному закону

f(t)= me- mt .

Вэтом случае состояние СМО можно представить двумя позициями:

λ

μ

канал «свободен» S0 и канал «занят» S1. Это называется размеченным графом системы.

Вероятности нахождения СМО в этих позициях (состояниях) соответственно равны p0(t) и p1(t), при условии p0 (t)+ p1 (t)= 1.

Поведение такой системы (из-за марковского приближения) описывается уравнениями А.Н.Колмогорова

dpdt0 = - l p0 + mp1 , dpdt1 = - mp1 + l p0 ,

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

или S1.

Кроме системы дифференциальных уравнений необходимо учитывать условие p0 + p1 = 1 . Поэтому система разрешается даже при отсутствии второго уравнения следующим образом.

Подставив в первое уравнение вместо p1 = 1- p0 , получим

dp

dt0 = - l p0 + m(1- p0 ) или

268

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

ность отказа, то есть средняя доля необслуженных заявок равна

269

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

Пример. Одноканальная СМО с отказами представляет собой одну телефонную линию. Заявка - вызов, пришедший в момент, когда линия занята, получает отказ. Интенсивность потока вызовов λ = 0,8 (вызовов в минуту). Средняя продолжительность разговора tоб = 1,5 мин . Все потоки событий - простейшие. Определить пре-

дельные (при t ® Ґ ) значения:

1)относительной пропускной способности q;

2)абсолютной пропускной способности А;

3)вероятности отказа Pотн.

Сравнить фактическую пропускную способность СМО с номинальной, которая была бы, если бы каждый разговор длился в точности 1,5 мин, и разговоры следовали бы один за другим без перерыва.

Решение. Определяем параметр μ потока обслуживаний: m= 1tоб = 11,5 = 0, 667 .

Согласно приведѐнной выше формуле получаем относительную пропускную способность СМО:

Таким образом, в установившемся режиме система будет обслуживать около 45% поступающих вызовов.

Далее находим абсолютную пропускную способность:

A = l q = 0,8Ч0, 455 » 0,364 ,

т. е. линия способна осуществить в среднем 0,364 разговора в минуту.

Вероятность отказа:

Pотк = 1- q = 0,545 ,

значит, около 55% поступивших вызовов будет получать отказ. Номинальная пропускная способность канала:

A = 1 = 0, 667 (разговора в минуту) ,

270