Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения
Раздел: Рефераты по математике
Тип: статья Добавлен 13:57:09 24 марта 2007 Похожие работы
Просмотров: 205 Комментариев: 3 Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать

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

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:53:11 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:53:01 24 ноября 2015
мля что куйня я не ето совсем искал !!!!8(
ЯR19:02:11 01 июня 2007Оценка: 2 - Плохо

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150529)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru