Дискретная математика & математическая логика

4.6. ПАРЕТО-ОПТИМИЗАЦИЯ

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

Итальянский экономист Вильфредо Парето (1848–1923) – рис. 4.14, предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier).

Рис. 4.14. Вильфредо Парето

Подмножество PF множества A называется его границей Парето для частичного порядка U, если любые два элемента PF не сравнимы, а любому другому элементу из A предшествует ка- кой-либо элемент из PF.

На рис. 4.15 множество A состоит из жирно нарисованных точек на плоскости. Одна точка предшествует другой, если обе ее

151

ве («горячее»), при облегчённом резерве («тёплое»), при холодном резерве («холодное»). Кроме того, указаны ограничения на применение этих методов. Вариант резервирования имеет вид вектора:

(ki , η); i =1, n; η=1, m.

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

Две постановки задачи оптимизации структурной схемы надёжности (ССН) системы выглядят следующим образом:

1) Найти (ki , η) :

Wc → min при Pc(t) ≥ Pcзад(t). 2) Найти (ki , η) :

Pc(t) → max при Wc ≤ Wc зад.

На первом этапе оптимизации по первому критерию добива-

ко второму этапу оптимизации. Соответствующее резервирование берётся за нулевое.

На втором этапе итеративно увеличивают резервы. Определение того, на каком участке необходимо добавить очередной резервный элемент, осуществляется итеративно по наибольшему приращению ВБР на единицу стоимости в соответствии с выражением для градиента [3, 4]:

итерации, начинающийся с 0 – это ССН, полученная на первом этапе. Пример. Пусть система автоматизации СА включает в свой состав пять подсистем. Известны значения вероятности безотказной работы (ВБР) Pi и стоимости Wi (где i = 1, …, 5) каждого из уст-

153

