Алгоритм решения задачи о ранце при определенных свойствах паретовских слоев

  • Сергей Викторович Чебаков Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь
  • Лия Валентиновна Серебряная БИП – университет права и социально-информационных технологий, ул. Короля, 3, 220004, г. Минск, Беларусь; Белорусский государственный университет информатики и радиоэлектроники, ул. П. Бровки, 6, 220013, г. Минск, Беларусь
DOI: https://doi.org/10.33581/2520-6508-2022-3-54-66

Аннотация

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

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

Сергей Викторович Чебаков, Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

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

Лия Валентиновна Серебряная, БИП – университет права и социально-информационных технологий, ул. Короля, 3, 220004, г. Минск, Беларусь; Белорусский государственный университет информатики и радиоэлектроники, ул. П. Бровки, 6, 220013, г. Минск, Беларусь

кандидат технических наук, доцент; заведующий кафедрой информационных технологий и математики экономико-правового факультета БИП – университета права и социально-информационных технологий, доцент кафедры программного обеспечения информационных технологий факультета компьютерных систем и сетей БГУИР

Литература

  1. Мartello S, Toth P. Knapsack problems: algorithms and computer implementations. New York: John Wiley & Sons; 1990. 308 p.
  2. Posypkin MA. [Combined parallel algorithm for solving the knapsack problem]. In: Trudy IV Mezhdunarodnoi konferentsii «Parallel’nye vychisleniya i zadachi upravleniya»; 27–29 oktyabrya 2008 g.; Moskva, Rossiya [Proceedings of the 4th International conference «Parallel Computing and Control Problems»; 2008 October 27–29; Moscow, Russia]. Moscow: Institute of Control Sciences of the Russian Academy of Sciences; 2008. p. 177–189. Russian.
  3. Chebakov SV. [A two-criterion model for constructing an optimal subset of alternatives with the maximum total probability of achieving the goal]. Vesci Nacyjanal’naj akadjemii navuk Belarusi. Seryja fizika-matjematychnyh navuk. 2005;2:112–118. Russian.
  4. Chebakov SV, Serebryanaya LV. Finding of optimal subset structure in the knapsack problem. Doklady BGUIR. 2019;6:72–79. Russian. DOI: 10.35596/1729-7648-2019-124-6-72-79.
  5. Chebakov SV, Serebryanaya LV. Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem. Journal of the Belarusian State University. Mathematics and Informatics. 2020;2:97–104. Russian. DOI: 10.33581/2520-6508-2020-2-97-104.
  6. Kung HF, Luccio F, Preparata FP. On finding the maxima of a set of vectors. Journal of the ACM. 1975;22(4):469–476. DOI: 10.1145/321906.321910.
Опубликован
2022-12-27
Ключевые слова: задача о ранце, многокритериальная оптимизация, множество Парето, паретовский слой
Как цитировать
Чебаков, С. В., & Серебряная, Л. В. (2022). Алгоритм решения задачи о ранце при определенных свойствах паретовских слоев. Журнал Белорусского государственного университета. Математика. Информатика, 3, 54-66. https://doi.org/10.33581/2520-6508-2022-3-54-66
Выпуск
№ 3 (2022): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

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

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