Л.Н. КОЛЕЧКИНА. Обоснование структурированного метода локализации значения линейной функции, заданной на комбинаторной конфигурации перестановок.

УДК 519.1

Л.Н. КОЛЕЧКИНА. Обоснование структурированного метода локализации значения линейной функции, заданной на комбинаторной конфигурации перестановок (русский) // Динамические системы, 2009. — Вып 27. — С. 67–80.

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

Ключевые слова: комбинаторная оптимизация, комбинаторная конфигурация перестановок, граф перестановочного многогранника, подграф графа, структурированный метод локализации.

Табл. 9. Библиогр. 14 назв.

УДК 519.1

Л.М. КОЛЄЧКIНА. Обґрунтування структурованого методу локалiзацiї значення лiнiйної функцiї, заданої на комбiнаторнiй конфiгурацiї перестановок (росiйська) // Динамические системы, 2009. — Вип 27. — С. 67–80.

Розглядається задача комбiнаторної оптимiзацiї на комбiнаторнiй конфiгурацiї перестановок, аналiзуються методи розв’язування таких задач. Описується метод локалiзацiї значення цiльової лiнiйної функцiї на основi застосування теорiї графiв, з огляду на властивостi й структуру множини перестановок. Обґрунтовується побудова послiдовностi значень лiнiйної функцiї, розкладання точок перестановок по пiдграфах графа переставного многогранника i їх використання для реалiзацiї методу.

Ключовi слова: комбiнаторна оптимiзацiя, комбiнаторна конфiгурацiя перестановок, граф переставного многогранника, пiдграф графа, структурований метод локалiзацiї.

Табл. 9. Бiблiогр. 14 назв.

MSC 2010: 90C27, 90C05, 90C06

L.N. KOLECHKINA. Substantiation of the structured method of localization of value of the linear function set on a combinatory configuration of shifts (Russian). Din. Sist., Simferopol’ 27, 67–80 (2009).

The problem of combinatory optimization on a combinatory configuration of shifts is considered, methods of the decision of such problems are analyzed. The method of localization of value of target linear function on the basis of application of the theory of graphs is described, considering properties and structure of set of shifts. Construction of sequence of values of linear function, decomposition of points of shifts on subgraphs of the graph of a permutable polyhedron and their use for method realization is proved.

Keywords: combinatorial optimization, combinatorial configuration of permutations, graph polyhedron of permutations, podgraph graph, structured method of localization.

Tbl. 9. Ref. 14.