Основные направления
Тематика исследований:
Направление 1. «Распределение ресурсов в сетевых канонических, иерархических и стохастических структурах»
Научный руководитель: д.т.н., профессор М. Х. Прилуцкий
Аннотация
Рассматривается широкий класс задач распределения ресурсов в сетевых канонических, иерархических и стохастических структурах.
Канонические структуры позволят моделировать процессы проектирования и изготовления сложных изделий. Построены математические модели, в рамках которых поставлены различные оптимизационные задачи. Математические модели учитывают различные представления исходных параметров — скалярное, интервальное, нечеткое. Проведено исследование построенных моделей, которое позволило синтезировать алгоритмы, дающие возможность решать широкий класс большеразмерных задач распределения ресурсов при изготовлении и проектировании сложных изделий.
Иерархические структуры позволят моделировать процессы распределения ограниченных ресурсов в многоуровневых системах. Элементы системы могут либо производить, либо передавать, либо потреблять однородный или разнородные ресурсы. Предполагается, что объемы ресурсов, соответствующих элементам системы, в общем случае ограничены как минимальными, так и максимальными величинами. Учитываются и интервальные ограничения на объемы ресурса, передаваемого от одних элементов системы к другим. Требуется определить такие объемы производимого, передающего и потребляемого ресурса, которые удовлетворяют интервальным ограничениям элементов системы, и соответствуют экстремальным значениям различных критериев оптимальности. В рамках построенной общей математической модели ставятся различные оптимизационные задачи, такие как: задача распределения ресурсов при проектировании сложных изделий; задача объемно-календарного планирования; задача распределения информационного ресурса в сети провайдера; задача разузлования, возникающая при проектировании производства сложных изделий; задача распределения энергоресурсов между потребителями и поставщиками; задачи бюджетирования и др.
В рамках стохастических сетевых структур рассматриваются проблемы оптимального планирования и управления некоторым классом производственных систем, функционирующих в условиях неопределенности. Строятся математические модели, даются постановки оптимизационных задач планирования и управления, предлагаются эффективные алгоритмы их решения. В качестве математических моделей, адекватных анализируемым производственным системам, выбраны управляемые однородные марковские цепи с конечным числом состояний и доходами. В рамках построенных математических моделей исследуются и решаются как задачи оптимального управления (классы управлений: общий, программный, рандомизированный), так и задачи оптимального планирования (календарное и объемно-календарное планирование).
Направление 2. «Экстремальные задачи на графах и методы их решения на высокопроизводительных вычислительных системах»
Научный руководитель: д.т.н., доцент Н. В. Старостин
Аннотация
В различных сферах деятельности человека возникают разнообразные задачи, которые можно свести к экстремальным задачам на графах. Как правило, подобрать алгоритм, пригодный для практического использования, становится непростой проблемой. Большой удачей считается свести прикладную задачу к известной полиноминально разрешимой задаче. На практике большинство прикладных задач оказываются NP-трудными. Кроме того нередки случаи, когда особенности прикладной сферы отражаются в появлении специфических ограничений и критериев в задачи, что не позволяет для ее решения использовать известные и хорошо себя зарекомендовавшие алгоритмы.
Другой серьезной проблемой является размерность графов, возникающих из прикладной области. Так, например, граф сетки трассировки в прикладной задаче топологического синтеза даже для небольших по современным меркам интегральных схем достигает нескольких миллионов вершин. При численном решении задач математической физики на распределенных вычислительных системах число элементов в графе сетки, аппроксимирующей расчетную область, может превышать 10 миллиардов элементов!
К самим алгоритмам и их программным реализациям нередко предъявляются особые требования, вытекающие из специфики процессов прикладной сферы. Традиционными являются ограничения по вычислительным издержкам. Нередко предполагается интеграция разрабатываемых программных решений в существующие системы, что приводит к значительному ограничению в выборе программных средств и инструментов, используемых для реализации алгоритмов. Для задач сверхбольших порядков приходится работать с распределенными данными, это требуется учитывать в алгоритмах и их программных реализациях.
Для решения экстремальных задач на графах развиваются многоуровневые методы. В их основе лежит концепция последовательной редукции исходной задачи, при этом поиск решения осуществляется на редуцированной версии задачи, а само решение в дальнейшем последовательно проецируется на исходную задачу. Многоуровневая парадигма допускает тесную интеграцию с другими подходами, предоставляя возможность комбинировать алгоритмы в гибридных схемах. Концепция многоуровневости не входит в противоречие с распределенной моделью представления графов, что позволяет успешно создавать параллельные версии алгоритмов на распределенной памяти.
Направление 3. «Построение и исследование приближенно-оптимальных алгоритмов, изучение условий оптимальности для некоторых классов экстремальных задач»
Научный руководитель: к.ф.м.н., доцент А. Г. Коротченко
Аннотация
Тематика научных исследований связана с построением и исследованием приближенно-оптимальных алгоритмов поиска экстремума для новых классов задач оптимизации, в том числе и многокритериальных.
Интерес к подобного рода исследованиям обусловлен с одной стороны тем обстоятельством, что при решении сложных задач оптимизации является важным использование эффективных процедур, а с другой стороны оптимальные по тому или иному критерию алгоритмы являются достаточно сложными в своей реализации. Поэтому в число требований, предъявляемых к алгоритму при его построении, естественно включать требования, связанные с простотой в реализации алгоритма. Решены и находятся в стадии решения задачи построения подобного рода алгоритмов, в том числе и параллельных, для классов функций, определяемых заданными мажорантами, для классов, возникающих при рассмотрении многошаговых процедур оптимизации, классов задач поиска экстремума, в которых требуется распределить заданный ресурс по этапам вычислений.
В последнее время рассматриваются задачи оптимизации специального вида, характерной особенностью которых является их многоэтапность. Такие задачи возникают, например, при распределении ресурсов различной природы, при построении формул численного интегрирования систем обыкновенных дифференциальных уравнений. Указанные задачи формулируются на языке перевода некоторой многошаговой системы из заданного начального состояния в априори неизвестное конечное состояние, определяемое в процессе ее функционирования таким образом, чтобы минимизировать число промежуточных состояний системы, если множество ее возможных состояний на каждом шаге задается с помощью точечно – множественного отображения. Для возникающих при этом некоторых классов экстремальных задач установлены достаточные условия, гарантирующие выполнение сформулированных выше требований. Рассматриваются новые классы подобного рода задач оптимизации.
Исследования проводились в рамках грантов РФФИ. По тематике исследований выполняются курсовые, дипломные, магистерские работы студентов и работы аспирантов.
Направление 4. «Модели и методы интеллектуальной поддержки процессов принятия решений»
Научный руководитель: к.т.н., доцент П. Д. Басалин
Аннотация
Тематика научных исследований связана с разработкой и исследованием моделей представления знаний, механизмов их приобретения (выявления) и интерпретации, базирующихся на концепции системы, основанной на знаниях. Рассматриваются вопросы построения и исследования оригинальных архитектур искусственных нейронных сетей и эффективных моделей их обучения, построения моделей нечеткого вывода на знаниях продукционного типа и представление их в нейросетевом базисе, разработки принципов организации и функционирования гибридных средств интеллектуальной поддержки, сочетающих в себе модели и методы концепции системы, основанной на знаниях, и нейросетевые технологии принятия решений в задачах трудноформализуемого и неформального плана, создания конкретных архитектур оболочек гибридных систем интеллектуальной поддержки процессов принятия решений, представления и решения конкретных прикладных задач в нейросетевом и смешанном базисах. По тематике направления выполняются курсовые, дипломные и магистерские диссертационные работы студентов, а также диссертационные работы аспирантов и соискателей. Конкретное практическое применение нашли следующие разработки:
• Система интеллектуальной поддержки этапа размещения ПТС в пунктах управления АЭС с выполнением требований эргономики (использована в разработках НИИИС им. Ю.Е. Седакова для ряда российских и зарубежных атомных электростанций)
• Синтез схем произвольной комбинационной логики в нейросетевом базисе (внедрение в НИИИС им. Ю.Е. Седакова)
• Оболочка гибридной системы интеллектуальной поддержки процессов принятия решений, способная через формализм базы знаний настраиваться на различные предметные (проблемные) области (проходит опытную эксплуатацию).
Направление 5. «Потоковые методы решения многоиндексных задач транспортного типа»
Научный руководитель: д.ф.-м.н., профессор Л. Г. Афраймович
Аннотация
Существует широкий класс прикладных задач, формализуемых в виде многоиндексных задач (целочисленного) линейного программирования транспортного типа. Примерами таких задач являются задачи распределения ресурсов в иерархических системах: задача объемно- календарного планирования, задача формирования портфеля заказов, задача переработки газового конденсата, задача распределения мощностей каналов передачи данных, транспортная задача с промежуточными пунктами и др. Многоиндексные задачи транспортного типа возникают также в области статистики и в смежной области защиты статистических данных, в задаче целочисленного сбалансирования многоиндексных матриц. Многоиндексные задачи о назначениях (подкласс многоиндексных транспортных задач целочисленного линейного программирования) возникают в теории расписаний при планировании изготовления скоропортящейся продукции, при планировании прохождения практики студентами, при планировании учебы клинических ординаторов по отделениям, при составлении расписания занятий, при планировании спортивных матчей и др.; в области технического анализа данных при сопровождении объектов в многосенсорных системах; в военной области при назначении военной техники на цели. Известны результаты, посвященные исследованию вопросов сводимости задач линейного и целочисленного линейного программирования к многоиндексным транспортным задачам, что также расширяет область применения методов решения многоиндексных задач.
В общем случае для решения многоиндексных задачи линейного программирования транспортного типа применимы общие методы исследований задач линейного программирования (например, симплекс метод, алгоритм Кармаркара). Особый интерес представляет исследования целочисленных задач. Однако в общей постановке класс целочисленных многоиндексных транспортных задач является NP-трудным уже в трехиндексном случае. Более того для задач данного класса не существует полиномиальных e -приближенных алгоритмов, иначе P=NP, данный результат также справедлив уже в трехиндексном случае. При отсутствии дополнительных ограничений на параметры для решения многоиндексных задач целочисленного линейного программирования транспортного типа применимы лишь экспоненциальные по верхней оценке вычислительной сложности общие методы целочисленного линейного программирования (например, метод динамического программирования, метод ветвей и границ, метод отсечения Гомори).
Одним из перспективных направлений при разработке эффективных алгоритмов исследования многоиндексных задач линейного программирования является нахождение подклассов задач, для решения которых применимы потоковые методы. Важное влияние на развитие данного направления оказывают активные исследования в области сетевой оптимизации. Существующие эффективные потоковые алгоритмы позволяют в случае сводимости задач линейного программирования к потоковым задачам построить алгоритмы их решения, обладающие более низкими оценками вычислительной сложности по сравнению с оценками общих методов решения задач линейного программирования. Сведение к потоковым задачам также позволяет предложить алгоритмы решения исходной задачи, гарантирующие нахождение целочисленного решения, и тем самым позволяет выделять полиномиально разрешимые подклассы задач в NP-трудном классе задач целочисленного линейного программирования. В ряде случае результаты сводимости к потоковым задачам могут быть применены при построении приближенных сетевых подходов к решению NP-трудных целочисленных многоиндексных задач.