Журнал «Современная Наука»

Russian (CIS)English (United Kingdom)
 MOSCOW +7(495)-142-86-81

Similarity criteria for dynamic problems of combinatorial optimization

Akhanova Marina Anatolievna  (Candidate of Social Sciences, Associate Professor, Industrial University of Tyumen (IUT))

Ovchinnikova Svetlana Valerievna  (Candidate of Social Sciences, Associate Professor, Industrial University of Tyumen (IUT))

Terekhova Natalya Vladimirovna  (Ph.D., Associate Professor, Industrial University of Tyumen (IUT))

The article describes the signs by which the similarity of dynamic tasks belonging to different classes is established. Those combinatorial optimization problems are considered dynamic, in which, when solving them, the existing information is produced, according to which the result is evaluated, and the optimal solution is found in stages with the calculation of partial sums of the objective function. The main signs of similarity for them is the change in the result of the solution in time and for its current reference the need to calculate a partial objective function. The process of their solution is described by a directed acyclic graph, and the partial values of the objective function change in time and are calculated in accordance with recursive rules. When finding their optimal values, the Bellman principle is fulfilled. Similarity properties are revealed that are characteristic of problems of this class and determine their universality, as a result of which the same method is used to solve them. To solve these problems, as a rule, dynamic programming is used. The analysis and use of the similarity property in combinatorial optimization makes it possible to bring unsolvable problems to solvable ones. Examples of some dynamic problems of combinatorial optimization are given.

Keywords:combinatorial optimization (CO), combinatorial configuration, dynamic problems, problem similarity, objective function.
 

Read the full article …

Citation link:
Akhanova M. A., Ovchinnikova S. V., Terekhova N. V. Similarity criteria for dynamic problems of combinatorial optimization // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2022. -№05. -С. 41-45 DOI 10.37882/2223-2966.2022.05.02
LEGAL INFORMATION:
Reproduction of materials is permitted only for non-commercial purposes with reference to the original publication. Protected by the laws of the Russian Federation. Any violations of the law are prosecuted.
© ООО "Научные технологии"

Terms Publications

Issues of the journals (Archive)

ECONOMICS AND LAW
HUMANITIES
NATURAL AND TECHNICAL SCIENCES
COGNITION

Серия - Natural and Technical Sciences