Маршрутно-распределительные задачи: теория и приложения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Иванко, Евгений Евгеньевич

• Иванко, Евгений Евгеньевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Иванко, Евгений Евгеньевич

Содержание

Введение

Обзор литературы

Глава I. Вводные аспекты

1.1. Маршрутно-распределительная задача

1.2. Задача коммивояжера

1.2.1. «Натуральные порядки»

1.2.2. Задача коммивояжера как задача линейного целочисленного программирования

1.2.3. Метод динамического программирования в задаче коммивояжера

1.2.4. Задача курьера

1.2.5. Обобщенная задача коммивояжера

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.5.4. Об одной дискретизации задачи последовательного управления

1.5.5. Задача быстродействия в классе простых движений с элементами маршрутизации

1.5.6. Игровые постановки

1.6. Устойчивость в задаче комбинаторной оптимизации

1.6.1. Введение

1.6.2. Классический подход

1.6.3. Реоптимизация

1.6.4. Шаблонные маршруты

1.7. Адаптивная устойчивость

1.7.1. Общая теория

1.7.2. Структура приложений адаптивной устойчивости

Глава II. Адаптивная устойчивость оптимального маршрута в задаче коммивояжера при изменении множества посещаемых вершин

II. 1. Введение и обозначения

11.2. Необходимые условия

11.2.1. Вопросы теории

11.2.2. Алгоритмические приложения

11.2.3. Эксперименты

11.3. Критерий адаптивной з^стойчивости

Н.3.1. Вопросы теории

11.3.2. Алгоритмические приложения

11.3.3. Эксперименты

11.4. Достаточные условия

II.4.1. Вопросы теории

П.4.2. Аналитические области адаптивной устойчивости

П.4.3. Алгоритмические приложения

11.4.4. Эксперименты

11.5. Задачи последовательного управления

11.5.1. Эвристические решения

11.5.2. Адаптивная устойчивость

11.6. Некоторые замечания

11.6.1. Топология областей адаптивной устойчивости

11.6.2. Асимптотика относительной площади области устойчивости в евклидовой ЗК

11.6.3. Примеры, демонстрирующие новизну постановки

II.6.4. Модельный пример прикладной задачи с применением областей адап-

тивной устойчивости

Глава III. Адаптивная устойчивость оптимального распределения при изменении множества распределяемых заданий

III. 1. Введение и обозначения

111.2. Необходимые условия

111.2.1. Вопросы теории

111.2.2. Алгоритмы

111.3. Критерий адаптивной устойчивости

111.4. Достаточные условия

111.5. Специфика задач распределения заданий

111.6. Алгоритмы

111.7. Сравнение областей адаптивной устойчивости

Глава IV. Усечение схемы динамического программирования

IV. 1. Условия предшествования

IV.2. «Встречное» динамическое программирование

IV.2.1. Задача коммивояжера

IV.2.1.1. Обозначения и классическая схема

IV.2.1.2. Сокращенная схема

IV.2.1.3. Сравнение трудоемкости

IV.2.1.4. Заключение

IV.2.2. Задача распределения заданий

IV.2.2.1. Обозначения и классическая схема

IV.2.2.2. Сокращённая схема МДП

IV.2.2.3. Сравнение трудоемкости

IV.3. Кластеризация в задаче коммивояжера

IV.3.1. Алгоритм решения ЗК без дополнительных условий

IV.3.2. Дополнительные условия па маршрут

IV.3.3. Эксперименты

IV.3.4. Заключение

IV.4. Выводы к четвертой главе

Глава V. Приложения

V.l. Адаптивная устойчивость в управлении перемещением транспортных средств236

V.l.l. Грузоперевозки

V.l.2. Авиапожарное патрулирование

V.2. Приложения минимаксной маршрутио-распределительной задачи

V.2.I. Математическая постановка задачи

V.2.2. Оптимизация перемещений в агрессивной среде

V.2.3. Эволюционная изменчивость

V.2.3.I. Содержательная постановка

V.2.3.2. Эвристический алгоритм

V.2.3.3. Модельный эксперимент

V.3. Оптимизация перемещений исследователя-этолога

V.3.I. Перестановка камер на местности

V.3.1.1. Формальная постановка задачи

V.3.I.2. Метод динамического программирования

V.3.1.3. Доказательство оптимальности

V.3.I.4. Эксперимент

V.3.2. Другие постановки

Заключение

Литература

Приложение А. Таксономическое дерево языков

Введение диссертации (часть автореферата) на тему «Маршрутно-распределительные задачи: теория и приложения»

Введение

Актуальность работы. Задачи комбинаторной оптимизации (ЗКО) встречаются практически во всех областях человеческого знания, где требуется из большого числа вариантов выбрать наилучший или как минимум целесообразный. В качестве примеров таких задач можно привести планирование производства; оптимизацию коммуникационной инфраструктуры; оптимизацию загрузки параллельно работающих исполнителей (это могут быть, например, станки, рабочие или конвейеры современного вычислителя); задачи оптимальной загрузки транспортных контейнеров; оптимизацию раскроя в швейном и металлообрабатывающем производствах, задачи оптимизации расписаний. С теоретической точки зрения многие ЗКО служат в качестве своеобразных эталонов трудоемкости для задач, поддающихся алгоритмическому решению за конечное число итераций. Исследование ЗКО сыграло важную роль в становлении современной теории сложности алгоритмов и в формулировке одной из важнейших математических проблем современности, касающейся равенства классов Р и NP. Большое внимание в диссертации уделяется разработке и исследованию алгоритмов. В этой связи следует отметить труды A.V. Aho, D.E. Kmitli, Л. von Neumann, A.M. Turing, .I.D. Ulmann, В.Л. Береснева, Э.Х. Гимади, А.Ю. Горнова, Ю.И. Журавлева, A.B. Кельмаиова, А.Н. Колмогорова, Ю.А. Кочетова, H.H. Кузюри-на, A.A. Лазарева, Вл.Д. Мазурова, А.Л. Семенова, М.Ю. Хачая, оказавшие влияние на работу автора.

Основное внимание в диссертации посвящено двум ЗКО: задаче коммивояжера (ЗК) и задаче распределения заданий (РЗ) (наиболее близким аналогом, по-видимому, является задача размещения заказа). К ЗК (или к ее расширению) обыкновенно сводится всякая задача построения оптимального порядка выполнения работ (не считая более общие задачи оптимизации расписаний). К РЗ сводятся задачи балансировки нагрузки одновременно работающих исполнителей. В настоящей диссертации исследуются как каждая из этих NP-трудных задач по отдельности, так и их важная с прикладной точки зрения комбинация: балансировка нагрузки в бригаде исполнителей осуществляющих перемещение по заданному множеству пунктов. Все исследуемые в диссертации задачи проявляют черты ЗК или РЗ и объединены общим названием «маршрутно-раенределительные задачи» (МРЗ). К МРЗ сводятся многие из перечисленных выше ЗКО, например: оптимизация перемещения транспортных средств, роботизированных манипуляторов, патрулирующих устройств,

оптимизация порядка выполнения заданий на конвейерных производствах и в параллельно работающих вычислителях, моделирование и анализ эволюционных деревьев и другие. В ряде перечисленных постановок, связанных с перемещениями системы, описываемой дифференциальными уравнениями, МРЗ становится непрерывной бесконечномерной задачей последовательного управления (см. работы A.A. Белоусова, Ю.И. Бердышева, М.С. Габриеляна, L.E. Dubins, Н.Ю. Лукояиова, H.H. Петрова, А.Г. Ченцова, A.A. Чикрия).

