Глобальные допуски в задачах комбинаторной оптимизации с аддитивной целевой функцией

Доклады Академии наук. 2012. Т. 446. № 1. С. 21–24.

Гольденгорин Б. И., Пардалос П. О., Чистяков В. В.

Известно, что при помощи минимальных значений допусков удается получить необходимые и достаточные условия единственности оптимального решения задачи комбинаторной оптимизации (ЗКО) с аддитивной целевой функцией и множеством невложенных друг в друга допустимых решений. Кроме того, понятие допуска определено локально, т.е. относительно одного выбранного оптимального решения. В этой статье вводится понятие глобального допуска относительно множества всех оптимальных решений и доказывается, что предположение о невложенности множества допустимых решений ЗКО можно ослабить, что обобщает известные соотношения для экстремальных значений допусков. В частности, формулируется новый критерий единственноссти оптимального решения ЗКО с аддитивной целевой функцией, основанный на равенствах между локально и глобально определенными допусками.

Ключевые слова: комбинаторная оптимизация, глобальные допуски, аддитивная целевая функция, экстремальное значение, общая теория комбинаторного анализа, исследование операций, алгоритмы решения задач вычислительной и дискретной математики