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

Содержание

Задание

Теоретическая часть

Метод ветвей и границ

Метод наискорейшего спуска

Практическая часть

Задача №1

Задача №2 Задание

Определение последовательности проведения проверок с использованием метода ветвей и границ, и количества повторных измерений методом наискорейшего спуска при ограничении на время проверок.

Дано:

1. Граф исходного множества модулей и таблицы длительности операций.

2. Характеристики параметров, допуски и погрешность измерений.

Теоретическая часть

Метод ветвей и границ

Наиболее перспективным способом решения оптимизационных задач контроля является метод ветвей и границ.

Идея этого метода заключается в следующем. Множество 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-1zi = Ø.

Метод ветвей и границ предполагает построение дерева ветвления вариантов Е и фактически представляет собой процедуру последовательного анализа вариантов, дополненную прогнозированием такого направления поиска, в котором с наибольшей вероятностью находится оптимальное решение. Идея прогнозирования заключается в оценке нижних границ минимизируемой целевой функции для разветвляемых подмножеств 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єГz0

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

∑τk ≤ t(L0*) и (V R)[tk≤Tk(zk)] (1.7)

k:zk є Z

где tk – время завершения к-го модуля, определяемое из полученного решения D.

 Скачать реферат