Содержание к диссертации
Введение
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
- Трсхиндексньге аксиальные задачи о назначениях с одной од поцикличсской подстановкой
- Трехиндексная аксиальная задача о назначениях наодноциклических подстановках на минимум
- Разрешимость многоиндексной аксиальной задачи о назначениях на одноциклических подстановках
- Двухслойная планарная задача о назначениях па одноцикличсских подстановках
Введение к работе
Необходимость принимать правильные (целесообразные, верные, оптимальные) решения а сложных ситуациях, возникающих при взаимодействиях между различными объектами окружающего мира, была осознана человечеством еще на стадии формирования биологического вида. Развитие экономических и производственных отношений в обществе потребовало решать задачи, связанные с принятием оптимальных решений в сложных системах взаимоотношения между различными объектами хозяйственной деятельности, будь то план строительства жилого дома, оптимальное расписание поездов метрополитена, доставка молочной продукции от молокозаводов к магазинами или составление плана работ по ос нос нию Солнечной системы.
Для решения подобных задач в математике возникла новая наука - исследование операций. В более узком смысле эту область науки называют теорией математических моделей и методов принятия решений. Во многих случаях переменные в таких задачах могут принимать только конечное число состояний. Например, в магазин может быть поставлено только конечное число молочных продуктов в конечном ассортименте, В теории математического программирования такие задачи входят в область дискретной оптимизации. Множество допустимых решений таких задач конечно, и ыы, в принципе, можем найти точное решение, перебрав все допустимые
решения.
Пытаясь решать дискретные задачи оптимизации переборными методами, в большинстве случаев мы замечаем, что с ростом размерности задач (объема исходных данных) число требуемых действий для нахождения оптимального решения растет очень быстро (например, экспоненциально). В то же время практические задачи, как правило, имеют достаточно большую размерность, К сожалению, пи в настоящий момент, ни в обозримом будущем вычислительные мощности компьютеров вряд ли позволят решать такие задачи подобным образом.
Среди дискретных задач оптимизации принято выделять класс задач Р, разрешимых за полиномиальное время (в зависимости от длины входа) и класс NP-трудных задач, для которых построение полиномиальных алгоритмов проблематично (если только NP не равно Р) [8]. К сожалению, многие естественные и интересные задачи дискретной оптимизации являются NP-трудными, Доказано, что если найдется быстрый алгоритм (число действий которого зависит полиномиально от размерности задачи) хотя бы для одной NP-трудпой проблемы, то такие алгоритмы можно будет построить для всех задач из этого класса. Одной из самых фундаментальных проблем современной математики является вопрос: сущеетвуег ли такой быстрый алгоритм для NP-трудных задач? Многие исследователи склоняются к отрицательному ответу па этот вопрос.
Ввиду проблематичности построения быстрых алгоритмов для NP-трудных задач научные исследования направляются на изучение более частных вопросов теории NP-трудных проблем. Можно выделить следующие основные направления исследований:
— выделяются классы подзадач, для которых удастся построить эффек-
тивные точные алгоритмы;
тем или иным способом ограничивают перебор среди всего множества допустимых решений;
строятся эффективные приближенные алгоритмы с гарантированной оценкой точности;
— исследуется вероятностное поведение алгоритмов при условии, что
для некоторых входных данных задано вероятностное распределение.
Одной из самых известных является задача о назначении. Выделяют несколько основных классов задачи о назначениях; классическая линейная задача о назначении, квадратичная задача о назначении, многоиндексная задача о назначении, трехиндексная аксиальная и планарная задачи о назначениях и т.д. Более полно и подробно о задаче о назначениях можно ознакомиться, например, в [41, 42, 43, 49, 101, 106].
Целью настоящей диссертационной работы является построение приближенных алгоритмов для различных модификаций многоипдекеной задачи о назначениях. С этой точки зрения исследована многоиндексная аксиальная задача о назначениях. Также исследованы трехиндексные аксиальные задачи на подстановках специального вида (случаи, когда одна подстановка является одноциклической, обе подстановки являются одноциклическими и случай, когда обе подстановки и их произведение являются одноциклическими). Рассмотрена трехиндексная (n-слойная) планарная задача о назначениях. Исследована m-слойная планарная задача о назначениях, когда 2 < т < п. Также рассмотрена двухслойная планарная задача о назначениях па одноциклических подстановках. Последнюю задачу можно рассматривать как задачу отыскания двух реберно непересекающихся га-мильтоновых циклов экстремального веса.
Приведем несколько примеров. Допустим, некий популярный музыкальный коллектив "АБВГД" планирует гастрольное турне. "АБВГД" отправляется на гастроли из своего родного города, собирается объехать п городов, каждый вечер давая концерт в новом городе, и вернуться обратно. Стоимость переезда из города в город зависит от времени поездки (различные расписания для различных видов транспорта, различия в тарифах для разных видов транспорта и внутри одного вида и т.д.). Менеджер группы "АБВГД11 хочет минимизировать затраты, связанные с передвижением. Одним из путей достижения его цели является решение трехиндексной аксиальной задачи о назначениях с одной одпоциклической подстановкой.
Допустим, что в рамках технологического или управленческого процесса некого крупного сырье-добывающего предприятия "OIL2" п пунктов добычи посещаются двумя видами транспорта при условии, что оба транспортных средства посещают каждый пункт один раз, оба маршрута начинаются и заканчиваются н одной точке (на аэродроме, в гараже, в ангаре). Каждый пункт несет затраты, связанные с посещением (например, обеспечение транспортных средств горючо-смазочными материалами). Цель менеджера компании TT0/L2|,: отвечающего за транспорт, минимизировать суммарные затраты. Если затраты каждого предприятия пе являются аддитивной функцией от вида транспорта (что само по себе не редкость для практических задач), то решение трехиндексной аксиальной задачи о па-значениях с двумя одноциклическими подстановками является одним из вариантов достижения поставленной цели.
Допустим, что некая держава проводит масштабные морские учения. Инспекция из состава командывания должна облететь п авианосцев и вер-нуться в штаб. Стоимость перемещения от авианосца к авианосцу зависит
от расстояния между кораблями и от устройства, которое используют по время посадки. Адъютанту поручено минимизировать стоимость инспекции. Один из возможных путей выполнения задания -решить двухслойную планарную задачу о назначениях с одной одноциклической подстановкой.
Допустим, что в рамках автоматизации производства на иском производственном объединении "КЛМН" решили совместить работу двух устройств. Каждое устройство выполняет на п деталях, расположенных на одной микросхеме, по одной операции, после чего возвращается в начальную точку. Во избежание технических накладок необходимо исключить перемещение от детали г к детали j и обратно для одного устройства, если такое перемещение осуществляет другое. Перед инженерами "КЛМН" стоит задача минимизации суммарного времени перемещения устройств. Скорости перемещения могут быть разными. Один из путей достижения этой цели - решение двухслойной планарной задачи о назначениях на од-ноциклических подстановках.
Требования одноциклнчности одной или нескольких подстановок может найти достаточно большое практическое применение. А как только возникает требование одиоцикличности какой-либо подстановки, то сразу появляется снизь с задачей коммивояжера, Трехипдексные аксиальные задачи па подстановках специального вида и двухслойную планарную задачу о назначениях с одноциклическими подстановками можно рассматривать как синтез задачи коммивояжера и миогоиндекспой задачи о назначениях. Поскольку и классическая задача коммивояжера и мпогоиндексная задача о назначениях очень актуальны для практических приложений, то также можно надеяться, что обобщение этих задач может найти широкое применение на практике,
Задача коммивояжера является одной из самых известной задачи в ис-
* следовании операций. Выделяют несколько основных классов задачи о ком-
мивояжере: симметричная задача о коммивояжере, асимметричная задача о коммивояжере, метрическая задача о коммивояжере, задача о коммивояжере на максимум и т. д. Имеется большое число работ, посвященных данной проблеме, например [88, 104, ПО, 111, 131].
Приведем далее математические постановки многоипдексной задачи о
назначениях и задачи коммивояжера, которые являются основой для ис-
w следуемых нами модификаций трехиндексных задач о назначениях и двух-
слойной планарной задачи о назначениях на одноциклических подстановках (она же задача отыскания двух реберно непересекающихся гамильтоно-вых контуров экстремального веса) и дадим краткий обзор по полученным результатам.
Многоипдексиая задача о назначениях (МЗН) является естественным обобщением классической линейной задачи о назначении» Первой работой, посвященной многойндекспой версии задачи о назначениях, можно считать работу Pierskalla [126], вышедшую в 1968 году. Наиболее известны две разновидности МЗН: аксиальная и планарная трехиндекснаи задача о назначении.
Трехиндексная аксиальная задача о назначениях (3-АЗН) может быть сформулирована следующим образом.
п п п
53 JZ S с№*ізк -* min
i=l j=i Ь=1 при условии, ЧТО
,р п п
її п
г-1 А-1
7І Ті
f=i i=i
^jfc — 1 Для 1 < г, js к <пг
где суд ~ заданные вещественные числа, 1 < zTij,&# < п.
Другими словами 3-АЗН состоит в таком выборе п элементов в кубической матрице {Cfjk) порядка п, что в каждом ее сечении выбран ровно один элемент и сумма выбранных элементов минимальна. (Под сечением матрицы понимается множество п2 ее элементов с фиксированным значением одного из индексов 1 < г, j, к < тг).
3-АЗН можно записать в алгебраической форме:
Х^м^со ~~> min
г=1
по всем подстановкам тг,а степени п.
Кагр первым показал, что 3-АЗН NP-трудна [99].
Трехиндексная планарная задача о назначении (3-ПЗН) формулируется следующим образом:
Ті її п
2 = 1 J=I k=l
при условии, что
Y^X^k = 1, J = 1,...,11, fc= 1,...,71, г=1
^хцк = 1, і = 1,...,n, k= 1,..,,n,
=1
Xijk Є {0,1}, ij,k = 1,...,77.
Трсхиндекетіая планарная задача о назначений NP-трудиа [73],
В обіцем случае m-индекспая аксиальная задача о назначениях (МАЗН)
формулируется следующим образом:
п п
при условии, что
п п
ТІ п п п
И X) X ^...^ = 1.
4 = 1 й-і = ї *fc+i-l z'*-i = l
для А = 2,..., m ~ 1, и ій = 1, 2,..., п,
зі тг
Іх=1 7^-1=1
Яїі-ь» Є (0,1} для 1 < г1} г"2ї..., іт < п.
Здесі> через с^а.„*т обозначены элементы прямоугольной пх ' - х п матрицы -заданные вещественные числа, 1 < г^ < п, к = 1,.., ?т. Будем называть матрицу (сгпг-*) матрицей коэффициентов стоимости.
Для МАЗН удобно использовать более компактную форму се записи с
помощью подстановок из симметрической группы Sn порядка п:
ГДЄ7Гі(І),,..а7Гт_і(І) ЄБп.
В общем случае МАЗН является КР^грудноЙ [73]. В случае, когда матрица коэффициентов стоимости является матрицей Monge [44], решением задачи является набор тождественных подстановок x^(j') = j, для
і = l,.,.,m — 1, j — 1,..,,n. Burkard, Rudolf и Woegingcr [4G] показали, что МАЗН остается NP-трудной для т > 3 в случае когда матрица коэффициентов стоимости является обратной матрице Monge.
Классическая задача коммивояжера (ЗК) (в англоязычной литературе The Traveling Salesman Problem (TSP)) состоит в нахождении обхода п городов, имеющего минимальную общую длину Считаются заданными расстояния между всеми парами городов. Обходом считается замкнутый маршрут, проходящий через каждый город ровно один раз. И хотя современный коммивояжеры не руководствуются в выборе маршрута столь жесткими ограничениями, ЗК является типичной "трудной" задачей комбинаторной оптимизации.
ЗК известна под разными именами, В начале тридцатых годов прошлого века Karl Meager исследовал разновидность ЗК, называемую задачей курьера (messenger problem или Botenproblcm) [39, 112]. Работа Monger [112] является первой публикацией па тему ЗК. В 1955 Morton и Land [11G] заметили, что ЗК может быть знакома статистикам как задача средних минимальных расстояний (the mean minimum distances problem). Они ссылаются на работы [77, 109], Сам термин "задача коммивояжера4 родился, по-видимому, в США. Первая работа, в которой используется именно этот термин, вышла в свет в 1949 году [133]. Тем не менее, точкой отсчета начала систематическое исследования ЗК как задачи комбинаторной оптимизации следует считать работу Dantzig, Fulkcrson и Johnson [59], За дальнейшей эволюцией ЗК можно проследить в обзорах [110, 111] а также н книгах [104] и [131]. Одна из последних книг, посвященная современному состоянию исследований по ЗК, вышла в 2002 году под редакцией Gutin G. и Punnen А, Р. [88].
Перечислим известные результаты для этих задач по упомянутым выше четырем направлениям исследований.
Как уже отмечалось выше, МАЗН полиномиально разрешима, когда матрица коэффициентов стоимости является матрицей Mongc [44]. Однако, максимизациониая версия МАЗН в случае, когда матрица коэффициентов стоимости является матрицей Monge, остается NP-трудной.
Burkard, Rudolf и Woegingcr [4б| исследовали случай 3-АЗН с мультипликативными коэффициентами, когда еу^ = UiVjW^ где щ, Vj^ w^ > 0. Они показали, что максимизациониая версия такой 3-АЗН полиномиально разрешима, а мипимизационная версия остается NP-трудной. В той же работе приводится еще несколько полиномиально разрешимых классов 3-АЗН.
Можно привести целый ряд работ, в которых ЗК также рассматривалась с точки зрения выявления полиномиально разрешимых подклассов. Первый нетривиальный полиномиально разрешимый случай метрической ЗК исследовал Flood [70]. Ои исследовал случаи, когда оптимальный тур определяется простым (т.е. не имеющим самопересечений) многоугольником на плоскости. Один из наиболее известных полиномиально разрешимых случаев, имеющих большое практическое применение, представлен Gilmore-Gomory ЗК [78]. Разновидности ЗК, полиномиально разрешимые с помощью Gilmore-Gomory схемы [78], можно найти в [11, 31,37,40, 51,79,98, 124].
Работы по выявлению полиномиальной разрешимости классов ЗК можно найти [32, 51, 60, 61].
Перейдем к переборным способам нахождения точного решения много-индексной аксиальной задачи о назначениях, В 1994 году был предложен алгоритм для МАЗН, использующий Лагранжевую релаксацию [127, 128].
Pierskalla [125] был первым, кто предложил эвристику для 3-АЗН. Применение метода ветвей и границ дав по уже стало классикой. Как правило, исходная задача разделяется на две подзадачи фиксированием значения переменной Xijk {xijk полагается либо 0, либо 1). Balas и Saltzman [36| предложили стратегию ветвления, которая позволяет фиксировать несколько переменных на каждом этапе. Burkard и Rudolf [45] исследовали различные схемы ветвления, Hansen и Kaufman [89] предложили прямодвойствсн-ный метод решения 3-АЗН, В [43] в качестве нижних границ для метода ветвей и границ используют Лагранжеву релаксацию. Другая субгради-ептпая процедура для решения Лагранжевой релаксации 3-АЗН описана Frieze и Yadcgar [74]. Burkard и Rudolf [45] получили хорошие результаты вычислительных экспериментов для алгоритма, использующего классические правила ветвления в сочетании со специальным шагом упрощения в каждой вершине. Модификация метода ветвей и границ, предложенная Balas и Saltzman [36], использует другую Лагранжеву релаксацию для вычисления нижних границ. Для решения граничных неравенств, составляющих данную релаксацию, используется субградиентная процедура.
Для 3-ПЗН первым метод ветвей и границ предложил Vlach в 1967 году [140]. Другую модификацию этого классического метода предложили Magos и Miliotis |108]. В 1996 году Magos предложил алгоритм поиска с запретами [107].
Далее мы коснемся переборных способов нахождения точного решения задачи комминояжера. Существует огромное количество работ, посвященных данному подходу. Прежде всего выделим метод динамического программирования, предложенный Held и Кагр в 1962 году [91], и, независимо от них, Коробковым В. К, и Кричспским R Е. в 1966 году [10] (с времен-
ной сложностью п2п). Также отметим алгоритм Лагранжевой релаксации, базирующийся на 1-дерене, предложенный Held и Кагр в 1970 году [92, 93], По сей день оба подхода имеют серьезные ограничения на размерность задач, к которой они применяются. Наилучшие результаты с применением Лагранженого подхода были получены Belloni и Luccna в 2000 году [38].
Считается, что хорошие результаты в этом направлении дает применение метода ветвей и сечений (The Branch-and-Cut method) [59] к двухин-дексной (double index) формулировке ЗК [122].
Вообще гоноря, существуют различные формулировки ЗК как задачи целочисленного линейного программирования. По соображениям, связанным с вычислениями, из двух различных целочисленных моделей наиболее предпочтительной оказывается та, чья линейная релаксация имеет наибольшее значение целевой функции. Также имеет смысл использовать модель, минимальную с точки зрения количества используемых неравенств, так как разработано множество способов расширения модели целочисленного линейного программирования дополнительными неравенствами.
Модели целочисленного линейного программирования для ЗК можно найти в [25, 26, 27, 00, 122]
Коснемся способов расширения модели целочисленного линейного программирования дополнительными неравенствами. Широко рассматриваются: монотонная релаксация (the monotone relaxation) [33, 54, 85, 8G], релаксация гамшіьтонова пути (Hamiltonian path relaxation) [129[, графическая релаксация (the graphical relaxation) [56] и множество других [54, 56, 58, 71, 83, 85, 87, 117, 118, 119, 120].
Для описанных выше моделей используются различные модификации метода ветвей и границ, в качестве нижней оценки берутся всевозможные
линейные релаксации (см., например, [55, 141]). Описание модификаций метода ветвей и границ можно найти в [52, 97, 121].
Кстати, впервые метод ветвей и границ был предложен Land и Doig [102] для задачи многомерного рюкзака. Определение этого метода можно найти в книге Вереснева, Гимади, Дементьева [1]. Вообще говоря, метод ветвей и границ не гарантирует избежания полного перебора. Но практическая реализация этого метода в ряде случаев дает хорошие апостериорные оценки времени работы метода. Подробный обзор применения этого метода к ЗК можно найти в работе Balas и Toth [34].
Для асимметричной ЗК (когда расстояние между двумя городами зависит от направления движения) її качестве оценок снизу для метода ветвей и границ для ЗК можно брать решение задачи о назначении или ее специальной модификации [34, 47, 64, 65, 113, 114, 138]. В 1989 году/ более сложную процедуру поиска оценок снизу предложил Toth [66, 67]. Он развил идею работы Carpaneto и Toth [48]. Метод ветвей и сечений также был рассмотрен для асимметричной ЗК в 2000 году Ascheuer [28], Afichcuer, Juenger и Reinelt [30] и в 1995 году Ascheuer, Fischetti и Groetschel [29].
Сущестпует огромное количество эвристик для ЗК. Условно нее эвристики для ЗК можно разделить на два класса: эвристики, конструирующие тур (такие эвристики строят тур, добавляя по вершине на каждом этапе), и эвристики, улучшающие тур (такие эвристики начинают свою работу с уже имеющего тура, улучшая его шаг за шагом). Также существует огромное количество алгоритмов, комбинирующих эти два класса. Более подробного данное направление освещено в [80, 81, 82, 92, 93, 94, 105, 130],
Как было сказано выше, построение точных эффективных алгоритмов для NP-трудных задач является проблематичным (дискуссия по этому во-
просу содержится в работе Гэри и Джонсона [8]).
Поэтому, помимо построения быстрых алгоритмов для отдельных классов задач, другим важным направление исследований является построение приближенных эффективных алгоритмов с априорными (гарантиронанны-ми) оценками точности. Это означает, что удается найти решение задачи, которое удовлетворяет некоторым требованиям по точности, установленными еще до получения приближенного решения. Этот подход будет использоваться для получения некоторых результатов во второй главе диссертации.
Общепринято считать, что известная работа Graham [84] но теории расписаний послужила началом для подобных исследований. В работе Johnson [96] вводятся понятия приближенного алгоритма и его точности н худшем случае.
В конце семидесятых годов вышло много интересных работ по приближенным алгоритмам и, как следствие этого, появилось несколько обзорон [68, 132, 134], в которых суммируются результаты, полученные за эти годы. Хорошим введением в эту область исследований являются диссертация Агога [22] и обзор Arora, Lund [23], работа Papadimitrou, Yannakakis [123], а также обзор [136].
Напомним определения основных понятий теории приближенных решений [9Q]. Пусть имеется приближенный алгоритм А для решения оптимизационной задачи. Пусть / - индивидуальная оптимизационная задача, Za[I) - значение приближенного решения, полученного алгоритмом А, Z*(I) - точное значение задачи. Есть несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма,
является так называемая относительная точность, под которой попимает-
* ся функция Ta[I) = Za(I)/Z*{I). Априорной оценкой относительной точ
ности приближенного алгоритма А решения оптимизационной задачи па
максимум (минимум) является величина Яд такая, что для любой индиви
дуальной задачи / выполняется неравенство
rA(I)>RA (rA(I)
Такую оценку Яд, не зависящую от размерности индивидуальной задачи /, называют константной.
В 1976 году Sahni и Gargles [135] показали, что нахождение даже 2-приближениого решения ЗК является NP^rpyjjHon задачей. Под полиномиальной приближенной схемой (PTAS) будем понимать последовательность полиномиальных приближенных алгоритмов, которые для любого фиксированного г > О находит (1 + г)-приближешгос решение. Последние исследования показали, что если Р/ NP, то для ЗК (в общем случае) невозможно построить PTAS.
Для метрической ЗК (когда расстояния между городами удовлетворяют неравенству треугольника) известен полиномиальный алгоритм с оценкой точности 3/2 (публикации: Christofides в техническом отчете [53], Сердюков в работе (16]). Отметим, что хотя в англоязычной литературе данный алгоритм известен, как алгоритм Кристофидеса, А, И. Сердюков открыл его совершенно независимо и практически одновременно, В настоящее время ряд исследователей используют название алгоритм Christofides and Serclyukov (см., например, Дейнеко). На протяжении многих лет он оставался лучшим
* результатом для данной задачи. В 1998 году Агога [24] предложил PTAS
для метрической ЗК. Вначале алгоритм имел п0^1^ временную сложность,
которая затем была улучшена до n{logn)^e\ (Несколькими месяцами позже Mitchell независимо предложил подобную схему, выполняемую за п\чч [115])» Схему можно применять и для ЗК в Rm для любой константы т. Если тне является константой, но зависит от п какт = O(logrc), то число вершин, при котором алгоритм работает за время, превышающее полиномиальное, растет экспоненциально от т. Подобная зависимость от размерности прекрасно согласуется с широко известным результатом Trevisan [139]: метрическая ЗК MAX-SNP-грудна в Ц^п).
Для ЗК на максимум с неотрицательными расстояниями между городами получены следующие результаты: в 1979 году получен алгоритм с оценкой точности 1/2 [69], в 1986 году получен алгоритм с оценкой точности 4/7 [13], в 1994 году алгоритм с оцеїгкой точности 38/63 [100].
Для симметричной ЗК на максимум получены следующие результаты: в 1979 году получен алгоритм с оценкой точности 2/3 [69], в 1984 году получен алгоритм с оценкой точности 13/18 [12], в 1998 году получен алгоритм с оценкой точности 5/7 в [90], и лучший на сегодняшний день, полученный в 1984 году, алгоритм с оценкой точности 3/4 Сердюкова с временной сложностью 0(п3) [17]»
Отметим, что Сердюковым получены интересные результаты и по целому ряду других классов ЗК [14, 18, 19, 21].
В 1992 году Crania и Spicksma [57] рассмотрели специальный класс 3^ АЗН, сформулированной в терминах теории графов. Длины ребер должны удовлетворять неравенству треугольника, а сумма ребер треугольника определяется либо как сумма длин его сторон (обозначим такую задачу как ТА) либо как сумма двух наиболее коротких сторон (обозначим такую задачу как 5А). В [57] показано, что обе задачи являются NP-трудными и
приводятся алгоритм с оценкой точности 3/2 для ТА и алгоритм с оценкой
-* точности 4/3 для SA.
Имеется еще одно важное направление в исследовании NP-трудных задач — это вероятностный анализ поведения алгоритмов. Здесь предполагается, что на множестве индивидуальных задач задано некоторое вероятностное распределение и оценивается математическое ожидание погрешности алгоритма па этом распределении. Вероятностное поведение некоторых данных r той или иной модели очень естественно для многих практических задач. TaKj спрос на молочные изделия может иметь вероятностный характер.
Здесь мы изложим идею построения алгоритма с оценками {єп,6п), впервые предложенную Гимади, Глебовым, Перепелицей в работе [3]- Данный подход являлся в своем роде революционным для исследования NP-трудных проблем. А впервые этот метод был реализован Гимади, Перепелица [5]. Работа [137] дает хорошую библиографию по данной тематике. Данный подход также будет использован при получении результатов диссертации.
Пусть К - некоторый класс задач. Через Z(S) обозначим оптимальное значение целевой функции для задачи S Є К. Будем считать, что рассматриваются задачи на минимум и Z(S) > 0 для всех S Є К.
Рассмотрим теперь некоторый алгоритм А, который может быть применен к любой задаче S класса К, так что результатом этого применения является допустимое решение задачи S со значением целевой функции Za{S). При этом, вообще говоря, не исключается, что применение алгоритма А к некоторым задачам из класса К может оказаться безрезультатным.
Если получено допустимое решение задачи S, то качество решения дан-
ной задачи может быть оценено через величину
ZA(S) - Z(S) Z{S) *
которая является относительным уклонением от оптимума целевой функции, полученным в результате применения алгоритма А.
Задаваясь некоторым є > О, можно определить множество задач
*H^№^}.
ZA(S) - Z(S) Z(S)
для которых относительная погрешность получаемых алгоритмом А решений не превышает заданной величины е. Набор множеств Кд для разных є > 0 мог бы служить достаточно полной характеристикой алгоритма А с точки зрения точности получаемых решений- Это, в свою очередь, позволяло бы сравнивать разные алгоритмы по указанным наборам множеств. Но трудность такого подхода к сравнению алгоритмов заключается в том, что практически мы, как правило, не имеем возможности получить простое описание множеств КА в явном виде.
В подобной ситуации можно пытаться использовать различные возможности косвенного описания, находить какие-то нетривиальные характеристики этих множеств. В качестве таких характеристик можно, например, рассматривать меры множеств К% относительно различных вероятностных распределений на классе /", что и осуществлено одним из возможных способов в [3].
Пусть заданы класс задач К и некоторое семейство Р вероятностных мер, определенных на классе К. Говорят, что алгоритм А имеет тип (,5) относительно Pf если
,{MS.}1_,
для всех р Є Р.
*> В этом случае также говорят, что алгоритм А имеет оценки (є, 5) от-
носительно Р .
Алгоритм А называется асимптотически точным на классе задач it, если существуют такие последовательности {єп)9 (5п), что для любого п алгоритм А удовлетворяет оценкам (єп,5п) на подмножестве Кп С К задач размерности п и при этом еп —> 0, 5п —+ 0 при п —* сю.
Заметим, что алгоритм будет точным в том и только в том случае, если он имеет оценки (0,0) относительно любого семейства вероятностных мер.
Нетрудно представить ситуацию, в которой величины є и 5 действительно могут трактоваться как оценки вероятностного характера для относительных погрешностей получаемых с помощью алгоритма А решении. В самом деле, пусть алгоритм А имеет тип (, 6) относительно Р и он используется для решения задач класса К, которые поступают из некоторого случайного источника, имеющего распределение р Є Р. Тогда можно быть уверенным, что вероятность не получить алгоритмом А решение с приемлемой относительной погрешностью - не более 6, При этом само распредсле-ниє Р мы можем и не знать, лишь бы было известно, что оно принадлежит семейству Р.
Использование техники оценок {епу8п) позволило установить условия асимптотической точности малотрудоемких приближенных алгоритмов для решения ряда труд порешаем ых задач дискретной оптимизации.
Для 3-АЗН этот подход был реализован Гимади и Сердюковым в работе
17]-
^ Для классической ЗК этот подход был реализован в статьях [5, б]. Для
ЗК на максимум данный подход был реализован работе [2, 4, 20].
Далее представим кратко результаты диссертационной работы, состоящей из введения, двух глав, заключения, списка публикаций автора по теме диссертации и списка используемой литературы.
В первой главе рассматриваются различные модификации многоиндексной аксиальной задачи о назначениях. Основываясь на идее построения быстрых приближенных алгоритмов с оценками качества [3], для классической многоиндекеїгой аксиальной задачи о назначениях предлагается приближенный алгоритм, имеющий временную сложность 0{пъ). Для решения задач на случайных входах приводятся условия его асимптотической точности. Рассмотрена трехиндексная аксиальная задача о назначениях на подстановках специального вида. Исследуются случаи, когда одна подстановка является одноциклической, обе подстановки являются одно-циклическими и случай, когда обе подстановки и их произведение являются одпоциклическими. Для первых двух задач предлагаются приближенные алгоритмы, являющиеся модификациями рапсе известных алгоритмов [б, 7]. Для решения задач на случайных входах указываются условия их асимптотической точности. Для третьей задачи показывается, что необходимым и достаточным условием разрешимости является нечетность п. Для минимизационной и максимизационпой версий задачи предлагаются полиномиальные приближенные алгоритмы. Алгоритм для задачи на минимум имеет временную сложность 0{п2) и использует лишь незначительную часть исходной информации, а именно п2 элементов из общего числа п3 элементов исходной матрицы входных данных (%*;) Формируя из исходной матрицы входных данных (^) множество подматриц {Dm} размера п х п, но имеющих общих элементов, можно получить несколько независимых решений, из которых выбирается наилучшее. Такая модификация
имеет несколько большую трудоемкость, а именно 0(n2Iog2 п), по существенно лучшие оценки вероятности несрабатывания и относительной погрешности. Данный подход реализуется для максимизационной версии задачи. Проводится обоснование условий на входные данные, гарантирующих асимптотическую точность алгоритмов. Рассматривается много индексная аксиальная задача о назначении па одпоциклических подстановках. Начиная с числа индексов, равного трем, существуют входы, на который задача не имеет решения. Приводится необходимое условие разрешимости задачи. Показывается достаточность этого условия для числа индексов, меньшего восьми.
Во второй главе рассматривается трехиндексная (тг-слойная) планар-ная задача о назначениях. Для m-слойной планарной задачи о назначениях, 2 < т < п, описывается полиномиальный приближенный алгоритм. Получены условия асимптотической точности алгоритма для задач на случайных входах. Исследуются двухслойная планарная задача о назначениях с одной одноциклической подстановкой и двухслойная планарная задача о назначениях на одпоциклических подстановках (случай, когда обе подстановки являются одпоциклическими). Отмечается, что последняя задача представляет из себя задачу отыскания в графе дкух реберно непересекающихся гамильтоповых контуров экстремального суммарного веса. Для двухслойной планарной задачи о назначениях с одной подстановкой и двухслойной планарной задачи о назначениях на одпоциклических подстановках предлагаются приближенные алгоритмы, использующие идеи рапсе известных алгоритмов [6, 7]. Отмечается, что для решения задач па случайных входах алгоритмы имеют условия асимптотической точности аналогичного [6, 7] вида. Исследуются метрический случай задачи отыскания
в графе двух реберно непересекающихся гамильтоповых циклов минимального суммарного веса. Для задачи с одинаковой весовой функцией предлагается приближенный алгоритм с оценкой точности 9/4+0(1/п), имеющий временную сложность 0(nz). Для задачи с разными весовыми функциями строится приближенный алгоритм с оценкой точности 12/5 + 0(1/п), имеющий временную сложность 0(п3). Для задачи отыскания в графе двух реберно непересекающихся гамильтоповых циклов максимального суммарного веса с одинаковыми весовыми функциями предлагается приближенный алгоритм с константной оценкой точности 3/4, имеющий временную сложность 0(тг3).
Основные результаты диссертации докладывались на Международной научной студенческой конференции (Новосибирск, 2000), Международной конференции |ТДискретный анализ и исследование операций4 (Новосибирск, 2000), на 12-ой Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001), на Европейской конференции по комбинаторике, теории графов и их приложениях СОМВ2001 (Барселона, 2001), на международной конференции "Новые технологии и автоматизация производства" 8th IEEE (Франция, 2001), на Всероссийской конференции "Проблемы оптимизации и экономические приложения11 (Омск, 2003), на Международной конференции по исследованию операций OR2003 (Гейдельберг, 2003), на научных семинарах Института математики СО РАН.
*>
Трсхиндексньге аксиальные задачи о назначениях с одной од поцикличсской подстановкой
Для задачи (1.1)-(1.2) н работе [7] представлен приближенный алгоритм с временной сложностью 0{пфп)і где фп - любая целочисленная функция, такая что 1 фп п. Алгоритм из [7] действует следующим образом. Подстановка 7Г берется произвольным образом. Из элементов исходной матрицы формируется подматрица размера п х п. Подстановка а строится по принципу выбора минимального элемента в строке. В работе [7] приведены условия асимптотической точности алгоритма решения задачи на случайных входных данных. Например, когда фп = тг, элементы ( распределены п интерпале [ani bn] с функцией распределения вида F (x) х, 0 і 1, где — (су — ап)/(Ьп ал)і предлагаемый алгоритм асимптотически точен при bnjan = o(n/lnn) при времени работы 0(п2). В качестве одной из разновидности трехиндексной аксиальной задачи о назначениях естественно рассматривать задачу, в которой накладываются дополнительные требования на вид подстановок. В контексте синтеза трехиндексной аксиальной задачи о назначениях и задачи коммивояжера можно рассмотреть требования одноцикличиости одной или нескольких подстановок. Трех индексная аксиальная задача о назначениях с одной одноцикличе-ской подстановкой формулируется следующим образом: при условии, что где Рп - множестно всех одноциклических подстановок степени п. Для решения задачи (1.3)-(1.4) предлагается следующий приближенный алгоритм. Обозначим через фп любую целочисленную функцию, 1 фп п. Алгоритм: Этап 1. Берем произвольную подстановку тг Є Рп. Пусть [djk) - пх п матрица, содержащая элементы исходной матрицы {o/t), где индексу = Этятг 6, Повторяем этап 2, пока j к. В противном случае идем на этап 1. Этап 7- Результатом работы алгоритма является значение / целевой функции. Лемма 1. Алгорипш находит допустимое приближенное решение задачи (1.3) Доказательство леммы 1 следует из описания алгоритма.
Перейдем к вероятностному анализу точности алгоритма дли решения задачи на случайных входах, определяемых множеством Мп матриц () размера п х пх п, где элементы Сц& - независимые случайные величины, выбираемые из отрезка [aw, 6J, где Ъп ап 0, с одинаковой функцией распределения. Данный алгоритм отличается от алгоритма из [7] заменой условия 7г Є Sn на тг Є Рп на этапе 1. Таким образом, оценки вероятности несрабатывания и относительной погрешности, условия асимптотической точности, полученные для алгоритма из [7], остаются справедливыми. Приведенный выше алгоритм может использоваться и для максимиза-ционной версии задачи. Заметим, что в этом случае алгоритм будет асимптотически оптимальными без дополнительных условий па Ьп/ап. Трех индексная аксиальная задача о назначениях с двумя оді юцнкл и чески-ми подстановками формулируется следующим образом: при условии, что Для решении задачи (1.5)-(1.6) предлагается следующий приближенный алгоритм. Алгоритм: Этап 1. Берем произвольную подстановку ж Є Sn. Пусть D = (djk) -nxn матрица, содержащая элементы исходной матрицы (су ), где индекс j — тг(і) такой, что Шагі, і, 1 t n—1. Просматриваем элементы строки ц матрицы Dc номерами столбцов U , і s п. Пусть гіа - помер столбца минимального из этих просмотренных элементов. Тогда, поменяв в г местами элементы 4+1 и 4о, получим подстановку a t+l\ Переходим к сле іуюіцему шагу. Этап 3. В результате выполнения первых двух этапа алгоритма получим подстановку а -1 . Обозначим а сг п_1 . Имеет приближенное решение целевой функции Время работы алгоритма 0(п2). Перейдем к вероятностному анализу точности алгоритма для решения задачи на случайных входах, определяемых множеством Мп матриц (суд-) размера п х п х п, где элементы с,д - независимые случайные величины, выбираемые из отрезка [оглМ, гДе &л ап 0, с одинаковой функцией распределения. Данный алгоритм фактически представляет из себя применения алгоритма из [б] к специально сформированной матрице D. Таким образом, оценки вероятности несрабатывания и относительной погрешности, условия асимптотической точности, полученные для алгоритма из [G], остаются справедливыми. Приведенный выше алгоритм может использоваться и для максимгоа-ционной версии задачи. Заметим, что в этом случае алгоритм будет асимптотически оптимальными без дополнительных условий на Ьп/ап В качестве естественного математического развития трехиндексной аксиальной задачи о назначениях па двух одноциклических подстановках может быть рассмотрена трехиндексиая аксиальная задача о назначениях на одноциклических подстановках, которая может быть сформулирована следующим образом:
Трехиндексная аксиальная задача о назначениях наодноциклических подстановках на минимум
Для решении задачи (1.5)-(1.6) предлагается следующий приближенный алгоритм. Алгоритм: Этап 1. Берем произвольную подстановку ж Є Sn. Пусть D = (djk) -nxn матрица, содержащая элементы исходной матрицы (су ), где индекс j — тг(і) такой, что Шагі, і, 1 t n—1. Просматриваем элементы строки ц матрицы Dc номерами столбцов U , і s п. Пусть гіа - помер столбца минимального из этих просмотренных элементов. Тогда, поменяв в г местами элементы 4+1 и 4о, получим подстановку a t+l\ Переходим к сле іуюіцему шагу. Этап 3. В результате выполнения первых двух этапа алгоритма получим подстановку а -1 . Обозначим а сг п_1 . Имеет приближенное решение целевой функции Время работы алгоритма 0(п2). Перейдем к вероятностному анализу точности алгоритма для решения задачи на случайных входах, определяемых множеством Мп матриц (суд-) размера п х п х п, где элементы с,д - независимые случайные величины, выбираемые из отрезка [оглМ, гДе &л ап 0, с одинаковой функцией распределения. Данный алгоритм фактически представляет из себя применения алгоритма из [б] к специально сформированной матрице D. Таким образом, оценки вероятности несрабатывания и относительной погрешности, условия асимптотической точности, полученные для алгоритма из [G], остаются справедливыми. Приведенный выше алгоритм может использоваться и для максимгоа-ционной версии задачи. Заметим, что в этом случае алгоритм будет асимптотически оптимальными без дополнительных условий на Ьп/ап В качестве естественного математического развития трехиндексной аксиальной задачи о назначениях па двух одноциклических подстановках может быть рассмотрена трехиндексиая аксиальная задача о назначениях на одноциклических подстановках, которая может быть сформулирована следующим образом: п В отличие от рассмотренных выше разновидностей трехиндексной аксиальной задачи о назначениях для задачи (1.7)-(1.8) существуют входы, па которых задача может не иметь решение. Задачу будем называть разрешимой если для нес существует такие подстановки тг3 а для которых выполняются условия (1.S). В противном случае задачу называем неразрешимой. В [7] для задачи (1.7)-(1.8) доказана следующая теорема. Теорема 2.
Трехиидекпая аксиальная задача о назначениях па одноциклических подстановках разрешима тогда и только тогда, когда п немеш-но, В [7 для решения задачи (1.7)-(1.8) представлен приближенный алгоритм с временной сложностью 0(ns). Алгоритм основан на таком согласо ванном преобразовании подстановок тг и а, которое почти всегда (с вероятностью, стремящийся к 1 при п — оо ) приводит их (а также подстановку o 7i ) к одноциклическому виду. При этом для отыскания исходной подстановки а используется точный алгоритм решения задачи о назначении на специально сформированной квадратной матрице порядка п. Там же приведены условия асимптотической точности алгоритма решения задачи на случайных входных данных. Ниже мы опишем алгоритм, который, в отличие от [7], всегда строит допустимое решение задачи и имеет существенно меньшую временную сложность, Перейдем к описанию алгоритма для нахождения приближенного решения задачи (1.7)-(1.8). Так же, как и и [7], в начале работы алгоритма формируется специальная квадратная матрица D = {djk) порядка п, состоящая из части элементов исходной матрицы (су ), где і = TT_1(J): Здесь в качестве подстановки тг Рп берется подстановка тг = (1, 2,. -. ,7ї), которая далее, в отличие от [7], остается без изменения. Кроме того, для отыскания одноциклической подстановки а используется неточный, а менее трудоемкий приближенный метод, основанный на выборе минимального элемента в текущей строке с учетом дополнительного требования одно-цикличности подстановки атг. Элементам подстановки атг будем сопоставлять вершины ориентированного графа G, а переходам от элемента к элементу - дуги графа G. На на чалыгом шаге работы алгоритма множество дуг графа G пусто- Далее граф представляется в виде (растущего от шага к шагу) частичного тура, т. е. такого подмножества дуг, которое может быть дополнены до гамильтоноиа обхода. Пусть в ходе работы алгоритма в графе G возникает некоторый максимальный (по включению) путь (s, ...,&), Тогда н его начальной вершине s будем хранить информацию о его концевой вершине к (в виде пометки p{s) = fc), а в концевой вершине к - информацию о начальной вершино s (в виде пометки q(k) = s). Далее будем полагать разность і — 1 равной п при і = 1, и сумму і + 1 равной 1 при г — п Этап 1. Выбирается одноциклическая подстановка 7Г = (1, 2, -. . ,тг) и формируется квадратная матрица D, как указано выше. Этап 2, В матрице D исключаются из дальнейшего рассмотрения (запрещаются) диагональные (1ц и "поддиагоиальные" d -i элементы, г = 1,...,п, для того, чтобы не появлялись непереставляемые элементы в подстановках и и атг. Этап 3. Он состоит из п — 4 шагов. На шаге t, 1 t п — 4, имеется Шаг 1: Шаг 1 начинается с подстановки а — тг. Первая строка выбирается в качестве текущей и в ней просматриваются нозапрещенные элементы матрицы D. Пусть к - номер столбца, в котором находится минимальный из просмотренных элементов. Тогда элементы 2 и к меняются местами и получается подстановка а \ В результате таких действий в подстановке а элемент 1 перейдет в к, а її подстановке а тг элемент п перейдет в к. При этом в графе G появится дуга {гг, Л:)- Помечаем ее концы: р(п) = к, д{к) = п. Чтобы избежать зацикливания к подстановке Х7Г, в матрице D запрещается элемент dk+itn Шаг , 2 п — 4.
Перед шагом имеется подстановка а = (4 ,4 » 1 ) На"шаге в качестве текущей берется строка j = ц и просматриваются элементы djk, расположенные в столбцах с номерами ij+u - , in - Эти столбцы и соответствующие им элементы текущей строки называются свободными. Пусть к - номер столбца, в котором находится минимальный из просмотренных и незапрещенных элементов. Поменяв в о- местами элементы щг и /г, получим подстановку а +1 , В графе G появилась новая дуга (s,k), где s = j — 1. Если концевые вершины s и к этой дуги не помечены, то осуществляется их пометка: p{s) = к, q(k) = з, а элемент dfc+i,s запрещается. Если помечена только вершина 5, то коррсктирутея пометки q{k) = q(s) и p(q(s)) = к и запрещается элемент -н,ф) Если помечена только вершина/с, то полагается p(s) = р(к) ид(р(&)) = 5 и запрещается элемент dp(fc)+i)5. Если помечены обе вершины s и і:, то полагается p(q(s)) р(к) и g(p(fc)) — 9(5). Элемент (1рф)+ілф) запрещается. Переход к следующему шагу. Заметим, что после п — 4 шагов работы алгоритма граф G представляет из себя частичный тур, содержащий п — 3 вершины. Другими словами, результат умножения первых п — 3 элементов подстановки а па одноцик-лическую подстановку 7г не содержит циклов. Этап 4. Среди шести подстановок, получаемых из подстановки а с помощью всевозможных перестановок трех последних элементов гп_2, гТі-і
Разрешимость многоиндексной аксиальной задачи о назначениях на одноциклических подстановках
Как было показано в разделе 1,4, етр- 36 данной диссертационной рабо-ты, трсхиндексиая аксиальная задача о назначениях на одноциклических подстановках разрешима не при всех п. Данное обстоятельство побудило интерес к исследованию вопроса разрешимости многойндексной аксиальной задачи о назначениях на одноциклических подстановках. Перейдем к формулировкам задачи. Многоиндексную аксиальную задачу на одноциклических подстановках можно сформулировать следующим образом: минимизировать па множестве подстановок { 1 к т} таких, что где через оди обозначена подстановка 7гх-_ія 2 тг +ітг , 1 к к т, обозначены элементы прямоугольной п х - х п матрицы заданные вещественные числа, 1 i\. п, к = 1,. ,., т. т Решение задачи может быть представлено выбором и п х - - - х п матрице (c iV-im) ровно го элементов, сумма весов которых и составляет целевую функцию. Классическая мпогоиндекспая задача о назначенных (на подстановках из симметрической группы Sn порядка п) iVP-трудна, начиная с числа индексов, равного трем [35, 36, 73]. В двухипдексном варианте эта задача полиномиально разрешима, чего нельзя еказать о двухиндекспой задачо о назначениях па одпоциклических подстановках, поскольку, очевидно, последняя совпадает с классической задачей коммивояжера. Отсюда следует, что рассматриваемая в диссертационной работе задача МАХ SNP-трудна [123, 135]. Более того, в отличие от двухиндексной задачи (коммивояжера) и мно-гоиндекспой задачи о назначениях многоиндексная аксиальная задача о назначениях на одно циклических подстановках не при всяких входах может иметь решение. Условия (1.20) для шестииидексной задачи проиллюстрированы па рисунке 1 в следующей наглядной форме (рис. 1-3)- В частности, здесь Далее будем ссылаться на следующие два очевидных утверждения, касающихся свойств подстановок из Sn Замечание 1.
При умножении произвольной подстановки яіз Sn па транспозицию (i,j) {как справа так и слева) четность числа циклов в подстановке меняется. При этоль число циклов уменьшается на единицу, если индексы і и j принадлежат разным циклам, и увеличивается па единицу, если i j находятся в одном цикле. Замечание 2. Для любых двух подстановок х и а из Sn имеет место свойство: подстановки тг и атга"1 имеют одинаковое число циклов. Задачу будем называть разрешимой, если для нее существует такая система подстановок {-к 1 А: га}, для которой выполняются условия (L20). В противном случае задачу называем неразрешимой. В 7] обоснован необходимый признак — нечетность п —- разрешимости трехиндексной задачи. Этот признак легко распространяется на случай произвольного числа индексов m 2. Теорема 4. При п т 2 для разрвгшімости т-индекспой задачи о назначении па одпоциклических подстановках из Рп необходимо, чтобы п было нечетным. Доказательство. Допустим противное: для некоторого четного п нашлись подстановки ( 1 k т}, удовлетворяющие условию (1.20). Тогда первые две подстановки тгі, Х2 и их произведение 7Г27Г1 являются одно-циклическими. Подстановка 7П представима в виде произведения (п — 1) транспозиций, число которых нечетно в силу четности тг. Согласно замечанию 1 после умножения одпоциклической подстановки 7Г2 на почетное число транспозиций (справа) мы получим подстановку 7Г2ТГі с четным числом циклов, т. е. 7Г2Л"! Рп. Пришли к противоречию. Рассмотрим разбиение множества нечетных натуральных чисел па подмножества, Легко видеть, что 7-индексиая задача не имеет смысла при п 7. Далее для определенности положим тг = (1,2,-.. , п). Лемма 3, Если п Є Ni и п 7, то 7-индексная задача о назначениях на одноциклических подстановках разрешима. Доказательство. Покажем, что если п Є N\ и п 7, то подстановки являются допустимым решением задачи. Действительно, в этом случае ПОДСТаНОВКИ, БХОДЯЩИе В (1.20), ИМеЮТ ВИДІ 7Г, 7Г2,7Г3, 7Г4,7Г5,7Г и являются одноциклическими,
Двухслойная планарная задача о назначениях па одноцикличсских подстановках
Для решения задачи (2,15)-(2.17) предлагается следующий приближенный алгоритм. Алгоритм: Этап 1. Подстановку тг Є Рп находим с помощью алгоритма из [6\ на матрице суд?, 1 jy к, п. Пусть D = (djk) - п х п матрица, такая что Этап 2. Этап состоит из п — 5 шагов» if/аг , 1 і п — 5. Просматриваем элементы строки ц матрицы D с номерами столбцов г.ч , t 5 п. Пусть г - номер столбца минимального иэ этих просмотренных элементов. Тогда, поменяв в а местами элементы i\li и &и\ получим подстановку а х\ Переходим к следующему шагу. Этап 3. В результате выполнения этапа 2 получим подстановку с "4 . Если а 4) удоклетворяст условию (2Л6), то положим а — а п 4\ иначе среди (4! — 1) подстановок, полученных из ст -4 с помощью перестановки 4 последних элементов, найдется хотя бы одна подстановка, удовлетворяющая условию (2,16), ее и берем в качестве а. Имеем приближенное решение целевой функции Время работы алгоритма 0(п2). Перейдем к вероятностному анализу точности алгоритма для решения задачи па случайных входах, определяемых множеством А1п матриц (сщ) размера п х п х щ где элементы суд - независимые случайные величины, выбираемые из отрезка [att,fort], где Ьп ап 0, с одинаковой функцией распределения. Данный алгоритм фактически представляет из себя последовательное применение алгоритма из [6] к каждому слою. Легко видеть, что оценки пе-роятности несрабатывания и относительной погрешности, условия асимптотической TOMHOCTHJ полученные для алгоритма из [6], остаются справедливыми. Приведенные выше алгоритмы могут использоваться и для максими-зационных версий задач. Заметим, что в этом случае алгоритмы будут асимптотически оптимальными без каких либо дополнительных условий на входные данные. Задачу (2.15)-(2.17) можно сформулировать в терминах теории графов. Элементам cijic (соответственно, C2jk)i 1 5; Зі к п сопоставим полный п-вершинный ориентированный граф Gi (соответственно, G2) с весами дуг cijk (соответственно, C2jjt).
Тогда подстановки тг,(7 в силу условий (2ЛС)-(2.17) будут соответствовать двум реберно непересекающимся гамильтоно-вым контурам Таким образом, двухслойная плапарная задача о назначениях на одноциклических подстановках заключается в отыскании в графе двух реберно непересекающихся гамильтоновых контуров минимального суммарного веса. Рассмотрим метрическую задачу на неориентированном графе- Тогда задачу можно сформулировать следующим образом. Дан полный п-вершинный неориентированный граф G — (VtE) с дву мя весовыми функциями ребер wi : Е —+ й, w2 Е — R. Для любых трех вершин i9j,k Є V справедливы неравенства W\(i,j) zt)i(i,k) + wiUtk) Wi{h3) (Ї,fc) + w2(j,k) (неравенство треугольника). Далее под W{(H) будем понимать Wi(II) — 2eHwi(e) Требуется найти такие реберно непересекающиеся гамильтоновы циклы Ні С В и Н2 С Е, суммарный вес которых W\{H{) + W2{H2) минимален. Обозначим w = Ші = г 2- Требуется найти реберно непересекающиеся гамильтоповы циклы Hi Z Е и Н2 С Е, суммарный вес которых W(Hi)+W(H2) минимален. Обозначим минимальный суммарный вес этих циклов через W . Алгоритм: Этап 1, С помощью алгоритма Кристофидеса-Сердкжова (16, 53] строим первый гамильтонов цикл Hi С G. Без ограничения общности считаем, ЧТО # {1,2,...,71,1}. Этап 2. Если п нечетно, то в качестве второго гамильтоиова цикла Н2 берем последовательность вершин {1,3,5,.. . ,п,2,4,., ,,п-1,1}, в которой идут в возрастающем порядке сначала все нечетные вершины, затем все четные вершины. На этом алгоритм закапчивает свою работу. В противном случае идем на этап 3. Этап 3. (Выполняется при четном п.) Через С2 (соответственно, Сз) обозначим совокупность п различных ребер вида (г г + 2) (соответственно, (і,г + 3)). Очевидної С2 С G является 2-фактором, состоящим из двух циклов: С" = {1,3,..., п — 1,1} и
Похожие диссертации на Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях
