Аннотация.

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

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

задача о рюкзаке, многомерная задача о рюкзаке, портфель проектов, улучшенный жадный алгоритм, локальный ограниченный перебор, полиномиальная временная сложность.

Стр. 54-64.

DOI: 10.14357/20790279190206

 Полная версия статьи в формате pdf.

Литература

1. Гельруд Я.Д. Методология создания информационно-аналитической системы управления проектами на основе комплекса математических моделей функционирования стейкхолдеров. Автореф. дис... д-ра техн. наук: 05.13.10 / Челябинск, (Юж.-Ур. гос. ун-т.), 2015. 43 с.
2. Лопухин М.М. ПАТТЕРН – метод планирования и прогнозирования научных работ. М.: Сов. радио, 1971.
3. Cetron M.J. QUEST Status Report // IEEE Transactions on Engineering Management. 1967. V. 14. №1. March. 443.
4. Nutt A.B. Testing TORQUE – a quantitative R&D research allocation system // IEEE Trans. on Eng. Manag. 1969.Vol. EM-16. №4.
5. The Analysis and Evaluation of Public Expenditures: the PPB System. Washington: U.S. Govern. Print Office, 1969.
6. Янч Э. Прогнозирование научно-технического прогресса. М.: Прогресс, 1970.
7. Ларичев О.И., Бойченко В.С., Мошкович Е.Н., Шепталова Л.П. Методы иерархических схем в программно-целевом планировании научных исследований / Препринт. М.: ВНИИСИ, 1978.
8. Martello S., Toth P. Knapsack problems: Algorithms and computer implementations / in: Series in Discrete Mathematics and Optimization. N. Y.: Wiley Inter Sciences, 1990. 296 p.
9. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Berlin / Heidelberg: Springer-Verlag, 2004. 548 p.
10. Dantzig G. B. Discrete-Variable Extremum Problems // Oper. Res. (INFORMS), 1957. Vol. 5, No. 2. pp. 266–277.
11. Vizvari B. On the Optimality of the Greedy Solutions of the General Knapsack Problems // Optimization. 1992. Vol. 23. No.2. pp. 125-138.
12. Дюбин Г.Н., Корбут А.А. Жадные алгоритмы для задач о ранце: поведение в среднем // Сибирский журнал индустриальной математики. 1999. Т.2. №2(4). С.68-93.
13. Korte B. Kombinatorische Optimierung und algorithmische Prinzipien // Ökonomische Prognose-, Enstscheidungs- und Gleichgewichtsmodelle. Weinheim: VCH Verlagsgesellschaft, 1986. рр. 286-341.
14. Гафаров Е.Р., Лазарев А.А., Вернер Ф. Алгоритмы решения задач максимизации суммарного запаздывания и максимизации количества запаздывающих требований для одного прибора // АиТ. 2010. № 10. С. 63–79.
15. Lazarev A., Salnikov A., Baranov A. Graphical Algorithm for the Knapsack Problems // Lecture Notes in Computer Science. 2011. 6873. pp. 459-466.
16. Weingartner H.M., Ness D.N. Method for the solution for the multidimensional 0–1 knapsack problem // Operations Research. 1967. Vol. 15. pp. 83–103.
17. Lorie J., Savage L.J. Three problems in capital rationing // Journal of Business. 1955. Vol. 28. pp. 229–239.
18. Manne A.S., Markowitz H.M. On the solution of discrete programming problems // Econometrica. 1957. Vol. 25. pp. 84–110.
19. Freville А. The multidimensional 0–1 knapsack problem: An overview // European Journal of Operational Research. 2004. Vol. 155. pp. 1–21
20. Левин М.Ш., Сафонов А.В. Эвристический алгоритм для многокритериальной блочной задачи о рюкзаке // Искусственный интеллект и принятие решений. 2009. № 4. С. 53-64.
21. Буркова И.В., Ткаченко М.В., Чураков П.П. Задача выбора множества проектов при выпуске инновационной продукции // Вестник Воронежского государственного технического университета. 2010. Т. 6. №9. С. 120-124.
22. Бурков В.Н., Буркова И.В., Уандыков Б.К., Чу Д.С. Метод допустимых решений в многомерной задаче о ранце // Экономика и менеджмент систем управления. 2015. Т.18. № 4.1. С. 136-144.
23. Буркова И.В., Пужанова Е.О., Марин О.Л. Задача о ранце и ее модификации // Научный вестник Воронежского государственного архитектурно-строительного университета. Серия: Управление строительством. Воронеж: ВГА-СУ, 2014. Вып. № 1(6). С. 103-112.
24. Бурков В.Н., Буркова И.В., Попок М.В., Овчинникова Т.И. Метод сетевого программирования // Проблемы управления. 2005. №3. С. 23 – 29.
25. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 c.
26. Гафаров Е.Р., Долгий А., Лазарев А.А., Вернер Ф. Новый эффективный алгоритм решения задачи об инвестициях // А и Т. 2016. №9. С. 150-166.
27. Рубинштейн М.И., Топка, В.В. Жадный алгоритм решения многомерной задачи о рюкзаке // Труды IV-ой Всесоюзной школы-семинара «Статистический и дискретный анализ данных и экспертное оценивание» (Одесса, 1991). ОдПИ,1991. С. 273-274.
28. Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т. Т.2. / Пер. с англ. М.: Мир, 1991. 702 c. (Schrijver, A. Theory of Linear and Integer Programming. N.Y.: John Wiley & Sons Ltd, 1986. 702 p.)
29. Shani S. Approximate algorithms for the 0–1 knapsack problem // Journal of Association for Computing Machinery. 1975. Vol.22. pp. 115–124.
30. Chandra A.K., Hirschberg D.S., Wong C.K. Approximation algorithms for some generalized knapsack problems // Theoretical Computer Sciences. 1976. No.3. pp. 293–304.
31. Magazine M. J., Oguz O. A fully polynomial approximation algorithm for the 0–1 knapsack problem // European Journal of Operational Research. 1981. No.8. pp. 270–273.