Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!
Реферат

Реферат по предмету "Математика"


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

Алгоритмы декомпозиции и перебора 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

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))

Переходим
на шаг 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/


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Происхождение земли
Реферат Декомпрессия
Реферат Анализ работы Вертгеймера "Продуктивное мышление"
Реферат Jungle Essay Research Paper The Jungle written
Реферат Образ преподобного Сергия Радонежского в Сказании Авраамия Палицына об осаде Троице-Сергиева монастыря
Реферат Учет материально-производственных запасов на примере предприятия ОАО АвтоВАЗагрегат
Реферат Вывоз капитала из России 3
Реферат Психиатрия. Рекуррентная депрессия
Реферат Международная организация уголовной полиции Интерпол
Реферат Анализ организации контроля исполнения документов
Реферат Активизация познавательной и творческой деятельности младших школьников во внеурочное время
Реферат Криминалистическая характеристика преступления
Реферат Международные гостиничные правила были впервые опубликованы Международной гостиничной ассоциацией 60 лет назад
Реферат Muscle Development Essay Research Paper The Upper
Реферат Alexander The Great Essay Research Paper IntroductionAlexander