close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
КАФЕДРА «ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ»
Математическое
моделирование и
Теория принятия решений
Пособие
СОСТАВИТЕЛЬ В.А. БОГАТЫРЕВ
Санкт-Петербург
2014
1.ВВЕДЕНИЕ
Целью
преподавания
дисциплины
«Имитационное
моделирование» является обучение студентов:
основным принципам и методам построения аналитических и
имитационных моделей массового обслуживания информационных
и телекоммуникационных систем;
основным принципам и методам построения аналитических и
имитационных
моделей
надежности
информационных
и
телекоммуникационных систем;
инструментальным средствам разработки и исследования
аналитических и имитационных моделей массового обслуживания
и надежности информационных систем;
методам и способам моделирования при расчете показателей
надежности
и
производительности
информационных
и
телекоммуникационных систем;
методам формирование критериев при проектировании и
эксплуатации систем в условиях многокритериальности. риска и
неопределенности
методам при проектировании и эксплуатации систем в выбора
и оптимизации систем в условиях многокритериальности. риска и
неопределенности
В результате изучения дисциплины студент должен:

знать основные принципы построения аналитических и
имитационных моделей надежности и массового обслуживания
применительно к задачам анализа, проектирования и оптимизации
информационных систем
 Уметь применять моделирование для решения типовых
задач проектирования и сервиса информационных систем.
 Владеть навыками аналитического и имитационного
