Control Systems and Computers, N6, 2020, Стаття 3
https://doi.org/10.15407/csc.2020.06.029
Nahirna A.M., Koliechkina L.M. Finding the Optimal Solution to the Problem of Conditional Optimization on the Graph of the set of Placement. Control Systems and Computers. 2020. № 6. C. 29-34.
УДК 364.2:331; 681.513
Колєчкіна Л.М., док. фіз.-матем. наук, професор, Лодзький университет, вул. Банаха 22, Лодзь 90-238, Польша, E–mail: ludapl@ukr.net,
Нагірна А.М., канд. фіз.-матем.наук, доцент, Національний університет «Києво-Могилянська академія», вул. Г. Сковороди, 2, м. Київ, 04070, Україна, E–mail: naghirnaalla@ukr.net
Знаходження оптимального розв’язку задачі умовної оптимізації на графі множини розміщень
Вступ. В роботі сформульована оптимізаційна задача на комбинаторній множині розміщень з додатковими обмеженнями. Розглянуто алгоритм вирішення даного типу завдань, що складається з чотирьох кроків. Алгоритм рішення полягає в побудові графа безлічі розміщень для знаходженні оптимального рішення. Наведено приклад практичної реалізації представленого алгоритму.
Метою даної статті є представлення методу розв’язання задачі умовної оптимізації на графі безлічі розміщень і демонстрація практичного прикладу реалізації.
Методи. Метод розв’язання комбінаторної завдання з додатковими обмеженнями на графі.
Результати. Сформульовано модель задачі умовної оптимізації на множині розміщень. Отримано лінійна форма цільової функції шляхом інтерпретації елементів безлічі розміщень, як точок евклідового простору. Розглянуто комбінаторний багатогранник розміщень, для якого існує граф безлічі розміщень. Запропоновано алгоритм вирішення цієї задачі і продемонстрована його практична застосовність.
Висновки. Запропонований алгоритм розв’язання задачі умовної оптимізації передбачає подання допустимого множини розміщень у вигляді графа, яке дозволяє значно скоротити шлях пошуку оптимального рішення, що демонструє розглянутий в роботі практичний приклад.
Завантажити повний текст PDF (англійською).
Ключові слова: задача умовної оптимізації, оптимальний розв’язок, граф, підграф, множина розміщень, цільова функція, обмеження.
Поступила 24.11.20
