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

Работа добавлена на сайт samzan.net:

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

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

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

sudo apt-get install python-matplotlib python-networkx

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

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

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

Модули Zi включают в себя непосредственно длительность контрольных операций i,а также интервалы tij , к примеру, ожидания переходных процессов, или длительности настроек при переходе от операции zi к zj , а также времени для переключения соответствующих цепей коммутации. Минимизация общего времени контроля Tk заключается в оптимальном заполнении указанных времен ожидания контрольно-измерительными операциями других модулей. Однако при этом необходимо, в некоторых случаях, учитывать частичную априорную технологическую упорядоченность модулей в виде ограничений на отношение порядка U, которые задаются в виде графа G(Z,U), где вершина 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) - деревом решений (ветвлений). Здесь S={Sk} множество вершин этого дерева, а ГD отношение порядка на этом множестве. Каждой вершине дерева решений соответствует некоторый модуль zi Z графа G (Z,U), а любой путь по дереву определяет соответствующий граф очередности V[Y(S), ГV]. Множество вершин Y(S) описывает определенный вариант процесса (незаконченный, если YZ и законченный, если 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)

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

Дано:

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

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 этот метод может быть применен следующим образом.

(2.2)

(2.3)

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

. (2.4)

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

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

T(Lk) = (2.5)

. (2.6)

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

где - предшественники вершины zi на множестве Y(Sk) графа V,

