Введение к работе
Актуальность темы. Проблемы, связанные с решением задач большой размерности блочно-модульного типа возникают в самых различных областях практической деятельности - при проектировании сложных технических систем, решении транспортных задач, создании информационно-вычислительных сетей и др.
Большая размерность этих задач не позволяет решать их непосредственно даже с использованием современных математических методов и вычислительной техники. В связи с этим возникает необходимость использования декомпозиционного подхода к их решению. Данный подход в общем случае заключается в разбиении процесса решения большой задачи на серию процессов решения меньших задач. Эти задачи обычно разделяются на два типа: блочные задачи, которые могут решаться независимо друг от друга и координирующая задача, которая позволяет осуществлять связь между ними.
При данном подходе возникает проблема организации ,процесса вычислений, обеспечивающего решение задачи при возможно меньшем числе тактов координации между подсистемами-блоками. Весьма актуальной поэтому является проблема изучения вычислительной сложности задач координации, а также разработка эффективных алгоритмов их решения.
Цель работы:
анализ применимости эффективных методов выпуклой оптимизации для решения задач математического программирования на основе декомпозиционного подхода;
разработка схемы декомпозиции для одного из подклассов таких задач - задач оптимального проектирования;
разработка и исследование эффективных методов и процедур решения координирующих задач, их программная реализация.
Научная новизна:
исследованы возможности применения современных методов выпуклого программирования при декомпозиционном подходе к решению задач большой размерности блочно-модульного типа;.
предложена аффинно инвариантная псевдометрика позволяющая удобно описывать свойства выпуклых компактов, используемые для оценки результативности методов выпуклого программирования;
разработан эффективный метод решения задач выпуклого программирования, для него получена теоретическая оценка необходимого числа итераций;
предложена схема декомпозиции задач математического программирования большой размерности, основанная на решении "задачи оптимальной декомпозиции" и использовании методов отсечений как в однокритериальном, так и в многокритериальном случае.
Практическая ценность. Предложенные в работе алгоритмы были использованы при реализации диалоговой системы выбора и анализа сложных технических систем.
Апробация. Основные положения диссертации рассматривались и обсуждались на семинарах Всесоюзного научно-исследовательского института прикладных автоматизированных систем ГКНТ и АН СССР, на Московской городской конференции "Системы автоматизированного проектирования (САПР-85)", на 5-й Республиканской межведомственной научно-технической конференции "Моделирование и ато-матизация процесов проектирования сложных технических систем", Одесса, 1987, на 14-й конференции IFIP по моделированию систем и оптимизации, Лейпциг (ГДР), 1989, а также на 6-м Международном симпозиуме "Системы - Моделирование - Управление", Закопане (Польша), 1990.
Публикации. По теме диссертации опубликовано семь работ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы составляет 119 страниц, включая 4 страницы списка цитированной литературы, содержащего 3? наименований.
