Контроль и диагностика систем

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 01.12.2009
Размер файла 508,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

29

Московский Авиационный Институт

(государственный технический университет)

КУРСОВАЯ РАБОТА

ПО КУРСУ: «кОНТРОЛЬ И ДИАГНОСТИКА СИСТЕМ»

ВАРИАНТ №7

Москва 2009 г.

Содержание

  • Задание
  • Теоретическая часть
    • Метод ветвей и границ
    • Метод наискорейшего спуска
  • Практическая часть
    • Задача №1
    • Задача №2
  • Задание
  • Определение последовательности проведения проверок с использованием метода ветвей и границ, и количества повторных измерений методом наискорейшего спуска при ограничении на время проверок.
  • Дано:
  • 1. Граф исходного множества модулей и таблицы длительности операций.

29

№ вершины

Z1

Z2

Z3

Z4

Z5

Длительность, фi

2

4

5

3

8

Дуги

1-3

2-4

2-5

3-4

Длительность, tij

15

12

3

7

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

№ параметра

1

2

3

4

5

уИЗМПАР

0.1

0.3

0.5

0.2

0.4

ti

20

30

15

50

5

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

Метод ветвей и границ

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

Идея этого метода заключается в следующем. Множество W(S0) всех допустимых вариантов решения у разбивается на непересекающиеся подмножества W(Sk), которые, в свою очередь, разбиваются на подмножества меньшей мощности W(Sl) до получения подмножества W(Sv), состоящего из единственного варианта. Процесс разбиения множества допустимых вариантов W(S0) на их непересекающиеся подмножества называется ветвлением вариантов, а получаемое при этом дерево - деревом решений. Каждой вершине дерева ветвления соответствует некоторый модуль из графа, а любой путь по дереву определяет соответствующий граф очередности. Множество вершин описывает определенный вариант процесса.

Пусть Y(Sk) - множество вершин в графе очередности D, соответствующих пути от S0 до Sк в дереве Е. из каждой вершины Sк выходит столько ветвей, сколько допустимых модулей (претендентов упорядочения) имеется в подмножестве Z\ Y(Sk). Множество допустимых на каждом шаге процесса ветвления модулей образует фронт упорядочения. Наглядное представление об образовании фронта упорядочения дает преобразованный в соответствии с формулой (1.1) граф G

F(zl) = max[f(zi) + til] (1.1)

zi>zj

Очевидно, на первом шаге процесса построения дерева Е фронт упорядочения образуют вершины, которые соединены с мажорантой одной дугой, на втором шаге к ним добавляются все последователи включенной в D вершины, в которую не входят дуги из других вершин и т.д. На произвольном шаге фронт упорядочения образуют модули, для которых Г0-1zi = Ш.

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

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

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

На основе исходной информации, заданной графом G, построим

¦Z¦- размерные матрицы, такие что

фi + tij, если (i,j) принадлежит U

bij = (1.2)

- ?, если (i,j) не принадлежит U

tij + фi, если (i,j) принадлежит U

dij = (1.3)

- ?, если (i,j) не принадлежит U

Введем следующие понятия:

а) наиболее раннее время начала модуля

Тн(Zк) = max { Тн(Zi) + bik}, Тн(Z0) = 0 (1.4)

0< i ? k

б) критический путь - самый длинный путь, ведущий от мажоранты графа к миноранте, причем за длину любого пути принимается сумма длительностей фi для всех модулей и всех задержек tij , входящих в этот путь.

Обозначим H = {Lij} - множество всех независимых путей на графе (путей, отличающихся друг от друга хотя бы одной дугой), ведущих от вершины zi к zj, и H' = {Lk}є H - множество всех независимых путей, ведущих от вершины zk к миноранте. Тогда такой путь представляет собой частичный подграф GL = (ZL, UL), длина которого равна:

T(L) = ? фk + ? tkl (1.5)

k:zk є ZL (k,l) є UL

Длина критического пути может быть вычислена из рекуррентной формулы:

Ткр = t(L0*) = max {t(L0)}= ф0 + max {t0,j + t(Lj*)} (1.6)

L0єH'

j:zjєГz0

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

k ? t(L0*) и (V R)[tk?Tk(zk)] (1.7)

k:zk є Z

где tk - время завершения к-го модуля, определяемое из полученного решения D.

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

N(Sk) = {zi¦zi є Z, Г-1zi є Y(Sk)} (1.8)

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

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