которое определяет фронт упорядочения. Согласно априорной час-тичной упорядоченности модулей, выражаемой отображением Гk, очередной модуль при пошаговом построении графа D может быть выбран только из |N(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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

(2.2)

(2.3)

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

. (2.4)

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

T(Lk) = (2.5)

. (2.6)

где - предшественники вершины zi на множестве Y(Sk) графа V,

. (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

Tоц(Sν) ≤ { Тоц (Sk)} | Sk Є S*}.

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

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

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

№ вершины	z1	z2	z3	z4	z5
Длительность τi	3	5	7	1	8

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

Дуги	1-3	2-4	2-5	3-4
Длительность tij	10	7	3	12

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

Решение:

На рисунке 2 изображен граф всех возможных вариантов проведения проверок:

Рисунок 2 – Граф вариантов проведения проверок

Переобозначим вершины zi в Sk (рисунок 3).

Рисунок 3 – Граф состояний

Проведем отсечение некоторых ветвей МВГ.

1.Построим z-размерную квадратную матрицу bij.

2. Определим наиболее раннее начало модуля zk.

или =>

Определим длины путей, которые ведут от вершины zj к миноранте.

T(Lk) =

или

Полученные данные сведем в таблицу №3:

Таблица №3

zi	i			U	tij
z0	0	0	33	(0, 1)	0
z1	3	0	33	(0, 2)	0
z2	5	0	16	(1, 3)	10
z3	7	13	20	(2, 4)	7
z4	1	32	1	(2, 5)	3
z5	8	8	8	(3, 4)	12
z6	0	33	0	(4, 6)	0
				(5, 6)	0

Расчет нижних границ для подмножества вариантов W(Sk):

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

Шаг 1

S0, z0;

N(S1) = {z1,z2};

Y(S1) = {z0};

t*(S0) = τ0 = 0;

Tоц(S0) = 0 + max {33 + 0; 16 + 0} = 33.

Шаг 2

S1, z1;

N(S1) = {z2,z3};

Y(S1) = {z0,z1};

t*(S1) = τ0 + τ1 + t01 = 0 + 3 + 0 = 3;

Tоц(S1) = 3 + max {16 + 0; 20 + 13 - 3} = 3 + 33 = 33.

Шаг 3

S2, z2;

N(S2) = {z1,z5};

Y(S2) = {z0,z2};

t*(S2) = τ0 + τ2 + t02 = 0 + 5 + 0 = 5;

Tоц(S2) = 5 + max {33 + 0; 8 + 8 - 5} = 5 + 33 = 38.

Шаг 4

S3, z2;

N(S3) = {z3,z5};

Y(S3) = {z0,z1,z2};

t*(S3) = τ0 + τ1 + τ2 + t01 + t12 = 0 + 3 + 5 + 0 + 0 = 8;

Tоц(S3) = 8 + max {20 + 13 - 8; 8 + 8 - 8} = 8 + 25 = 33.

Шаг 5

S4, z3;

N(S4) = {z2};

Y(S4) = {z0,z1,z3};

t*(S4) = τ0 + τ1 + τ3 + t01 + t03 = 0 + 3 + 7 + 0 + 10 = 20;

Tоц(S4) = 20 + max {16 + 0} = 36.

Шаг 6

S5, z3;

N(S5) = {z4,z5};

Y(S5) = {z0,z1,z2,z3};

t*(S5) = τ0 + τ1 + τ2 + τ3 + t01 + t12 + t23 = 7 + 5 + 3 + 0 + 0 + 0 = 15;

Tоц(S5) = 15 + max {1 + 32 - 15; 8 + 0} = 15 + 18 = 33.

Шаг 7

S6, z5;

N(S5) = {z3};

Y(S5) = {z0,z1,z2,z5};

t*(S5) = τ0 + τ1 + τ2 + τ5 + t01 + t12 + t25 = 8 + 5 + 3 + 0 + 0 + 3 = 19;

Tоц(S5) = 19 + max {20 + 0} = 39.

Шаг 8

S7, z4;

N(S7) = {z5};

Y(S7) = {z0,z1,z2,z3,z4};

t*(S7) = τ0 + τ1 + τ2 + τ3 + τ4 + t01 + t12 + t23 + t34 = 1 + 7 + 5 + 3 + 0 + 0 + 0 + 12 = 28;

Tоц(S7) = 28 + max {8 + 0} = 36.

Шаг 9

S8, z5;

N(S8) = {z4};

Y(S8) = {z0,z1,z2,z3,z5};

t*(S8) = τ0 + τ1 + τ2 + τ3 + τ5 + t01 + t12 + t23 + t35 = 8 + 7 + 5 + 3 + 0 + 0 + 0 + 0 = 23;

Tоц(S8) = 23 + max {1 + 32 - 20} = 33.

Шаг 10

S9, z4;

N(S9) = {z6};

Y(S9) = {z0,z1,z2,z3,z5,z4};

t*(S9) = τ0 + τ1 + τ2 + τ3 + τ5 + τ4 + t01 + t12 + t23 + t35 + t54 = 0 + 3 + 5 + 7 + 8 + 1 + 0 + 0 + 0 + 0 + 0 = 24;

Tоц(S9) = 24 + max {0 + 33 - 24} = 33.

Таким образом, мы получили дерево решений (рисунок 5).

Рисунок 4 – Граф решений

Таблица №4 – Оценки нижних границ

S	zi	N(Sk)	Y(Sk)	t*(Sk)	Tоц(Sk)
S0	z0	z1z2	z0	0	33
S1	z1	z2z3	z0z1	3	33
S2	z2	z1z5	z0z2	5	38
S3	z2	z3z5	z0z1z2	8	33
S4	z3	z2	z0z1z3	20	36
S5	z3	z4z5	z0z1z2z3	15	33
S6	z5	z3	z0z1z2z5	19	39
S7	z4	z5	z0z1z2z3z4	28	36
S8	z5	z5	z0z1z2z3z5	23	33
S9	z4	z6	z0z2z2z3z5z4	24	33

Наряду с ручным счетом, решение задачи реализовано с помощью программного алгоритма, написанного на языке программирования Python версии 2.7.

Листинг программы представлен в приложении 1 (c. 35).

Для работы программа требует файл под названием “data” с исходными данными в следующем виде:

7 - кол-во элементов

0 3 5 7 1 8 0 - тау

-1 0 0 -1 -1 -1 -1 - матрица t

-1 -1 -1 10 -1 -1 -1

-1 -1 -1 -1 7 3 -1

-1 -1 -1 -1 12 -1 -1

-1 -1 -1 -1 -1 -1 0

-1 -1 -1 -1 -1 -1 -1

0 1 1 0 0 0 0 - матрица связей графа

0 0 0 1 0 0 0

0 0 0 0 1 1 0

0 0 0 0 1 0 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

Результат работы программы:

$ python main.py

Рисунок graph.png сохранен

Рисунок variant_tree.png сохранен

Построим z-размерную матрицу bij:

-∞ 0 0 -∞ -∞ -∞ -∞

-∞ -∞ -∞ 13 -∞ -∞ -∞

-∞ -∞ -∞ -∞ 12 8 -∞

-∞ -∞ -∞ -∞ 19 -∞ -∞

-∞ -∞ -∞ -∞ -∞ -∞ 1

-∞ -∞ -∞ -∞ -∞ -∞ 8

-∞ -∞ -∞ -∞ -∞ -∞ -∞

Определим более раннее время начала модуля zk.

Tn(z0) = 0

Tn(z1) = 0 + 0 = 0

Tn(z2) = 0 + 0 = 0

Tn(z3) = 0 + 13 = 13

Tn(z4) = 0 + 12 = 12

Tn(z4) = 13 + 19 = 32

max(Tn(z4)) = 32

Tn(z5) = 0 + 8 = 8

Tn(z6) = 32 + 1 = 33

Tn(z6) = 8 + 8 = 16

max(Tn(z6)) = 33

Определим длины путей, которые ведут от вершины zk к миноранте.

T(L*(z0)) = 0 + 0 + 3 + 10 + 7 + 12 + 1 + 0 = 33

T(L*(z0)) = 0 + 0 + 5 + 7 + 1 + 0 = 13

T(L*(z0)) = 0 + 0 + 5 + 3 + 8 + 0 = 16

max(T(L*(z0))) = 33

T(L*(z1)) = 3 + 10 + 7 + 12 + 1 + 0 = 33

T(L*(z2)) = 5 + 7 + 1 + 0 = 13

T(L*(z2)) = 5 + 3 + 8 + 0 = 16

max(T(L*(z2))) = 16

T(L*(z3)) = 7 + 12 + 1 + 0 = 20

T(L*(z4)) = 1 + 0 = 1

T(L*(z5)) = 8 + 0 = 8

T(L*(z6)) = 0

Полученные данные сведем в таблицу.

z τ Tn TL U t

z0 0 0 33 (0, 1) 0

z1 3 0 33 (0, 2) 0

z2 5 0 16 (1, 3) 10

z3 7 13 20 (2, 4) 7

z4 1 32 1 (2, 5) 3

z5 8 8 8 (3, 4) 12

z6 0 33 0 (4, 6) 0

(5, 6) 0

Оценки нижних границ:

S z N Y t* Tоц

S0 z0 12 0 0 33

S1 z1 23 01 3 33

S2 z2 15 02 5 38

S3 z2 35 012 8 33

S4 z3 2 013 20 36

S5 z3 45 0123 15 33

S6 z5 3 0125 19 39

S7 z4 5 01234 28 36

S8 z5 4 01235 23 33

S9 z4 6 012354 24 33

Рисунок solve_tree.png сохранен

Файл graph.png показан на рисунке 5.

Рисунок 5 – Автоматически построенный программой исходный граф

Файл varint_tree.png показан на рисунке 6.

Рисунок 6 – Автоматически построенный программой граф вариантов проведения проверок

Файл solve_tree.png показан на рисунке 7.

Рисунок 4 – Автоматически построенный программой граф решений

Вывод

Оптимальному процессу контроля соответствует следующая стратегия прохождения модулей {z0,z1,z2,z3,z4,z5,z6}. При этом общее время контроля составляет Т = 33 единицы.

Результаты ручного решения задачи идентичны результатм, полученным с помощью созданного программного алгоритма.

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

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

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

Рассмотрим две следующие задачи:

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

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

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

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

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

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

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

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

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

Тогда первая задача может быть сформулирована следующим образом.

Найти

(3.13)

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

(3.13)

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

Дано:

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

Таблица №5. Исходные данные

№ параметра	1	2	3	4	5
δизм/ δпар	0.3	0.2	0.4	0.1	0.5
ti	30	5	15	20	50

Таблица №6. Зависимость вероятности получения правильных результатов от величин δизм/ δпар для случая усреднения результатов n и повторных измерений .

δизм / δпар

0.3

0.2

0.4

0.1

0,5

0,99634

0,99775

0,99821

0,99846

0,99868

0,99879

0,99890

0,99895

0,99901

0,99909

0,99914

0,99918

0,99784

0,99859

0,99886

0,99901

0,99915

0,99923

0,99931

0,99933

0,99937

0,99942

0,99945

0,99948

0,99419

0,99669

0,99748

0,99785

0,99816

0,99833

0,99849

0,99859

0,99867

0,99876

0,99882

0,99887

0,99893

0,99930

0,99945

0,99955

0,9996

0,99963

0,99967

0,99970

0,99971

0,99973

0,99974

0,99975

0,99110

0,99533

0,99657

0,99714

0,99756

0,99780

0,99801

0,99818

0,99828

0,99839

0,99848

0,99854

Найти:

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

Суммарное время измерения контролируемых параметров не должно превышать 5 минут.
Достоверность результатов контроля данного объекта должна быть не менее 0.992.

Решение:

Работоспособность объекта характеризуется пятью параметрами, которые запишем в таблицу №7.

Таблица №7. Параметры, определяющие работоспособность объекта контроля

№ параметров

ti(c)

pi(1)

±0,2

±0,5

±5,0

±0,3

±0,1

±0,06

±0,10

±2,00

±0,03

±0,05

0.3

0.2

0.4

0.1

0.5

0,99634

0,99784

0,99419

0,99893

0,99110

Для каждого параметра вычисляется значение Ψi (ni) по формуле:

Постоянно выбирается наибольшее значение Ψi (ni).

Для n1 все Ψi (n1) равны нулю.

На основании таблицы №6 получим следующие значения:

Наибольшим является , поэтому далее вычислим

Следующим наибольшим является , поэтому далее вычислим

Все следующие действия выполнялись с помощью программного алгоритма.

Результат представлен в таблице № 8.

Таблица № 8

ni	Ψ1 (ni)	N	Ψ2 (ni)	N	Ψ3 (ni)	N	Ψ4 (ni)	N	Ψ5 (ni)	N
1	-	-	-	-	-	-	-	-	-	-
2	0.0000472	6	0.0001503	2	0.0001676	1	0.0000185	12	0.0000854	3
3	0.0000154	15	0.0000541	4	0.0000528	5	-		0.0000249	9
4	-		0.0000300	7	0.0000247	10	-	-	0.0000114	16
5	-		0.0000280	8	0.0000207	11	-	-	-	-
6	-		0.0000160	13	-	-	-	-	-	-
7	-		0.0000160	14	-	-	-	-	-	-

Цифры в графе N таблица №8 означают, на каком номере этапа должно быть добавлено одно повторное измерение i-го параметра.

Для каждого этапа по формулам:

последовательно вычислим значения P(N) и T(N), которые впишем в таблицу №9.

Таблица №9

N	n1	n2	n3	n4	n5	Р(N)	T(N)
1	1	1	2	1	1	0.98103	2 мин 15 сек
2	1	2	2	1	1	0.98176	2 мин 20сек
3	1	2	2	1	2	0.98595	3 мин 10сек
4	1	3	2	1	2	0.98622	3 мин 15сек
5	1	3	3	1	2	0.98700	3 мин 30сек
6	2	3	3	1	2	0.98840	4 мин 00сек
7	2	4	3	1	2	0.98855	4 мин 05сек
8	2	5	3	1	2	0.98869	4 мин 10сек
9	2	5	3	1	3	0.98992	5 мин 00сек
10	2	5	4	1	3	0.99029	5 мин 15сек
11	2	5	5	1	3	0.99059	5 мин 30сек
12	2	5	5	2	3	0.99096	5 мин 50сек
13	2	6	5	2	3	0.99104	5 мин 55сек
14	2	7	5	2	3	0.99112	6 мин 00сек
15	3	7	5	2	3	0.99158	6 мин 30сек
16	3	7	5	2	4	0.99214	7 мин 20сек

Оптимальным количеством повторных измерений контролируемых параметров для задачи, в которой суммарное время измерений не должно превышать 5 минут, является следующий набор: n1=2, n2=5, n3=3, n4=1, n5=3, при этом максимальная достоверность результатов равна 0.98992, а суммарное измерение равно 5 мин 00сек.
Оптимальным количеством повторных измерений контролируемых параметров для задачи, в которой достоверность результатов контроля должна быть не менее 0.992 является следующий набор: n1=3, n2=7, n3=5, n4=2, n5=4, при этом достоверность результатов контроля равна 0.99214, а суммарное время измерения равно 7 мин 20сек.

Таким образом, заданным ограничениям удовлетворяют по времени набор параметров, соответствующих строке 9, по достоверности – 16 в таблице №9.

Наряду с ручным расчетом, решение задачи реализовано с помощью программного алгоритма, написанного на языке Python версии 2.7. Листинг программы представлен в приложении 2 (c. 53).

Результат работы программы:

$ python main2.py

N n Ψ max

1 2 3 0.00016764

2 2 2 0.00015032

3 2 5 0.00008536

4 3 2 0.00005408

5 3 3 0.00005284

6 2 1 0.00004717

7 4 2 0.00003003

8 5 2 0.00002803

9 3 5 0.00002492

10 4 3 0.00002473

11 5 3 0.00002071

12 2 4 0.00001852

13 6 2 0.00001601

14 7 2 0.00001601

15 3 1 0.00001537

16 4 5 0.00001144

N n1 n2 n3 n4 n5 P(N) T(N)

1 1 1 2 1 1 0.98103 2 мин 15сек

2 1 2 2 1 1 0.98176 2 мин 20сек

3 1 2 2 1 2 0.98595 3 мин 10сек

4 1 3 2 1 2 0.98622 3 мин 15сек

5 1 3 3 1 2 0.98700 3 мин 30сек

6 2 3 3 1 2 0.98840 4 мин 0сек

7 2 4 3 1 2 0.98855 4 мин 5сек

8 2 5 3 1 2 0.98869 4 мин 10сек

9 2 5 3 1 3 0.98992 5 мин 0сек

10 2 5 4 1 3 0.99029 5 мин 15сек

11 2 5 5 1 3 0.99059 5 мин 30сек

12 2 5 5 2 3 0.99096 5 мин 50сек

13 2 6 5 2 3 0.99104 5 мин 55сек

14 2 7 5 2 3 0.99112 6 мин 0сек

15 3 7 5 2 3 0.99158 6 мин 30сек

16 3 7 5 2 4 0.99214 7 мин 20сек

n Ψ1(ni) Ψ2(ni) Ψ3(ni) Ψ4(ni) Ψ5(ni)

1 --------- --------- --------- --------- ---------

2 0.0000472 0.0001503 0.0001676 0.0000185 0.0000854

3 0.0000154 0.0000541 0.0000528 --------- 0.0000249

4 --------- 0.0000300 0.0000247 --------- 0.0000114

5 --------- 0.0000280 0.0000207 --------- ---------

6 --------- 0.0000160 --------- --------- ---------

7 --------- 0.0000160 --------- --------- ---------

Вывод

Спроектированная таким образом система автоматизированного контроля удовлетворяет требуемой достоверности результатов контроля и времени проведения проверок.

Результаты ручного решения задачи идентичны результатам, полученным с помощью созданного программного алгоритма.

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

Пискунов В.А. Курс лекций и лабораторных работ по дисциплине “Контроль и диагностика систем ЛА”.
Пискунов В.А. Учебное пособие “Комбинаторные методы дискретной оптимизации в прикладных задачах организации контроля систем ЛА”.

Приложение 1

Листинг программы на языке Python 2.7

# -*- coding: utf-8 -*-

import sys

import copy

import matplotlib.pyplot as plt

import networkx as nx

solve_table = ''

S = 0

class Node:

"""Узел графа"""

def __init__(self, number, tau=0):

self.number = number # номер узла

self.tau = tau # вес узла

self.Toc = 0

self.childs = [] # узлы-потомки

self.childs_numbers = [] # номер узлов-потомков

self.parents = [] # узлы-родители

self.parents_numbers = [] # номера узлов-родителей

def set_child(self, child): # mass - это t между узлами

"""Добавить к узлу потомков"""

#TODO добавить проверку типа

self.childs.append(child) # добавляем потомка

self.childs_numbers.append(child.number) # добавляем номер потомка

child.set_parent(self) # добавляем потомку родителя

def del_childs(self):

self.childs = []

self.childs_numbers = []

def set_parent(self, parent):

"""Добавить к узлу родителя"""

#TODO добавить проверку типа

self.parents.append(parent) # Добавляем родителя

self.parents_numbers.append(parent.number) # Добавляем номер родителя

def display_graph(graph):

"""Выводит граф на экран"""

for node in graph:

sys.stdout.write(

"Number: " + str(node.number) + "\tTau: " + str(node.tau))

sys.stdout.write("\tParents:")

if len(node.parents):

for parent in node.parents:

sys.stdout.write("\t\t", parent.number)

else:

sys.stdout.write("\t\tNone")

sys.stdout.write("\tChilds:")

if len(node.childs):

for child in node.childs:

sys.stdout.write("\t\t", child.number)

else:

sys.stdout.write("\t\tNone")

def draw_graph(graph):

gr = nx.Graph()

for i in graph:

for j in i.childs:

gr.add_edge(str(i.number), str(j.number))

pos = nx.spring_layout(gr)

colors = range(20)

nx.draw(gr, pos, node_size=700, node_color='#A0CBE2', width=4,

edge_cmap=plt.cm.Blues, with_labels=True)

file_name = "graph.png"

plt.savefig(file_name) # save as png

sys.stdout.write('Рисунок ' + file_name + ' сохранен\n')

# plt.show() # display

def make_tree(graph):

"""Функция для построения дерева"""

tree = Node(0)

tree.set_parent(Node(0))

make_next_node(tree, graph)

return tree

def make_next_node(tree, graph):

"""Рекурсивная функция для вычисления потомков узла"""

possible_next_nodes = copy.copy(

graph) # с самого начала все узлы могут быть следующими

for i in tree.parents_numbers:

possible_next_nodes[i] = None # отсекаем уже использованные узлы

for possible_node in range(len(possible_next_nodes)): # цикл по всем возможным следующим узлам

if possible_next_nodes[possible_node] is not None:

for parents_number in possible_next_nodes[possible_node].parents_numbers: # цикл по всем родителям узла

if not parents_number in tree.parents_numbers: # если родитель узла еще не был в дереве, то мы этот узел пока использовать не можем

possible_next_nodes[possible_node] = None

break # если хотя бы одного родителя нет, то дальше и проверять не стоит

for possible_node in range(len(possible_next_nodes)): # цикл по всем возможным следующим узлам

if possible_next_nodes[possible_node] is not None:

tree.set_child(Node(possible_node))

for child in tree.childs: # добавим каждому потомку родителей родителя

child.parents = copy.copy(tree.parents)

child.parents_numbers = copy.copy(tree.parents_numbers)

child.set_parent(

Node(child.number)) # не забываем добавить самого себя

for child in tree.childs:

make_next_node(child, graph) # рекурсивно пробегаем по всем потомкам

def display_tree(tree, tab=0):

"""Функция вывода дерева"""

sys.stdout.write(tab * '\t' + str(tree.number) + '\n')

for i in tree.childs:

display_tree(i, tab + 1) # чем глубже рекурсия - тем шире табуляция

def draw_tree(count, tree, with_Toc=False):

tr = nx.Graph()

add_edge_to_tree(count, tree, tr, with_Toc)

pos = nx.spring_layout(tr)

colors = range(20)

nx.draw(tr, pos, node_size=200, node_color='#A0CBE2', width=2,

edge_cmap=plt.cm.Blues, with_labels=True)

if with_Toc:

file_name = 'solve_tree.png'

else:

file_name = 'variant_tree.png'

plt.savefig(file_name) # save as png

sys.stdout.write('Рисунок ' + file_name + ' сохранен\n')

# plt.show() # display

def list_to_str(list):

"""Функция принимает список и возвращает строку, созданную из списка"""

string = ''

for i in list:

string += str(i)

return string

def add_edge_to_tree(count, node, tr, with_Toc):

if node.childs_numbers:

for child in node.childs:

if len(child.parents_numbers) != count: # не будем рисовать последний узел

if with_Toc:

node_name = 'Z' + str(node.number) + ' ' + list_to_str(

node.parents_numbers) + ' (' + str(node.Toc) + ')'

child_name = 'Z' + str(child.number) + ' ' + list_to_str(

child.parents_numbers) + ' (' + str(child.Toc) + ')'

else:

node_name = list_to_str(node.parents_numbers)

child_name = list_to_str(child.parents_numbers)

tr.add_edge(node_name, child_name)

add_edge_to_tree(count, child, tr, with_Toc)

def read_data_from_file(file_name):

"""Функция чтения вводных данных из файла"""

data = open(file_name)

count = int(data.readline()[0])

# первая строка файла должна содержать кол-во элементов

tau = [int(x) for x in data.readline().split()[:count]]

data.readline() # пропускаем пустую строку

t = []

for i in xrange(count):

t.append([int(x) for x in data.readline().split()[:count]])

data.readline() # пропускаем пустую строку

link = []

for i in xrange(count):

link.append([int(x) for x in data.readline().split()[:count]])

graph = []

for i in xrange(count):

graph.append(Node(i, tau[i]))

for i in xrange(count):

for j in xrange(count):

if link[i][j]:

graph[i].set_child(graph[j])

data.close()

return count, graph, t, tau

def calculate_b(count, tau, t):

b = [-1] * count # матрица для b. TODO найти более элегантное решение для заполнения матрицы

for i in range(count):

b[i] = [-1] * count

for i in xrange(count):

for j in xrange(count):

if t[i][j] >= 0:

if i < j:

b[i][j] = tau[i] + t[i][j]

return b

def display_b(b):

sys.stdout.write("Построим z-размерную матрицу bij:\n")

for i in range(len(b)):

for j in b[i]:

if j == -1:

temp = "-∞"

else:

temp = str(j)

sys.stdout.write(temp + '\t')

sys.stdout.write("\n")

def calculate_Tn(count, graph, tau, t, b):

sys.stdout.write("Определим более раннее время начала модуля zk.\n")

Tn = []

for i in xrange(count):

temp = []

if i == 0:

sys.stdout.write("Tn(z%d) = 0\n" % i)

Tn.append(0)

continue

for parent in graph[i].parents:

temp.append(Tn[parent.number] + b[parent.number][i])

sys.stdout.write("Tn(z%d) = %d + %d = %d\n" % (i, Tn[parent.number], b[parent.number][i], Tn[parent.number] + b[parent.number][i]))

if len(temp) > 1:

sys.stdout.write("max(Tn(z%d)) = %d\n" % (i, max(temp)))

Tn.append(max(temp))

sys.stdout.write("\n")

return Tn

def calculate_TL(count, graph, tau, t):

sys.stdout.write(

"Определим длины путей, которые ведут от вершины zk к миноранте.\n")

TL = []

for x in xrange(count):

temp = []

generate_path(

graph[x], [], temp) # находим все пути от узла i до последнего узла

all_TL = []

for i in temp: # находим max

sys.stdout.write("T(L*(z%d))" % x)

sum_path = 0

for j in xrange(len(i)):

if i[j] != count - 1:

if j != 0:

sys.stdout.write(" + ")

else:

sys.stdout.write(" = ")

sum_path += tau[i[j]] # сумма всех узлов

sum_path += t[i[j]][i[j + 1]]

#прибавляем веса связей между узлами

sys.stdout.write(

"%d + %d" % (tau[i[j]], t[i[j]][i[j + 1]]))

else:

sys.stdout.write(" = %d\n" % sum_path)

all_TL.append(sum_path)

TL.append(max(all_TL)) # находим максимальное

if len(all_TL) > 1:

sys.stdout.write("max(T(L*(z%d))) = %d\n" % (x, max(all_TL)))

sys.stdout.write("\n")

return TL

def generate_path(node, path, temp):

path.append(node.number)

if len(node.childs):

for child in node.childs:

generate_path(child, copy.copy(path), temp)

else:

temp.append(path)

def display_data_table(count, tau, Tn, TL, t):

sys.stdout.write('Полученные данные сведем в таблицу.\n')

sys.stdout.write('z\tτ\tTn\tTL\tU\tt\n')

U = []

t_temp = []

for i in range(len(t)):

for j in range(len(t[i])):

if t[i][j] != -1:

U.append((i, j))

t_temp.append(t[i][j])

for i in range(len(U)):

if i > len(tau) - 1:

sys.stdout.write("\t\t\t\t%s\t%d\n" % (str(U[i]), t_temp[i]))

else:

sys.stdout.write("z%d\t%d\t%d\t%d\t%s\t%d\n" % (i, tau[

i], Tn[i], TL[i], str(U[i]), t_temp[i]))

sys.stdout.write('\n')

def make_solve_tree(count, tree, Tn, TL, tau, t):

global solve_table

solve_table += 'S\tz\tN\tY\tt*\tTоц\n'

solve_tree = copy.copy(tree)

add_Toc_to_node(count, solve_tree, Tn, TL, tau, t)

recursive_make_solve_tree(

count, tree, Tn, TL, tau, t, solve_tree)

return solve_tree

def recursive_make_solve_tree(count, tree, Tn, TL, tau, t, solve_tree):

solve_tree.childs = copy.copy(tree.childs)

solve_tree.childs_numbers = copy.copy(tree.childs_numbers)

if len(solve_tree.childs) == 0:

return

for child in solve_tree.childs:

add_Toc_to_node(count, child, Tn, TL, tau, t)

temp = {}

for child in solve_tree.childs:

temp[child.Toc] = child.number

for child in solve_tree.childs:

if child.number == temp[min(temp.keys())]: # если у потомка наименьший Toc

for child_of_tree in tree.childs:

if child_of_tree.number == temp[min(temp.keys())]: # находим такой же потомок у главного дерева

recursive_make_solve_tree(count, child_of_tree,

Tn, TL, tau, t, child)

else:

child.del_childs()

def add_Toc_to_node(count, node, Tn, TL, tau, t):

if len(node.parents_numbers) == count:

return

t_star = 0

for i in xrange(len(node.parents_numbers)):

t_star += tau[node.parents_numbers[i]] # сумма всех узлов

if i < len(node.parents_numbers) - 1:

if t[node.parents_numbers[i]][node.parents_numbers[i + 1]] >= 0:

t_star += t[node.parents_numbers[i]][node.parents_numbers[

i + 1]] # прибавляем веса связей между узлами

temp = {}

for child in node.childs:

q = TL[child.number]

if t_star < Tn[child.number]:

q += Tn[child.number] - t_star

temp[q] = child.number

node.Toc = max(temp.keys()) + t_star

global solve_table

global S

solve_table += "S" + str(S) + '\t' + "z" + str(node.number) + '\t' + list_to_str(node.childs_numbers) + '\t' + list_to_str(node.parents_numbers) + '\t' + str(t_star) + '\t' + str(node.Toc) + "\n"

S += 1

def main():

count, graph, t, tau = read_data_from_file("data")

# draw_graph(graph)

# первый этап

tree = make_tree(graph)

# display_tree(tree)

# draw_tree(count, tree)

#второй этап

b = calculate_b(count, tau, t)

display_b(b)

#третий этап

Tn = calculate_Tn(count, graph, tau, t, b)

#четвертый этап

TL = calculate_TL(count, graph, tau, t)

display_data_table(count, tau, Tn, TL, t)

#пятый этап

solve_tree = make_solve_tree(count, tree, Tn, TL, tau, t)

global solve_table

sys.stdout.write("Оценки нижних границ:\n")

sys.stdout.write(solve_table)

# display_tree(solve_tree)

draw_tree(count, solve_tree, True)

if __name__ == '__main__':

main()

Приложение 2

Листинг программы на языке Python 2.7

# -*- coding: utf-8 -*-

import sys

import copy

sigma_default = [0.1, 0.2, 0.3, 0.4, 0.5]

p_default = [

[0.99893, 0.99930, 0.99945, 0.99955, 0.99960, 0.99963, 0.99967, 0.99970, 0.99971,

0.99973, 0.99974, 0.99975],

[0.99784, 0.99859, 0.99886, 0.99901, 0.99915, 0.99923, 0.99931, 0.99933, 0.99937,

0.99942, 0.99945, 0.99948],

[0.99634, 0.99775, 0.99821, 0.99846, 0.99868, 0.99879, 0.99890, 0.99895, 0.99901,

0.99909, 0.99914, 0.99918],

[0.99419, 0.99669, 0.99748, 0.99785, 0.99816, 0.99833, 0.99849, 0.99859,

0.99867, 0.99876, 0.99882, 0.99887],

[0.99110, 0.99533, 0.99657, 0.99714, 0.99756, 0.99780, 0.99801, 0.99818,

0.99828, 0.99839, 0.99848, 0.99854]]

def get_p(sigma):

p = [[] for i in sigma]

for i in range(len(sigma)):

p[i] = p_default[sigma_default.index(sigma[i])]

return p

def get_psi(i, j, p, t):

a = p[j][i]

if i == 0:

b = 0

else:

b = p[j][i - 1]

try:

return (a - b) / (b * t[j])

except ZeroDivisionError:

return -1

def get_table_psi(p, t):

table_psi = []

for i in range(len(p[0])):

table_psi.append([0 for x in t])

for j in range(len(t)):

table_psi[i][j] = get_psi(i, j, p, t)

return table_psi

def get_max_value(list):

max_value = 0

i_max = 0

j_max = 0

for i in range(len(list)):

for j in range(len(list[i])):

if list[i][j] > max_value:

max_value = list[i][j]

i_max = i

j_max = j

return i_max, j_max

def list_to_str(list):

s = ''

for i in list:

s += str(i) + "\t"

return s

def get_max_table(p, t, psi):

count = 1

multi = 1

for i in p:

multi *= i[0]

P = [multi]

T = [sum(t)]

temp_table = []

max_table = [[1 for i in psi[0]]]

temp = []

sys.stdout.write("N\tn\tΨ\tmax\n")

for i in range(len(psi)):

temp_table.append(copy.copy(psi[i]))

a = get_max_value(temp_table)[0]

b = get_max_value(temp_table)[1]

if temp_table[a][b] == -1:

continue

sys.stdout.write(

"%d\t%d\t%d\t%2.8f\n" % (count, a + 1, b + 1, temp_table[a][b]))

temp.append(temp_table[a][b])

count += 1

temp_table[a][b] = 0

max_table[-1][b] += 1

max_table.append(copy.copy(max_table[-1]))

P.append(P[-1] * p[b][a] / p[b][a - 1])

T.append(T[-1] + t[b])

while P[-1] < 0.992 and T[-1] < 600:

a = get_max_value(temp_table)[0]

b = get_max_value(temp_table)[1]

if temp_table[a][b] == -1:

continue

sys.stdout.write(

"%d\t%d\t%d\t%2.8f\n" % (count, a + 1, b + 1, temp_table[a][b]))

temp.append(temp_table[a][b])

count += 1

temp_table[a][b] = 0

max_table[-1][b] += 1

max_table.append(copy.copy(max_table[-1]))

P.append(P[-1] * p[b][a] / p[b][a - 1])

T.append(T[-1] + t[b])

sys.stdout.write("\n")

sys.stdout.write("N\tn1\tn2\tn3\tn4\tn5\tP(N)\t\tT(N)\n")

for i in range(len(max_table) - 1):

sys.stdout.write("%d\t%s%4.5f\t\t%d мин %dсек\n" % (

i + 1, list_to_str(max_table[i]), P[i + 1], T[i + 1] / 60, T[i + 1] % 60))

sys.stdout.write("\n")

sys.stdout.write('n\tΨ1(ni)\t\tΨ2(ni)\t\tΨ3(ni)\t\tΨ4(ni)\t\tΨ5(ni)\n')

for i in range(len(p[0])):

sys.stdout.write("%d\t" % (i + 1))

for j in range(len(t)):

if psi[i][j] == -1 or psi[i][j] not in temp:

sys.stdout.write('---------\t')

else:

sys.stdout.write('%4.7f\t' % psi[i][j])

sys.stdout.write("\n")

def main():

sigma = [0.3, 0.2, 0.4, 0.1, 0.5]

t = [30, 5, 15, 20, 50]

p = get_p(sigma)

psi = get_table_psi(p, t)

get_max_table(p, t, psi)

if __name__ == '__main__':

main()

1. Работа электрических органов рыб
2. Организация и тактика тушения пожаров во Дворце искусств
3. Тема 5. Патентная система налогообложения 1
4. Система городского хозяйства
5. Гидрология (шпаргалка)
6. кезе~ со~ында~ы стылма~ан дайын ~нім ~алды~тары
7. Роман Лазурко Роман Лазурко На шляхах Европи Вступне слово Історія це скарбниця досвіду
8. на тему- Учет готовой продукции и ее реализация Выполнила- студентка заочного отдел
9. Тема- Производительность труда на АТ
10. Иностранные инвестиции
11. Реферат- Общение как форма межличностных отношений
12. ТЕМА- ПРАВОВАЯ И ДЕОНТОЛОГИЧЕСКАЯ ОЦЕНКА ВРАЧЕБНЫХ ОШИБОК И НЕСЧАСТНЫХ СЛУЧАЕВ В МЕДИЦИНЕ.
13. Эпоха Средневековья в философско-исторических работах ЛПКарсавина
14. Гефест Капитал по Югу России
15. реферату- Облік валових витрат і валових доходівРозділ- Бухгалтерський облік оподаткування Облік валових.html
16. ru Соглашение об использовании Материалы данного файла могут быть использованы без ограничений
17. Nme- fmily nme first nme 2
18. 1 Современные концепции генезиса надобщинных структур и образования протогосудасртв
19. Библиотечномузейное объединение План проведения новогодних мероприятий
20. Сны и сновидения в русской литературе

Материалы собраны группой SamZan и находятся в свободном доступе