Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения (стр. 2 из 2)
Итерация 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-медиане. В результате расчетов получены следующие данные:
- число 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.