Дипломная работа: Блочно-симметричные модели и методы проектирования систем обработки данных

Математическая постановка – критериальной задачи предпологает, что задано множество допустимых решений , на котором определена векторная целевая функция (ВЦФ) [98,99].

,(1.2.4)

Причем критерии ВЦФ считаем минимизируемыми:

Fv(x)→min, v=1,2,…,N.(1.2.5)

Элемент  называется Парето-оптимальным, если не существует такого допустимого решения , что выполняются неравенства , v=1, 2,…, N, среди которых хотя бы одно является строгим.

Через  обозначаем паретовское множество (ПМ), состоящее из всех Парето-оптимальных элементов рассматриваемой задачи с ВЦФ (1) на множестве . Эта задача называется дискретной, если мощность  множества ее допустимых решений конечна.

Первоначальная формулировка проблемы многокритериальной (векторной) оптимизации восходит к [98, 99] и состоит в нахождении одного или всех элементов ПМ . Заметим, что в однокритериальном случае () ПМ  представляет собой множество всех оптимумов данной оптимизационной задачи. Для последней, однако, более естественной является проблема нахождения какого-либо («первого попавшегося») оптимума. Как обобщение этой проблемы для многокритериального случая в настоящей работе в качестве основной рассматриваем проблему нахождения полного множества альтернатив (ПМА). Подмножество  назовем ПМА, если оно удовлетворяет двум условиям: его мощность  минимально и выполняется , где , где

.

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

В системном моделировании, в частности, в теорий выбора и принятия решений наиболее распространенными способами нахождения МА являются следующие.

1.  Построение (определение) детерминированного формального механизма, позволяющего генерировать альтернативы с помощью параметров алгоритма или с помощью параметров формулы . [100-103]

2.  Представление МА в неявном виде с помощью системы соотношений (ограничений ). [104-105]

3.  Перечисление всех элементов МА, т.е. представление каждого элемента МА в явном виде. [108, 109]

В работе [121], именно в контексте алгоритмической проблемы, относящейся к последнему из указанных выше трех способов, осуществляется обоснование оценок мощности МА для таких многокритериальных дискретных задач, как задачи о совершенных паросочетаниях, о коммивояжере, о цепях между парой вершин и другие при этом нахождение МА понимается как перечисления с предъявлением всех его элементов [110, 100]. При определенных условиях нижние оценки мощности ПМ и ПМА перечисленных задач оказывается экспоненциальным. Последнее означает, что для рассматриваемых задач проблема нахождения МА является труднорешаемой [110,111]. Или (в терминологии [112,113]) она имеет экспоненциальную вычислительную сложность.

Следуя, [112], рассматриваемую - критериальную задачу назовем индивидуальной, если все ее параметры имеют фиксированные значения. Говорим о массовой  - критериальной задаче или, коротко, о задаче, если для некоторых параметров заданы не фиксированные значения, а диапазоны их изменения.

Анализируя приложения той или другой задачи, нетрудно убедиться, что состав критериев ВЦФ обычно меняется. Например, в системах автоматизированного проектирования электронной техники [114-118] возникает многокритериальные задачи на графах, в которых остовное дерево (связывающая сеть) может оценивается такими критериями, как вес, «узкое место» (минимаксный критерий), степень, диаметр и т.д. [119,120]. При этом по мере необходимости эти критерии входят в состав ВЦФ в разнообразных комбинациях, порождая различные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений , каждый элемент  которого является связным остовным подграфом данного графа.

Используя понятие «задача» как переменное, употребляем для ее обозначения символ  [120]. Конкретизируя рассматриваемую задачу, т.е. определяя для нее множество допустимых решений , присваиваем ей общепринятое наименование и собственное, отличающее её от других задач, обозначение .

Перечислим рассматриваемые здесь дискретные многокритериальные задачи:

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

2.   - задача об остовных деревьях,  - остовное дерево связного -вершинного графа;

3.   - задача о цепях,  - простая цепь между выделенной парой вершин  графа ;

4.   - задача о коммивояжере,  - гамильтонов цикл в -вершинном графе;

5.   - задача о покрытии -вершинного графа цепями,  - остовной подграф, компонентами связности которого являются простые цепи, причем покрытие  может представлять собой либо совершенное паросочетание, либо трисочетание, либо состоять из 2- и 3-вершинных цепей.

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

Таким образом, решение многокритериальных задач ДП весьма сложно в вычислительном отношении, о чем свидетельствует результаты исследований.

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

1.3 Постановка задачи исследования

Проектирование систем обработки данных многоэтапный и длительный процесс в зависимости от сложности проектируемой информационной системы.

В настоящее время в процессе проектирования СОД широко используются системы управления базами данных (СУБД), система автоматизации процесса проектирования программного и информационного обеспечения и множество других вспомогательных инструментальных средств. Вместе с тем процесс проектирования систем обработки данных остается творческим процессом, зависящим от опыта знаний и способностей разработчиков. При этом наиболее сложным и длительным является разработка прикладного программного и информационного обеспечения систем обработки данных.

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21