Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях

• Автор: Коркишко, Наталья Михайловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Новосибирск
• Количество страниц: 116 с. : ил.

Оглавление
Введение

1 Приближенные алгоритмы решения многоиндексной аксиальной задачи о назначениях

1.1 Многоиндексная аксиальная задача о назначениях

1.1.1 Постановка задачи

1.1.2 Нриближенный алгоритм

1.2 Трехиндексные аксиальные задачи о назначениях с одной одноциклической подстановкой

1.2.1 Постановка задачи

1.2.2 Приближенный алгоритм

1.3 Трехиндексные аксиальные задачи о назначениях с двумя одноциклическими подстановками

1.3.1 Постановка задачи

1.3.2 Приближенный алгоритм
1.4 Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на минимум
1.4.1 Постановка задачи
1.4.2 Приближенный алгоритм
1.4.3 Корректность работы алгоритма

1.4.4 Анализ оценок качества алгоритма
* 1.5 Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум
1.5.1 Постановка задачи
1.5.2 Приближенный алгоритм
1.5.3 Анализ корректности работы и оценок качества алгоритма
1.6 Разрешимость многоиндексной аксиальной задачи о назначе-
ниях на одноциклических подстановках
1.6.1 Постановка задачи
1.6.2 Предварительные замечания и необходимый признак
разрешимости задачи
1.6.3 Критерий разрешимости 7-индексной задачи
1.6.4 Заключительные замечания о разрешимости многоиндексной задачи
2 Приближенные алгоритмы решения трехиндексной планар-'* ной задачи о назначениях
2.1 т-слойная планарная задача о назначениях
2.1.1 Постановка задачи
2.1.2 Приближенный алгоритм для случая т < п/2
2.1.3 Анализ работы алгоритма
2.2 Двухслойная планарная задача о назначениях с одной одноциклической подстановкой
2.2.1 Постановка задачи
2.2.2 Приближенный алгоритм

2.3 Двухслойная планарная задача о назначениях на одноцикли-
•'* ческих подстановках
2.3.1 Постановка задачи
2.3.2 Приближенный алгоритм
2.3.3 Постановка задачи в терминах теории графов
2.3.4 Алгоритм с оценкой точности 9/4 + 0(1/п) для метрической задачи с одинаковой весовой функцией
2.3.5 Обоснование оценок точности алгоритма
„ 2.3.6 Алгоритм с оценкой точности 12/5 + 0(1/п) для метрической задачи с разными весовыми функциями
2.3.7 Обоснование оценок точности алгоритма
2.4 Двухслойная планарная задача о назначениях на одноциклических подстановках на максимум
2.4.1 Постановка задачи
2.4.2 Приближенный алгоритм с константной оценкой точности 3/
2.4.3 Обоснование оценок точности алгоритма
Заключение
Список публикаций автора по теме диссертации
Благодарности
Список литературы

Шаг1, £, 1 < ^ < п—1. Просматриваем элементы строки матрицы И с
номерами столбцов г* , I < б < п. Пусть г!„ - номер столбца минимального из этих просмотренных элементов. Тогда, поменяв в сг^ местами элементы 4+1 и 4о, получим подстановку а^+1 Переходим к следующему шагу.
Этап 3. В результате выполнения первых двух этапа алгоритма получим подстановку (Д"“1). Обозначим о = «Д"-1). Имеет приближенное решение целевой функции

/а ~ ^ ^ ^г,ж(г),а7г(г) • г=
Время работы алгоритма 0(п2).
Перейдем к вероятностному анализу точности алгоритма для решения задачи на случайных входах, определяемых множеством Мп матриц (с,д.) размера п х п х п, где элементы с,д - независимые случайные величины, выбираемые из отрезка [ап,Ьп], где Ьп > ап > 0, с одинаковой функцией распределения.
Данный алгоритм фактически представляет из себя применения алгоритма из [6] к специально сформированной матрице £>. Таким образом, оценки вероятности несрабатывания и относительной погрешности, условия асимптотической точности, полученные для алгоритма из [6], остаются справедливыми.
Приведенный выше алгоритм может использоваться и для максимиза-ционной версии задачи. Заметим, что в этом случае алгоритм будет асимптотически оптимальными без дополнительных условий на Ьп/ап.