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

Авторы

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

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

задача о ранце, многокритериальная оптимизация, множество Парето, паретовский слой

Аннотация

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

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

  • Сергей Викторович Чебаков, Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 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

Выпуск

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

Раздел

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

Лицензия

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

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

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

[1]
Чебаков, С.В. и Серебряная, Л.В. 2022. Алгоритм решения задачи о ранце при определенных свойствах паретовских слоев. Журнал Белорусского государственного университета. Математика. Информатика. 3 (дек. 2022), 54–66. DOI:https://doi.org/10.33581/2520-6508-2022-3-54-66.