Исследование устойчивости найденных оптимальных решений является одним из важнейших направлений качественного анализа любой оптимизационной задачи. Не являются в этом смысле исключением и ЗКО. В связи с данными исследованиями необходимо отметить школы в ВЦ РАН под рук. основателя теории устойчивости в ЗКО В.К. Леонтьева; Белорусском ГУ под рук. В.А. Емеличева; Институте кибернетики HAH Украины под рук. И.В. Сергиенко; оригинальные работы по устойчивости алгоритмов решения целочисленных ЗКО, основанных па переборе ¿-структур, ведущиеся в Омском ГУ под рук. A.A. Колоколова; работы М. Либура, Польша, А. Фиакко, США и оригинальный результат В.Г. Дейнеко, связанный с критерием оптимальности шаблонного маршрута (The Master Tour Problem).

В общем случае исследование возможности конструктивного использования найденного оптимального решения при построении оптимально1 о решения задачи с возмущенными начальными данными связано с понятием реоптимизации (reoptimization) и, в меньшей степени, онлайн-оптимизации. В области реоптимизации решений полиномиальных задач следует отметить работы P.M. Spira, F. Chin, V. King, С. Demetrescu. Сам термин «реопти-мизация» принадлежит, по всей видимости, M.W. Schaffter. Особенный интерес реоптими-зация представляет в NP-трудных задачах, например в ЗК (С. Archetti, L. Bertazzi, M. G. Speraiiza, S. Arora, H.-J. Bockenhauer, J. Hroiukovic, B. Escoffier, G. Ausiello, T. Berg). В NP-трудных задачах (и в частности в ЗК) реоптимизация, как правило, оказывается также NP-трудной (A. Zych). Ситуация не меняется н в случае, когда известны все оптимальные решения исходной задачи (Л. Hromkovic). Среди современных авторов, активно работающих над вопросами реоптимизации, следует отметить Л. Hromkovic, H.-Л. Bockenhauer, А. Zych, T. Tamir.

В настоящей диссертации рассматривается оригинальный подход к постоптимальному анализу, цели которого близки к классической устойчивости, рассматриваемые постановки к реоптимизации, а методология исследования основана на принципе Беллмана.

А именно изучаются условия, описывающие класс возмущений, к которым фиксированный алгоритм позволяет адаптировать найденное оптимальное решение. Подобная «ал-горитмоспецифическая» усточивость/реоптимизация названа в диссертации адаптивиой устойчивостью. Исследование адаптивиой устойчивости оптимальных решений трудоемких дискретных задач представляет прикладной интерес в первую очередь как средство постоптимального анализа и отбора наиболее перспективных среди множества несравнимых между собой оптимальных решений, соответствующих различным математическим моделям исследуемого явления.

Цель диссертационной работы состоит в исследовании методов решения, постоптимального отбора решений, а также областей прикладного применения МРЗ.

Для достижения поставленной цели были решены следующие задачи:

- построена единообразная теория адаптивной устойчивости оптимальных решений в ЗКО, обладающей определенной структурой, для случаев добавления, удаления или замены одного из элементов множества начальных данных; построенные теоретические схемы реализованы применительно к ЗК и РЗ; разработаны оригинальные алгоритмы проверки адаптивной устойчивости и проведена оценка их трудоемкости; численно построены области адаптивной устойчивости для ЗК на конечном подмножестве точек евклидовой плоскости с целочисленными координатами; результаты для ЗК обобщены на задачу оптимального размещения графа на своих вершинах;

-для «симметричных» постановок ЗК и РЗ построены экономные в вычислительном отношении «встречные» варианты метода динамического программирования (МДП); проведена оценка снижения трудоемкости МДП в ЗК, возникающего при добавлении в задачу одного условия предшествования; построен специфический для ЗК эвристический «неметрический» метод кластеризации посещаемых вершин, позволяющий учитывать условия предшествования;

- исследованы точные и эвристические решения ряда прикладных задач, в частности построен и реализован на ЭВМ МДП в задаче перестановки объектов на пересеченной местности; на основе минимаксной МРЗ (ММРЗ) [43] в постановке с общим плавающим стартом (location problem) разработана математическая модель для исследования филогенетических задач; предложен численный метод декомпозиции задачи последовательного управления в набор соответствующих по ограничениям задач управления.

Научная новизна. Все результаты, выносимые на защиту, являются новыми. В

частности:

- введено понятие адаптивной устойчивости; предложены определения адаптивной устойчивости оптимальных решений ЗКО при добавлении, удалении или замене одного из элементов множества начальных данных;

- получены соответствующие новым определениям необходимые, достаточные, а также необходимые и достаточные условия сохранения (возможности адаптации) оптимальных решений;

- построенная общая теория реализована для ЗК и РЗ и задачи оптимального размещения графа на своих вершинах;

- предложены усеченные схемы МДП для «симметричных» постановок ЗК и РЗ; доказана корректность предложенных схем и проведена оценка их трудоемкости; проведена теоретическая оценка трудоемкости специфического МДП для ЗК с условиями предшествования; построен МДП для задачи перестановки объектов на неоднородной местности;

- разработан метод иерархической кластеризации посещаемых вершин в ЗК и задаче курьера (ЗК с условиями предшествования), позволяющий понижать размерность задачи;

- предложен метод использования ММРЗ в целях поиска как областей потенциального расположения филогенетического предка, так и областей вероятной гибридизации для группы организмов с заданной функцией схожести.

Практическая значимость. Результаты, изложенные в диссертации, могут быть использованы в прикладных постановках ЗК и РЗ для построения областей адаптивной устойчивости, используемых как для целесообразного постоптимального отбора среди оптимальных решений, так и для описания возмущений начальных данных, к которым известное оптимальное решение допускает адаптацию за полиномиальное от размерности задачи число операций. Такого рода «быстрая» адаптация может применяться, например, в программных комплексах, обслуживающих транспортные компании, поскольку в процессе перевозки грузов ситуация часто изменяется.

Предложенный алгоритм кластеризации позволяет понижать размерность ЗК с сохранением условий предшествования. Алгоритм может служить самостоятельным эвристическим способом решения задачи курьера.При этом будучи остановлен на любой итерации, он может быть доведен до некого целесообразного решения исходной задачи с помощью любого другого точного, приближенного или эвристического способа решения задачи курьера. Такая «смешанная» стратегия решения может быть полезна, например, в

задаче оптимизации распределения заданий и перемещения бригады исполнителей и агрессивной внешней среде, где важно найти баланс между точностью решения (опасностью для здоровья работников бригады) и временем расчета (опасностью распространения заражения). Работы в этой области ведутся совместно с кафедрой атомной энергетики УЭИ УрФУ.

