Блочно-симметричные модели и методы проектирования систем обработки данных (стр. 12 из 22)

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

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

-разработать общую блочно-симметричную модель проектирования систем обработки данных;

- сформулировать и решить задачу декомпозиции систем обработки данных на кластеры функциональных задач и исходных документов;

- разработать методы синтеза модульных блок-схем обработки данных;

- разработать многокритериальные блочно-симметричные модели и методы проектирования модульных блок-схем обработки данных;

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

Выводы к разделу 1

- Приведен анализ существующих моделей и методов проектирования модульных систем обработки данных.

- Приведен краткий обзор методов и алгоритмов дискретного программирование для решения задач проектирование систем обработки данных.

- Сформулированы задачи диссертационного исследования.

2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ

В данном разделе рассматриваются общая постановка блочно-симметричной задачи дискретного программирования, её особенности и свойства. Разработан общий подход решения задач данного класса.

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

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

Сформулирован также частные задачи проектирования модульных блок-схем обработки данных [142]

2.1 Общая постановка блочно-симметричных задач дискретного программирования

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

Рассмотрим общую постановку блочно-симметричных задач дискретного программирования [126, 127].

Постановка задачи. Пусть задано множество объектов

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

, , ,

Элементы которой целочисленные и булевы. Необходимо объединить элементы множество

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

Для формализованной постановки задачи введем следующие переменные. Пусть

- булева матрица, где , если -й элемент распределяется в -ю группу, в противном случае. Аналогично , где , если -й элемент распределяется в -ю группу и в противном случае. В общем случае матрицы переменных и могут быть целочисленными [136].

Определим на множестве

функцию , зависящую от распределения элементов множеств и по подмножествам и . Соответственно на множестве - функции , а на множестве - функции , определяющие ограничения на множествах и .

Блочно-симметричная задача дискретного программирования формулируется следующим образом:

,(2.1.1)

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

(2.1.2)

(2.1.3)

В множестве ограничений (2.1.2) и (2.1.3) в зависимости от постановок задач знаки неравенств могут меняться на противоположеные.

В общем случае двухиндексные матрицы – переменных

и и заданная матрица могут быть целочисленными.

Рассмотрим задачу при условии, когда переменные

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

(2.1.4)

Рассмотрим выражение (2.1.4), которое представляет собой произведение матриц переменных

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

В задаче (2.1.1) -(2.1.3) можно выделить множество ограничений вида (2.1.2), которые зависят от переменной

, и множество ограничений вида (2.1.3), которые зависят от переменной .

Функционал вида

можно представить следующим образом:

(2.1.5)

(2.1.6)

(2.1.7)