Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Лагздин, Артем Юрьевич
05.13.18
Кандидатская
2012
Омск
103 с. : ил.
Стоимость:
499 руб.
Оглавление
Введение
1 Задачи оптимального размещения взаимосвязанных объектов на сетях и методы их решения
1.1 Математические модели
1.2 Моделирование прикладных проблем и связь с известными
задачами оптимизации
1.3 Алгоритмы решения
2 Полиномиальные алгоритмы на древовидных сетях для специальных структур связей
2.1 Минисуммный критерий
2.2 Минимаксный критерий
3 Алгоритмы и их экспериментальное исследование для произвольных структур связей
3.1 Параллельный алгоритм динамического программирования на невзвешенной древовидной сети
3.2 Экспериментальное исследование параллельного алгоритма
3.3 Алгоритм поиска приближенного решения для произвольных сетей
Заключение
Литература
Приложение
Приложение
Введение
Задачи оптимального размещения объектов имеют много практических приложений. Их необходимо решать при проектировании генеральных планов предприятий, расстановке технологического оборудования в цехах, размещении элементов на печатных платах, определении мест расположения пунктов обслуживания и выполнении других работ.
Первые попытки анализа задач оптимального размещения относятся к XVII веку, когда Ферма сформулировал следующую задачу: найти точку на плоскости, сумма евклидовых расстояний от которой до трех фиксированных минимальна. В начале XX века ее обобщил Вебер, рассматривая произвольное число точек, которым приписаны веса. Более детальные исследования задач размещения связаны с появлением и развитием исследования операций.
По признаку наличия фиксированных связей между объектами задачи оптимального размещения можно разбить на два класса - размещение взаимосвязанных объектов и размещение-распределение [30]. В задачах первого класса требуется найти позиции для размещения объектов с заранее заданной структурой связей между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера [4,12,14-16,25-27,42-44,47,48,50,51,54,57-59,61,63-77,79, 81,83,84,87-89,91,93,94]. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача
сопоставим каждому узлу кг £ У0(тг) поддерево гД(ж) = (Ц(тг),и7г)), обозначим ?7(ж) = |1К'('7г){&г}|- Функцию Г можно представить как сумму весов ребер сети Т с неотрицательными целыми коэффициентами
*'(*)= XI аФ)гШМз)), (2-1)
{7г(г),7г и)}еи
где г(7г(г),7г(у)) - вес ребра {7г(г),7гф')} £ С/, а(ж) £ Z+. Поясним данное представление. Для любого к — 1
р(п(Н),тт(к +1)) = г(тг(к),п(1)), (2.2)
{тг(*:))7г(г)}еСД.Л+1
где £Дд+1 С и - множество ребер кратчайшего пути между узлами ж (к) и 7г{к+ 1). Заменив в функции (1.5) выражение р(ж(к),ж(к + 1)) согласно (2.2) для всех к = 1
Заметим, что по построению, в размещении ж*, полученном алгоритмом Ате, справедливо а.ц{ж*) — 1 для всех ребер (тг*(г), 7г*(у)} £ и0(ж*) И ОьД7Г*) = 2 ДЛЯ всех ребер {тг*(з), 7Г*(£)} € {/;(7Г*), I — 1
Отметим некоторые свойства коэффициентов ац (ж) в зависимости от размещения тт. Произвольное ребро и = {тг(г), 7г(у)} £ II разбивает множество узлов V сети Т на два подмножества Ац(ж) = = {п(к) £ Уж(к) соединен с ж(г) цепью, не содержащей ребра
н} и (тг(г)} и А(ж) = {7г(£;) £ Уж(к) соединен с ж(у) цепью, не
содержащей ребра и} и {7г(Д} Имеет место
Лемма 2.1 Значение коэффициента (ж) для произвольного размещения ж цепи Ск на сети Т равно числу пар узлов {ж (к), ж (к + 1)} сети Т таких, что ж (к) и ж (к + 1) не принадлежат одновременно одному множеству Иу (ж) или А*-(ж), к = 1
Доказательство. Рассмотрим произвольную пару узлов {ж(к), 7г(/И-1)} сети Т. В случае, если ж(к),ж(к + 1) £ или
Название работы | Автор | Дата защиты |
---|---|---|
Модель и алгоритмы анализа и сегментации речевого сигнала | Конев, Антон Александрович | 2007 |
Математическая и информационная поддержка методов обработки литературных текстов на основе формально-грамматических параметров | Сидоров, Юрий Владимирович | 2002 |
Математическое моделирование потоков жидкости в разветвленных галереях водопропускных сооружений | Тимофеева Ольга Алексеевна | 2016 |