Оптимізаційні задачі на переставленнях: метод комбінаторного відсікання з використанням алгоритму Кармаркара
Loading...
Date
2011
Authors
Ємець, Олег
Ємець, Єлизавета
Ольховський, Дмитро
Journal Title
Journal ISSN
Volume Title
Publisher
ВПЦ НаУКМА
Abstract
Останнім часом інтенсивно досліджуються задачі комбінаторної оптимізації, що призводить до розробки нових підходів та методів до їх розв’язування. Актуальною є розробка поліноміальних алгоритмів для розв’язування задач комбінаторної оптимізації. У цьому дослідженні запропоновано використовувати алгоритм Кармаркара у методі комбінаторного відсікання для розв’язування допоміжних задач лінійного програмування. Викладено метод комбінаторного відсікання на основі алгоритму Кармаркара. Сформульовано та доведено теорему про скінченність запропонованого методу.
Description
Combinatorial optimization problems have been intensively researched in recent years, which lead to the development of new approaches and methods to solve these tasks. Important is the development of algorithms for solving combinatorial optimization. Method for solving combinatorial cut-off method of linear programming problems using Karmarkar’s algorithm is proposing in this paper. The article describes the method of combinatorial cut-off based on the Karmarkar algorithm. Formulated and proved a theorem about the finiteness of the proposed method.
Keywords
переставлення, метод комбінаторного відсікання, метод Кармаркара, permutations, combinatorial cut-off method, Karmarkar’s algorithm
Citation
Ємець О. О. Оптимізаційні задачі на переставленнях: метод комбінаторного відсікання з використанням алгоритму Кармаркара / Ємець О. О., Ємець Є. М., Ольховський Д. М. // Наукові записки НаУКМА. - 2011. - Т. 125: Комп'ютерні науки. - С. 61-63.