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

Sudo apt-get install python-matplotlib python-networkx

Программное обеспечение

Содержание

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(Национальный Исследовательский Университет)

Факультет №3«Системы управления,

информатика и электроэнергетика»

Кафедра №308«Информационные технологии»

Курсовая работа

по курсу

«Технический контроль и диагностика систем ЛА»

Выполнил: Громов Павел Дмитриевич

Группа: 03-417

Проверил:доцент, к.т.н. Пискунов Вячеслав Алексеевич

Москва 2012 год

Программное обеспечение……………………………………………………………………………………………………3

Систематизация процесса контроля в условиях ограничений частичной упорядоченности……………………………………………………………………………………………………………………4

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

Практическая часть……………………………………………………………………………………………………….9

Выводы……………………………………………………………………………………………………………………….24

Определение количества повторных измерений контролируемых параметров оптимального по критерию максимума достоверности результатов……………………………….25

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

Практическая часть…………………………………………………………………………………………………….27

Выводы……………………………………………………………………………………………………………………….34

Список используемой литературы………………………………………………………………………………………35

Приложение 1……………………………………………………………………………………………………………………….36 Приложение 2……………………………………………………………………………………………………………………….53

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

Python — высокоуровневый язык программирования общего назначения, ориентированный на повышение производительности разработчика и читаемости кода. Синтаксис ядра Python минималистичен. В то же время стандартная библиотека включает большой объём полезных функций.

Python поддерживает несколько парадигм программирования, в том числе структурное, объектно-ориентированное, функциональное, императивное и аспектно-ориентированное. Основные архитектурные черты — динамическая типизация, автоматическое управление памятью, полная интроспекция, механизм обработки исключений, поддержка многопоточных вычислений и удобные высокоуровневые структуры данных. Код в Питоне организовывается в функции и классы, которые могут объединяться в модули (которые в свою очередь могут быть объединены в пакеты).

Минимальные системные требования:

ü Операционная система Linux/MacOS/Windows

ü Большинство современных компьютеров и даже мобильных телефонов способны запустить интерпретатор Python.

ü Для отрисовки изображений требуется установить библиотеки matplotlib и networkx. Чтобы установить их на операционную систему Ubuntu Linux, требуется выполнить команду в терминале:

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

Особенно острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тестового контроля работоспособности бортового оборудования. Поэтому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оптимального их проведения представляет практическую ценность.

Модули Z_i включают в себя непосредственно длительность контрольных операций t_i_,а также интервалы t_ij , к примеру, ожидания переходных процессов, или длительности настроек при переходе от операции z_i к z_j , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля T_k заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U), где вершина Z₀ (мажоранта), для которой t₀ и t₀_i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S₀). Висячая вершина графа (в примере Z_v) фиксирует окончание процесса ветвление вариантов.

Путем в графе G(Z,U) является последовательность ориентированных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине расположения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого подмножества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает преобразование его в дерево. Такое преобразование необходимо потому, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предварительном упорядочении.

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

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

Идея этого метода заключается в следующем. Множество W(S₀) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(S_k), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(S_i) до получения подмножества W(S_ν), состоящего из единственного варианта. Процесс разбиения множества допустимых вариантов W(S₀) на их непересекающиеся подмножества называется ветвлением вариантов, а получаемое при этом дерево D ( S,Г_D) - деревом решений (ветвлений). Здесь S={S_k} множество вершин этого дерева, а Г_D отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль z_i Î Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), Г_V]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YÌZ и законченный, если Y=Z) , а Г_V отношение порядка на множестве Y(S).

Пусть Y(S_k)—множество вершин в графе очередности V, соответствующих пути от S₀ до S_k в дереве D. Из каждой вершины S_k выходит столько ветвей, сколько допустимых модулей (претендентов для упорядочения) имеется в подмножестве Z\Y(S_k). Множество допустимых на каждом шаге процесса ветвления модулей образует фронт упорядочения. Наглядное представление об образовании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, которые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в которую не входят дуги из других вершин, и т. д. Hа произвольное шаге фронт упорядочения образуют те модули, для которых Г_о^-1z_i= .

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

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

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

На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||b_ij|| и ||d_ij|| такие, что

(2.2)

(2.3)

Вводится понятие T_н(z_k)- наиболее раннее время начала модуля z_k

(2.4)

Обозначим H={L_ij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины z_i к z_j и — множество всех независимых путей, ведущих от вершины z_k к миноранте (висячей вершине графа G).

Некоторый путь L_k по этому дереву представляет собой частичный подграф G(Z_k,U_k), при этом длина пути:

T(L_k) = (2.5)

Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины z_k к миноранте графа G.

. (2.6)

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

(2.7)

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

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

. (2.8)

где t^*(S_k)=Στ_i + Στ_kl .

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

Т_оц (S_k)= min { Т_оц (S_k)} | S_k Є S^*} ,

где S^*Є S- подмножество вершин, из которых можно продолжать ветвление на данном этапе построения дерева очередности.

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

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

T_оц(S_ν) ≤ { Т_оц (S_k)} | S_k Є S^*}. (2.9)

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

Дано:

1. Граф исходного множества модулей:

