Том 5, серия 2, номер 2, 1998 г., Стр. 20-33
УДК 519.87+519.854
Л. Е. Горбачевская
Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода
Аннотация:
Рассмотрены задачи двухуровневого программирования, обобщающие простейшую задачу размещения. Показана их сводимость к задаче выбора подмножества строк в паре матриц. Поставленные задачи изучаются в условиях квазивыпуклости или связности матриц затрат. Показывается, что при одних комбинациях этих условий исходные задачи эффективно разрешимы, при других же остаются NP-трудными. Показана NP-трудность задачи с парой связных матриц и указаны дополнительные условия, при которых задача решается эффективно.
Библиогр. 9.
Горбачевская Л. Е. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: orlab@math.nsc.ru
Статья поступила 17 августа 1998 г.