моделирования с использованием инструментальных средств
современных систем компьютерной математики и имитационного
моделирования.
2. МАРКОВСКИЕ МОДЕЛИ ПРОЙЕССОВ И СИСТЕМ
2.1. ОРИЕНТИРОВАННЫЙ ГРАФ СОСТОЯНИЯ СИСТЕМЫ.
МАРКОВСКИЕ ПРОЦЕССЫ.
Вероятностные (стохастические) модели используются для
исследования таких систем, процесс функционирования которых
определяется случайными факторами. Учет случайных факторов
является обязательным при исследовании процессов применения,
эксплуатации, ремонта и обеспечения технических комплексов, при
оценке их эффективности, разработке автоматизированных систем
управления, обосновании технических требований к системам и так
далее.
В данной главе рассматриваются дискретные системы с
непрерывным временем. Возможные состояния такой системы S0, S1, S2,
… можно перечислить (перенумеровать), а переход ее из одного
состояния в другое возможен в любой, наперед неизвестный, случайный
момент времени, причем этот переход осуществляется скачком
(мгновенно). Число состояний системы может быть как конечным, так и
бесконечным (но счетным).
Множество S={S0, S1, S2, …} возможных состояний системы и
множество возможных ее переходов из одного состояния в другое
удобно представлять в виде ориентированнного графа (рис 2.1.),
вершинам которого соответствуют состояния системы, а дугам –
возможные переходы, причем направление дуги указывает, из какого
состояния и в какое возможен переход системы. Процесс
функционирования системы в данном случае можно представить как
случайное перемещение (блуждание) точки, изображающей систему, по
графу состояний. Характерной особенностью стохастических систем
является то, что для любого момента времени t нельзя однозначно
указать, в каком из состояний находится система, а можно определить
только распределение вероятностей для состояний, то есть определить
значения вероятностей Pk(t) того, что в момент времени система
находится в состоянии Sk..
Так как в любой момент времени t система обязательно находится
в одном из возможных ее состояний, то при t любом справедливо
нормировочное условие:
N
Pk t
1,
k 0
где N+1 – число возможных состояний системы.
(2.1)
Совокупность функциональных соотношений и логических
условий, позволяющих вычислить значение вероятностей Pk(t) для
k=0,N, и представляет
10=
21=
собой
вероятностную
модель системы.
Из
изложенного
01=2
12=
следует,
что
при
разработке
модели
S0
S1
S2 системы
необходимо
прежде всего определить
Рис. 2.1.
множество S ее возможных
состояний и дать описание законов, в соответствии с которыми она
переходит из одного состояния в другое.
Множество S можно определить, во-первых, как множество
допустимых комбинаций возможных состояний элементов системы.
Важным при этом является анализ и учет взаимосвязей между
элементами системы.
Во-вторых, каждое состояние системы можно охарактеризовать
численными значениями одного или нескольких ее параметров, т.е.
множество возможных комбинаций численных значений параметров
системы. Этот подход более целесообразен, так как набор параметров,
характеризующих состояние системы, определяют не только исходя из
природы системы, но и с учетом цели проводимого исследования.
Оба указанных подхода не исключают, а наоборот, дополняют
друг друга, так как на основе анализа возможных состояний элементов
системы можно определить ее параметры.
Чтобы выявить и описать закономерности перехода системы из
одного состояния в другое, каждый переход удобно рассматривать как
результат воздействия на систему некоторого случайного потока
событий.
Поток – это последовательность однородных событий, следующих
одно за другим в случайные моменты времени (например, поток отказов
технических систем, поток сообщений, поступающих в АСУ, и тому
подобные).
Наиболее
важными
свойствами
потоков
являются
:
стационарность, ординарность и отсутствие последействия.
Стационарность потока означает, что его вероятностные
характеристики не зависят от времени. Важнейшей характеристикой
потока является его интенсивность
– среднее число событий в
единице времени. Для стационарного потока
=const, а для
нестационарного = (t) – функция времени.
Ординарность потока означает практическую невозможность
появления двух и более событий в один и тот же момент времени.
Отсутствие последействия означает, что события появляются в
потоке независимо друг от друга, т.е. вероятность появления
определенного числа событий за некоторый произвольно выбранный
промежуток времени не зависит от того, сколько событий произошло
раньше (не зависит от предыстории изучаемого потока).
Поток событий, обладающий всеми тремя свойствами, называется
простейшим или стационарным пуассоновским потоком. Число
событий пуассоновского потока, попадающих на любой участок,
распределено по закону Пуассона, то есть вероятность попадания ровно
k событий на участок (t0, t0+ )
ak
(2.2)
Pk
e a , k 0,1,2,...,
k!
где а – среднее число событий, приходящихся на участок . Для
простейшего потока а= , а для нестационарного пуассоновского
t0
a
t dt .
t0
Определим закон распределения F(t) интервала времени между
событиями. Так как F(t) – вероятность того, что на участок
длительности t попадает хотя бы одно событие, то
F(t)= 1–P(0)=1–e- t
(2.3)
- t
f(t) = F’(t)= e , t 0.
Таким образом, закон распределения интервалов времени между
событиями
простейшего
потока
является
экспоненциальным
(показательным).
Математическое ожидание Mt (средняя длительность интервала
между событиями), дисперсия Dt и среднее квадратическое отклонение
распределенной по показательному закону,
t случайной величины,
определяются соотношениями
1
1
1
.
(2.4)
Mt
te t dt
; Dt
;
t
2
0
Экспоненциальное распределение обладает замечательным
свойством «не помнить о прошлом»: если рассматриваемый
промежуток времен уже «длился» некоторое время, то это никак не
влияет на закон распределения оставшейся части этого промежутка. Это
означает, что вероятность появления события в течение некоторого
интервала времени не зависит от того, сколько времени прошло после
появления предыдущего события, а среднее время ожидания этого
события также не зависит от того, с какого момента времени мы его
ожидаем.
Простейшие потоки событий довольно часто встречаются на
практике, так как суммарный поток, образующийся при взаимном
наложении достаточно большого числа стационарных и ординарных
потоков с последействием (что часто имеет место на практике), является
простейшим.
Из сказанного следует: если переход системы из состояния Si в
состояние Sj происходит под воздействием L простейших потоков
интенсивности t l 1, L , то
L
ij
l
.
l 1
Таким образом, каждой дуге (i,j) графа состояний можно
поставить в соответствие интенсивность суммарного потока событий ij.
Такой граф называется размеченным, и ему соответствует квадратная
матрица интенсивностей переходов ij порядка (N+1, N+1), причем
ij
0 . Для размеченного графа состояний (рис 2.1) имеем
0
0
01
0
ij
10
12 .
0
0
21
.
2.2.
Уравнения
Колмогорова
для
вероятностей
состояний
Введем обозначения:
Pk(t) – вероятность того, что система в момент времени t
находится в состоянии Sk(k=0, 1, 2, …, N);
Pik( t) – условная вероятность того, что система, будучи в момент t
в состоянии Si, за время перейдет в состояние Sk(k i).
Так как Pik( t) – вероятность появления хотя бы одного события за
время t, то
Pik t 1 e ik t ,
где ik – интенсивность потока событий, под воздействием которого
система переходит из состояния Si в состояние Sk .
Разлагая показательную функцию в ряд Тейлора, имеем:
Pik
t
1
1
ik
t
lim
t
t
ik
2
ik
2!
Pik
0
t
3!
ik .
t
t
3
... ;
(2.5)
Пусть в момент времени t система находится в одном из
возможных состояний. Определим вероятность Pk(t+) того, что в
момент t+ t она будет находиться в состоянии Sk (k=0,1,…,N).
Предположим, что за время
t система может только один раз
изменить свое состояние. Это означает, что система может попасть в
состояние Sk двумя способами.
1.
В момент t система находилась в одном из состояний Si(i k),
которое соединено дугой (i, k) с состоянием Sk , а за время t перешла в
состояние Sk . Вероятность этого события
P1
Pi t Pik t ,
i ,k Vk
где Vk – множество дуг, заходящих в вершину Sk . Например, для
состояния S1 (рис. 2.1) Vk
0,1 , 2,1 ,
P1=P0(t)P01( t)+P2(t)P21( t) .
2.
В момент t система находилась в состоянии Sk и за время t
не вышла из него ни по одной из дуг, исходящих из вершины Sk..
Вероятность этого события
P2
Pk t 1
Pki
t ,
k ,i Vk
где Vk – множество дуг, исходящих из вершины Sk . Для состояния S1
(рис. 2.1) Vk
1,0 , 1,2 ,
P2=P1(t)[1–P10( t)–P12( t)] ,
где [P10( t)+P12( t)] – вероятность того, что система, будучи в момент t
в состоянии S1, за время
t перейдет из него в состояние S0 или S2.
Так как оба способа несовместны, то
Pk t
t
Pi t Pik
t
Pk t 1
i ,k Vk
Pki
t ,
i ,k Vk
(2.6)
k 0,1,..., N .
Перенесем Pk(t) в левую часть и разделим все члены уравнения
(2.6) на t, получим
Pk t
t Pk t
P t
Pki t
.
Pi t ik
Pk t
t
t
t
i ,k Vk
i ,k Vk
В результате предельного перехода при t 0 с учетом выражения
(2.5) получим систему дифференциальных уравнений Колмогорова
dPk t
Pk t
ik Pi t
ki ,
dt
(2.7)
i ,k Vk
i ,k Vk
k 0,1,..., N .
Уравнение (2.7) в отличие от уравнения (2.6) является точным, так как
члены, соответствующие двум и более переходам системы за время t и
опущенные в выражении (2.6), в результате предельного перехода
обращаются в нуль. Действительно, пусть за время t система может
перейти из состояния Si в состояние Sk через состояние Sj. Условная
вероятность этого события с учетом формулы (2.5)
2
Pij t Pjk t
ij jk t ;
lim
t
0
Pij
t Pjk
t
t
lim
t
ij
jk
t
0.
0
При записи правой части уравнения (2.7) целесообразно
руководствоваться мнемоническим правилом : «то, что втекает,
прибавляется, а что вытекает – вычитается».
Для рассматриваемого примера (рис 2.1) уравнения Колмогорова
имеют вид (читателю рекомендуется записать их самостоятельно)
dP0 t
P1 t 2 P0 t ;
dt
dP1 t
2 P0 t
P2 t
P1 t ;
dt
dP2 t
P1 t
P2 t .
dt
Интегрируя систему линейных дифференциальных уравнений
(2.7) с учетом условия нормировки (2.1) при заданных начальных
условиях (например, Pk(0)=1, а для всех i k Pi(0)=0 – в начальный
момент система находится в состоянии Sk), можно определить
распределение для вероятностей состояний системы в любой момент
времени.
На практике часто наибольший интерес представляет поведение
системы в установившемся режиме при t
. Здесь сразу же возникает
вопрос, как поведут себя вероятности Pk(t) при t
, стремятся ли они к
каким либо пределам, существует ли в системе некоторый
установившийся (стационарный) режим.
Предельные вероятности Pk lim Pk t существуют и не зависят
t
от начального состояния системы, если граф ее состояний конечен и
существует маршрут между любой парой его вершин, то есть система
может перейти из каждого состояния в любое другое за конечное число
шагов. Такие системы называют эргодическими.
Предельная вероятность Pk – это средняя доля времени, в течение
которого система находится в состоянии Sk . Если, например, Pk=0,3, то
это означает, что в состоянии Sk система времени ее функционирования.
Для вычисления предельных вероятностей в уравнениях (2.7)
производные приравнивают нулю и получают систему линейных
алгебраических уравнений
(2.8)
Pk
k 0, N .
ik Pi
ki ,
i ,k Vk
i ,k Vk
Так как система (2.8) однородна, то при вычислении вероятностей
Pk одно из уравнений (2.8) заменяют нормировочным условием
N
Pk
1.
k 0
При
аналитическом
исследовании
удобно
использовать
следующий способ решения системы (2.8): сначала все предельные
вероятности выражают через какую-либо одну, а затем их подставляют
в условие нормировки.
2.3. Рекомендации построения диаграмм состояний и
переходов марковских процессов
При построении марковских моделей рекомендуется давать их
графическое представление в виде графов состояний и переходов,
при этом рекомендуются использовать следующие правила
построения диаграмм:
a) Каждое состояние системы представляется вершиной графа
с идентификатором состояния.
b) Переходы между состояниями системы отмечаются
линиями (ребрами) со стрелками, соединяющими состояния.
c) На линиях переходов указываются соответствующие
интенсивности переходов.
Для системы с одним элементом в простейшем случае
построения модели надежности диаграмма включает два состояния:
работоспособное состояние с интенсивностью отказов λ и
неработоспособное состояние с интенсивностью восстановлений μ
(рис 1.1 а). Стрелка от состояния 0 к состоянию 1 обозначает
появление отказа с вероятностью λΔ(t) в течение времени Δt,
стрелка от состояния 1 к состоянию 0 - завершение восстановления
системы с вероятностью μΔt в течение времени Δt.
Для оценки вероятности безотказности работы R(t) применима
диаграмма, изображенная на рис. 1.1 б), в которой состояние 1
является поглощающим.
Рассмотрим дублированный вычислительный комплекс из
двух идентичных элементов (полукомплексов).
При построении модели надежности выделим следующие
состояния комплекса:
0 –оба полукомплекса работоспособны;
1 - один полукомплекс отказал и осуществляется его
восстановление, а второй комплекс в это время выполняет
функциональные задачи;
2 - оба полукомплекса отказали.
Граф состояний и переходов на рис 1.1 г) соответствует
случаю, когда после отказа двух элементов простои на
восстановление допустимы так как они не приводяк к
катастрофическим последствиям. Граф состояний и переходов на
рис 1.1д) соответствует случаю, когда после отказа двух элементов
простои на восстановление не допустимы, так как они не приводят
к катастрофическим последствиям. Например при управлении в
реальном времени функциональные задачи не могут быть
выполнены в реальном времени, управляемый объект теряет
управлении что приводит к катастрофическим последствиям , после
чего восстановление управляющего дублированного комплекса уже
становится не актуальным.
а)
б)
в)
г)
е)
д)
ж)
Рис. 1.1. Диаграмма состояний и переходов для системы с
одним элементом
Для дублированного вычислительного комплекса возможны
отказы, приводящие его из полностью работоспособного состояния
0 сразу в состояния 2 (состояние поглощения), в котором
восстановление не производится. Такой случай возможен,
например, при отказе общего для двух полукомплексов блока
электропитания, в результате чего выполнение функциональных
задач в реальном времени становится не возможным. Диаграмма,
соответствующая описанному случаю представлена на рис.1.1 д).
Диаграмма по рис. 1.1 д) может использоваться при анализе
надежности встроенного контроллера, в котором имеется
возможность заменить резистор, но нет возможности восстановить
отказавшую микросхему (нет запасных элементов или нет
технологических возможностей выпаять отказавшую микросхему и
на ее место впаять исправную). Отказ резистора вызывает переход
в состояние 1, а отказ микросхемы в состояние 2. Состояние 2
является поглощающим.
Если для рассмотренного случая ремонт в состоянии 2 все же
возможен, но он более сложен и соответственно выполняется с
меньшей интенсивностью восстановления, то описанный процесс
моделируется диаграммой, представленной на рис 1.1 е).
В реальных системах возможно некоторое запаздывание
восстановления после возникновения отказа, что может
обусловливаться задержкой обнаружения отказа системой контроля
или задержкой вызова ремонтников. На рис. 1.1 ж) отображен
случай, когда восстановление проводится только после отказа двух
элементов.
При рассмотрении элемента в одном из двух состояний 0
работоспособном (0) либо неработоспособном (1), для системы из
двух неидентичных элементов (различающихся по интенсивностям
отказов и восстановлений) возможны четыре состояния 0, 1, 2, 3.
Если элементы соединены последовательно, то система имеет
одно работоспособное состояние 0, а состояния 1, 2, 3 неработоспособны. При параллельном соединении элементов
состояния 0, 1, 2. являются работоспособными, а состояние 3 неработоспособно.
Диаграмма состояний и переходов невосстанавливаемой
системы (последовательной или параллельной) с двумя элементами
изображена на рис 1.2 а), а восстанавливаемой системы на рис.1.2
б). Диаграмма состояний и переходов по рис. 1.2 в) соответствует
случаю, когда ремонт может быть начат сразу после отказа без
организации очереди на восстановление элементов (число двух
ремонтников два).
а)
б)
г)
в)
Рис.1.2. Диаграмма состояний и переходов системы с двумя
элементами
В диаграммах состояний и переходов системы могут быть учтены
стратегии восстановления. При ограниченном восстановлении,
когда ремонтируется в каждый момент времени только один
элемент (имеется один ремонтник) возможны различные
дисциплины
восстановления
(стратегия
технического
обслуживания). Например, возможно в третьем состоянии
ремонтировать всегда первый элемент. Вводя дополнительные
состояния на диаграмме (на рис 1.2 г) состояние 3 - два компонента
отказали, первым отказал компонент 1; состояние 4 - два
компонента отказали, первым отказал компонент 2) можно учесть
дисциплину технического обслуживания, при которой в состоянии
отказа двух элементов продолжается восстановление элемента,
отказавшего первым (ремонт которого соответственно начат
раньше).
Приведем примеры построения диаграмм состояний и переходов
для различных дисциплин восстановления (технического
обслуживания) системы дублированных элементов. На рис.1.3 а)
представлена диаграмма состояний и переходов для случая, если
восстановление системы реализуется только после отказа обоих
дублированных элементов. Система
функционирует, после
восстановления одного элемента, он начинает выполнять
функциональные задачи, но при этом возможны отказы.
Одновременно с функционированием восстановленного элемента
другой элемент системы продолжает восстанавливаться. Если до
полного завершения ремонта двух элементов вычислительный
процесс не возобновлять, то процесс обслуживания будет
представлен диаграммой на рис 1.3. б). Если восстановление
проводится только до первого работоспособного состояния с
переходом в рабочий режим с прекращением дальнейшего
восстановления до исходного состояния, то при приоритете
восстановления первого элемента имеем диаграмму, приведенную
на рис 1.3 в) (следует отметить не рациональность последней
дисциплины обслуживания.
А)
б)
в)
Рис. 1.3. примеры построения диаграмм состояний и переходов
для различных дисциплин восстановления систем
На рис.1.4 представленная диаграмма состояний и переходов для
системы дублированных элементов, не допускающий перерывы
выполнения
функциональных
задач.
Такие
требования,
предъявляются, например, к дублированным управляющим
системам, функционирующим в реальном масштабе времени.
Состояние 3 является поглощающим, так как для него невозможно
управление объектом в реальном времени.
Рис. 1.4. Диаграмма состояний и переходов для дублированных
систем, не допускающих перерывы вычислений
Для систем с дублированием элементов общая причина отказа
может быть отображена прямым переходом с интенсивностью λ3 от
состояния с двумя работоспособными состояниями 0 к состоянию 3
с отказом обоих элементов (рис 1.5 а). Если при отказе по общей
причине двух элементов их восстановление отличается от
восстановления при раздельном отказе элементов, например
интенсивность восстановления при отказе по общей причине
меньше, то при расчете надежности может использоваться
диаграмма по рис.1.5 б). Диаграмма по рис 1.5 может быть
использована для моделирования надежности дублированного
комплекса, когда возможны отказы двух вычислительных машин
по общей причине скачка напряжения в сети электропитания.
б)
а)
Рис. 1.5. Диаграмма состояний и переходов для системы с
общей причиной отказа
При разработке марковских моделей надежности по возможности
число состояний должно минимизироваться, для этого может
использоваться симметричность системы. Например, если в
системе имеются два идентичных элементов, то диаграмма
состояний и переходов может быть приведена к виду на рис. 1.6, на
котором состояние 0 - два элемента работоспособны, состояние 1один элемент работает один отказал и восстанавливается,
состояние 2 – оба элемента отказали один из них
восстанавливается.
Рис 1.6. Упрощение диаграммы состояний и переходов
Для описания случайного процесса перехода состояний
(отказ/восстановление) применяют вероятности состояний P1(t),
P2(t), … , Pi(t), … , Pn(t), где Pi(t) – вероятность нахождения системы
в момент t в i-м состоянии. Очевидно, что для любого t
n
Pi (t )
1.
i 1
Рис. 1.7. Диаграмма состояний и переходов
По графу состояний (рис. 1.7) составляется система
обыкновенных дифференциальных уравнений первого порядка
(уравнений Колмогорова – Чепмена) по следующему правилу:
а) для i-го состояния в левой части записывается производная
по времени t от Pi(t);
б) в правой части число членов равно числу стрелок,
соединяющих рассматриваемое состояние с другими состояниями;
в) каждый член правой части равен произведению
интенсивности перехода на вероятность того состояния, из
которого выходит стрелка;
г) знак произведения положителен, если стрелка входит
(направлена острием) в рассматриваемое состояние, и отрицателен,
если стрелка выходит из него.
dPi (t )
λli Pl (t ) Pi (t )
λij .
dt
l a,b,...,c
j d,g,...,z
Для решения системы дифференциальных уравнений для
вероятностей состояний P1(t), P2(t), …, Pi(t), …, Pn(t), задается
начальное значение вероятностей P1(0), P2(t), …, Pi(0), …, Pn(0).
Если в начальный момент t = 0 состояние системы известно,
например, S(t=0) = Si, то Pi(0) = 1, а вероятности остальных
состояний равны нулю.
Для системы из одного элемента с диаграммой состояний и
переходов по рис 1.8. система дифференциальных уравнений для
вероятностей состояний имеет вид
λP0 t
λP0 t
dP0 t / dt
dP1 t / dt
μP1 t ;
μP1 t .
Рис.1.8. Диаграммы состояний для одного элемента
Рассмотрим системы с дублированием элементов, для первой из
которых (рис. 1.9 а) восстановление проводится всегда, а для
второй (рис. 1.9.б) после достижения состояния полного отказа
(отказ двух элементов) восстановление не производится.
Для
рассматриваемых
восстанавливаемых
систем
с
дублированием элементов, диаграммы которой представлены на
рис. 1.9. а) и б), выделим следующие состояния:
11 – оба элемента работоспособны,
01 - отказал первый, второй работает,
10 - отказал второй, первый работает;
00 – оба элемента отказали.
а)
б)
Рис.1.9. Диаграммы состояний и переходов для системы с
дублированием элемента
Система дифференциальных уравнений для определения
вероятностей состояний системы по рис. 4.3 а) имеет вид:
dP11 t / dt
λ1 + λ2 P11 t
μ1P01 t
P t
μ1 + λ2 P01 t ;
P t
λ1 +
dP01 t / dt
1 11
dP10 t / dt
2 11
dP00 t / dt
λ2 P01 t
2
P10 t
μ2 P10 t ;
μ1P00 t ;
λ1P10 t - μ1P00 t .
Система дифференциальных уравнений для системы по рис. 4.3
б) записывается как:
λ1 + λ2 P11 t
dP11 t / dt
μ1P01 t
P t
μ1 + λ2 P01 t ;
P t
λ1 +
dP01 t / dt
1 11
dP10 t / dt
2 11
dP00 t / dt
λ2 P01 t
2
μ2 P10 t ;
P10 t ;
λ1P10 t .
С помощью полученных выражений можно рассчитать
вероятность
работоспособного
состояния
и
отказа
восстанавливаемого объекта в любой момент t. Для этого после
нахождения вероятностей всех работоспособных состояний
достаточно их просуммировать. Так для представленных на рис. 1.9
дублированных систем, учитывая, что для параллельного
соединения элементов, система работоспособна для состояний 11,
01 и 10, получаем функцию надежности (нестационарный
коэффициент готовности) как:
Pс t
P11 t
P01 t
P10 t ;
Коэффициент готовности системы kг. определяется для
стационарного (установившегося) режима (для произвольного
достаточно удаленного от начала работы момента времени t
∞).
В установившемся режиме Pi(t) =Pi = const, поэтом dPi(t)/dt = 0 и
системы
дифференциальных
уравнений.
соответствующие
диаграммам состояний и переходов преобразуются в системы
алгебраических уравнений с нулевыми левыми частями, поскольку
dPi(t)/dt = 0.
Таким образом, для определения вероятностей состояний
системы в установившемся режиме, диаграмма состояний которых
имеет n вершин требуется составить алгебраические уравнения для
(n-1) –й вершины добавив уравнение
n
Pi 1.
i 0
Так для системы из одного элемента ( рис. 1.8)получаем:
0
P0 P1;
0 P0 P1.
С учетом того что: P0 + P1 = 1.
При этом система работоспособна при работоспособности
единственного элемента , а поэтому kг = P0.
Система дифференциальных уравнений, приведенная выше,
преобразуется в систему алгебраических уравнений
0
λ1 + λ2 P11
μ1P01
P
μ1 + λ2 P01;
P
λ1 +
0
1 11
0
2 11
0
λ2 P01
2
P10
μ2 P10 ;
μ1P00 ;
λ1P10 - μ1P00 ,
с учетом того что P11 P01 P10 P00 1;
При этом коэффициент готовности вычисляется как:
kг = P11
P01
P10 .
Рассмотрим методологию решения систем алгебраических
уравнений
с
использованием
инструментальных
средств
компьютерной математики, на примере системы математических
расчетов Mathcad.
Алгебраические уравнения в Mathcad решаются как
численными, так и аналитическими методами.
2.3. СРЕДСТВА КОМПЬЮТЕРНОЙ МАТЕМАТИКИ ДЛЯ
ИССЛЕДОВАНИЯ МАРКОВСКИХ ПРОЦЕССОВ
Решение систем линейных алгебраических уравнения с
помощью вычислительного блока Given/find.
При решении систем линейных уравнений используется
вычислительный блок, Given - find.
Блок Given - find для решения алгебраических уравнений
имеет следующую структуру:
Given
Уравнения
Ограничительные условия выражения с функцией
Find(x1, x2,…,xn)- встроенная функция для решения системы
уравнения относительно переменных x1, x2,…,xn.
Вставлять логические операторы «=» при наборе уравнений
следует с логической панели Boolean . Для вывода результата после
набора Find(x1, x2,…,xn) следует ввести оператор « » с панели
«Вычисления»
Пример символьного решения системы алгебраических
уравнений приведен на рис 1.10, а численного решения - на рис
1.11.
Рис. 1.10. Пример
алгебраических уравнений
символьного
решения
системы
Рис.
1.11.
Пример
алгебраических уравнений
численного
решения
системы
Решение системы линейных алгебраических уравнений
возможно в матричной форме на основе вычислительного блока
Given/find (рис 1.12)
Рис.1.12. Решение системы линейных алгебраических
уравнений матричной форме с помощью блока Given / find
Решение систем линейных алгебраических уравнений с
помощью функции Isolve.
Для использования встроенной функции Isolve решаемая
система уравнений записывается в матричном виде, при этом
формат функции Isolve (А.b), где А матрица коэффициентов
системы, b- вектор правых частей. Листинг рассматриваемого
примера решения системы уравнений приведен на рис. 1.13.
Функция Isolve (А.b) позволяет получить символьное решение (рис.
1.14) для чего используется знак « » с панели Symbolic.
Рис. 1.13. Численное решение системы уравнений с помощью
функции Isolve
Рис. 1.14. Символьное решение системы уравнений с
помощью функции Isolve
2.3. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ (СМО)
2.3.1. Общая характеристика СМО
Основными признаками реальной системы, позволяющими
рассматривать ее как своеобразную СМО, являются :
– наличие объектов, нуждающихся в случайные моменты
времени в обслуживании (в выполнении некоторых работ над
собой или для себя); эти объекты порождают так называемый
входящий поток заявок (требований) на обслуживание;
– наличие объектов, которые производят обслуживание и
называются обслуживающими приборами (каналами);
– возникновение задержек в обслуживании (образование
очереди).
В качестве своеобразных СМО могут рассматриваться: системы
связи и ремонта; пункты технического обслуживания; вычислительные
центры и отдельные ЭВМ: автоматизированные производственные
цехи, поточные линии; транспортные системы; системы материального
обеспечения.
Для задания СМО необходимо указать: входящий поток заявок,
множество обслуживающих приборов и дисциплину обслуживания.
При аналитическом исследовании СМО чаще всего предполагают,
что входящий поток – простейший поток событий интенсивности .
Часто заявку отождествляют с ее материальным носителем : поток
приборов, агрегатов, машин, поступающих на ремонт; поток отчетов,
поступающей в вычислительный центр и так далее
Обслуживающий прибор (канал) – это материальный объект или
совокупность объектов, одновременно участвующих в обслуживании
заявки. В каждый момент времени прибор может обслуживать только
одну заявку.
Основным параметром обслуживающего прибора является
среднее время обслуживания одной заявки t обсл или производительность
1
прибора
. Под временем обслуживания tобсл всегда будем
t обсл
понимать время от момента начала обслуживания заявки до момента
готовности прибора к обслуживанию очередной заявки.
При аналитическом исследовании СМО обычно полагают, что tобсл
– случайная величина, распределенная по показательному закону, то
есть
F0 t
P t обсл t
1 e t;
g t
e t.
Таким образом, каждый обслуживающий прибор при непрерывной
работе порождает поток обслуженных заявок интенсивности .
Отсутствие последействия в данном случае означает, что
вероятность завершения обслуживания заявки в любой момент времени
не зависит от того, сколько времени оно уже продолжалось.
В зависимости от числа обслуживающих приборов и характера
взаимосвязи между ними в процессе обслуживания заявок различают
одноканальные и многоканальные, однофазные и многофазные
системы.
Заявка считается обслуженной системой, если она обслужена
одним из ее приборов.
Если
обслуживание
заявки
должно
осуществляться
последовательно несколькими приборами, то такие системы называются
многофазными. Схема одноканальной многофазной (трехфазной) СМО
изображена на рис. 2.3. Заявка считается обслуженной системой, если
она прошла все фазы обслуживания. Типичными примерами
многофазных СМО являются технологические потоки сборки (ремонта)
приборов, агрегатов или машин.
Дисциплина обслуживания – это совокупность правил поведения
заявки от момента ее поступления в систему до момента прекращения
обслуживания. К основным правилам обслуживания относятся: выбор
свободного прибора, назначение очередной заявки на обслуживание и
дисциплина очереди.
Выбор свободного прибора может осуществляться:
– случайным образом (например, с равной вероятностью);
– в порядке нумерации (наибольший или наименьший номер);
– в зависимости от времени нахождения прибора в состоянии
«свободен» (наименьшее или наибольшее время).
В основе правил назначения очередной заявки на обслуживание
лежит или фактическое время ожидания, или остающаяся часть времени
ожидания. Частными случаями .являются:
– равновероятное поступление на обслуживание любой заявки из
очереди;
– строгая очередность – заявки к обслуживанию назначаются в
порядке поступления;
– обратная очередность – «последним пришел – первым
обслуживается».
Иногда назначение на обслуживание происходит по некоторой
системе приоритетов, (пенсионеры обслуживаются в первую очередь).
Дисциплина очереди определяет, в каких случаях заявка
становится в очередь и когда она покидает систему, и задается в виде
ограничений, накладываемых на параметры СМО: длина очереди
(максимально допустимое число заявок в очереди т), время ожидания
заявки в очереди tож или время пребывания заявки в системе tc(tc=
tож+tобсл).
Ограничение времени ожидания (пребывания) означает, что заявка
может ожидать обслуживания (находиться в СМО) какое-то время, не
превышающее некоторой случайной величины ож( с).
Эти ограничения определяют поток заявок, уходящих из очереди
(системы) необслуженными. Обычно предполагают, что этот поток –
простейший поток событий интенсивности
v 1 / ож ;
v 1/ c ,
где
– среднее допустимое время ожидания (пребывания).
ож с
Следует подчеркнуть, что дисциплина очереди не является чем-то
внешним по отношению к заявкам. Наоборот, чаще всего указанные
ограничения определяются характером заявок.
В зависимости от совокупности ограничений, накладываемых на
параметры СМО, различают:
– СМО с отказами – образование очереди не допускается; заявка,
заставшая все приборы занятыми, покидает систему;
– чистая СМО с ожиданием – любая заявка, поступившая в
систему, будет рано или поздно обслужена (на параметры СМО
ограничения не накладываются);
– смешанные СМО – накладывается ограничение на один из
параметров: т – СМО с конечной очередью; tож(tс) – СМО с
ограниченным временем ожидания (пребывания) или одновременно на
параметры т и tож(tс).
Главная задача исследования СМО – установление связи между
параметрами системы (n – число каналов, m, , , v) и показателями ее
эффективности.
Для решения этой задачи прежде всего необходимо построить
математическую модель системы.
2.3.2. Математическая модель однофазной СМО
и показатели ее эффективности.
1. Математическая модель
Состояние однофазной СМО с абсолютно надежными обслуживающими приборами в любой момент времени полностью определяется
числом заявок k, находящихся в ней. Действительно, если k п, то k
заявок находятся на обслуживании, очереди нет; k приборов заняты
обслуживанием заявок, а n – k приборов свободны. Если k > n, то все
приборы заняты (n заявок обслуживается), а k–п заявок находится в
очереди.
Величина k может принимать значения k=0, 1, 2, . . ., N, где N =
n+m, причем для СМО с отказами m=0, а для систем с неограниченной
очередью т и N
.
Увеличение числа заявок в системе (переход из состояния Sk в
состояние Sk+1) происходит под воздействием потока заявок интенсивности , которая не зависит от k, то есть
(2.9)
k,k+1 = .
Уменьшение числа заявок в системе (переход из состояния Sk в
состояние Sk–1) происходит в общем случае под воздействием потока
обслуживании интенсивности
и потока уходов заявок из очереди
(системы) интенсивности v, причем k,k+1= f(k, n, , v), а вид этой
функции определяется типом СМО.
Из сказанного следует, что однофазной СМО соответствует граф
состояний (рис. 2.4), вершины которого (S0, S1, S2, . . .) образуют
последовательную цепочку и любые две соседние вершины соединены
двумя
встречно
направленными
дугами,
а
процесс
ее
функционирования представляет собой так называемый процесс
«гибели и размножения» (уменьшение и увеличение числа заявок).
10
21
01
S0
12
S1
…
32
23
…
N-2,N-3
N-3,N-2
S2
SN-2
N-1,N-2
N,N-1
N-2,N-1
N-1,N
SN-1
SN
Рис. 2.4
Определим предельные вероятности состояний Рk, для СМО с
конечным числом состояний. Для СМО Pk, – это вероятность того, что в
произвольный момент времени в системе находится ровно k заявок.
В СМО с конечным числом состояний всегда имеет место стационарный режим, так как между любыми двумя вершинами графа
существует маршрут.
Уравнения Колмогорова имеют вид:
– состояние S0
(2.10)
10P1= 01P0
– состояние S1
01P0+ 21P2= 10P1+ 12P1;
учитывая выражение (2.10), получим
(2.11)
21P2= 12P1
– состояние S2
12P1+ 32P3= 21P2+ 23P2;
учитывая формулу (2.11), имеем
(2.12)
32P3= 23P2
— состояние Sk-1 (по аналогии)
(2.13)
k,k-1Pk= k-1,kPk-1
– состояние SN-1
(2.14)
N-1,NPN-1= N,N-1PN .
Для состояния SN непосредственно по графу находим уравнение
N-1,NPN-1= N,N-1PN ,
которое совпадает с уравнением (2.14).
Поэтому последнее уравнение исключаем из /рассмотрения, а
вместо него используем условие нормировки
N
Pk
1.
(2.15)
k 0
Для решения системы уравнений (2.10) – (2.15) выразим все
вероятности Pk k 1, N через Р0 и получим
01
P1
P0 ;
10
12
P2
P1
21
01
12
10
21
P0 ;
(2.16)
..........................................
k 1,k
Pk
Pk
k ,k 1
k
Pk
P0
i 1
01
12
10
21
...
1
i 1,i
,
k
k 1,k
P0 .
k ,k 1
1,2 ,..., N
i ,i 1
Подставляя значения Рд в формулу (2.15), получим
k
N
P0
P0
k 1i 1
N
k
P0
k 1i 1
i 1,i
1,
i ,i 1
(2.17)
1
i 1,i
.
i ,i 1
Обратим внимание на структуру формул (2.16) и (2.17). В формуле
(2.16) имеем произведение отношений интенсивностей перехода слева
направо к интенсивностям перехода справа налево для всех переходов
между начальной и рассматриваемой вершинами графа состояний. В
формуле (2.17) имеем сумму этих произведений, вычисленных для всех
вершин графа S k k 1, N .
Подставляя в формулы (2.16) и (2.17) значения интенсивностей
переходов i,i-1 и i-1,i для СМО любого типа, можно рассчитать
вероятности ее состояний и определить показатели, эффективности.
2. Показатели эффективности.
Эффективность СМО характеризует ее приспособленность к
выполнению задач по обслуживанию заявок. Показатель эффективности
– это количественная мера эффективности, определяющая степень
соответствия результатов функционирования СМО целям (задачам),
стоящим перед системой.
Рассмотрим наиболее часто используемые показатели эффективности СМО.
1. Вероятность отказа в обслуживании Ротк – вероятность того,
что поступившая в систему заявка не будет обслужена. Это очень
важный показатель для СМО.
Абсолютная пропускная способность СМО Q – это среднее число
заявок, обслуживаемых системой в единицу времени. Для оценки
потенциальных возможностей СМО по обслуживанию заявок
используется номинальная пропускная способность системы
Qном n .
3. Относительная пропускная способность q – это средняя доля
заявок, обслуживаемых системой:
Q
q
;
q q .
(2.18)
Величину q можно определить и через Ротк. Действительно, Ротк –
средняя доля времени, в течение которого заявки получают отказ, а
следовательно, и средняя доля заявок, не принимаемых системой на
обслуживание, то есть.
q 1 Pотк .
(2.19)
4. Среднее число занятых приборов
k
NЗ
л 1
kPk ;
Nз
Q
q
q ,
(2.20)
t обсл / t з – параметр обслуживания (среднее необходимое число
где
обслуживающих приборов).
Производными от данного показателя являются коэффициент
занятости (загрузки) приборов Kз и коэффициент их простоя Kп:
Nз
KЗ
q
q;
Kп 1 K з ,
(2.21)
n
n
где – номинальный коэффициент загрузки приборов.
5. Средняя длина очереди L – математическое ожидание числа
заявок, ожидающих обслуживания. Производным от показателей Nз и L
является среднее число заявок, находящихся в системе,
Y=Nз+L.
(2.22)
6. Среднее время ожидания обслуживания t ож – математическое
ожидание времени пребывания заявки в очереди.
7. Среднее время пребывания заявки в системе
*
(2.23)
t c t ож t обсл ,
*
где t ож
– среднее время от момента начала обслуживания до момента
окончания обслуживания ( t *обсл t обсл 1 / ).
8. Экономическая эффективность СМО может быть оценена
средней прибылью, получаемой в единицу времени при функционировании системы :
E c0 Q C ; C n K з c з K п cп сож L c y 1 q ; (2.24)
где c0 – прибыль, получаемая при обслуживании заявки; c – функция
стоимости потерь; cз – стоимость эксплуатации прибора в единицу
времени; сп — стоимость единицы времени простоя прибора; сож –
стоимость потерь, связанных с простаиванием заявка в очереди в
единицу времени; сy – стоимость убытков, связанных с уходом заявки
из системы.
Выбор показателя для оценки эффективности конкретной СМО
определяется как особенностями системы (ее типом) и ее назначением,
так и задачами проводимого исследования.
Определим показатели эффективности для СМО рассматриваемых
типов, при этом сначала рассмотрим систему с конечной очередью, а
затем полученные результаты используем при анализе других систем.
2.3.3. СМО с конечной очередью
СМО с конечной очередью длины т характеризуется тем, что при
поступлении очередной заявки возможны три исхода:
– заявка немедленно принимается на обслуживание, если в системе в данный момент находится k заявок и k<n;
– заявка становится в очередь, если п k<n+m;
– заявка получает отказ и покидает систему, если k=n+m.
Следовательно, в любой момент времени система может находиться в
одном из п+т+1 состояний, то есть множество состояний
S
S k / k 0,1,..., n m .
Увеличение числа заявок в системе происходит только под воздействием потока заявок интенсивности , а уменьшение числа заявок в
системе — только в результате завершения обслуживания одной из
заявок, то есть
k , 1 k n,
, k 0,1,..., n m 1;
k ,k 1
k, k -1
n , 1 k n m
(k занятых приборов порождают поток обслуженных заявок интенсивности k ).
Размеченный граф состояний СМО с конечной очередью для п=3,
т=2 изображен на рис. 2.5.
2
S0
3
S1
3
3
S3(Sn)
S2
S4
S5(Sn+m)
Рис. 2.5
Для определения вероятностей состояний системы в формулы
(2.16) и (2.17) подставим значения
;
i , i n;
λi,i-1 n , i n
i 1,i
i ,i 1
и получим:
– для k n
k
i 1
k
i 1,i
2
i ,i 1
...
i
...
k
k
k
k!
k!
,
;
– для k<n
k
n
i 1,i
k
k n
n
i 1,i
n
k n
n! i n 1 i ,i 1
n! n
n!
Полагая в уравнении (2.17) N=n+m, находим
i 1
.
i ,i 1
k
n
P0
1
k
1
n n m
1 k!
n!
k n
.
(2.25)
k n 1
0
Учитывая, что
/0!=1 и вычисляя сумму т членов геометрической прогрессии со знаменателем , находим
1
m
1
P0
,
1
k
!
n
!
1
k 0
Из уравнения (2.16) находим вероятности состояний
n
k
n
(2.26)
k
Pk
k!
n
Pk
P0 ,
k
n;
(2.27)
k
k n
P0
P, k n
(2.28)
k n 0
n!
n! n
На основании формул (2.25) – (2.28) определим основные показатели эффективности системы.
1. Вероятность отказа в обслуживании – это вероятность того, что
в СМО имеется п+т заявок, то есть
n m
(2.29)
P0
n! n m
Зная Ротк по формулам (2.19) – (2.21), можно вычислить абсолютную и относительную пропускную способность системы, среднее
число занятых приборов, коэффициенты их загрузки и простоя.
2. Вероятность того, что поступившая в систему заявка застанет
все каналы занятыми (не будет немедленно принята на обслуживание),
Pотк
Pn
m
n m
Pож
n 1
Pk
1
k n
n 1
Pk
1 P0
k 0
k
k
0 k!
.
(2.30)
3. Средняя длина очереди
n
m
L
rPn r ; Pn
r
P0 ,
n
!
r 1
где Pn+r – вероятность того, что в очереди находится ровно r заявок
(k=n+r).
Подставляя в полученное выражение Pn+r, находим
r
n 1
m 1
;
(2.31)
nn!
n 1
m
P0 1
m 1 m
L
,
1.
(2.32)
2
nn!
1
4. Среднее время ожидания в очереди определяется как математическое ожидание. Если к моменту поступления заявки в очереди
находится r=0, 1, . . ., т–1 заявок, то она поступит на обслуживание
после завершения обслуживания r+1 заявок, то есть
r 1
;
t ож r
n
m 1r 1
L
.
(2.33)
t ож
Pn r
n
r 0
Среднее время ожидания t ож Lt з – это среднее время накопления очереди длиной L.
Среднее число заявок, находящихся в СМО, и среднее время
пребывания заявки в системе определяются по формулам (2.22) и (2.23)
с учетом формул (2.31) – (2.33).
Из полученных соотношений следует, что показатели Ротк, q, Nз, L,
Y не зависят от конкретных значений и , а только от их соотношения
. Показатели t ож , t c и Q , напротив, чувствительны к изменению не
только параметра , но и к изменению при =const. Так, например,
при увеличении
и
в два раза Ротк, q, NЗ и L не изменяются, Q
увеличивается, а t ож уменьшается в два раза, то есть при
L
P0 1 2
... m
одновременном увеличении плотности потоков заявок и обслуживании
характеристики процесса обслуживания улучшаются.
2.3.4. СМО с отказами
СМО с отказами является частным случаем СМО с конечной
очередью при m=0. Полагая в формулах (2.25) – (2.29) т=0, найдем
показатели эффективности СМО с отказами:
– вероятность простоя всех обслуживающих приборов из выражения (2.26)
1
k
n
;
(2.34)
k
!
k 0
– вероятность того, что в системе находится k заявок, из формулы
(2.27)
P0
k
(2.35)
P0 , k 1,2,..., n ;
k!
– вероятность отказа в обслуживании из выражения (2.29)
Pk
n
n
k
1
;
(2.36)
n! k 0 k !
– абсолютная и относительная пропускная способность системы и
среднее число занятых приборов
q 1 Pотк ; Q
q; N з
q
1 Pотк
(2.37)
Зависимости (2.34) – (2.36) были впервые получены датским
инженером А.К.Эрлангом и поэтому известны как формулы Эрланга.
Советский ученый Б.А.Севастьянов доказал, что формулы Эрланга
справедливы при любом законе распределения времени обслуживания,
но при конечном и постоянном значении его математического
ожидания. Это позволяет использовать соотношения (2.34) – (2.37) для
решения широкого класса практических задач.
Pотк
Pn
2.3.5. Чистая СМО с ожиданием.
Чистая СМО с ожиданием характеризуется тем, что любая заявка,
поступившая в систему, будет обязательно обслужена (Ротк=0).
Вероятности состояний для этой системы можно получить из уравнений
(2.25) – (2.28) в результате предельного перехода при т
.
k n
Так как сумма
в формуле (2.25) сходится только при <1,
k n 1
то в рассматриваемой системе стационарный режим имеет место только
при <1; если
1, то очередь неограниченно возрастает. Так как
m
0 при <1, то из выражения (2.26) находим
lim
m
n
k
1
n
n 1
k
1
n
,
(2.38)
k
!
n
!
1
k
!
n
!
1
k 0
k 0
Вероятности состояний системы Рk, рассчитываются по формулам
(2.27) и (2.28), где Р0 вычисляется по формуле (2.38).
Показатели эффективности чистой СМО с ожиданием:
– относительная и абсолютная пропускная способность системы
из формулы (3.19) при Ротк=0
q=1; Q= ;
(2.39)
– среднее число занятых каналов
Q
;
(2.40)
Nз
; Kз Nз / n
P0
– вероятность того, что заявка, поступившая в систему, будет
ожидать обслуживания, из формул (2.30) и (2.38)
n 1
k
n 1
k
n
1
n
P0
; (2.41)
k k 0 k ! n! 1
n! 1
– средняя длина очереди, как следует из формулы (3.32) при
т
,
n 1
P0
1
L
Pож
;
(2.42)
2
nn! 1
1
– среднее время ожидания
Pож
L
;
(2.43)
t ож
1
– вероятность пребывания заявки в очереди более t единиц
времени
(2.44)
P t ож t Pож e n t .
Методику вычисления рассмотренных показателей эффективности
СМО поясним на примере.
На пункте технического обслуживания (ПТО) оборудованы две
линии по обслуживанию техники. Время обслуживания одной единицы
техники распределено по показательному закону с параметром
t обсл 2 ч. Число единиц техники, одновременно находящихся на ПТО,
не должно превышать четырех единиц. Поток техники на обслуживание
простейший поток заявок интенсивности
=0,5ед./ч. Определить
показатели эффективности работы ПТО.
Решение. Анализ задачи показывает, что ПТО можно рассматривать как СМО с конечной очередью, параметры которой n=2,
m=2, =0,5 ед./ч, =0:5 ед./ч, = 1, =0,5.
Pож
1
k 0
Результаты вычислений для различных значений п и т (различных
вариантов организации ПТО) приведены в табл. 2.1.
Расчет показателей СМО целесообразно производить в последовательности, указанной в таблице. Если =1 (для п=1, m=3), то Р0 и L
рассчитывают непосредственно по формулам (2.25) и (2.31).
Из полученных данных видно, что уменьшение п при постоянном
значении п+т=4 позволяет значительно (в 1,7 раза) повысить
коэффициент загрузки линий Kз Однако эффективность обслуживания
техники значительно снизилась: при п=1 каждая пятая машина
(Ротк=0,2) уходит с ПТО необслуженной, а при n=2 только одна из 25
машин (Ротк=0,044) получает отказ; среднее время пребывания машины
на ПТО при n=1 t c t обсл t ож 4,4 ч , а при п=2 t c 2,344 ч .
Таблица 2.1
Показатели
п=2, т= 2
п=1, т= 3
п=2, т=0
Р0
Pож
Ротк
q = 1–Ротк
Q (ед./ч)
Nз (ед.)
Кз (%)
L (ед.)
t ож (ч)
0,348
0,304
0,044
0,956
0,478
0,956
47,8
0,174
0.348
0,2
0,8
0.2
0,8
0,4
0,8
80
1,2
2,4
0,4
–
0,2
0,8
0,4
0,8
40
–
–
п=2, т
0,333
0,333
0
1,0
0,5
1,0
50
0,333
0.666
Исключение очереди на ПТО (п=2,т=0) приводит к значительному возрастанию вероятности отказа (с 0,044 до 0,2). Отсутствие
ограничения на длину очереди (п=2, m
) несколько повышает
загрузку линий, однако приводит к увеличению времени ожидания
почти в два раза (с 0,348 до 0,666 ч). Для этого случая целесообразно
определить вероятность того, что число машин, одновременно
находящихся на ПТО, превышает 4:
4
1
1
1
Pk 4 1
Pt 1 0,333 1 1
0,215 ,
2
!
2
!
2
2
!
4
i 0
то есть пятую часть времени на ПТО находится более четырех машин
одновременно.
Приведенный пример наглядно показывает важность сравнения
различных вариантов организации СМО и учета при синтезе СМО
экономических показателей.
2.3.6. Смешанные системы массового обслуживания
СМО с ограниченным временем ожидания характеризуется тем,
что уменьшение числа заявок в ней происходит как в результате
завершения обслуживания одной из заявок, так и в результате ухода
заявок из очереди с интенсивностью v.
Если число заявок в системе k<n, то k,k-1= k .. Если в очереди
имеется r заявок (k=n+r), то переход из состояния Sk в состояние Sk-1
осуществляется или в результате завершения обслуживания одной из п
заявок, или в результате ухода из очереди одной из r заявок, то есть
v
n
rv
n r
n
;
k ,k 1
v
t обсл /
ож .
Таким образом, для СМО с ограниченным временем ожидания
k ,
1 k n;
,
(2.45)
k ,k 1
k ,k 1
n r
, k n r , r 1.
Граф состояний системы изображен на рис. 2.6 (п=2).
Подставляя выражения (2.45) в формулы (2.16) и 2.17), как и в
случае СМО с конечной очередью, получим
k
n
n
r
P0
k 0
k!
n!
r 1
1
1
r
n
(2.46)
j
j 1
k
Pk
2
k!
P0 , k
2 +v
(2.47)
n;
2 +2v …
2 +rv
2 +(r+1)v
…
S0
S1
S3
S2 (Sn)
S2+r
Рис.2.6
Pn
n r
r
1
r
P0 n!
n
j
, r
1.
(2.48)
j 1
Определим основные показатели эффективности системы. Средняя длина очереди
1
n
r
P0
L
rPn 1
r r
n j
. (2.49)
n
!
r 1
r 1
j 1
На каждую из L заявок, находящихся в очереди, действует поток
уходов интенсивности v, то есть в среднем в единицу времени из
очереди уходит Lv заявок. Следовательно, абсолютная пропускная
способность
Q
vL ;
(2.50)
относительная пропускная способность
Q
v
q
1
L
(2.51)
вероятность отказа в обслуживании
v
Pотк 1 q
L
L, L
Pотк ;
(2.52)
среднее число занятых приборов
Nз Q /
L
1 Pотк ;
(2.53)
вероятность того, что любая заявка будет обслужена,
Pобсл 1 Pотк q
(2.54)
При вычислениях в формулах (2.46) и (2.49) в качестве приближенного значения для бесконечных сумм берется сумма конечного
числа l–1 членов, а остаток оценивается следующим образом :
r
r 0
l
r
n
j 1
j
l!
l
r
e ;
r l
r
l
r
n
j
l 1!
l
e .
j 1
Из выражений (2.50) – (2.54) следует, что основные показатели
СМО можно вычислить через Ротк, причём для определения Ротк
используют таблицы с тремя входами: n, , .
СМО с ограниченным временем пребывания характеризуется тем,
что заявка может уйти необслуженной как из очереди, так и после
начала обслуживания. Интенсивность перехода данной системы из
состояния Sk в Sk-1 (уменьшения числа заявок)
Подставляя выражения (2.9) и (2.55) в формулы (2.16) и (2.17),
можно определить вероятности состояний данной системы.
Если одновременно накладывается ограничение на время ожидания (пребывания) и длину очереди, то число состояний системы
конечно и равно п+т+1, а интенсивности переходов определяются
формулами (2.45) или (2.55), в которых r = 1, 2, . . ., т. Типичным
примером системы данного типа является вычислительное устройство,
которое может одновременно обрабатывать п сообщений и имеет
буферную память для хранения т сообщений. Поток сообщений –
простейший
сообщения
v
2.7.
1/
c
c
поток интенсивности
, время обработки одного
1
, информация теряет свою ценность через время
. Граф состояний для случая n=2, m=3 изображен на рис.
2.3.7. Особенности применения моделей массового
обслуживания
+v
S0
2 +2v
S1
2 +3v
S2
2 +4v
S3 (S n)
2 +5v
S4
S5 (Sn+m)
Рис.2.7
Рассмотренные модели массового обслуживания находят широкое
применение при исследовании надежности технических систем,
организации их эксплуатации и использования по назначению, а также
при анализе и синтезе автоматизированных систем управления.
Достаточно подробно вопросы практического применения моделей
СМО рассмотрены в работе [1].
При решении прикладных задач необходимо прежде всего правильно определить, насколько аппроксимирующие предположения,
принятые при разработке математических моделей СМО, приемлемы
для реальной системы и каким образом ее специфические особенности
можно учесть в типовой модели.
Основными аппроксимирующими предположениями при разработке моделей СМО были предположения о том, что все потоки
событий являются простейшими. Широкое использование указанных
предположений обусловливается следующими факторами.
1. Простейший поток событий, как уже отмечалось, носит предельный характер и поэтому часто встречается в практических задачах.
Так, например, Н. М. Седякин показал, что поток отказов элементов
технических систем сводится к простейшему, если
n
1
n
2
1
,
(2.56)
0
,
1
2
t
t
i 1 i
i 1 i
где ti – среднее время наработки i-го элемента данного типа на отказ, а п
– число элементов. Если n>10, то это условие выполняется и тогда,
когда каждый из элементов отказывает через постоянные интервалы
времени.
2. Простейший поток заявок ставит СМО в наиболее тяжелые
условия. И. Н. Коваленко показал, что система, рассчитанная на
обслуживание простейшего потока, будет обслуживать любой другой
поток с одинаковой интенсивностью более надежно.
3. При простейшем потоке заявок показатели эффективности СМО
с отказами и ограниченным временем ожидания практически не зависят
от вида закона распределения времени обслуживания, а определяются
его средним значением. Показатели эффективности реальной СМО при
простейшем потоке заявок не хуже значений этих показателей,
вычисленных в предположении об экспоненциальном распределении
времени обслуживания.
4. При указанных предположениях можно получить аналитическую модель системы и на основе ее исследования найти ее оптимальные параметры. Простая модель позволяет разобраться в основных
закономерностях явления, наметить «ориентиры» для построения
статистической модели системы, позволяющей учесть те особенности
реальной системы, которые трудно (или невозможно) учесть при
аналитическом исследовании. Сочетание простых аналитических
моделей и статистического моделирования вероятностных систем на
ЭВМ — один из основных методов современного научного
исследования.
При решении прикладных задач всегда необходимо учитывать
возможность использования результатов исследования стационарного
режима для оценки эффективности системы на конечных интервалах
времени. Характеристики стационарного режима с достаточной для
практики точностью можно использовать для процессов длительностью
(3 4) 1/ [1].
При исследовании СМО предполагалось, что обслуживающие
приборы абсолютно надежны. Если вероятность успешного обслуживания заявки Р<1, то ее влияние на эффективность СМО можно
учесть через Pотк В этом случае
0
Pотк 1 1 Pотк
P,
0
где Р отк — вероятность отказа для системы с абсолютно надежными
приборами (Р=1).
Все рассмотренные модели СМО относятся к классу так называемых разомкнутых систем, в которые поступает неограниченный
поток заявок и его параметры не зависят от процесса обслуживания.
Однако на практике часто встречаются системы, когда поток заявок
ограничен и его параметры зависят от процесса обслуживания
(замкнутые системы).
Типичным примером замкнутой системы является следующая
система. Имеется п ремонтных мастерских, которые предназначены для
обслуживания и ремонта т технических систем. Технические системы
отказывают только в период эксплуатации с интенсивностью
(в
период ремонта =0), производительность каждой мастерской . Число
возможных состояний данной системы m+1 (k=0, 1, 2, ..., т – число
технических систем, требующих ремонта). Граф состояний данной
системы для п=2, т=5 (рис. 2.8) свидетельствует о том, что для ее
исследования нельзя использовать ни одну из рассмотренных моделей
СМО. При ее исследовании необходимо непосредственно использовать
выражения (2.16) и (2.17) для процесса «гибели и размножения».
5
S0
S1
2
2
2
4
3
2
S2
S3 (S n)
2
S4
S5 (Sm)
Рис.2.8
Приведенный пример показывает, что при выборе модели СМО
для решения конкретной задачи ошибки можно исключить, если
построить размеченный граф состояний. На основе анализа размеченного графа состояний в некоторых случаях можно установить, что
для исследования системы, по формальным признакам не относящейся
к системам массового обслуживания, можно использовать одну из
известных моделей СМО.
При решении прикладных задач следует также всегда отличать
показатели эффективности L, t ож , t c от ограничений, накладываемых на
параметры СМО: т, ож , c . Показатели L, t ож , t c используются для
оценки эффективности СМО, а параметры т, ож , c определяются
спецификой процесса обслуживания и физическими свойствами заявок
(например, емкость хранилищ в ремонтном органе, время старения
информации и так далее).
Задачи, решаемые с помощью моделей СМО, можно разделить на
два основных класса. К первому классу относятся задачи анализа
эффективности систем и определения числа обслуживающих приборов,
обеспечивающих требуемые значения показателей ее эффективности.
Ко второму классу относятся задачи определения числа и типа
(производительности) обслуживающих приборов.
2.3. МОДЕЛИ НАДЕЖНОСТИ
2.3.1. Структурная модель надежности
Структурная схема надежности в соответствии с рекомендациями и
пояснениями ГОСТ Р 51901.14-2005 является наглядным представлением
модели надежности системы. Она показывает логическую связь
компонентов, в процессе работы системы.
Методы расчета на основе структурной схемы надежности
предназначены для систем без восстановления, у которых порядок появления
отказов не имеет значения. Для восстанавливаемых невоссанавливаемых
систем у которых порядок появления отказов и восстановлений должен
учитываться, используются другие методы, например на основе Марковских
моделей.
В структурной модели предполагается, что в любой момент времени
элемент системы может находиться только в одном из двух возможных
состояний: исправном или неисправном.
Методы расчета на основе структурной схемы надежности оганичены
предположением о независимости отказов и восстановлений различных
элементов. Это предположение сводится к тому что имеется неограниченное
восстановление , когда на каждый элементможет быть выделен отдельный
ремонтник и ремонтники не мешают друг другу в том числе на оганиченном
пространстве , например замена нескольких эменентов на одной плате .
Структурные методы Другим важным предположением является то, что
отказ (или ремонт) любого блока не влияет на вероятность отказа (или
ремонта) любого другого блока системы. Это означает, что имеются
достаточные ресурсы для обслуживания блоков, нуждающихся в ремонте, и
что любое необходимое количество специалистов может заниматься
восстановлением конкретного блока одновременно, не мешая друг другу.
Таким образом, предполагается, что отказы и ремонт отдельных блоков
являются статистически независимыми событиями. Такое Предположение
статистической независимости событиямиотказов и восстановлений
позволяет использовать рассматриваемые модели для оценки не только
вероятности безотказной работы невосстанавливаемых систем , но и
коэффициента готовности систем с восстановлением.
Структурная модель надежности (структура системы) – логическая
схема взаимодействия элементов, определяющая работоспособность
системы. Графическое отображение элементов системы
однозначно
определяет состояние системы (работоспособное/ неработоспособное) по
состоянию (работоспособное/ неработоспособное) элементов.
По структуре системы могут быть:
система без резервирования (основная система);
системы с резервированием.
При разработке структурной схемы надежности системы
формулируется условие работоспособности (отказа).
При формулировании нескольких условий отказа, структурная
схема надежности представляется для каждого из них.
При
составлении структурной схемы надежности система в соответствии с
процессом функционирования разделяется на блоки (по возможности
число блоков должно быть минимальным), таким образом, чтобы
каждый блок был независимым по отказам.
Схема надежности должна отображать возможные пути,
реализации функций, возложенных на систему. Пути, проходящие от
входа до выхода, включают совокупность элементов (блоков),
работоспособность которых обеспечивает функционирование системы.
Следует обратить внимание, что структура вычислительной
системы может не совпадать со структурой модели надежности, и более
того для одной и той же вычислительной структуры структурная
модель надежности может меняться в зависимости от формулировки
условий работоспособности системы
На рис иллюстрируется представление компьютерной системы,
включающей несколько групп компьютеров (кластеров) разными
схемами расчета надежности (структурные модели надежности), в
зависимости от функциональной однородности компьютеров и
функциональной однородности компьютеров, объединяемых в каждую
группу (кластер).
Рис. Варианты представления структурной схемы надежности
компьютерной системы.
Последовательно-параллельные
структурные
модели
надежности резервированных систем
При общем резервировании, изделие резервируются в целом.
При раздельном (поэлементном) резервировании резервируются
отдельные части изделия.
Основным параметром резервирования является его кратность.
Под кратностью резервирования m понимается отношение числа резервных
изделий к числу резервируемых (основных).
Различают резервирование с целой и дробной кратностью.
При резервировании с целой кратностью величина m есть целое
число, при резервировании с дробной кратностью величина m есть дробное
несокращаемое число. Например, m=3/2 означает наличие резервирования с
дробной кратностью, при котором число резервных элементов равно трем,
число основных – двум , а общее число элементов равно пяти.
Последовательное
соединение
элементов
Если
для
функционирования системы необходимо, работоспособность всех
элементов, то структурная схеме надежности
сводится к
последовательному соединению всех эдементов (рис )..
P1
P2
Pn
Рис. Последовательное соединение элементов
Вероятность
безотказной
работы
системы
при
последовательном соединении для случая независимости отказов
равна произведению вероятностей безотказной работы входящих в
нее элементов:
n
P(t ) P1 t P2 t
... Pn t
Pi t ,
(
i 1
где Pi — вероятность безотказной работы i-го элемента; n —
количество последовательно соединенных элементов.
Для систем из равнонадежных элементов
P(t ) p (t ) n
При постоянной (не меняющейся со временем) интерсивности отказов
элементов :
Pc (t)= e
t
λc
=, λc =
n
λi ,
i=1
Если элементы каждого типа равны по надежности, то :
r
λc =
N i λi ,
i=1
где N i — число элементов i-го типа; r — число типов элементов.
Наработка до отказа системы
надежности равна
из элеменгтов не равной
n
t
T
P(t )dt
e
0
i
i 1
dt
0
Если система построена из n равнонадежных элементов , то
наработка до отказа вычисляется как :
T
e
0
n t
1
n
T ≅ min(Tj ), j = 1,2,...,n ,
Параллельное соединение элементов.
Для параллельного соединения элементов (рис 2), при резервировании с
постоянным
включением
элементов.
Система
сохраняет
работоспособность при исправности хотябы обного из n элементов
Рис - Параллельное соединение элементов надежности при
резервировании с постоянным включением элементов
Вероятность безотказной работы n параллельно соединенных элементов
(кратность резервирования (n-1)/1) вычисляется как
n
P(t ) 1 Q t
1
1 Pi (t ) .
i 1
Для систем из элементов равной надежности
P(t ) 1 (1 p(t )) n
Если система построена из n равнонадежных элементов , то наработка
до отказа вычисляется с учетом что в исходном состоянии,когда все
элементы работоспособны суммарная интенсивность отказов всех n
элементов nλ, после одного отказа суммарная интенсивность отказов n-1
элементов (n-1) λ, и так далее после i отказов (n-i) λ , таким образом
наработка до отказа вычисляется как
n 1
1
1n1 1
.
T
i
i
i 0 n
i 0 n
Для параллельного соединения элементов, при резервировании с замещением .
В рассматриваемых системах в каждый момент времени работоспособного
функционирования системы отказывать может только один элемент с
интенсивностью λ. За рассматриваемое время t вероятность что не будет ни
i
t
t
t
одного отказа e , будет один отказ te , будет i отказов
e t и так
i
далее, таким образом вероятность что в системе из n элементов за время t
сохранит работоспособность хотя бы один элемент
i
i
n 1
t
t
t
t
.
P(t ) e
1 e
i!
i!
i 0
i n
Если система построена из n равнонадежных элементов , то наработка
до отказа вычисляется с учетом что в исходном состоянии,когда все
элементы работоспособны отказывает только один функционирующий
элемент интенсивность отказов
которого λ, после одного
отказа
интенсивность отказов функционирующего элемента λ, и так далее таким
образом наработка до отказа всех n элементов вычисляется как
n
T
При облегченном (теплом) резервировании среднее время до отказа
1
1
1
1
T
...
2 0
(n 1) 0
0
Первое слагаемое соответствует этапу функционирования когда работает
только один элемент и нет резервных, второе когда один работает и один
резервный и так далее последние слагаемое соответствует исходному
состоянию когда один элемент работает и (n-1) элементов находятся в
резерве когда их интенсивность отказов 0 .
Общее резервирование целой кратности с постоянно включенным
резервом
Структура системы с общим резервированиеь целой кратности с
постоянно включенным резервом приведена на рис. (рис.2.1,а):
ВБР системы вычисляется как
m 1
n
Pc (t)= 1
1
pi (t)
,
i=1
где рi(t) – вероятность безотказной работы i-го элемента в течении
времени t; n – число последовательно соединенных элементов цепи; m –
число резервных цепей (кратность резервирования (m/1).
При экспоненциальном распределении времени до отказа элементов
P (t ) 1 (1 e
n m 1
)
Средняя наработка до отказа
m
1
T
1
n
i 0
i 1
j
j 1
n
суммарная
j
интенсивность
отказов
основной
n
j 1
последовательно соединенных элементов , причем
отказов j –го элемента.
а)
λj интенсивности
б)
Рис Общее резервирование целой кратности
А)с постоянно включенным резервом , б) с резервированием
замещением
Общее резервирование целой кратности с резервированием
замещением
При последовательном соединении в кажжой параллельной цепи n
одинаковых элементов с интенсивностью отказов
i
i
n 1
nt
nt
nt
nt
P(t ) e
1 e
i
!
i!
i 0
i n
При последовательном соединении в кажжой параллельной цепи n
элементов с разной интенсивностью отказов
i
n
n
t
P(t ) e
k
n 1
t
k
k 1
k 1
i 0
i
n
n
i!
t
1 e
k
k
k 1
k 1
i n
i!
t
Рис .
Раздельное (поэлементное) резервирование с постоянно
включенным резервом
Поэлементное резервирование с постоянным включением резерва.
Структурная модель надежности системы с поэлементным резервированиеи
при постоянном включении резерва представлена на рис
Будем считать что в системе имеется n последовательно соединенных
основных элементов, при этом i –й осрновной элемент имеет кратность
резервирования mi/1 (рис ).
Рассматриваемая система работоспособна если во всех n группах
параммельно соединенных элементов исправен хотя бы один из элемент ,
так как в i-й группе имеется один основной и mi резервных элементов , а их
общее число mi +1 , то ВБР системы вычисляется как
n
1 (1 pi (t )) mi
P(t )
1
,
i 1
где pi (t ) -ВБР элемента i –й группы.
Средняя наработка до отказа вычисляется как
n
1 (1 pi (t )) mi
T
1
dt .
0 i 1
Если все элементы равновероятны и кратность их резервирования
одинакова и равна m/1 ( один основной и m резервных элементов) (рис ), то
1 (1 p (t )) m
P(t )
1 n
.
Средняя наработка до отказа вычисляется как
1 (1 p (t )) m
T
1 n
dt
0
Рис . Поэлементное резервирование с постоянно включенным резервом при
одинаковой надежности элементов и их кратности резервирования .
При поэлементном резервировании n элементов если k-й элемент
имеет mk резервных элементов при их резервировании замещением
(холодный резерв)
n
P(t )
Rk (t )
k 1
где
Rk (t ) e
kt
mk 1
i 0
t
i!
i
k
1 e
kt
i mk
Рассмотрим систему
резервировании замещением
из
t
i!
i
k
двух
дублированных
элементов
при
Рис система из двух дублированных элементов при резервировании
замещением
За рассматриваемое время t вероятность что не будет ни одного отказа
первого типа элемента e 1t , и будет один его отказ 1te 1t , вероятность что
не будет ни одного отказа элемента второго типа e 2t , и будет один его отказ
2t
,
2te
Вероятность безотказной работы системы в течении время t
2t
P(t ) e 1t 1te 1t e 2t
2te
Структура соединения элементов приведена на рис.
системы вычисляется как
(рис.2.1,а):ВБР
n
Pc (t)=
1 [1
pi (t)] m ,
i=1
где рi(t) – вероятность безотказной работы i-го элемента; mi – кратность
резервирования i-го элемента; n – число элементов основной системы.
t
При экспоненциальном законе надежности, когда pi (t) e i
n
Pc (t)=
1 [1 e
t
λi
]
mi
,
i=1
Комбированное последовательно- параллельное соединения элементов
Структурная схема надежности может включать
последовательно- параллельных соединения элементов.
комбинации
Рис
комбинации последовательные и параллельные соединения
элементов
Расчет надежнсти таких систем сводится к многоэтапной процедуре с
выделением рассмотренных выше типовых схем последовательно
параллельного соединения элементов
Для соединения элементов модели надежности , представленной на рис 3
вероятность отказа
первой цепи
P =1 p1p2p3,
второй
QII = 1 p4p5p6p7,
третьей
QIII =1 p8 p9,
четвертой
QIV =1 p10.
Вероятность безотказной работы всей системы
P = [1
Рис 3
(1
p1p2p3)(1
p4p5p6p7)(1
p8p9)(1
p10)] p11p12
Логическая схема соединения элементов
Структура типа «k из n»
Структура типа “k из n” работоспособна, если исправны хотя бы k из n
элементов. При k=1 структура преобразуется в параллельное соединение, при
k=n – в последовательное соединение.
Рис Структура типа “k из n”
Вероятность безотказной работы структуры “k из n” при постоянном
включении резерва (горячий резерв) вычисляется как
n
k 1
C ni ( p(t )) i (1 p(t )) n
p S (t )
i k
i
C ni ( p(t )) i (1 p(t )) n i ,
1
i 0
i
i
n i
где Cn ( p(t )) (1 p(t )) вероятность исправности в момент времени t
ровно i элементов структуры, имеющих ВБР p(t), причем
Cni
n ! i !( n
i )!
Наработка до отказа рассматриваемых систем при нагруженном
резерве определяется как
1 1
1
1
T
(
...
)
k k 1
n
Модель надежности со структурой типа “k из n” может использоваться
при оценке надежности вычислительных систем кластерной архитектуры. В
кластерной вычислительной системе значение k может определяться, исходя,
например, из минимального числа компьютеров, обеспечивающих
стационарный режим обслуживания запросов при заданной интенсивности
входного потока. Для управляющих вычислительных систем значение k
может обусловлено выделением на каждый объект управления отдельного
управляющего компьютера .
При резервировании замещением (холодный резерв) вероятность
безотказной работы системы [Ушаков]
i
n k
i
kt
kt
P(t ) e
1 e t
i!
i!
i 1
i n k 1
Наработка до отказа рассматриваемых систем при ненагруженном
резерве определяется с учетом того что система функционирует пока не
откажет n-k+1 элемент , то есть
t
T
n k 1
k
Модель надежности соответствующая структуре «2 из 3», используется
, например, при оценке надежности трехканальных систем мажоритарного
резервирования в которых результат формируется по большинству, то есть
система сохраняет функционирование при исправности не менее двух из трех
каналов. Аналогично при пятиканальной
схеме мажоритарного
резервирования модель расчета надежности сводится к структуре «3 из 5».
Схема структуры с мажоритарным резервированием представлена на
рис а) На рис б) приведен пример реализации мажоритарного элемента, а
на рис состав микросхемы КР 1533ЛП3, реализующую мажоритарную
логику
Z
x1 x2
x2
x3
x1 x3
Если из-за отказа работы устройств наблюдается расхождение
результатов на выходах n устройств , то мажоритарный орган М выдает
результат по большинству. Вероятность безотказной работы системы:
n
p S (t )
PM
C ni ( p(t )) i (1 p(t )) n i
i int( n / 2)
где -int(n/2)- ближайшее целое не меньшее n/2
РМ, p - вероятность безотказной работы мажоритарного элемента
(органа) и резервируемого устройства (канала, элемента).
Для троированной системы (n=3):
РМ3 = РМ(3р2 – 2p3).
При n=5:
РМ5 = РМ(10р3 – 15р4 + 6р5)
На риc 5 показано семейство функций РМ Pм при различных n. Из
представленных зависимостей видно, что мажоритарное резервирование
относительно надежности одного элемента (канала) дает эффект повышения
надежности, если p>0.5, в противном случае надежность устройства
понижается.
Рис Мажоритарное резервирование
Рис. Надежность системы при мажоритарном резервировании
Схема мажоритарного резервирования
не позволяет достичь
вероятности безотказной работы системы больше чем ВБР РМЖ.
Для L-каскадной схеме с мажоритарным резервированием,
представленной на рис , ВБР вычисляется как :
РМ3 =(РМ)L(3р2 – 2p3)L.
Эффект снижения ВБР системы из-за ненадежности мажоритарного
органа для L-каскадного соединения мажоритарных схем ( рис ) проявляется
еще в большей степени чем для базовой схемы мажоритарного
резервирования ( рис ) .
Рис. Многокаскадной схеме с мажоритарным резервированием
Данный недостаток устраняется в многокаскадной схеме с
мажоритарным резервированием, когда мажоритарные органы также
резервируются, подобная схема резервирования представлена на рис .
Рис Многокаскадная схема с мажоритарным резервированием, при
резервировании мажоритарных органов.
ВБР системы по рис вычисляется как:
РМ3 =[3(РМ р) – 2 (РМ p)3]L
Здесь мажоритарные органы также резервируются. Первоначальный
канал обработки информации разбивается на последовательные участки
(слои).
Исправление ошибки, связанной с неисправностью мажоритарного
органа происходит через слой резервированных подсистем.
Предположим, что каждый из элементов А имеет вероятность отказа
q, а каждое переключающее устройство B имеет вероятность отказа .
Тогда вероятность отказа системы, приведенной на рис. 12, будет равна
(202)
СИСТЕМЫ, НЕ СВОДЯЩИЕСЯ К ПОСЛЕДОВАТЕЛЬНОПАРАЛЛЕЛЬНОМУ СОЕДИНЕНИЮ ЭЛЕМЕНТОВ
Существуют системы, структурная модель надежности которых не
сводятся к последовательно-параллельному соединению элементов.
Системы, не сводящиеся к последовательно – параллельному соединению, в
теории надежности относят к структурно сложным системам. Примеры
таких систем, приведены на рис. 1.2. Простейшая структура, не сводящаяся к
параллельно-последовательному соединению является мостиковая схема (
рис а)
а)
б)
и)
Рис. 1.2. системы, не сводящиеся к последовательным или параллельным
соединением
Приведенные схемы, не сводящиеся к параллельно-последовательной
структуре,
Для функционирования системы необходимо, чтобы в работоспособном
состоянии были элементы В1 и С1 или элементы А и С1, или А и С2, или В2
и С2.
К схеме по рис
может быть приведена структура вычислительного
комплекса в котором В1и С1 соответствуют памяти и процессору одного
полукомплекса , а В1и С1- второго полукомплекса. Элемент А соответствует
двухвходовой памяти которая может подключаться к одному из процессором
после отказа подключенному к нему блока памяти. Ддухвходавая память
может использоваться для межмашинного обмена полукомплексов, если этот
обмен необходим для решения задачи и если каждыйполукомплекс решает
свои задачи , которые не могут в случае отказа полукомплекса возложены на
другой полукомплекс то структурная модель радежностиструктуры по рис
сводится к последовательному соединению элементов А,В1,В2,С1,С2.
Схема по рис а ) может соответствовать двухмашинному вычислительному
комплексу , содержащего процессоры 1,3 и память 2,4. Доступ процессора
одного полукомплекса к памяти второго полукомплекса в случае отказа
памяти своего полукомплекса может осуществляться через адаптер ( модуль
комплексирования) 5.
Схема по рис
а)
также соответствует
дублированному комплексу , предусматривающему реконфигурацию через
переключатель 5 позволяющую формировать структуру с процессором и
памятью относящимся к разным полукомплексам.
Структуры , несводящиеся к параллельно последовательному соединению
элементов могут входить составной частью в более сложные схемы,
например, представленной на рис . комбинации мостиковых схем.
Рис Комбинации мостиковых схем
Рассмотрим методы расчета
систем, структурная модель надежности
которых не сводятся к последовательно-параллельному соединению
элементов.
2.3.8. Структурная функция надежности
Для задания модели надежности системы може использоваться
структурная функция надежности . Состояние i-го элемента отобразим как :
1, если i - й элемент работает,
xi
0, если i - й элемент отказал.
При
как; ( x)
этом
структурная,
функция
1, если система работает,
системы
определяется
0, если система отказала.
Структурная функция системы может задаваться в виде логической
функции .
Структурная функция надежности
при
последовательном
и
параллельном соединенных элементов имеет вид
n
( x)
xi
x1 ... xn
i 1
n
( x) 1
(1 xi )
x1 ... xn .
i 1
Для структуры типа к из n структурная функция представима в виде
1, если
n
xi
k
xi
k
i 1
( x)
0, если
n
i 1
Для мостиковой схемы (рис ) структурную функцию можно задать как:
. ( x1 , x,2 , x3 , x4 , x5 ) x1 x3 x2 x4 x1 x5 x4 x2 x5 x3
Или
( x1 , x, 2 , x3 , x4 , x5 )
( x1
x2 )( x3
x4 )( x1
x5
x4 )( x2
x5
x3 )
Перебирая всевозможные состояния схемы структурную функцию
можно задать в виде СДНФ. Например, для мостиковой схемы:
( x1 , x,2 , x3 , x4 , x5 ) x1 x2 x3 x4 x5 x1 x2 x3 x4 x 5 x1 x2 x3 x 4 x5 x1 x2 x 3 x4 x5 x1 x 2 x3 x4 x5
x 1 x2 x3 x4 x5
x1 x2 x 3 x4 x 5
x1 x 2 x3 x4 x 5
x 1 x2 x3 x4 x 5
x1x2 x 3 x 4 x5
x1 x 2 x3 x 4 x5
x1 x2 x3 x 4 x5 x1 x 2 x 3 x4 x5 x1 x2 x 3 x4 x5 x1 x 2 x 3 x4 x5 x1 x 2 x 3 x4 x 5 .
П ри представлении стуктурной функции в виде СДНФ позволяет легко
перейти к формуле для оценки вероятности безотказной работы системы
путем замены xi и xi на значение ВБР pi и вероятности отказа (1- pi )
соответствующего элемента.
2.3.4. Метод перебора состояний
Метод предполагает перебор состояний с подсчетом работоспособных
состояний,
при
определении
их
вероятностей.
При
анализе
работоспособности каждого состояния системы необходимо учитывать не
только число отказавших элементов, но и их расположение в схеме.
Вероятность безотказной работы системы определяется как сумма
вероятностей всех работоспособных состояний
Пример перебора всевозможных состояний системы на примере
мостиковой схемы приведен таблицей .
Табл
Расчет мостиковой схемы методом перебора
Число
отказавши
Работоспособные состояния
Вероятност
ь состояния
Число
состояний
х
элементов
0
(1,2,3,4,5)
p5
1
1
(1,2,3,4),
(1,2,3,5),(1,2,4,5),
(1,3,4,5), (2,3,4,5)
p4q
5
2
(1,2,3), (1,2,4), (1,3,4), (1,3,5),
(1,4,5), (2,3,4), (2,3,5), (2,4,5)
p3q2
8
p2q3
2
3
(1,3), (2,4)
Для мостиковой схемы получаем следующие работоспособные
состояния (каждое состояние определяется указанием работоспособных
систем):
P
p1 p 2 p3 p 4 p5
p1 p 2 p3 p 4 q5
p1 p 2 p3 q 4 p5
p1 p 2 q3 p 4 p5
p1 p 2 q3 p 4 q5
p1q 2 p3 p 4 q5
q1 p 2 p3 p 4 q5
p1 p 2 q3 q 4 p5
p1q 2 q3 p 4 p5
q1 p 2 q3 p 4 p5
q1q 2 q3 p 4 p5
p1q 2 q3 p 4 q5 .
p1q 2 p3 p 4 p5
p1q 2 p3 q 4 p5
q1 p 2 p3 p 4 p5
q1 p 2 p3 q 4 p5
Заметим , что приведенную функцию можно формально получить на
основе структурную функцию , заданной в виде СДНФ
В случае равной надежности элементов для мостиковой схемы имеем :
p S p 5 5 p 4 q 8 p 3 q 2 2 p 2 q 2 p 5 5 p 4 2 p 3 2 p . ()
Достоинством метода перебора состояний является его простота.
Недостатком является громоздкость. Для сложных систем с большим числом
элементов метод может оказаться неприменимым из-за проблем размерности
Результаты расчета надежности мостиковой схемы при равной
надежности элементов схемы в зависимости от надежности элемента p
приведены на рис .
На рис
представлена зависимость вероятности
безотказной работы мостиковой схемы от времени функционирования при
p(t ) e t , λ – интенсивность отказов элементов.
Рис. Надежность мостиковой схемы
Рис. Зависимость вероятности безотказной работы мостиковой схемы
от времени функционирования
Представленные на рис зависимости позволяют сделать вывод что при
высокой надежности элементов надежность мостиковой структуры выше
надежности элемента, а при низкой надежности элемента (р<0,5) надежность
системы ниже надежности элемента . Аналогичные вывод можно сделать по
рис из которого видно что существует граница наработки выше которой
надежность мостиковой структуры (кривая 1)
ниже
надежности
элемента(кривая 2).
При высокой надежности элементов , когда p 1и q 0 расчет
надежности можно упростить, учитывая что с ростом показателя степени над
q соответствующий член суммы быстро стремиться к нулю, при этом оценка
будет нижней, что вполне приемлемо для расчета надежности. Такая
возможность иллюстрируется на рис. , на котором кривая 1 соответствует
точной оценке надежности мостиковой схемы по формуле (), кривые 2-4
соответствуют погрешности оценке вероятности безотказной работы при
отбрасывании последнего слагаемого , двух и трех последних слагаемых.
Расчеты подтверждают достаточно малую погрешность получаемую при
отбросе последних слагаемых формулы формируемой на основе учета всех
состояний системы.
Рис. Расчет надежности при отбрасывании младших слагаемых
степенного ряда , формируемого при учете всех состояний структуры.
2.3.3. Метод разложения по ключевым ( особым) элементам
Метод основан на представлении схемы композицией более простых
структур
(параллельно-последовательных или иных структур расчет
которых не представляет трудности), формируемых из исходной при
всевозможных комбинациях исправности (отказа) совокупности особых
элементов. К особым элементам относится некоторое множество элементов
структуры, которые препятствуют представлению схемы в виде параллельнопоследовательного соединения элементов.
В основу метода положены следующие правила разложения сложной
структуры:
1. В исходной системе выбирается элемент или группа элементов,
влияющих на то, что структура не сводится к параллельнопоследовательному соединению элементов
2. Рассматриваются всевозможные состояния особых элементов и
определяются вероятности этих состояний
3.Для каждого из возможных состояний
выделенных особых
элементов определяется структурная схема надежности оставшейся части
системы. Для состояния особого элемента,
соответствующего его
исправности, входы этого элемента соединяются , а не исправности –
разрываются.
4.Определяется вероятности ее работоспособности при условии
вероятности возникновения каждого состояния особых элементов
Надежность системы определяется на основе формулы полной
вероятности
n
P(A)
P( A / H i ) P( H i )
i 1
При этом H1, H2,..., Hn, группа событий , обладающая следующими
свойствами: все события попарно несовместны: Hi Hj = ; i, j=1,2,...,n; i j;
а их объединение образует пространство элементарных исходов
: = H1 H 2  H n .
В случае необходимости рассматриваемое
разложение может
проводиться многократно.
Представление разложения мостиковой схемы относительно особого
элемента иллюстрируется на рис
. Пример многократного применения
метода разложения схемы относительно особого элемента приведен на рис
Рис. Разложение мостиковой схемы относительно особого элемента
иллюстрируется на рис
Рис
Многократное применения
относительно особого элемента.
метода
разложения
схемы
Оценим надёжность мостиковой схемы представленной на рис. 5.1.
Для мостиковой схемы (рис. 3.2, а) в качестве особого элемента
выберем диагональный элемент 5. При исправности элемента 5 мостиковая
схема превращается в параллельно - последовательное соединение на рис
(рис. 3.5, а), а при неисправности этого элемента - в последовательно параллельное (рис. 3.5, б).
Рис
Таким образом, получаем точную оценку исследуемой схемы
Pc
p5 1
1 p1 1 p3
1
1 p2 1 p4
1 p5 1
1 p1 p2 1 p3 p4
Метод так же как метод перебора является точным, поэтому
результаты расчета для мостиковой схемы совпадают с представленными на
рис
и рис .
Приведем пример расчета некоторой коммуникационной системы на
основе рассматриваемого метода.
Пусть имеется телекоммуникационная структура приведенноая на рис
, при этом кружками представлены узлы коммутации, имеющие ВБР P0, а
прямоугольниками каналы связи имеющие ВБР P1
телекоммуникационная структура
Для указанной схемы работоспособность требует безотказности двух
коммутаторов, связанных с входом и выходом схениы. В качестве особых
выделим пару коммутаторов, связанные радиальным каналом, тогда при
условии исправности обоих выделенных коммутаторов схема расчета
сводится к рассмотренной ранее
мостиковой схеме, а при условии
исправности
одного
из
рассматриваемых
коммутационных
работоспособность схемы обеспечивается при исправности двух
подключенных к нему каналов связи.
Таким образом, получаем формулу для расчета ВБР структуры по рис
p0 (t ) 2 ( p1 (t )(1 [1 p1 (t )]2 ) 2 (1 p1 (t ))(1 [1 p1 (t ) 2 ]2
2
Pc (t ) p0 (t )
2 p0 (t )(1 p0 (t )) p1 (t ) 2
где
p1 (t ) exp( 1t ), p0 (t ) exp( 0t )
1 , 0 - интенсивности отказов каналов и коммутаторов, t- время работы.
2.3.5. Метод минимальных путей и минимальных сечений
Метод минимальных путей и минимальных сечений (метод ЭзариПрошана) позволяет получить приближенную верхнюю и нижнюю оценку
надежности систем сложной структуры.
Путем
называется
любая
совокупность,
элементов
при
работоспособности которой - система работоспособна.
Сечением (разрезом) - называется любая совокупность, элементов,
отказ которых вызывает не работоспособность системы.
Минимальный путь
совокупность, элементов работоспособности
которой обеспечивает работоспособность системы, а отказ любого из них
приводит к неработоспособности системы.
Иначе говоря, минимальный путь это множество элементов системы,
работоспособность
которых необходима и достаточна для
работоспособности системы.
Для минимального пути выполняются два условия:
если
все
элементы,
принадлежащие
минимальному
пути,
работоспособны, то система работоспособна;
если отказали все элементы, не принадлежащие минимальному пути и
хоть один из элементов минимального пути, то система отказывает .
Минимальным сечением называется множество элементов системы,
отказ которых необходим и достаточен для отказа системы.
Минимальным сечением называется множество элементов системы,
для которого выполняются два условия:
1) если работают все элементы, не принадлежащие минимальному
сечению и хоть один из элементов минимального сечения, то и система
работает;
2) если все элементы, принадлежащие минимальному сечению,
отказали, то и вся система отказывает.
Для мостиковой схемы определим все минимальные пути как :
{1,2}, {3,4}, {1,5,4}, {2,5,3}.
А минимальные –сечения как :
{1,3}, {2,4}, {1,5,4}, {2,5,3}.
Пусть для исследуемой системы найдены все минимальные пути. При
этом некоторые элементы системы могут принадлежать
нескольким
минимальным путям.
Вероятность работы минимального пути равна произведению
вероятностей работы всех входящих в него элементов.
Если хоть один из минимальных путей системы работоспособен, то
система работоспособна.
Если мы все минимальные пути соединим параллельно, то получим
систему с надежностью, не меньшей, чем надежность исходной системы.
Таким образом,
представление системы в виде параллельного
соединения минимальных путей
дает верхнюю (завышенную,
оптимистическую) оценку надежности системы.
Для получения оценки надежности сверху на основе минимальных
путей :
1) находим все минимальные пути системы;
2) элементы каждого минимального пути соединяем последовательно;
3) все полученные на предыдущем шаге цепочки с последовательным
соединением элементов соединяем параллельно.
Для мостиковой схемы параллельное соединение мини-путей дает
систему на рис. 5.4.
Оптимистичность оценки по методу минимальных путей очевидна из
того, что отказ элемента, входящего в несколько минимальных путей
например первого судя по схеме на рис приводит к потере одного пути (
1,2) , а в реальной системе его отказ вызывает отказ также минимального
пути (1,5,4)
Рис. 5.4. Параллельное соединение минимальных путей для мостиковой
схемы
Пусть для исследуемой системы найдены все минимальные -сечения.
Каждому минимальному сечению сопоставим систему из параллельно
соединенных элементов этого минимального сечения.
Система отказывает, если отказывают все элементы, хотя бы одного
минимального сечения, то есть для всех ее минимальных сечений хотя бы
один элемент будет работоспособен .
Представим систему в виде последовательного соединения
минимальных сечений.
Таким образом для оценки по методу минимальных сечений:
1) находим все минимальные сечения системы;
2) элементы каждого минимального сечения соединяются параллельно;
3) все минимальные сечения соединяются последовательно.
Надежность полученной системы с последовательно-параллельным
соединением не превышает надежности исходной системы, так как
ненадежность элементов, входящих в несколько минимальных сечений
учитывается несколько раз.
Для мостиковой схемы последовательное соединение минимальных сечений приводит к системе на рис. 5.5.
Рис. 5.5. Последовательное соединение минимальных сечений для
мостиковой схемы.
Таким образом, получена верхняя и нижняя оценка систем
Последовательное
соединение
Минимальных
Параллельное
Pc
путей
соединение
Минимальных
сечений
Или подставляя формулы для
последовательных соединений получим:
1
1 k
N
qi
i
Bk
соответствующих
Pc
1
1
j
M
pi
i
параллельно
,
Aj
где A1 , A2 ,..., AM , B1 , B2 ,..., BN
множество минимальных путей и минимальных сечений.
Следовательно, для мостиковой схемы получаем оценку надежности
снизу и сверху как.
Pc 1 (1 p1 p2 )(1 p4 p3 )(1 p1 p5 p4 )(1 p2 p5 p3 )
Pc (1 q1q3 )(1 q2q4 )(1 q1q5q4 )(1 q2q5q3 )
при равной надежности элементов получаем
Pc 1 (1 p 2 ) 2 (1 p 3 ) 2 .
Pc 1 (1 q 2 ) 2 (1 q 3 ) 2
Результаты расчета надежности мостиковой схемы по методу
минимальных путей ( кривая 1) и сечений ( кривая 2) при λ=10 -4 ч-1
представлены на рис а) , а при λ=10-6 ч-1 на рис б). На рис а) кривая 3
соответствует точной оценке на основе полного перебора.
Результаты оценки погрешности расчета надежности мостиковой
схемы по методу минимальных путей представлены на рис
. На рис а )
-4
-1
при λ=10 ч кривая 1 отражает разницу оценки надежности по методу
минимальных путей и минимальных сечений, кривая 2 разницу оценки по
методу минимальных путей с точной оценкой, а кривая 3 разницу расчета по
минимальным сечениям с точной оценкой. . На рис а ) при λ=10 -6 ч-1 кривая
1 отражает разницу оценки надежности по методу минимальных путей и
точной оценки, а кривая 3 разницу расчета по минимальным сечениям с
точной оценкой.
Из представленных зависимостей видна достаточна высокая точность
методов минимальных путей и сечений, особенно в наиболее интересном для
практики диапазоне параметров. Метод минимальных сечений наиболее
интересен для инженерных расчетов ,так как он дает нижнею (осторожную)
оценку надежности, при этом
метод минимальных путей, может
использоваться для оценки погрешности расчета надежности так как он дает
оптимистический (завышенный) результат.
Рис. Надежность мостиковой схемы по методу минимальных путей и
сечений
Рис. Погрешность оценки надежность мостиковой схемы по методу
минимальных путей и сечений
2.3.6.Метод Литвака-Ушакова
Оценка надежности по методу Литвака-Ушакова является
усовершенствованием метода минимальных путей и минимальных сечений.
Метод Литвака предусматривает реализацию следующего алгоритма: .
1.
Нахождение множества минимальных путей.
2.
Нахождение множества минимальных сечений.
3.
Формирования
вариантов
множеств
непересекающихся
минимальных путей.
4.
Формирования
вариантов
множеств
непересекающихся
минимальных сечений
5.
Для всех вариантов непересекающихся минимальных путей
представляем их в виде параллельного соединения минимальных путей,
проводим оценку вероятности работоспособности каждого варианта и
выбираем наибольшее значение, , которое используется как нижняя оценка
надежности системы.
6.
Для всех вариантов непересекающихся минимальных путей
представляем их в виде последовательное соединение минимальных сечений,
проводим оценку вероятности работоспособности каждого варианта и
выбираем наименьшее значение, , которое используется как верхняя оценка
надежности системы.
7.
Определяем погрешность расчета как разницу между верхней и
нижней оценкой надежности системы, .В случае приемлемой погрешности
надежность системы оцениваем по нижнему приближению.
Для мостиковой схемы выделяем множество минимальных путей
{1,3}, {2,4}, {1,5,4}, {2,5,3} и минимальных сечений{1,2}, {3,4}, {1,5,4},
{2,5,3}
Выделяем среди них не пересекающиеся минимальные пути
{ {1,3}, {2,4} }; {1,5,4} ; {2,5,3},
и не пересекающиеся минимальные сечения
{{1,2}, {3,4}};{1,5,4};{2,5,3}
Таким образом, получаем (рис )
Pc Max 1 (1 p1 p2 )(1 p4 p3 ),(1 p1 p5 p4 ),(1 p2 p5 p3 ) ;
Pc Min (1 q1q3 )(1 q2q4 ),(1 q1q5q4 ),(1 q2q5q3 )
При равной надежности всех элементов имеем:
Max 1 (1 p 2 ) 2 , p 3
Ps
Мin 1 (1 q 2 ), (1 q 3 )
Рис. Метод Литвака, пояснения к расчету надежности
Результаты расчета надежности мостиковой схемы по методу Литвака (
кривая 1 для путей) и сечений ( кривая 2 для сечений) при λ=10 -4 ч-1
представлены на рис На рис кривая 3 соответствует точной оценке.
Результаты оценки погрешности D(t) расчета надежности мостиковой
схемы по методу Литвака при λ=10-4 ч-1 представлены на рис 2 а) . Кривая
1 отражает разницу оценки Литвака-Ушакова по минимальным путям и
минимальныv сечениям, кривая 2 разницу оценки Литвака по минимальным
непересекающимся путям с точной оценкой, а кривая 3 разницу расчета по
минимальным непересекающимся сечениям с точной оценкой. На рис а )
при λ=10-6 ч-1 кривая 1 отражает разницу оценки надежности по методу
Литвака на основе минимальных непересекающихся сечений и путей ,
кривая 2- разницу оценки Литвака по путям с точной оценкой, а кривая 3
разницу оценки Литвака по минимальным сечениям и точной оценки.
Рис расчета надежности мостиковой схемы по методу Литвака
а)
б)
Рис 2.
Результаты оценки погрешности D(t) расчета надежности
мостиковой схемы по методу Литвака
Метод включения -исключения
В комбинаторном анализе , вероятностных расчетах в том числе
теории надежности в ряде случаев эффективно используется принцип
включений-исключений . суть которого заключается в следующем:
Для вычисления размера (числа элементов, кардинального числа )
объединения нескольких множеств, требуется просуммировать размеры этих
множеств по отдельности, затем вычесть размеры всех попарных
пересечений этих множеств, прибавить обратно размеры пересечений
всевозможных троек множеств, вычесть размеры пересечений четверок, и так
далее, вплоть до пересечения всех множеств.
Формально это выглядит следующим образом:
n
card (
n
Ai )
card ( Ai )
i 1
i 1
( 1)n 1 card ( A1
card ( Ai
Aj )
i, j
A2
...
card ( Ai
Aj
Ak ) ...
i , j ,r
An )
Принцип включения-исключения иллюстрируется с помощью диаграмм
Венна
Пусть на диаграмме представленной на рис отмечены три множества A B
C
Рис Принцип включения-исключения диаграмма Венна
Тогда площадь объединения A B C равна сумме площадей A,B,C,
и за вычетом дважды покрытых площадей
A B, A C , B C , но с
прибавлением трижды покрытой площади A B C
S A B C S A S B S C S A B S A C S B C S A B
Приведем
формулировку
метода
включенияисключения,
ориентированную на вычисление вероятностей
Пусть Ai –события, P(Ai) их вероятности, то вероятность их объединения (т.е.
того, что произойдёт хотя бы одно из этих событий) равна:
n
P(
n
Ai )
i 1
P( Ai )
i 1
P( Ai
i, j
Aj )
P( Ai
Aj
Ak ) ...
i , j ,r
... ( 1)n 1 P( A1 A2 ... An )
В соответствии с принципом включения-исключения вероятность
работоспособности мостиковой схемы на основе учета пересекаемости
минимальных путей получим
C
Pc
p1 p2
p4 p3
p1 p5 p4
p2 p5 p3
по одному минимальному пути
( p1 p2 p4 p3
p1 p2 p5 p4
p1 p2 p5 p3
p4 p3 p1 p5
p4 p3 p2 p5
p1 p5 p4 p2 p3 )
по два минимальных пути
(4 p1 p2 p3 p4 p5 )
( p1 p2 p3 p4 p5 )
по три минимальных пути
по четыре минимальных пути
А на основе минимальных сечений
Pc 1 (q1q3 q4 q2
q1q5q4
q2 q5q3 )
по одному минимальному сечению
(q1q3q4 q2
q1q3q5q4
q1q3q2 q5 q4q2q1q5 q4q2q5q3 q1q2q3q4q5 )
по два минимальных сечения
(4q1q2 q3q4 q5 )
(q1q2 q3q4 q5 )
по три минимальных сечения
по четыре минимальных сечения
В случае равной надежности элементов при оценке по принципу
включения - исключения на основе минимальных путей имеем
Pc
(2 p 2 2 p 3 )
(5 p 4 p 5 )
по одному минимальному пути
по два минимальных пути
(4 p 5 )
( p5 )
по три минимальных пути
по четыре минимальных пути
А сечений
Pc 1
(2q 2
2q 3 )
по одному минимальному сечению
(5q 4 q 5 )
по два минимальных сечения
(4q 5 )
(q5 )
по три минимальных сечения
по четыре минимальных сечения
Результаты оценки надежности мостиковой схемы по методу
включения- исключения для путей при λ=10-4 ч-1 представлены на рис , а
для сечений на рис. На рис
кривые 1-4 соответствую первому , второму
третьему и четвертому приближению (точная оценка). Из графиков видно
увеличение точности при увеличении шага приближения.
МАРКОВСКИЕ МОДЕЛИ НАДЕЖНОСТИ
1 МАРКОВСКИХ
МОДЕЛЕЙ
НАДЕЖНОСТИ,
ОСНОВНЫЕ
ПОЛОЖЕНИЯ
2 МАРКОВСКИЙ
АНАЛИЗ
ЯВЛЯЕТСЯ
ОДНИМ
ИЗ
ЭФФЕКТИВНЫХ
МЕТОДОВ
АНАЛИЗА
НАДЕЖНОСТИ
,
ПРИМЕНЯЕМЫЙ ДЛЯ ОЦЕНКИ И АНАЛИЗА ВЕРОЯТНОСТНЫХ
ХАРАКТЕРИСТИК ТЕХНИЧЕСКИХ СИСТЕМ [ГОСТ Р 51901.15-2005].
Система
представляющая набор элементов
рассматривается в
различных состояниях, каждое из которых определяется комбинацией
работоспособного и неработоспособного состояний ее элементов. Переходит
между состояниями
системы происходит в момент отказа или
восстановления элемента система. Рассматриваемый процесс переходов
описывается моделью дискретных состояний с непрерывным временем. В
соответствии с этим способом представления изменения состояний системы
применяют методологию анализа пространства состояний.
Используемая для анализа надежности системы модель дискретных
состояний позволяет отражать функционирование системы в отношении
стратегий и политики технического обслуживания (приоритетное
восстановление, проблемы организации очереди, ограниченный ресурс).
Марковские модели
позволяют отразить порядок,
возникновения
многократных отказов.
Марковские модели дают возможность графически отображать процесс
отказов/восстановлений, который представляют в виде переходов от одного
символа состояния к другому, вместе составляющих диаграмму состояний и
переходов системы. Сумма всех вероятностей состояний равна единице. В
любой момент времени системе соответствует только одно состояние в
диаграмме состояний и переходов. Если по практическим причинам
состояния с низкой вероятностью опущены, выполнение вышеупомянутого
условия будет приближенным.
Марковские модели могут применяться к системам, в которых часть или
все элементы являются невосстанавливаемыми.
Случайный процесс называется марковским, если для любого момента
t0 вероятность состояния системы в будущем (t > t0) зависит только от
состояния в настоящем (t = t0) и не зависит от того, когда и каким образом
система пришла в это состояние (иначе: при фиксированном настоящем
будущее не зависит от предыстории процесса – прошлого).
Предположения, связанные с вероятностью перехода, формулируются по
ГОСТ Р 51901.15-2005 следующим образом:
- переходы состояний являются статистически независимыми событиями;
- интенсивность отказов λ и интенсивность восстановлений μ постоянны во
времени для каждого состояния ( при переходе в другие состояния эти
интенсивности могут меняться);
- вероятности перехода из одного состояния в другое в интервале времени
Δt (Δt - мало) задаются величинами λΔt и/или μΔt.
Для того чтобы случайный процесс с непрерывным временем был
марковским, необходимо, чтобы интервалы времени между соседними
переходами из состояния в состояние были распределены по
экспоненциальному закону [Алиев].
Таким образом, для марковского процесса вероятности перехода в
другое состояние за время ∆t
Pij ( t ) 1 exp( ij t )
Пусть интервал времени ∆t достаточно мал. Тогда, разлагая exp(
ij
t)
в ряд по степеням ij t при ∆t → 0 и пренебрегая величинами высшего
порядка малости, получим вероятность перехода из одного состояния в
другое за бесконечно малый интервал времени:
Pij ( t ) ij t
При этом
Pij
lim
ij
t 0 t
НАДЕЖНОСТЬ ВОССТАНАВЛИВАЕМОГО ЭЛЕМЕНТА
Определим коэффициент готовности
от времени, когда время
безотказной работы и время восстановления подчинены экспоненциальным
законам с интенсивностями отказов λ и μ соответственно.
Элемент может находиться в двух состояниях работоспособном и
отказавшем
Рассмотрим произвольный момент времени t и отстоящий от него на
малый интервал времени Δt момент t+ Δt. Вероятность отказа на малом
интервале Δt при условии, что в момент t объект был работоспособен,
составит λΔt. Вероятность восстановления на малом интервале Δt при
условии, что в момент t объект не был работоспособен, составит μΔt.
Найдем Kг(t+ Δt), используя формулу полной вероятности.
Пусть А – некоторое событие, которое может произойти
только вместе с одним из событий А1, А2 … Аn , между собой попарно
несовместных. Тогда
Р(А)=Р(А1)Р(А/А1)+ Р(А2)Р(А/А2)+…+ Р(Аn)Р(А/Аn).
В качестве события А рассмотрим нахождение элемента в
работоспособном состоянии в момент (t+ Δt), вероятность которого равна
Kг(t+Δt) по определению коэффициента готовности. В качестве события А1
определим наличие работоспособного состояния в момент t; его вероятность
это Kг(t). В качестве события А2 определим событие, состоящее в том, что
объект в момент t неработоспособен и восстанавливается; вероятность этого
состояния (1 – Kг(t)).
Согласно приведенным выше пояснениям условные вероятности
приобретут значения
Р(А/А1)=1 – λΔt , Р(А/А2)= μΔt,
а формула полной вероятности примет вид (n = 2)
Kг(t+Δt) = Kг(t)( 1 – λΔt) + (1 – Kг(t)) μΔt.
Преобразуем ( ) к виду
(Kг(t+Δt) – Kг(t))/Δt = –Kг(t)(λ + μ ) + μ
Переходя к пределу при Δt→0 , получим
K′г(t) + (λ + μ )Kг(t) = μ .
Решение полученного линейного дифференциального уравнения
относительно Kг(t), имеет вид
K Г (t ) Ce
(
)t
.
Постоянная C должна быть определена из начального условия, т.е.
должна быть известна вероятность того, что в начальный момент времени t =
0 объект работоспособен. Например, если он достоверно работоспособен, то
Kг(0) = 1, после чего получаем
K Г (t )
e
(
)t
.
График Kг(t) показан на рис. .(кривая1).
Если в начальный момент объект достоверно неработоспособен, то
K Г (t )
e
(
)t
,
и график Kг(t) изображается кривой 2. Расчет коэффициента готовности
проведен при μ=1, λ=0,1 1/ч. Кривая 3 уточняет расчет нестационарного
коэффициента готовности при работоспособном исходном состоянии.
Рис. Сходимость нестационарный
стационарному коэффициент готовности
коэффициент готовности к
Независимо от того, с какой вероятностью объект
работоспособен в начальный момент времени, Kг(t) стремится с течением
времени к постоянному значению μ/(λ + μ).
Марковские модели и показатели готовности восстанавливаемых
систем
Марковские
модели
позволяют
представить
процесс
функционирования вычислительных и телекоммуникационных систем в виде
диаграммы состояний и переходов, которая позволяет составить систему
дифференциальных уравнений или систему линейных алгебраических
уравнений. Решение которых позволяет найти коэффициент готовности (
стационарный коэффициент готовности) , Нестационарный коэффициент
готовности ( мгновенный коэффициент готовности, функция готовности).
Дадим определения этих показателей надежности по ГОСТ 53489
.2009.
Коэффициент готовности (в области надежности в технике
availability (measure), inherent availability): Вероятность того, что изделие в
данный момент времени находится в работоспособном состоянии,
определенная в соответствии с проектом при заданных условиях
функционирования и технического обслуживания.
Эксплуатационный коэффициент готовности (operational
availability): Вероятность того, что изделие в данный момент времени
находится в работоспособном состоянии, определенная из опыта при
фактических условиях функционирования и технического обслуживания.
Мгновенный коэффициент
готовности K(t) (instantaneous
availability): Вероятность того, что изделие в данный момент времени
находится в работоспособном состоянии.
Как синоним
будем рассматривать понятие нестационарный
коэффициент готовности, функция готовности.
Мгновенный коэффициент неготовности U(t) (instantaneous
unavailabilit): Вероятность того, что изделие в данный момент времени
находится в неработоспособном состоянии при условии, что необходимые
внешние ресурсы предоставлены.
Средний коэффициент готовности (mean availability): Среднее
значение мгновенного коэффициента готовности на интервале времени (t1,
t2).
Стационарный коэффициент готовности kг (steady state availability,
asymptotic availability): Предел, если он существует, мгновенной готовности,
когда время стремится к бесконечности.
При определенных условиях стационарный коэффициент готовности
может быть выражен как отношение средней продолжительности
работоспособного состояния к сумме средней продолжительности
работоспособного
состояния
и
средней
продолжительности
неработоспособного состояния по внутренней причине.
Стационарный коэффициент неготовности U (mean availability):
Предел, если он существует, мгновенной неготовности, когда время
стремится к бесконечности.
Коэффициент оперативной готовности (operating instantaneous
availability): Вероятность того, что изделие в данный момент времени t1
находится в работоспособном состоянии и, начиная с этого момента,
выполнит требуемую функцию при данных условиях в интервале (t1, t2).
Коэффициент оперативной готовности при определенных условиях
представляет собой произведение коэффициента готовности и вероятности
безотказной работы.
Коэффициент технического использования (в области надежности
в технике) (steady-state availability ratio): Доля времени нахождения
изделия
в
работоспособном
состоянии
относительно
общей
продолжительности эксплуатации в заданном интервале времени, включая
все виды технического обслуживания.
Коэффициент сохранения эффективности (effectiveness retention
ratio): Отношение значения показателя эффективности применения изделия
за определенный период эксплуатации к номинальному значению этого
показателя, вычисленному при условии, что отказы изделия в течение этого
периода не произойдут.
Модели размножения и гибели в расчете надежности
Процессы размножения и гибели представляют частный случай
марковских процессов, для которых переходы из некоторого состояния Sk
происходят только в соседние состояния Sk-1, Sk , Sk+1 , что в ряде случаев
позволяет упростить расчеты (рис ).
Рис. Процесс размножения и гибели (фрагмент переходов)
Процесс размножения и гибели
диаграммой представленной на рис .
в
общем
случае
описывается
Рис. Диаграмма состояний и переходов для процесса «размножения и
гибели».
Для стационарного режима процесса размножения и гибели система
алгебраических уравнений имеет вид:
0
01 P0
10 P1 ,
0
12
P1
10
P
P,
01 0
21 2
…
0
k ,k 1
k ,k 1
Pk
P
k 1,k k 1
P ,
k 1,k k 1
…
n
Pi 1
i 0
Откуда последовательно находим
01
P1
P0 ;
P2
10
01 12
10
P0 ;
21
Pk
...
1...
k 1,k
12 01
k ,k
21 10
P0 ,
и, учитывая что сумма вероятностей всех сотояний равна единице,
получим
1
P0
1
01
12
01
...
n 1, n
01
,
а это позволяет найти вероятности
всех состояний и другие
характеристики процесса размножения и гибели.
10
21
10
n,n 1
10
Таким образом, рассмотрены методы разработки моделей надежности
на основе аппарата марковских процессов. При этом рассмотрены методы
составления диаграмм состояний и переходов марковских процессор и
правила составления
систем дифференциальных и алгебраических
уравнения, позволяющих определить надежность систем соответственно в
нестационарном режиме и в стационарном режимах. Рассмотрим теперь
методологию решения систем алгебраических
и дифференциальных
уравнений с использованием инструментальных средств компьютерной
математики.
Марковские модели резервированных восстанавливаемых систем
МАРКОВСКИЕ МОДЕЛИ НАДЕЖНОСТИ ДУБЛИРОВАННЫХ
СИСТЕМ, АНАЛИЗ ДИСЦИПЛИН ВОССТАНОВЛЕНИЯ ДЛЯ
СТАЦИОНАРНОГО РЕЖИМА
Рассмотрим варианты дисциплин восстановления системы с
параллельным соединением двух элементов, при приоритетном
обслуживании первого элемента в состоянии отказа двух элементов и при
дисциплине обслуживания предполагающей восстановление того элемента,
который отказал первым в условиях ограниченного и неограниченного
восстановления.
При моделировании будем считать заданными интенсивности отказов
и восстановлений первого 0 , 0 и второго 1 , 1 элементов.
Для варианта обслуживания при неограниченном восстановлении (два
ремонтника) диаграмма состояний и переходов дублированной системы
представлена на рис 2.1.
Рис. 2.1 Диаграммы состояний и переходов для системы с дублированием
элемента при восстановлении двумя ремонтниками
Составим уравнения для нахождения вероятностей стационарных
состояний в виде:
Искомый стационарный коэффициент готовности найдем как
Построение графиков зависимость коэффициента готовности от
интенсивностей отказов и восстановлений дано на рис 2.2.
Рис.2.2. Зависимость коэффициента готовности от интенсивностей
отказов и восстановлений при неограниченном восстановлении
Диаграммы состояний и переходов для системы с дублированием
элемента при восстановлении двумя ремонтниками, уравнения для
нахождения
стационарных вероятностей и
график
зависимости
стационарного коэффициента готовности при приоритетном обслуживании
первого элемента в состоянии отказа двух элементов приведены на рис. 2.3
Рис. 2.3. Диаграммы состояний и алгебраические уравнения в матричной
форме
Диаграммы состояний и переходов для системы с дублированием
элемента при восстановлении одним ремонтником, уравнения для
нахождения
стационарных вероятностей и
график
зависимости
стационарного коэффициента готовности при дисциплине обслуживания
предполагающей восстановление того элемента, который отказал первым
дана на рис. 2.4
Рис. 2.4 Диаграммы состояний и алгебраические уравнения в матричной
форме для системы с дублированием элемента при дисциплине
обслуживания предполагающей восстановление того элемента, который
отказал первым.
компьютерные технологии решения систем дифференциальных
уравнений
В Mathcad имеются несколько встроенных функций для решения
системы N дифференциальных уравнений:
rkfixed( (y0,to,t1,M,D)- Метод Рунге-Кутты с фиксированным шагом;
Rkadapt( (y0,to,t1,M,D)- Метод Рунге-Кутты с переменным шагом;
Bulstoer( (y0,to,t1,M,D)- Метод Булирша -Штера;
При этом:
y0- вектор начальных значений в точке to размера N 1;
to –начальная точка расчета;
t1- конечная точка расчета;,
M число шагов на которых численный метод находит решение
D- векторная функция размера N 1, задающая уравнения
Решение систем дифференциальных уравнения для нахождения
нестационарного коэффициента готовности
Пример составления и решения
системы дифференциальных
уравнения для нахождения нестационарного коэффициента готовности
дублированной системы приведен на рис .
Рис. Решение систем дифференциальных уравнения
Определим коэффициент нестационарной готовности дублированных
систем при различных дисциплинах технического обслуживания. Результаты
расчета представлены на рис , на котором кривая 1 соответствуют
дисциплине обслуживания с восстановление первого элемента в состоянии с
отказом двух элементов (рис. ), кривая 2 дисциплине с продолжением после
отказа двух элементов продолжается восстановление элемента, отказавшего
первым (рис ). Кривая 3 соответствует системе в которой после отказа двух
элементов восстановление не производится ( диаграмма на рис
), такая
дисциплина применима для
управляющих систем, не допускающих
перерыва управления в реальном масштабе времени ( такой перерыв
вызывает отказ объекта управления – например транспортного средства).
Рис
. Варианты зависимости коэффициента нестационарной
готовности
дублированных систем от дисциплины технического
обслуживания
Оценка коэффициент оперативной готовности
В соответствии с ГОСТ 53489 .2009 Коэффициент оперативной
готовности (operating instantaneous availability) определяется как вероятность
того, что изделие в данный момент времени t1 находится в работоспособном
состоянии и, начиная с этого момента, выполнит требуемую функцию при
данных условиях в интервале (t1, t2).
Коэффициент оперативной готовности условиях представляет собой
произведение коэффициента готовности и вероятности безотказной работы.
В соответствии с этим определением, если изделие может находиться в
двух состояниях работоспособном и неработоспособном ( без выделения
различных работоспособных состояний) , то коэффициент оперативной
готовности в установившимся режиме ( для достаточно большого t1)
вычисляется как
kог (t ) kг P(t )
где k г - стационарный коэффициент готовности , P(t ) - вероятность
безотказной работы в течении времени выполнения задачи t.
В неустановившимся
(нестационарном) режиме коэффициент
оперативной готовности рассчитывается как
kог (t1 , t2 ) kг (t1 ) P(t2 )
где k г (t1 ) нестационарный коэффициент готовности , P (t2 ) вероятность безотказной работы в течении времени выполнения задачи t2.
Для систем, которые
могут
находиться в
нескольких
работоспособных состояниях, в установившимся режиме коэффициент
оперативной готовности вычисляется как:
kог (t )
Bi Pi (t ) ,
i S
где
Bi вероятность системы в
i-го состояния системы в
установившемся режиме Pi (t ) - вероятность безотказной работы в течении
времени выполнения задачи t, при нахождении системы в i-м состоянии .
В нестационарном режиме коэффициент оперативной готовности
рассчитывается как
kог (t1 , t2 )
Bi (t1 )Pi (t2 )
i S
На рис приведен листинг определения коэффициента оперативной
готовности для дублированной системы в стационарном, а на рис
в
нестационарном режиме.
Рис Определения коэффициента оперативной
дублированной системы в стационарном режиме.
готовности
для
Рис
Определения коэффициента оперативной
дублированной системы в нестационарном режиме.
готовности
для
Оценка коэффициент сохранения эффективности
В соответствии с ГОСТ 53489 .2009 Коэффициент сохранения
эффективности (effectiveness retention ratio):
Отношение значения показателя эффективности применения изделия за
определенный период эксплуатации к номинальному значению этого
показателя, вычисленному при условии, что отказы изделия в течение этого
периода не произойдут.
K ЭФ
1
ЭН
n
i 1
Эi Pi ,
где Эi - эффективность объекта в i-м работоспособном состоянии; Pi вероятность пребывания объекта в i-м работоспособном состоянии;
Эн=max(Эi) - номинальное значение показателя эффективности объекта,
определенное при условии отсутствия отказов; n - количество
работоспособных состояний объекта.
Показатель эффективности должен выбираться так, что его значение
было чем больше, тем лучше.
Для рассматриваемой дублированной системы в режиме разделения
нагрузки, когда запросы выполняются разными машинами в нагруженном (
горячем) резерве эффективность оценим по показателю
обратному
значению среднему времени пребывания запросов.
В исходном состоянии, когда оба узла работоспособны и происходит
распределение поступающего потока между двумя узлами, среднее время
пребывания запросов в системе, каждый узел которой представим в виде
системы массового обслуживания М/М/1, вычислим как
v
T0
,
1
2
v , λ - интенсивность входного потока запросов.
где
Для состояний с работоспособностью одного узла
v
T1
1
Таким образом, для дублированной системе коэффициент сохранения
эффективности определяется как
T
kcэ P0 P0 0
T1 .
В
качестве
показателя
эффективности
рассматриваемых
дублированных вычислительных систем , может быть принят
запас
среднего
времени
пребывания запросов
относительно некоторого
предельно-допустимого времени. При работе дублированной системы в
реальном времени, эффективность может быть оценена по вероятности
превышения времени пребывания запросов
значения предельнодопустимого времени .
Листинг расчета коэффициента сохранения эффективности для
дублированной системы представлен на рис
Рис
расчета коэффициента сохранения эффективности для
дублированной системы
МОДЕЛИРОВАНИЕ
ОБСЛУЖИВАНИЯ В GPSS.
СИСТЕМЫ
МАССОВОГО
Система имитационного моделирования общего применения
GPSS (General Purpose Simulation System) предназначена для
описания и исследования дискретных моделей систем массового
обслуживания (СМО). Динамическими объектами в СМО являются
транзакты (сообщения, заявки), это решаемые в системе задачи,
которые представляют собой единицы исследуемых потоков.
Функционирование СМО представляется как процесс прохождения
транзактов через фиксированную структуру объектов аппаратной и
ряда других категорий.
Блоки генерации и удаления транзактов
GENERATE Tcp,Tм,Тн,Кт,Пр,Кп,Рп - блок генерации
транзактов
Тср - средний интервал времени между последовательными
транзактами;
Тм - разброс интервала времени относительно Тср;
Тн - время появления первого транзакта;
Кт - количество генерируемых транзактов;
Пр - приоритет транзактов;
Кп - количество параметров транзакта;
Рп - размер памяти для одного параметра.
TERMINATE Nз - блок удаления транзакта
Nз - уменьшение счетчика числа завершений на величину Nз.
Блоки занятия и освобождения приборов
SEIZE Ип - блок занятия прибора
Ип - имя прибора, подлежащего занятию транзактом.
RELEASE Ип - блок освобождения прибора
Ип - имя освобождаемого прибора.
Операторы вычислительной категории
Ип VARIABLE АВ - оператор описания целой переменной
Ип FVARIABLE АВ - оператор описания действительной
переменной
Ип BVARIABLE ЛВ - оператор описания булевской
переменной
Ип - имя переменной
АВ - арифметическое выражение
ЛВ - логическое выражение.
SAVEVALUE И,П - оператор изменения сохраняемой
величины
И - имя или номер изменяемой ячейки
П - значение, которое надо записать в ячейку.
Блок задержки транзактов
ADVANCE Тср,Тм - параметры блока соответствуют
параметрам блока GENERATE
Блоки занятия и освобождения очереди.
Транзакт помещается в очередь в том случае, когда некоторое
устройство (или обслуживающий персонал) не в состоянии
обслужить его немедленно (например, устройство занято, либо
память переполнена). Статистические данные об очередях могут
быть получены с помощью двух типов блоков:
QUEUE Ио, К - блок занятия очереди
Ио - имя очереди;
К - количество мест в очереди, занимаемое транзактом.
DEPART Ио, К - блок освобождения очереди
Ио - имя очереди;
К - количество мест в очереди, освобождаемое транзактом.
Блок QUEUE может быть помещен перед любым блоком
модели, в котором может возникнуть задержка. Очередь к занятому
устройству автоматически организуется пакетом моделирования
независимо от того, есть в программе блок QUEUE или нет. По
очередям печатается информация: имя или номер очереди(QUEUE),
максимальная длина очереди за время моделирования (MAX),
минимальная длина очереди (CONT.), число входов в очередь
(ENTRIES), число входов в очередь без последующего ожидания нулевые входы (ENTRIES(0)), средняя длина очереди (AVE.CONT),
среднее время пребывания в очереди (AVE.TIME), среднее время
пребывания в очереди при учете только ненулевых
входов(AVE.(0)).
Моделирование
одноканальной
системы
массового
обслуживания с очередью. Промоделируем процесс прохождения
заявок, поступление которых подчиняется равномерному закону со
средним значением 10 и интервалом [8,12] единиц времени, а
обработка - равномерному закону со средним 5 и интервалом [2,8]
Модель представим программой (нумерация блоков для GPSS
World не обязательна):
1 GENERATE 10,2
2 QUEUE 1
3 SEIZE k
4 DEPART 1
5 ADVANCE 5,3
6 RELEASE k
7 TERMINATE 1
Для реализации моделирования следует на позиции
панели
нажатием левой кнопки мыши инициировать создание нового
документа
(модели)
или
выполнить
последовательность
инициализаций File, New. Для обоих вариантов возникает меню
«Новый документ», при этом следует инициировать позицию Model
(рис. 7.1), после чего открывается рабочее поле для задания
программы моделирования
Рис. 7.1. Подготовка к заданию новой модели
После открытия нового документа инициируется позиция
панели Edit (Рис. 7.2) Insert GPSS Blocks, после чего появляется
соответствующая панель, предназначенная для задания блоков
GPSS (Рис. 7.3). Для задания требуемого блока GPSS, на
соответствующей позиции панели производится нажатие правой
клавиши мыши, после чего формируется панель для задания
параметров
соответствующего
блока.
Например,
при
инициализации блока Generate возникает панель в соответствии с
рис. 7.4. Результаты набора программы моделирования
представлены на рис. 7.5.
…
Рис.7.2. Панель Edit
Рис 7.3. Панель Edit Insert GPSS Blocks
Рис.7.4. Панель задания параметров блока Generate
Рис. 7.5. Пример подготовки программы моделирования
Для трансляции модели следует щелчком левой кнопки мыши
инициализировать позицию главного меню «Command». После
появления выпадающего меню следует инициировать пункт «Greate
simulation» (Создать выполняемую модель) этого меню. После чего
появится окно Jornal с сообщением о результатах трансляции (рис.
7.6).
Рис. 7.6. Окно Jornal с сообщением о результатах трансляции
При успешной трансляции для моделирования системы
следует щелчком левой кнопки мыши инициализировать позицию
главного меню «Command» После появления выпадающего меню
следует инициировать пункт «Start» этого меню. После появления
диалогового окна «Start Command» (рис.7.7) необходимо указать
число прогонов модели и нажать левой клавишей мыши кнопку
меню «OK», после чего выдается отчет о результатах
моделирования (рис. 7.8).
Рис. 7.7. Диалогового окна «Start Command»
Рис. 7.8 Отчет о результатах моделирования
В процессе выполнения программы собирается стандартная
статистическая информация, которая автоматически выводится на
печать по окончании моделирования. Выходные статистические
данные для блоков (BLOCK COUNTS) содержат текущее
(CURRENT) и общее (TOTAL) показания счетчиков числа входов
для каждого блока. В стандартном выводе статистической
информации по устройствам представлена следующая информация:
номер (имя) устройства (FACILITY), число входов или
обслуживаний (ENTRIES), коэффициент использования устройства
(UTIL.), среднее время одного обслуживания (AVE.TIME).
Ниже
представлены
результаты
моделирования
рассматриваемой одноканальной системы массового обслуживания
GPSS World Simulation Report - Untitled Model 2.1.1
Sunday, October 16, 2012 17:39:47
START TIME
END TIME BLOCKS FACILITIES
STORAGES
0.000
1013.630 7
1
0
NAME
K
VALUE
10000.000
LABEL
LOC BLOCK TYPE
ENTRY COUNT
CURRENT COUNT RETRY
1 GENERATE
100
0
0
2 QUEUE
100
0
0
3 SEIZE
100
0
0
4 DEPART
100
0
0
5 ADVANCE
100
0
0
6 RELEASE
100
0
0
7 TERMINATE
100
0
0
FACILITY
ENTRIES UTIL. AVE. TIME AVAIL.
OWNER PEND INTER RETRY DELAY
K
100 0.492
4.991 1
0 0 0 0 0
QUEUE
MAX CONT. ENTRY ENTRY(0) AVE.CONT.
AVE.TIME AVE.(-0) RETRY
1
1 0 100 100 0.000 0.000 0.000 0
FEC XN
PARAMETER
101 0
PRI
BDT
VALUE
1021.106 101
ASSEM CURRENT NEXT
0
1
ИМИТАЦИОННОЕ
МОДЕЛИРОВАНИЕ
МАССОВОГО ОБСЛУЖИВАНИЯ ТИПА М/M/1
СИСТЕМЫ
Имитационная модель СМО М/М/1. Имитационная модель
в GPSS для СМО М/М/1 может быть реализована как
GENERATE
(Exponential(1,0,10))
QUEUE 1
SEIZE kan
DEPART
1
ADVANCE
(Exponential(1,0,10))
RELEASE
kan
TERMINATE
1
После открытия нового документа инициируется позиция
панели Edit Insert GPSS Blocks, после чего появляется
соответствующая панель, предназначенная для задания блоков
GPSS. Подготовка модели проводится в соответствии с описанием
к лабораторной работе №8.
Для трансляции модели следует щелчком левой кнопки мыши
инициализировать позицию главного меню «Command». После
появления выпадающего меню следует инициировать пункт «Greate
simulation» (Создать выполняемую модель) этого меню. После чего
появится окно Jornal с сообщением о результатах трансляции. При
успешной трансляции выдается сообщение об этом
10/23/05 16:03:26 Model Translation Begun.
10/23/05 16:03:26 Ready.
Если ввести ошибку в программу, например в блоке
GENERATE (Exponential(1,0,10)
- не достает закрывающей
скобки, то после инициализации команды формируется сообщение
об ошибке
10/23/05 16:06:58 Model Translation Begun.
10/23/05 16:06:58 Line 2, Col 1. Expecting right parenthesis.
10/23/05 16:06:58 QUEUE 1
10/23/05 16:06:58 **** Model Translation Aborted ****
Копия экрана после успешной трансляции и задании 100
прогонов модели приведена на рис. 9.1. .
Рис. 9.1. Экрана после 100 прогонов модели
Отчет о резульатах моделирования представлен ниже.
GPSS World Simulation Report - Untitled Model 1.4.1
Sunday, October 16, 2012 21:23:44
START TIME
END TIME BLOCKS FACILITIES
STORAGES
0.000
1038.946 7
1
0
NAME
DEV
SER
VALUE
10001.000
10000.000
LABEL
LOC BLOCK TYPE
ENTRY COUNT
CURRENT COUNT RETRY
1 GENERATE
101
0
0
2 QUEUE
101
0
0
3 SEIZE
101
1
0
4 DEPART
100
0
0
5 ADVANCE
100
0
0
6
7
RELEASE
TERMINATE
100
100
FACILITY
ENTRIES UTIL.
OWNER PEND INTER RETRY DELAY
DEV
101 0.992 10.200 1
0
0
0
0
AVE. TIME AVAIL.
101 0
0
0
0
QUEUE
MAX CONT. ENTRY ENTRY(0) AVE.CONT.
AVE.TIME AVE.(-0) RETRY
SER
20 1 101 3 7.766 79.890 82.336 0
CEC XN
PARAMETER
101 0
PRI
M1
VALUE
1035.472 101
FEC XN
PARAMETER
102 0
PRI
BDT
VALUE
1048.861 102
ASSEM CURRENT NEXT
3
4
ASSEM CURRENT NEXT
0
1
МОДЕЛИРОВАНИЕ МНОГОКАНАЛЬНЫХ СИСТЕМ
Имитационное моделирование СМО с многомерный поток
и одном обслуживающем приборе
Рассмотрим пример решения задачи при двух потоках на
входе, одном обслуживающем аппарате и очереди к нему:
GENERATE 30,5
TRANSFER ,GEN2
GENERATE 20,5
GEN2 QUEUE
QOA
SEIZE
OA
DEPART
QOA
ADVANCE 10,5
RELEASE OA
TERMINATE 1
Подготовка модели и ее реализация производится в соответствии с
описанием лабораторной работы № 9.
Процесс моделирования одноканальной системы при двух потоках
на входе иллюстрируется на рис.10.2.
Рис. 10.2. Моделирование одноканальной системы при двух
потоках на входе
Отчет по результатам имитационного моделирования
рассматриваемой системы приведен ниже:
GPSS World Simulation Report - Untitled Model 2.2.1
Thursday, October 27, 2012 18:18:28
START TIME
END TIME BLOCKS FACILITIES
STORAGES
0.000
10074.910 7
0
1
NAME
QSYST
SYST
VALUE
10001.000
10000.000
LABEL
LOC BLOCK TYPE
CURRENT COUNT RETRY
ENTRY COUNT
1
2
3
4
5
6
7
GENERATE
1001
QUEUE
1001
ENTER
1001
DEPART
1001
ADVANCE
1001
LEAVE
1000
TERMINATE
1000
0
0
0
0
0
0
0
0
1
0
0
0
0
0
QUEUE
MAX CONT. ENTRY ENTRY(0) AVE.CONT.
AVE.TIME AVE.(-0) RETRY
QSYST
1 0 1001 999 0.000 0.002 0.859 0
STORAGE
CAP. REM. MIN. MAX. ENTRIES AVL.
AVE.C. UTIL. RETRY DELAY
SYST
3 2 0 3 1001 1 1.482 0.494 0 0
FEC XN PRI
BDT
PARAMETER VALUE
1002 0
10077.289 1002
1001 0
10079.189 1001
ASSEM CURRENT NEXT
0
5
1
6
Имитационное моделирование многоканальной СМО
Рассмотрим пример решения задачи при трех идентичных каналах
обслуживания с общей очередью к ним:
SYST STORAGE 3
GENERATE 10,5
QUEUE
QSYST
ENTER
SYST
DEPART
QSYST
ADVANCE 15,5
LEAVE
SYST
TERMINATE 1
Процесс выполнения моделирования многоканальной СМО
иллюстрируется на рис. 10.3.
Рис.10.3. Моделирование многоканальной СМО
Отчет по результатам имитационного моделирования
рассматриваемой системы приведен ниже.
GPSS World Simulation Report - Untitled Model 3.1.1
Thursday, October 27, 2012 18:32:36
START TIME
END TIME BLOCKS FACILITIES
STORAGES
0.000
5006.995 7
0
1
NAME
QSYST
SYST
VALUE
10001.000
10000.000
LABEL
LOC BLOCK TYPE
CURRENT COUNT RETRY
1 GENERATE
501
ENTRY COUNT
0
0
2
3
4
5
6
7
QUEUE
501
ENTER
501
DEPART
501
ADVANCE
501
LEAVE
500
TERMINATE
500
0
0
0
0
0
0
1
0
0
0
0
0
QUEUE
MAX CONT. ENTRY ENTRY(0) AVE.CONT.
AVE.TIME AVE.(-0) RETRY
QSYST
1 0 501 500 0.000 0.002
1.043 0
STORAGE
CAP. REM. MIN. MAX. ENTRIES AVL.
AVE.C. UTIL. RETRY DELAY
SYST
3 2 0 3
501 1 1.495 0.498 0 0
FEC XN
PARAMETER
502 0
501 0
PRI
BDT
VALUE
5008.688 502
5009.330 501
ASSEM CURRENT NEXT
0
5
1
6
4.Теория принятия решений
4.1. ТИПОЛОГИЯ ПРОБЛЕМНЫХ ЗАДАЧ ТПР
По классификации Саймона все проблемы подразделяются на
три класса:
1.
Хорошо
структурированные
или
количественно
сформулированные
проблемы,
в
которых
существенные
зависимости могут быть выражены количественно. Эти проблемы
составляют предмет теорий исследования операций, мaccoвoгo
обслуживания, марковских процессов, надежности и др.
2. Неструктурированные, или качественно выраженные
проблемы, coдержащие лишь словесные описания важнейших
acпектов изучаемого объекта, eгo признаков и характеристик,
количественные зависимости между которыми неизвестны.
3. Слабо структурированные проблемы, содержащие как
качественные, так и количественные зависимости между
параметрами системы и показателями ее эффективности, причем
качественные, малоизвестные, неопределенные зависимости имеют
тенденцию доминировать. Эти проблемы составляют предмет
системного анализа и теории принятия решений.
Объектом применения эвристических методов, прежде всего,
являются слабо структурированные проблемы, а также
структурированные проблемы в условиях неопределенности целей
применений
и
конфликтности,
связанной
с
многокритериальностью.
Например,
при
проектировании
компьютерной системы желательно одновременное достижение:
высокой производительности, надежности и точности, малого веса,
габаритов, энергопотребления, шума, вредных воздействий и
потребления расходных материалов, высоких графических
возможностей, низкой стоимости, больших объемов памяти.
Обеспечение множества перечисленных требований зачастую
противоречиво, например, высокая надежность и низкая стоимость
одновременно не достижимы. Таким образом, в условиях
многокритериальности естественно возникновение технических
противоречий, разрешение которых требует нахождения
компромисса,
как
правило,
эвристическими
методами.
Многокритериальные (векторные) задачи теории принятия
решений (ТПР) возникают при:
стремлении достичь некоторого множества целей
(высокая надежность низкая стоимость и эксплуатационные
расходы, большие объемы хранения, оперативность поиска и
обработки информации и др);

многофункциональности системы (например, в одном
устройстве совмещены функции принтера, сканера, факса, модема,
телефонного и копировального аппарата);

различных условиях применения (ноутбук может
использоваться как мобильное устройство с питанием от батареи и
связью через беспроводные системы и как стационарное с
питанием от электросети с возможностью подключения к
проводным локальным вычислительным сетям и т п).
Решение
векторных
(многокритериальных)
задач
в
большинстве случаев (при отсутствии однозначного решения в
области Парето, когда одна альтернатива доминирует над
остальными по всем параметрам) требует нахождение компромисса
на основе эвристических приемов.
Применение эвристических методов эффективно в условиях
неопределенности (например, решение открытия предприятия
сервиса в условиях не достаточного изучения спроса и
конкуренции).
Одним из центральных приложений эвристических методов
является разрешение системной проблемы. Выделяются девять
признаков системной проблемы, которые определены ниже.
Слабая структурированность. Слабо структурированные
проблемы, содержащие как качественные, так и количественные
зависимости между параметрами системы и показателями ее
эффективности, причем качественные и неопределенные
зависимости доминируют.
Конфликтность.
Системные
проблемы
формируются
противоречиями между стремлением технической системы,
природы и общества к своему развитию и всегда ограниченными
возможностями практической реализации этого устремления.
Неопределенность. Динамику системных проблем можно
описать лишь возможными сценариями (вариантами) развития
событий. Учесть заранее все ситуации, с которыми придется
столкнуться при разрешении системной проблемы, невозможно.

Неоднозначность. Системная проблема часто имеет
несколько вариантов разрешения, которые затруднительно
ранжировать по их предпочтительности.
Наличие риска. Для разрешения любой системной проблемы
требуются определенные ресурсы (финансовые, материальные,
информационные и другие), вложение которых непременно
сопровождается
элементами
риска,
обусловленными
противодействием со стороны как внешних, так и внутренних сил.
Противодействие связано с тем, что любой вариант разрешения
системной проблемы отвечает интересам одних субъектов и
ущемляет интересы других.
Многоаспектность. Системные проблемы затрагивают
множество разнородных сторон той субстанции, в которой они
возникают и развиваются, а между этими сторонами существует
взаимное влияние. При решении социальных проблемах
анализируются гуманитарные, экономические, политические,
этнические и другие взаимосвязанные вопросы. Разрешение
технических проблем связано с экономическими, финансовыми,
технологическими, эстетическими, экологическими и другими
аспектами.
Комплексность. Системные проблемы затрагивают, как
правило, области многих научных дисциплин (математики, физики,
химии, биологии, социологии, экономики и др.), но ни одна из них
в отдельности не дает эффективные способы их целостного
разрешения.
Эволюционность. Любая системная проблема является
продолжением какой-либо проблемы прошлого, и сама является
источником новой проблемы. Поиск решения проблемы должен
исключать возникновение новых проблем и поддерживать
преемственность в развитии.
Эвристические методы применяются при решении творческих
задач связанных с разрешением противоречий (конфликтов).
Область применения эвристических методов - решение
изобретательских,
научных,
социальных
экономических,
экологических и других системных задач, требующих
нестандартного творческого подхода.
В процессе решения изобретательских и творческих задач
выделяются этапы:
формулирование проблемы;

определение критериев выбора решения ;

определение весов критериев;

формирование
(генерирование)
альтернатив,
включая перечисление известных вариантов и генерирование
дополнительных вариантов;

анализ альтернатив;

выбор альтернативы;

внедрение альтернативы;

оценка эффективности решения.
Реализация перечисленных этапов, характерных для
различных творческих процессов, во многом опирается на
эвристические методы, в том числе поиска решений проблемных
задач, среди которых выделяется иерархия методов, включающая:
случайный, систематический и логический поиск.
РАЦИОНАЛЬНОЕ ПОВЕДЕНИЕ
Одно из основных допущений теории принятия решений
состоит в том, что человек делает рациональный выбор.
Рациональный выбор означает, что решение является результатом
упорядоченного процесса мышления. При условии рациональности
поведения существует некоторая функция, устанавливающая
человеческий выбор - функция полезности. Полезность в процессе
выбора личностью с рациональным мышлением максимизируется.
Полезность - это воображаемая мера психологической и
потребительской ценности различных благ. Человек оценивает
различные альтернативы и выбирает из них наиболее полезную.
Человек выбирает какие-то действия, когда на получаемый
результат (исход) действия влияют случайные события,
неподвластные человеку. Имея некоторые знания о вероятностях
событий, человек может рассчитать наиболее выгодную
совокупность и очередность своих действий.
Обозначим через х, у, z различные исходы (результаты)
процесса выбора, а через р, q-вероятности тех или иных исходов.
Лотереей называется игра с двумя исходами: исходом х,
получаемым с вероятностью р, и исходом у, получаемым с
вероятностью 1-р . Примером лотереи является подбрасывание
монеты. Ожидаемая (или средняя) цена лотереи определяется по
формуле рх+(1—р)у.

Возникают вопросы: нельзя ли заменить ЛПР автоматом и
следует ли при принятии решений учитывать какие-то особенности
человеческого поведения? Известен парадокс Алле [30], суть
которого поясняется двумя лотереями на рис. 7. 1 а)
а)
б)
в)
Рис 7.1 . Парадокс Алле
Обозначим: U(5 млн)=1; U(l млн)=U; U(0)=0. В лотерее рис.
7.1 а) есть выбор между действиями А (получить 1 млн) и В
(согласиться на лотерею). В экспериментах подавляющее
большинство людей предпочитает А. Из этого следует U>0,1+0,89U
или U>10/11.
Во лотерее 7.1 б) есть выбор между действиями С и D.
Подавляющее большинство людей предпочитает действие С (почти
та же вероятность «проиграть» но выигрыш больше). Тогда
0,1>0,11U, т.е. U<10/11. Совершая такой выбор, люди действуют не
в соответствии с функцией полезности.
Рассмотрим две лотереи, показанные на рис. 7. 1 в), для
которых средняя цена лотерей одинакова, но эксперимент
показывает, что люди предпочитают правую лотерею, где при той
же средней цене риск проигрыша исключен.
Часто наблюдается отклонение поведения людей от
рационального. Приведем один из наиболее известных примеров
нерационального поведения людей - «дилемму генерала» [30].
Генерал потерпел поражение в войне и хочет вывести свои войска
(600 чел.) с территории противника. У него есть две возможные
дороги, и разведка дала оценки возможных потерь при выборе
каждой из них. Данные о дорогах и возможных потерях
представлены на рис. 7.2.а).
a)
б)
Рис. 7.2 Пример нерационального поведения
Большинство людей, выбирают первую дорогу, стараясь
избежать лотереи, когда в одном из исходов погибает весь личный
состав соединения. Но эта же дилемма была представлена
испытуемым в ином виде (рис. 7.2 б). Теперь уже большинство
испытуемых выбирает вторую дорогу, так как на ней с
вероятностью р=1/3 можно спасти все соединение. Легко увидеть,
что лотереи на рис. 7.2 эквивалентны, но одна из них представлена
в виде выигрышей, а другая - в виде потерь.
4.2. ПСИХОЛОГИИ КОЛЛЕКТИВНОГО ВЫБОРА
Рассмотрим особенности психологии коллективного выбора.
При расхождении мнений в группе голосование является
единственно возможным способом формирования коллективного
решения. Но процедуры голосования обладают рядом свойств, в
некоторых случаях дающих неожиданный или нежелательный
результат. Перечислим такие парадоксы голосования.
Коллектив не всегда прав. Коллектив состоит из субъектов,
каждый из которых может заблуждаться. Это приводит к тому, что
голосование, даже единогласное, не гарантирует правильности
принятого решения. Вероятность ошибки коллективного мнения
меньше, но она не нулевая. Известны случаи (Бруно, Галилей,
Коперник и др.), когда один несогласный располагал истиной, а все
остальные заблуждались.
Возможность непринятия решения. Процедура голосования
может закончиться тем, что согласованные условия принятия
решения (скажем, "простое большинство" 50% плюс один голос)
не будут выполнены и, следовательно, решение не будет принято.
Парадокс Кондорсе. Суть парадокса в возможности
цикличности графа предпочтений. Пусть каждая из трех фракций
парламента, образующих большинство лишь попарно, выдвинула
свой вариант законопроекта: а, b и с. Если индивидуальные
предпочтения фракций таковы: (a>b>c), (b>с>а) и (с>а>b), то любая
процедура закончится неприятием решения. При переходе к
процедуре парного сравнении (по олимпийской системе) исход
зависит от последовательности сравнения пар альтернатив.
Например, (a, b) a (a, c) c , при другой последовательности
(a, c) c, (b, c) b . То есть результат зависит от порядка попарного
голосования, задаваемого спикером.
Возможность победы меньшинства не исключена при
мажоритарной системе голосования. Рассмотрим некоторые такие
возможности.
Первая - признание легитимными (законными) выборы при
низкой (меньше 50%) явке избирателей. Решение автоматически
предоставляется меньшинству.
Меньшинство может победить и при стопроцентной явке
избирателей в случае "растаскивание" голосов. Пусть одна партия
обладает 60 % потенциальных голосов, второй принадлежит 40 %
электората. Если первые выдвинут двух кандидатов, да еще
равноценных, а вторые одного, то победит меньшинство. Другая
возможность потенциальной победы меньшинства - создание
множества «виртуальных партий» с программами близкими к
партии большинства.
Меньшинство имеет шансы победить при стопроцентной явке
и без растаскивания голосов. Пусть решение принимается
большинством голосов в 2/3, то возможность победы меньшинства
иллюстрируется на рис. 7.3, из которого видно, что победило
меньшинство в 4/9 против 5/9. Для реализации такой возможности
необходимо выполнение трех условий: выборы должны быть
многоступенчатыми, на каждой ступени решение принимается по
большинству голосов, меньшинство должно соблюдать дисциплину
голосования (т.е. голосовать именно там, где нужно).
Рис 7.3. Парадокс голосования
Парадокс подавляющего большинства. Какой бы высокий
процент большинства ни был назначен для легитимности принятия
решения
оно не является демократическим.
Предложим
максимально "демократичную" процедуру голосования, состоящую
всего из двух правил:
а) Решение принимается при любом числе N голосующих
только в том случае, если "за" проголосовало не менее N-1 человек,
и лишь один (не более!) "против" (N большое).
б) Каждый голосует "за", если предложенная альтернатива ему
лично не наносит ущерба (и тем более, если она ему выгодна).
Председательствующий может (если захочет) через эту
процедуру реализовать любое угодное ему лично решение.
Пусть "состояние" – это наличие у каждого определенной
суммы. Из любого начального состояния с помощью введенного
правила можно перейти в любое наперед заданное состояние за
конечное число шагов. Шаг первый: кто за то, чтобы у такого-то
отобрать все деньги и раздать их всем поровну? Исход ясен.
Можно, для ускорения процесса, предложить у такого-то отобрать
деньги и отдать целевой персоне. Процедура и тут сработает. Рано
или поздно цель будет достигнута, вполне легитимно. Суть
парадокса состоит в том, что данная процедура узаконивает
принесение в жертву интересов одного всем остальным. При этом
остальные забывают, что каждый из них может стать жертвой.
ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ
Задача принятия решений (ПР) возникает, когда присутствует
несколько вариантов действий (альтернатив) для достижения
заданного или желаемого результата. При этом требуется выбрать
наилучшую в определенном смысле альтернативу.
Общая постановка задачи принятия решений формулируется
следующим образом. Пусть X— множество альтернатив, Y—
множество возможных последствий (исходов, результатов).
Предполагается существование причинной связи между выбором
некоторой альтернативы xi X и наступлением соответствующего
исхода yi Y . Кроме того, предполагается наличие механизма
оценки качества такого выбора — обычно оценивается качество
исхода. Требуется выбрать наилучшую альтернативу, для которой
соответствующий исход дает наилучший результат.
В теории принятия решений используются "разумные"
процедуры выбора из нескольких возможных альтернатив
наилучшей. Насколько правильным будет выбор, зависит от
качества данных, используемых при описании ситуации, в которой
принимается решение. С этой точки зрения процесс принятия
решений может принадлежать к одному из трех возможных
вариантов.
1. Принятие решений в условиях определенности, когда
данные известны точно.
2. Принятие решений в условиях риска, когда данные можно
описать с помощью вероятностных распределений.
3. Принятие решений в условиях неопределенности, когда
данным нельзя приписать относительные веса (весовые
коэффициенты), которые представляли бы степень их значимости в
процессе принятия решений.
По существу, в условиях определенности данные надежно
определены, в условиях неопределенности они не определены.
Принятие решений в условиях риска, следовательно, представляет
"промежуточный" случай.
Выделяются задачи принятия решений в условиях
многокритериальности когда имеется несколько целей и
соответственно оценок эффективности альтернатив (рис. 8.1).
Задача принятия решений
Выбор оптимальных
параметров
С числовыми
критериями
С нечисловыми
критериями
В детерминированных
ситуациях (в условиях
определенности)
Выбор оптимальной
стратегии действия
В антагонистических играх
В неантагониститических играх
В статистически неопределенных
ситуациях ( в условиях риска)
Выбор оптимальной
структуры (синтез
структуры)
С независимыми
элементами структуры
Со связанными элементами
структуры
В неопределенных
ситуациях
Рис 8.1. Задача принятия решений
Эвристические методы наиболее эффективно применяются
при принятии решений в условиях многокритериальности и
неопределенности.
4.3.МНОГОКРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
ПРИНЯТИЯ
РЕШЕНИЙ
Задачи векторной (многокритериальной) оптимизации
возникают, когда эффективность решения требуется оценить по
разным критериям.
Векторная задача принятия решений представляется как
<T, A, K, X, F, G, D>, где T – постановка задачи; A – множество
альтернатив; K – множество критериев; X – множество шкал оценок
критериев; F – отображение множества допустимых решений в
множество предпочтений эксперта; D – решающее правило,
называется мно гок ритер иальной , если множество K содержит
два или более элементов.
Необходимо отметить, что большинство практических задач
принятия решений являются многокритериальными. В частности,
при проектировании информационных комплексов системные
интеграторы анализируют различные варианты их архитектурного
построения на основе критериев: высокая производительность ,
низкая стоимость, высокая надежность и др. Однако достигнуть
наилучших значений одновременно по перечисленным критериям
как правило невозможно.
Постановку
задачи
векторной
оптимизации
можно
представить следующим образом:

