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

  Повний текст PDF - 456.926 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"