Z0 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z1 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z2 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z5 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z3 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z4 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Z6 острый дефицит общего времени на контроль испытывается обычно на этапе предполетной подготовки при проведении тесто¬вого контроля работоспособности бортового оборудования. По¬этому минимизация общего времени контроля всех параметров объекта за счет расчленения процедур контроля на модули и оп¬тимального их проведения представляет практическую ценность. Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U) , к примеру рис. 2.1, где вершина Z0 (мажоранта), для которой t0 и  0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов. Путем в графе G(Z,U) является последовательность ориенти¬рованных дуг U, которые выражают ограничения порядка между вершинами на этом пути. Длина пути от начала процесса (мажоранты) до некоторой вершины соответствует глубине распо¬ложения проверяемого подмножества и равна числу дуг на нем. В дальнейшем, говоря о глубине расположения проверяемого под¬множества, подразумевается нахождение соответствующей вершины на некотором k-м уровне графа G, что предполагает пре¬образование его в дерево. Такое преобразование необходимо пото¬му, что граф, построенный из непосредственного анализа объекта, обычно получается слишком сложным и нуждается в предваритель¬ном упорядочении. Поставленная задача примыкает по своей сущности к классу экстремальных комбинаторных задач. В принципе она может быть решена простым перебором вариантов, однако необходимый при этом объем вычислений не позволяет получить оптимального результата даже в простейшем случае. Перспективным способом решения оптимизационных задач контроля является метод ветвей и границ. Идея этого метода заключается в следующем. Множест¬во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу¬чения подмножества W(Sν), состоящего из единственного вариан¬та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари¬антов, а получаемое при этом дерево D ( S,ГD) - деревом реше¬ний (ветвлений) (рис. 2.2). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi  Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если Y=Z) , а ГV отношение порядка на множестве Y(S). Пусть Y(Sk)—множество вершин в графе очередности V, соот-ветствующих пути от S0 до Sk в дереве D. Из каждой вершины Sk выходит столько ветвей, сколько допустимых модулей (претенден¬тов для упорядочения) имеется в подмножестве Z\Y(Sk). Множе¬ство допустимых на каждом шаге процесса ветвления модулей об¬разует фронт упорядочения. Наглядное представление об образо¬вании фронта упорядочения дает преобразованный граф G. Очевидно, на первом шаге процесса построения дерева D фронт упорядочения образуют вершины, ко¬торые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в кото¬рую не входят дуги из других вершин, и т. д. Hа произвольное ша¬ге фронт упорядочения образуют те модули, для которых Го-1zi= . Метод ветвей и границ предполагает построение дерева ветвле¬ния вариантов D и фактически представляет собой процедуру пос-ледовательного анализа вариантов, дополненную прогнозировани¬ем такого направления поиска, в котором с наибольшей вероятно¬стью находится оптимальное решение. Идея прогнозирования за¬ключается в оценке нижних границ минимизируемой целевой функ¬ции для разветвляемых подмножеств W(Sk). На каждом шаге, ветвление продолжается из вершины, имеющей минимальную оцен¬ку. Задача сводится к отысканию па дереве конечной вершины, со¬ответствующей оптимальному допустимому решению со значением целевом функции, меньшим или равным оценкам висячих вершин дерева D. Как показывает практика применение метода ветвей и границ, его эффективность значительно зависит от способа представления решения в виде дерева вариантов и метода оценки нижней границы целевой функции. Для минимизации Tk этот метод может быть применен следующим образом. На основе исходной информации, заданной графом G, строится -размерные квадратные матрицы ||bij|| и ||dij|| такие, что (2.2) (2.3) Вводится понятие Tн(zk)- наиболее раннее время начала модуля zk . (2.4) Обозначим H={Lij}—множество всех независимых путей (путей, отличающихся друг от друга хотя бы одной дугой) на графе, ведущих от вершины zi к zj и — множество всех не¬зависимых путей, ведущих от вершины zk к миноранте (висячей вершине графа G). Некоторый путь Lk по этому дереву представляет собой частичный подграф G(Zk, Uk), при этом длина пути: T(Lk) = (2.5) Длина критического пути вычисляется из рекуррентного соотношения наиболее длинного пути из вершины zk к миноранте графа G. . (2.6) На основании приведенных выражений процесс преобразования графа G(Z,U) в граф очередности V=(Y,ГD) может быть интерпретирован следующим образом. Находится для каждой вер¬шины Sk S дерева ветвления вариантов D множество где - предшественники вершины zi на множестве Y(Sk) графа V, которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(Sk)|, выражающего мощность фронта упо¬рядочения. На основе (2.6) можно записать выражение для оценки нижних границ для произвольного подмножества вариантов W(Sk) в следующем виде: . (2.8) Tоц(Sk) = t*(Sk) + max {t(L*i) +max[0,TH(zi)-t*(Sk)]}, i:ziЄN(Sk) где t*(Sk)=Στi + Στkl . i:zi Є-Y(Sk) (k,l Є ГD) На каждом шаге для дальнейшего разветвления выбирается вершина S*k , для которой справедливо равенство Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} , Sk где S* Є S - подмножество вершин , из которых можно продолжать ветвление на данном этапе построения дерева очередности. Выбранная вершина Sk Є S* в итоге получает N (Sk) последователей, определяющих разбиение множества возможных вариантов W (Sk) на N (Sk) непересекающихся подмножеств. При достижении в процессе ветвления W (Sν) , состоящего из единственного варианта V [ Y (Sν), Гν)] , при этом Y (Sν)= Z и последний вариант будет оптимальный, если Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

Рисунок 1 - Граф исходного множества

2. Таблицы длительности операции и минимального времени задержки между модулями (таблица №1, таблица №2)

Таблица №1. Длительность операции

№ вершины	z1	z2	z3	z4	z5
Длительность τ_i

Таблица №2. Минимальное время задержки между модулями

Дуги	1-3	2-4	2-5	3-4
Длительность t_ij

Найти: Последовательность проведения проверок системы МВГ.

Решение: