Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

В [1] описаны алгоритмы для решения частично целочисленных задач производственно-транспортного типа, основанные на идее декомпозиции Бендерса и метода направленного перебора. В данной работе предлагаются декомпозиционные алгоритмы для простейшей задачи размещения (ПЗР), задачи о p-медиане [2, 8] и некоторых других постановок, в которых наряду с отсечениями Бендерса для решения целочисленной подзадачи используется лексикографический перебор L-классов [?]. Краткое сообщение о них имеется в [7].
Рассмотрим ПЗР в следующей постановке. Дано конечное множество пунктов возможного размещения предприятий и список клиентов. Предприятия производят однородный продукт в неограниченном количестве. Известны стоимости размещения предприятий в указанных пунктах и затраты на удовлетворение спроса каждого клиента. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Введем некоторые обозначения: