Блочно-симметричные модели и методы проектирования систем обработки данных
Исключить
из рассмотрения
строку с номером
.
Пересчитать
величины
относительно
столбца с учетом
нового состояния
.
Переход к 3.6.
Проверить
условие: все
ли процедуры
распределены?
Если нет, то
перейти к следующей
итерации, приняв
.
Иначе переход
к 4
Запомнить
содержание
матриц
и
.
Переход к 5.
Вычислить
относительно
и составить
матрицу
.
Переход к 6.
-я
итерация.
В матрице
найти
-й
минимальный
элемент. При
наличии нескольких
минимальных
элементов,
среди них выберем
такой элемент,
для которого
значение суммы
по строкам
минимально.
Если элементов
такого свойства
несколько, то
среди этих
минимальных
элементов
выберем элемент
расположенный
первым от начало
отсчета строк.
Переход к 6.2.
Определить
элементы
матрицы
.
Проверить
ограничения
на число информационных
элементов в
логическом
массиве. Если
оно неудовлетворительно,
то перейти к
6.3.
Исключить
из рассмотрения
элемент
.
Установить
.
Переход к 6.1.
Вычислить
состояние
матрицы
.
Переход к 6.5.
Исключить
из рассмотрения
строку с номером
.
Пересчитать
величины
относительно
столбца с учетом
нового состояния
.
Переход к 6.6.
Проверить
условие: все
ли информационные
элементы
распределены?
Если нет, то
перейти к следующей
итерации, приняв
.
Иначе переход
к 7.
Вывод решения
задачи: матриц
,
,
и значение
целевой функции
.
Сравним сложность для получения решения с использованием данного алгоритма, оцениваемую общим количеством шагов, с широко известным методом «ветвей и границ» для решения дискретных задач комбинаторного типа.
Необходимые количество шагов в процессе решения задачи с использованием алгоритма итеративных отображений равно
,(3.1.3)
где
,
- количество
итераций в
процессе формирования
соответствующих
решений
и
.
Число шагов
с использованием
метода «ветвей
и границ» для
решения указанных
задач определяется
по следующей
формуле
.(3.1.4)
Сравнение соотношений (3.1.1), (3.1.2) показывает эффективность и полиномиальную сложность разработанных алгоритмов для решения поставленных задач большой размерности, в отличие от метода «ветвей и границ».
Блок-схема алгоритма итеративных отображений приведена на рис. 3.1.1.
Рассмотрим численный пример решения задачи. Необходимо синтезировать блок-схему модульной СОД, минимизирующую общее число обращений к логическим массивом базы данных.
Задача решается
при следующих
условиях: допустимое
число процедур
в составе модуля
3, допустимое
число информационных
элементов в
составе логических
массивов 4. Число
модулей и логических
массивов определяется
по формулам:
и
,
с округлением
в большую строку.
В таблице
3.1.1 представлена
исходная матрица
с
выделенным
базисом
в
верхнем левом
углу исходной
матрицы. В базис
вошли 1, 2, 3, 4, 5 и строки
1, 2, 3 матрицы
.
На рисунке
3.1.2 показан процесс
формирования
решения
с использованием
разработанного
алгоритма.
Матрица
определена
с использованием
соотношения
(3.1.1).
Процесс
отображений
представлен
таблицей, в
которой приведены
номер итерации
,
минимальный
элемент из
,
в соответствии
с которым
отображается
номер процедуры
в номер модуля
.
На рисунке
представлены
матрицы
и
,
содержание
которых определено
базисом поиска
решения
,
а в правой матрице
и
,
полученные
с использованием
алгоритма
итеративных
отображений.
На рисунке
3.1.2 показан процесс
формирования
решения
.
Матрица
определена
с использованием
соотношения
(3.1.2) и матрицы
.
Процесс отображения
представлен
таблицей, в
которой приведены
номер итерации
,
минимальный
элемент
из
в соответствии
с которым номер
информационного
элемента
отображается
в номер файла
.
На рисунке
3.1.2 представлена
матрица
,
которая сформирована
до поиска
оптимального
решения и определена
базисом, а также
матрица, полученная
в результате
формирования
решения
.
А также представлены
матрица решения
задачи
,
полученная
с использоваием
алгоритма
итеративных
отображений,
и матрица
,
полученная
в результате
отображения.
Матрица
соответствует
матрице целевой
функции
,
отражающей
взаимосвязи
программных
модулей и логических
масивов базы
данных модульной
блок-схемы.
Оптимальное
значение целевой
функции, полученное
при этом базисе
и ограничеиях,
равно
=
=6.
С использованием алгоритма итеративных отображений решаются и частные задачи вида (2.4.1)-(2.4.4) и (2.4.5)-(2.4.8) как части блочно-симметричных задач.
3.2 Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных
Как показал опыт проектирования систем обработки данных в ряде случаев к ним предъявляются различные технологические требования, часто противоречивые, которые необходимо учитывать. При этом одни требования имеют важное значение в качестве критериев эффективности, а другие – определяют технологические ограничения в процессе проектирования систем обработки данных.
В процессе анализа и синтеза систем обработки данных возникает необходимость одновременного учета нескольких показателей эффективности, которые определяют качество разрабатываемой ситемы в области заданных ограничений. Тогда задача сводится к тому, что необходимо использовать несколько критериев, чтобы наиболее адекватно отобразить их требуемую постановку. В этом случае необходимо формулировать и решать многокритериальные блочно-симметричные задачи.
Общая постановка многокритериальной задачи формулируется следующим образом [121-123,135,142,143].
Необходимо найти экстремум вектора функций, отражающего показатели эффективности разрабатываемых систем обработки данных в области заданных технологических ограничений.
Приведем математическую постановку общей многокритериальной задачи.
Пусть,
- двухиндексная
переменная,
отражающая
распределение
элементов
одного типа
по группам, а
- переменная,
отражающая
распределение
элементов
другого типа
по соответствущим
группам. Задана
матрица
взаимосвязи
элементов
различных типов
между собой.
Определены
критерии
,
эффективности,
зависящие от
переменных
и
,
доставляющие
экстремум
функции вида
,
.
Многокритериальная блочно-симметричная задача дискретного программирования формулируется следующим образом:
,(3.2.1)
при ограничениях вида
,
,(3.2.2)
,
.(3.2.3)
Для решения
однокритериальной
блочно-симметричной
задачи (
)
разработан
и предложен
эффективный
алгоритм, позволяющий
определить
оптимальные
решения при
определенных
условиях. Используя
разработанный
алгоритм можно
предложить
следующую схему
решения многокритериальной
задачи.
Решается
однокритериальная
задача
при ограничениях
вида (3.2.2) - (3.2.3) с
использованием
заданного
алгоритма.
Определяются
переменные
и
.
Определяются
значение функций
,
.
Решается
однокритериальная
задача
при ограничениях
вида (3.2.2) - (3.2.3) с
использованием
заданного
алгоритма.
Определяются
переменные
и
.
Определяются
значение функций
,
.
Решается
однокритериальная
задача
при ограничениях
вида (3.2.2) - (3.2.3) с
использованием
заданного
алгоритма.
Определяются
переменные
и
.
Экстремальные
значения функций
определяют
область нахождения
решения.
Таким образом, в результате решения многокритериальной задачи определяется область решения, в которой находится решение, удовлетворяющее всем критериям и соответствующим условиям [135].
Рассмотрим постановку и решение двухкритериальной задачи разработки модульной блок-схемы системы обработки данных.
В данной
постановке
необходимо
множество
процедур обработки
данных
распределить
по программным
модулям, а множество
информационных
элементов
,
необходимых
для реализации
заданных процедур,
распределить
по массивам
базы данных
таким образом,
чтобы минимизировать
связи между
программными
модулями.
В качестве критерия эффективности используем минимум взаимосвязей между модулями блок-схем и массивами базы данных. Данный критерий позволяет представить структуру блок-схемы в виде слабосвязанных компонент модулей и связанных с ними массивов базы данных, уменьшить число обращений модулей к массивам в процессе их обработки. При заданных числовых характеристиках: времени обработки процедуры информационных элементов, времени обращения модулей к массивам базы данных, объемов процедур и информационных элементов, формируется критерии минимума времени обработки блок-схем, минимума памяти при обработке блок-схем и т.д.
В матрчной форме данный критерий запишется в виде
.(3.2.4)
В процессе проектирования модульных блок-схем часто необходимо, определить межмодульный интерфейс,который представляет собой состав и число информационных элементов между модулями систем обработки данных. Данный критерий позволяет определить содержание межмодульного интерфейса и оптимальную структуру всей модульной блок-схемы.
Критерий минимума информационных элементов, используемых программными модулями (межмодульной интерфейс) блок-схемы обработки данных в матричной форме записывается следующим образом:
.(3.2.5)
В общем случае данные критерии противоречивы, для которых трудно определить точное решение.
В матричной форме двухкритериальная блочно-симметричная задача запишется в следующем виде:
(3.2.6)
(3.2.7)
при ограничениях вида (3.2.2) – (3.2.3).
-
сумма единичных
элементов
результирующих
булевых матриц
(3.2.6) и (3.2.3);
,