Тоц(Sk) = t*(Sk) + max {t(Li*) + max [0, Тн(zi) - t*(Sk)]} (1.9)

i:zj є N(Sk)

где t*(Sk) = max{ti¦i:zi є Y(Sk)}

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

Тоц(Sk*) = min{ Тоц(Sk)¦Sk є S*} (1.10)

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

S* = {Si¦Si:¦?Si¦<¦N(Si)¦} (1.11)

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

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

t*(Sн) ? min{ Тоц(Sk)¦ Skє S*}. (1.12)

если (12) не выполняется, то поиск оптимального решения продолжается из вершины, имеющей наименьшую из оценок Тоц(Sk*).

Метод наискорейшего спуска

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

Рассмотрим задачу:

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

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

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

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

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

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

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

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

Тогда задача формулируется: найти

(2.1)

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

(2.2)

контролируемые параметры независимы.

Р(N) - достоверность результатов контроля на N-ом этапе процесса решения;

Т(N) - суммарное время измерения всех контролируемых параметров на N-ом этапе процесса решения.

Сущность метода заключается в следующем. Берется исходный состав контролируемых параметров, которые определяют работоспособность объекта, и для них вычисляются значения достоверности контроля Р(1) и суммарное время измерения этих параметров Т(1) при однократных измерениях (индекс “1” означает отсутствие повторения измерений)

(2.3)

(2.4)

вычисляем

шi(ni) = (pi(ni) - pi(ni - 1)) / (pi(ni - 1) ti) (2.5)

Затем на первом этапе процесса решения последовательно для всех контролируемых параметров (i = 1, 2, ... , m) вычисляются значения Рi(2) (вероятность получения правильного результата по всем контролируемым параметрам при условии, что i-й параметр измеряется двукратно) и Тi(2) (суммарное время измерения всех контролируемых параметров при условии, что i-й параметр измеряется двукратно)

Pi(2) = p1(1) p2(2) ... pi-1(1) pi(2) pi+1(1) ... pm(1) (2.6)

Ti(2) = t1 + t2 + ... + ti-1 + 2ti + ti+1 + ... + tm (2.7)

Далее для всех контролируемых параметров на первом этапе вычисляются значения относительного приращения достоверности результатов, в зависимости от приращения суммарного времени измерения.

шi(2) = шi(2) P(1) (2.8)

Среди величин шi(2) требуется найти наибольшую. Однако нетрудно заметить, что наибольшей величине шi(2) соответствует и наибольшая величина шi(2), так как они отличаются между собой лишь на постоянный множитель Р(1). Пусть, например, наибольшей оказалась величина шs(2). Это означает, что на первом этапе процесса решения задачи повторно следует измерить s-й параметр.

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

P(2) = (ps(2)/ps(1)) P(1) (2.9)

а суммарное время измерения всех m параметров значением

T(2) = T(1) + ts (2.10)

На втором шаге исходными значениями уже являются Р(2) и Т(2). Теперь для всех параметров аналогичным образом должны быть вычислены значения Pi(3) и Ti(3) при условии, что к общему количеству измерений, которое стало равно (m+1) (m однократных плюс одно повторное измерение), добавлено еще одно измерение. Затем вычисляются значения шi(3). Пусть наибольшей из этих величин оказалось шr(3). Это означает, что на втором этапе процесса решения повторно следует измерить r-й параметр. Однако наибольшей может оказаться величина шs(3) с тем же индексом, что и на первом этапе процесса, т.е. может оказаться, что следует произвести еще одно повторное измерение s-го параметра, ни производя, ни одно повторное измерение других параметров.

Подобный процесс решения задачи продолжается до тех пор пока:

Т(N) ? T0 < T(N+1) (2.11)

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

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

Задача №1

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

29

Рис 1.1. Исходный граф.

Таблица1.1.

№ вершины

Z1

Z2

Z3

Z4

Z5

Длительность, фi

2

4

5

3

8

Таблица1.2

Дуги

1-3

2-4

2-5

3-4

Длительность, tij

15

12

3

7

Найти: последовательность проведения проверок методом ветвей границ.

Решение:

1. Найдем наиболее раннее время начала модуля Zk:

Тн(Zк) = max { Тн(Zi) + bik}, Тн(Z0) = 0

Тн(Z0) = 0

Тн(Z1) = 0

