Издательство Института математики
Препринты ИМ СО РАН

Препринт № 48

Л.Е.Горбачевская
К ДВУХУРОВНЕВОЙ ЭКСТРЕМАЛЬНОЙ ЗАДАЧЕ ВЫБОРА
НОМЕНКЛАТУРЫ ИЗДЕЛИЙ
Новосибирск,1998. 29 с. (Препринт РАН.
Сиб. отд-ние. Ин-т математики; № 48).

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

Библиогр. 5.
Ключевые слова и фразы: оптимизация, целочисленность, двухуровневая задача, стандартизация, динамическое программирование, квазивыпуклость, квазивогнутость, NP-трудность.
Адрес автора: 630090 Новосибирск, пр. Академика Коптюга, 4.
Институт математики им. С. Л. Соболева СО РАН.

ballred.gif (80 bytes)  Головная страница  ballred.gif (80 bytes)   Препринты 1998  ballred.gif (80 bytes) Препринты 1999  ballred.gif (80 bytes)