p align="left">Следуя, [112], рассматриваемую - критериальную задачу назовем индивидуальной, если все ее параметры имеют фиксированные значения. Говорим о массовой - критериальной задаче или, коротко, о задаче, если для некоторых параметров заданы не фиксированные значения, а диапазоны их изменения. Анализируя приложения той или другой задачи, нетрудно убедиться, что состав критериев ВЦФ обычно меняется. Например, в системах автоматизированного проектирования электронной техники [114-118] возникает многокритериальные задачи на графах, в которых остовное дерево (связывающая сеть) может оценивается такими критериями, как вес, «узкое место» (минимаксный критерий), степень, диаметр и т.д. [119,120]. При этом по мере необходимости эти критерии входят в состав ВЦФ в разнообразных комбинациях, порождая различные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений , каждый элемент которого является связным остовным подграфом данного графа. Используя понятие «задача» как переменное, употребляем для ее обозначения символ [120]. Конкретизируя рассматриваемую задачу, т.е. определяя для нее множество допустимых решений , присваиваем ей общепринятое наименование и собственное, отличающее её от других задач, обозначение . Перечислим рассматриваемые здесь дискретные многокритериальные задачи: 1. - задача о совершенных паросочетаниях, в которой - совершенное паросочетание графа с четным числом вершин ; 2. - задача об остовных деревьях, - остовное дерево связного -вершинного графа; 3. - задача о цепях, - простая цепь между выделенной парой вершин графа ; 4. - задача о коммивояжере, - гамильтонов цикл в -вершинном графе; 5. - задача о покрытии -вершинного графа цепями, - остовной подграф, компонентами связности которого являются простые цепи, причем покрытие может представлять собой либо совершенное паросочетание, либо трисочетание, либо состоять из 2- и 3-вершинных цепей. 6. - задача о назначениях, т.е. задача о совершенных паросочетаниях на двудольном графе , , - совершенное паросочетание на . Таким образом, решение многокритериальных задач ДП весьма сложно в вычислительном отношении, о чем свидетельствует результаты исследований. По мере развития моделей и методов дискретного программирования, постановки новых задач и других приложений появляется необходимость разработки новых подходов моделей и методов решения задач. 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), которые зависят от переменной . Функционал вида можно представить следующим образом: (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). Матричная форма постановки блочно-симметричных задач позволяет использовать аппарат теории матриц и разрабатывать эффективные алгоритмы решения задач этого класса.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
|