11.4. Алгоритмы оптимального резервирования

При решении задач оптимального резервирования используются различные методы оптимизации. Рассмотрим некоторые из этих методов.

Градиентный метод.

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

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

Функция надёжности системы на N-ом шаге процесса: .

Затраты на обеспечение этой надёжности: , где - вектор состава резервных элементов наN-ом шаге.

В соответствии с описанной процедурой на следующем “N+1”-ом шаге процесса отыскивается максимальное значение из всех рассчитываемых по формуле (11.3) для каждой подсистемы.

(11.3), где , и далее .

Тогда , где . Отсюда видно, что содержание процесса движения к экстремуму не изменится, если на “N+1”-ом шаге мы будем двигаться в направлении . Таким образом, рассчитав для каждого участка значение можно определить в какой последовательности следует добавлять резервные элементы, чтобы остановившись на любом произвольном шаге процесса мы имели бы систему, резерв которой оптимален в рассматриваемом смысле.

Для высоконадёжных систем и близки к единице, поэтому можно записать приближенное выражение:

Процесс прекращается на таком шаге N, когда для прямой задачи . Для обратной задачи: .

Градиентный метод не даёт строгого оптимального решения, т.е. перебор ведётся в ограниченной области возможных решений. Из любой точки процесса решения, характеризуемой некоторым вектором состава системы X^(N)можно прийти только в такую точку “N+1”, чтобы выполнилось условиеX^(N+1)>X^(N). Иначе говоря, после каждого шага в системе обязательно добавляется резервный элемент. Перекомпоновка резерва между подсистемами не допускается. Метод может быть рекомендован на этапах предварительного проектирования надёжных систем.

Пример решения задачи оптимального резервирования градиентным методом рассмотрен в [20,21].

Методы прямого перебора и динамического программирования

Эти методы являются наиболее точными методами оптимального резервирования. Метод прямого перебора, который сводится к перебору всех возможных решений, является громоздким и редко применяется при проектировании систем. Метод динамического программирования является модификацией метода прямого перебора (алгоритм Кеттеля) [20]. Применительно к задаче оптимального резервирования он сводится к отысканию доминирующей последовательности решений, т.е. последовательности векторов состава системы, включающие все множество оптимальных решений. Будем считать, что один состав системы, представляющий собой некоторую комбинацию расположения резервных элементов, доминирует над другим, если имя одного и того же уровня надёжности обеспечение этого состава связано с наименьшими затратами. Члены доминирующей последовательности обладают тем свойством, что если вектор состава системы X^(K)член доминирующей последовательности с показателями надёжностиP_Kи затратамиC_K, то невозможно найти такой вектор составаX^(l), чтобы имели место оба неравенстваP_l>P_K; C_lC_K. Все неоптимальные решения, не входящие в состав доминирующей последовательности в силу того, что они обладают большей величиной затрат при тех же затратах, чем члены доминирующей последовательности, просто исключаются из рассмотрения. Задача состоит в построении доминирующей последовательности для всей системы, состоящей из “n” подсистем. Для этого берутся две произвольные подсистемы(n-1)-ую и “n”-ую, для которых строится доминирующая последовательность. После построения доминирующей последовательности для “n-1”-ой и “n”-ой подсистемы вся система сводится к системе из 1, 2, …,n-2,(n-1)* подсистем, где(n-1)* - некая условная подсистема, получающаяся в результате композиции подсистем “n” и(n-1).Систематически применяя подобную процедуру, мы через “n” этапов сведём нашу систему, состоящую из “n” подсистем к одной условной подсистеме 1*, для которой будет известна доминирующая последовательность. Требуемый вектор состава резервных элементовX₀выбирается из доминирующей последовательности, исходя из заданных ограничений, т.е. при решении первой задачи оптимального резервирования выбирается такой векторX₀при которомP(X₀)≥P₀, а при решении второй – такой, при которомC(X₀)C₀.

Для построения доминирующей последовательности для “n-1”-ой и “n”-ой подсистем составляется таблица. Размер таблицы определяется по заданным значениям надёжности или затрат. В таблице:x_n-1иx_nчисло резервных элементов в “n-1”-ой и “n”-ой подсистемах;P(x_n-1,x_n), С(x_n-1,x_n) – показатели надёжности и “стоимости” последовательно соединённых на логической схеме “n-1”-ой и “n”-ой системах соответственно приx_n-1иx_nрезервных элементах.

Таблица №11.1

xn	xn-1
	0	1	2	…
0	P(0,0); С(0,0)	P(1,0); С(1,0)	P(2,0); С(2,0)
1	P(0,1); С(0,1)	P(1,1); С(1,1)	P(2,1); С(2,1)
2	P(0,2); С(0,2)	P(1,2); С(1,2)	P(2,2); С(2,2)
…

