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

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

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

На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n<^>6), где n - число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125.

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

Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, в среднем не превышающую О(2<^>0,4n), которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n - число вершин графа.

Предложен алгоритм решения k-SAT-задачи в среднем за полиномиальное время и 3-SAT-задачи за полиномиальное время. Предлагаемый метод позволяет существенно сократить время решения SAT-задач.

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

Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основании сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей O(mn<^>2), где в случае решения ЗНВП в произвольных графах n - число вершин, а m - число ребер в графе, а в случае решения ЗНП n - число столбцов, а m - число строк в матрице B. Показано, что погрешность решения этих задач предложенными процедурами A1 и A2 не превышает 5 % при плотности строк матрицы B, равной 0,5 и более. Предложенные алгоритмы можно использовать для эффективного планирования распределения ресурсов в GRID-системах в масштабе реального времени при достаточно жестких ограничениях на время решения задач, если допустимое время планирования находится в диапазоне от 5 до 100 мс.

Розглянуто метод побудови точних і наближених розв'язків задачі про мінімальне покриття на основі рангового підходу в дискретному просторі станів. Показано, що даний метод у ряді випадків дозволяє отримати точні розв'язки задачі про мінімальне покриття протягом поліноміального часу.

Запропоновано алгоритми визначення мінімальних вершинних покриттів та максимальних незалежних множин у довільних графах для випадків зважених та незважених вершин, які мають поліноміальну часову складність.

Запропоновано алгоритм поліноміальной складності для розв'язування задачі три-виконуваність.

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

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

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

Показано, что SAT-задачу (satisfiability problem) нельзя считать универсальной NP-полной задачей, а следовательно, вопрос о существовании хотя бы одной NP-полной задачи остается открытым, чем объясняется безуспешность попыток установить взаимосвязь между классами P и NP.

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

Дано обоснование машинного доказательства гипотезы о четырех красках, выполненного группой математиков, возглавляемой К. Аппелем и В. Хейкеном.

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

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