Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода

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