Курсовая работа по «Техническому контролю и диагностике систем ЛА»

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

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

 

Факультет №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

 

 

 

 

 

 

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

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

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

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

(1.1)

при ограничениях

(1.2)

x_j {0;1},  j=1,…,n,                                      (1.3)

причем p_j ≥0, c_j≥0.

Решение задачи может быть получено с помощью метода ветвей и границ.

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

Эффективность вычислительных алгоритмов зависит от точности и простоты способа  определения верхней границы  возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.

Рассмотрим алгоритм решения задачи (1.1) — (1.3) методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой  функции.

Множество U переменных x_j рассматривается как три множества.

S -множество фиксированных переменных, вошедших в допустимое решение; E_s — множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство

G_S — множество свободных переменных, из которых производится выбор для включения в S очередной переменной.

Обозначим h_1j = p_j/c_j и допустим, что x_j S (j= 1, . .., k < п), вычисляется указанное отношение и параметры номеруются (ранжируются) в соответствии с ранжировкой: 

h_1,k+1 ≥h_1,k+2≥ ...≥h_1l, l≤n,                                                                                             (1.4)

(1.5)

(1.6)

Условия (1.5), (1.6) означают, что в множество S без нарушения неравенства (1.2) можно дополнительно ввести элементы х_к+1, х_{к +2},..., х_l-1. При введении в множество S элементов х_к+1, х_{к +2},..., х_l неравенство (1.2) не выполняется.

Для определения верхней границы  решения может быть использовано 
выражение:

                                                                                                                        (1.7)

где

                                                                                                                      (1.8)

(1.9)

Из условий (1.1)-(1.3)  следует, что L'_s не меньше максимального значения величины

при ограничениях

 

Поясним процесс определения L'_S графиком (рис. 1.1). Строим кусочнолинейную функцию L(с) с убывающим значением градиента h. Вычисляем с'₁ и по графику находим L'_S.

Выбор очередной переменной для  включения в множество S производится с помощью условия:

                                                                                                                     (1.10)

Для выбранной переменной х_r определяются величины Р_S(x_r) и Р_S( x_r), т.е. в S включается х_r = 1   или   х_r = 0.

Если в процессе решения окажется, что в множестве G_S нет элементов, которые могут быть введены в множество S без нарушения ограничения (1.5), то полученное решение принимается в качестве первого приближенного решения L₀.

Все вершины дерева возможных вариантов, для которых выполняются условия Q_S ≤ L₀ из дальнейшего рассмотрения исключаются.

Из оставшихся ветвей выбирается ветвь  с максимальным значением Р_S, и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено , то полученное решение принимается в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для всех оставшихся ветвей выполняется условие Р_S ≤ L₀.

 

 

 

 

 

 

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

Дано:

Нормированные вероятности отказов для элементов  Q_i, затраты на контроль i-ого параметра C(x_i).

№	1	2	3	4	5	6	7	8	9	10
Qi	0,04	0,15	0,13	0,08	0,02	0,09	0,06	0,08	0,03	0,04
C(xi)	5	1	4	2	6	3	2	3	1	1

 

Найти:  Выбрать такие параметры, чтобы C≤18 при Q=Q_max.

Решение:

Для удобства расчетов проранжируем таблицу 4 в порядке убывания и присвоим новые номера элементам, следующим образом:

№(нов.)	1	2	3	4	5	6	7	8	9	10
№(стар.)	2	4	10	3	6	7	9	8	1	5
Qi	0,15	0,08	0,04	0,13	0,09	0,06	0,03	0,08	0,04	0,02
C(xi)	1	2	1	4	3	2	1	3	5	6
hi	0,15	0,04	0,04	0,0325	0,03	0,03	0,03	0,0267	0,008	0,0033

 

Значение  l определяет сумма q₁+ q₂+ q₃+ q₄+ q₅+ q₆+ q₇ + q₈ =17, отсюда l=9

при l = 9,  , ,

 

 

 

Первый  шаг

Выбор очередной переменной для включения в множество S производится с помощью условия: ,

x_r = x₁,

 

= 0.06 + 0.09 + 0.04 + 0.15 + 0.07 + 0.17 + 0.03 + 0.026*2 =0.662;

 

 

= = 0 + 0.09 + 0.04 + 0.15 + 0.07 + 0.17 + 0.03 + 0.026*3 = =0.628;

 

= 18 – 1 = 17;

 

Второй  шаг

 

x₁ S  , E_s = ø, x_j G_s (j = 2,…,10), Р_S (x₁) =0.662

Выбираем очередную  переменную:

x_r = x₂,

= (0.06 + 0.09) + (0.04 + 0.15 + 0.07 + 0.17 + 0.03) + 2*0.026 = 0.15 + 0.46 + 0.052 = 0.662;

18 – 13 – 1 =  4

= = 0.06 + 0.46 + 4*0.026 = 0.104 + 0.06 + 0.46 = 0.624

 

= 18 – 3 = 15;

 

Третий  шаг

 

x₁, x₂ S  , E_s = ø, x_j G_s (j = 3,…,10), P_S (x₂) =0.662

 

Выбираем очередную  переменную:

 

x_r = x₃,

 

= 0.662

 

 

= = (0.06 + 0.09) + (0.15 + 0.07 + 0.17 + 0.03) + 3*0.026 = 0.15 + 0.42 + 0.078 = 0.648;

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Математически задачу выбора набора параметров из заданной их совокупности можно сформулировать следующим образом.

Пусть работоспособность  объекта контроля характеризуется  совокупностью n взаимосвязанных параметров. Образующих множество S={x₁, x₂,…,x_n}. Проверка всех параметров из S влечет контроль всех N элементов системы и дает однозначный ответ: объект исправен, если все N элементов исправны, или неисправен. Если по крайней мере один из элементов отказал. Для x_i определено подмножество R(x_i) элементов, проверяемых при контроле i-ого параметра. Причем предполагается, что эти подмножества могут пересекаться, т.е. i, j: R(x_i) ∩ R(x_j).

Пусть Ω –  некоторый набор параметров из множества  S, т.е. . Тогда и , где Ω-набор контролируемых параметров, а - неконтролируемый набор. Значение  из S можно представить булевым вектором, причем:

1, если x_i

0. если x_i

  x_i=

 

Задача выбора параметров в этом случае формулируется  двояко:

1. Найти набор, для которого

Р(Ω)=max                                                                                                                                  (1.11)

при

 

2. Найти набор Ω. Для которого: 

(1.12)

при

где - апостериорная вероятность работоспособного состояния объекта контроля при положительном исходе контроля выбранных параметров ;