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

2) , тогда, если

a) x'p < 1; если p=1, процесс завершается, в противном случае идем на шаг 2;

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)) < F(k-1), тогда F(k-1) заменяем на F(k) в системе отсечений задачи P(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-медиане. В результате расчетов получены следующие данные: