Максимизация линейной целевой функции с помощью жадного алгоритма

Рассматриваются задачи, обобщающие известную задачу о базе матроида максимального веса. Цель статьи состоит в выявлении классов задач, при решении которых с использованием жадных алгоритмов удается получать оптимальные решения при любой линейной целевой функции. Предложено обобщение аксиомы матроидов, являющееся достаточным и необходимым условием оптимальности жадного алгоритма в случае монотонных вниз систем целочисленных неотрицательных векторов. Расширена область действия критерия оптимальности, справедливого для случая систем множеств, не обладающих свойством монотонности вниз. Установлены новые критерии и достаточные условия оптимальности жадного алгоритма – как в общем, так и в частных случаях. Библиогр. 11.