ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИC ИНТЕРВАЛЬНЫМИ ПАРАМЕТРАМИ

摘要

Рассмотрены задачи оптимизации на графах c интервальными параметрами, обоснованы соответствующие экспоненциальные и полиномиальные оценки их вычислительной сложности. для выделенного подкласса полиномиально разрешимых задач предложены 2 алгоритма: нахождение оптимального решения и нахождение субоптимального решения. Установлены достаточные условия статистической эффективности алгоритма нахождения субоптимального решения. Библ. 23.