Введение
1 О труднорешаемых задачах о назначениях 32
1.1 Планарная m-слойная 3-индексная задача о назначениях на одноциклических подстановках 32
1.1.1 Постановка задачи 32
1.1.2 Алгоритм приближённого решения задачи 33
1.1.3 Общий вероятностный анализ алгоритма 36
1.1.4 Случай равномерного распределения 39
1.2 Задача о назначениях с ограничениями на циклы в подстановке 45
1.2.1 Постановка задачи 45
1.2.2 Описание TSP-подхода 46
1.2.3 Результаты применения TSP-подхода 47
1.3 О разрешимости аксиальной 8-индексной задачи о назначениях на одноциклических подстановках 53
1.3.1 Постановка задачи 53
1.3.2 Предварительные замечания 55
1.3.3 Разрешимость задачи 8-АЗНО 59
2 2 Задача нескольких коммивояжеров с различными весовыми функциями маршрутов 73
2.1 Постановка задачи 73
2.2 Приближённый алгоритм решения задачи 74
2.3 Вероятностный анализ алгоритма
2.3.1 Входные данные с усеченным нормальным распределением 77
2.3.2 Входные данные с показательным распределением 80
3 Задача нескольких коммивояжеров с одинаковыми весовыми функциями маршрутов 85
3.1 Постановка задачи 86
3.2 Подход к приближённому решению задачи
3.2.1 Об алгоритмах нахождения гамильтонова цикла в случайном графе 88
3.2.2 Алгоритм Гимади-Перепелицы 1973 89
3.2.3 Алгоритм Angluin-Valiant 1979 92
3.3 Вероятностный анализ подхода 94
3.3.1 Непрерывное распределение входных данных 94
3.3.2 Дискретное распределение входных данных 100
Заключение 103
Публикации автора по теме диссертации 105
Благодарности 109
Литература
