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

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 _0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений 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
Длительность tij

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

Решение:

Z0

Z1

Z2

Z2

Z5

Z3

Z1

Z5

Z3

Z4

Z3

Z5

Z5

Z4

Z4

Z2

Z5

Z4