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

• Published in: Кибернетика и системный анализ
• Date: 2013
• Main Authors: Емец, О.А., Емец, Е.М., Парфёнова, Т.А., Чиликина, Т.В.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
• Subjects: Системный анализ
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/86221
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 121-138. — Бібліогр.: 18 назв. — рос.

Розглянуто умовну лінійну повністю комбінаторну задачу мінімізації на переставленнях. Запропоновано способи галуження, відсікання та оцінювання в методі гілок та меж для цієї задачі. Наведено ілюстративний приклад застосування методу до задачі. Доведено властивість запропонованої оцінки допустимої підмножини, яка збільшує ефективність галужень та відсікань. A conditional linear fully combinatorial minimization problem on permutations is analyzed. The methods of branching, cutting, and estimating in the branch and bound method are proposed for this problem. An illustrative example of applying the method to the problem is presented. The property of the proposed estimation of the feasible subset, which increases the efficiency of branching and cutting, is proved.