Математичне моделювання практичних задач у вигляді лінійних задач на переставленнях та їх розв’язання з застосуванням властивостей комбінаторних многогранників

Abstract

В роботі дано огляд сучасних підходів до розв’язання умовних лінійних задач на комбінаторних множинах. Особливу увагуприділено дослідженню допустимих областей переставних многогранників з додатковими обмеженнями спеціальноговигляду. Показано, що в окремих випадках додаткове дослідження допустимої області дозволяє зменшити вимірність задачі,перейти від розгляду переставних многогранників з обмеженнями до поліпереставних без обмежень, знаходити розв’язкиумовних задач без використання методів лінійного або дискретного лінійного програмування. Побудовано математичнумодель однієї задачі розміщення виробництва у вигляді лінійної задачі на переставленнях з додатковими обмеженнями, дорозв’язання якої пропонується застосовувати викладені підходи. Бібліогр.: 10 назв.

В работе дан обзор современных подходов к решению условных линейных задач на комбинаторных множествах. Особоевнимание уделено исследованию допустимых областей перестановочных многогранников с дополнительнымиограничениями специального вида. Показано, что в отдельных случаях дополнительное исследование допустимой областипозволяет уменьшить размерность задачи, перейти от рассмотрения перестановочных многогранников с ограничениями кполиперестановочным без ограничений, находить решения условных задач без использования методов линейного илидискретного линейного программирования. Построена математическая модель одной задачи размещения производства ввиде линейной задачи на перестановках с дополнительными ограничениями, к решению которой предлагается применятьизложенные подходы. Библиогр.: 10 назв.

At the article a review of modern approaches to solution of linear optimization problems with constraints on combinatorial sets isgiven. The special attention is given for investigating permutation polyhedron’s admissible domains with special constraints. It isshown, that sometimes additional research of admissible domain allows reducing dimension of problems, passing from considerationof permutation polyhedrons with constraints to polypermutation polyhedrons without constraints, finding solutions of problems withrestrictions without using linear optimization methods or discrete linear optimization methods. The mathematical model of somemanufacture accommodation problem as a linear problem on permutations with additional restrictions is constructed. For solution ofthe problem using the se approaches is recommended. Refs.: 10 titles.