Условия эффективной разрешимости квадратичной задачи выбора. Часть 2
DOI:
https://doi.org/10.33581/2520-6508-2025-2-75-88Ключевые слова:
комбинаторная оптимизация, квадратичная задача о назначениях, оптимизация на подстановках, эффективно разрешимые случаиАннотация
В современной терминологии условия классической теоремы Харди, Литлвуда и Полиа о перестановке трех систем гарантируют строгую разрешимость задачи оптимизации билинейной формы с симметрической матрицей Тёплица специального вида. Билинейная форма с указанной матрицей принимает экстремальные значения на подстановках двух видов в зависимости от того, одинаковые или противоположные упорядочения имеют компоненты двух векторов, определяющих значения переменных. В предыдущей части статьи были описаны условия достижения минимума функционала квадратичной задачи выбора на первой из заданных подстановок, обобщающие ряд результатов аналогичного плана для задачи минимизации квадратичной формы и квадратичной задачи о назначениях. В этой части работы рассматриваются условия, накладывание которых на элементы четырехиндексной матрицы гарантирует достижение минимума функционала квадратичной задачи выбора на второй подстановке, приведенной в теореме о перестановке трех систем. Результаты, представленные в двух частях статьи, на сегодняшний день описывают наиболее широкие классы четырехиндексных матриц, для которых функционал квадратичной задачи выбора принимает экстремальные значения на фиксированных подстановках.
Библиографические ссылки
Koopmans TC, Beckmann M. Assignment problems and the location of economic activities. Econometrica. 1957;25(1):53–76. DOI: 10.2307/1907742.
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.
Hardy GH, Littlewood JE, Pólya G. Inequalities. Cambridge: Cambridge University Press; 1934. XII, 314 p.
Харди ГХ, Литлвуд ДжИ, Полиа Г. Неравенства. Левин ВИ, переводчик. Москва: Государственное издательство иностранной литературы; 1948. 456 с.
Демиденко ВМ. Условия эффективной разрешимости квадратичной задачи выбора. Часть 1. Журнал Белорусского государственного университета. Математика. Информатика. 2024;1:45–58. EDN: TEYTMM.
Бурков ВН, Рубинштейн МИ, Соколов ВБ. Некоторые задачи оптимального размещения информации в памяти большого объема. Автоматика и телемеханика. 1969;9:83–91.
Тимофеев ББ, Литвинов ВА. К вопросу об организации размещения массивов информации в памяти на магнитных лентах. Кибернетика. 1969;4:56–61.
Метельский НН. Об экстремальных значениях квадратичной формы на симметрической группе. Весцi Акадэмii навук БССР. Серыя фiзiка-матэматычных навук. 1972;6:107–110.
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).
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.
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.
Woeginger GJ. Computational problems without computation. Nieuw Archief voor Wiskunde. 2003;4(2):140–147.
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.
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.
Демиденко ВМ. Квадратичная задача о назначениях с аддитивно монотонными матрицами и неполными матрицами анти-Монжа: условия эффективной разрешимости. Дискретная математика. 2007;19(1):105–132. EDN: HZFCZF.
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.
Çela E. Assignment problems. In: Pardalos PM, Resende MGC, editors. Handbook of applied optimization. Oxford: Oxford University Press; 2002. p. 661–678.
Burkard R, Dell’Amico M, Martello S. Assignment problems. Philadelphia: Society for Industrial and Applied Mathematics; 2009. XX, 382 p.
Демиденко ВМ. Эффективно разрешимые случаи и полиэдральные аспекты оптимизационных задач на подстановках [диссертация]. Минск: [б. и.]; 2011. 315 с.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2025 Журнал Белорусского государственного университета. Математика. Информатика
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).
