Метод ветвей и границ для решения задачи о линейном порядке на взвешенных турнирах

В турнире, дугам которого приписаны неотрицательные веса, требуется найти множество дуг с минимальным суммарным весом, смена ориентации которых преобразует исходный турнир в транзитивный. Для решения этой задачи предлагается новый вариант метода ветвей и границ. При вычислении нижних оценок целевой функции используется техника лагранжевых релаксаций. Верхние оценки находятся с помощью метода шума. Приводятся результаты численного эксперимента на турнирах, содержащих не более 100 вершин. Табл. 1, ил. 7, библиогр. 32.