Программные продукты и системы

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

Блок системы, исходная надежность которого р°, может быть неоднократно дублирован разнотипными элементами из и их типов. Элемент ^-го типа (J = \;n), имеющий надежность рр характеризуется совокупностью т параметров, заданных вектором

цена , atj - вес , ац - габарит j-vo элемента и т.д.).

Требуется из л типов выбрать такой состав элементов, который при их параллельном подсоединении обеспечит максимальную надежность блока. Максимально допустимые значения ограничивающих факторов известны ( Ь, -бюджет, Ь2 - вес, и т.д.).

Формальная постановка задачи состоит в максимизации функции надежности блока р(х), путем выбора состава средств (вектора х = (х \ ), не приводящего, однако, к

нарушению ограничений по указанным факторам:

p(x) = l-q' I \q' -> max,                v1'

_             ij, i = \;m,                                   (2)

Xje{OX...}, j = UH,                                  (3)

где qj —1-pj-ненадежность у-го элемента; х, -количество дублирующих элементову-го типа.

МЕТОД И АЛГОРИТМ РЕШЕНИЯ

Максимизация функции (1) эквивалентна минимизации функции ненадежности:

q(x)-q T\ QJ ~ ^xp\-\lnq - у хМпа,\\ = р~^х/ —> min ^ ' )=1 '             [ '           )-

Вводя обозначения

j = i;n, (5)

целевую функцию (1) сведем к линейной форме

L{x) =

Таким образом, исходная задача сведена к задаче целочисленного линейного программирования (ЗЛП) (6), (2), (3), где целевая функция L(x) - это модуль показателя степени экспоненциальной функции ненадежности блока (4).

Целочисленное решение может быть получено известными методами [4,5] путем последовательного введения дополнительных ограничений (правильных отсечений) в конечную симплексную таблицу (с-таблицу) нецелочисленной ЗЛП (6), (2). Для иллюстрации решения будем использовать следующую версию симплексного алгоритма решения ЗЛП (6), (2), в которой для удобства последующих записей обозначено Vi,j: -ад^а^-

Алгоритм

2°. Привести ограничения (2) к каноническому виду и записать ЗЛП в виде начальной с-таблицыТ1:

,(7)

где S,- дополнительные неотрицательные переменные (невязка).

3°. Есть ли строка / = к, где Ък > 0 ? - иначе идти к 8° (опорный план получен).

4°. Есть ли в строке ; = к элемент а^ > 0 ? -иначе идти к 14° (задача несовместна).

5°. Столбец j = s разрешающий.

6°. Выбор разрешающей строки / = г (р-строки) из условия:

nun

7°. Шаг обыкновенного жорданова исключения (ОЖИ) - замена er<->xs.

Пересчет элементов Т1 по формулам:

4 ~ ZT'

Идти к 2°.

8°. Если тахс =с < 0, идтик 13°.

9°. Столбец j = s разрешающий.

10°. Если Vi: au £ 0 -идтик 14° (задача неограниченна).

11°. Выбор р-строки / = г из условия (8).

12°. Шаг ОЖИ (пересчет по формулам (9)), идти к 8°.

13°. Записать решение х° = (х°), р(х") (см.

14°. Конец.

При формировании правильного отсечения для /-и порождающей строки полученной конечной с-таблицы используется формула:

где (а) = а - [а] - дробная часть числа а; [а] -целая.

После ввода ограничения в конечную с-таблицу находится новое решение ЗЛП. Последовательный ввод таких ограничений прекращается после получения решения в целых числах.

ПРИМЕР ВЫЧИСЛЕНИЙ

В таблице представлены учитываемые параметры резервирующих элементов четырех типов.

Таблица

В знаменателях дробей записан коэффициент качества элемента j-ro типа по /-му виду

параметра а»: К =-£-^-- Коэффициент Kg

определяет собой надежность блока, если весь ресурс /-го вида потратить на элементы j-ro типа и при этом другие ограничения не учитывать. Действительно:

 — —

atj

 Ing/

-7-fV**.

(П)

Учитьшая (5), ЗЛП (6), (2) для исходных данных, приведенных в таблице, в каноническом виде запишется:

е1 = - X] - 2x2 ~ 4х$ - 6х4 +14,

Е2 = ~4Xj - ЗХ2 ~ ?Х3 ~ $Х4 + 14,

£3 - ~Х1 ~ 2^2 - 4хз - 8х4 +14, L = 102Цх) = 10xj + 23х2 + 40х3 + 70х4 -> max .

После двух шагов ОЖИ (е3 ++ х3, е2 <-> х2) получено решение *°=(0;7/2;7/4;0), записанное в конечной с-таблице ТЗ:

(13)

Выбирая в качестве порождающей строку /=2, согласно (10) получим правильное отсечение Zi, которое записано в нижней строке ТЗ.

После замены Zj <-> е2 получим решение в целых числах х° = (0,3,2,0) (Т4).

Примечание. Для удобства вычислений коэффициенты Cj (5) умножены на 102и округлены в ближайшую сторону. Такое округление слабо влияет ни структуру оптимального решения, однако может внести существенную погрешность в L(x), поэтому надежность р(х°) следует вычислять по исходной формуле (1) для полученного решения х°, тогда: р(х°) = 1 - 0,б3-0,4* = 0,966.

Решение данной задачи вырожденное

(й=0). В общем случае число значащих переменных X] равно рангу матрицы (r=miir{ n;m \). В случае целочисленности переменных дд оно может быть и большим.

В заключение отметим, что решение целочисленной ЗЛП (12), которое было бы получено методом нормированных функций [2,3], привело бы к тому же решению. Это важно в том плане, что дальнейшее усложнение исходной задачи на случай резервирования нескольких последовательных звеньев системы разнотипными элементами и при наличии многих ограничивающих факторов сделает невозможным сведение решения к ЗЛП. В то же время, метод нормированных функций может позволить сформулировать достаточно эффективную процедуру решений столь общей задачи оптимального резервирования.

Список литературы

1-Барлоу Р., Прошан Ф. Математическая теория надежности. - М.: Сов.радио, 1969.- 485с.

2. Берзин Б.А. Оптимальное распределение ресурсов и элементы синтеза систем. - М.: Сов.Радио.- 303 с.

3. Берзин Е.А., Палюх Б.В. Оптимизация надежности АСУ Методом нормированных Функций. (Ст.СНТ.) - Апатиты: Кольский НЦ РАН, 1995.-С.112-121.

4. Дегтярев Ю.И. Исследование операций. - М.: ВШ, 1986.-319с.

5. Корбут А.А., Финкельштейн Ю.Ю. Дискретное про граммирование.- М.: Наука, 1969.- 368с.