Принятие решения о работоспособности объекта

Федеральное Агентство по Образованию

Рязанский Государственный Радиотехнический Университет

Курс лекций по дисциплине

«ДИСКРЕТНАЯ МАТЕМАТИКА»

Рязань,2006

Содержание

Принятие решения о работоспособности объекта.. 3

Получение уравнения гиперплоскости, проходящей через n заданных точек. 7

Задача о кротчайшем пути.. 12

Алгоритм Минти.. 12

Табличный способ расчета кротчайшего пути(алгоритм Форда) 13

Решение задачи о кратчайшем пути в графе на основе ЛП.. 14

Сетевой график.. 15

Определение критического пути на сетевом графе.. 17

Табличный способ расчета сетевого графа.. 17

Расчет сетевого графа на основе линейного программирования. 17

Кратчайший остов графа. 18

Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательности ребер или дуг. 18

Алгоритм Прима определение минимального остовного дерева(случай многоуровнего графа) 19

Решение задачи о кротчайшем остове графа на основе линейного программирования.. 20

Алгоритм венгерского метода.. 21

Модификация задачи о назначениях.. 24

Решение задачи о назначении на основе. 25

линейного программирования. 25

Решение задачи коммивояжера.. 25

Решение задачи о наименьшем покрытии.. 27

методом ветвей и границ.. 27

Алгоритм метода ветвей и границ.. 28

Решение задачи о наименьшем покрытии на основе линейного программирования. 29

Принятие решения о работоспособности объекта

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

Исходное множество задано следующим видом(табл.1):

Таблица 1.

№ по списку	Х1	Х2	Работоспособность
			+
			+
			+
			+
			+
			+
			+

Где Х1,Х2-значения параметров.

Необходимо узнать, работоспособен ли объект с параметрами Х^*₁=0, Х^*₂=0. Где *-это контролируемый объект.

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

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

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

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

N

∑a_ijx_j+m_i<=0, i=1,2,…,m. (1)

j=1

Исходными данными для определения количества линейных неравенств и значений их коэффициентов являются граничные точки. Для построения области работоспособности предлагается использовать метод гиперплоскостей, позволяющий получить область в виде многогранника, вершинами которого будут граничные точки. Грани многогранника представляют собой гиперплоскости, которые соответствуют уравнениям неравенств (1) при замене знака ”≤” на знак ”=”.

Блок-схема алгоритма метода гиперплоскостей.

Граф исходного множества имеет вид(рис.1):

х2 1

10

9 2 7

8

6 6

5 • 4

3 3

2 5

0 1 2 3 4 5 6 7 8 9 10 11 х1

Рисунок 1. Граф множества.

1)Берется n+1 точка в многомерном пространстве, где n-размерность пространства. Через каждые n точек проводиться гиперплоскость и заполняется таблица.

-уравнение гиперплоскости.

Берем 1,2,3-ю точки. Проводим линию (так как пространство 2-х мерное) через точки 1-2, 2-3, 3-1.

Прямая	1-2	2-3	1-3
Вершина
Координаты вершины	2,3	6,8	1,8
Координаты 1-й точки	6,10	1,8	6,10
Координаты 2-й точки	1,8	2,3	2,3
Уравнение прямой	Х1-2,5х2+19=0	Х1+0,2х2-2,6=0	7х1-4х2-2=0

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

2)Берем 4-ю точку и для нее ищем генеральную гиперплоскость.

Генеральная гиперплоскость обладает свойством, что данная точка (4) и вершина гиперплоскости должны лежать по разные стороны от нее.

Генеральная гиперплоскость ищется среди всех ранее построенных плоскостей.

В данном примере генеральной гиперплоскостью является 1-3. Имеем n+1 точку и через каждые n точек проводим гиперплоскость.

В результате получим следующий рисунок:

х2 1

10

9 2 7

8

6 4 6

5 •

3 3

2 5

0 1 2 3 4 5 6 7 8 9 10 11 х1

Рисунок 2. Граф множества, поделенного гиперплоскостями.

Алгоритм нахождения генеральной точки гиперплоскости

Берется линейная форма гиперплоскости (левая часть равенства) и в нее подставляем координаты точек вершины и данной точки. Если линейные формы имеют разные знаки, то генеральная гиперплоскость найдена. Генеральная гиперплоскость после этого исключается, исключаются также плоскости повторяющиеся.

Прямая	1-3	3-4	1-4
Вершина

3)для точки 5 генеральная гиперплоскость- 1-4.

Прямая	1-4	4-5	1-5
Вершина

Прямая	3-4	3-5	5-4
Вершина

В результате имеем:

х2 1

10

9 2 7

8

6 4 6

5 •

3 3

2 5

0 1 2 3 4 5 6 7 8 9 10 11 х1

Рисунок 3. Граф множества.

4)Берем точку 6. Генеральная гиперплоскость- 1-5.

Прямая	1-5	5-6	1-6
Вершина

5)Берем точку 7. Генеральная гиперплоскость- 1-6.

Прямая	1-6	6-7	7-1
Вершина

Получим границу областей работоспособности:

(1-2)-(2-3)-(3-5)-(5-6)-(6-7)-(7-1).

Переходим от равенств к неравенства. Для перехода от равенства к неравенству необходимо в линейную форму равенства подставить координаты вершины. Если линейная форма положительна, то знак «=» заменяется на «>=», если отрицательна, то вместо «=» ставится «<=».

Получаем уравнения:

(1-2) х1-2,5х2+19=0

подставляем координаты вершины (точка 3)и получаем:

х1-2,5х2+19≥0

(2-3) х1+0,2х2-2,6≥0

(3-5) х1+6х2-20≥0

(5-6) -х1+0,7х2+6,5≥0

(6-7) -х1-0,5х2+14≥0

(7-1) -х1-2х2+26≥0

Штрихуем полученную область, штриховка выполняется в направлении точки, которою мы выбираем. Если выполняется, то штрихуем в этом направлении, если нет, то в обратном.

Если множество будет невыпуклым, то его можно представить совокупностью выпуклых множеств.

Дата добавления: 2015-08-21