Статья

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

Работа добавлена на сайт bukvasha.net: 2015-10-29

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 21.4.2025



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

- число 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/



1. Реферат на тему Objectivity In Journalism Essay Research Paper Merriam
2. Диплом Социальная реклама благотворительных фондов и органов опеки и попечительства Воронежской области
3. Статья на тему Молитва Годунова
4. Статья на тему Обеспечение безопасности технологических процессов добычи переработки транспортировки нефти и газа
5. Реферат Занятия физической культурой при миопии отягощенной астигматизмом средней степени
6. Реферат на тему Irony Essay Research Paper Assignment Freewrite on
7. Курсовая Трехфазные электротехнические устройства
8. Книга Загальнотеоретичні проблеми адвокатології, Синеокий
9. Реферат на тему Качество продукции и организация технического контроля
10. Реферат на тему Setting Used In Edgar Allan Poe