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

Эти методы являются наиболее точными методами оптимального резервирования. Метод прямого перебора, который сводится к перебору всех возможных решений, является громоздким и редко применяется при проектировании систем. Метод динамического программирования является модификацией метода прямого перебора (алгоритм Кеттеля) [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

Доминирующая последовательность строится следующим образом: для прямой задачи из таблицы находится наименьшее значение 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

Первый член доминирующей последовательности для композиции блоков 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

Таким образом в клетках 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