Контроль и диагностика систем

Содержание
Задание
Теоретическая часть
Метод ветвей и границ
Метод наискорейшего спуска
Практическая часть
Задача №1
Задача №2

Задание
Определение последовательности проведения проверок с использованием метода ветвей и границ, и количества повторных измерений методом наискорейшего спуска при ограничении на время проверок.
Дано:
1. Граф исходного множества модулей и таблицы длительности операций.
№ вершины Z1
Z2
Z3
Z4
Z5
Длительность, τi 2 4 5 3 8
Дуги 1-3 2-4 2-5 3-4
Длительность, tij 15 12 3 7
2. Характеристики параметров, допуски и погрешность измерений.
№ параметра 1 2 3 4 5
σИЗМ /σПАР 0.1 0.3 0.5 0.2 0.4
ti 20 30 15 50 5
Теоретическая часть
Метод ветвей и границ
Наиболее перспективным способом решения оптимизационных задач контроля является метод ветвей и границ.
Идея этого метода заключается в следующем. Множество W(S0 ) всех допустимых вариантов решения σ разбивается на непересекающиеся подмножества W(Sk ), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Sl ) до получения подмножества W(Sv ), состоящего из единственного варианта. Процесс разбиения множества допустимых вариантов W(S0 ) на их непересекающиеся подмножества называется ветвлением вариантов, а получаемое при этом дерево – деревом решений. Каждой вершине дерева ветвления соответствует некоторый модуль из графа, а любой путь по дереву определяет соответствующий граф очередности. Множество вершин описывает определенный вариант процесса.
Пусть Y(Sk ) – множество вершин в графе очередности D, соответствующих пути от S0 до Sк в дереве Е. из каждой вершины Sк выходит столько ветвей, сколько допустимых модулей (претендентов упорядочения) имеется в подмножестве Z\ Y(Sk ). Множество допустимых на каждом шаге процесса ветвления модулей образует фронт упорядочения. Наглядное представление об образовании фронта упорядочения дает преобразованный в соответствии с формулой (1.1) граф G
F(zl ) = max[f(zi ) + til ] (1.1)
zi →zj
Очевидно, на первом шаге процесса построения дерева Е фронт упорядочения образуют вершины, которые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в которую не входят дуги из других вершин и т.д. На произвольном шаге фронт упорядочения образуют модули, для которых Г0 -1 zi = Ø.
Метод ветвей и границ предполагает построение дерева ветвления вариантов Е и фактически представляет собой процедуру последовательного анализа вариантов, дополненную прогнозированием такого направления поиска, в котором с наибольшей вероятностью находится оптимальное решение. Идея прогнозирования заключается в оценке нижних границ минимизируемой целевой функции для разветвляемых подмножеств W(Sk ). На каждом шаге ветвление продолжается из вершины, имеющей минимальную оценку. Задача сводится к отысканию на дереве конечной вершины, соответствующей оптимальному допустимому решению со значением целевой функции, меньшим или равным оценкам висячих вершин дерева Е.
Как показывает практика применения метода ветвей и границ, эффективность его значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции.
Для минимизации этот метод может быть применен следующим образом.
На основе исходной информации, заданной графом G, построим
│Z│– размерные матрицы, такие что
τi + tij , если (i,j) принадлежит U
bij = (1.2)
- ∞, если (i,j) не принадлежит U
tij + τi , если (i,j) принадлежит U
dij = (1.3)
- ∞, если (i,j) не принадлежит U
Введем следующие понятия:
а) наиболее раннее время начала модуля
Тн (Zк ) = max { Тн (Zi ) + bik }, Тн (Z0 ) = 0 (1.4)
0< i ≤ k
б) критический путь – самый длинный путь, ведущий от мажоранты графа к миноранте, причем за длину любого пути принимается сумма длительностей τi для всех модулей и всех задержек tij , входящих в этот путь.
Обозначим H = {Lij } – множество всех независимых путей на графе (путей, отличающихся друг от друга хотя бы одной дугой), ведущих от вершины zi к zj , и H’ = {Lk }є H – множество всех независимых путей, ведущих от вершины zk к миноранте. Тогда такой путь представляет собой частичный подграф GL = (ZL , UL ), длина которого равна:
T(L) = ∑ τk + ∑ tkl (1.5)
k:zk є ZL (k,l) є UL
Длина критического пути может быть вычислена из рекуррентной формулы:
Ткр = t(L0 *) = max {t(L0 )}= τ0 + max {t0, j + t(Lj *)} (1.6)
L0 єH’
j:zj єГz 0
Так как длина критического пути характеризует наименьшую длительность процесса контроля, то выражение (6) может послужить основой для оценки нижних границ минимизируемого функционала. Необходимыми условиями для достижения этой границы являются:

∑τk ≤ t(L0 *) и (VR)[tk ≤Tk (zk )] (1.7)
k:zk є Z
где tk – время завершения к-го модуля, определяемое из полученного решения D.
На основании приведенных выражений процесс преобразования графа G = (Z, Г) в граф очередности G = (Z, ГD ) может быть интерпретирован следующим образом. Определим для каждой вершины Sk є S дерева ветвления вариантов Е множество
N(Sk ) = {zi │zi є Z, Г-1 zi є Y(Sk )} (1.8)
которое определяет фронт упорядочения. Согласно априорной части упорядоченности модулей, выражаемой отображением Г, очередной модуль при пошаговом построении графа D может быть выбран только из │N(Sk )│, выражающего мощность фронта упорядочения.
На основе (6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk ) в следующем виде:
Тоц (Sk ) = t*(Sk ) + max {t(Li *) + max [0, Тн (zi ) - t*(Sk )]} (1.9)
i:zj є N(Sk )
где t*(Sk ) = max{ti │i:zi є Y(Sk )}
На каждом шаге для дальнейшего разветвления выбирается вершина Sk * , для которой справедливо равенство
Тоц (Sk * ) = min{ Тоц (Sk )│Sk є S*} (1.10)
Где S* с S – подмножество вершин, из которых можно продолжать ветвление, т.е.

S* = {Si │Si :│∆Si │<│N(Si )│} (1.11)
Выбранная вершина Sk є S* в итоге ветвления получает│N(Sk )│последователей, определяющих разбиение множества возможных вариантов W(Sk ) на │N(Sk )│непересекающихся подмножеств.
При достижении в процессе ветвления подмножества W(Sν ), состоящего из единственного варианта D(Sν ) = [Y(Sν ), ГD ], Y(Sν ) = Z, последний будет оптимальным если
t*(Sν ) ≤ min{ Тоц (Sk )│ Sk є S*}. (1.12)
если (12) не выполняется, то поиск оптимального решения продолжается из вершины, имеющей наименьшую из оценок Тоц (Sk * ).

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию