49743 (588672), страница 9

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

Текст из файла (страница 9)

(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).

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

Свойство 4. Симметричность задачи заключается в возможности вычисления (2.1.11) как слева направо, так и обратном направлении.

Указанные свойства и особенности блочно-симметричных задач ДП позволяют синтезировать алгоритмы, обеспечивающих решение практических задач большой размерности.

В ряде постановок задач функционал (2.1.1) можно представить в виде вектора функций . В этом случае формулируется многокритериальная блочно-симметричная задача дискретного программирования.

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

Утверждение. Распределение элементов множества по непересекающим подмножествам соответствует логическому сложению строк матриц , а распределение элементов множества по непересекающимся подмножествам - логическому сложению столбцов матрицы . [132, 133] Результаты данного утверждения позволяют просто вычислить оценки и направления поиска решения для разработки эффективных алгоритмов.

Введем понятие базиса решения задач. Под базисом понимается заранее заданный состав элементов подмножеств и .

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

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

1. В булевой матрице выделим подматрицу , , и определим её как базис решения задачи.

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

3. В соответствии с полученными оценками осуществим распределение элементов множества по множествам . В результате зафиксируем решение и промежуточную. Матрицу , , .

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

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

6. Следует отметить, что поиск решения задачи может осуществляться как в прямом направлении по схеме , так и в обратном направлении по схеме .

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

2.2 Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического проектирования

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

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

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

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

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

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

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

Аналогично введём переменную

, , , где

В ряде случаев на данном этапе определяются характеристики задач и документов.

Введем - время разработки -ой задачи, - объем -ого документа, - общая стоимость разработки -ой задачи и -го документа, - время разработки и подготовки -го документа, -стоимость разработки -ой задачи, - стоимость подготовки -го документа.

Характеристики

Список файлов ВКР