Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Ченцов, Павел Александрович
01.01.09
Кандидатская
2004
Екатеринбург
147 с. : ил.
Стоимость:
499 руб.
Список сокращений и обозначений
Глава I. Задачи распределения в группы
1. Введение
2. Оптимизация разбиений измеримого пространства в условиях неточных вычислений
3. Разбиение в сумму интервалов натурального ряда
4. Оценки и алгоритмы на их основе
5. Вычислительный эксперимент
Глава II. Маршрутные задачи с ограничениями
1. Введение
2. Задача коммивояжера с ограничениями
3. Задача курьера
4. Один приближенный метод решения задачи коммивояжера
5. Вычислительный эксперимент
Список литературы
А Приложение
Список сокращений и обозначений
ДП — динамическое программирование. ЗК — задача коммивояжера, п/м — подмножество, в/з — вещественнозначное N — натуральный ряд.
•М, = {0} и АГ = {0; 1; 2;
М. — множество вещественных чисел, д
= - равенство по определению
Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий. В качестве основного используется метод динамического программирования. Кроме того, рассматриваются приближенные методы. Задачи такого рода возникают, например, в приложениях, связанных с распределением потока задач в многопроцессорных вычислительных комплексах, транспортными задачами, распределением товаров и грузов по складам и хранилищам, распределением работ между исполнителями и т.д. При решении такого рода задач возникают, однако, существенные трудности с организацией вычислений. Так, например, в известной задаче коммивояжера с п городами возникает п вариантов конкретного выбора маршрута. Данная задача является ИР-полной (см. в этой связи [16]). Поэтому представляется важным построение быстродействующих приближенных алгоритмов, использующих специфику той или иной конкретной задачи. С другой стороны, представляется важным исследование структуры решения, что может, в частности, осуществляться посредством применения различных модификаций известного метода динамического программирования Р.Беллмана (см. [3], [5], [25], [40]). Отметим, в частности, применение метода динамического программирования для решения задачи коммивояжера [4], [49]. Для решения этой актуальной задачи применялись и другие методы (точные и приближенные). Отмстим, в частности, известный метод ветвей и границ [37], а также процедуры сведения замкнутой версии задачи к незамкнутой [37] в связи с конструкциями данной работы. Следует упомянуть о естественных связях задачи коммивояжера
Покажем, что Т*(Кі) = T)**(/6“) Vi Є I,п. Возьмем произвольный номер і Є 1, тг. Рассмотрим более детально значения
Т.*(КЛ = таxwj — minWj, Т.**(К?) = тахгв? — min wf
1 к ' jeKi J jeKi J г г J jeK« 1 jeK? J
Т.*(КЛ = таxw — min w, T**(K?) = max w — min w,
1 4 ' weWi tue Wi 1 4 1 ' w£W,° W&W?
где Wi = {Wl:l 6 Ki}, a Wta = {wf : l G Kf}. Ho W? = {wa(l) : l G Kf}, а так как Kf = {a_1(y) : j G Ki}, то справедливо следующее выражение W° — {wQ(a-i(p) : l G Ki}, т.е. Wf = {иц : l G К,}-, итак W{ совпадает с W°, откуда следует, что
Т*(Кг)=ТГ(К?) (1.3.33)
Итак, из (1.3.33), (1.3.31) и (1.3.28) следует, что любому разбиению
№)ієРп є А* (1,1V) можно поставить в соответствие разбиение (K?)ie^ G Д* (1, IV) так, что
Т*(№ети) = ГД(АГ?)І6І^). (1.3.34)
Напротив, любому разбиению (АТг);еГп Є Д«(1> ^0 можно сопоставить разбиение'(АГг)геу^ 6 Д*(1, IV) так, что (в упомянутых ранее обозначениях)
(КГЪе тп = (^)геТН- (1-3-35)
Именно, следует полагать при г 6 1,п, что /б, == {«(у) : у 6 /б*}. Применяя операцию
-> (*?)геТЛ> определенную ранее, получаем: при в Е 1,п
/с = (а-х(у) : у 6 бб3} = {а-х(а(у)) : У € Тб5} - /б5.
Название работы | Автор | Дата защиты |
---|---|---|
Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти | Салищев, Сергей Игоревич | 2016 |
Задачи наилучшего выбора с разладкой | Ивашко, Евгений Евгеньевич | 2009 |
Тестовые задачи на графах | Дебрев, Евгений Валерьевич | 2004 |