 |
Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных
|
|
|
|
Как показал опыт проектирования систем обработки данных в ряде случаев к ним предъявляются различные технологические требования, часто противоречивые, которые необходимо учитывать. При этом одни требования имеют важное значение в качестве критериев эффективности, а другие – определяют технологические ограничения в процессе проектирования систем обработки данных.
В процессе анализа и синтеза систем обработки данных возникает необходимость одновременного учета нескольких показателей эффективности, которые определяют качество разрабатываемой ситемы в области заданных ограничений. Тогда задача сводится к тому, что необходимо использовать несколько критериев, чтобы наиболее адекватно отобразить их требуемую постановку. В этом случае необходимо формулировать и решать многокритериальные блочно-симметричные задачи.
Общая постановка многокритериальной задачи формулируется следующим образом [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);
, 
, 
- переменная распределения процедур обработки данных по модулям блок-схемы;
, 
, 
- переменная распределения информационных элементов по массивам базы данных;
- взаимосвязи между информационными элементами и процедурами обработки данных;
- транспонированная матрица.
Для решения поставленной задачи разработан и предложен алгортм, основанный на вышеуказанной схеме решения общей многокритериальной задачи.
Рассмотрим численный пример решения двухкритериальной задачи. На таблице 3.2.1 приведена исходная матрица. Используя предложенный алгоритм решения однокритериальных задач находим решение двухкритериальной задачи. На рис. 3.2.3 и 3.2.4 приведён численный пример решения двухкритериальной задачи. Значение целевой функции приведены на рис. 3.2.5. Полученное решение определяет область, ограниченную треугольником АВС (рис. 3.2.6).
Разработано программное обеспечение решения двухкритериальной задачи вида (3.2.6) – (3.2.7) и (3.2.2) – (3.2.3) при любом размере исходной матрицы (размер исходной матрицы генерируется случайным образом) в среде Delphi 7.0. Программное опеспечение описано в разделе 3.3.
|
|
|
|
|
|
