Метод упорядочения значений линейной функции на множестве перестановок

• Published in: Кибернетика и системный анализ
• Date: 2009
• Main Authors: Донец, Г.А., Колечкина, Л.Н.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2009
• Subjects: Системный анализ
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/44342
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Метод упорядочения значений линейной функции на множестве перестановок / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2009. — № 2. — С. 50-61. — Бібліогр.: 9 назв. — рос.

Стаття присвячена новому методу, який дає можливiсть знайти розв’язок комбiнаторної задачi, враховуючи властивостi i структуру множини перестановок, на якiй розглянуто задачу. Описано побудову послiдовностi значень лiнiйної цiльової функцiї, розклад точок множини перестановок по гiперплощинах та їх залежнiсть. Це дозволяє побудувати алгоритм знаходження точки — елемента множини перестановок, в якiй досягається задане значення цiльової функцiї. The paper deals with the new method of solving a combinatorial problem with account for the properties of the set of permutations and its structure. Using this method, the values of the linear objective function are sequenced and the set of permutations is decomposed over hyperplanes, with account for element recurrences. This makes it possible to develop an algorithm of finding the point (an element of the set of permutations) at which the objective function attains a given value.