Введение
1 Приближенные алгоритмы решения много индексной аксиальной задачи о назначениях 27
1.1 Многошідексная аксиальная задача о назначениях 27
1.1.1 Постановка задачи 27
1.1.2 Нриближепный алгоритм 28
1.2 Трсхиндексньге аксиальные задачи о назначениях с одной од поцикличсской подстановкой 31
1.2.1 Постановка задачи 31
1.2.2 Приближенный алгоритм 32
1.3 Трехиндексные аксиальные задачи о назначениях с двумя од поциклическими подстановками 34
1.3.1 Постановка задачи 34
1,3.2 Приближенный алгоритм 34
1.4 Трехиндексная аксиальная задача о назначениях наодноциклических подстановках на минимум 36
1.4.1 Постановка задачи 30
1.4.2 Приближенный алгоритм 37
1.4.3 Корректность работы алгоритма 40
1.4.4 Анализ оценок качества алгоритма 44
1.5 Трех индексная аксиальная задача о назначениях на одноциклических подстановках на максимум 45
1.5.1 Постановка задачи 45
1.5.2 Приближенный алгоритм 4G
1.5.3 Анализ корректности работы и оценок качества алгоритма 47
1.6 Разрешимость многоиндексной аксиальной задачи о назначениях на одноциклических подстановках 53
1.6.1 Постановка задачи 53
1.6.2 Предварительные замечания и необходимый признак разрешимости задачи 54
1.6.3 Критерий разрешимости 7-иидсксной задачи 56
1.6.4 Заключительные замечания о разрешимости многоиндексной задачи 62
2 Приближенные алгоритмы решения трехиндекснои планарной задачи о назначениях 63
2.1 m-слойная планарная задача о назначениях 63
2.1.1 Постановка задачи 63
2.1.2 Приближенный алгоритм для случая т < тг/2 64
2.1.3 Анализ работы алгоритма 65
2.2 Двухслойная планарная задача о назначениях с одной одноциклической подстановкой 69
2.2.1 Постановка задачи 69
2.2.2 Приближенный алгоритм 70
2.3 Двухслойная планарная задача о назначениях па одноцикличсских подстановках 72
2.3.1 Постановка задачи 72
2.3.2 Приближенный алгоритм . , 73
2.3.3 Постановка задачи в терминах теории графов , . 74
2.3.4 Алгоритм с оценкой точности 9/4 + 0(1/п) для метрической задачи с одинаковой весовой функцией . 75
2.3.5 Обоснование оценок точности алгоритма 77
2.3.6 Алгоритм с оценкой точности 12/5 + 0(1/п} для метрической задачи с разными весовыми функциями . 78
2.3.7 Обоснование оценок точности алгоритма 80
2.4 Двухслойная планарная задача о назначениях на одпоциклических подстановках на максимум 86
2.4.1 Постановка задачи 86
2.4.2 Приближенный алгоритм с константной оценкой точности 3/4 86
2.4.3 Обоснование оценок точности алгоритма 89
Заключение 94
Список публикаций автора по теме диссертации 97
Благодарности 99
Список литературы 100