Тн(Z2) = 0

Тн(Z3) = 2+15 = 17

Тн(Z4) = 4+12 = 16 или Тн(Z4) = 2+15+5+7 = 29 тогда maxТн(Z4) = 29

Тн(Z5) = 4+3 = 7

Тн(Z6) = 4+3+8 = 15 или Тн(Z6) = 2+15+5+7+3 = 32 или Тн(Z6) = 4+12+3 = 19 тогда maxТн(Z6) =32

2. Найдем длину критического пути T(L):

T(L*( Z0)) = 0+2+15+5+7+3 = 32

T(L*( Z1)) = 0+2+15+5+7+3 = 32

T(L*( Z2)) = 0+4+12+3 = 19

T(L*( Z3)) = 0+5+7+3= 15

T(L*( Z4)) = 0+3= 3

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

T(L*( Z6)) = 0

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

Таблица 1.3

Z

фi

Тн(Zi)

T(L*( Zi))

U

tij

Z0

0

0

32

0,1

0

Z1

2

0

32

0,2

0

Z2

4

0

19

1,3

15

Z3

5

17

15

2,4

12

Z4

3

29

3

2,5

3

Z5

8

7

8

3,4

7

Z6

0

32

0

4,6

0

5,6

0

3. Составим дерево проверок:

Рис. 1.2 - Дерево проверок

4. Рассчитаем t*(Sk) и полученные значения занесем в таблицу 1.4:

t*(S0) = 0

t*(S1) = 2

t*(S2) = 4

t*(S3) = 2+15+5=22

t*(S4) = 2+4=6

t*(S8) = 2+5+15=22

t*(S9) = 2+4+8+3=17

t*(S15) = 2+15+5+7+3 = 32

t*(S16) = 2+15+5+8 = 30

t*(S17) = 2+4+3+8+5 = 22

t*(S26) = 2+4+3+8+5+7+3=32

5. Рассчитаем оценку нижней границы для множества W(Sk) и полученные значения занесем в таблицу 1.4.

Tоц(S0) = 0 + max{(19,32) + max(0,(0,0)-0)} = 32

