49743 (588672), страница 8
Текст из файла (страница 8)
Используя понятие «задача» как переменное, употребляем для ее обозначения символ [120]. Конкретизируя рассматриваемую задачу, т.е. определяя для нее множество допустимых решений
, присваиваем ей общепринятое наименование и собственное, отличающее её от других задач, обозначение
.
Перечислим рассматриваемые здесь дискретные многокритериальные задачи:
-
- задача о совершенных паросочетаниях, в которой
- совершенное паросочетание графа
с четным числом вершин
;
-
- задача об остовных деревьях,
- остовное дерево связного
-вершинного графа;
-
- задача о цепях,
- простая цепь между выделенной парой вершин
графа
;
-
- задача о коммивояжере,
- гамильтонов цикл в
-вершинном графе;
-
- задача о покрытии
-вершинного графа цепями,
- остовной подграф, компонентами связности которого являются простые цепи, причем покрытие
может представлять собой либо совершенное паросочетание, либо трисочетание, либо состоять из 2- и 3-вершинных цепей.
-
- задача о назначениях, т.е. задача о совершенных паросочетаниях на двудольном графе
,
,
- совершенное паросочетание на
.
Таким образом, решение многокритериальных задач ДП весьма сложно в вычислительном отношении, о чем свидетельствует результаты исследований.
По мере развития моделей и методов дискретного программирования, постановки новых задач и других приложений появляется необходимость разработки новых подходов моделей и методов решения задач.
1.3 Постановка задачи исследования
Проектирование систем обработки данных многоэтапный и длительный процесс в зависимости от сложности проектируемой информационной системы.
В настоящее время в процессе проектирования СОД широко используются системы управления базами данных (СУБД), система автоматизации процесса проектирования программного и информационного обеспечения и множество других вспомогательных инструментальных средств. Вместе с тем процесс проектирования систем обработки данных остается творческим процессом, зависящим от опыта знаний и способностей разработчиков. При этом наиболее сложным и длительным является разработка прикладного программного и информационного обеспечения систем обработки данных.
Как показал анализ известных исследований наиболее эффективным подходом является разработка формализованных моделей и методов проектирования модульных систем, обеспечивающее качественную и ускоренную разработку таких систем. Принцип модульности предполагает декомпозицию сложных систем на отдельные части (модули) на основе заданных критериев эффективности.
В данной работе необходимо разработать формализованные модели, методы, алгоритмы и программные средства проектирования модульных систем обработки данных на основе новых подходов.
Одним из этапов проектирования систем обработки данных является определение переченя и последовательности решения функциональных (прикладных) задач обработки данных и состава исходных документов, в которых содержится необходимая входная информация (информационные элементы) и установленные взаимосвязи между ними.
При большом числе прикладных задач и требуемых для их решения исходных документов, появляется необходимость декомпозиции этой структуры с целью разделения ее на слабосвязанные фрагменты для облегчения процесса проектирования.
В последующем каждый фрагмент представляется в виде множества процедур обработки данных и взаимосвязанным с ними информационных элементов. На этом этапе необходимо сформулировать структуру модульной системы обработки данных, представляющую собой совокупность процедур обработки данных, объединенных в модули и совокупности информационных элементов, объединены в массивы (таблицы) базы данных и установить между ними оптимальные взаимосвязи.
Необходимо обосновать и выбрать критерии оптимизации в процессе формализованного проектирования систем обработки данных.
Большие размерности задач, решаемые на каждом этапе проектирования обусловливают необходимость исследования и разработки новых подходов, моделей, методов и алгоритмов проектирования систем обработки данных.
Одним из новых направлении постановки и решения задач эффективного проектирования СОД являются блочно-симметричные модели и методы, которые позволяют решать задачи большой размерности. Разработка и развитие этих методов является весьма актуальной проблемой.
В процессе проектирования СОД возникает необходимость учета вектора критериев оптимизации, которые часто бывают противоречивым.
В этом случае решается многокритериальная задача дискретного программирования, алгоритмы решения которых являются сложными и требуют новых подходов.
Анализ существующих методов проектирования модульных систем обработки данных (МСОД), алгоритмов реализации этих моделей и проведенные исследования показали необходимость разработки новых подходов и классов моделей и методов проектирования систем обработки данных.
На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.
Необходимо разработать взаимосвязанный комплекс моделей и методов, алгоритмов и программ формализованного проектирования систем обработки данных, включающий следующие задачи:
-разработать общую блочно-симметричную модель проектирования систем обработки данных;
- сформулировать и решить задачу декомпозиции систем обработки данных на кластеры функциональных задач и исходных документов;
- разработать методы синтеза модульных блок-схем обработки данных;
- разработать многокритериальные блочно-симметричные модели и методы проектирования модульных блок-схем обработки данных;
- разработать подход, эффективные методы и алгоритмы решения блочно-симметричных задач и программное обеспечение.
Выводы к разделу 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), которые зависят от переменной
.
Функционал вида можно представить следующим образом: