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.

1. Golshteyn E. G., Yudin D. B. Transport-type linear programming problems, Moscow, Nauka, 1969, 384 p. (in Russian)

2. Vasko F. J., Storozhyshina N. Balancing a transportation problem:Is it really that simple? // Operational Research Society. 2011. Vol. 24, N. 3. P. 205—214. DOI: 10.1057/ori.2011.6

3. Hasibuan N. A. Russel Approximation Method And Vogel’s Approximation Method In Solving Transport Problem // International Journal of Informatics and Computer Science. 2017. Vol. 1, N. 1. P. 1—7. DOI: 10.30865/ijics.v1i1.454

4. Reinfeld N., Vogel W. Mathematical Programming. Methods of solving production and transportation problems. Moscow, Publishing House of Foreign Literature, 1960, 304 p. (in Russian)

5. Putcha C., Shekaramiz A. А Comprehensive Method for Arriving at Initial Feasible Solution for Optimization Problems in Engineering with Illustrative Examples // Turkish Journal of Computer and Mathematics Education. 2021. Vol. 12, N. 5. P. 1189—1205. DOI: 10.17762/turcomat.v12i5.1785

6. Dantzig G. B. Application of the Simplex Method to a Transportation Problem, Activity Analysis of Production and Allocation / Koopmans T. C. Ed. New York: John Wiley and Sons, 1951. P. 359—373

7. Al-Faqih H. I., Shrefe А. M. Efficiency of the Simplex Method in Solving Transportation Problems // Academic Journal of Science and Technology. 2025. Vol. 5, N. 1. P. 270—276. DOI: 10.64095/ajst.v5i1.99

8. Aderemi A. O., Favour O. I., Adebisi А. L. Comparative Study of Efficiency of Integer Programming, Simplex Method and Transportation Method in Linear Programming Problem (LPP) // American Journal of Theoretical and Applied Statistics. 2015. Vol. 4, N. 3. P. 85—88. DOI: 10.11648/j.ajtas.20150403.13

9. Arsham H., Kahn A. B. А Simplex-Type Algorithm for General Transportation Problems: An Alternative to SteppingStone // Journal of the Operational Research Society. 1989. Vol. 40, N. 6. P. 581—590. DOI: 10.1057/palgrave.jors.0400607

10. Gottschlich C., Schuhmacher D. The Shortlist Method for Fast Computation of the Earth Mover’s Distance and Finding Optimal Solutions to Transportation Problems // PLOS One. 2014. Vol. 9, N. 10. DOI: 10.1371/journal.pone.0110214

11. Ikura Y., Nemhauser G. L. А Polynomial-Time Dual Simplex Algorithm for the Transportation Problem // Cornell University’s School of Operations Research and Industrial Engineering. 1983. Technical Report No. 602.

12. Schwinn J., Werner R. On the effectiveness of primal and dual heuristics for the transportation problem // IMA Journal of Management Mathematics. 2018. Vol. 30, N. 3. P. 281—303. DOI: 10.1093/imaman/dpy011

13. Frangioni A., Manca A. А Computational Study of Cost Reoptimization for Min-Cost Flow Problems // INFORMS Journal on Computing. 2006. Vol. 18, N. 1. P. 61—70. DOI: 10.1287/ijoc.1040.0081

14. Sabbagh M. S., Ghafari H., Mousavi S. R. А new hybrid algorithm for the balanced transportation problem // Computers & Industrial Engineering. 2015. Vol. 82. P. 115—126. DOI: 10.1016/j.cie.2015.01.018

15. Bienkowski M., Fuchssteiner D., Marcinkowski J., Schmid S. Online Dynamic В-Matching // ACM SIGMETRICS. 2021. Vol. 48, N. 3. P. 99—108.

16. Manne A. S. А Target-Assignment Problem // Operations Research. 1958. Vol. 6, N. 3. P. 346—351.

17. Lyu N., Wang M., Zhong Y., Zhang Y., Sun L. Weapon target allocation problem based on matching model of bipartite graphs // Systems Engineering and Electronics. 2024. Vol. 46, N. 2. P. 549—560.

18. Dasgupta S., Meirovitch Y., Zheng X. А neural algorithm for computing bipartite matchings // Proc Natl Acad Sci USA. 2024. Vol. 121, N. 37. P. 1—10. DOI: 10.1073/pnas.2321032121

19. Tizik A. P., Tsurkov V. I. Method of successive modification of functional for solving transport problem, Automation and Telecommunications, 2012, no. 1, pp. 148—158 (in Russian)

20. Leonov V. Yu., Tizik A. P., Torchinskaya E. V., Tsurkov V. I. Decomposition method for solving a transport problem with a quadratic objective function, Izvestiya RAS. TiSU, 2017, no. 5. pp. 46—52 (in Russian).

21. Wang L. P., Tizik A. P., Tsurkov V. I. Decomposition method for solving a linear three-index transport problem, Izvestiya RAS. TiSU, 2019, no. 6. pp. 57—62 (in Russian).

22. Wang L. P., Yesenkov A. S., Strelkova E. S., Tizik А. P. Decomposition method for the optimization problem of effective shooting, Izvestiya RAS. TiSU, 2021, no. 6. pp. 61—65, DOI: 10.31857/S0002338821060160 (in Russian).