Алгоритм упрощения решения в задачах дискретной оптимизации

Autor: Chernov, Sergii, Titov, Sergiy, Chernova, Lyudmila, Gogunskii, Viktor, Chernova, Liubava, Kolesnikova, Kateryna
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: Eastern-European Journal of Enterprise Technologies; Том 3, № 4 (93) (2018): Mathematics and Cybernetics-applied aspects; 34-43
Восточно-Европейский журнал передовых технологий; Том 3, № 4 (93) (2018): Математика и кибернетика-прикладные аспекты; 34-43
Східно-Європейський журнал передових технологій; Том 3, № 4 (93) (2018): Математика та кібернетика-прикладні аспекти; 34-43
ISSN: 1729-3774
1729-4061
Popis: Typically, the search for solutions in discrete optimization problems is associated with fundamental computational difficulties. The known methods of accurate or approximated solution of such problems are studied talking into consideration their belonging to so-called problems from P and NP class (algorithms for polynomial and exponential implementation of solution). Modern combinatorial methods for practical solution of discrete optimization problems are focused on the development of algorithms which allow obtaining an approximated solution with guaranteed evaluation of deviations from the optimum. Simplification algorithms are an effective technique of the search for solutions to an optimization problem. If we make a projection of a multi-dimensional process onto a two-dimensional plane, this technique will make it possible to clearly display a set of all solutions to the problem in graphical form. The method for simplification of the combinatorial solution to the discrete optimization problem was proposed in the framework of this research. It is based on performance of decomposition of a system that reflects the system of constraints of the original five-dimensional original problem on a two-dimensional plane. This method enables obtaining a simple system of graphic solutions to a complex problem of linear discrete optimization. From the practical point of view, the proposed method enables us to simplify computational complexity of optimization problems of such a class. The applied aspect of the proposed approach is the use of obtained scientific results in order to provide a possibility to improve the typical technological processes, described by systems of linear equations with existence of systems of linear constraints. This is a prerequisite for subsequent development and improvement of similar systems. In this study, the technique for decomposition of a discrete optimization system through projection of an original problem on two-dimensional coordinate planes was proposed. In this case, the original problem is transformed to a combinatorial family of subsystems, which makes it possible to obtain a system of graphic solutions to a complex problem of linear discrete optimization.
Зазвичай пошук розв’язку в задачах дискретної оптимізації пов'язаний з принциповими обчислюваними труднощами. Відомі методи точного або наближеного розв’язку таких задач вивчаються з урахуванням належності їх до, так званих, задач з класу P та NP (алгоритми поліноміальної та експоненціальної реалізації розв’язку). Сучасні комбінаторні методи для практичного розв’язку задач дискретної оптимізації потребують розробки алгоритмів, які дозволяють отримувати наближений розв'язок з гарантованою оцінкою відхилення від оптимуму. Алгоритми спрощення є ефективним прийомом пошуку розв’язку оптимізаційної задачі. Якщо виконати проектування багатовимірного процесу на двовимірну площину, то такий прийом дозволить наочно відобразити у графічній формі множини розв’язків задачі. В рамках даного дослідження запропоновано спосіб спрощення комбінаторного розв’язку задачі дискретної оптимізації. Він заснований на тому, що виконується декомпозиція системи, яка відображає систему обмежень п’ятивимірної вихідної задачі на двовимірну координатну площину. Такий спосіб дозволяє отримати просту систему графічних розв’язувань складної задачі лінійної дискретної оптимізації. З практичної точки зору запропонований метод дозволяє спростити обчислювальну складність оптимізаційних задач такого класу. Прикладним аспектом запропонованого підходу є використання отриманого наукового результату для забезпечення можливості вдосконалення типових технологічних процесів, що описуються системами лінійних рівнянь з наявністю системами лінійних обмежень. Це складає передумови для подальшого розвитку та удосконалення подібних систем. В даному дослідженні запропоновано методику декомпозиції дискретної оптимізаційної системи шляхом проекції вихідної задачі на двовимірні координатні площини. За такого прийому вихідна задача трансформується в комбінаторне сімейство підсистем, що дозволяє отримати систему графічних розв’язувань складної задачі лінійної дискретної оптимізації
Обычно поиск решений в задачах дискретной оптимизации связан с принципиальными вычислительными трудностями. Известные методы точного или приближенного решения таких задач изучаются с учетом принадлежности их к так называемым задачам из класса P и NP (алгоритмы полиномиальной и экспоненциальной реализации развязку). Современные комбинаторные методы для практического решения задач дискретной оптимизации ориентированы на разработку алгоритмов, которые позволяют получать приближенное решение с гарантированной оценкой отклонения от оптимума. Алгоритмы упрощения является эффективным приемом поиска решений оптимизационной задачи. Если выполнить проекцию многомерного процесса на двумерную плоскость, то такой прием позволит наглядно отобразить в графической форме множество решений задачи. В рамках данного исследования предложен способ упрощения комбинаторного решении задачи дискретной оптимизации. Он основан на том, что выполняется декомпозиция системы, которая отражает систему ограничений пятимерной исходной задачи на двумерной координатной плоскости. Такой способ позволяет получить простую систему графических решения сложной задачи линейной дискретной оптимизации. С практической точки зрения предложенный метод позволяет упростить вычислительную сложность оптимизационных задач такого класса. Прикладным аспектом предложенного подхода является использование полученного научного результата для обеспечения возможности совершенствования типовых технологических процессов, описываемых системами линейных уравнений с наличием систем линейных ограничений. Это составляет предпосылки для дальнейшего развития и совершенствования подобных систем. В данном исследовании предложена методика декомпозиции дискретной оптимизационной системы путем проекции исходной задачи на двумерные координатные плоскости. При этом исходная задача трансформируется в комбинаторное семейство подсистем, что позволяет получить систему графических решений сложной задачи линейной дискретной оптимизации
Databáze: OpenAIRE