Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Истомин, Алексей Михайлович
01.01.09
Кандидатская
2015
Новосибирск
101 с. : ил.
Стоимость:
499 руб.
Оглавление
Введение
1 Задача нескольких коммивояжёров с входными данными специального вида
1.1 Постановка задачи
1.2 Алгоритм приближенного решения задачи
1.2.1 Вспомогательная процедура построения гамильтоновой цени . .
1.2.2 Описание алгоритма решения задачи
1.2.3 Описание входных данных
1.3 Вероятностный анализ алгоритма
1.3.1 Входные данные, распределённые по нормальному закону
1.3.2 Входные данные, распределённые по показательному закону . .
2 Задача двух коммивояжёров с ограничениями на пропускные способности рёбер
2.1 Постановка задачи и предварительные сведения
2.2 Новые алгоритмы решения задач на минимум и па максимум с общей весовой функцией
2.'2.1 Описание1 вспомогательной процедуры
2.3 Анализ точности алгоритмов в среднем
2.3.1 Анализ алгоритма для задачи на минимум
2.3.2 Анализ алгоритма для задачи на максимум
2.4 Новые алгоритмы решения задач на минимум и па максимум с различными весовыми функциями маршрутов
2.4.1 Описание вспомогательной процедуры
2.5 Анализ ючноети алгоритмов в среднем
2.5.1 Анализ алгоритма для задачи на минимум
2.5.2 Анализ алгоритма для задачи па максимум
3 Задача маршрутизации транспортных средств в евклидовом пространстве
3.1 Предварительные сведения
3.2 Случай равномерного распределения на круге единичной площади
Заключение
Публикации автора по теме диссертации
Благодарности
Литература
Введение
Современный Экономический прогресс во многом обусловлен научным подходом к решению задач ортанизацнп предприятий: оі дизайна изделий и эффективной ор-гапизадии производства до ценообразования н целесообразно выстроенной дени доставки продукции до конечного потреби юля.
Для эффективного решения таких проблем возникает необходимость построения математических моделей реальных процессов и алгоритмов решения возникающих при этом задач. Как правило, решение этих задач связано со значительными трудностями вычислительного харакк'ра. Общее представление о сложности таких задач дает книга [18]. В этой книге приводится более 500 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых построение эффективных алгоритмов их решения в настоящее время считается маловероятным.
Появление вычислительной техники привело к тому, что все реже приходится решать отдельную конкретную задачу, а все больше писать программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому имеет смысл говорить о сложности не для одной индивидуальной задачи /.
Пусть 1п п < т < /I1 " < п/Л. Положим
6 т +
Возьмем Е = а„(‘3пг + Зн?). Поскольку ь -лом случае ОТ < (Зпг + 6т)п„ = ,г, по теореме Петрова имеем:
Рг{/д > (1 +С„)ОРТ} < Рг{5 > .г} < ехр = ехр(--"Г + °Ш) < = ^
Таким образом, поскольку величины сп и 8п стремятся к 0 с ростом п. алгоритм А в условиях теоремы асимптотически точен.
Название работы | Автор | Дата защиты |
---|---|---|
Исследование и решение минимаксных и минисуммных задач размещения на сетях | Филимонов, Дмитрий Валерьевич | 2004 |
Вопросы оптимальности в теории синхронизируемых автоматов | Прибавкина, Елена Владимировна | 2009 |
Обмен информацией в иерархических системах управления в условиях неопределенности | Фоменко, Павел Вячеславович | 1984 |