• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Доклады Академии наук. 2012. Т. 446. № 1. С. 21-24.
Гольденгорин Б. И., Пардалос П. О., Чистяков В. В.

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