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
