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

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

Аннотация

Описан класс четырехиндексных вещественных матриц, для которых гарантирована эффективная разрешимость квадратичной задачи выбора – достижение экстремальных значений ее функционала на одной из подстановок специального вида, приведенных в классической теореме Харди, Литлвуда и Полиа о перестановке трех систем. Условия, определяющие введенный класс матриц, обобщают все ранее предложенные условия, накладываемые на вид матриц и гарантирующие строгую разрешимость задач минимизации билинейной формы на декартовом произведении симметрической группы (условия теоремы о перестановке трех систем), квадратичной формы на симметрической группе, а также результаты аналогичного плана, полученные для квадратичной задачи о назначениях.

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

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

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

 

Литература

  1. Hardy GH, Littlewood JE, Pólya G. Inequalities. Cambridge: Cambridge University Press; 1934. XII, 314 p. Russian edition: Hardy GH, Littlewood JE, Pólya G. Neravenstva. Levin VI, translator. Moscow: Gosudarstvennoe izdatel’stvo inostrannoi literatury; 1948. 456 p.
  2. Timofeev BB, Litvinov VA. [On the problem of organizing the disposition of information files on magnetic tapes]. Kibernetika. 1969;4:56–61. Russian.
  3. Pratt VR. An Nlog N algorithm to distribute N records optimally in a sequential access file. In: Miller RE, Thatcher JW, editors. Complexity of computer computations. Proceedings of a symposium on the complexity of computer computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department. New York: Plenum Press; 1972. p. 111–118 (The IBM research symposia series). DOI: 10.1007/978-1-4684-2001-2_11.
  4. Lawler EL. The quadratic assignment problem: a brief review. In: Roy B, editor. Combinatorial programming: methods and applications. Proceedings of the NATO advanced study institute held at the Palais des Congrès, Versailles, France, 2–13 September, 1974. Dordrecht: D. Reidel Publishing Company; 1975. p. 351–360 (NATO advanced study institutes series. Series C, Mathematical and physical sciences; volume 19). DOI: 10.1007/978-94-011-7557-9_20.
  5. Vickson RG, Lu Xinjian. 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.
  6. Woeginger GJ. Computational problems without computation. Nieuw Archief voor Wiskunde. Vijfde Serie. 2003;4(2):140–147.
  7. 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.
  8. Demidenko VM. Quadratic assignment problem with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability. Discrete Mathematics and Applications. 2007;17(2):105–133. DOI: 10.1515/dma.2007.011.
  9. Demidenko VM, Dolgiy A. [Efficiently solvable cases of a quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices]. Kibernetika i sistemnyi analiz. 2007;1:135–151. Russian.
  10. 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.
  11. Çela E. Assignment problems. In: Pardalos PM, Resende MGC, editors. Handbook of applied optimization. Oxford: Oxford University Press; 2002. p. 661–678.
  12. Burkard R, Dell’Amico M, Martello S. Assignment problems: revised reprint. Philadelphia: Society for Industrial and Applied Mathematics; 2009. XXII, 393 p. (Other titles in applied mathematics). DOI: 10.1137/1.9781611972238.
Опубликован
2024-04-15
Ключевые слова: комбинаторная оптимизация, квадратичная задача о назначениях, оптимизация на подстановках, строгая разрешимость задач
Поддерживающие организации Работа выполнена в рамках государственной программы научных исследований «Конвергенция-2025» (подпрограмма «Математические модели и методы», задание 1.5.01).
Как цитировать
Демиденко, В. М. (2024). Условия эффективной разрешимости квадратичной задачи выбора. Часть 1. Журнал Белорусского государственного университета. Математика. Информатика, 1, 45-58. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/6078
Выпуск
№ 1 (2024): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

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

Лицензия 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).