Q1 ( x )

Q2 ( x )
min (max) ,
min (max) ,
.......... .......... .......... .. ,

Qs ( x ) min (max) ,
g1 ( x1 , x2 ,..., xn ) b1 ,
g 2 ( x1 , x2 ,..., xn ) b2 ,
.......... .......... .......... .. ,
g m ( x1 , x2 ,..., xn ) bm ,
dj
xj
D j , j 1,2,..., n .
Многокритериальность задач ТПР обусловлена:
Множественностью технических требований, которые
предъявляются к системе и, соответственно, выбором нескольких
критериев оптимальности;
наличием нескольких целей разработки (выбора) системы
(ИС должна быть надежной, высокопроизводительной, дешевой,
занимать мало места, быть малошумной и дешевой в эксплуатации,
потреблять мало электроэнергии, и др.);
сложностью структуры системы, включающей несколько
взаимосвязанных подсистем, каждая из которых оценивается по
своим параметрам (например, построение корпоративной
информационной
системы,
состоящей
из
иерархической
коммуникационной подсистемы, кластера серверов, рабочих
станций, сети хранения данных);
необходимостью обеспечения оптимальности системы при
различных условиях ее функционирования (например, Notebook,
который работает как в стационарных условиях (электропитанием
от сети, проводная сеть Ethernet c выходом в Internet) или
мобильных условиях (питание от батареи, беспроводная связь и
др.);
многофункциональностью системы (совмещение принтера,
факса, сканера, модема);
цикличностью работы системы. Система в цикле
выполняет различные задачи (например, в контуре управления
технологическим процессом сбор информации с датчиков,
обработка информации, формирование управляющих воздействий в
соответствии с циклом работы технологического процесса).
Трудности многокритериальных решений вызваны:
противоречиями между частными критериями (улучшение
по одному приводит к ухудшению по другому);
сложностью выбора принципа оптимальности;
учетом приоритетов различных критериев;
измерением различные частных критериев в различных
единицах (Кг, сек, руб и.т д).
Нормализация частных критериев оптимальности. Чтобы
согласовать различные единицы измерения, нужно произвести
нормализацию.
Под нормализацией понимается приведение частных
критериев к единому безразмерному виду. Когда частные
критерии оптимальности имеют одинаковую шкалу измерения и
приведены к безразмерному виду при помощи положительного
линейного преобразования:


~  Qi ( x ) Qi
(Qi ( x )) Qi ( x )
Qi Qi
где Qi
,
max Qi ( x) , Qi
x Dx
min Qi ( x) , Qi
Qi , i 1,2,...s .
x Dx
Нормирование может осуществляться как
eq
eqн
, где eq –
величина, подлежащая нормализации, e qн - нормирующее идеальное
значение; в качестве нормирующих используются максимальные
значения (Е1/maxE), или разброс max ei min ei (E1/(maxE–minE)).
Например, пусть варианты решений представлены векторами:
(1,2,3,4,1), (2,1,3,3,5), (2,7,2,2,5) , тогда нормирование может быть
осуществлено как ( 1 , 2 , 3 , 4 , 1 ), ( 2 , 1 , 3 , 3 , 5 ) ,( 2 , 7 , 2 , 2 , 5 ) .
2 7 3 4 5
2 7 3 4 5
2 7 3 4 5
При нормализации времени ожидания запросов в
многомашинной ВС (представленной системой массового
обслуживания) в качестве максимального может быть взято время
ожидания в системе с одной машиной при распределении в нее
всего потока запросов, или предельно допустимое по техническому
заданию (ТЗ) время ожидания.
Этапы решения многокритериальных задач:
1. Нахождение области допустимых решений R;
2. Нахождение области не худших (эффективных) решений
( области компромиссов - области Парето);
3. Сужение области не худших решений (области Парето);
4. Поиск решения в суженной области не худших решений.
Первый и второй этапы при выборе решений предполагают
использование некоторого безусловного критерия предпочтения БПК, предполагающего объективный выбор. Заметим, что в ряде
случаев, поиск решения может завершиться на втором или третьем
этапах.
Поиск решения на четвертом этапе (среди не худших
решений) может осуществляться на основе:
некоторого условного критерия предпочтения (УПК),
допускающего субъективность ЛПР;
функции полезности, учитывающей предпочтения ЛПР
(субъективные);
обобщенного критерия эффективности, учитывающего
взаимосвязь между частными критериями (предполагает
объективность решения, но требует глубокое изучение объекта).
Решение задачи в определенной мере опирается на
эвристические методы.
4.4.
ОБЛАСТЬ
ЭФФЕКТИВНЫХ
ОПТИМАЛЬНОСТЬ ПО ПАРЕТО
Пусть имеются две альтернативы:
a ' ( x1 ' x2 '... xm ' )
РЕШЕНИЙ.
X ',
a" ( x1" x2 "... xm " )
X ",
X ' доминирует по
альтернатива
доминирования по Парето) X '  X " если
i( xi ' xi " ) ( i( xi ' xi " )).
Парето
(отношение
.
Если для y Y не существует более предпочтительного по
Парето, то y называется эффективным или Парето оптимальным
решением, т.к. решение не может быть улучшено по одному
критерию без ухудшения по другому. Множество эффективных по
Парето решений образует область компромисса.
ПРИНЦИП ПАРЕТО - оптимальное решение следует искать
только среди элементов множества недоминируемых элементов
(область компромисса, область Парето).
Действительно,
иначе
всегда
найдется
более
предпочтительная точка y Y .
Множество Парето соответствует решениям не сравнимым по
ПАРЕТО.
(x , x )
i
Rnp
xi
xi
j
xj
xj
Если
i (x'i >x”i), то имеет место доминирования по
отношение Слейтера. Решение называют слабоэффективным
решением многокритериальной задачи или решением эффективным
по Слейтеру, если не существует более предпочтительного по
Слейтеру решения.
Если решение эффективно по Слейтеру, то оно не может быть
улучшено сразу по всем критериям.
Пример: Пусть альтернативы представлены точками 1-5 на
рис. 8.2.
Рис 8.2. Представление множества альтернатив
При переходах 5-1, 1-2, 3-4, 4-5 улучшается только один
критерий. При 2-3 эти решения не доминируют по Парето, т.к. один
параметр лучше, а др. хуже.
{1, 2, 3, 4} - слабоэффективные решение (область Слейтера),
{2, 3} – эффективные решения (область Парето)
Дано множество решений:
(1, 2, 3,4, 5),
(1, 1, 1, 1, 1),
(2, 1, 3, 4, 5),
(2, 2, 2, 2. 2),
(2, 1, 3, 4, 4),
для которого область Парето находим как:
(1,2,3,4,5), (2,1,3,4,5), (2,2,2,2,2)
Соотношение множества решений, допустимых решений,
решений эффективных по Парето и Слейтеру проиллюстрировано
на рис.8.3.
Рис. 8.3. Соотношение множества решений, допустимых
решений, решений эффективных по Парето и Слейтеру
Определение
области
компромиссов.
Рассмотрим
некоторую точку A в области решений R. Стоит задача определить
все множество точек, которые доминируют над точкой A. Точки
лежащие выше и правее (северо–восточнее) выбранной точки А
доминируют над ней по Парето, причем все не худшие решения
лежат на границе области R.
R
Рис 8.4. Определение области Парето.
Существует различные способы определения области
компромисса. При графическом - на границе области решений
помешается прямоугольный треугольник и если продолжение
линий исходящих из прямого угла не пересекают границу области,
то точка принадлежит области компромисса.
Алгоритм формирования множества Парето. Пусть имеется
n альтернатив, каждая из которых характеризуется набором
частных критериев. Алгоритм состоит из n циклов сравнения
каждой альтернативы с уже вошедшими в множество Парето
альтернативами.
В каждом цикле сравнения возможны три исхода:
1. Если сравниваемая альтернатива по всем частным
критериям хуже чем хотя бы одна из вошедших в множество
Парето, то альтернатива исключается из рассмотрения.
2. Если сравниваемая альтернатива хотя бы по одному
частному критерию хуже, а по другим лучше, чем каждая из
альтернатив уже вошедших в множество Парето, то
эта
альтернатива добавляется в множество Парето.
3. Если сравниваемая альтернатива по всем частным
критериям лучше, чем одна или несколько альтернатив из
множества Парето, то эти альтернативы исключаются, а лучшая
включается в множество Парето.
Пример:
Альтернативы y1,y2
Циклы
сравнения
1
2
3
4
5
6
7
8
9
3, 10
2, 9
9, 5
6, 7
4, 4
6, 4
8, 3
7, 8
10, 6
1
2
3
4
5
6
7
8
9
Множество
Парето
1
1
1, 3
1, 3, 4
1, 3, 4
1, 3, 4
1, 3, 4
1, 3, 8
1, 8, 9
Множество Парето для двух критериев можно построить
графически. Для каждой точки — кандидата в множества Парето —
строится прямоугольник. На рис. 8.4 такие прямоугольники
построены для точек 1, 2 и 6. Все точки, оказавшиеся внутри
построенных прямоугольников, например, точки 8, 4, 5 для
прямоугольника с вершиной в точке 6, исключаются из
рассмотрения. Процесс продолжается до тех пор, пока не будут
построены прямоугольники для всех точек. Неисключенные точки
(в данном случае это точки 1, 3, 9) образуют множество Парето.
Заметим, что при других направлениях улучшения критериев y1, y2
правила исключения будут другими.
y2
1
2
3
7
8
6 9
4
5
y1
Рис48.4 Определение области Парето (дискретный случай).
Метод Н. Н. Моисеева заключается в последовательном
итеративном процессе решения простейших оптимизационных
задач. Сначала задаются начальные произвольные значения
критериев: W1 (o)=C1; W2 (0)=C2.
Затем решаются две оптимизационные задачи:
1.W1 (0) max; W2(0)=C2;
W2(1) max; W1 (1) =С1
Решив эти две задачи, находят точки а и b.
Прямая, соединяющая эти две точки, является областью
Парето в первом приближении. Далее решаются две аналогичные
задачи. При этом задаются значения критериев: W1(o)=Сз; W2(0)=С4.
Затем решаются две оптимизационные задачи:. W1 (2)
max;
(2)
(3)
(3)
W2 =C3; W2
max; W1 =С4
Через полученные точки снова проводят прямые. После
соединения точек получают ломаную acdb, которая является
областью Парето второго приближения. В большинстве случаев
второе приближение является достаточным. В случае большего
числа критериев метод может выполняться с помощью ЭВМ.
8.5. СУЖЕНИЕ ОБЛАСТИ ЭФФЕКТИВНЫХ РЕШЕНИЙ.
Сужение множество Парето на основе критерий
удовлетворения ТЗ. Пусть имеем два частных критерия y1, y2 и
требования технического задания (ТЗ), выраженные неравенствами:
а1<y1<а2; b1<y2<b2
определяющими прямоугольную форму
области допустимых значений критериев y1, y2. Возможное
взаимное расположение области D и множества Парето приведено
на рис.8.5 может быть различно. На рис. 8.5 а) область Парето
соответствует ТЗ. В примере неграмотного ТЗ на рис. 8.5 в) ни одна
из точек множества Парето не попадает в область допустимых
значений, а на рис 8.5 б) вообще ни одна точка области возможных
решений не соответствует ТЗ.
Рис 4.5 Сужение области Парето
Метод Т-упорядочивания. Основан на том, что у ЛПР
имеется представление о предпочтительности одних критериев над
другими.
Рассмотрим две альтернативы
Z
( Z1....Z i ..... Z j ..... Z m ),
W
( Z1....Z i
..... Z j
..... Z m ).
Критерии i-й, j-й, равноценны, если для всех векторов Z и W
оценки Z(Zm) и W(Zm) одинаковы по предпочтению независимо от
δ, то есть, если от одного критерия вычесть δ, а другому прибавить,
эффективность альтернативы не измениться.
Критерий i-й более важен, чем j-й, если оценка Z менее
предпочтительная, чем W.
Метод Т-упорядочивания позволяет строить отношения
доминирования более сильные, чем отношения по Парето.
Пусть заданы решения
Z
W
(1;0.5;0.1;0.2),
(0.4;0.9;0.1;0.2),
которые по Парето несоизмеримы. Если первый критерий
предпочтительней, чем второй, тогда W можно улучшить:
W ' (0.8;0.5;0.1;0.2) W '  W По Парето Z доминирует над W’, а т.к.
W’  W, то Z  W. Таким образом, путем переноса мы смогли
сравнить несоизмеримые по Парето решения, что и требовалось
сделать.
4.6. ПОИСК РЕШЕНИЯ В ОБЛАСТИ ПАРЕТО
Возможны следующие способы поиска решений в области
Парето:
приведение векторного показателя к скалярному;
ранжирование критерия по важности;
сравнение эффективности относительно затрат;
выявление
взаимосвязей
между
различными
параметрами и назначение комплексного критерия;
использование функции полезности.
Приведение векторного показателя к скалярному базируется
на принципах: равенства, абсолютной или относительной уступки.
Принцип равенства.
Все
критерии
принимаются
одинаково важными. Наилучшим компромиссным решение
считается такое, при котором достигается равенство всех
локальных критериев. Графически искомое решение - точка
пересечения прямой проведенной из центра с границей R. Рис. 8.6
а)
Рис 4.6 Применение принципа равенства
На рис. 4.6 б-г) проиллюстрированы трудности применения
принципа равенства к поиску решений. Частично преодолеть
проблему позволяет принцип квазиравенства, предусматривающего
поиск решения, для которого значения отдельных локальных
критериев отличаются друг от друга не более чем на величину
(рис.4.6 д)).
Принцип абсолютной уступки. По принципу абсолютной
уступки «справедливым является такой компромисс, при котором
суммарный абсолютный уровень снижения одного или нескольких
критериев не превосходит суммарного абсолютного уровня
повышения других критериев».
Пусть есть два решения Е0(е10, е20, …, ек0) и Е1(е11, е21, …, ек1)
k
k
q
1
(e
абс
k
q
0
q
1
e )
q 1
e0q ,
e
q 1
q 1
Если ∆абс> 0, то решение Е1 лучше решения Е0, иначе лучше
решения Е1.
Принципу абсолютной уступки соответствует критерий
оптимальности :
k
eq
max
q 1
Пример: Даны два решения Е0(2,7) и Е1(3,5), тогда ∆абс = (3-2)
+ (5-7) = -1 < 0 , следовательно, альтернатива E0 лучше Е1.
Принцип
относительной
уступки.
По
принципу
относительной уступки
«Справедливым является такой
компромисс, при котором суммарный относительный уровень
снижения качества одного или нескольких критериев не
превосходит суммарный относительный уровень повышения
качества по остальным критериям».
Пусть есть два решения Е0(е10, е20, …, ек0) и Е1(е11, е21, …, ек1)
(e1q e0q )
e0q
q 1
k
отн
k
q 1
q
q
0
e
Если ∆отн > 0, то решение Е1 лучше решения Е0, иначе лучше
решение Е1.
Принципу относительной уступки соответствует критерий
оптимальности:
k
eq
max
q 1
Для ранее сравниваемых решений Е0 (2,7) и Е1 (3,5)
∆отн = (3-2)/2 + (5-7)/7 = 3/14 > 0 , таким образом решение E1
лучше решения Е0 (в отличии от ранее проведенного выбора по
принципу абсолютной уступки ).
Аддитивный скалярный критерий. Аддитивный критерий
формируется следующим образом:
нормируем все критерии;
вводим ранжирование критериев с помощью
1, 0
1;
параметра αi - причем
i
i
i
ищем оптимальное решение по
критерию оптимальности задаваемому в виде
аддитивному
i
xi
max .
i
При максимизации обобщенного критерия если частный
критерий максимизируется (чем больше значение, тем лучше), то
он включается в свертку со знаком «плюс», если же он
минимизируется (чем меньше значение, тем лучше) - то со знаком
«минус».
Достоинство: В одном обобщенном критерии можно
объединять частные критерии, представляющие различные
физические величины (электрические, массогабаритные и др.).
Недостаток: Можно получить большие значения Y
(взвешенные суммы) за счет большого значения одного частного
критерия, но при недопустимо малых значениях других
критериев. Так на рис 8.7 Y2 > Y1, но y1 во втором случае ниже
допустимого (неравномерный вклад критериев).
1)
Y1=y1+y2
y2
y1
2)
Y2=y1+y2 >Y1
y2
y1 min
y1
Рис 4.7. Неравномерный вклад критериев
Пусть выбран обобщенный аддитивный критерий:
Y=а1*y1+а2*y2
Рис 8.8. Поиск решения по аддитивному критерию
Необходимо найти оптимальную точку множества Парето, в
которой Y имеет максимальное значение.
Для решения этой задачи построим линию уровня критерия Y,
т.е. линию постоянных значений: а1*y1+а2*y2=const, отсюда:
y2
const
1
* y1
2
Предельное значение положения линии уровня — положение,
когда линия уровня касается кривой границы множества Парето
(точка касания — точка оптимума рис. 8.8).
Из рис. 4.9 а) видно, что при малом весе a1 наибольший вклад
в Y вносит критерий y2, а при малом a2 — критерий y1.
Аддитивному критерию соответствует прямая
1 y1
2 y2 ,
которая достигает максимума при касании границы область
компромисса D. Из рис 8.9 б) видно, что аддитивный критерий
неприменим в случае невыпуклой области D.
А)
б)
y2
y2 опт
a2
y2 max
0
a1
y1 max
0
y1опт
y1
Рис 4.9. Множество Парето и аддитивный критерий
Тип нормализации и исключение заведомо неэффективных
альтернатив может влиять на результаты принятия решения.
Пусть имеются три альтернативы (решения):
f(x1)=(10, 10, 3), f(x2)=(8, 8, 10), f(x3)=(0, 0, 0).
Проведём нормировку:
f i ( x) min( f i )
max( f i ) min( f i )
для рассматриваемых
альтернатив получим: (1;1;0,3), (0,8;0,8;1), (0,0,0). И
соответственно имеем:
f1(x1)+f2(x1)+f3(x1)=2,3,
f1(x2)+f2(x2)+f3(x2)=2,6,
f1(x3)+f2(x3)+f3(x13)=0 ,
таким образом X 2 X1 (решение X2 предпочтительнее X1).
Если
провести
нормировку
без
учета
худшего
решения(0,0,0), то получим (1, 1, 0) и (0, 0, 1) и, соответственно,
f1(x1)+f2(x1)+f3(x1)=2, f1(x2)+f2(x2)+f3(x2)=1, то есть X1 X 2 (X1
предпочтительнее X2).
Таким образом, показано, что нормирование влияет на выбор
решения.
Мультипликативный
скалярный
критерий
Мультипликативный скалярный критерий определяется в виде
k
k
xi
или
max
xi
i 1
i
max .
i 1
Во втором случае учитывается важность (приоритета)
локальных критериев. Если локальный (частный) критерий при
возрастании приводит к возрастанию эффективности, то он
ставится в числитель, иначе – в знаменатель. Если xi ≤0 , то
0.
требуется преобразование xi
так чтобы xi
Мультипликативный критерий можно свести к аддитивной
форме:
k
k
k
Ai
lg k
i
i
lg Ai .
i 1
i 1
Возможна комбинация: мультипликативного и аддитивного
критериев:
k
k
k
x
i i
i 1
(1
)
xi i .
i 1
Варьированием параметра β от 0 до 1 вводится значимость
аддитивного и мультипликативного критерия в обобщенном
критерии.
Пусть объект характеризуется двумя частными критериями y1
и y2 , а мультипликативный критерий имеет вид Y y 1 1 * y 2 2 . Для
простоты положим a1=a2=1. Тогда уравнение линий уровня
критерия Y будет иметь вид: y1*y2=const. Отсюда получаем
уравнение для y2 как гиперболу: y2=const/y1.Увеличение Y приводит
к параллельному сдвигу гиперболы. Ее предельное положение
(касание границы области Парето) дает оптимальную точку (рис
8.10).
Рис. 8.10. Область Парето и мультипликативный критерий
Пусть имеется два частных критерия y1, y2 и ЛПР может
объединить их в составе аддитивного либо мультипликативного
критерия: Y1=a1*y1(x)+a2*y2(x), Y 2 y 1 1 ( x ) * y 2 2 ( x ) , для которых
точки оптимума получаются при разных значениях аргументов,
т.е.:Arg Y1(x)опт Arg Y2(x)опт. Надо выяснить какой критерий более
оптимистичен.
y2
СЛТ
b2
II
III
СХТ
b1
a1
I
РТ
IV
a2
y1
Рис 4.11. Поле выбора решения
В поле выбора решения, представленном на рис. 8.11 можно
указать следующие характерные точки: РТ — рассматриваемая
точка; СЛТ — самая лучшая точка (утопическая точка); она обычно
недостижима, так как y1 и y2 одновременно не могут принять
своих наилучших значений; СХТ — самая худшая точка
(антиутопическая точка).
Рассмотрим квадранты поля выбора: I, II, III и IV. Все точки
(решения) в квадранте I — лучше РТ, так как в них y1 и y2 больше,
чем в РТ, независимо от точки зрения ЛПР. Все точки в квадранте
III — хуже РТ, так как в них y1 и y2 меньше, чем в РТ, независимо
от точки зрения ЛПР. В квадрантах II, IV — предпочтительность
решений (точек) относительно решения представленного РТ
зависит от точки зрения ЛПР его оптимизма (осторожности
склонности к риску).
Рассмотрим сначала аддитивный критерий (рис. 8.12). Пусть
ЛПР одинаково относится к критериям y1 и y2. Тогда линия уровня
Y=0.5*y1+0.5*y2=const — это линия равнодушия или нейтральная
в смысле предпочтения ЛПР. При нормировке поле выбора
решения станет квадратом, а нейтральная линия уровня —
биссектрисой областей II и IV.
Точки областей II и IV над нейтральной линией — лучше, чем
на этой линии, а под ней — хуже. Их количество одинаковое.
Линия уровня мультипликативного критерия делит области II и IV
на неравные части — худших точек больше, чем лучших. Поэтому
мультипликативный критерий выражает пессимистическую точку
зрения ЛПР. По аналогичным причинам оптимистический
критерий должен иметь линии уровня с обратной по сравнению с
мультипликативным критерием кривизной.
y2
мультипликативный
критерий
(пессимизм ЛПР)
оптимистический
критерий
аддитивный критерий
(нейтральность ЛПР)
y1
Рис 8.12. Оптимизм аддитивного и мультипликативного
критериев
Метод отклонения от идеала (целевое программирование).
Качество каждой альтернативы оценивается расстоянием между
этой альтернативой и некоторой идеальной альтернативой.
Идеальной называется альтернатива, в которой каждый частный
критерий принимает свое наилучшее достижимое значение с
учетом современного состояния техники, причем все частные
критерии должны принимать свои наилучшие значения
одновременно.
Идеальная альтернатива y (0 ) имеет идеальные параметры:
y
(0)
(0) (0) (0) (0)
y , y , y ,... y
1 2 3
n
Тогда можно определить расстояние между идеальной и
реальной альтернативой. Чем меньше это расстояние, тем лучше.
Различают следующие разновидности данного критерия:
1) Сумма абсолютных отклонений от идеала для частных
критериев одной размерности.
Y
| yi
i
y i(0 ) |
или
l
Y
i 1
n
ai( y i( 0 )
yi )
ai( y i
i l 1
y i( 0 ) )
.
максимизируемые
частные критерии
минимизируемые
частные критерии
y i(0 )
yi
yi
y i(0 )
Данный критерий нужно минимизировать, так как чем меньше
расстояние, тем ближе к идеалу.
2) Сумма относительных отклонений для частных критериев
разной размерности.
l
Y
i 1
ai
yi
yi
(0)
(0)
yi
y i max
n
i l
(0)
yi yi ,
ai
(0)
1
y i min y i
где yi max — максимальное значение y i на множестве заданных
альтернатив; yi min — минимальное значение y i на множестве
заданных альтернатив.
Принцип Максимина. Идея этого принципа состоит в
повышении уровня всех критериев в результате максимального
подтягивания критерия, имеющего наименьшее значение. В
векторе решений (x1, x2,…, xn) ищется критерий, имеющий
минимальное значение xmin , и выбирается решение позволяющее
увеличить xmin.
Решения состоит в выполнении этапов:
представления
всех
критериев
к
виду,
предусматривающему их максимизацию ( или минимизацию);
нормирования всех компонент векторов;
выделения для каждого вектора наихудшего элемента;
выбора среди наихудших элементов (представляющих
вектор) наилучшего, определяющего выбранную альтернативу.
Методы, основанные на ранжировании критериев.
Принцип главного критерия.
Метод состоит в том, что один
кр итер ий позицио нир уется как г лавный , а остальные
критерии переводятся в ограничения,
W1
W2
W3
max
C3
C3

