Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

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




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, требуется выполнить команду в терминале:

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

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

Модули Zi включают в себя непосредственно длительность контрольных операций ti,а также интервалы tij , к примеру, ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U), где вершина Z0 (мажоранта), для которой t0 и t 0i равны нулю, фиксирует начало процесса построения множества возможных вариантов (допустимых) решений W(S0). Висячая вершина графа (в примере Zv) фиксирует окончание процесса ветвление вариантов.

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



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

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

Идея этого метода заключается в следующем. Множест­во W(S0) всех допустимых вариантов решения разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Si) до полу­чения подмножества W(Sν), состоящего из единственного вариан­та. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вари­антов, а получаемое при этом дерево D ( S,ГD) - деревом реше­ний (ветвлений). Здесь 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) может быть интерпретирован следующим образом. Находится для каждой вер­шины SkS дерева ветвления вариантов D множество

(2.7)

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

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

. (2.8)

где t*(Sk)=Στi + Στkl .

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

Тоц (Sk)= min { Тоц (Sk)} | Sk Є S*} ,

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

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

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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є 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




Дата добавления: 2013-12-29; просмотров: 377; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10184 - | 7791 - или читать все...

Читайте также:

  1. B. Сохранение жизни и здоровья в условиях автономного существования
  2. I. Торможение процесса модернизации в Японии
  3. II. ПУТИ РАЗВИТИЯ КАПИТАЛИЗМА 4 страница. В ответ на усиление антирабовладельческой агитации плантаторы требовали ограничений свободы слова и печати, призывали конгресс из- дать закон, запрещавший
  4. IV. Определение участников процесса СП
  5. June, 2010. Аналогичная ситуация наблюдается в атмосферных процессах, в частности, в увеличении числа торнадо, ураганов, тропических штормов, наводнений и т.д. Глобальные
  6. V Вопросы выходного контроля
  7. VI. МАТЕРИАЛЫ ДЛЯ КОНТРОЛЯ ЗА УСВОЕНИЕМ ТЕМЫ
  8. А. Правила поведения в природных условиях
  9. Адаптация личности в организации: сущность процесса и факторы
  10. Анализ инвестиционных проектов в условиях инфляции
  11. Анализ инвестиционных проектов в условиях риска
  12. Аналитический метод. - когда в планируемом периоде не предполагаются существенные изменения в условиях работы предприятия, по сравнению с предшествующим периодом;


 

18.204.2.53 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.008 сек.