Блочно-симметричные модели и методы проектирования систем обработки данных
Сформулированы задачи диссертационного исследования.
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)
(2.1.8)
(2.1.9)
В постановке
задачи (2.1.5) - (2.1.9) выделим
блок функции
(2.1.6), (2.1.7), зависящий
только от переменной
,
и блок функций
(2.1.8), (2.1.9), зависящий
только от переменной
,
объединенных
единым функционалом
вида (2.1.5). Заметим,
что в ряде постановок
задач может
быть блок ограничений
вида
(2.1.10)
зависящий
от переменных
и
.
В этом случае можно выделить блок функционала цели вида (2.1.5), (2.1.10).
Отсюда следует.
Определение
2.1. Блочно-симметричной
задачей дискретного
программирования
назовем задачу
вида (2.1.5) - (2.1.9), где
переменные
и
и значения
функций
,
,
- целые, либо
булевые
Рассмотрим
выражение
(2.1.4). из него следует
что переменные
и
симметричны
относительно
заданной матрицы
и
функция (2.1.4) может
быть определена
как слева направо,
так и наоборот,
т.е.
(2.1.11)
На основе общей постановки определим основные свойства сформулированного класса задач, отличающие его от традиционных постановок задач дискретного программирования.
Свойство
1. В блочно-симметричной
задаче имеется
два типа переменных
и
различного
содержания,
определенных
как целочисленные
(булевы) матрицы
на заданной
матрице
.
В общем случае переменных может быть и больше в зависимости от постановок задач.
Свойство
2. Блочность
задачи заключается
в выделении
в постановке
отдельных
блоков функций
вида (2.1.5), (2.1.10); (2.1.6), (2.1.7) и
(2.1.8), (2.1.9), которые
соответственно
зависят от
переменных
и
.
Как видно из указанных соотношении каждый из блоков имеет свою целевую функцию и координируется общим функционалом вида (2.1.5).
Свойство 3. Блочно-симметричную задачу в большинстве случаев можно представить в матричной форме вида (2.1.11).
Матричная форма постановки блочно-симметричных задач позволяет использовать аппарат теории матриц и разрабатывать эффективные алгоритмы решения задач этого класса.
Свойство 4. Симметричность задачи заключается в возможности вычисления (2.1.11) как слева направо, так и обратном направлении.
Указанные свойства и особенности блочно-симметричных задач ДП позволяют синтезировать алгоритмы, обеспечивающих решение практических задач большой размерности.
В ряде постановок
задач функционал
(2.1.1) можно представить
в виде вектора
функций
.
В этом случае
формулируется
многокритериальная
блочно-симметричная
задача дискретного
программирования.
Анализ постановки, свойств и особенности блочно-симметричных задач позволил разработать и предложить подход и схему метода решения общей задачи на основе следующего утверждения.
Утверждение.
Распределение
элементов
множества
по непересекающим
подмножествам
соответствует
логическому
сложению строк
матриц
,
а распределение
элементов
множества
по непересекающимся
подмножествам
- логическому
сложению столбцов
матрицы
.
[132, 133] Результаты
данного утверждения
позволяют
просто вычислить
оценки и направления
поиска решения
для разработки
эффективных
алгоритмов.
Введем понятие
базиса решения
задач. Под базисом
понимается
заранее заданный
состав элементов
подмножеств
и
.
В матрице
базис находится
как некоторая
матрица
элементы которых
определены.
Данную матрицу
путем перестановки
номеров строки
столбцов матрицы
и их перенумировки
всегда можно
определить
в левом верхнем
углу. Такое
представление
упрощает процедуру
оценок и определения
направления
поиска решения.
Для решения
блочно-симметричной
задачи дискретного
программирования
при условии,
когда
,
и
- булевы матрицы,
разработана
и предложена
эффективная
схема решения
задачи. Схема
поиска решения
состоит из
следующих
основных этапов:
В булевой
матрице
выделим
подматрицу
,
,
и определим
её как базис
решения задачи.
Определим
матрицу
,
,
направления
поиска решения
путем логического
сложения небазисных
строк матрицы
со строками
базиса и вычислим
значения оценок
только