49743 (588672), страница 12

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

Текст из файла (страница 12)

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

,(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)

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

1. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .

2. Определяются значение функций , .

3. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .

4. Определяются значение функций , .

5. Решается однокритериальная задача при ограничениях вида (3.2.2) - (3.2.3) с использованием заданного алгоритма. Определяются переменные и .

6. Экстремальные значения функций определяют область нахождения решения.

Таким образом, в результате решения многокритериальной задачи определяется область решения, в которой находится решение, удовлетворяющее всем критериям и соответствующим условиям [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);

, , - переменная распределения процедур обработки данных по модулям блок-схемы;

, , - переменная распределения информационных элементов по массивам базы данных;

- взаимосвязи между информационными элементами и процедурами обработки данных;

- транспонированная матрица.

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

Характеристики

Список файлов ВКР