КиСА | Содержание

Том 49>№ 2 МАРТ — АПРЕЛЬ 2013

УДК 519.85

Емец O.А., Емец Е.М., Парфенова Т.А., Чиликин Т.В.

РЕШЕНИЕ ЛИНЕЙНЫХ УСЛОВНЫХ ПОЛНОСТЬЮ КОМБИНАТОРНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ НА ПЕРЕСТАНОВКАХ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ

Аннотация. Рассмотрена условная линейная полностью комбинаторная задача минимизации на перестановках. Предложены способы ветвления, отсечения и оценки в методе ветвей и границ для этой задачи. Приведен иллюстративный пример применения метода к задаче. Доказано свойство предложенной оценки допустимого подмножества, которая увеличивает эффективность ветвлений и отсечений.

Ключевые слова: комбинаторная оптимизация, перестановки, метод ветвлений и отсечений.

ПОЛНЫЙ ТЕКСТ

Емец Олег Алексеевич,
доктор физ.-мат. наук, профессор, заведующий кафедрой Полтавского университета экономики и торговли,
e-mail: yemetsli@mail.ru.

Емец Елизавета Михайловна,
кандидат физ.-мат. наук, доцент Полтавского университета экономики и торговли,
e-mail: yemetsli@mail.ru.

Парфёнова Татьяна Александровна,
кандидат физ.-мат. наук, доцент Полтавского университета экономики и торговли,
e-mail: tapa@mail.ru.

Чиликина Татьяна Васильевна,
кандидат физ.-мат. наук, доцент, старший преподаватель Полтавского университета экономики и торговли,
e-mail: tv0502@gmail.com.