|
| |
|
Слаботочка Книги 6 Ti, разбивающего каждое такое подмножество оптимальным образом. Оптимальным разбиением называется такое, которое обеспечивает минимальное среднее значение суммарной стоимости всех дальнейших разбиений, производимых до получения одноэлементных подмножеств. Если а* (Qj)-оптимальная стратегия разбиений некоторого подмножества Qj, содержащего отказавший элемент, а С [а* (Qj)] - стоимость реализации оптимальной стратегии, то процедура построения а* (Q) представляет собой рекуррентный процесс последовательного определения а* (Qj) для всех подмножеств, состоящих из двух, трех элементов и т. д. На каждом шаге этого процесса находится тест g Tj, такой, что С [а* (Qj)] = min [с%, -f Qt,-, С [о* (Qfj,)] -f (1 Qf„) С [a* (Qf„)] 1 • Для построения оптимальной программы поиска отказа методом динамического программирования необходимо найти и запомнить тесты, разбивающие оптимальным образом все возможные подмножества множества Q. Прямое использование метода динамического программирования для данной задачи при реальных размерностях задачи оказывается весьма трудоемким, а иногда даже практически нереализуемым. 16.2.4. Перестановочный прием. В случае поэлементных проверок удается получить простое правило нумерации тестов для нахождения процедуры, минимизирующей средние затраты на поиск отказавшего элемента. Перестановочный прием заключается в том, что от любой произвольной нумерации тестов можно попарной перестановкой только лишь соседних тестов за конечное число шагов перейти к любой наперед заданной последовательности их проведения, в том числе и оптимальной. Если удается найти удобный критерий сравнения двух соседних тестов по влиянию порядка их применения на результирующий целевой функционал - среднее время поиска отказавшего элемента, то при определенных условиях удается вычислить критерий для каждого теста и затем пронумеровать все тесты в соответствии с монотонным изменением этого критерия. При произвольной нумерации тестов целевой функционал вида (16.1) для данного частного случая С [а (Q)] = ci -bi С [а (е)] -f Pi С fo (Qxi)], где С [а (eJ] = О, так как - одноэлементное множество, которое далее уже не нужно проверять, а С [а (Q\ei)] = С2 + С [а (Q\(ei Ve))]- Окончательно С = Ci + pi (Ca Ч-рг (Сз + Рз (4 + •••)))- Записав аналогичное выражение для случая, когда для элементов с номерами ft и А: + 1 изменен порядок проверки, и сравнив значения суммарных затрат для обоих этих случаев, находим, что оптимальный порядок при возможности поэлементной проверке соответствует нумерации элементов в соответствии с условием Примечание. В случае равенства порядок проверки безразличен. 16.2.5. Рекурсивный метод. Для точного решения рассматриваемой задачи можно использовать так называемый рекурсивный метод, который оказывается на практике эффективнее метода динамического программирования. Будем рассматривать последовательный поиск отказавшего элемента в множестве Q как многошаговый процесс последовательного разбиения Q, продолжаю- щийся до получения в результате разбиении одноэлементных подмножеств. Идея метода при построении программы поиска состоит в последовательном разбиении Q по каждой ветви графа до получения одноэлементных подмножеств, определении наилучших разбиений на каждом уровне и с возвращением на предыдущий уровень. Для разбиения множества Q на первом шаге (уровне) может быть использован любой тест матрицы Т. Рассмотрим первый из них (первоначальная нумерация тестов во всех матрицах предполагается произвольной). Применение этого теста разбивает Q на подмножества и Q. Предположим, что оптимальные стратегии дальнейшего поиска отказа о* (Q) (если исход не успешен) и о* (И) (если исход успешен) известны. Тогда образуем условно-оптимальную стратегию о* (Q) = [tl, а* (Qj), а* (Q,)] и вычислим среднюю стоимость ее реализации в соответствии с (16.1). Далее аналогичным образом определим условно оптимальную стратегию а* (Q) и запомним стратегию с меньшей стоимостью. Предположим, что для некоторого подмножества Qj стратегия o*(Qj), необходимая для построения а} (Q), оказывается неизвестной. Тогда запомним лучшую из найденных I -1 условно оптимальных стратегий и перейдем к рассмотрению возможных разбиений подмножества Q,. Сформируем матрицу существенных тестов Тг и для каждого t\i) 6 Tt аналогично предыдущему определим условно-оптимальную стратегию а** (Qj) = и<$1 а* (Qfo), о* (Qt-,)], k = 1,..., т, а затем оптимальную а* (Q) так, чтобы C[a*(Qj)]= min C[a**(Qj)]. Поскольку предыдущий цикл вычислений был прерван именно из-за отсутствия а* (Qj), то теперь эти вычисления могут быть продолжены. Систематическое повторение описанной процедуры для каждого подмножества, полученного в результате разбиения Q последовательным применением тестов, очевидно, приведет к построению оптимальной стратегии. Эффективность метода может быть дополнительно повышена за счет построения стратегий, достаточно близких к оптимальным, и правил отсеивания неперспективных вариантов стратегий путем сравнения нижних границ стоимостей реализаций этих вариантов с лучшим из результатов, полученных к текущему моменту вычислений. Как следует из приведенного выше описания, построение условно-оптимальных стратегий а* (Qj), й == 1, .... rrii, для определения оптимальной стратегии а* (Qj) удобно производить в порядке нумерации тестов tt) матрицы Tj. Для упрощения операции отсева удобно заранее выбрать такой порядок нумерации, чтобы условно-оптимальные стратегии с меньшими номерами в среднем оказывались лучше, чем другие варианты. Тогда при наличии простого способа оценки нижних границ стоимостей очередные варианты условно-оптимальных стратегий можно будет отбрасывать без построения. Предположим, что на некотором цикле определения а* (Qj) уже построены k - 1 условно-оптимальных стратегий и среди этих стратегий выбрана лучшая а* (Qj) стоимостью С [а"* (Qj)]. Пусть rf„ - нижняя граница стоимости условно-оптимальной стратегии а** (Qj). Тогда очевидно, что стратегия а** (Qj) не может быть лучше, если C[a-(01 < 4). В этом случае вариант а** (Qj) не является перспективным и может быть отброшен без построения. правила нумерации тестов матриц 7; и вычисления нижних границ могут быть эффективным образом подобраны с учетом структуры конкретных задач. Однако можно рекомендовать следующие простые правила. Нумерация тестов матриц Ti, полученных преобразованием Т, производится в порядке неубывания стоимостей тестов, включенных в эти матрицы. Для определения Г(,-) используется элементарное следствие (16.1): стоимость условно-оптимальной стратегии а** (Qj) не может быть меньше стоимости теста tiy примененного для разбиения Qj на первом шаге, т. е. Г,) = eft). Как следует из анализа задачи, логика построения оптимальной стратегии поиска отказа остается неизменной при рассмотрении как множества Q, так и любого его подмножества, что объясняется рекуррентной структурой задачи. Для того чтобы использовать эту рекуррентность для сокращения вычислений, тесты исходной матрицы Т нумеруются в порядке неубывания мощностей контролируемых ими подмножеств, т. е. в порядке неубывания числа единиц в каждой строке. 16.2.6. Минимаксный критерий. На практике планирование работ по контролю технических систем часто проводится без учета информации о надежности систем из-за отсутствия такой информации или слишком большой ее недостоверности. В этих случаях целесообразным оказывается минимаксный подход к задачам построения программ проведения проверок. При таком подходе оптимальная стратегия строится в предположении реализации самой неблагоприятной ситуации. Будем считать достоверно известным факт отказа в ОК только одного элемента и рассмотрим задачу построения условной программы поиска этого элемента последовательным применением тестов матрицы Т так, чтобы максимальные затраты на реализацию программы были минимальными. Процедуру применения тестов матрицы Т для поиска отказавшего элемента снова будем рассматривать как последовательное разбиение множества Q. Тогда некоторая стратегия а (Qj) поиска отказа в подмножестве Qj, на первом шаге которой применяется тест /fj, G 7j (Tj формируется по правилам, описанным выше), может быть записана аналогично (16.1). Стоимость реализации этой стратегии представляет собой случайную величину, максимальное значение которой может быть найдено из выражения R [о (QJ] = 4 -f max {R [a (Qo)], R \o (Qfo)]}. (16.2) Описанная выше методика построения статистически оптимальных программ: поиска отказавшего элемента может быть применена и в данном случае, если используемые при проведении вычисления средние стоимости С [а (Qj)] заменить максимальными стоимостями, найденными по (16.2). 16.3. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ОТКАЗОВ С ВОССТАНОВЛЕНИЕМ ОБЪЕКТА КОНТРОЛЯ 16.3.1. Предварительные замечания. Во многих практических ситуациях не удается сделать сколько-нибудь обоснованных предположений о возможности отказа только одного элемента при информации об отказе системы. Пусть возможны любые комбинации отказавших-элементов, причем допускается замена любых отказавших элементов работоспособными по мере их обнаружения. Процесс восстановления производится следующим образом. Последовательным применением некоторых тестов матрицы Т в ОК производится поиск первого отказавшего элемента. Этот элемент заменяется годным, после чего контролируется работоспособность всех элементов минимального поданожества Q„, включающего замененный элемент. При результате «проверка Q„ не успешна» производится дальнейший поиск отказавших элементов в этом подмножестве и замена их годными, причем 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 [90] 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 |