Xreferat.com » Рефераты по информатике и программированию » Блочно-симметричные модели и методы проектирования систем обработки данных

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

и методы проектирования систем обработки данных" width="21" height="25" align="BOTTOM" border="0" />, Блочно-симметричные модели и методы проектирования систем обработки данных.

Если Блочно-симметричные модели и методы проектирования систем обработки данных - конечное (или счетное) множество или декартово произведение конечного (счетного) множества на множество мощности континиума, то будет иметь место задача ДП. В этом случае условие принадлежности Блочно-симметричные модели и методы проектирования систем обработки данных некоторому множеству может быть записано в виде:


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

Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных; Блочно-симметричные модели и методы проектирования систем обработки данных; Блочно-симметричные модели и методы проектирования систем обработки данных. (1.2.2)


При Блочно-симметричные модели и методы проектирования систем обработки данных - задача частично дискретного программирования.

Если Блочно-симметричные модели и методы проектирования систем обработки данных- множество всех целочисленных векторов, то при Блочно-симметричные модели и методы проектирования систем обработки данных - имеем задачу целочисленного программирования (ЦП). А при Блочно-симметричные модели и методы проектирования систем обработки данных - задачу частичного целочисленного программирования (ЧЦП).

В наибольшей степени изучены методы решения задач целочисленного линейного программирования (ЦЛП):


Блочно-симметричные модели и методы проектирования систем обработки данных;(1.2.3)


Здесь Блочно-симметричные модели и методы проектирования систем обработки данных - множество всех неотрицательных целых чисел, частный случай задач ЦЛП Блочно-симметричные модели и методы проектирования систем обработки данных задачи с булевыми переменными, где в (1.2.3):


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


В ряде задач ЦП требование целочисленности накладывается и на целевую функцию.

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

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

Обычно эффективное решение задачи тесно связанно с математической моделью задачи, со структурой модели и ее особенностями.

Рассмотрим некоторые математические модели дискретного программирования и методы их решения.

Модели задач ДП. Классическим примером моделей этого класса являются модели целочисленного линейного программирования, в которых переменными являются неделимые величины. Модели этого класса в свою очередь генерировали различные варианты постановки прикладных задач и определены как модели с неделимостями.

В процессе развития теории дискретного программирования выделился класс комбинаторных моделей. [83]

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

Одним из типичных примеров комбинаторной модели является задача о коммивояжере. [84]

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

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

Постановка различных комбинаторных задач может часто формулироваться в виде модели с булевыми переменными, которые принимают только два значения 0 или 1.

К булевым моделям сводятся большое число прикладных задач, что свидетельствует о перспективности моделей этого класса. [85]

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


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

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


Эти модели образуют класс моделей с неоднородной разрывной целевой функцией.

Модели нахождения экстремума на области, задаваемой не только линейными неравенствам (ограничениями) но и логическими условиями. Такие области оказываются невыпуклыми либо несвязными. Эти задачи образуют модели на не классических областях. [84]

Особый интерес исследователей вызывают многоэкстремальные модели, в которых необходимо определить оптимальные значения более одной целевой функции при наличии (либо отсутствии) систем ограничений. Как правило, модели этого класса сложны в вычислительном отношении. Вместе с тем, постановки целого ряда прикладных задач сводятся к моделям данного класса. Решение указанных задач является актуальным. [103, 105, 107]

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

Следует отметить, что разработка моделей тесно связана с методом ее реализации, и наоборот разработка новых методов, в свою очередь, приводит к появлению новых моделей для постановки прикладных задач.

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

Типичным примером комбинаторных методов является метод ветвей и границ [115]. Суть данного метода заключается в направленном переборе допустимых решений на основе вычисления оценок. Основное этапы подхода заключается в следующем:

Исходное множество решений Блочно-симметричные модели и методы проектирования систем обработки данных разбиваются не подмножества Блочно-симметричные модели и методы проектирования систем обработки данных (процесс ветвления);

Для каждого из подмножеств Блочно-симметричные модели и методы проектирования систем обработки данных вычисляется значения оценок (нижние или верхние границы);

На основе выбранного значения оценок вычисляются допустимые решения;

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

Идея метода отсечений заключается в следующем. Решается исходная задача. Если полученное решение удовлетворяет условию целочисленности, то задача решена. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение. Далее решается задача с дополнительно введенным ограничением. Итеративный процесс повторяется, до тех пор, пока не будет получено целочисленное решение.

Примерами успешной реализации методов отсечения являются алгоритмы Гомори [83] .

Вместе с тем, следует отметить ограниченное использование точных методов для решения прикладных задач большой размерности. Несмотря на использование мощных вычислительных систем с большой памятью, совершенствование и развитие математического аппарата «проклятье дискретности» остается и на сегодняшний день.

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

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

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

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

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


Блочно-симметричные модели и методы проектирования систем обработки данных,(1.2.4)


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


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


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

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

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

Блочно-симметричные модели и методы проектирования систем обработки данных - задача о коммивояжере, Блочно-симметричные модели и методы проектирования систем обработки данных - гамильтонов цикл в Блочно-симметричные модели и методы проектирования систем обработки данных-вершинном графе;

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

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

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

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


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


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

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

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

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

Одним из этапов проектирования систем обработки данных является определение переченя и последовательности решения функциональных (прикладных) задач обработки данных и состава исходных документов, в которых содержится необходимая входная информация (информационные элементы) и установленные взаимосвязи между ними.

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

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

Необходимо обосновать и выбрать критерии оптимизации в процессе формализованного проектирования систем обработки данных.

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

Одним из новых направлении постановки и решения задач эффективного проектирования СОД являются блочно-симметричные модели и методы, которые позволяют решать задачи большой размерности. Разработка и развитие этих методов является весьма актуальной проблемой.

В процессе проектирования СОД возникает необходимость учета вектора критериев оптимизации, которые часто бывают противоречивым.

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

Анализ существующих методов проектирования модульных систем обработки данных (МСОД), алгоритмов реализации этих моделей и проведенные исследования показали необходимость разработки новых подходов и классов моделей и методов проектирования систем обработки данных.

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

Необходимо разработать взаимосвязанный комплекс моделей и методов, алгоритмов и программ формализованного проектирования систем обработки данных, включающий следующие задачи:

-разработать общую блочно-симметричную модель проектирования систем обработки данных;

- сформулировать и решить задачу декомпозиции систем обработки данных на кластеры функциональных задач и исходных документов;

- разработать методы синтеза модульных блок-схем обработки данных;

- разработать многокритериальные блочно-симметричные модели и методы проектирования модульных блок-схем обработки данных;

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


Выводы к разделу 1


Приведен анализ существующих моделей и методов проектирования модульных систем обработки данных.

Приведен краткий обзор методов и алгоритмов дискретного программирование для решения задач проектирование систем

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: