Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

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

Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники
Горшок торфяной для цветов.
Рекомендуются для выращивания крупной рассады различных овощных и цветочных, а также для укоренения саженцев декоративных, плодовых и
7 руб
Раздел: Горшки, ящики для рассады
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения А.А. Колоколов, Т.В. Леванова, Институт информационных технологий и прикладной математики СО РАН 1. Введение В описаны алгоритмы для решения частично целочисленных задач производственно-транспортного типа, основанные на идее декомпозиции Бендерса и метода направленного перебора. В данной работе предлагаются декомпозиционные алгоритмы для простейшей задачи размещения (ПЗР), задачи о p-медиане и некоторых других постановок, в которых наряду с отсечениями Бендерса для решения целочисленной подзадачи используется лексикографический перебор L-классов . Рассмотрим ПЗР в следующей постановке. Дано конечное множество пунктов возможного размещения предприятий и список клиентов. Предприятия производят однородный продукт в неограниченном количестве. Известны стоимости размещения предприятий в указанных пунктах и затраты на удовлетворение спроса каждого клиента. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Введем некоторые обозначения: m - число пунктов возможного размещения предприятий, i - номер предприятия, - число клиентов, j - номер клиента, ci - стоимость размещения предприятия в пункте i; ij - затраты на удовлетворение спроса клиента j предприятием i (включающие издержки на производство и транспортировку); xij - часть всей продукции, которую необходимо доставить с предприятия i клиенту j; Обозначим . Мы используем следующую модель ПЗР:     (1)     (2)     (3)     (4) 2. Алгоритм перебора L - классов В и других работах развивается подход к анализу и решению задач целочисленного программирования, основанный на регулярных разбиениях пространства R . Много результатов было получено с помощью 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) = 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 &l ; 1; если p=1, процесс завершается, в противном случае идем на шаг 2; b) x'p = 1; идем на шаг 1. Шаг 2. Находим максимальный номер , такой, что . Формируем задачу ЛП, добавляя к исходной следующие ограничения:       ее целевая функция . Находим решение x' этой задачи. Возможны варианты: 1) , процесс завершается; 2) , тогда возможны случаи: a) ; если , процесс завершается, иначе и переходим на шаг 1. В результате работы алгоритма перебора L-классов мы получаем лексикографически монотонную последовательность представителей L-классов множества M/L. 3. Декомпозиционный алгоритм После фиксирования всех переменных zi мы получаем из (1)-(4) транспортную задачу (z) и соответствующую ей двойственную задачу D(z) с переменными , которая имеет вид     (6)     (7)     (8) Оптимальное решение этой задачи используется для построения отсечения Бендерса. Опишем основные шаги декомпозиционного алгоритма. Предварительный шаг. Формулируем исходную задачу целочисленного программирования P(1): найти лексикографически минимальное решение системы, состоящей из неравенства       и нескольких ограничений вида     (9)       Обозначим z(k), x(k) , v(k), u(k) - оптимальные решения задач P(k), (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. Формулируем и решаем транспортную задачу (z(k)). Эта задача имеет оптимальное решение x(k), более того, можно получить все (см. ). Мы находим также значения двойственных переменных u(k), v(k). Вычисляем . Если F(z(k), x(k)) &l ; 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-классов . Нами разработаны и другие варианты перебора  L-классов. Описанный алгоритм является конечным и дает оптимальное решение простейшей задачи размещения. На каждой итерации мы рассматриваем систему типа (9). Число дополнительных ограничений монотонно растет. Мощность системы ограничений можно ограничить и применить процедуру отбрасывания отсечений. Нами предложен также ряд приближенных алгоритмов. Схема алгоритма в основном остается такой же для задачи о p-медиане и других постановок задач размещения. Специфика задач учитывается в процедурах решения производственной и транспортной задач. Нами был реализован вариант описанного алгоритма, проведены экспериментальные исследования на IBM PC/A -486 для простейшей задачи размещения и задачи о p-медиане. В результате расчетов получены следующие данные: - число L-классов, просматриваемых на каждой итерации, и их общее число; - количество использованных отсечений и время счета; - доля L-классов, анализируемых после нахождения оптимального решения; - о поведении алгоритма на примерах с различным соотношением производственных и транспортных затрат и другие характеристики. Список литературы Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978.-167с. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. - 335 с. Заикина Г.М., Колоколов А.А., Леванова Т.В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 25-41. Колоколов А.А. Применение регулярных разбиений в целочисленном программировании // Известия вузов. Математика. 1993. .12. С. 11-30. Колоколов А.А. Регулярные разбиения в целочисленном программировании //Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 67 - 93. Kolokolov A.A. O he L-s ruc ure of he i eger li ear programmi g problems. //Proceedi gs of he 16 h IFIP- C7 Co fere ce o Sys em Modelli g a d Op imiza io . Compieg e. Fra ce, 1993. P. 756-760. Kolokolov A.A., Leva ova .V. Some L-class E umera io Algori hms for Simple Pla Loca io Problem // Abs rac s of I er a io al Co fere ce o Opera io s Research. Berli , 1994. P.75. Krarup J., Pruza P.M. he simple pla loca io problem: survey a d sy hesis // Europ. J. of Oper. Res., 1983. .12. P. 36-81.

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

1. Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.

2. Физическая активность студентов на Севере и стадии изменения поведения, связанного с выполнением физических упражнений

3. Применение метода частотных диаграмм к исследованиям устойчивости систем с логическими алгоритмами управления

4. Алгоритмы выполнения манипуляций

5. Разработка алгоритмов контроля и диагностики системы управления ориентацией космического аппарата

6. Алгоритмы экономической (кадастровой) оценки городских земель и территориально-экономического зонирования
7. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры
8. Информационные потоки в ЭВМ. Алгоритм работы процессора

9. Алгоритмы сортировки

10. Написание игровой программы Tetris и описание алгоритма

11. VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

12. Алгоритм создания базы данных складского учета

13. Компьютерный файлово-загрузочный полиморфный стелс-вирус ONEHALF 3544, особенности алгоритма и методы борьбы с ним

14. Алгоритм компактного хранения и решения СЛАУ высокого порядка

15. Алгоритмы и протоколы маршрутизации

16. Практика перевода числа из одной системы счисления в другую + блок-схема алгоритма определения наименьшего числа

Папка для труда "Спортивное авто", 325х245 мм.
Размер: 325х245 мм. Материал: ткань.
322 руб
Раздел: Папки для труда
Машинка детская с полиуретановыми колесами "Бибикар спорт", красный.
Все еще не можете определиться, что подарить ребенку на торжество? Куклы и конструкторы уже негде складывать, а удивить малыша очень
2150 руб
Раздел: Каталки
Планшетик "Кто самый умный?".
Этот говорящий планшетик – прекрасный подарок для маленьких эрудитов! 200 умных вопросов, 20 игровых тем, 3 уровня – играй и узнавай много
445 руб
Раздел: Планшеты и компьютеры

17. Разработка средств оценки эффективности алгоритмов поиска и обнаружения целей прицельных радиоэлектронных комплексов

18. Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры

19. Сравнительный анализ нейросетевых реализаций алгоритмов распознавания образов

20. Генетический алгоритм

21. Структуры данных и алгоритмы

22. Алгоритм компактного хранения и решения СЛАУ высокого порядка
23. Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
24. Интуитивное понятие алгоритма и его свойств

25. Некоторые алгоритмы реализации UPSCALING

26. Декларация или алгоритм новой школы

27. Современные алгоритмы антибактериальной терапии сепсиса

28. Алгоритм расчета стоимости оказания медицинской и фармацевтической помощи пациентам с хронической алкогольной интоксикацией

29. Алгоритм развития для науки

30. Об алгоритмах самоорганизации в задаче синтеза информационных технологий обработки сигналов

31. Способ устойчивого решения неустойчивых задач и его алгоритм

32. Системный подход и алгоритм управления подготовкой студентов к духовно-просветительской деятельности

Шкатулка "Шиповник" (36x26x18 см).
Шкатулка очень удобна в использовании, и к тому же станет украшением вашего домашнего интерьера! Размер: 36x26x18 см. Оформление корпуса:
2706 руб
Раздел: Шкатулки для рукоделия
Френч-пресс, 1000 мл.
Френч-пресс Rosenberg изготовлен из высококачественной нержавеющей стали и термостойкого стекла. Удобная ненагревающаяся ручка.
503 руб
Раздел: Френч-прессы
Заварочный чайник эмалированный Mayer & Boch "Подсолнух", 1,5 л, с ситечком.
Заварочный эмалированный чайник. Материал корпуса: углеродистая сталь. Толщина стенок - 0,8 мм. Внешнее и внутреннее покрытие -
715 руб
Раздел: Чайники заварочные

33. Алгоритмы трассировки

34. Алгоритм создания сценария рекламного радиоролика

35. Составление алгоритма расчета расхода сырья верхних трикотажных изделий

36. Образ государства как алгоритм политического поведения

37. Типовой алгоритм составления бюджета

38. СППР фінансового аналізу на базі алгоритмів нечіткої логіки
39. Постановка и разработка алгоритма решения задачи Учёт основных средств
40. Алгоритм и программа

41. Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала

42. Генетические алгоритмы

43. Алгоритм определения динамических характеристик гидроупругих систем для управления гидросооружениями

44. Формализация понятия алгоритма

45. Анализ алгоритма вируса

46. Алгоритмы выделения контуров

47. Конфигурирование програмного обеспечения алгоритмов IGRP, EIGRP на маршрутизаторе Cisco

48. Понятие алгоритма

Мягкая игрушка "Волк. Забивака", 24 см.
Этот обаятельный, улыбчивый символ Чемпионата мира по футболу ещё и сувенир в память о событии мирового масштаба на всю жизнь! Уже
1280 руб
Раздел: Игрушки, фигурки
Портмоне для CD/DVD "Brauberg", на 96 дисков.
Вмещает 96 CD/DVD дисков. Цвета - ассорти (синий, черный, красный, серый). Тканевая окантовка. Застежка - молния. Обложка - пластик. Цвет
487 руб
Раздел: Боксы, сумки для CD, DVD
Шахматы обиходные, деревянные с доской.
Шахматы - настольная логическая игра со специальными фигурами на 64-клеточной доске для двух соперников, сочетающая в себе
660 руб
Раздел: Шахматы

49. Разработка алгоритмов и программных средств подсистемы документооборота системы управления содержанием информационного сервера

50. Алгоритм сжатия "Unbuffered RLE"

51. Алгоритм «рамо»

52. Модификация алгоритма определения клик графа с параметрической адаптацией

53. Методика и алгоритмы контроля работоспособности и диагностики сейсмометрических каналов

54. Варианты алгоритма возведения в степень: повышение точности и ускорение
55. Алгоритм нисходящего разбора. Нисходящие распознаватели
56. Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка

57. Циклические алгоритмы

58. Разработка программы, реализующей алгоритм шифрования ГОСТ 28147-89

59. Исследование и разработка алгоритмов программной среды взаимодействия рабочих станций вычислительных сетей

60. Генетический алгоритм

61. Методы и алгоритмы построения элементов систем статистического моделирования

62. Математическая логика и теория алгоритмов

63. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

64. Алгоритм внедрения управленческого абсолюта

Конструктор электронный "Знаток". 180 схем, артикул 180-Znat.
Набор электронных блоков и соединений, позволяющий конструировать электрические цепи без пайки. В иллюстрированном руководстве описано 180 схем.
1815 руб
Раздел: Инженерные, научно-технические
Полка для ванной (сиденье) (белый).
Материал: пластик. Длина: 680 мм. Ширина: 310 мм. Высота: 40 мм. Выдерживает вес до 100 кг.
451 руб
Раздел: Решетки, сиденья для ванны
Ручки гелевые "Lipari", 30 цветов.
Набор ручек гелевых. В наборе: 30 цветов (0,5 мм - 4 штуки, 0,8 мм - 6 штук, неон - 6 штук, флуоресцентные - 6 штук, металлик 1 мм - 8
311 руб
Раздел: Цветные

65. Групповой полет летательных аппаратов – алгоритм обработки информации относительного движения.

66. Алгоритм ситуационного анализа для разрешения конфликтных ситуаций

67. Общий алгоритм оценки эффективности рекламной кампании

68. Горные породы, алгоритмы их определения

69. Алгоритм и его свойства

70. Алгоритм криптографического преобразования в режиме простой замены
71. Алгоритм работы программы "Консультант Плюс"
72. Алгоритми сортування

73. Алгоритмічні мови програмування

74. Алгоритмы вокруг нас

75. Алгоритмы и организация данных

76. Алгоритмы на графах. Кратчайшие расстояния на графах

77. Алгоритмы параллельных процессов при исследовании устойчивости подкрепленных пологих оболочек

78. Алгоритмы поиска подстроки в строке

79. Алгоритмы сжатия данных

80. Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

Кольцеброс с корзинами и мячами.
Спортивная игра. Цель играющих - набросить кольца с установленного расстояния на один из четырех вертикальных стержней, так чтобы кольца
470 руб
Раздел: Кольцебросы, кегли
Рюкзак "Стрит", черный.
Практичный рюкзак с универсальным дизайном подойдет для тех, кто в первую очередь ценит комфорт и сохранность своих вещей. Станет надежным
330 руб
Раздел: Без наполнения
Комплект детского постельного белья 1.5 "Принцесса".
Постельное белье из бязи выполнено из высококачественного хлопка, что гарантирует крепкий и здоровый сон. Комплект не требует особого
1498 руб
Раздел: Детское, подростковое

81. Алгоритмы численного решения задач

82. Використання генетичних алгоритмів для складання розкладу

83. Интеллектуальные информационные технологии и системы: генетические алгоритмы

84. Компрессия информации и упорядочение дерева по алгоритму Виттера

85. Методические проблемы изучения алгоритмов работы с величинами

86. Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
87. Принципы разработки алгоритмов и программ для решения прикладных задач
88. Программирование на Delphi с алгоритмами и кодами

89. Програмна реалізація криптографічного алгоритму RC5

90. Проектування керуючих автоматів Мура та Мілі за заданою граф-схемою алгоритму

91. Разработка алгоритма работы интеллектуальной информационной системы "Расчет меню"

92. Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов

93. Розробка алгоритмів та складання програм на мові програмування MS VisualBasic for Application

94. Сжатие речи на основе алгоритма векторного квантования

95. Способы описания алгоритма. Виды операторов

96. Структура інформаційної системи. Декомпозиція інформаційних систем

Ножницы "Pigeon" для ногтей новорожденных.
Ножницы для ногтей новорожденных "Pigeon" благодаря маленьким закругленным и тонким лезвиям, позволяют подстригать ногти малыша
721 руб
Раздел: Маникюрные наборы детские
Точилка механическая "Classic", синяя.
Цветной пластиковый корпус с прозрачным контейнером, объемный контейнер для стружки, стальные самозатачивающиеся ножки. Размеры: 91x88x4 мм.
317 руб
Раздел: Точилки
Карандаши металлик, трехгранные, 12 цветов.
Карандаши цветные металлик. Трехгранные. Удобно точить. Прочный грифель. Количество цветов: 12. В ассортименте, без возможности выбора.
324 руб
Раздел: 7-12 цветов

97. Структуры и алгоритмы обработки данных

98. Формализация понятия "алгоритм"

99. Генетические алгоритмы


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.