Блочно-симметричные модели и методы проектирования систем обработки данных
Если
- конечное (или
счетное) множество
или декартово
произведение
конечного
(счетного) множества
на множество
мощности континиума,
то будет иметь
место задача
ДП. В этом случае
условие принадлежности
некоторому
множеству может
быть записано
в виде:
,
;
,
;
;
.
(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
Приведен анализ существующих моделей и методов проектирования модульных систем обработки данных.
Приведен краткий обзор методов и алгоритмов дискретного программирование для решения задач проектирование систем