ройств. При синтезе оптимальной в смысле критериев 1 и 2 ССН допускается: мажоритарное резервирование подсистемы 1 на начальном шаге оптимизации и резервирование замещением с нагруженным режимом работы элементов на других шагах (при необходимости возможна замена мажоритарного резервирования на резервирование замещением с нагруженным режимом работы элементов уже на начальном шаге, либо использования МЭ, мажоритарного элемента, 3 из 5; резервирование замещением с нагруженным режимом работы элементов для подсистем 2, 3, 4; резервирование замещением снагруженным либо ненагруженным режимом работы резервных элементов для подсистемы 5. Ненадежностью и стоимостью мажоритарныхэлементов ипереключающих устройств можнопренебречь.

Заданные значения вероятностей безотказной работы подсис-

тем: P1 = 0,9, P2 = 0,75, P3 = 0,82, P4 = 0,8, P5 = 0,9, их стоимости

W1 = 16, W2 = 11, W3 = 13, W4 = 12, W5 = 15 соответственно. Заданное значение ВБР системы Pcзад(t) = 0,94, заданное (допустимое) значение стоимости системы

W зад = 120.

Решение:

А. Найдем Wc → min при Pс (t ) ≥ Pсзад (t ).

1. Для начала проверим выполнение такого условия Pi (t) ≥ Pсзад (t) для каждого i от 1 до 5.

Видно, что ни для одного из участков системы это условие не выполняется, поэтому необходимо введение резервных элементов. На первом участке системы требуется использовать неадаптивное мажоритарное резервирование (два из трёх):

P (t) = P3 + 3P2 (1 − P) = 3P2 − 2P3 .

1

На остальных участках– резервирование замещением с нагруженным режимом работы резервных подсистем, т.е. P(t) =1 − (1− P)2 – работаетхотябыодинканализдвух.

154

В результате получим следующую структурную схему надёжности системы – рис. 4.16:

Рис. 4.16. ССН для первой попытки выполнения условия Pi (t) ≥ Pсзад (t) для каждого i от 1 до 5

Затем ещё раз проверим выполнение условия Pi (t) ≥ Pсзад (t) , рассчитав значение ВБР на каждом участке:

P4 (t) =1 − (1− P4 )2 = 0,96 > Pcзад (t),

P5 (t) = 1 − (1 − P5 )2 = 0,99 > Pcзад (t).

Условие не выполняется для второго участка, значит, введём на нём ещё один резервный элемент – рис. 4.17:

Рис. 4.17. ССН для второй попытки выполнения условия Pi (t) ≥ Pсзад (t) для каждого i от 1 до 5

155

Получим:

P2 (t) =1 − (1 − P2 )3 = 0,9844 > Pcзад (t),

P3 (t) = 1 − (1 − P3 )2 = 0,9676 > Pcзад (t),

P4 (t) =1 − (1− P4 )2 = 0,96 > Pcзад (t),

P5 (t) = 1 − (1 − P5 )2 = 0,99 > Pcзад (t).

Найдем ВБР системы и ее стоимость на 0-м шаге (для j = 0):

Pс0 = 0,972·0,9844·0,9676·0,96·0,99 = 0,8799 <Pcзад (t),

Wс0 = 3·16 + 3·11 + 2· (13 + 12 + 15) = 161.

Теперь, когда каждая подсистема обладает ВБР большей или равной заданной, начнём увеличивать ВБР всей системы.

Попробуем увеличить ВБР для 1-й подсистемы. Поскольку разрешено использовать неадаптивное мажоритарное резервирование, то придётся вводить 5 каналов и осуществлять выбор 3 из 5:

P1 (t) = P5 + 5P4 (1 − P) +10P3 (1− P)2 .

1

На остальных участках– резервирование замещением с нагруженным режимом работы резервных подсистем, т.е. Pi1(t) =1− (1− Pi )n – работаетхотябыодинканализимеющихся. Получим:

156

Сведём расчёты первой итерации в табл. 4.2. Исходное: 0-й шаг – каналы 3, 3, 2, 2, 2. Вводим ещё один канал на каждом участке, а на первом – ещё два. Получаем 5, 4, 3, 3, 3.

Таблица 4 . 2

Первая итерация задачи А

Получим градиенты – табл. 4.3:

Таблица 4 . 3

Определение наиболее выигрышного участка задачи А

(δ1i )* = δ14 , значит, очередной элемент надо добавить на 4-м участке. Следовательно, ССНдля шагаj = 1 будетиметьвид(рис. 4.18):

Рис. 4.18. ССН для первой итерации увеличения вероятности безотказной работы

Pс1 = 0,972·0,9844·0,9676·0,992·0,99 = 0,909 <Pcзад (t), Wс1 = Wс0 + W4 = 173.

157

Мы увеличиваем резерв только на 4-м участке, остальные без изменений. Вторая итерация – табл. 4.4, 4.5. Исходное: 1-й шаг – увеличиваем резерв только на 4-м участке, остальное без изменений. Каналы: 3, 3, 2, 3, 2. 2-й шаг – опять увеличиваем резервы, в том числе на 4-м. Получаем 5, 4, 3, 4, 3.

Таблица 4 . 4

Вторая итерация задачи А

Таблица 4 . 5

Определение наиболее выигрышного участка для 2-й итерации задачи А

довательно, ССН для шага j = 2 будет иметь вид (рис. 4.19):

Рис. 4.19. ССН для второй итерации увеличения вероятности безотказной работы

Pс2 = 0,972·0,9844·0,994·0,992·0,99 = 0,934 <Pcзад (t) .

Wс2 = Wс1 + W3 = 186,

158

т.е. увеличиваем резерв только на 3-м участке, остальные без изменений. Третья итерация – табл. 4.6, 4.7. Исходное: 2-й шаг – увеличиваем резерв только на 3-м участке, остальное без изменений.

участке. Это два дополнительных элемента. Следовательно, ССН для шага j = 3 будет иметь вид (рис. 4.20):

Рис. 4.20. ССН для 3-й и последней итерации увеличения вероятности безотказной работы (задача А)

159

Pс3 = 0,9914·0,9844·0,994·0,992·0,99 = 0,953≥ Pcзад (t),

что удовлетворяет условию Pc(t) ≥ Pcзад (t).

Стоимость реализации системы на третьем шаге оптимизации

Wс3 = Wс2 + 2W1 = 218.

Итак, минимальная стоимость реализации системы Wсmin = 218 при достигаемой Pc(t) = 0,953 больше заданной 0,94.

Б. Найдем Pc(t) → max при Wс ≤ Wсзад .

1. Для начала проверим выполнение условия Wс ≤ Wсзад (i от 1 до 5) для нерезервированной системы (рис. 4.21):

Рис. 4.21. ССН нерезервированной системы

Найдем ВБР системы и ее стоимость на 0-м шаге (для j = 0):

Pс0 = 0,9·0,75·0,82·0,8·0,9 = 0,39852.

Wс0 = 16 + 11 + 13 + 12 + 15 = 67 < Wсзад .

Видно, что для нерезервированной системы условие по стоимости выполняется, но имеется запас стоимости для увеличения надёжности системы, поэтому необходимо введение резервных элементов. На первом участке системы требуется использовать неадаптивное мажоритарное резервирование – выбор двух из трёх:

P (t) = P3 + 3P2 (1 − P) = 3P2 − 2P3 .

1

На остальных участках – резервирование замещением с нагруженнымрежимомработырезервныхподсистем, т.е. P (t) =1− (1− P )2 – работаетхотябыодинканализдвух.

160