Том 4, серия 2, номер 2, 1997 г., Стр. 23-33
УДК 519.854
Ю. А. Кочетов, А. В. Плясунов
Полиномиально разрешимый класс задач двухуровневого линейного программирования
Аннотация:
Характерной особенностью задач двухуровневого программирования является наличие вспомогательной оптимизационной задачи, которая используется при задании области допустимых решений. Показано, что если вспомогательная задача является задачей о рюкзаке с непрерывными переменными, то оптимальное решение задачи двухуровневого линейного программирования может быть найдено с полиномиальной трудоемкостью. Установлено, что при введении дополнительных ограничений в условия вспомогательной задачи исходная задача становится NP-трудной.
Библиогр. 8.
Кочетов Ю. А. 1
Плясунов А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 25 марта 1996 г.