Tоц(S1) = 2 + max{(19,15) + max(0,(0,17-2)} = 32

Tоц(S2) = 4 + max{(32,7) + max(0,(0,7)-5)} = 36

Tоц(S3) = 22 + max{19 + max(0,0-22)} = 41

Tоц(S4) = 6 + max{(15,8) + max(0,(17,7)-6)} = 32

Tоц(S8) = 22 + max{(3,8) + max(0,(29,7)-22)} = 32

Tоц(S9) = 17 + max{15 + max(0,17-17)} = 32

Tоц(S15) = 32 + max{8 + max(0,7-32)} = 40

Tоц(S16) = 30+ max{3+ max(0,29-30)} = 33

Tоц(S17) = 22 + max{3 + max(0,29-22)} = 32

Tоц(S26) = 32 + max{0 + max(0,32-32)} = 32

Таблица 1.4.

S

Zi/i = Sk

N(Sk)

Y(Sk)

t*(Sk)

Tоц(Sk)

S0

Z0

Z1 Z2

Z0

0

32

S1

Z1

Z2 Z3

Z0 Z1

2

32

S2

Z2

Z5 Z1

Z0 Z2

4

36

S3

Z3

Z2

Z0 Z1 Z3

22

41

S4

Z2

Z5 Z3

Z0 Z1 Z2

6

32

S8

Z3

Z4 Z5

Z0 Z1 Z2 Z3

22

32

S9

Z5

Z3

Z0 Z1 Z2 Z5

17

32

S15

Z3

Z5

Z0 Z1 Z2 Z3 Z4

32

40

S16

Z5

Z4

Z0 Z1 Z2 Z3 Z5

30

33

S17

Z5

Z4

Z0 Z1 Z2 Z5 Z3

22

32

S26

Z1

Z6

Z0 Z1 Z2 Z5 Z3 Z4

32

32

Составим дерево оптимального решения (рис 1.3)

Рис1.3 - Дерево оптимального решения

Таким образом получили, что оптимальному процессу контроля соответствует последовательность проверок { Z0 Z1 Z2 Z5 Z3 Z4}, при этом общее время контроля составляет Топт = 32 ед.

Задача №2

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

Таблица 2.1

№ параметра

1

2

3

4

5

уИЗМПАР

0.5

0.3

0.2

0.1

0.4

ti

3

5

15

20

50

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

- суммарное время измерения контролируемых параметров не должно превышать 5 мин.

Решение:

1. Для каждого параметра определим значение pi(ni):

Таблица 2.2

n

уИЗМПАР

0.5

0.3

0.2

0.1

0.4

1

0.99110

0.99634

0.99784

0.99893

0.99419

2

0.99533

0.99775

0.99859

0.99930

0.99669

3

0.99657

0.99821

0.99886

0.99945

0.99748

4

0.99714

0.99846

0.99901

0.99955

0.99785

5

0.99756

0.99868

0.99915

0.99960

0.99816

6

0.99780

0.99879

0.99923

0.99963

0.99833

7

0.99801

0.99890

0.99931

0.99967

0.99849

8

0.99818

0.99895

0.99933

0.99970

0.999859

9

0.99828

0.99901

0.99937

0.99971

0.99867

10

0.99839

0.99909

0.99942

0.99973

0.99876

11

0.99848

0.99914

0.99945

0.99974

0.99882

12

0.99854

0.99918

0.99948

0.99975

0.99887

2. Для каждого значения параметра вычисляются значения yi(ni) выбирается наибольшее значение:

3.

y1(ni)

y1(2) = (0.99533-0.99110)/0.99110*3 = 0.001422661

y1(3) = 0.000415272

y1(4) = 0.000190653

y1(5) = 0.000140401

y1(6) = 0.000718243

y1(7) = 0.000070154

y1(8) = 0.000056779

y1(9) = 0.000033394

y1(10) = 0.000036729

y1(11) = 0.000030048

y1(12) = 0.00002003

y2(ni)

y2(2) = 0.000283035

y2(3) = 0.000092207

y2(4) = 0.000050089

y2(5) = 0.000044067

y2(6) = 0.000022029

y2(7) = 0.000022026

y2(8) = 0.000010011

y2(9) = 0.000012012

y2(10) = 0.000016015

y2(11) = 0.000010009

y2(12) = 0

y3(ni)

y3(2) = 0.000050108

y3(3) = 0.000018025

y3(4) = 0.000010011

y3(5) = 0

y4(ni)

y4(2) = 0.000018519

y4(3) = 0

y5(ni)

y5(2) = 0.000050292

y5(3) = 0.000015852

y5(4) = 0

Полученные результаты сведем в таблицу:

Таблица 2.3

n

Y1(n)

N

Y2(n)

N

Y3(n)

N

Y4(n)

N

Y5(n)

N

1

-

-

-

-

-

-

-

-

-

-

2

0.001422661

1

0.000283035

16

0.000050108

10

0.000018519

20

0.000050292

9

3

0.000415272

3

0.000092207

6

0.000018025

21

-

-

0.000015852

23

4

0.000190653

4

0.000050089

11

0.000010011

26

-

-

-

-

5

0.000140401

5

0.000044067

12

-

-

-

-

-

-

6

0.000718243

2

0.000022029

17

-

-

-

-

-

-

7

0.000070154

7

0.000022026

18

-

-

-

-

-

-

8

0.000056779

8

0.000010011

25

-

-

-

-

-

-

9

0.000033394

14

0.000012012

24

-

-

-

-

-

-

10

0.000036729

13

0.000016015

22

-

-

-

-

-

-

11

0.000030048

15

0.000010009

27

-

-

-

-

-

-

12

0.00002003

19

-

-

-

-

-

-

-

-

4. Для каждого этапа последовательно вычисляются значения Р(N) и Т(N), которые затем заносятся в таблицу:

Таблица 2.4

N

n1

n2

n3

n4

n5

1

2

1

1

1

1

2

3

1

1

1

1

3

4

1

1

1

1

4

5

1

1

1

1

5

6

1

1

1

1

6

6

2

1

1

1

7

7

2

1

1

1

8

8

2

1

1

1

9

8

2

1

1

2

10

8

2

2

1

2

11

8

3

2

1

2

12

8

4

2

1

2

13

9

4

2

1

2

14

10

4

2

1

2

15

11

4

2

1

2

16

11

5

2

1

2

17

11

6

2

1

2

18

11

7

2

1

2

19

12

7

2

1

2

20

12

7

2

2

2

21

12

7

3

2

2

22

12

8

3

2

2

23

12

8

3

2

3

24

12

9

3

2

3

25

12

10

3

2

3

26

12

10

4

2

3

27

12

11

4

2

3

Расчет Т(N)

Т = 3 + 5 + 15 + 20 + 50 = 93 с = 1 мин 33 с

Т(1) = 93 + 3 = 96 с = 1 мин 36 с

Т(2) = 96 + 3 = 99 с = 1 мин 39 с

Т(3) = 99 + 3 = 102 с = 1 мин 42 с

Т(4) = 102 + 3 = 105 с = 1 мин 45 с

Т(5) = 105 + 3 = 108 с = 1 мин 48 с

Т(6) = 108 + 5 = 113 с = 1 мин 53 с

Т(7) = 113 + 3 = 116 с = 1 мин 56 с

Т(8) = 116 + 3 = 119 с = 1 мин 59 с

Т(9) = 119 + 50 = 169 с = 2 мин 49 с

Т(10) = 169 + 15 = 184 с = 3 мин 4 с

Т(11) = 184 + 5 = 189 с = 3 мин 9 с

Т(12) = 189 + 5 = 194 с = 3 мин 14 с

Т(13) = 194 + 3 = 197 с = 3 мин 17 с

Т(14) = 197 + 3 = 200 с = 3 мин 20 с

Т(15) = 200 + 3 = 203 с = 3 мин 23 с

Т(16) = 203 + 5 = 208 с = 3 мин 28 с

Т(17) = 208 + 5 = 213 с = 3 мин 33 с

Т(18) = 213 + 5 = 218 с = 3 мин 38 с

Т(19) = 218 + 3 = 221 с = 3 мин 41 с

Т(20) = 221 + 20 = 241 с = 4 мин 1 с

Т(21) = 241 + 15 = 256 с = 4 мин 16 с

Т(22) = 256 + 5 = 261 с = 4 мин 21 с

Т(23) = 261 + 50 = 311 с = 5 мин 11 с

Расчет Р(N)

Р = р1р2р3р4р5 = 0.97857

Р(1) = (р1(2)/р1(1)) Р = 0.98275

Р(2) = (р1(3)/р1(2)) Р(1) = 0.98398

Р(3) = (р1(4)/р1(3)) Р(2) = 0.98454

Р(4) = (р1(5)/р1(4)) Р(3) = 0.98495

Р(5) = (р1(6)/р1(5)) Р(4) = 0.98519

Р(6) = (р2(2)/р2(1)) Р(5) = 0.98658

Р(7) = (р1(7)/р1(6)) Р(6) = 0.98679

Р(8) = (р1(8)/р1(7)) Р(7) = 0.98696

Р(9) = (р5(2)/р5(1)) Р(8) = 0.98944

Р(10) = (р3(2)/р3(1)) Р(9)= 0.99018

Р(11) = (р2(3)/р2(2)) Р(10) = 0.99064

Р(12) = (р2(4)/р2(3)) Р(11) = 0.99089

Р(13) = (р1(9)/р1(8)) Р(12) = 0.99099

Р(14) = (р1(10)/р1(9)) Р(13) = 0.99110

Р(15) = (р1(11)/р1(10)) Р(14)= 0.99119

Р(16) = (р2(5)/р2(4)) Р(15) = 0.99141

Р(17) = (р2(6)/р2(5)) Р(16) = 0.99152

Р(18) = (р2(7)/р2(6)) Р(17)= 0.99163

Р(19) = (р1(12)/р1(11)) Р(18) = 0.99169

Р(20) = (р4(2)/р4(1)) Р(19) = 0.99206

Р(21) = (р3(3)/р3(2)) Р(20) = 0.99233

Р(22) = (р2(8)/р2(7)) Р(21)= 0.99238

Полученные результаты занесем в таблицу:

Таблица 2.5

N

n1

n2

n3

n4

n5

Р(N)

Т(N)

1

2

1

1

1

1

0.98275

1 мин 36 с

2

3

1

1

1

1

0.98398

1 мин 39 с

3

4

1

1

1

1

0.98454

1 мин 42 с

4

5

1

1

1

1

0.98495

1 мин 45 с

5

6

1

1

1

1

0.98519

1 мин 48 с

6

6

2

1

1

1

0.98658

1 мин 53 с

7

7

2

1

1

1

0.98679

1 мин 56 с

8

8

2

1

1

1

0.98696

1 мин 59 с

9

8

2

1

1

2

0.98944

2 мин 49 с

10

8

2

2

1

2

0.99018

3 мин 4 с

11

8

3

2

1

2

0.99064

3 мин 9 с

12

8

4

2

1

2

0.99089

3 мин 14 с

13

9

4

2

1

2

0.99099

3 мин 17 с

14

10

4

2

1

2

0.99110

3 мин 20 с

15

11

4

2

1

2

0.99119

3 мин 23 с

16

11

5

2

1

2

0.99141

3 мин 28 с

17

11

6

2

1

2

0.99152

3 мин 33 с

18

11

7

2

1

2

0.99163

3 мин 38 с

19

12

7

2

1

2

0.99169

3 мин 41 с

20

12

7

2

2

2

0.99206

4 мин 1 с

21

12

7

3

2

2

0.99233

4 мин 16 с

22

12

8

3

2

2

0.99238

4 мин 21 с

23

12

8

3

2

3

0.99317

5 мин 11 с

Далее производить расчет нецелесообразно, т.к. решение задачи найдено

Оптимальное решение задачи - n1 = 12, n2 = 8, n3 = 3, n4 = 2, n5 = 2, где Т = 4мин 21 с, при этом максимальная достоверность результатов равна 0.99238 ( в таблице2.5. оптимальное решение этой задачи выделено голубым цветом)

Программная часть

Задача №1

рис.3.1. Интерфейс программы

В данное окно вводятся исходные данные. При нажатии кнопки «Расчет» начинаем расчет. В итоге получаем следующее окно.

рис. 3.2. Результат расчета

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

В нижней таблице «Таблица результатов» приведены результаты расчета.

Построим граф по результатам таблицы «Таблица результатов», и проверим: совпали ли результаты с ручным расчетом.

29

рис.3.3. Оптимальное решение

Таким образом, мы видим, что оптимальное решение, как и в случае ручного расчета, есть последовательность проверок {Z0, Z2, Z1, Z5, Z3, Z4}, при этом общее время контроля составляет Топт = 32 ед.

Задача №2

Решение, полученное программным путем совпадает с ручным расчетом, значит задача решена верно, т.е. оптимальное решение задачи - n1 = 12, n2 = 8, n3 = 3, n4 = 2, n5 = 2, где Т = 261с = 4мин 21 с, при этом максимальная достоверность результатов равна 0.992.

Заключение

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

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

3. Решения, полученные программным путем и рассчитанные вручную, совпадают как для первой, так и для второй задачи.

Список литературы

1. Селезнев А.В. и др. «Проектирование АСК бортового оборудования ЛА», Машиностроение, 1983 г.;

2. Загрутдинов Г.М. «Достоверность автоматизированного контроля», КХГ,1980 г.


Подобные документы

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

    курсовая работа [195,5 K], добавлен 08.11.2009

  • Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.

    курсовая работа [4,0 M], добавлен 05.03.2012

  • Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.

    курсовая работа [38,9 K], добавлен 15.11.2009

  • Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

    курсовая работа [2,2 M], добавлен 29.05.2015

  • Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.

    презентация [441,5 K], добавлен 19.10.2014

  • Общее понятие специальный проверок, цели, задачи, принципы и порядок их проведения. Типовой перечень операций проведения специальных технических проверок. Методики проведения специальных проверок служебных помещений, аппаратуры, техники и сувениров.

    курсовая работа [567,4 K], добавлен 30.04.2014

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

    презентация [323,6 K], добавлен 30.10.2013

  • Ознакомление с методами решения оптимизационных задач. Алгоритм метода ломанных. Определение наименьшего значения целевой функции. Описание метода анализа математической модели. Расчет поиска минимума по методу ломаных. Листинг программы, интерфейс.

    курсовая работа [2,2 M], добавлен 06.12.2014

  • Решение задачи на тему максимизации функций многих переменных. Описание метода дихотомии, его применение для решения нелинейных уравнений. Решение данной задачи с использованием метода покоординатного спуска. Составление алгоритмов, листинг программы.

    курсовая работа [138,5 K], добавлен 01.10.2009

  • Постановка задачи о коммивояжере. Нахождение оптимального решения с применением метода ветвей и границ. Основной принцип этого метода, порядок его применения. Использование метода верхних оценок в процедуре построения дерева возможных вариантов.

    курсовая работа [167,8 K], добавлен 01.10.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.