Задача оптимального резервирования

Для повышения надёжности сложных систем часто используется резервирование элементов (узлов), то есть в случае отказа одного элемента, используется его резервная копия (дубликат). Если считать отказы каждого элемента и их дубликатов независимыми случайными событиями и обозначить через pi- вероятность отказа i-ro элемента, то для двух экземпляров такого элемента - вероятность отказа при дублировании равна рЛ Соответственно вероятность отказа при наличии Xi экземпляров равна р.*’ . А вероятность сохранения работоспособности элемента равна 1 - р.*;

Соответственно для системы из N элементов вероятность сохранения работоспособности Р(х), которую можно считать мерой надёжности, вычисляется по формуле

Резервирование требует затрат, поэтому могут быть ограничены суммарные затраты, суммарный вес, объём или какая-либо ещё характеристика набора элементов или несколько таких характеристик. Соответственно имеем ограничение

или несколько ограничений такого вида. Заданные величины ai >0 - это стоимость, соответственно вес или объём одного экземпляра i-ro элемента (узла). Необходимо выбрать такое резервирование для каждого элемента, то есть такой вектор x(xi,X2,...,xn), чтобы выполнялось ограничение (5.8) и была максимальная надёжность Р(х) или минимальная вероятность отказа системы, т.е. 1 -Р(х). Поскольку переменные Xi принимают целочисленные значения, задача может быть решена по методу динамического программирования. Очередной шаг- это очередной элемент (узел), состояние- это уже использованный ресурс и т.д. по аналогии с использованием транспортных средств (разд. 4.2). Наличие в целевой функции произведения вместо суммы существенного значения не имеет как при отбраковке путей, приводящих в одно и то же состояние, так и при отбраковке непаретовских точек.

В [1] рекомендовано решать задачу на минимум вероятности отказа системы по алгоритму Р. Веллмана. Однако данная задача может быть решена и с использованием множеств Парето и с отбраковкой части паретовских точек по методу ветвей и границ. С этой целью будем решать задачу на максимум вероятности сохранения работоспособности системы и вместо целевой функции Р(х) (5.7) рассмотрим её логарифм In Р(х). Такая замена даёт ту же точку максимума из-за монотонности функции логарифм. Однако она позволяет перейти от произведения к сумме и преобразовать задачу к уже решённой задаче распределения ресурса (5.1, 5.2). Действительно

Далее вместо задачи на максимум In Р(х) будем рассматривать задачу на минимум функции минус In Р(х) при ограничении (5.8) и получаем задачу(5.1, 5.2), в которой

Максимальные значения переменных Xi определяются перебором в процессе счёта из условия 5.8.

По смыслу задачи значения переменных Xi обычно не превышают 3, что однако не делает бессмысленным разработку быстродействующих алгоритмов решения задачи, так как к этой же модели могут сводиться другие задачи, в которых эти значения могут быть существенно больше. Кроме того, как уже отмечалось, возможно наличие нескольких ограничений вида 5.8. В этом случае, как показано в [1], задача сводится к многократному решению задачи с одним ограничением.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >