Дипломная работа: Блочно-симметричные модели и методы проектирования систем обработки данных
В задаче (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] Результаты данного утверждения позволяют просто вычислить оценки и
направления поиска решения для разработки эффективных алгоритмов.
Введем понятие базиса
решения задач. Под базисом понимается заранее заданный состав элементов
подмножеств и .
В матрице базис находится как
некоторая матрица элементы которых определены. Данную матрицу путем
перестановки номеров строки столбцов матрицы и
их перенумировки всегда можно определить в левом верхнем углу. Такое
представление упрощает процедуру оценок и определения направления поиска
решения.
Для решения
блочно-симметричной задачи дискретного программирования при условии, когда , и - булевы матрицы,
разработана и предложена эффективная схема решения задачи. Схема поиска решения
состоит из следующих основных этапов:
1.
В булевой матрице
выделим подматрицу , , и определим её как базис
решения задачи.
2.
Определим матрицу
, , направления поиска решения путем логического сложения
небазисных строк матрицы со
строками базиса и вычислим значения оценок только по позициям базиса.
3.
В соответствии с
полученными оценками осуществим распределение элементов множества по множествам . В результате зафиксируем
решение и промежуточную. Матрицу , , .
4.
Определим матрицу
, , . направления
поиска решения путем
логического сложения небазисных столбцов промежуточной матрицы со столбцами базиса и
вычислим значения оценок только по позициям базиса матрицы .
5.
В соответствии с
полученными оценками матрицы распределим
элементы множества по множествам.
В результате фиксируем решение и
целевую матрицу , на которой определено значение целевой функции .
6.
Следует отметить,
что поиск решения задачи может осуществляться как в прямом направлении по схеме
, так и в обратном
направлении по схеме .
При заданном базисе
решение данного класса задач имеет полиноминальную вычислительную сложность.
2.2
Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического
проектирования
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 |