Combinatorial assignment algorithm goals

Background. Combinatorial algorithms for assigning targets (assignments) are used in the allocation of means of destruction (resources). The main advantage of combinatorial algorithms for local search for optimal target assignment is low asymptotic complexity. However, these algorithms, as a rule, do not provide an optimal solution to the task of assigning goals. In this regard, the paper solves the problem of developing a combinatorial algorithm that provides an optimal or suboptimal solution to the goal assignment problem. The purpose of the study is to substantiate the type of global and local objective function for solving the purpose assignment problem, develop an algorithm for local search for optimal goal assignment using the combinatorial method, and evaluate the quality of the problem solution. Materials and methods. The combinatorial algorithm was developed on the basis of a formalized formulation of the problem using a matrix of goal assignments. The sum of the elements on the main diagonal of the matrix is considered as a global objective function. The minimum sum of the elements is found by rearranging the columns and rows of the matrix. To carry out the next permutation, the values of the elements on the main diagonal of the matrix are analyzed, and the maximum gain from the permutation is determined. Results. The functions of global and local search for optimal solutions are defined based on the analysis of the values of the elements on the main diagonal of the goal assignment matrix and the evaluation function for meeting the necessary and sufficient optimality conditions. The goal assignment problem was solved using the developed algorithm. Statistical estimates of the effectiveness of goal assignment are calculated using the developed algorithm. Conclusions. The developed combinatorial algorithm for the local search for the minimum of the objective function of goal assignment provides an optimal or suboptimal solution to the goal assignment problem. This is confirmed by the results of goal assignment using a linear discrete programming algorithm and a local search algorithm using the combinatorial method. The asymptotics of the algorithm is no more O(2n² ) .