Условия эффективной разрешимости квадратичной задачи выбора. Часть 2

Авторы

  • Виталий Михайлович Демиденко Белорусский государственный экономический университет, пр. Партизанский, 26, 220070, г. Минск, БеларусьАннотация.

Ключевые слова:

комбинаторная оптимизация, квадратичная задача о назначениях, оптимизация на подстановках, эффективно разрешимые случаи
Поддерживающие организации
Работа выполнена в рамках государственной программы научных исследований «Конвергенция-2025» (подпрограмма «Математические модели и методы», задание 1.5.01).

Аннотация

В современной терминологии условия классической теоремы Харди, Литлвуда и Полиа о перестановке трех систем гарантируют строгую разрешимость задачи оптимизации билинейной формы с симметрической матрицей Тёплица специального вида. Билинейная форма с указанной матрицей принимает экстремальные значения на подстановках двух видов в зависимости от того, одинаковые или противоположные упорядочения имеют компоненты двух векторов, определяющих значения переменных. В предыдущей части статьи были описаны условия достижения минимума функционала квадратичной задачи выбора на первой из заданных подстановок, обобщающие ряд результатов аналогичного плана для задачи минимизации квадратичной формы и квадратичной задачи о назначениях. В этой части работы рассматриваются условия, накладывание которых на элементы четырехиндексной матрицы гарантирует достижение минимума функционала квадратичной задачи выбора на второй подстановке, приведенной в теореме о перестановке трех систем. Результаты, представленные в двух частях статьи, на сегодняшний день описывают наиболее широкие классы четырехиндексных матриц, для которых функционал квадратичной задачи выбора принимает экстремальные значения на фиксированных подстановках.

Биография автора

  • Виталий Михайлович Демиденко, Белорусский государственный экономический университет, пр. Партизанский, 26, 220070, г. Минск, БеларусьАннотация.

    доктор физико-математических наук, доцент; профессор кафедры высшей математики факультета цифровой экономики

Библиографические ссылки

  1. Koopmans TC, Beckmann M. Assignment problems and the location of economic activities. Econometrica. 1957;25(1):53–76. DOI: 10.2307/1907742.
  2. Hardy GH, Littlewood JE, Pólya G. The maximum of a certain bilinear form. Proceedings of the London Mathematical Society. 1926;25:265–282. DOI: 10.1112/plms/s2-25.1.265.
  3. Hardy GH, Littlewood JE, Pólya G. Inequalities. Cambridge: Cambridge University Press; 1934. XII, 314 p.
  4. Харди ГХ, Литлвуд ДжИ, Полиа Г. Неравенства. Левин ВИ, переводчик. Москва: Государственное издательство иностранной литературы; 1948. 456 с.
  5. Демиденко ВМ. Условия эффективной разрешимости квадратичной задачи выбора. Часть 1. Журнал Белорусского государственного университета. Математика. Информатика. 2024;1:45–58. EDN: TEYTMM.
  6. Бурков ВН, Рубинштейн МИ, Соколов ВБ. Некоторые задачи оптимального размещения информации в памяти большого объема. Автоматика и телемеханика. 1969;9:83–91.
  7. Тимофеев ББ, Литвинов ВА. К вопросу об организации размещения массивов информации в памяти на магнитных лентах. Кибернетика. 1969;4:56–61.
  8. Метельский НН. Об экстремальных значениях квадратичной формы на симметрической группе. Весцi Акадэмii навук БССР. Серыя фiзiка-матэматычных навук. 1972;6:107–110.
  9. Pratt VR. An N log N algorithm to distribute N records optimally in a sequential access file. In: Miller RE, Thatcher JW, editors. Complexity of computer computations. Proceedings of the symposium; 1972 March 20–22; New York, USA. New York: Plenum Press; 1972. p. 111–118 (The IBM research symposia series).
  10. Vickson RG, Lu X. Optimal product and server locations in one-dimensional storage racks. European Journal of Operational Research. 1998;105(1):18–28. DOI: 10.1016/S0377-2217(97)00023-4.
  11. Burkard RE, Çela E, Rote G, Woeginger GJ. The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases. Mathematical Programming. 1998;82:125–158. DOI: 10.1007/BF01585868.
  12. Woeginger GJ. Computational problems without computation. Nieuw Archief voor Wiskunde. 2003;4(2):140–147.
  13. Woeginger GJ. Exact algorithms for NP-hard problems: a survey. In: Jünger M, Reinelt G, Rinaldi G, editors. Combinatorial optimization – eureka, you shrink! Revised papers of the 5th International workshop dedicated to Jack Edmonds; 2001 March 5–9; Aussois, France. Berlin: Springer; 2003. p. 185–207 (Goos G, Hartmanis J, van Leeuwen J, editors. Lecture notes in computer science; volume 2570). DOI: 10.1007/3-540-36478-1_17.
  14. Demidenko VM, Finke G, Gordon VS. Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices. Journal of Mathematical Modelling and Algorithms. 2006;5(2):167–187. DOI: 10.1007/s10852-005-9013-2.
  15. Демиденко ВМ. Квадратичная задача о назначениях с аддитивно монотонными матрицами и неполными матрицами анти-Монжа: условия эффективной разрешимости. Дискретная математика. 2007;19(1):105–132. EDN: HZFCZF.
  16. Demidenko VM, Dolgui A. Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices. Cybernetics and Systems Analysis. 2007;43(1):112–125. DOI: 10.1007/s10559-007-0030-1.
  17. Çela E. Assignment problems. In: Pardalos PM, Resende MGC, editors. Handbook of applied optimization. Oxford: Oxford University Press; 2002. p. 661–678.
  18. Burkard R, Dell’Amico M, Martello S. Assignment problems. Philadelphia: Society for Industrial and Applied Mathematics; 2009. XX, 382 p.
  19. Демиденко ВМ. Эффективно разрешимые случаи и полиэдральные аспекты оптимизационных задач на подстановках [диссертация]. Минск: [б. и.]; 2011. 315 с.

Загрузки

Опубликован

2025-11-11

Выпуск

№ 2 (2025): Журнал Белорусского государственного университета. Математика. Информатика

Раздел

Дискретная математика и математическая кибернетика

Лицензия

Copyright (c) 2025 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).

Как цитировать

[1]
Демиденко, В.М. 2025. Условия эффективной разрешимости квадратичной задачи выбора. Часть 2. Журнал Белорусского государственного университета. Математика. Информатика. 2 (ноя. 2025), 75–88. DOI:https://doi.org/10.33581/2520-6508-2025-2-75-88.