Введение к работе
Актуальность темы. Одним из классов прикладных задач, получивших широкое распространение и выделившихся в отдельную область дискретной оптимизации, являются задачи стандартизации и размещения [1]. Классической задачей в этой области исследований является простейшая задача размещения. Она возникает, в частности, при выборе номенклатуры изделий для удовлетворения заданного спроса по критерию минимума суммарных затрат в сфере производства и потребления.
В настоящей работе рассматривается обобщение этой задачи, а именно, двухуровневые задачи стандартизации и размещения. Задачи многоуровневого программирования возникают при моделировании процессов принятия решений в иерархических системах, в которых каждый уровень иерархии полностью не определяет поведение нижних уровней, а может только влиять на их решения. Каждый уровень иерархии, зная решения вышестоящих уровней, принимает свое решение, руководствуясь своими целями и используя свои возможности. В целом задача состоит в поиске решения верхнего уровня, которое приводит всю иерархическую систему к достижению определенной цели.
В последние 10-15 лет интерес к задачам многоуровневого программирования значительно возрос [2]. В настоящее время это интенсивно развивающееся направление математического программирования имеет обширную область применения для решения задач проектирования транспортных сетей, управления, планирования, технического проектирования. В публикациях рассматриваются, в основном, непрерывные задачи двухуровневого программирования. В последние годы появились работы, посвященные изучению дискретных задач двухуровневого и многоуровневого программирования, но в целом эта область математического программирования мало исследована.
Цель работы. Применение методологии многоуровневого программирования к задачам стандартизации и размещения; исследование свойств двухуровневых задач стандартизации; выделение классов задач, допускающих эффективное решение; разработка подходов к построению нижних оценок оптимальных значений целевых функций рассматриваемых задач.
Метод исследования. При решении поставленных задач использовались методы математического программирования, в частности, методы динамического, линейного, дискретного программирования и теории графов.
Научная новизна. В работе предлагаются новые постановки задач стандартизации и размещения, использующие методологию многоуровневого программирования. Проводится анализ двухуровневых задач стандартизации. Выделены полиномиально разрешимые и NP-трудные классы рассматриваемых задач, предложены подходы к оценке их оптимумов.
Практическая ценность. Полученные результаты позволяют разработать алгоритмы для решения ряда практических задач стандартизации и размещения, возникающих при моделировании процессов принятия решений в иерархических системах.
Апробация работы. Основные результаты диссертации докладывались на Международной конференции по проблемам оптимизации и экономическим приложениям (г. Омск, 1997 г.), на Международной Сибирской конференции по исследованию операций (г. Новосибирск, 1998 г.), на семинарах Института математики СО РАН и Института вычислительной математики и математической геофизики СО РАН.
Публикации. По теме диссертации опубликовано 7 работ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Общий объем работы 131 страница, список литературы содержит 76 наименований.