Учебник Математики и информатики

Отношения и графы, Свойства и типы однородных отношений

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

В первую очередь принимаются меры по сокращению продолжительности работ, находящихся на критическом пути. Это достигается:

Перераспределением всех видов ресурсов, как временных, так и трудовых, материальных, энергетических; при этом распределение ресурсов должно идти, как правило, из зон, менее напряжённых, в зоны, объединяющие наиболее напряжённые работы;
Сокращением трудоёмкости критических работ за счёт передачи части работ на другие пути, имеющие резервы времени;
Параллельным выполнением работ критического пути;
Пересмотром топологии сети, изменением состава работ и структуры сети.

При моделировании мероприятий, проводимых в войсках, вершинами графов будут отдельные действия объектов, а дугами временные нормативы их выполнения. Моделирование систем управления (СУ) для решения задач распознавания предполагает использование в качестве вершин графов отдельные пункты управления (ПУ), а в качестве дуг – расстояние между ними.

Задача распознавания решается в процессе непрерывном сопоставлении последовательности выявленных признаков с эталонами возможных действий объектов и выборе на этой основе гипотезы о проводимом мероприятии. По выявленным признакам определяются вершины графов, «спорящих» по данной реализации и фиксируется время выявления. Вершины графов выявленные по каждой последующей реализации, сопоставляются по времени с ранее выявленными. Если вновь выявленная вершина не согласуется во времени с предыдущей – синтезируется очередной вариант текущего графа (см. рис.3.7).

a b

Tа T1 Tb T2

Рис.3.7. Решение задач распознавания объектов

Под согласованностью вершин понимается совпадение временного интервала между соответствующими реализациями с границами (Т1, Т2) с ожидаемым проявлением вершин, согласно эталонным описаниям.

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

Отношения – это характеристика взаимосвязи событий в графе. Они могут быть однородными и неоднородными. Однородные отношения имеют место, когда два рядом стоящих события на графе имеют одинаковую природу и однозначно связаны друг с другом. Неоднородные отношения характеризуют отсутствие однозначной связи событий на графе.

Свойства однородных отношений:

Детерминированность – обязательное наступление второго события, при наличие первого.
Полнота – то есть следование второго события из первого, а также возможность обратного следования первого из второго (откат назад).

Однородные

отношения

Н еоднородные отношения: из одного события могут следовать несколько разнородных событий

Сходство текущего и эталонного графов может оцениваться без использования ЭВМ, путём вычисления следующего приближённого показателя:

ω =Δτ •Δn/ τм • N, где

Δτ – длительность интервала наблюдения текущего графа, границами которого являются значения времени выявления вершин графа и времени последней реализации.

τм – длительность мероприятия по эталонному описанию.

Δn – количество выявленных вершин в текущем графе.

N – общее количество потенциально проявляющихся вершин в пределах интервала наблюдения текущего графа.

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

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

Вывод – распознавание состояния и задач объекта.

Для примера рассмотрим граф проведения итоговой проверки части комиссией вышестоящих органов.

Содержание