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

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

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