Для поиска вероятного предка (либо области вероятной гибридизации) для множества «эволюционирующих объектов» в работе предлагается использовать ММРЗ, а также обобщенную «задачу мультнкурьера» (посещаются не точки, а конечные множества, на которых заданы условия предшествования [521) в постановке с плавающим стартом. Рассматриваемый подход может использоваться в случае, если известна степень схожести исследуемых объектов и целесообразно предположить, что эволюционное развитие объектов шло в рамках известного числа выраженных «русел». Работы в данной области ведутся совместно с лабораторией филогенетики и биохронологии ИЭРиЖ УрО РАН.

Построенный МДП для оптимального решения задачи перестановки объектов может применяться для оптимизации работ в ходе многократного перемещения наблюдательных устройств на пересеченной местности. Разработанные алгоритмы используются в интересах дистанционного мониторинга состояния особо охраняемых природных территорий Свердловской области.

Исследования рассматриваемых в диссертации задач проводились при поддержке грантов РНФ 14-11-00109, РФФИ 10-01-90020-р-урал-а, 10-08-484-а, 11-01-90432-Укр-ф-а, 13-04-847а, 13-01-90414-У кр-ф-а, 13-08-043а, 13-01-96022-р- урал-а, 14-08-00419; региональных целевых программ УрО РАИ 13Г11, 13П13; программ Президиума УрО РАН для молодых ученых 13-1-НП-1, 13-1-ТГ-779, 14-1-ИП-5.

На защиту выносятся следующие основные результаты:

- введено понятие адаптивной устойчивости; получены соответствующие новому понятию необходимые, достаточные, а также необходимые и достаточные условия адаптивной устойчивости для ЗКО, обладающих определенной структурой;

- построенная абстрактная теория реализована для ЗК и РЗ в случае добавления, удаления или замены одного из элементов начальных данных, включая вывод условий адаптивной устойчивости, разработку соответствующих алгоритмов и оценку их трудоемкости;

- предложен метод постоптимального предпочтения найденных оптимальных реше-

ний на основе их адаптивной устойчивости к потенциальным возмущениям;

- разработан усеченный вариант МДП для РЗ с равноценными исполнителями; показана корректность разработанного алгоритма и проведена оценка его трудоемкости; проведена теоретическая оценка влияния условия предшествования на трудоемкость МДП в ЗК; разработан МДП и показана его корректность для задачи перестановки объектов на неоднородной местности;

- разработан эвристический алгоритм кластеризации элементов начальных данных в ЗК и задаче курьера; для разработанного алгоритма проведена оценка трудоемкости, проделаны вычислительные эксперименты;

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: всероссийской конференции «Дискретная оптимизация и исследование операций», Новосибирск, 2010; международной научно-технической конференции «Суперкомпыотерные технологии: разработка, программирование, применение», Дивно-морское, 2010; 14-ой конференции «Математическое программирование и приложения», Екатеринбург, 2011; международной конференции «Анализ моделирование, развитие экономических систем», Севастополь, 2011; международной конференции «Алгоритмический анализ неустойчивых задач», Екатеринбург, 2011; 7-ой международной конференции «Безопасность АЭС и подготовка кадров», Обнинск, 2011; международной суперкомпьютерной конференции «Научный сервис в сети Интернет», 2012; всероссийской конференции «Управление в технических, эргатических, организационных и сетевых системах», Санкт-Петербург, 2012 (2 доклада); 26-th European international conference on operational research, Rome, Italy, 2013; 14th International Conference Computational and Mathematical Methods in Science and Engineering, Rota, Spain, 2014; международной конференции Алгоритмический анализ неустойчивых задач (АAl 13-2014), Челябинск, 2014.

Кроме того, результаты диссертации докладывались на: расширенном семинаре лаборатории дискретных экстремальных задач ИМ СО РАН; семинаре сектора математических методов распознавания и прогнозирования отдела математических проблем распознавания и методов комбинаторного анализа ВЦ РАН; расширенном семинаре отдела математического программирования ИММ УрО РАН; заседании ученого совета МММ УрО РАН; семинаре лаборатории дискретной оптимизации Омского филиала ИМ СО РАН; расширенном семинаре кафедры дифференциальных уравнений математического факультета УдГУ; расширенном семинаре лаборатории оптимального управления ИДСл-

ТУ СО РАН; расширенном семинаре кафедры экономико-математических методов и статистики факультета экономики и управления ЮУрГУ; расширенном семинаре кафедры системного программирования ЮУрГУ; расширенном семинаре лаборатории интеллектуальных систем Научно-исследовательского института многопроцессорных вычислительных систем им А.В. Каляева ЮФУ; неоднократно обсуждались на расширенном семинаре отдела управляемых систем Института математики и механики УрО РАН.

Публикации. Материалы диссертации опубликованы в 28 печатных работах, из них одна монография [48], 13 статей в рецензируемых журналах [22, 30, 34, 38, 39, 41, 42, 4446, 49, 52, 127], 1 статья в сборнике трудов [36], 13 публикаций в сборниках материалов конференций [23, 24, 35, 37, 40, 43, 47, 50, 51, 53, 71, 125, 126].

Личный вклад автора. Все выносимые на защиту результаты получены лично автором за исключением вспомогательных результатов, используемых в доказательствах, которые приводятся в тексте диссертации для полноты изложения и специально отмечены. В работах [22-24, 30, 51 53, 71[ А.Г. Ченцову принадлежат постановки задач, общая схема исследования и некоторые идеи доказательств; A.M. Григорьеву и П.А. Ченцову принадлежит программная реализация и проведение вычислительных экспериментов; С.Т. Князеву принадлежит обзор возможных приложений; конкретные доказательства основных положений, разработка алгоритмов и оценка их трудоемкости проведены автором диссертации самостоятельно.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 5 глав, заключения, библиографии и 1 приложения. Общий объем диссертации 289 страниц, включая 52 рисунка и 15 таблиц. Библиография включает 165 наименований на 16 страницах.

Обзор литературы

Начинается диссертация с введения основных понятий, связанных с реализацией общей схемы динамического программирования в дискретных задачах [1], применением принципа Беллмана в задаче коммивояжера [92, 102] и задаче распределения заданий [15, 55, 92]. В связи с возможными приложениями развиваемой в диссертации теории устойчивости рассматриваются элементы теории управления [12, 59, 03, 76, 89] с особым вниманием такой малоизученной области как задачи последовательного управления [8, 73, 95]. Подробный обзор состояния самих задач (коммивояжера и распределения заданий) проводится в первой главе перед их формальным изложением.

Далее рассматриваются вопросы усточивости и реоитимизации оптимальных решений задачи комбинаторной оптимизации.

Устойчивость оптимальных маршрутов в задаче коммивояжера при изменении матрицы весов подробно изучалась в литературе, начиная с 1970-х годов. По-видимому первой работой в этой области является [61]. Наиболее значимые дальнейшие результаты для ряда общих постановок задач комбинаторной оптимизации при возмущении весовой функции получены научными коллективами в Вычислительном центре РАН под руководством проф. В.К. Леонтьева [17, 18, 62, 160]; в Белорусском государственном университете под руководством проф. В.А. Емеличева [31, 32]; в Институте кибернетики HAH Украины под руководством академика РАН и HAI! Украины PI.В. Сергиенко [79-82], а также работы, ведущиеся в Польской Академии Наук под руководством Марека Либуры [138, 139, 147, 162]. Отдельно следует упомянуть работы, ггоствященные исследованию вопросов устойчивости алгоритмов решения задач линейного целочисленного программирования на основе анализа устойчивости лексико-графических структур. Эти исследования ведутся в Омском государственном университете; под руководством проф. A.A. Колоколова [26-29];

Более близкими к исследованиям настоящей диссертации следует считать работы, связанные с понятием шаблонного маршрута (master lour) и решениями ЗК на основе кривых Пеано. Так в работе [140| по-видимому впервые ставится задача поиска такого маршрута обхода клиентов, для которого каждый «иодмаршрут», соответствующий активным на момент начала обхода клиентам (составляющим подмножество исходного множества клиентов), был бы максимально близок к оптимальному маршруту на данном подмножестве активных клиентов (в формальной постановке речь идет о минимизации максимально го

или среднего отклонения). Иными словами ищется маршрут, сужение которого (без потери исходного порядка обхода) на всякое подмножество множества исходных вершин позволяет получить «достаточно близкий» к оптимальному «иодмаршрут». Для построения таких маршрутов использовались эвристические алгоритмы решения задачи коммивояжера на основе кривых Пеано [99, 105, 106, 146] (данные исследования связаны в основном с именами Джона Бартольди и Дмитриса Бертсимаса). Более глубокое исследование задачи поиска подобных «универсальных» маршрутов, получившей соответствующее название universal TSP (и связанной с ней задачи a priory TSP) проведено в работах [124, 156, 159], связанных в первую очередь с именем Дэвида Шмойса. Важной в контексте диссертации следует считать формулировку «оптимальной» версии задачи universal TSP, названную Кристосом Пападимитру в книге [143, с.435] master tour property:

«Пусть города в евклидовой задаче коммивояжера расположены в вершинах выпуклого многоугольника. В таком случае не только нахождение оптимального маршрута является легкой задачей (это периметр многоугольника), но также имеет место свойство шаблонного маршрута: оптимальный маршрут для каждого подмножества городов может быть получен простым отбрасыванием из шаблонного маршрута городов, не попавших в подмножество».

Отметим, что таким же свойством обладают упоминавшиеся выше решения задачи коммивояжера на основе кривых Пеано, однако в этом случае речь обычно не идет о точных решениях порядок сохраняется на уровне эвристик.

Ключевой результат в области исследования шаблонных маршрутов получен в работе [115], где показано, что для задачи коммивояжера с симметричной матрицей весов существует перенумерация вершин, сводящая данную матрицу к виду матрицы Кальмансона [132] тогда и только тогда, когда оптимальное решение исходной задачи есть шаблонный маршрут.

Приведенные работы, посвященные устойчивости оптимальных решений в дискретных задачах, связаны либо с изучением устойчивости при изменении некоторой функции стоимости при неизменном множестве начальных данных, либо с построением шаблонного маршрута в задаче коммивояжера, всякий подмаршрут которого является оптимальным. В общем случае исследование возможности конструктивного использования найденного оптимального решения при построении оптимального решения задачи с возмущенными начальными данными связано с понятием реоптимпзации (reoptimization). Мотивом к раз-

витию данных работ послужила публикация [114, 161], в которой показан существенный выигрыш в трудоемкости решения задачи минимального остовного дерева, содержащего V вершин, при наличии такого решения для V\ {.-;;} при х Е V. Позже рсоптимизационпый подход позволил улучшить оценку трудоемкости в задаче поиска кратчайшего пути в ориентированном графе [116, 134]. Сам термин реоптимизация появился, по всей видимости, в работе [155]. Особенный интерес реоптимизация представляет в КР-трудных задачах. Так реоптимизации оптимальных маршрутов в исследуемой в настоящей диссертации задаче коммивояжера посвящено множество работ [96, 104, 107, 118, 152, 153]. Вообще в ИР-труд-ных задачах (и в частности в задаче коммивояжера) даже при известном оптимальном решении его реоптимизация, как правило, оказывается КтР-трудной [148, 152, 163]. Ситуация не меняется и в случае, когда известны все оптимальные решения исходной задачи.

Другим близким подходом является онлайн-оптимизация, где ставится задача динамического изменения целесообразного решения задачи в ходе постоянно и относительно быстро изменяющихся начальных данных, с использованием предыдущих решений [97, 108, 109, 128, 158].

В постоптимальном анализе настоящей диссертации предполагается известным не только оптимальное решение исходной задачи, но и оптимальные решения конечного множества близких к исходной «подзадач». Мощность этого множества подзадач обычно «невелика» по сравнению с числом возможных состояний исходной задачи (и может быть меньше мощности множества ее оптимальных решений), а решение каждой из таких подзадач обладает не большей трудоемкостью, чем решение исходной задачи. При наличии такого набора решений, идейно опираясь на принцип Веллмана, удается построить полиномиальные условия проверки возможности реоптимизации для некоторых классов возмущений.

В подходе настоящей диссертации исследуются условия, обеспечивающие возможность простой в вычислительном отношении адаптации найденного оптимального решения к абстрактному возмущению начальных данных (в частности, к добавлению, удалению или замене одного из элементов) с сохранением оптимальности. Все полученные условия напрямую зависят от производимого возмущения и позволяют определить множества возмущений, допускающих подобную адаптацию. Важной особенностью исследований диссертации является возможность анализа устойчивости оптимального решения при росте числа элементов входных данных, например, изучаются условия при которых удается

«вставить» (с небольшими, по сравнению с решением всей задачи заново, вычислительными затратами) новый элемент начальных данных в найденный оптимальный маршрут с сохранением оптимальности последнего. Полученные условия, впрочем, не ограничиваются исследованием оптимальных маршрутов в задаче коммивояжера, но также применяются к задаче распределения заданий, а в работе [48) обобщаются и на случай абстрактной задачи комбинаторной оптимизации, обладающей рядом структурных ограничений.

Также в диссертации излагается «встречный» метод динамического программирования в замкнутой задаче коммивояжера с симметричной матрицей стоимости перемещении и минимаксной задаче распределения заданий с равносильными исполнителями. Насколько известно автору, такой метод предложен впервые, однако, учитывая большое число работ, посвященных методу динамического программирования в задаче коммивояжера, начиная с классических работ [102, 123] и далее, например, [64, 66, 92, 121] возможное существование схожего «симметричного» метода динамического программирования в задаче коммивояжера весьма вероятно. 13 связи с этим «встречный» метод для задачи коммивояжера не выносится на защиту, хотя подробно излагается в диссертации. В отличие от задачи коммивояжера метод динамического программирования в минимаксной задаче распределения заданий несколько менее изучен. Наиболее подробно этот метод излагается в монографии [92].

Наконец рассматриваются различные приложения, связанные с решением задачи коммивояжера и задачи распределения заданий в интересах актуальных задач атомной энергетики, а также экологии и таксономии животных. Задачи, связанные с оптимизацией перемещений бригады исполнителей в агрессивной внешней среде, активно изучаются коллективом под руководством А.Г. Ченцова [3, 67, 68, 83, 84, 90]. Исполняемые задания как правило моделируются конечными множествами. Выполнение задания может означать посещение множества в одной точке; «вход» во множество и «выход» из него могут быть различны; наконец, выполнение задания может заключаться в посещении всех точек конечного множества, соответствующего заданию. Отдельный как теоретический, так и прикладной интерес представляют задачи, в которых влияние агрессивной среды зависит от списка невыполненных заданий.

Список литературы диссертационного исследования кандидат наук Иванко, Евгений Евгеньевич, 2015 год

Литература

1. Арис Р. Дискретное динамическое программирование. — Москва : Мир, 1969.

2. Бабурин А., Гимади Э. X., Коркишко Н. М. Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса // Дискретн. анализ и исслед. опер. — 2004, — Т. 2, № 11:1,— С. 11-25.

3. Балушкин Ф. А., Сесекин А. II., Ченцов А. Г. Задачи маршрутизации перемещений и их приложения в атомной энергетике // Материалы 4-ой международной конференции "Математика, ее приложения и математическое робразование". - Улан-Удэ, 2011.- С. 21-25.

4. Беллман Р. Динамическое программирование. — Москва : Иностранная литература, 1960.

5. Белоусов А. А. О линейных дифференциальных играх преследования с интегральными ограничениями // Дифференциальные уравнения и топология, тез. докл. Между-нар. конференции, посвящ. 100-летию со дня рождения Л. С. Понтрягина. — Москва, 2008. - С. 321-322.

6. Бердышев Ю. И. Синтез оптимального по быстродействию управления для одной нелинейной системы четвертого порядка // Прикл. математика и механика. — 1975. — Т. 39, .У® 6. - С. 985-994.

7. Бердышев Ю. И. К задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнения и процессы управления. — 1999. № 2. — С. 3-27.

8. Бердышев Ю. И. Нелинейные задачи последовательного управления. — 2000.

9. Бердышев Ю. И. О выборе очередности сближения нелинейного объекта с группой движущихся точек // Изв. РАН. Теория и системы управления. — 2011.— № 1.— С. 32 39.

10. Бердышев Ю. И. О некоторых задачах выбора очередности сближения управляемой системы с группой объектов // Тр. ИММ УрО РАН. - 2012. - Т. 18, № 3. - С. 56-66.

11. Бронштейн Е. М., Гиндуллнн Р. В. Об одном классе задач маршрутизации // Математическое моделирование. — 2011. — Т. 23, № 0. — С. 123-132.

12. Варга Д. Оптимальное управление дифференциальными и функциональными уравнениями. Москва : Наука, 1977.

13. Васильев О. В., Леденева Т. М. Транспортная задача и оптимизация грузоперевозок // Вестник Воронежского государственного технического университета. — 2011. -Т. 7, № 11.- С. 82-84.

14. Гамкрелидзе Р. В. Основы оптимального управления. Тбилиси : Изд-во Тбилисского ун-та, 1977.

15. Гольдштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, — Москва : Наука, 1969.

16. Гольдштейн Е. Г., Юдин Д. Б. Линейное программирование. — Москва : Наука, 1969.

17. Гордеев Э. Н., Леонтьев В. К. Устойчивость в задачах на узкие места // Журнал вычислительной математики и математической физики. — 1980. — Т. 20, № 4. — С. 1071-1075.

18. Гордеев Э. Н., Леонтьев В. К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // Журнал вычислительной математики и математической физики. — 1996. — Т. 36, № 1. — С. 66-72.

19. Горнов А. Алгоритмы решения задач оптимального управления с терминальными ограничениями // Вычислительные технологии. — 2008. — Т. 13, № 4. — С. 44-50.

20. Горнов А. Алгоритмы решения задач оптимального управления с терминальными ограничениями // Мехатроника, автоматизация, управление. — 2010. № 8. — С. 2-6.

21. Горнов А. Алгоритмы решения задач оптимального управления с фазовыми ограничениями // Вычислительные технологии. — 2010. — Т. 15, № 2. — С. 24-30.

22. Григорьев А. М., Иванко Е. Е., Чепцов А. Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры // Моделирование и анализ информационных систем, — 2011.— Т. 18, № 3.— С. 101-124.

23. Григорьев А. М., Иваико Е. Е., Чеицов А. Г. К вопросу о применении параллельных алгоритмов для решения задач маршрутизации по методу динамического программирования // Тезисы докладов конференции «Анализ моделирование, развитие экономических систем». — Севастополь, 2011. — С. 14.

24. Григорьев А. М., Иванко Е. Е., Ченцов А. Г. Решение задач маршрутной оптимизации применительно к радиационно-опасным объектам с использованием суперкомпьютера «уран» // Тезисы докладов 7-ой международной конференции «Безопасность АЭС и подготовка кадров». — Т. 2. — Екатеринбург, 2011. — С. 103-105.

25. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва : Мир, 1982.

26. Девятерикова М. В. Исследование устойчивости задач и алгоритмов целочисленного программирования на основе регулярных разбиений : Дисс... кандидата наук / М. В. Девятерикова ; Омский государственный университет. 2001.

27. Девятерикова М. В., Колоколов А. А. Анализ устойчивости 1-разбиения множеств в конечномерном пространстве /7 Дискретн. анатиз и исслед. опер. — 2000. — Ж0 7:2. — С. 47-53.

28. Девятерикова М. В., Колоколов А. А. Об устойчивости некоторых алгоритмов целочисленного программирования // Известия вузов. Математика. — 2003. — № 12. — С. 41-48.

29. Девятерикова М. В., Колоколов А. А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика. — 2004. — № 3. — С. 48-54.

30. Динамическое программирование в обобщенной задаче курьера, осложненной внутренними работами / А. М. Григорьев, Е. Е. Иванко, С. Т. Князев, А. Г. Ченцов // Мехатроника, автоматизация, управление. — 2012. — № 7. — С. 14-21.

31. Емеличев В. А., Кузьмин К. Г., Леонович А. М. Устойчивость в векторных комбинаторных задачах оптимизации // Автоматика и телемеханика. — 2004. — X2 2. — С. 79-92.

32. Емеличев В. А., Подкопаев Д. П. О количественной мере устойчивости векторной задачи целочисленного программирования // Журнал вычислительной математики и математической физики. — 1998.- Т. 38, № 11. — С. 1801-1805.

33. Ефремов Д. В. Системный анализ и метод проектирования информационной логистической системы транспортного предприятия : Дисс... кандидата наук / Д. В. Ефремов ; Самарск.гос.техн.ун-т. — 2003.

34. Иванко Е. Е. Достаточные условия устойчивости оптимального маршрута в задаче коммивояжера при добавлении новой вершины и при удалении существующей // Вестн. Удмуртск. унив. Математика. Механика. Коми, науки.— 2010.— К2 1. — С. 46-56.

35. Иванко Е. Е. Устойчивость оптимальных маршуртов в задаче коммивояжера при добавлении и удалении вершин // Матер, всеросс. копф. «Дискретная оптимизация и исследование операций». — Новосибирск : Изд-во Ин-та математики, 2010. - С. 105.

36. Иванко Е. Е. Эмпирический метод dropby масштабируемого решения задачи коммивояжера // Сб. научи, тр. «Алгоритмы и программные средства параллельных вычислений». — Т. 10. — Екатеринбург : Изд-во Ин-та математики и механики УрО РАН, 2010.-С. 3-7.

37. Иванко Е. Е. Эмпирический метод dropby распараллеливания приближенного решения задачи коммивояжера // Материалы международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, приме/

нение.» СКТ-2010. — Т. 1. - Таганрог-Москва : Изд-во ЮжФУ, 2010.- С. 229-236.

38. Иванко Е. Е. Достаточные условия устойчивости в задаче коммивояжера // Труды Института математики и механики УрО РАН. — 2011. — JVS 3. — С. 155-168.

39. Иванко Е. Е. Критерий устойчивости оптимального маршрута в задаче коммивояжера при добавлении вершины // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. — 2011. — JV2 1. — С. 58-66.

40. Иванко Е. Е. Критерий устойчивости оптимальных решений при росте размерности распределительной задачи // Тезисы 14-ой конференции «Математическое программирование и приложения». — Екатеринбург, 2011.— С. 178.

41. Иванко Е. Е. Метод масштабирования в приближенном решении задачи коммивояжера // Автоматика и телемеханика. — 2011. — № 12. — С. 115-129.

42. Иванко Е. Е. Критерий устойчивости оптимальных решений минимаксной задачи о разбиении на произвольное число подмножеств при изменении размерности исходного множества // Тр. Инст. математики и механики УрО РАН. — 2012. — № 4. — С. 180-194.

43. Иванко Е. Е. Минимаксная задача мультикоммивояжера с плавающим центром в исследовании эволюционной изменчивости // Матер, конф. «Управл. в техн., эргатических, организационных и сетевых системах». — Санкт-Петербург, 2012. — С. 1164-1167.

44. Иванко Е. Е. Динамическое программирование в задаче перестановки однотипных объектов // Труды Института математики и механики УрО РАН. — 2013.— № 4.— С. 125 - 130.

45. Р1ванко Е. Е. Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями // Вестник ЮУрГУ, серия «Математическое моделирование и программирование». — 2013. - № 1. — С. 124-133.

46. Иванко Е. Е. Усеченный метод динамического программирования в замкнутой задаче коммивояжера с симметричной функцией стоимости // Труды Института математики и механики УрО РАН. - 2013. - № 1. - С. 121-129.

47. Иванко Е. Е. Устойчивость в задаче комбинаторной оптимизации как полиномиальная «адаптируемость» оптимальных решений при возмущении множества начальных данных // Материалы международной конференции «Дискретная оптимизация и исследование операций». — Новосибирск, 2013. — С. 117.

48. Иванко Е. Е. Устойчивость и неустойчивость в дискретных задачах. — Екатеринбург : Издательство УрО РАИ, 2013.

49. Иванко Е. Е. Адаптивная устойчивость в задачах комбинаторной оптимизации // Труды Института математики и механики УрО РАН. — 2014. — № 1. — С. 100 - 108.

50. Иванко Е. Е. Адаптивная устойчивость как метод оценки качества решения задачи комбинаторной оптимизации // Тез. докл. междунар. конф. «Алгоритмический анализ неустойчивых задач». — Екатеринбург, 2014. — С. 198-199.

51. Иванко Е. Е., Григорьев А. М. Области неустойчивости оптимальных маршрутов в задаче коммивояжера при добавлении новой вершины // Тез. докл. междунар. конф. «Алгоритмический анализ неустойчивых задач». — Екатеринбург, 2011. — С. 232-233.

52. Иванко Е. Е., Ченцов А. Г., Ченцов П. А. Об одном подходе к решению задачи маршрутизации перемещений с несколькими участниками // Известия РАН. Теория и системы управления. — 2010. — А5 4. — С. 63-71.

53. Иванко Е. Е., Чепцов П. А., Ченцов А. Г. Об одном методе решения задачи мультиком-мивояжера // Материалы конференции «Управление в технических, эргатических, организационных и сетевых системах».— Санкт-Петербург, 2012.— С. 1168-1171.

54. Исследование моделей организации грузовых перевозок с применением мультиагент-ной системы для адаптивного планирования мобильных ресурсов в реальном времени / Н. О. Амелина, А. Н. Лада, И. В. Майоров и др. // Проблемы управления.— 2011. — А2 6.-С. 31-37.

55. Канторович Л. В., Горстко А. Б. Оптимальные решения в экономике. — М : Наука, 1972.

56. Карманов В. Г. Математическое программирование;. — Москва : Наука, 1975.

57. Коротаева Л. Н., Назаров Э. М., Чепцов А. Г. Об одной задаче о назначениях // Ж. вычисл. матем. и матем. физ. — 1993. Т. 33, № 4. — С. 483-494.

58. Коротаева Л. Н., Сесекип А. Н., Ченцов А. Г. Об одной модис|>икации метода динамического программирования в задаче последовательного сближения // Ж. вычисл. матем. и матем. физ. — 1989. — Т. 29, № 8. — С. 1107-1113.

59. Красовский Н. Н. Некоторые задачи теории устойчивости движения. — Москва : Физматлит, 1959.

60. Лежнев А. В. Динамическое программирование в экономических задачах. - Москва : Бином, 2010.

61. Леонтьев В. К. Устойчивость задачи коммивояжера // Журн. вычисл. математики и мат. физики. - 1975. - Т. 15, № 5. - С. 1298 1309.

62. Леонтьев В. К. Устойчивость в линейных дискретных задачах // Проблемы кибернетики. - 1979. - № 35. - С. 169-185.

63. Математическая теория оптимальных процессов / Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко, — Москва : Наука, 1969.

64. Меламед И. И., Сергеев С. И., Сигал И. X. Задача коммивояжера, вопросы теории // Автоматика и телемеханика. — 1989. — № 9. С. 3-34.

65. Меламед И. И., Сергеев С. И., Сигал И. X. Задача коммивояжера, приближенные алгоритмы // Автоматика и телемеханика. 1989. — 11. — С. 3-26.

66. Меламед И. П., Сергеев С. П., Сигал И. X. Задача коммивояжера, точные алгоритмы // Автоматика и телемеханика. — 1989. - Xе 10. — С. 3-29.

67. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В. В. Коробкин, А. Н. Сесекин, О. Л. Ташлыков, А. Г. Чепцов. — Москва : Новые технологии, 2012.

68. Методы маршрутной оптимизации радиационно опасных работ / О. Л. Ташлыков, А. Н. Сесекин, С. Е. Щеклеин, А. Г. Ченцов // Седьмая научно-техническая конференция «Безопасность, эффективность и экономика атомной энергетики». Москва, 2010,- С. 153-156.

69. Мину М. Математическое программирование: теория и алгоритмы. — Москва : Наука, 1990.

70. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — Москва : Мир, 1984.

71. Параллельная реализация метода динамического программирования в обобщенной задаче курьера / А. М. Григорьев, Е. Е. Иванко, П. А. Ченцов, А. Г. Ченцов // Труды международной суперкомпьютерной конференции «Научный сервис в сети Интернет: поиск новых решений». — Абрау-Дюрсо, 2012. — С. 315-319.

72. Перекатов А. Е., Чикрий А. А. Поочередное преследование по позиции // Автомат, и телемех. - 1993. - Аз 10. - С. 86-95.

73. Петров Н. Н. Об одной задаче преследования группы убегающих // Автомат, и телемех. - 1996. — № 6. — С. 48-54.

74. Петров Н. Н. К нестационарной задаче группового преследования с фазовыми ограничениями // МТИП. - 2010. - Т. 2, № 4. С. 74-83.

75. Петров Н. Н., Соловьева Н. А. Групповое преследование в рекуррентных дифференциальных играх // Изв. ИМИ УдГУ. - 2012. — № 1. — С. 99-100.

76. Понтрягин Л. С. Избранные научные труды. Том 2. Оптимальное управление.— Москва : Наука, 1986.

77. Реконфигурируемые мульти-конвейерные вычислительные структуры / И. А. Каляев, И. И. Левин, Е. А. Семерников, В. И. Шмойлов. — Ростов-на-Дону : ЮНЦ РАН, 2008.

78. Сабирянова К. Г., Ченцов А. Г. Динамическое программирование в задаче оптимизации покрытия // Автомат, и телемех. — 1994. — А2 3. — С. 54-64.

79. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации. — Киев : Наукова думка. 1988.

80. Сергиенко И. В., Козерацкая Л. Н., Лебедева Т. Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач, — Киев : Наук, дум., 1995.

81. Сергиенко И. В., Семенова Н. В. Задачи целочисленного программирования с неоднозначно заданными данными: точные и приближенные решения // Кибернетика и системный анализ. — 1995. — 6. — С. 75-86.

82. Сергиенко Т. И. Об устойчивости по ограничениям многокритериальной задачи целочисленного программирования // Доклады АН УССР.- 1989.— Т. А, № 3.— С. 79-81.

83. Сесекин А. Н., Ченцов А. А., Ченцов А. Г. Задачи маршрутизации с ограничениями, ориентированные на применение в атомной энергетике // Материалы конференции «Дискретная оптимизация и исследование операций». — Новосибирск, 2010. — С. 154.

84. Сесекин А. Н., Ченцов А. А., Ченцов А. Г. Об одной задаче маршрутизации «на узкие места» // Тр. ИММ УрО РАН. - 2010. - Т. 16, № 1. - С. 152 170.

85. Сесекин А. Н., Ченцов А. Г. Метод динамического программирования в задаче коммивояжера. — Екатеринбург : УГТУ- УПИ, 2005.

86. Сигал И. X., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. — Москва : Физматлит, 2007.

87. Сихарулидзе Г. Г. Об одном обобщении задачи коммивояжера // Автоматика и Телемеханика. - 1971. — № 8. — С. 116-123.

88. Субботин А. И., Субботина Н. Н. К вопросу обоснования метода динамического программирования в задаче оптимального управления // Изв. АН СССР. Техн. кибернетика. - 1983. - № 2. - С. 24-32.

89. Субботин А. И., Ченцов А. Г. Оптимизация гарантии в задачах управления,— Москва : Наука, 1981.

90. Ташлыков О. J1. Дозовые затраты персонала в атомной энергетике. Анализ. Пути снижения. Оптимизация. - LAP LAMBERT Academic Publishing, 2011.

91. Ченцов А. Г. Обобщенные множества притяжения и приближенные решения, их формирующие /'/ Тр. ИММ УрО РАН. - 2004. - Т. 10, № 2. - С. 178-196.

92. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. — Москва : РХД, 2007.

93. Ченцов А. Г., Ченцов П. А. Динамическое программирование в задаче оптимизации разбиений // Автоматика и телемеханика. — 2002. — Т. 68, № 5. — С. 133 146.

94. Черноусько Ф. Л. Динамическое программирование // Соросовский образовательный журнал. — 1998. — № 2. - С. 139-144.

95. Чикрий А. А., Калашников С. Ф. Преследование управляемым объектом группы убегающих // Кибернетика. — 1987. — N2 4,— С. 1-8.

96. Archetti С., Bertazzi L., Speranza М. G. Reoptimizing the traveling salesman problem // Networks. — 2003. — Vol. 42, no. 3. — P. 154-159.

97. Ausiello G., Becchetti L. On-Line Algorithms // Paradigms of Combinatorial Optimization. - John Wiley and Sons, Inc., 2014. — P. 473-509. - ISBN: 9781119005353. - URL: http://dx.doi.org/10.1002/9781119005353.chl5.

98. Balas E., Fischetti F., Pulleyblank W. R. The precedence-constrained asymmetric traveling salesman polytope // Math. Program. Ser. — 1995. — Vol. 68. - P. 241-265.

99. Bartholdi J. J., Platzrnan L. K. An o(n logn) planar travelling salesman heuristic based on spacefilling curves // Operations Research Letters.— 1982. — Vol. 1, no. 4. — P. 121-125.

100. B.Efron. Bootstrap methods: Another look at the jackknife // The Annals of Statistics. — 1979. - Vol. 7, no. 1. P. 1-26.

101. Behzad A., Modarrcs M. A new efficient transformation of the generalized traveling salesman problem into traveling salesman problem // Proc. of the 15th Intl. Conf. of Systems Engineering (ICSE). — Las Vegas, 2002.

102. Bellman R. Dynamic programming treatment of the travelling salesman problem // J. Assoc. Comput. Mach.— 1962, — no. 9,- P. 61-63.

103. Berdyshev Y. I. A problem of the sequential approach to the group of moving points by third order non-linear control system // J. Appl. Math. Mechs. — 2002.— Vol. 66, no. 5. - P. 709-718.

104. Berg Т., Hempel H. Reoptimization of traveling salesperson problems: Changing single edge-weights // In Proceedings of the 3rd International Conference on Language and Automata Theory and Applications. — 2009.— P. 141-151.

105. Bertsimas D., Grigni M. On the spacefilling curve heuristic for the euclidean traveling salesman problem // Operations Research Letters. — 1989. — Vol. 8, no. 5. — P. 241-244.

106. Bertsimas D., Jaillet P., Odoni A. On the spacefilling curve heuristic for the euclidean traveling salesman problem // Operations Research Letters. — 1990.— Vol. 38, no. 6.— P. 1019 -1033.

107. Bockenhauer H.-J., Komra D. Reoptimization of the metric deadline tsp //J. Discrete Algorithms. - 2010. — Vol. 8, no. 1. - P. 87-100.

108. Bubeck S. Introduction to online optimization. — 2011. — URL: http://www.princeton. edu/~sbubeck/BubeckLectureNotes .pdf (online; accessed: 15.12.2014).

109. Buchbinder N., Naor J. The design of competitive online algorithms via a primal-dual approach // Foundations and Trends in Theoretical Computer Science. — 2009. — Vol. 3, no. 2-3. — P. 93-263.

110. Burkard R., Dell'Amico M., Martello S. Assignment Problems. — Philadelphia : SIAM, 2009.

111. C. Hanson J. Richardson A. G. Path planning of a dubins vehicle for sequential target observation with ranged sensors // Proceedings of American Control Conference. — 2011. P. 1698-1703.

112. Campbell L. Historical Linguistics: An Introduction. — Edinburgh University Press, 2004.

113. Casti J., Richardson M., Larson R. Dynamic programming and parallel computers //J. of optimization theory and applications. — 1973. Vol. 12, no. 4. — P. 423-438.

114. Chin F., Houck D. Algorithms for updating minimum spanning trees // Journal of Computing and System Sciences. - 1978. — Vol. 16. — P. 333-344.

115. Deineko V. G., Rudolf R., Woeginger G. J. Sometimes travelling is easy: the master tour problem // J. Discrete Math. - 1998. — Vol. 11, no. 1. P. 81-93.

116. Demetrescu C., Italiano G. F. A new approach to dynamic all pairs shortest paths // In J. ACM. - 2004. - Vol. 51. P. 968- 992.

117. Dubins L. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents // American Journal of Mathematics. - 1957. — Vol. 79, no. 3. — P. 497 516.

118. Escoffier B., Ausiello G., Bonifaei V. Complexity and approximation in reoptimization // Computability in context: Computation and Logic in the Real World. — Imperial College Press, 2011.

119. A fast and scalable radiation hybrid map construction and integration strategy / R. Agar-wala, D. L. Applegate, D. Maglott, G. D. Schuler // Genome Research. — 2000. — no. 10. — P. 350-364.

120. Gengler M. An introduction to parallel dynamic programming // Lecture Notes in Computer Science. - 1996. - Vol. 1054. — P. 87-114.

121. Gutin G., Punnen A. P. The Traveling Salesman Problem and Its Variations. — Dordrecht : Springer, 2002.

122. Iladamard J. Sur les problemes aux derivees partielles et leur signification physique // Princeton University Bulletin. — 1902. — P. 49-52.

123. Held M., Karp R. M. A dynamic programming approach to sequencing problems // Journal of the Society for Industrial and Applied Mathematics.— 1962.— Vol. 10, no. 1.— P. 196-210.

124. Improved lower bounds for the universal and a priori tsp / I. Gorodezky, R. Kleinberg, D. Shmoys, G. Spencer // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. - Springer Berlin Heidelberg, 2010. — Vol. 6302 of Lecture Notes in Computer Science. — P. 178-191.

125. Ivanko E. Adaptive stability in graph placement problem // Proceedings of the 14th International Conference on Mathematical Methods in Science and Engineering (CMMSE-2014). - Vol. 3. — Rota, Spain, 2014. — P. 739 - 742.

126. Ivanko E. E. Gtsp approach to sequential control problem // Abstract book of 26th international conference on operational research. — Rome, 2013. — P. 91.

127. Ivanko E. E. On one approach to tsp structural stability // Advances in Operations Research.— 2014. 8 pages.— URL: http://www.hindawi.com/journals/aor/2014/ 397025/.

128. Jaillet P., Wagner M. Online vehicle routing problems: A survey // The Vehicle Routing Problem: Latest Advances and New Challenges / Ed. by Bruce Golden, S. Raghavan, Edward Wasil. — Springer US, 2008. — Vol. 43 of Operations Research/Computer Science Interfaces. — P. 221-237.

129. Jain A. K., Murthy M. N., Flynn P. J. Data Clustering: A Review. — ACM Computing Reviews, 1999.

130. Johnson D., McGeoch L., Rothberg E. Asymptotic experimental analysis for the held-karp traveling salesman bound // Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms. — Atlanta, Georgia, 1996. — P. 341-350.

131. J.Tukey. Bias and confidence in not-quite large samples // Annals of Mathematical Statistics. - 1958. - Vol. 29. - P. 614.

132. Kalmanson K. Edgeconvex circuits and the traveling salesman problem // Canadian Journal of Mathematics. - 1975. - Vol. 27, no. 5. — P. 1000-1010.

133. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. — Springer Verlag, 2005.

134. King V. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs //In Proc. 40th IEEE Symposium on Foundations of Computer Science. - 1999. - P. 81-91.

135. Korf R. E. A complete anytime algorithm for number partitioning // Journal of Computer and System Sciences. — 1998. Vol. 106, no. 2. - P. 181 203.

136. Kuhn H. The hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. - no. 2. - P. 83-97.

137. Land A. H., Doig A. G. An automatic method of solving discrete programming problems // Econometrica. — 1960. — Vol. 28. - P. 497-520.

138. Libura M. Sensitivity analysis for minimum hamiltonian path and travelling salesman problems // Discrete Applied Mathematics. — 1991.— Vol. 30.- P. 197-211.

139. Libura M. Optimality conditions and sensitivity analysis for combinatorial optimization problems // Control and Cybernetics. — 1996. — no. 25. - P. 1165-1180.

140. A minimal technology routing system for meals on wheels / J. Bartholdi, L. Platzinan, R. L. Collins, W. II. Warden // Interfaces. - 1983.- Vol. 13, no. 3. — P. 1-8.

141. Nilsson C. Heuristics for the traveling salesman problem // Technical Report / Linkoping University. — 2003.

142. Padberg M., Rinaldi G. Optimization of a 532-city symmetric traveling salesman problem by branch and cut // Operations Research. — 1987.— Vol. 6, no. 1. — P. 1 7.

143. Papadimitriou C. Computation complexity. — San Diego : University of California, 1994.

144. Papadimitriou C., Yannakakis M. Optimization, approximation and complexity classes // Journal of Computer and System Sciences. — 1991. — Vol. 43. - P. 425-440.

145. Pesvaradi T. Optimal horizontal quidance law for aircraft in the terminal area // IEEE Trans. Automat. Control. - 1972. - Vol. A17, no. 6, — P. 763-772.

146. Platzman L., Bartholdi J. Spacefilling curves and the planar travelling salesman problem // J. ACM. - 1989. — Vol. 36, no. 4. - P. 719 737.

147. Poort E. S. Aspects of sensitivity analysis for the traveling salesman problem : Ph.D. thesis / E. S. Poort ; University of Groningen. — 1997.

148. Proof verication and hardness of approximation problems / S. Arora, C. Lund, R. Motwani et al. // Proceedings of 33rd Annual Symposium on Foundations of Computer Science. — 1992. - P. 14-23.

149. Psaraftis H. N. A dynamic programming solution to the single-vehicle many to-many immediate request dial-a-ride problem // Transport. Science. — 1980. — Vol. 14. — P. 130 154.

150. A radiation hybrid transcript may of the mouse genome / P. Avner, T. Bruls, I. Poras, L. Eley // Nature Genetics. - 2001. - no. 29.- P. 194 200.

151. Renaud J., Boctor F. F., Ouenniche J. A heuristic for the pickup and delivery traveling salesman problem // Computers & Operations Research. — 2000. — no. 27. — P. 905-916.

152. Reoptimization of minimum and maximum traveling salesman's tours / G. Ausiello, B. Es-coffier, J. Monnot, V. T. Paschos // In Journal of Discrete Algorithms. — 2009. — Vol. 7. — P. 453-463.

153. Reusing optimal tsp solutions for locally modified input instances / H.-J. Bockenliauer. L. Forlizzi, J. Hromkovic et al. // In Fourth IFIP International Conference on Theoretical Computer Science—TCS. - 2006. — P. 251-270.

154. Sadecki J. Parallel dynamic programming algorithms: multitransputer systems // Int. J. Appl. Math. Comput. Sci. — 2002. - Vol. 12, no. 2. - P. 241-255.

155. Schaffter M. W. Scheduling with forbidden sets // Discrete Applied Mathematics.— 1997. - Vol. 72. - P. 155-166.

156. Schalekamp F., Shmoys D. Algorithms for the universal and a priori tsp // Oper. Res. Lett. - 2008. - Vol. 36, no. 1. - P. 1-3.

157. Schrijver A. Combinatorial Optimization. — Berlin : Springer, 2003. — Vol. A.

158. Shalev-Shwartz S. Online learning and online convex optimization // Foundations and Trends in Machine Learning. — 2012. — Vol. 4, no. 2. - P. 107-194.

159. Shmoys D., Talwar K. A constant approximation algorithm for the a priori traveling salesman problem // LNCS. - 2008. - Vol. 5035. - P. 331-343.

160. Sotscov Y. N., Leontev V. K., Gordeev E. Some concepts of stability analysis in combinatorial optimization // Discrete Applied Mathematics. — 1995. — Vol. 58. P. 169-190.

161. Spira P. M., Pan P. On finding and updating shortest paths and spanning trees // In Proceedings of the 14th Annual Symposium on Switching and Automata Theory. — 1973. -P. 82-84.

162. Stability aspects of the traveling salesman problem based on k-best solutions / M. Libura, E. S. Poort, G. Sierksma, J. A. Veen // Discr. Appl. Math. - 1998. - Vol. 87. - P. 159 185.

163. A theoretical framework of hybrid approaches to max-sat / T. Asano, K. Hori, T. Ono, T. Hirata // Algorithms and Computation.— Springer Berlin Heidelberg, 1997. -Vol. 1350 of Lecture Notes in Computer Science. — P. 153-162.

164. Tsp. scan chain optimization.— 2005.— URL: http://www.tsp.gatech.edu/apps/ scan.html (online; accessed: 04.10.2012).

165. Valenzuela C., Jones A. Estimating the held-karp lower bound for the geometric tsp // European Journal of Operational Research. — 1997. — Vol. 102, no. 1. — P. 157-175.

Приложение А Таксономическое дерево языков

борейская

н о с т р а т и ч е с к а я афразийская египетский

египетский

египетский западпосемитская иврит

иврит центральносемитская арабский южносемитская эфиопская

амхарский

чадская

западночадская хауса индоевропейские

греко-армянская греческая

греческий армянская

армянский балто-славянская славянская

болгарский русский сербский балтийская

латышский арийская

индоарийская хинди

бенгальский маратхи сингальский иранская

персидский курдский италийская

латино-фалискская испанский итальянский французский германская

западногерманская английский немецкий северогерманская норвежский

уральские

фино-угорская угорская

венгерский хантыйский мансийский фино-пермская финский удмуртский коми самодийская

северная

ненецкий нганасанский

алтайские

тюркская

кыпчакская

казахский якутская

якутский горно- алтайская

алтайский саянская

тувинский монгольская

северомонгольская бурятский монгольский японо-рюкюсская японская

японский корейская

корейская

корейский дравидийская

южно-дравидийская тамил о-капнадская тамильский малаялам

с т р и ч е с к а я австроазиатская мон-кхмерская

вьетская

вьетнамский австронезийская

малайско-полинезийская надветвь калимаитанская зона

малагасийский западнозондская малайский индонезийский восточно-малайско-полинезийская маори

центральнофилиппипская филиппинский пама-ньюнга

пама-ньюнга

пама-ныонга тай-кадайская тайская

тайская

тайский

сино-кавказская сино-тибетские

лоло-бирманская бирманская

бирманский китайские

китайские

китайский

баскский

баскский

баскский

баскский северокавказский дагестанский

дагестанский

дагестанский

нигеро-конголезская

нигеро-сахарская бенуэ-конголезская вольта-нигерские эдоидные эдо дефоидная

йорубоидные йоруба бантоидная банту

суахили

банту

сесото

койсанские

н а м а нама

нама

нама

нама

ин до- тихоокеанские

папуасский папуасский

папуасский

папуасский

папуасский

чукотский

чукотский

чукото-камчатская чукото-корякская чукотский

чукотский

289

ЧУ