Задача определения минимального числа станций для подключения терминальных точек объекта управления

Abstract

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

The relevance of the research is caused by a wide spreading of real time systems and by the necessity to develop the computer-aided design techniques for such systems. The aim of the research is to develop the technique for determining minimum number of computer network stations which are capable of connecting the set of terminal points of a control object. The author has used the achievements in the field of linear programming with integer and Boolean variables. The task of selection of minimum number of stations connecting the given set of terminal points of the control object was stated as the integer linear programming. The author singled out this task features for the field of application under consideration. Taking into account these features the methods was developed. It is more efficient than the existing methods for solving the integer programming problems. The method allows locating the search for optimal solution among the vertices of unit hypercube using the Simplex Method.