Том 323 № 5 (2013): Управление, вычислительная техника и информатика
Задача определения минимального числа станций для подключения терминальных точек объекта управления
Актуальность исследования обусловлена широким распространением распределенных систем реального времени и необходимостью разработки методов автоматизированного проектирования таких систем. Целью работы является разработка метода определения минимального числа станций компьютерной сети, способных подключить заданное множество терминальных точек объекта управления. Методы исследования используют достижения в области линейного программирования с целочисленными и булевыми переменными. Результаты исследования. Задача выбора минимального числа станций, способных подключить заданную совокупность терминальных точек объекта управления, сформулирована как задача целочисленного линейного программирования. Выделены особенности, которыми обладает данная задача для рассматриваемой области применения. Учитывая эти особенности, разработан метод, который является более эффективным в сравнении с существующими методами решения задач целочисленного программирования. Метод позволяет локализовать поиск оптимального решения среди вершин единичного гиперкуба, используя для этой цели процедуру симплекс-метода.
Ключевые слова:
целочисленное линейное программирование, целочисленные покрытия, целочисленные задачи, симплекс-метод, булевские покрытия