Полиномиально разрешимый класс задач двухуровневого линейного программирования

Характерной особенностью задач двухуровневого программирования является наличие вспомогательной оптимизационной задачи, которая используется при задании области допустимых решений. Показано, что если вспомогательная задача является задачей о рюкзаке с непрерывными переменными, то оптимальное решение задачи двухуровневого линейного программирования может быть найдено с полиномиальной трудоемкостью. Установлено, что при введении дополнительных ограничений в условия вспомогательной задачи исходная задача становится NP-трудной.
Библиогр. 8