Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the Set of Partial Permutations
Loading...
Date
2020
Authors
Koliechkina, Liudmyla
Nahirna, Alla
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
An optimization problem on a combinatorial set of partial permutations with additional constraints is formulated in the paper. An
algorithm for solving this type of problem is considered, which consists of four steps. The algorithm lies in constructing a graph of
a set of partial permutations to find the optimal solution. An example of a practical implementation of the presented algorithm is
given.
Вступ. Сформульовано оптимізаційну задачу на комбінаторній множині розміщень з додатковими обмеженнями. Розглянуто алгоритм розв’язання даного типу задач, який складається з чотирьох кроків. Алгоритм розв’язання полягає у побудові графу множини розміщень для знаходження оптимального розв’язку. Наведено приклад практичної реалізації представленого алгоритму. Мета статті — представлення методу розв’язання задачі умовної оптимізації на графі множини розміщень і демонстрація практичного прикладу реалізації. Методи. Метод розв’язання комбінаторної задачі з додатковими обмеженнями на графі. Результати. Сформульовано модель задачі умовної оптимізації на множині розміщень. Одержано лінійну форму цільової функції шляхом інтерпретації елементів множини розміщень як точок евклідового простору. Розглянуто комбінаторний многогранник розміщень, для якого існує граф множини розміщень. Запропоновано алгоритм розв’язання даної задачі та продемонстровано його практичне застосування. Висновки. Запропонований алгоритм розв’язання задачі умовної оптимізації передбачає представлення допустимої множини розміщень у вигляді графа, що дозволяє значно скоротити шлях пошуку оптимального розв’язку, про що свідчить розглянутий у статті практичний приклад.
Вступ. Сформульовано оптимізаційну задачу на комбінаторній множині розміщень з додатковими обмеженнями. Розглянуто алгоритм розв’язання даного типу задач, який складається з чотирьох кроків. Алгоритм розв’язання полягає у побудові графу множини розміщень для знаходження оптимального розв’язку. Наведено приклад практичної реалізації представленого алгоритму. Мета статті — представлення методу розв’язання задачі умовної оптимізації на графі множини розміщень і демонстрація практичного прикладу реалізації. Методи. Метод розв’язання комбінаторної задачі з додатковими обмеженнями на графі. Результати. Сформульовано модель задачі умовної оптимізації на множині розміщень. Одержано лінійну форму цільової функції шляхом інтерпретації елементів множини розміщень як точок евклідового простору. Розглянуто комбінаторний многогранник розміщень, для якого існує граф множини розміщень. Запропоновано алгоритм розв’язання даної задачі та продемонстровано його практичне застосування. Висновки. Запропонований алгоритм розв’язання задачі умовної оптимізації передбачає представлення допустимої множини розміщень у вигляді графа, що дозволяє значно скоротити шлях пошуку оптимального розв’язку, про що свідчить розглянутий у статті практичний приклад.
Description
Keywords
conditional optimization problem, optimal solution, graph, subgraph, of the Set of Partial Permutations, objective function, constraints, article, задача умовної оптимізації, оптимальний розв’язок, граф, підграф, множина розміщень, цільова функція, обмеження
Citation
Koliechkina L. Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the Set of Partial Permutations / L. M. Koliechkina, A. M. Nahirna // Control systems and computers. - 2020. - № 6. - P. 29-34.