W
k
C
k
Например: минимизируется стоимость информационной
системы C min при выполнении ограничений на среднее время
пребывания запросов в системе T Tдоп , либо ищется максимум
вероятности безотказной работы Pотк max при выполнении
ограничений на стоимость реализации проект системы C C В .
Метод лексикографической оптимизации. Пусть заданы две
альтернативы a’ и a’’, представляемых векторами W1’и W1’’.
Ранжируем критерии по их важности W1>W2>W3>…и т д .
Имеем a’  a’’:
если (W1’ > W1’’) ;
либо при (W1’ = W1’’) и (W2’ > W2’’);
либо при (W1’ = W1’’) и (W2’ = W2’’) и (W3’ > W3’’) и так
далее.
Метод последовательных уступок. Суть мето да уступок
состоит в том, что вначале решается задача оптимизации по
главному критерию W1 без учета значений по другим критериям.
Результат решения – это оптимальное значение W 1* критерия W1.
Лицо, принимающее решение, определяет величину уступки W1
для критерия W1. После этого производится оптимизация по
следующему по степени важности критерию W2 при выполнении
*
W1 . Эта процедура
ограничений на критерий W1: W1 W1
последовательно выполняется для всех критериев.
Алгоритм метода:
1. Определяем относительный ранг каждого из критериев:
W1>W2>W3>…
2. Проводим оптимизацию только по критерию W1, находя
некоторое решение X1= max W2.
3. Переводим W1 из ранга критериев в ранг ограничений,
давая ему некоторый запас изменения в худшую сторону. Уступка
обозначается ∆1.
4. Проводим оптимизацию по W2, в пределах заданной
уступки ∆1. Находим новое решение Х2(∆1)=max W2. При W1 ≥ X1
- ∆1.
5. Задаем уступку для Х2. При этом W2 ≥ X2 - ∆2.
6. Проводим оптимизацию по W3, в пределах заданных
уступок ∆1 и ∆2 . Находим новое решение Х3(∆1∆2)=max W3.
7. Аналогично Х1 и Х2 задаем уступку для Х3. При этом
W3 ≥ X3 - ∆3.
8. Повторяем для всех критериев.
Метод обобщенного критерия. Критерий представляется в
виде
удельной
стоимости
качества,
например,
производительность/стоимость. …
Подобный критерий широко используется в рекламе, но
следует заметить, что его использование часто приводит к выбору
морально устаревшей не эффективной, но дешевой техники.
8.7.
МЕТОД
ПОСЛЕДОВАТЕЛЬНОГО
ПОИСКА
УДОВЛЕТВОРИТЕЛЬНЫХ ЗНАЧЕНИЙ КРИТЕРИЕВ ДЛЯ
АНАЛИЗА СТРУКТУРИРОВАННЫХ ПРОБЛЕМ (STEM)
Метод STEM, применяется для многокритериальной
оптимизации. Исходными данными являются множество критериев
и
множество
линейных
ограничений.
{ Ci Ci ( x), i I }
Предполагается, что для каждого i-го критерия, i 1, m , получена
модель, связывающая вектор параметров x со значением критерия
Сi. Решение включает следующие этапы.
Этап 1. Последовательно для каждого из критериев решается
задача оптимизации. Результат решения для Сi-го критерия – это
*
оптимальные значения вектора параметров x i и оптимальное
*
значение критерия C i* . Полученные значения x i подставляются в
выражения для остальных j-x критериев и рассматриваются
значения Ci* j . Производится нормирование полученных значений,
результат нормирования C i* j обозначается как C i j . Полученные
значения заносятся в табл.8.1, в которой для каждого из критериев
выделяются отдельная строка и отдельный столбец.
Таблица. 8.1
Значения критериев для последовательной оптимизации
Крит
ерии
С
С2
C11 1
C12
Сj
Сm
1
С1
…
C1j
…
C1m
С2
C 21
C 22
…
Сi
…
…
C i1
C i2
…
Сm
…
…
C m1
C m2
1
…
C 2j
…
C 2m
…
…
…
…
…
…
…
…
…
…
…
…
Ci
j
C mj
C im
C mm
1
Так как значения критериев нормированы, то диагональные
элементы равны единице, а остальные элементы таблицы меняются
в диапазоне от нуля до единицы. В частности, элементы
C11 , C12 , ..., C1j , ..., C1m представляют значения соответственно критериев
C1 , C 2 , ..., C j , ..., C m , полученные при решении однокритериальной задачи
линейного программирования для критерия С1.
Этап 2. Вычисляются технические веса или индексы
критериев. Для этого формируется система уравнений
m
λi 1 αi
,
λ i 1 , где i – индекс критерия Сi; j – среднее значение
λj
1 αj
i 1
Сj-го критерия, равное
m
αj
i 1
Ci j
C jj
m 1
.
Таким образом, j – это среднее значение элементов Сj-го
столбца за исключением диагонального элемента. Результат
выполнения этого этапа – это значение индексов i, i 1, m .
Этап 3. Производится оптимизация по глобальному критерию
m
C
λ i Ci совместно с ограничениями. Результат решения – вектор
i 1
оптимальных параметров x 0 , а также компромиссные значения
локальных критериев C10 , C 20 , ..., Ci0 , ..., C m0 .
Этап 4. Аналитик производит попарное сравнение значений
критериев C1 , C 2 , ..., Ci , ..., C m , полученных при решении локальных
однокритериальных задач, а также при оптимизации глобального
критерия. Для выполнения этой процедуры исходные данные
представляются в виде табл.8.2.
Целесообразно формировать два варианта таблицы 8.2:
вариа нт 1 включает нормированные значения критериев, а
вариа нт 2 – их абсолютные значения. Очевидно, что первая
строка табл. 8.2 содержит наилучшие значения критериев. В
процессе попарного сравнения аналитик должен принять решение:
являются
ли
компромиссные
значения
критериев
удовлетворительными. Если да, то получено окончательное
решение, в противном случае – переход на этап 5.
Таблица 8.2.
Попарное сравнение значений критериев
Критерии
Задача
C
1
Локальная
однокритериальная
C
…
2
…
i
C11
C 22
C10
C 20
Глобальная
C
C
m
…
…
C ii
…
C i0
…
C mm
C m0
Этап 5. Определяется критерий Ck, компромиссное значение
которого является наименее удовлетворительным. Для выбранного
критерия Ck устанавливается предельное значение Dk, при котором,
по мнению аналитика, значения критерия Ck становятся
приемлемыми.
Этап 6.
Таблица 4.3.
Влияние ограничения на критерий Ck
Лока
льные
критерии
C1
C2
Ограничения на критерий Ck
Ck Dk
Ck
Dk –
… Ck
Dk – i0 Dk
Dk
C1(Dk)
C1(Dk
–
… C1(Dk – i0 Dk)
C2(Dk
–
… C2(Dk – i0 Dk)
Dk)
C2(Dk)
Dk)
…
Ck-1
…
Ck-1(Dk)
…
Ck-1(Dk –
Dk)
Ck+1
Dk)
…
Cm
…
Cm(Dk)
–
i0 Dk)
Ck+1(Dk –
Ck+1(Dk)
… …
… Ck-1(Dk
… Ck+1(Dk
–
i0 Dk)
…
Cm(Dk
–
… …
… Cm(Dk – i0 Dk)
Dk)
Производится
решение
(m–1)-й
локальных
однокритериальных
задач
оптимизации
с
учетом
удовлетворительного ограничения на критерий Ck Dk. Результат
решения – наилучшие значения критериев C1 , C2 , ..., Ck 1 , Ck 1 , ..., Cm при
наличии ограничения Ck
Dk.. Наилучшие значения критериев
обозначаются как C1(Dk), C2(Dk), …, Cm(Dk). Осуществляется
изменение
наилучшие
ограничения на критерий: Ck Dk Dk , и находятся
значения критериев для нового ограничения:
C1 ( Dk
Dk ), C 2 ( Dk
Dk ), ..., C m ( Dk
Dk ) .
Произвольное
ограничение
имеет вид Ck Dk i Dk , i 0, 1, 2, ..., i0 . Результаты выполнения этого
этапа представляются в виде табл. 8.3.
На основе анализа табл. 8.3 принимается решение об
окончательном значении для ограничения критерия Ck: C k Dk i Dk
Этап 7.
Полученное окончательное ограничение для
критерия Ck включается в состав ограничений исходной задачи, а
критерий Ck исключается из числа оптимизируемых критериев.
Производится переход на этап 1, выполняется следующая итерация
рассматриваемого метода.
4.8. МЕТОД РАНЖИРОВАНИЯ МНОГОКРИТЕРИАЛЬНЫХ
АЛЬТЕРНАТИВ ELECTRE
Исходными данными для применения метода ELECTRE
являются:
перечень
критериев
–
C1,C2,…,Ci,…,Cm;
множество
альтернатив A =(A1, A2, …, Ai,…, Ad); значения критериальных
оценок для каждой из альтернатив – ais , i 1, m; s 1, d .
Необходимо упорядочить альтернативы по степени их
перспективности.
Реализация метода включает выполнение следующих этапов.
Этап 1. Для каждого критерия эксперт устанавливает его
важность wi , i 1, m . Значения важности – это целое положительное
число.
Этап 2. Формируется таблица для индексов согласия, строки
и столбцы которой соответствуют множеству альтернатив. Индекс
согласия z A A определяет степень согласия перспективности As-й
альтернативы по отношению к Ar-й альтернативе:
m
zA A
wi / wi ,
s r
s r
i I ,I
i 1
где I – множество критериев, по которым альтернатива As
предпочтительней альтернативы Ar, т.е. ais air , i I ; I – множество
критериев, по которым альтернативы As и Ar равнозначны, т.е.
ais air , i I .
Таблица индексов согласия имеет следующий вид (табл. 8.4).
Таблица 8.4.
Индексы согласия
Альтернативы
A
A
Альтернат
ивы
1
…
2
z
…
z
…
r
A
d
…
z
*
…
2r
2d
…
…
…
…
… zsr
……
… zdr
…
…
zsd
…
…
…
*
*
A2
12
1r
21
As
…
Ad
…
z
A1
…
A
zs1
…
zd1
zs2
…
zd2
z
1d
z
…
Этап 3. Формируется таблица индексов несогласия, строки и
столбцы которой соответствуют множеству альтернатив. Индекс
несогласия u A A определяет степень отрицания гипотезы о
перспективности альтернативы As по отношению к альтернативе Ar.
Для вычисления u A A необходимо определить множество Iкритериев, по которым альтернатива Ar превосходит альтернативу
As и для каждого из них найти текущий индекс несогласия:
air a is
u A A (i)
, i I ,
s r
s r
s r
Li
где L – длина шкалы для i-го критерия, включенного в
множество I . Окончательно индекс несогласия u A A max
u A A (i ) .
i
s r
Индексы несогласия заносятся в табл. 8.5.
Таблица 8.5.
Индексы несогласия
Альтернативы
Альтернативы
A1
A2
…Ar
…
Ad
A1
*
u12
… u1r
…
u1d
A2
u21
*
… u2r
…
u2d
…
As
…
us1
…
us2
……
… usr
…
…
…
usd
…
Ad
…
ud1
…
ud2
……
… udr
…
…
…
*
s r
Этап 4. Устанавливаются предельные значения для индекса
согласия z(1) и индекса несогласия u(1).
Этап 5. Для каждой пары альтернатив As и Ar производится
сравнение индекса согласия z sr и индекса несогласия u sr с
предельными значениями z(1) и u(1). Если zsr z(1) и usr u(1), то
альтернатива As доминирует над альтернативой Ar, при условии, что
одно из неравенств выполняется как строгое.
Переход на этап 6. В противном случае альтернативы As и Ar
объявляются несравнимыми либо эквивалентными. Переход на
этап 7.
Этап 6. Доминируемая альтернатива Ar удаляется.
Оставшиеся
альтернативы
образуют
п ерво е
ядро
недо ми нир уемых аль тер на ти в .
Этап
7.
Производится
ослабление
требований
к
предпочтению альтернатив, т.е. уменьшается предельное значение
индекса согласия до величины z(2) и увеличивается предельное
значение для индекса несогласия до величины u(2). Переход на этап
5 для выполнения следующей итерации ранжирования альтернатив.
Результат – второ е ядро недоминируемых аль тер на ти в.
Количество итераций определяется аналитиком, в последнее ядро
входят наилучшие альтернативы, а последовательность ядер
соответствует их упорядочению по предпочтению.
4.9.
ПРИНЯТИЕ
РЕШЕНИЙ
В
УСЛОВИЯХ
НЕОПРЕДЕЛЁННОСТИ
Неопределенность при решении проблемных задач может
обусловливаться недостаточной осведомленностью ЛПР. Так,
могут быть заранее неизвестны: погода в некотором районе,
покупательский спрос на продукцию, объем перевозок,
соотношения рубля, доллара и евро, интенсивность потока
запросов, данные по интенсивности отказов элементной базы и т. д.
Условия зависят от объективной действительности, которую в
теории решений называют «природой». Рассмотренные варианты
принятия решений называются «играми с природой». «Природа» в
теории статистических решений рассматривается как некая
незаинтересованная инстанция, «поведение» которой неизвестно,
но, оно не содержит элемента сознательного противодействия
нашим планам. Таким образом, лицу принимающему решение не
противостоит
разумный
противник,
интересы
которого
противоположны.
Данные, необходимые для принятия решения в условиях
неопределенности, обычно задаются в форме матрицы, строки
которой соответствуют возможным действиям, а столбцы –
возможным состояниям системы.
Пусть, например, ставится задача закупки крупной (Е1) ,
средней (Е2) или мелкой (Е3) партии расходных материалов для
предприятия сервиса по печати фотографий. Эффективность
решения зависит от наплыва туристов, который определяется
условиями природы : F1- - лето солнечное, F2 - дождливое, F3 –
среднее по погоде.
Под результатом решения eij можно понимать оценку,
соответствующую варианту Ei и условиям Fj и характеризующие
прибыль, полезность или надёжность. Обычно мы будем называть
такой результат полезностью решения.
Тогда семейство (матрица) решений e имеет вид :
ij
F1
F2
Fn
E1
e11
e12
e1n
E2
e21
e22
e2 n
Em
em1 em 2
emn
Чтобы прийти к однозначному и по возможности наилучшему
варианту решению необходимо ввести оценочную (целевую)
eij сводится к одному
функцию. При этом матрица решений
столбцу. Каждому варианту Ei приписывается некоторый результат
eir, характеризующий, в целом, все последствия этого решения.
Такой результат в дальнейшем будем обозначать тем же символом
eir.
Ниже определим эвристические правила (критерии) выбора
считая для определенности, что лучшему варианту соответствует
большее значение показателя
Минимаксный критерий Вальда. Выбор решения по
минимаксному
критерию
(ММ-критерий)
осуществляется
следующим образом: матрица решений дополняется ещё одним
столбцом из наименьших результатов eir min
eij каждой строки.
j
Выбирается вариант соответствующий наибольшему значению
дополнительного столбца eir. y max
min eij
j
i
ММ-критерий применяется, если ситуация, в которой
принимается решение следующая: о возможности появления
внешних состояний Fj ничего не известно; решение реализуется
только один раз; необходимо исключить риск.
Пусть даны матрицы решений, выражающее доходы:
1 5 3 1
3 2 4 2
3 4 3 3 наилучшее решение
1
999 999 999 999 999 1
1.1 1.1
1.1
1.1
1.1 1.1выбираемое решение
1.1
Второй пример показывает неэффективность применения
критерия Вальда в некоторых случаях.
Критерий Байеса – Лапласа.
Обозначим через pi –
вероятность появления внешнего состояния Fj.
Правило выбора по критерию Байеса: матрица решений e
дополняется ещё одним столбцом, содержащим математическое
ожидание значений каждой из строк, выбираются те варианты, в
строках которых стоит наибольшее значение этого столбца.
ij
n
y
max
i
p j eij
j 1
По критерию Лапласа считается, что все события
равновероятны , то есть pj =1/n.
При этом предполагается, что ситуация, в которой
принимается
решение,
характеризуется
следующими
обстоятельствами: ЛПР имеет суждение о вероятности появления
состояния Fj; решение реализуется многократно; для малого числа
реализаций решения допускается некоторый риск.
Критерий
Байеса-Лапласа
(B-L-критерий)
более
оптимистичен, чем минимаксный критерий, однако он
предполагает большую информированность и достаточно
длительную реализацию.
Критерий Сэвиджа. Соответствующее критерию Сэвиджа
правило выбора теперь трактуется так:
Каждый элемент матрицы решений
вычитается из
eij
наибольшего результата max eij соответствующего столбца
Разности (max eij eij ) образуют матрицу риска (остатков) eij .
i
Эта матрица пополняется столбцом наибольших разностей eir.
Выбирают те варианты, в строках которых стоит наименьшее для
этого столбца значение.
y
min max (max eij eij )
i
j
i
Величину
(max eij
eij )
можно трактовать как максимальный
i
дополнительный выигрыш, который достигается, если в состоянии
Fj вместо варианта Ei выбирать другой, оптимальный для этого
внешнего
состояния
вариант.
Величину
(max eij eij ) можно
i
интерпретировать и как потери (штрафы) возникающие в состоянии
Fj при замене оптимального для него варианта на вариант Ei. В
последнем случае eir представляет собой максимально возможные
(по всем внешним состояниям Fj , j = 1, n ) потери в случае выбора
варианта Ei.
Требования, предъявляемые к ситуации, в которой
принимается решение, совпадают с требованиями к ММ-критерию.
1 5 3
3 2 4
3 4 3
.
Если матрица решений соответствует доходам, то матрица
сожалений равна
2 0 1 2
0 3 0 3
0 1 1 1 наилучшее решение
,
а если потерям, то то матрица сожалений
0 3 0 3
2 0 1 2 выбираемое
2 2 0 2
решение .
Для матрицы решений, соответствующей доходам
1
999 999 999 999 999
1.1 1.1
1.1
1.1
1.1
1.1
Матрица сожалений имеет вид
0.1
0
0.1 выбранное
998.9 998.9 998.9 998.9 998.9 998.9
0
0
0
0
0
решение
.
Таким образом, для рассматриваемого примера критерий
Сэвиджа дает более приемлемый результат, чем критерий Вальда.
Производные критерии. Критерий Гурвица. Стараясь занять
наиболее уравновешенную позицию, Гурвиц предположил
оценочную функцию, которая находится между точкой зрения
крайнего оптимизма и крайнего пессимизма:
max eir = C min eij + (1- C) max eij ,
i
j
j
где С– весовой множитель 0 С 1.
По критерию Гурвица: матрица решений eij дополняется
столбцом, содержащим среднее взвешенное наименьшего и
наибольшего результатов для каждой строки. Выбираются
только те варианты, в строках которых стоят наибольшие
элементы eir этого столбца.
Весовой коэффициент С определяет меру оптимизма ЛПР.
При С=1 критерий Гурвица превращается в ММ-критерий, а при
С=0 - в критерий “азартного игрока” max
eir = max
max eij , считающего
i
i
j
что всегда повезет.
Критерий Ходжа–Лемана. Является композицией ММкритерия и критерия Баеса-Лапласа. С помощью параметра
выражается степень доверия к используемому распределению
вероятностей. Если доверие велико, то доминирует критерий БаесаЛапласа, иначе – ММ-критерий, таким образом
n
eij pi + (1- ) min eir ,
0
1.
max eir = max
i
i
j
j 1
По критерию Ходжа-Лемана: матрица решений
e ij
дополняется столбцом, составленным из средних взвешенных
математических ожиданий и наименьшего результата каждой
строки. Отбираются варианты, которым соответствует
набольшее значение дополнительного столбца.
При =1 критерий Ходжа-Лемана переходит в критерий
Байеса-Лапласа, а при = 0 становится минимаксным.
Для применения критерия Ходжа-Лемана желательно, чтобы
ситуация в которой принимается решение, удовлетворяла
свойствам: вероятности появления состояния Fj неизвестны, но
некоторые предположения о распределении вероятностей
возможны;
принятое
решение
допускает
многократную
реализацию; при малой кратности реализации допускается
некоторый риск.
Критерий Гермейера. Ориентирован на величину потерь и
формулируется как:
max eir = max min eijpj.
i
i
j
В экономических приложениях преимущественно фигурируют
цены и затраты, таким образом, условие eij 0 обычно выполняется.
Когда среди величин eij встречаются положительные значения,
можно
перейти
к
строго
отрицательным
значениям
преобразованием eij - a , где a 0. При этом выбор оптимального
варианта решения зависит от а.
По критерию Гермейера: матрица решений e ij дополняется
столбцом, содержащим в каждой строке наименьшее
произведение имеющегося в ней результата на вероятность
соответствующего состояния Fj. Выбираются варианты. в
строках
которых
находится
наибольшее
значение
дополнительного столбца.
Критерий Гермейера обобщает ММ-критерий: при равной
вероятности событий pj =1/n, j =1, n , они становятся идентичными.
Критерий произведений. По критерию произведений
матрица решений e ij дополняется новым столбцом, содержащим
произведения всех результатов каждой строки. Выбираются
варианты, в строках которых находятся наибольшие значения
этого столбца.
max П eij .
i
j
Критерий применим когда: вероятности появления состояния
Fj неизвестны; с появлением каждого из состояний Fj по
отдельности необходимо считаться; критерий применим и при
малом числе реализаций решения; некоторый риск допускается.
Критерий произведений приспособлен в первую очередь для
случаев,
когда
все
eij
положительны.
Если
условие
положительности нарушается, то следует выполнять некоторый
сдвиг eij+а, где константа а> min
eij . Результат зависит от а.
ij
5. ЭВРИСТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
ВЫБОРА И ПРОЕКТИРОВАНИЯ ИНФОРМАЦИОННЫХ
СИСТЕМ И ТЕХНОЛОГИЙ
5.1. СТРУКТУРА ИНФОРМАЦИОННОЙ СИСТЕМЫ
В данном разделе рассматривается применение описанных
эвристических методов к проектированию информационных
систем. При создании информационной системы стоит задача
оптимизации
структуры
многоуровневой
компьютерной
отказоустойчивой системы в условиях многовариантности
входного потока по интенсивности запросов и по распределению
вероятностей запросов к различным группам серверов.
Известно, что высокая производительность надежность и
отказоустойчивость компьютерных систем требует избыточности
(резервирования) средств обработки, хранения и передачи данных,
в том числе коммуникационных узлов и их связей.
Достижение компромисса обеспечения требований высокой
надежности и производительности при низкой стоимости системы
сопряжено с решением задачи векторной оптимизации структуры
компьютерной системы. В результате оптимизации структуры
серверной
системы,
содержащей
N
групп
(кластеров)
резервированных
серверов
различного
функционального
назначения определяется распределение числа серверов каждого
типа, обеспечивающее при заданных параметрах потока запросов и
ограничениях на стоимость реализации системы компромисс
максимизации надежности и производительности. Оптимизация
проводится на основе аддитивного и мультипликативного
критериев, а также коэффициента сохранения эффективности, при
заданной интенсивности запросов (возможно средней). Вместе с
тем при возможных изменениях интенсивности входного потока
(что характерно для реальных компьютерных систем) структура,
оптимизированная к средней интенсивности запросов, может
привести к потерям потенциальной эффективности системы. Таким
образом, задача оптимального проектирования серверных систем
(центров обработки данных) при неопределенности входного
потока, в том числе, при многовариантности интенсивности
запросов или распределения вероятностей обращения к различным
типам серверов, представляется актуальной.
Для современных корпоративных информационных систем и
центров
обработки
данных
характерна
многоуровневая
организация, в которой можно выделить уровень рабочих станций
(клиенты), центр обработки (серверная подсистема) и уровень
хранения
данных.
Телекоммуникационная
подсистема
компьютерной системы, как правило, стоится по иерархическому
принципу с выделением уровней ядра (магистрали), распределения
и доступа.
Типовая
многоуровневая
структура
отказоустойчивой
компьютерная система (корпоративная сеть), коммуникационная
подсистема которой реализованная на основе решений Cisco,
представлена на рис. 9.1.
Рис. 9.1. Типовая многоуровневая структура компьютерной
системы.
Оптимизация структуры компьютерных систем, к которым
предъявляются
высокие
требования
по
надежности,
отказоустойчивости
и
производительности,
сопряжена
с
определением числа (кратности резервирования) компьютерных и
коммуникационных узлов на различных уровнях системы.
Проведем
векторную
оптимизацию
структуры
многоуровневой компьютерной системы в условиях вариантности
входного потока запросов по интенсивности и по распределению
вероятностей запросов к различным группам серверов. Векторная
оптимизация направлена на достижение компромисса максимума
надежности и производительности
средств на ее реализацию.
системы при ограничении
9.2. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ
В рассматриваемой многоуровневой компьютерной системе
(центр обработки данных) имеется N типов (по функциональному
назначению) серверов. Серверы каждого типа объединяются в
группы (кластеры). Входящие в состав каждой группы серверы
идентичны по параметрам. Серверы разных кластеров даже при их
реализации на однотипном оборудовании могут иметь различное
время обслуживания запросов, так как каждый кластер выделяется
на реализацию определенного приложения (задачи).
Многоуровневая структура компьютерной системы без
резервирования коммуникационных узлов (исходная структура), в
которой каждая группа серверов подключается к корневому
коммуникационному узлу (уровень ядра) через отдельный
коммуникационный узел представлена на рис. 9.2. В структуре по
рис. 9.2 выделяются уровни: коммутирующих узлов верхнего
уровня (КВУ), коммутирующих узлов нижнего уровня (КНУ) и
серверов ( компьютерные узлы). Каждый из КВУ связан с одной из
N групп компьютерных узлов.
Для узлов каждого уровня будем считать заданными средние
времена выполнения запросов, вероятности работоспособных
состояний и стоимости реализации.
Рис.9.2. Многоуровневая структура компьютерной системы
без резервирования коммуникационных узлов.
При этом:
v0i и v1i .- среднее время передачи запроса к i-му серверу
через коммутационный узел соответственно верхнего и нижнего
уровней, v2i. -среднее время выполнения запроса в сервере i-й
группы;
p0 , (p10, p11,…, p1N), (p20, p21,…, p2N) показатели надежности
КВУ, КНУ и серверов соответствующих групп;
c0 , (с10, с11,…, с1N), (с20, с21,…, с2N)– стоимости (затраты на
реализацию) КВУ, КНУ и серверов соответствующих групп.
В зависимости от вариантов формирования входного потока
выделим следующие случаи:
S1: Заданы (известны) средняя интенсивность суммарного
потока запросов и вероятности (доли) распределения запросов на
обслуживание в каждую из N групп кластеров - ( b1 , b2 , b3 ,..., bN ), где
N
bi
1
(имеется один вариант входного потока).
i 1
S2: возможны z вариантов входного потока с вероятностями
z
их возникновения a1 , a2 , a3 ,..., az ,
ai 1 Варианты отличаются
i 1
интенсивностью запросов 1 , 2 , 3 ,..., z , а доли распределения
запросов на обслуживание в N кластеров ( b1 , b2 , b3 ,..., bN ) для всех z
вариантов одинаковы.
S3: возможны z вариантов входного потока, наблюдаемых с
вероятностей a1 , a2 , a3 ,..., az , варианты различаются распределением
вероятностей (долей) (b1 , b2 , b3 ,..., bN )k при неизменности интенсивности
потока запросов .
S4: возможны z вариантов входного потока, причем их
a1 , a2 , a3 ,z . . Варианты
a. . ,
вероятности
известны и равны различаются интенсивностью запросов k (для k-го варианта) и
распределением вероятностей (долей) (b1 , b2 , b3 ,..., bN )k запросов на
обслуживание в N групп серверов.
Случай S4 является комбинацией случаев S2 и S3. Для всех
N
выделенных случаев bij 1 .
j 1
Требуется определить распределение числа узлов (кратностей
резервирования) различных типов n=(n0, n10, n11,…, n1N , n20, n21,…,
n2N ), для которого достигается компромисс по максимуму
надежности структуры и минимуму времени пребывания запросов,
при ограничении средств С0 на построение системы:
P(n)→Max; T0(n)→ Min , T1(n)→ Min,… , TN(n)→ Min для
C(n)≤С0 .
При этом n0 - кратность резервирования коммутационных
узлов верхнего уровня (КВУ), а (n10, n11,…, n1N) - кратности
резервирования коммутационных узлов нижнего уровня (КНУ),
используемых для подключения N групп серверов, кратность
резервирования в каждой из которых (n20, n21,…, n2N).
Искомая в результате оптимизации структура, представлена
на рис. 9. 3.
Рис.5. 3. Многоуровневая структура с резервированием узлов.
Задача проектирования компьютерной системы связана с
векторной оптимизацией ее структуры, при которой в качестве
частных показателей используются показатели, характеризующие
производительность (время пребывания запросов) надежность.
Стоимость реализации системы рассматривается как ограничение.
5.3. ВЕКТОРНАЯ ОПТИМИЗАЦИЯ ИНФОРМАЦИОННОЙ
СИСТЕМЫ
Оценка среднего времени пребывания запросов в системе.
При оценке среднего времени пребывания запросов в системе
будем считать, что каждый компьютерный и коммуникационный
узел исследуемой системы представим в виде одноканальной
системы массового обслуживания типа М/М/1 (СМО с бесконечной
очередью при простейшем входном потоке и экспоненциальном
распределении времени обслуживания запросов). Предположим,
что все поступающие в систему запросы поэтапно передаются
через КВУ и КНУ на обслуживание в один серверов. При заданной
интенсивности λ суммарного входного потока среднее время
пребывания в системе запросов, адресуемых к серверам i-го
группы, вычисляется как:
Ti ( , n)
vi 0
v j0 bj
N
1
j 0
v1i
v b
1 1i i
n1i
n0
v2i
.
v2i bi
1
n2i
(1)
Если время передачи через КВУ для всех запросов одинаково
и равно v0, то
v0
v
1 0
n0
Ti ( , n)
v1i
v b
1 1i i
n1i
v2i
.
v2i bi
1
n2i
При поиске оптимального решения следует учитывать условие
стационарности
процесса
обслуживания
(отсутствие
перегруженности узлов):
N
v j0 bj
j 0
v1i bi
n1i
1,
n0
v2i bi
n2i
1,
1,
ni 1,
i=0,1,…,N
(2)
Потоки запросов, адресуемые к различным группам серверов,
передаются через коммутационные узлы верхнего уровня с
дальнейшим разделением потоков в долях (b1 , b2 , b3 ,..., bN )k .
Среднее время пребывания в системе запросов, адресуемых к
разным группам серверов, вычисляется как:
N
T ( , n)
i
bi [
0
1
N
vi 0
v j0 bj
v1i
v b
1 1i i
n1i
n0
j 0
v2i
]
v2i bi
1
n2i
(3)
Оценка надежности системы. Предполагая, что для
функционирования системы достаточно исправности хотя бы
одного узла каждого типа, вероятность работоспособного
состояния системы вычисляется как:
N
Pc (n)
(1 (1 p0 ) n0 )
(1 (1 p1i ) n1i )(1 (1 p2i ) n2 i ) .
(4)
i 0
При ограничении допустимого времени ожидания запросов,
заданного
для
каждой
группы
серверов,
вероятность
работоспособности системы оценим как:
n0
Pc (n)
j
0
C p (1 p0 )
j 1
(5)
L
j
n0
n0 j
i 0
n1i
n2 i
g 1 s 1
(i, j , g , s )Cng1i p1gi (1 p1i ) n1i g Cns2 i p2s j (1 p2i ) n2 i
где
(i, j , g , s)
0,
if
T (i, j , g , s) Tl (i ),
1,
if
T (i, j , g , s) Tl (i),
предельно допустимое среднее время пребывания в
системе запросов к i-й группе серверов,
T (i, j, g , s) -среднее время пребывания в системе запросов к i-й
группе серверов при исправности j узлов КВУ и в i-й группе
работоспособности g узлов КНУ и s серверов:
Tl (i ) -
T (i, j , g , s)
vi 0
N
vi 0 bi
1
j
i 0
v1i
v b
1 1i i
g
v2i
.
v2i bi
1
s
Приведенные формулы учитывают возможность отказов узлов
разного уровня системы, а линии связи рассматриваются как
абсолютно надежные. Надежность связей при грубой нижней
оценке можно учесть, считая, что их отказы приводят к отказам
соответствующих узлов. Уточненная оценка резервированных
многоуровневых систем с учетом отказов линий связей, сетевых
адаптеров и портов коммутационных узлов рассмотрена в [5]. При
двухуровневой структуре системы расчет надежности с учетом
отказов базового оборудования резервированных коммутационных
узлов, их портов, сетевых адаптеров и связей между ними может
быть выполнен по модели, описанной в [6-7].
Комплексные показатели эффективности системы.
Эффективность
структуры
системы
с
учетом
ее
производительности (среднего времени пребывания запросов) и
надежности оценим на основе мультипликативного критерия,
который при заданном значении интенсивности входного потока λ
можно представить в виде
M ( , n)
T ( , n)
.
P ( n)
Оптимальность
(6)
структуры
мультипликативного критерия
достигается
Min
n
при
минимуме
T ( , n)
.
P ( n)
Критерий оптимальности можно сформулировать также как:
N
Min[ 1 P(n) T ( , n)]
n
или
Ti ( , n)
Min
n
i 0
P ( n)
.
Здесь P(n) определяются по формулам (4) или (5), среднее
время пребывания запросов в системе T ( , n) для случая S1
вычисляется по формуле (3).
Оптимальная структура ищется
с учетом условия
стационарности (2) и ограничения на стоимость реализации
C (n) C0 ,
N
N
(7)
C (n) c0 n0 c1
n1i
i 0
c2i n2i
i 0
В случае S2-S4, когда с вероятностями a1 , a2 , a3 ,..., az возможны
варианты формирования входного потока, эффективность
структуры определим по минимуму среднего времени пребывания
запросов
или
по
минимуму
среднего
значению
мультипликативного критерия (6) для всех возможных вариантов
формирования входного потока
z
A
ak M k ( , n),
где
M k ( , n)
k 0
T k ( , n)
P ( n)
.
(8)
Для случая S2 (при изменении варианта k меняется λ, а
( b1 , b2 , b3 ,..., bN ) не меняется):
N
T k ( , n)
i
bi [
0
1
N
j 0
vi 0
v j0 kbj
n0
v1i
v b
1 1i k i
n1i
v2i
]
v2i k bi
1
n2i
при
v1i k bi
n1i
(9)
1.
Для случая S3 (λ - не меняется, ( b1 , b2 , b3 ,..., bN ) - меняется):
N
T k ( , n)
i
bki [
0
1
N
j 0
vi 0
v j 0 bkj
n0
v1i
v b
1 1i ki
n1i
v2i
],
v2i bki
1
n2i
при
v1i bki
n1i
при
v1i k bki
n1i
1
(10)
Для случая S4 (меняется λ и ( b1 , b2 , b3 ,..., bN ) ):
N
T k ( , n)
i
bki [
0
1
N
j 0
vi 0
v j 0 k bkj
n0
v1i
v b
1 1i k ki
n1i
v2i
]
v2i k bki
1
n2i
1.
Оптимизация по математическому ожиданию среднего
значения мультипликативного критерия (8) с учетом различных
вариантов входного потока приводит при конкретном значении λ к
возможным потерям относительно оптимизации для этого значения
λ.
Пример оптимизации структуры для случая S2. Для случая
формирования входного потока S2 оптимизацию проведем, когда
имеется N=3 группы серверов, причем все коммуникационные узлы
нижнего уровня идентичны по параметрам. Будем считать
заданными следующие параметры:
p=(0,95, 0,95, 0,95, 0,95, 0,9, 0,89, 0,99); v=(0,5, 0,5, 0,5, 0,5,
5, 3, 7) с.; b=(0,33, 0,34, 0,33); c=(1, 0,5, 0,5, 0,5 , 3, 3, 9) y.e.;
С0=150 y.e.
λ=(0,1, 0,5, 1, 1,2) 1/c; a=(0,1, 0,2, 0,3, 0,4).
При решении оптимизационной задачи (с использованием
пакета математических расчетов Mathcad) установлено, что
минимум
математического
ожидания
мультипликативного
критерия (8) ( T k ( , n) вычисляется по (9) при ограничениях (2), (7))
достигается при распределении числа различных узлов, задаваемым
вектором n=(5, 3, 3, 3, 11, 7, 10) шт.
Таким образом, оптимальная структура компьютерной
системы при ограничении средств на ее реализацию С0≤150 y.e включает 5 коммутационных узлов верхнего уровня, три группы
КНУ по 3 узла в каждой, и соответственно три группы серверов по
11, 7 и 10 узлов в каждой.
Зависимость среднего времени пребывания запросов T k ( , n)
(9) от интенсивности входного потока λ при оптимальном
распределении числа узлов n=(5, 3, 3, 3, 11, 7, 10) шт. представлена
на рис 9.4 кривой 1. Кривые 2-4 на рис 9.4 соответствуют
зависимости среднего времени пребывания запросов к первой
второй и третьей группам серверов.
Рис.5.4. Среднее время пребывания запросов T k ( , n) ко всем
группам серверов, а также к первой второй и третьей группам
серверов.
Оптимизация структуры по минимуму математического
ожидания мультипликативного критерия (8) с учетом всех z
вариантов входного потока приводит к возможным потерям
эффективности (по мультипликативному критерию) относительно
структур, оптимизируемых по минимуму (6) для конкретной
интенсивности запросов λ (указанные потери ожидаемы в области
близких значений к интенсивности λ, при которой проведена
оптимизация).
На рис. 9.5 представлена зависимость от интенсивности
входного потока λ разницы D( , k , n) M k ( , nk ) M ( , n) , между
мультипликативным критерием M ( , n) структуры, число узлов
которой n найдено по критерию минимум среднего
мультипликативного
критерия
(8)
для
всех
вариантов
интенсивностей входного потока (λ=0,1, 0,5, 1, 1,2) 1/с и
мультипликативным критерия M k ( , nk ) структуры при числе узлов
nk , найденном по критерию минимум мультипликативного
критерия (7) для λ=λ. На рис. 9.5 кривые 1-3 представляют
зависимость D( , k , n) при числе узлов nk найденном в результате
оптимизации по критерию (7) при λk=1,2; 1; 0,5; 1/с (k=2,3,4), а
кривая 4 зависимость 0,1 D( , k , n) в случае оптимизации структуры
при λ=0,1 1/с (k=1).
Из представленных зависимостей видна эффективность
оптимизации по математическому ожиданию мультипликативного
критерия (8) с учетом многовариантности интенсивности входного
потока.
Рис. 5. 5. Сравнение по мультипликативному критерию
оптимизации структуры с учетом всех вариантов интенсивности
входного потока и одного из них.
Оптимизация по минимуму математического ожидания
мультипликативного критерия (8) с учетом всех вариантов
входного потока может приводить к возможным потерям
относительно
значений
мультипликативного
критерия,
достигаемых при адаптивной оптимизации для каждого
возможного значения λ. При адаптивной оптимизации изменения
потока приводит к реконфигурации структуры в реальном времени.
Оценим эти потери в зависимости от интенсивности входного
потока λ величиной d ( , n) M ( , n( )) M ( , n) , причем M ( , n) значение
мультипликативного критерия при оптимальном числе узлов,
найденном по минимуму среднего мультипликативного критерия
z
A
ak
k 0
T ( , n)
P ( n)
с учетом всех вариантов интенсивностей входного
потока (λ=(0,1;
0,5;
1;
1,2) 1/с), а M ( , n( )) значение
мультипликативного критерия (6) при определении оптимального
числа узлов для каждого (текущего) значения интенсивности
запросов. Таким образом, оцениваются потери эффективности при
априорной оптимизации структуры с учетом возможных вариантов
входного
потока
относительно
адаптивной
оптимизации
конфигурации для каждого значения λ (при изменении
интенсивности запросов происходит перестройка структуры в
реальном времени). Расчеты позволяют оценить потенциально
возможные потери от оптимизации структуры «в среднем» для всех
вариантов входного потока, относительно адаптации структуры к
изменению входного потока. При этом реализуемость, сложность и
возможные издержки при адаптивной оптимизации структуры
здесь не обсуждаются. Зависимость d(λ,n) представлена на рис. 9.6
кривой 1.
Оптимизация
структуры
по
критерию
минимум
математического ожидания мультипликативного критерия (8) с
учетом всех вариантов входного потока приводит к возможному
увеличению времени пребывания запросов относительно значений
достигаемых при адаптивной оптимизации структуры для каждого
возможного значения λ.
Оценим эти издержки в зависимости от возможной
интенсивности входного потока λ для запросов к первой, второй и
третьей группам серверов величинами:
t1 ( , n) T1 ( , n( )) T1 ( , n) ,
t2 ( , n) T2 ( , n( )) T2 ( , n) , t3 ( , n) T3 ( , n( )) T3 ( , n) ,
где T1 ( , n( )) , T2 ( , n( )) , T3 ( , n( )) - средние времена пребывания
запросов к серверам первой, второй и третьей групп. Значения
T1 ( , n( )) , T2 ( , n( )) , T3 ( , n( )) вычисляются по (1) при распределении
числа узлов n( ) , найденном в результате адаптивной оптимизации
по минимуму мультипликативного критерия для каждого значения
λ.
T1 ( , n) , T2 ( , n) , T3 ( , n)
средние
времена
пребывания
соответствующих
запросов
(вычисляемые
по
(1))
при
распределении числа узлов n, получаемом в случае оптимизации
структуры по минимуму критерия A
z
ak
k 0
T ( , n)
P ( n)
с учетом всех
вариантов интенсивностей входного потока (λ=0,1, 0,5, 1, 1,2) 1/с.
На рис.9.6 кривые 2-4 представляют зависимости 10t1(λ,n),
t2(λ,n), t3(λ,n)
потенциальных издержек среднего времени
пребывания запросов к серверам первой, второй и третьей групп
при оптимизации структуры по минимуму среднего значения
мультипликативного критерия (8), относительно адаптивной
оптимизации структуры к изменениям загрузки.
Рис. 9.6. Сравнение по среднему времени пребывания
запросов оптимизации структуры по минимуму среднего
мультипликативного критерия и адаптивной оптимизации
структуры к изменениям загрузки.
Представленные зависимости позволяют сделать вывод об
эффективности оптимизации с учетом всех возможных вариантов
входного потока и о потенциальной эффективности адаптивной
оптимизации. Вместе с тем, потенциальные возможности
адаптивной оптимизации структуры не всегда реализуемы из-за не
возможности переключения узлов к различным группам при
каждом кратковременном изменении потока. Помимо этого
адаптивная оптимизация требуют дополнительных аппаратных,
временных, и стоимостных издержек на ее реализацию (например,
на организацию системы мониторинга текущей загрузки для всех
типов запросов), которые могут свести на нет положительный
эффект от адаптации.
Пример оптимизации структуры для случая S3. Рассмотрим
случай S3, при котором возможны z вариантов входного потока
(k=0,2,…z), различающиеся (при постоянстве интенсивности λ=1)
вероятностями распределения запросов к N=3 группам серверов,
заданными матрицей b
kj
N
z
0,1 0,1 0, 7
0,3 0,1 0,5
0,5 0,1 0,3
,
(11)
0, 7 0,1 0,1
Вероятности вариантов входного потока заданы вектором
a=(0,3, 0,2, 0,2, 0,3), k-й элемент которого соответствует
вероятности k-го варианта входного потока (для k- го варианта
распределения запросов к различным группам серверов
представлены k-й строкой матрицы (11)).
Таблица 9.1
Результаты оптимизации структуры компьютерной системы
Типы узлов
Целевая функция
z
различных
T k ( , n)
T k ( , n)
T k ( , n)
Tk(
T
ak T k ( , n)
уровней
k 0
При
При
При
При
структуры
При k=0,1.2,3 k=0
k=1
k=2
k=3
3
3
4
5
6
Число КВУ
(шт)
, n)
Число КНУ
первой
группы
(шт)
Число КНУ
второй
группы
(шт)
Число КНУ
третьей
группы
(шт)
Число
серверов первой
группы (шт)
Число
серверов второй
группы (шт)
Число
серверов третьей
группы (шт)
2
1
2
3
6
1
1
1
1
1
2
3
3
3
2
10
5
7
14
25
3
3
1
2
2
12
13
13
10
6
Будем считать, что: v=(0,5; 0,5; 0,5; 0,5; 5, 3, 7) с.; c=(1; 0,5;
0,5; 0,5; 3; 3; 9) y.e.; С0≤150 y.e.
Оптимизация структуры проводится по минимуму среднего
z
времени пребывания запросов в системе, T
ak T k ( , n) , ( T k ( , n)
k 0
вычисляется по (10)) с учетом ограничений (2),(7).
Распределение числа различных типов узлов n=(n0, n10, n11,…,
n1N, n20, n21,…, n2N ), найденное при минимизации среднего времени
z
пребывания запросов T
ak T k ( , n) дано в таб . 9.1.
k 0
В таб . 9.1 также представлено распределение числа узлов
различного типа, найденное при минимизации среднего времени
пребывания запросов T k ( , n) для каждого (k-го) варианта
распределения входного потока. Все варианты структуры
определены при стоимости ее реализации (7) не более 150 y.e.
Зависимость среднего времени пребывания запросов в системе
от варианта k=0,1,…,z распределения вероятностей адресации
запросов (доли запросов) к различным группам серверов (k-й
вариант соответствует k-й строке матрицы (11)) представлена на
рис. 9.7. На рис. 9.7 по оси абсцисс даны значения доли запросов
распределяемых в первую группу серверов (для рассматриваемого
примера доля запросов распределяемых во вторую группу серверов
постоянна
а в третью группу
определяется как
bk 3 1 0,1 bk1 ). Кривая 1 соответствует зависимости T(k,n) при
распределении числа узлов n=(n0, n10, n11,…, n1N , n20, n21,…, n2N ),
z
найденном при минимизации выражения T
ak T k ( , n) . Кривые 2-5
bk 2
0,1 ,
k 0
представляют зависимости средних времен пребывания запросов
при числе узлов n, найденном в результате минимизации целевой
функции (10) при k-м варианте входного потока ( представляемого
k-й строкой матрицы (11)). На рис. 9.7 кривым 1-4 соответствует
левая, а кривой 5 - правая ось ординат.
Представленные
зависимости
подтверждают
целесообразность оптимизации структуры с учетом всех
возможных вариантов входного потока.
Таким образом, поставлена и решена задача векторной
оптимизации структуры многоуровневой компьютерной системы в
условиях многовариантности входного потока по интенсивности
запросов и по распределению вероятностей запросов к различным
группам резервированных серверов, доступ к которым
осуществляется через коммуникационную подсеть, имеющей
структура типа “дерево” с резервированием коммуникационных
узлов двух уровней.
В результате оптимизации определяется распределение числа
коммуникационных и серверных узлов каждой группы,
обеспечивающее при заданных ограничениях на стоимость
реализации системы компромисс требований наибольшей
надежности и наименьшего времени ожидания запросов. Показана
эффективность проектирования и многоуровневых компьютерных
систем с применением предлагаемой векторной оптимизации.
Рис.5.7. Зависимость среднего времени пребывания запросов в
системе от распределения вероятностей адресации к различным
группам серверов.
Проведенных исследований могут использоваться при
обосновании (выборе) вариантов построения отказоустойчивых
структурно - резервированных компьютерных систем.
Литература
1. Алиев Т.И. Основы моделирования дискретных систем. СПб: –
СПбГУ ИТМО, 2009. — 363 с
2. Клейнрок Л. Вычислительные системы с очередями. М.: Мир,
1979.
3. Клейнрок
Л.
Теория
массового
обслуживания.
М.:
Машиностроение, 1979.
4. Компьютерные сети. / Э. Таненбаум .-3-е изд., перераб. и доп. СПб.: Питер, 2011.
5. Гуров С.В, Половко А.М. Основы теории надежности. Питер
2006
6. Черкесов Г.Н. Надежность аппаратно-программных комплексов.
Питер. 2005.
7. Ушаков И.А. Курс теории надежности систем. М:-Дрофа , 2008.
239 с.
8. Острейковский В.А. Теория надежности . М., Высшая
школа.2003.
9. Гнеденко В.В., Беляев Ю.К., Соловьев А.А., Математические
методы в теории надежности. –М.: Наука, 1965
10. Дианов В.Н. Диагностика и надежность автоматических
систем. М., МГИУ 2004.
11. Шубинский И.Б. Активная защита от отказов управляющих
модульных вычислительных систем. СПб . Наука, 1993.
12. Иыуду К.А. Надежность контроль и диагностика
вычислительных машин и систем. Высшая школа.1989.
13. Надежность автоматизированных систем управления: Учебное
пособие для ВУЗов / под ред. Хетагурова Я.А. - М.: Высшая
школа, 1979г.
14. Дружинин Г.В. Надежность автоматизированных систем. - М.:
Энергоатомиздат, 1986. - 564 с.
15. Коваленко И.Н. Методы расчета высоконадежных систем. М.,
Радио и связь .1988.
16. Богатырев В.А., Богатырев С.В. Объединение резервированных
серверов в кластеры высоконадежной компьютерной системы //
Информационные технологии. - 2009. - № 6. - С. 41-47.
17. Богатырев В.А., Богатырев С.В. К анализу и
оптимизации серверных систем кластерной архитектуры с
балансировкой нагрузки //Приборы и системы. Управление,
контроль, диагностика. - 2010. - № 2. - С. 4-9.
18. Томашевский
В.,
Жданова
E.
Имитационное
моделирование в среде GPSS. Бестселлер 2003- 416с.19. Энциклопедический словарь справочник
/http://doc.unicor.ru/tt/217.html
20. Эвристические методы / http://msk.treko.ru/
21. Джонс Дж., Методы проектирования, М., «Мир», 1986.
22. Кудрявцев А. В. Обзор методов создания новых технических
решений /http://www.metodolog.ru
23. Кудрявцев А. В.Методы интуитивного поиска технических
решений /http://www.metodolog.ru/0068
24. Андрейчиков А.В. Андрейчикова О.Н. Анализ, синтез ,
планирование решений в экономике. М. Финансы и статистика,
2000
25. Основные понятия ТРИЗ, АРИЗ.
http://www.metodolog.ru/editornotes.
26. Альтшуллер Г. С. Алгоритм изобретения. М.: Московский
рабочий, 1973.
27. Альтшуллер Г. С. Творчество как точная наука. М.: Советское
радио, 1979.
28. Методы поиска идей http://www.inventech.ru/pub/
29. Теоpeтические основы сиcтeмногo анализа / Новосельцев
В.И.др.] ; под ред. В. И. Новосельцева. М. : Майор, 2006. 592 с
30. Захаров А.. Универсальная Схема Эволюции
/http://www.metodolog.ru
31. Самсонова М.В. Технология и методы коллективного решения
проблем //http|www.inventech/ru
32. Титов В.В. Системно-морфологический подход в технике,
науке, социальной сфере. http://www.serendip.boom.ru
33. Акимов С.В. Введение в морфологические методы и
моделирование знаний предметной области
http://structuralist.narod.ru/articles/articles.htm
34. Норенков И.П. Основы автоматизированного проектирования.
— М.: МГТУ им. Н.Э.Баумана, 2002.
35. Джонс Дж. К., Методы проектирования, М., «Мир», 1986
36. А.Н. Божко, А.Ч. Толпаров Структурный синтез на элементах с
ограниченной сочетаемостью
http://www.techno.edu.ru:16001/db/msg/13845.html
37. Кузьмина Е.А., КузьминА.М. Функционально-стоимостный
анализ и метод АВС "Методы менеджмента качества" № 12
2002.
38. Кузьмина Е.А., Кузьмин А.М. Функционально-стоимостный
анализ. Экскурс в историю. Методы менеджмента качества. 2002. - № 7. - С. 14-20.
39. Кузьмина Е.А., Кузьмин А.М. Функционально-стоимостный
анализ. Концепции и перспективы. Методы менеджмента
качества. - 2002. - № 8. - С. 8-14
40. Функционально-стоимостный анализ ФСА
http://inventech.ru/lib/
41. Основные положения методики проведения функциональностоимостного анализа: Методические рекомендации. РГАСНТИ
45.01.75 — М.: Информ— ФСА, 1991. —40 с.
42. Ивлев В., Попова Т. Методология функциональностоимостного анализа ABC (ФСА),//www.citforum.btsau.net.ua
43. Применение методов технического творчества при проведении
ФСА: Методические рекомендации. М.: Информэлектро, 1990
44. Управление качеством. Учебник / С. Д. Ильенкова, Н. Д.
Ильенкова, С. Ю. Ягудин и др.; Под ред. Доктора
экономических наук, профессора Ильенковой С. Д. М.: ЮНИТИ
http://www.iso.staratel.com/index.php
45. Перегудова Ф.И., Тарасенко Ф.П. "Основы системного анализа"
Томск: Изд-во НТЛ, 2001
46. Фомин В.Н. Квалиметрия. Управление качеством.
Сертификация: Учебное пособи М. Ось-89 , 2007
47. Половинкин А.И. Основы инженерного творчества М
Машиностроение , 1988 -368 с.
48. Теории и методы принятия решений: учебник для вузов. / О.И.
Ларичев .- М. : Логос, 2003.
49. Основы системного анализа и теории принятия решений /Ф.Г.
Коломоец.- Минск: Тесей, 2006.
50. Введение в исследование операций. /Х.А Таха -М.: Вильямс,
2006.
51. Методы принятия решений : учебник для вузов.
/И.Г
Черноруцкий. - СПб.: БХВ , 2005.
52. Исследование операций: учебник для вузов. /И.К. Волков.- М.:
МГТУ Им. Баумана Н.Э., 2002.
53.
1/--страниц
Пожаловаться на содержимое документа