Управление стрельбой при наличии дополнительных батарей

Классическая транспортная задача линейного программирования, заключающаяся в минимизации стоимости перевозок между пунктами производства и потребления, имеет множество приложений, одним из которых является задача об эффективном управлении стрельбой. В статье рассматривается модифицированная постановка этой задачи. В ней присутствуют основные и вспомогательные батареи, каждая из которых может выполнить ограниченное число выстрелов по целям с заданной эффективностью. Вспомогательные батареи могут вести огонь только по заранее определенным целям. Цель заключается в таком распределении целей между батареями, которое максимизирует суммарную эффективность поражения. Для решения предложенной задачи применяется метод декомпозиции. Исходная задача большой размерности разбивается на множество более простых одномерных и двумерных подзадач. На первом этапе находится начальное псевдорешение как совокупность решений этих подзадач. Если оно оказывается допустимым для исходной задачи, то является и оптимальным. В противном случае запускается итерационный процесс последовательного согласования решений подзадач путем циклического пересчета коэффициентов целевой функции в двумерных задачах. Этот процесс гарантирует монотонное приближение к оптимальному решению. В статье детально разбираются возможные случаи, возникающие в ходе работы алгоритма, включая особый вырожденный случай, для разрешения которого предлагается введение дополнительных ограничений. Теоретически обосновывается возможность замены ограничений-неравенств на ограничения-равенства для основных батарей в рамках декомпозиционного подхода без потери общности. Эффективность предложенного алгоритма подтверждается результатами вычислительных экспериментов. Аппроксимация зависимости времени работы от размерности задачи демонстрирует полиномиальную сложность метода. Полученные результаты открывают перспективы для применения данного подхода к другим неклассическим постановкам задач оптимизации транспортного типа.

1. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Москва, Наука, 1969, 384 с.

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. Рейнфельд Н., Фогель У. Математическое программирование. Методы решения производственных и транспортных задач. М.: Издательство иностранной литературы, 1960. 304 с.

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. Тизик А. П., Цурков В. И. Метод последовательной модификации функционала для решения транспортной задачи // АиТ. 2012. № 1. С. 148—158.

20. Леонов В. Ю., Тизик А. П., Торчинская Э. В., Цурков В. И. Декомпозиционный метод решения транспортной задачи с квадратичной целевой функцией // Изв. РАН. ТиСУ. 2017. № 5. С. 46—52.

21. Ванг Л. П., Тизик А. П., Цурков В. И. Декомпозиционный метод решения линейной трехиндексной транспортной задачи // Изв. РАН. ТиСУ. 2019. № 6. С. 57—62.

22. Ванг Л. П., Есенков А. С., Стрелкова Е. С., Тизик А. П. Декомпозиционный метод для оптимизационной задачи об эффективной стрельбе // Изв. РАН. ТиСУ. 2021. № 6. С. 61—65. DOI:10.31857/S0002338821060160