Shooting Control with Additional Batteries

The classical linear programming transportation problem of minimizing the cost of transportation between production and consumption points has many applications, one of which is the problem of efficient fire control. The article considers a modified formulation of this problem. It includes main and auxiliary batteries, each of which can fire a limited number of shots at targets with a given efficiency. Auxiliary batteries can fire only at predetermined targets. The goal is to distribute targets between batteries in such a way that the total efficiency of destruction is maximized. The decomposition method is used to solve the proposed problem. The original problem of large dimension is divided into many simpler one-dimensional and two-dimensional subproblems. At the first stage, the initial pseudo-solution is found as a set of solutions to these subproblems. If it is admissible for the original problem, then it is also optimal. Otherwise, an iterative process of sequentially coordinating the solutions of the subproblems is launched by cyclically recalculating the coefficients of the objective function in two dimensional problems. This process guarantees a monotonic approximation to the optimal solution. The article examines in detail possible cases arising during the algorithm operation, including a special degenerate case, for the resolution of which it is proposed to introduce additional constraints. The possibility of replacing inequality constraints with equality constraints for the main batteries within the framework of the decomposition approach without loss of generality is theoretically substantiated. The efficiency of the proposed algorithm is confirmed by the results of computational experiments. Approximation of the dependence of the running time on the problem dimension demonstrates the polynomial complexity of the method. The obtained results open up prospects for applying this approach to other non classical formulations of transport-type optimization problems.