Контроль и диагностика систем (стр. 1 из 4)

Московский Авиационный Институт

(государственный технический университет)

КУРСОВАЯ РАБОТА

ПО КУРСУ: «кОНТРОЛЬ И ДИАГНОСТИКА СИСТЕМ»

ВАРИАНТ №7

Москва 2009 г.

Содержание

Задание

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

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

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

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

Задача №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(S₀) всех допустимых вариантов решения σ разбивается на непересекающиеся подмножества W(S_k), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(S_l) до получения подмножества W(S_v), состоящего из единственного варианта. Процесс разбиения множества допустимых вариантов W(S₀) на их непересекающиеся подмножества называется ветвлением вариантов, а получаемое при этом дерево – деревом решений. Каждой вершине дерева ветвления соответствует некоторый модуль из графа, а любой путь по дереву определяет соответствующий граф очередности. Множество вершин описывает определенный вариант процесса.

Пусть Y(S_k) – множество вершин в графе очередности D, соответствующих пути от S₀ до S_к в дереве Е. из каждой вершины S_к выходит столько ветвей, сколько допустимых модулей (претендентов упорядочения) имеется в подмножестве Z\ Y(S_k). Множество допустимых на каждом шаге процесса ветвления модулей образует фронт упорядочения. Наглядное представление об образовании фронта упорядочения дает преобразованный в соответствии с формулой (1.1) граф G

F(z_l) = max[f(z_i) + t_il] (1.1)

z_i→z_j

Очевидно, на первом шаге процесса построения дерева Е фронт упорядочения образуют вершины, которые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в которую не входят дуги из других вершин и т.д. На произвольном шаге фронт упорядочения образуют модули, для которых Г₀^-1z_i = Ø.

Метод ветвей и границ предполагает построение дерева ветвления вариантов Е и фактически представляет собой процедуру последовательного анализа вариантов, дополненную прогнозированием такого направления поиска, в котором с наибольшей вероятностью находится оптимальное решение. Идея прогнозирования заключается в оценке нижних границ минимизируемой целевой функции для разветвляемых подмножеств W(S_k). На каждом шаге ветвление продолжается из вершины, имеющей минимальную оценку. Задача сводится к отысканию на дереве конечной вершины, соответствующей оптимальному допустимому решению со значением целевой функции, меньшим или равным оценкам висячих вершин дерева Е.

Как показывает практика применения метода ветвей и границ, эффективность его значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции.

Для минимизации этот метод может быть применен следующим образом.

На основе исходной информации, заданной графом G, построим

│Z│– размерные матрицы, такие что

τ_i + t_ij, если (i,j) принадлежит U

b_ij= (1.2)

- ∞, если (i,j) не принадлежит U

t_ij + τ_i, если (i,j) принадлежит U

d_ij = (1.3)

- ∞, если (i,j) не принадлежит U

Введем следующие понятия:

а) наиболее раннее время начала модуля

Т_н(Z_к) = max { Т_н(Z_i) + b_ik}, Т_н(Z₀) = 0 (1.4)

0< i ≤ k

б) критический путь – самый длинный путь, ведущий от мажоранты графа к миноранте, причем за длину любого пути принимается сумма длительностей τ_i для всех модулей и всех задержек t_ij, входящих в этот путь.

Обозначим H = {L_ij} – множество всех независимых путей на графе (путей, отличающихся друг от друга хотя бы одной дугой), ведущих от вершины z_i к z_j, и H’ = {L_k}є H – множество всех независимых путей, ведущих от вершины z_k к миноранте. Тогда такой путь представляет собой частичный подграф G_L = (Z_L, U_L), длина которого равна:

T(L) = ∑τ_k+ ∑t_kl(1.5)

k:z_kє Z_L(k,l) є U_L

Длина критического пути может быть вычислена из рекуррентной формулы:

Т_кр = t(L₀*) = max {t(L₀)}= τ₀ + max {t_0,j+ t(L_j*)} (1.6)

L₀єH’

j:z_jєГ_z0

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

∑τ_k≤ t(L₀*) и (VR)[t_k≤T_k(z_k)] (1.7)

k:z_kє Z

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

На основании приведенных выражений процесс преобразования графа G = (Z, Г) в граф очередности G = (Z, Г_D) может быть интерпретирован следующим образом. Определим для каждой вершины S_kє S дерева ветвления вариантов Е множество

N(S_k) = {z_i│z_i є Z, Г^-1z_iє Y(S_k)} (1.8)

которое определяет фронт упорядочения. Согласно априорной части упорядоченности модулей, выражаемой отображением Г, очередной модуль при пошаговом построении графа D может быть выбран только из │N(S_k)│, выражающего мощность фронта упорядочения.

На основе (6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(S_k) в следующем виде:

Т_оц(S_k) = t*(S_k) + max {t(L_i*) + max [0, Т_н(z_i) - t*(S_k)]} (1.9)

i:z_jє N(S_k)

где t*(S_k) = max{t_i│i:z_iє Y(S_k)}

На каждом шаге для дальнейшего разветвления выбирается вершина S_k*, для которой справедливо равенство

Т_оц(S_k*) = min{ Т_оц(S_k)│S_k є S*} (1.10)

Где S* с S – подмножество вершин, из которых можно продолжать ветвление, т.е.

S* = {S_i│S_i:│∆S_i│<│N(S_i)│} (1.11)

Выбранная вершина S_k є S* в итоге ветвления получает│N(S_k)│последователей, определяющих разбиение множества возможных вариантов W(S_k) на │N(S_k)│непересекающихся подмножеств.

При достижении в процессе ветвления подмножества W(S_ν), состоящего из единственного варианта D(S_ν) = [Y(S_ν), Г_D], Y(S_ν) = Z, последний будет оптимальным если

t*(S_ν) ≤ min{ Т_оц(S_k)│ S_kє S*}. (1.12)

если (12) не выполняется, то поиск оптимального решения продолжается из вершины, имеющей наименьшую из оценок Т_оц(S_k*).

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

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

Рассмотрим задачу:

Требуется обеспечить не менее, чем заданную достоверность результатов контроля при условии, что суммарно время измерения контролируемых параметров не превысит некоторой величины.

Введем следующие обозначения:

Р – достоверность результатов контроля объекта (вероятность получения правильных результатов, Р₀ – заданное значение );

Т – суммарное время измерения всех контролируемых параметров (Т0 – заданное значение);

m – количество контролируемых параметров;

n_i – количество повторных измерений i-го параметра;

t_i – время одного измерения i-го параметра;

p_i(n_i) – достоверность результатов контроля i-го параметра при n_i – кратном измерении.

Тогда задача формулируется: найти

(2.1)

при условии, что выполняется ограничение