Алгоритмы декомпозиции и перебора L-классов для
решения некоторых задач размещения
А.А. Колоколов, Т.В. Леванова, Институт информационных
технологий и прикладной математики СО РАН
1. Введение
В
[1] описаны алгоритмы для решения частично целочисленных задач
производственно-транспортного типа, основанные на идее декомпозиции Бендерса и
метода направленного перебора. В данной работе предлагаются декомпозиционные
алгоритмы для простейшей задачи размещения (ПЗР), задачи о p-медиане [2, 8] и
некоторых других постановок, в которых наряду с отсечениями Бендерса для
решения целочисленной подзадачи используется лексикографический перебор
L-классов [?]. Краткое сообщение о них имеется в [7].
Рассмотрим
ПЗР в следующей постановке. Дано конечное множество пунктов возможного
размещения предприятий и список клиентов. Предприятия производят однородный
продукт в неограниченном количестве. Известны стоимости размещения предприятий
в указанных пунктах и затраты на удовлетворение спроса каждого клиента.
Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы
суммарные производственно-транспортные затраты были минимальны. Введем
некоторые обозначения:
m
- число пунктов возможного размещения предприятий, i - номер предприятия,
n
- число клиентов, j - номер клиента,
ci
- стоимость размещения предприятия в пункте i;
tij
- затраты на удовлетворение спроса клиента j предприятием i (включающие
издержки на производство и транспортировку);
xij
- часть всей продукции, которую необходимо доставить с предприятия i клиенту j;
Обозначим
.
Мы
используем следующую модель ПЗР:
(1)
(2)
(3)
(4)
2. Алгоритм перебора L - классов
В
[?] и других работах развивается подход к анализу и решению задач
целочисленного программирования, основанный на регулярных разбиениях
пространства Rn. Много результатов было получено с помощью L-разбиения.
Дадим
определение L-разбиения. Пусть , - символы
лексикографического порядка. Точки являются
L-эквивалентными, если не существует , такой что . Это
отношение разбивает любое множество на классы
эквивалентности, которые называются L-классами. L-разбиение обладает рядом
важных свойств.
1)
Каждая точка образует
отдельный L - класс. Остальные классы состоят только из нецелочисленных точек и
называются дробными.
2)
Если X ограниченное множество, то фактор-множество X/L - конечно.
3)
L - разбиение согласовано с лексикографическим порядком, то есть для любого X
все элементы X/L могут быть линейно упорядочены следующим образом: для всех .
Если
X ограничено, то X/L можно представить в виде
Рангом
L - класса V называется число , если V
дробный L - класс и r(V) = n+1 для любой целой точки.
Алгоритм
перебора L - классов основан на идее поиска элемента L - разбиения,
непосредственно следующего за данным L - классом в порядке лексикографического
возрастания (для задачи на минимум).
Пусть
. Рассмотрим
этот метод более подробно для многогранника . Задача
булева программирования (БП) имеет вид:
(5)
Соответствующая
задача линейного программирования (ЛП) состоит в нахождении лексикографически
минимального элемента множества M.
Пусть
и известен
некоторый представитель . Сначала мы
ищем соседний к V дробный элемент V' такой, что где r - ранг
класса V, и x - некоторая точка из V'. Если V' будет найден, продолжаем процесс
для V' вместо V.
В
противном случае мы ищем V' такой, что , - ранг V', . Если V' не
может быть найден, мы уменьшаем (если это возможно) r' на 1 и продолжаем просмотр.
Если V' будет найден, мы возвращаемся к началу процедуры и V' становится
исходным L - классом.
Если
не существует соседнего дробного L-класса, то либо мы получаем оптимум задачи
БП, либо приходим к выводу, что задача не имеет решения. Процесс является
конечным, так как M ограничено.
Опишем
алгоритм перебора L - классов. Для простоты номер итерации будем опускать.
Шаг
0. Решаем исходную задачу ЛП. Если она не имеет решения или ее решение
целочисленное, процесс завершается. В противном случае идем на шаг 1.
Шаг
1. Обозначим через оптимальное
решение задачи ЛП, которая рассматривалась на предыдущем шаге. Находим
Формируем
задачу ЛП путем добавления к исходной ограничений
Ее
целевая функция . Находим
решение x' этой задачи. Возможны случаи:
1)
, процесс
завершается;
2)
, тогда, если
a)
x'p
b)
x'p = 1; идем на шаг 1.
Шаг
2. Находим максимальный номер , такой, что . Формируем
задачу ЛП, добавляя к исходной следующие ограничения:
ее
целевая функция . Находим
решение x' этой задачи. Возможны варианты:
1)
, процесс
завершается;
2)
, тогда
возможны случаи:
a)
; если , процесс
завершается, иначе и переходим на
шаг 1.
В
результате работы алгоритма перебора L-классов мы получаем лексикографически
монотонную последовательность представителей L-классов множества M/L.
3. Декомпозиционный алгоритм
После
фиксирования всех переменных zi мы получаем из (1)-(4) транспортную задачу T(z)
и соответствующую ей двойственную задачу D(z) с переменными , которая
имеет вид
(6)
(7)
(8)
Оптимальное
решение этой задачи используется для построения отсечения Бендерса.
Опишем
основные шаги декомпозиционного алгоритма.
Предварительный
шаг. Формулируем исходную задачу целочисленного программирования P(1): найти
лексикографически минимальное решение системы, состоящей из неравенства
и
нескольких ограничений вида
(9)
Обозначим
z(k), x(k) , v(k), u(k) - оптимальные решения задач P(k), T(z(k)), D(z(k))
соответственно, и z(0), x(0) - лучшее из известных решений задачи (1)-(4) со
значением целевой функции F(0).
Итерация
k,
Шаг
1. Решаем задачу P(k) с помощью алгоритма перебора L - классов. Если мы не
можем получить допустимого решения, то F(k-1) - оптимальное значение целевой
функции, z(k-1) и x(k-1) - оптимальное решение исходной задачи. Процесс решения
заканчивается.
Иначе
переходим на шаг 2.
Шаг
2. Формулируем и решаем транспортную задачу T(z(k)). Эта задача имеет оптимальное
решение x(k), более того, можно получить все (см. [8]). Мы
находим также значения двойственных переменных u(k), v(k). Вычисляем . Если
F(z(k),
x(k))
Переходим
на шаг 3.
Шаг
3. Строим следующее ограничение (отсечение Бендерса):
(10)
Переходим
на шаг 4.
Шаг
4. Формулируем задачу P(k+1): найти z, которое является лексикографически
минимальным целочисленным решением системы неравенств задачи P(k) и (10).
Переходим
к следующей итерации (на шаг 1).
Мы
можем построить систему (9), например, используя приближенные комбинаторные
алгоритмы и отсечения Бендерса. На шаге 1 алгоритма можно использовать
L-регулярные отсечения. Вычислительный эксперимент показал эффективность
применения таких гибридных вариантов алгоритма перебора L-классов [3]. Нами
разработаны и другие варианты перебора L-классов.
Описанный
алгоритм является конечным и дает оптимальное решение простейшей задачи
размещения. На каждой итерации мы рассматриваем систему типа (9). Число
дополнительных ограничений монотонно растет. Мощность системы ограничений можно
ограничить и применить процедуру отбрасывания отсечений. Нами предложен также
ряд приближенных алгоритмов.
Схема
алгоритма в основном остается такой же для задачи о p-медиане и других
постановок задач размещения. Специфика задач учитывается в процедурах решения
производственной и транспортной задач.
Нами
был реализован вариант описанного алгоритма, проведены экспериментальные
исследования на IBM PC/AT-486 для простейшей задачи размещения и задачи о
p-медиане. В результате расчетов получены следующие данные:
-
число L-классов, просматриваемых на каждой итерации, и их общее число;
-
количество использованных отсечений и время счета;
-
доля L-классов, анализируемых после нахождения оптимального решения;
-
о поведении алгоритма на примерах с различным соотношением производственных и
транспортных затрат и другие характеристики.
Список литературы
Бахтин
А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи
производственно-транспортного типа. Новосибирск: Наука, 1978.-167с.
Береснев
В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации.
Новосибирск: Наука, 1978. - 335 с.
Заикина
Г.М., Колоколов А.А., Леванова Т.В. Экспериментальное сравнение некоторых
методов целочисленного программирования // Методы решения и анализа задач
дискретной оптимизации. Омск: ОмГУ, 1992. С. 25-41.
Колоколов
А.А. Применение регулярных разбиений в целочисленном программировании //
Известия вузов. Математика. 1993. N.12. С. 11-30.
Колоколов
А.А. Регулярные разбиения в целочисленном программировании //Методы решения и
анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 67 - 93.
Kolokolov A.A. On the L-structure of
the integer linear programming problems. //Proceedings of the 16th IFIP-TC7
Conference on System Modelling and Optimization. Compiegne. France, 1993. P.
756-760.
Kolokolov A.A., Levanova T.V. Some
L-class Enumeration Algorithms for Simple Plant Location Problem // Abstracts
of International Conference on Operations Research. Berlin, 1994. P.75.
Krarup J., Pruzan P.M. The simple
plant location problem: survey and synthesis // Europ. J. of Oper. Res., 1983.
N.12. P. 36-81.
Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/