Доминирующая последовательность строится следующим образом: для прямой задачи из таблицы находится наименьшее значение P₁ >P₀ (P₀ – задано). Если это значение может быть получена с помощью нескольких вариантов, то выбирается вариант с наименьшими затратамиC₁, а остальные исключаются из рассмотрения. Полученный вектор состава системы с показателямиP₁иC₁будет первым членом доминирующей последовательности. Далее из таблицы находится следующий по величине показатель надёжностиP₂>P₁ и аналогично определяется второй член доминирующей последовательности и т.д. Для обратной задачи члены доминирующей последовательности определяются показателю “стоимости”.

Проиллюстрируем алгоритм Кеттеля на примере.

Пример №1.

Передающее устройство состоит из 3х блоков (1, 2, 3). Вероятности отказов блоков за наработку [0, t_i] равныQ₁(t_i)=0,1;Q₂(t_i)=0,02; Q₃(t_i)=0,01, а величина затрат на каждый блок: С₁=3; C₂=2; Q₂=1.Определить оптимальный состав устройства, который может быть получен путём нагруженного резерва при условии, что величина отказа устройства за наработку (0,t_i)Q(t_i) Q₀(t_i)=0.03 при минимальных затратах.

Решение.

Рассмотрим композицию блока 1 и блока 2 и построим для них доминирующую последовательность. В клетках 1, 2, 3 (номера клеток в таблице N2) записываются значения вероятности отказа за наработку (0,t_i) – величиныQ₁(x₁) и значения затратС₁(x₁) для блока 1 в зависимости от числа резервных элементовx₁. В клетках 4, 5, 6 записываются те же значения для блока 2. Эти значения определяются следующим образом:

1, 2;j=1, 2;

Максимальное число резервных элементов взято равным двум. В случае необходимости размер таблицы может быть увеличен. В клетках 7-15 записаны значения вероятностей отказа за наработку (0, t_i) и затрат для последовательного соединения блоков 1 и 2 с различным числом резервных элементов, подключенных к каждому из них:

Таблица №11.2

			Число x1 резервных элементов к блоку 1
			0	1	2
			С1=3; Q1=0.1	С2=6; Q2=0.01	С3=9; Q3=0.001
Число x2резервных элементов к блоку 2	0	С4=2; Q4=0.02	С7=5; Q7=0.12	С8=8; Q8=0.03	С9=11; Q9=0.021
	1	С5=4; Q5=0.0004	С10=7; Q10=0.1	С11=10; Q11=0.01	С12=13; Q12=0.0014
	2	С6=6; Q6=0.000008	С13=9; Q13=0.1	С14=12; Q14=0.01	С15=15; Q15=0.001

Первый член доминирующей последовательности для композиции блоков 1 и 2 находится в клетке 8 таблицы №2. ему соответствует максимально допустимое значение вероятности отказа, равное Q₀(t_i)=0,03. Векторы состава устройства, расположенные в клетках 7, 10, 13 имеют значение вероятности отказа больше чемQ₀(t_i). Второй член – в клетке 11: он обладает следующим меньшим значением . Векторы состава устройства, расположенные в клетках 9 и 14, исключаются из рассмотрения, так как они имеют такое же и большее значение , чем у второго члена при больших затратах. Третий член доминирующий последовательности расположен в клетке 12, а четвёртый – в клетке 12. Остальные члены исключаются, т.к. имеют ненадёжность большую, чем заданнаяQ₀(t_i).

Далее строится таблица №3, в которую заносятся значения полученной доминирующей последовательности (клетки 1, 2, 3, 4) и значения Q₃(x₃) и С₃(x₃), полученные аналогично предыдущему для блока 3.

Таблица №11.3

			Число x1 и x2 резервных элементов, подключенные к блокам 1 и 2
			x1= 1 x2 =0	x1= 1 x2 =1	x1= 2 x2 =1	x1= 2 x2 =2
			С1=8; Q1=0.03	С2=10; Q2=0.01	С3=13; Q3=0.0014	С4=15; Q4=0.001
Число x3резервных элементов, подключённых к блоку 3	0	С5=1; Q5=0.01	С8=9; Q8=0.04	С9=11; Q9=0.02	С10=14; Q10=0.011	С11=16; Q11=0.011
	1	С6=2; Q6=0.0001	С12=10; Q12=0.03	С2=12; Q2=0.01	С14=15; Q14=0.0015	С15=17; Q15=0.0011
	2	С7=3; Q7=0.000001	С16=11; Q16=0.03	С2=13; Q2=0.01	С16=16; Q16=0.0014	С19=18; Q19=0.001

Таким образом в клетках 8-19 записаны вероятности отказов за время (0, t_i) устройства и затрат при различном числе резервных элементов, подключённых к каждому из основных. Просматривая все значения , приведённые в таблицеN3, находим требуемый вектор состава системы, который имеет и минимальное значение затрат. Этот вектор состава находится в клетке 12 – в ней приведены значения и С=10. При этом к блокам 1 и 3 подключается по одному резервному элементу.

Вектор оптимального состава:

x₁=1;x₂=0;x₃=1, при этомQ=0,03, С=10=min.

Логическая схема устройства, обеспечивающая при С=10=minпредставлена на рис 11.2

Рис. 11.5