Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок

Loading...
Thumbnail Image
Date
2020
Authors
Донец, Георгий
Колечкина, Людмила
Нагорная, Алла
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Рассмотрена задача на множестве перестановок с квадратичной функцией цели и дополнительными линейными ограничениями. Предложен метод решения сформулированной задачи, который включает два этапа. На первом этапе находится множество опорных решений. Составляется квадратичная функция для соответствующей транспозиции и формируются подзадачи с дополнительными ограничениями. При их решении находится множество опорных решений, удовлетворяющих ограничениям основной задачи. Второй этап заключается в нахождении оптимального решения из подмножества оптимальных решений и множества допустимых решений.
Розглянуто задачу на множині перестановок з квадратичною функцією цілі і додатковими лінійними обмеженнями. Запропоновано метод розв'язання сформульованої задачі, який складається з двох етапів. На першому етапі здійснюється знаходження множини опорних розв’язків. Складається квадратична функція для відповідної транспозиції і формуються підзадачі з додатковими обмеженнями. Для їхнього розв’язання знаходять множину опорних розв’язків, що задовольняє обмеження основної задачі. Другий етап полягає в знаходженні оптимального розв’язку з підмножини оптимальних роз’язків і множини допустимих розв’язків.
The problem with a quadratic objetive function and additional linear constraints is considered on the set of permutations. A solution method is proposed, which consists of two stages. At the first stage, the set o f support solutions is found. A quadratic function is composed for the corresponding transposition and sub-problems are generated with additional constraints. A set o f supporting solutions that satisfy the constraints of the main problem can be found in the course of their solution. The second stage is to find the optimal solution from the subset of optimal solutions and the set o f feasible solutions.The problem with a quadratic objetive function and additional linear constraints is considered on the set of permutations. A solution method is proposed, which consists of two stages. At the first stage, the set o f support solutions is found. A quadratic function is composed for the corresponding transposition and sub-problems are generated with additional constraints. A set o f supporting solutions that satisfy the constraints of the main problem can be found in the course of their solution. The second stage is to find the optimal solution from the subset of optimal solutions and the set o f feasible solutions.
Description
Keywords
условная оптимизация, квадратичная функция, множество перестановок, транспозиция элементов, прирост функции, прирост ограничения, множество допустимых решений, множество опорных решений, оптимальное решение, статья, умовна оптимізація, квадратична функція, множина перестановок, транспозиція елементів, приріст функції, приріст обмеження, множина допустимих розв'язків, множина опорних розв'язків, оптимальний розв’язок, conditional optimization, quadratic function, set of permutations, transposition of elements, increase in function, increase in constraint, set of feasible solutions, set of support solutions, optimal solution
Citation
Донец Г. А. Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок / Г. А. Донец, Л. Н. Колечкина, А. Н. Нагорная // Кибернетика и системный анализ. - 2020. - Т. 56, № 2. - С. 129-140.