Рефетека.ру / Математика

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

А.А. Колоколов, Т.В. Леванова, Институт информационных технологий и прикладной математики СО РАН

1. Введение

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

Рассмотрим ПЗР в следующей постановке. Дано конечное множество пунктов возможного размещения предприятий и список клиентов. Предприятия производят однородный продукт в неограниченном количестве. Известны стоимости размещения предприятий в указанных пунктах и затраты на удовлетворение спроса каждого клиента. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Введем некоторые обозначения:

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

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

ci - стоимость размещения предприятия в пункте i;

tij - затраты на удовлетворение спроса клиента j предприятием i (включающие издержки на производство и транспортировку);

xij - часть всей продукции, которую необходимо доставить с предприятия i клиенту j;

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

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

Мы используем следующую модель ПЗР:

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

(1)

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

(2)

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

(3)

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

(4)

2. Алгоритм перебора L - классов

В [?] и других работах развивается подход к анализу и решению задач целочисленного программирования, основанный на регулярных разбиениях пространства Rn. Много результатов было получено с помощью L-разбиения.

Дадим определение L-разбиения. Пусть Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения- символы лексикографического порядка. Точки Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияявляются L-эквивалентными, если не существует Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, такой что Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Это отношение разбивает любое множество Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияна классы эквивалентности, которые называются L-классами. L-разбиение обладает рядом важных свойств.

1) Каждая точка Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияобразует отдельный L - класс. Остальные классы состоят только из нецелочисленных точек и называются дробными.

2) Если X ограниченное множество, то фактор-множество X/L - конечно.

3) L - разбиение согласовано с лексикографическим порядком, то есть для любого X все элементы X/L могут быть линейно упорядочены следующим образом: Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещениядля всех Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения.

Если X ограничено, то X/L можно представить в виде

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

Рангом L - класса V называется число Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, если V дробный L - класс и r(V) = n+1 для любой целой точки.

Алгоритм перебора L - классов основан на идее поиска элемента L - разбиения, непосредственно следующего за данным L - классом в порядке лексикографического возрастания (для задачи на минимум).

Пусть Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Рассмотрим этот метод более подробно для многогранника Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Задача булева программирования (БП) имеет вид:

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

(5)

Соответствующая задача линейного программирования (ЛП) состоит в нахождении лексикографически минимального элемента множества M.

Пусть Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияи известен некоторый представитель Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Сначала мы ищем соседний к V дробный элемент V' такой, что Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещениягде r - ранг класса V, и x - некоторая точка из V'. Если V' будет найден, продолжаем процесс для V' вместо V.

В противном случае мы ищем V' такой, что Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, - ранг V', Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Если V' не может быть найден, мы уменьшаем (если это возможно) r' на 1 и продолжаем просмотр. Если V' будет найден, мы возвращаемся к началу процедуры и V' становится исходным L - классом.

Если не существует соседнего дробного L-класса, то либо мы получаем оптимум задачи БП, либо приходим к выводу, что задача не имеет решения. Процесс является конечным, так как M ограничено.

Опишем алгоритм перебора L - классов. Для простоты номер итерации будем опускать.

Шаг 0. Решаем исходную задачу ЛП. Если она не имеет решения или ее решение целочисленное, процесс завершается. В противном случае идем на шаг 1.

Шаг 1. Обозначим через Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияоптимальное решение задачи ЛП, которая рассматривалась на предыдущем шаге. Находим

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

Формируем задачу ЛП путем добавления к исходной ограничений

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

Ее целевая функция Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Находим решение x' этой задачи. Возможны случаи:

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

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

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

b) x'p = 1; идем на шаг 1.

Шаг 2. Находим максимальный номер Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, такой, что Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Формируем задачу ЛП, добавляя к исходной следующие ограничения:

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

ее целевая функция Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Находим решение x' этой задачи. Возможны варианты:

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

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

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

В результате работы алгоритма перебора L-классов мы получаем лексикографически монотонную последовательность представителей L-классов множества M/L.

3. Декомпозиционный алгоритм

После фиксирования всех переменных zi мы получаем из (1)-(4) транспортную задачу T(z) и соответствующую ей двойственную задачу D(z) с переменными Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, которая имеет вид

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

(6)

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

(7)

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

(8)

Оптимальное решение этой задачи используется для построения отсечения Бендерса.

Опишем основные шаги декомпозиционного алгоритма.

Предварительный шаг. Формулируем исходную задачу целочисленного программирования P(1): найти лексикографически минимальное решение системы, состоящей из неравенства

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

и нескольких ограничений вида

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

(9)

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

Обозначим 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, Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

Шаг 1. Решаем задачу P(k) с помощью алгоритма перебора L - классов. Если мы не можем получить допустимого решения, то F(k-1) - оптимальное значение целевой функции, z(k-1) и x(k-1) - оптимальное решение исходной задачи. Процесс решения заканчивается.

Иначе переходим на шаг 2.

Шаг 2. Формулируем и решаем транспортную задачу T(z(k)). Эта задача имеет оптимальное решение x(k), более того, можно получить все Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения(см. [8]). Мы находим также значения двойственных переменных u(k), v(k). Вычисляем Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Если

F(z(k), x(k)) < F(k-1), тогда F(k-1) заменяем на F(k) в системе отсечений задачи P(k).

Переходим на шаг 3.

Шаг 3. Строим следующее ограничение (отсечение Бендерса):

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

(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.

Похожие работы:

  1. • Некоторые свойства многогранника. Задачи о P ...
  2. • Понятие алгоритма, его свойства. Описание алгоритмов с ...
  3. • Комбинаторные задачи
  4. • Интуитивное понятие алгоритма и его свойств
  5. • Алгоритмы поиска подстроки в строке
  6. • Алгоритмы поиска подстроки в строке
  7. • Кодирование различных типов информации. Состав ...
  8. • Проблемы создания искусственного интеллекта
  9. • Способы описания алгоритма. Виды операторов
  10. • Программирование на Паскале
  11. • Методы и алгоритмы компоновки, размещения и трассировки ...
  12. • Возможен ли искусственный интеллект
  13. • Построение маршрута при групповой рассылке сетевых ...
  14. • Сущность искусственного интеллекта
  15. • Алгоритмизация процесса обучения младших школьников
  16. • Теоретические основы алгоритмизации процесса обучения младших ...
  17. • Блочно-симметричные модели и методы проектирования ...
  18. • Задача Y- пентамино
  19. • Алгоритмизация задач
Рефетека ру refoteka@gmail.com