Лабораторная работа 1. Построение и исследование моделей

Предисловие

Данное пособие включает три лабораторные работы.

В лабораторной работе 1 рассматривается задача определения оптимальной (рациональной) структуры рассматриваемой АСОИУ. Предложены для анализа и исследования модель и алгоритм решения этой задачи на основе теории графов.

В лабораторной работе 2 рассматриваются задачи оптимального распределения задач, возложенных на АСОИУ, между отдельными узлами распределенной АСОИУ с учетом ресурсных возможностей каждого узла.

Лабораторная работа 3 посвящена вопросам построения и анализа моделей, позволяющих спланировать процесс проектирования АСОИУ.

Лабораторная работа 1. Построение и исследование моделей

Синтеза оптимальной (рациональной) структуры АСОИУ

Цель работы: - ознакомиться с постановкой и методом решения задачи определения оптимальной (рациональной) структуры АСОИУ на основе применения теории графов.

Порядок выполнения работы:

1. Предложить на содержательном уровне пример АСОИУ, для которой будет решаться задача определения оптимальной (рациональной) структуры.

2. Построить информационно-логическую модель выбранной АСОИУ в виде графа, рассматривая вершины графа как решаемые системой задачи, а дуги – информационные связи между этими задачами. Число вершин граф – не менее 10, а число дуг – не менее 25. Согласовать это предложение с преподавателем.

3. Изучить алгоритм решения задачи построения оптимальной (рациональной) структуры АСОИУ как задачи определения сильно связанных компонент графа, предложенного в п.2.

4. Реализовать алгоритм, построив оптимальную (рациональную) структуру АСОИУ, в которой сильно связанные компоненты – это подсистемы рассматриваемой АСОИУ.

5. Составить отчет по лабораторной работе, в котором отразить:

- что представляет собой выбранная АСОИУ, для которой решается задача определения оптимальной (рациональной) структуры;

- постановку, математическую модель и алгоритм решения задачи определения оптимальной (рациональной) структуры выбранной АСОИУ;

- найденную оптимальную (рациональную) структуру АСОИУ;

- результаты анализа и исследования эффективности рассмотренной модели и алгоритма ее решения.

6. Ответить на вопросы преподавателя.

Методические указания

Постановка задачи определения оптимальной (рациональной) структуры АСОИУ.

Проектирование любого объекта, в том числе и АСОИУ, требует предварительного анализа этого объекта с целью его структуризации. Структуризация АСОИУ – это локализация ее границ и выделение структурных составных частей. Выделенную по определенному признаку часть АСОИУ называют ее подсистемой.

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

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

Функциональной структурой АСОИУ называют структуру, элементами которой являются подсистемы, автоматизирующие выполнение отдельных функций управления.

Функция управления – это совокупность действий, выполняемых в системе управления для достижения объектом управления определенной цели.
Связи между элементами функциональной структуры АСОИУ – это потоки информации, циркулирующей между отдельными функциональными подсистемами. Информация, поступающая от одной функциональной подсистемы к другой подсистеме, может быть двух видов.

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

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

Для построения организационной (функциональной) структуры АСОИУ проводят системный анализ объекта автоматизации и его системы управления с целью выявления решаемых этой системой задач. Результаты этого анализа представляют в виде направленного информационно-логического графа, вершины которого – решаемые задачи управления, а дуги – информационные связи между этими задачами.

Задачу построения организационной (функциональной) структуры АСОИУ можно сформулировать как задачу выявления сильно связанных компонент графа. Эти сильно связанные компоненты можно рассматривать как подсистемы АСОИУ, причем связь между этими подсистемами будет минимальной (более точно, рационально минимальной).

Методические указания

Рассмотрим некоторые частные постановки задач формализованного распределения множества решаемых задач между узлами АСОИУ при различных критериях и ограничениях.

1.1. Первая задача

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

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

Найти

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

,

,

В этих соотношениях:

- время решения задачи , если она расположена в узле ;

- допустимая загрузка в узле ;

- переменная, равная 1, если задача решается в узле , и равная 0 – в противном случае.

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

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

Вершины второго уровня получают, фиксируя для при и т. д. Для каждой вершины находят оценку, вычисляемую по формуле

,

где - число рассмотренных уровней ветвления; .

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

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

- исключены все элементы , тогда решение отсутствует;

- остался лишь один элемент , он обязательно входит в оптимальное решение, если оно существует. Значение заменяется величиной , и этот элемент в дальнейшем поиске не участвует;

