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

Блочно-симметричные модели и методы проектирования систем обработки данных
МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ Модели и методы решения задач дискретного программирования при проектировании систем обработки данных На основе выбранного значения оценок вычисляются допустимые решения; Постановка задачи исследования Общая постановка блочно-симметричных задач дискретного программирования Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического проектирования Проектирование модульных блок-схем систем обработки данных Частные задачи проектирования модульных блок-схем систем обработки данных Эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок-схем обработки данных Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных Кульба В.В., Мамиконов А.Г. Синтез оптимальных модульных СОД.М.:Наука, 1986
158931
знак
0
таблиц
1
изображение

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

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

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

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

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

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

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

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

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

Математическая постановка – критериальной задачи предпологает, что задано множество допустимых решений , на котором определена векторная целевая функция (ВЦФ) [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.   - задача о назначениях, т.е. задача о совершенных паросочетаниях на двудольном графе , ,  - совершенное паросочетание на .

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

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


Информация о работе «Блочно-симметричные модели и методы проектирования систем обработки данных»
Раздел: Информатика, программирование
Количество знаков с пробелами: 158931
Количество таблиц: 0
Количество изображений: 1

Похожие работы

Скачать
448518
14
55

... также невысока и обычно составляет около 100 кбайт/с. НКМЛ могут использовать локальные интерфейсы SCSI. Лекция 3. Программное обеспечение ПЭВМ 3.1 Общая характеристика и состав программного обеспечения 3.1.1 Состав и назначение программного обеспечения Процесс взаимодействия человека с компьютером организуется устройством управления в соответствии с той программой, которую пользователь ...

Скачать
308601
37
3

... производительных сил, тем быстрее повышается Б. населения. В еще большей степени Б. связано с эффективностью социально-экономической политики в данном обществе. Информатика как наука. Предмет и объект прикладной информатики. Системы счисления Инфоpматика — это основанная на использовании компьютерной техники дисциплина, изучающая структуру и общие свойства информации, а также закономерности и ...

Скачать
113309
0
0

... . Особо стоит отметить наличие в СЗИ защиты загрузки операционной системы с гибких магнитных дисков и CD-ROM, которая обеспечивает защиту самих средств защиты от "взлома" с использованием специальных технологий. В различных СЗИ существуют программные и аппаратно-программные реализации этой защиты, однако практика показывает, что программная реализация не обеспечивает необходимой стойкости. ...

Скачать
129027
5
16

... разных этапах производства (потребления) электроэнергии. Основная цель создания таких систем – дальнейшеё повышение эффективности технических и программных средств автоматизации и диспетчеризации СЭС для улучшения технико-экономических показателей и повышения качества и надёжности электроснабжения ПП. Реформирование электроэнергетики России требует создания полномасштабных иерархических систем ...

0 комментариев


Наверх