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

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2013
• Автори: Емец, О.А., Емец, Е.М., Парфёнова, Т.А., Чиликина, Т.В.
• Формат: Стаття
• Мова: Російська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
• Теми: Системный анализ
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/86221
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Решение линейных условных полностью комбинаторных оптимизационных задач на перестановках методом ветвей и границ / О.А. Емец, Е.М. Емец, Т.А. Парфёнова, Т.В. Чиликина // Кибернетика и системный анализ. — 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.