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

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