- осталось несколько элементов, они участвуют в дальнейшем поиске оптимального решения.

Рассмотрим решение первой частной задачи. Необходимо найти при следующих ограничениях:

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

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

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

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

Таким образом, . Поэтому имеем:

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

или

Значение целевой функции в первом случае , а во втором случае . Варианты равнозначны.

 

1.2. Вторая задача

Необходимо так распределить задачи между узлами , чтобы обеспечить минимум общих затрат (критерий 1) или минимум общего времени решения (критерий 2) при выполнении ограничений на общее время решения (9) или общие затраты (6) соответственно.

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

(15)

при следующих ограничениях:

(16)

(17)

В соотношениях (15) - (17) приняты следующие обозначения:

- затраты (время решения) задачи , расположенной в узле ,

- время решения (затраты) на задачу , расположенную в узле ,

- общее время решения (затраты) всех задач.

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

Если условие (16) выполняется, то это и будет оптимальным решением. Если оно не выполняется, то из матрицы коэффициентов и исключают те элементы, которые не могут войти ни в одно допустимое решение. Для этого последовательно рассматриваются все элементы матрицы и проверяют следующее условие:

(18)

где - минимальный элемент в соответствующей строке;

- рассматриваемый элемент, .

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

Если условие (18) нарушается, то соответствующий элемент не входит в допустимое решение и исключается из матрицы . Из матрицы исключается соответствующий элемент .

Из условия (17) следует, что в каждой строке может быть только один элемент. Поэтому без учета выражения (14) равен . Отсюда следует, что если для элементов одновременно выполняются условия и , , то эти элементы могут быть исключены из рассмотрения.

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

Далее используется метод «ветвей и границ». В отличие от предыдущей задачи, ветвление осуществляется с учетом ограничения (16), что существенно сокращает число рассматриваемых вариантов. Оценка для каждой вершины находится по элементам матрицы (15) аналогично предыдущей задаче (14). Ограничение при этом имеет следующий вид:

, (19)

где - уровень ветвления;

.

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

(30)

при следующих ограничениях:

(31)

(32)

(33)

Пусть

Сначала находим минимальные элементы в каждой строке матрицы и проверяем, удовлетворяется ли условие (31) по одноименным элементам матрицы

.

Условие (31) не выполняется, и задачу «в лоб» решить не удается. Приступим к упрощению матриц коэффициентов и . Для матрицы последовательно для всех элементов проверяется условие (18), т.е. условие

(34)

где - минимальный элемент в соответствующей строке;

- рассматриваемый элемент, .

Для

Элемент не удовлетворяет условию (34), он исключается из матрицы , и одноименный элемент исключается из матрицы . Аналогично для имеем:

Для

 

Для

 

Для :

Легко видно, что для все элементы удовлетворяют условию (34).

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

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

- (3 и 7) и (1,5 и 3) – условие выполняется и, следовательно, можно убрать элементы и ;

- (2 и 4) и (2 и 9) - условие снова выполняется и, следовательно, можно убрать элементы и .

Таким образом, первая строка матрицы запишется как (3 – 2 -), а последняя строка как (7 - - 1).

После соответствующих упрощений матрицы и принимают следующий вид:

Из матрицы в каждой строке выбираем минимальные элементы и получаем следующее решение:

 

 

Подсчитываем время решения: 2+5+3+4+5=19<20. Оно не превышает допустимой величины. Задача решена.

 

Варианты задач

Вариант 1.

Первая задача

,

Вторая задача

 

, ,

 

Вариант 2.

 

Первая задача

,

Вторая задача

 

, ,

 

 

Вариант 3.

 

Первая задача

,

Вторая задача

 

, ,

 

 

Вариант 4.

 

Первая задача

,

Вторая задача

 

, ,

 

Вариант 5.

 

Первая задача

,

Вторая задача

 

, ,

Методические указания

Предисловие

Данное пособие включает три лабораторные работы.

В лабораторной работе 1 рассматривается задача определения оптимальной (рациональной) структуры рассматриваемой АСОИУ. Предложены для анализа и исследования модель и алгоритм решения этой задачи на основе теории графов.

В лабораторной работе 2 рассматриваются задачи оптимального распределения задач, возложенных на АСОИУ, между отдельными узлами распределенной АСОИУ с учетом ресурсных возможностей каждого узла.

Лабораторная работа 3 посвящена вопросам построения и анализа моделей, позволяющих спланировать процесс проектирования АСОИУ.

Лабораторная работа 1. Построение и исследование моделей