Обозначим
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).
Шаг
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с.
Рекомендуем скачать другие рефераты по теме: заключение реферата, защита дипломной работы.