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

Федеральное государственное бюджетное учреждение науки Институт математики и механики им. H.H. Красовского Уральского отделения Российской академии наук

На правах рукописи

Иванко Евгений Евгеньевич

Маршрутно-распределительные задачи: теория и приложения

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

3 О PFH Z015

005562834

Екатеринбург - 21)15

005562834

Работа выполнена в отделе управляемых систем ФГБУН Институт математики и механики им. H.H. Красовского Уральского отделения РАН (ИММ УрО РАН).

Научный консультант: доктор физико-математических наук, профессор, член-

корреспондент РАН, главный научный сотрудник ИММ УрО РАН Ченцов Александр Георгиевич;

Официальные оппоненты: Колоколов Александр Александрович, доктор физико-

математических наук, профессор, заведующий лабораторией дискретной оптимизации Омского филиала Института математики СО РАН, г. Омск;

Петров Николай Никандрович, доктор физико-математических наук, профессор, заведующий кафедрой дифференциальных уравнений ФГБОУ ВПО Удмуртский государственный университет, г. Ижевск;

Горнов Александр Юрьевич, доктор технических наук, главный научный сотрудник лаборатории оптимального управления Института динамики систем и теории управления СО РАН, г. Иркутск.

Ведущая организация: ФГБОУ ВПО Южно-Уральский Государственный Университет, г. Челябинск

Защита состоится 14 октября 2015 г. в 11 часов на заседании диссертационного совета Д 004.006.04 при ИММ УрО РАН, расположенном по адресу. 620990, г. Екатеринбург, ул. С.Ковалевской 16.

С диссертацией можно ознакомиться в библиотеке ИММ УрО РАН и на сайте ИММ УрО РАН http://vnvwrus.imm.uran.ru/C16/Diss/defauIt.aspx.

Автореферат разослан 10 сентября 2015 г.

Ученый секретарь диссертационного совета,

доктор фпз.-мат. наук.

Скарин Владимир Дмитриевич

Общая характеристика работы

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

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

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

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

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

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

Цель диссертационной работы состоит в исследовании методов ре-

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

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

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

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

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

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

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

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

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

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

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

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

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

в процессе перевозки грузов ситуация часто изменяется.

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

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

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

Исследования рассматриваемых в диссертации задач проводились при поддержке грантов РНФ 14-11-00109, РФФИ 10-01-96020-р-урал-а, 10-08-484-а, 11-01-90432-У кр-ф-а, 13-04-847а, 13-01-90414-Укр-ф-а, 13-08-643а, 13-01-96022-р-урал-а, 14-08-00419; региональных целевых программ УрО РАН 13П1, 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; международной конференции Алгоритмический анализ неустойчивых задач (ААНЗ-2014), Челябинск, 2014.

Кроме того, результат!,[ диссертации докладывались на: расширенном семинаре лаборатории дискретных экстремальных задач ИМ СО РАН; семинаре сектора математических методов распознавания и прогнозирования отдела математических проблем распознавания и методов комбинаторного анализа

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

Публикации. Материалы диссертации опубликованы в 28 печатных работах, из них одна монография [1|, 13 статей в рецензируемых журналах [2-14], 1 статья в сборнике трудов [17], 13 публикаций в сборниках материалов конференций [15, 1С, 18-28].

Личный вклад автора. Все выносимые на защиту результаты получены лично автором за исключением вспомогательных результатов, используемых в доказательствах, которые приводятся в тексте диссертации для полноты изложения и специально отмечены. В работах [2, 4, 8, 18, 19, 21-23] А.Г. Ченцову принадлежат постановки задач, общая схема исследования и некоторые идеи доказательств; А.М. Григорьеву и П.А. Ченцову принадлежит программная реализация и проведение вычислительных экспериментов; С.Т. Князеву принадлежит обзор возможных приложений; конкретные доказательства основных положений, разработка алгоритмов и оценка их трудоемкости проведены автором диссертации самостоятельно.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 5 глав, заключения, библиографии и 1 приложения. 0610

щий объем диссертации 289 страниц, включая 52 рисунка и 15 таблиц. Библиография включает 165 наименований на 16 страницах.

Содержание работы

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

Первая глава начинается с формулировки МРЗ в общем виде (раздел 1.1) и ее частных случаев: ЗК (раздел 1.2) и РЗ (раздел 1.3). Для каждой из частных задач приводятся постановки в терминах линейного целочисленного программирования, а также схемы динамического программирования. В разделе 1.4 излагается общий подход МДП в дискретных задачах, включая краткое обсуждение вычислительных аспектов реализации данного метода на современных многопроцессорных компьютерах. Раздел 1.5 посвящен обзору непрерывных маршрутных и маршрутно-распределительных задач (задач последовательного управления), связанных с движением управляемой системы, описываемой дифференциальными уравнениями. Завершается глава I двумя разделами, посвященными устойчивости в задачах комбинаторной оптимизации. В разделе 1.6 проводится краткий обзор существующих подходов к устойчивости. Раздел 1.7 посвящен описанию предложенной автором схемы исследования адаптивной устойчивости и ее возможных приложений. Рассмотрим последний раздел подробнее.

Пусть X ф 0, |Х| < оо — множество допустимых начальных данных ЗКО а М. ф 0, \ЛЛ\ < оо множество допустимых состояний (решений) этой задачи, реализующихся на всевозможных начальных данных из X. Зафиксируем исходное множество начальных данных А С X, возмущенное

множество начальных данных А* С X и соответствующие этим множествам множества состояний Ма С Л4 и Мл- С Л4. Ранее в [1, 3, 5, б, 9, 15, 20, 21, 25] рассматривались А' е {А е Р'(Х) \ {А ф 0) к. (Зг е Х\ А,Зх е А: А £ {Аи{л},Л\{х}, (Л\{х})и{г}})}. Фиксированное А* далее будем называть просто возмущением.

На М. зададим функцию стоимости £>: М. —> Е. Пусть далее для В е {А, А'} Nв — Аг£гшп„сЛ/п О (а) есть множество оптимальных состояний, реализующихся на начальных данных В. Учитывая выбор А, Б, X, далее будем писать 2 = £), X). Решением ЗКО £>, X) будем считать нахождение хотя бы одного ао £ Л/д и определение О(оа).

Введем понятие адаптивной устойчивости. Обычно Ма П Ма- = 0, а значит и Nа П Лга- = 0■ Для задачи £), X) и возмущения А" с X зафиксируем мультифункцию А: Ма —> Т-"(МА-)- Избегая роста в

прикладных задачах следует предполагать Уа 6 Ма |-А(а)| < | Л|. Мультифункцию А далее будем называть адаптирующей функцией.

Определение 1. Оптимальное состояние ао € АГа будем считать адаптивно устойчивым или А-устойчивым к возмущению А*, если *4(ао) П

Аф 0-

Далее для ЗКО, обладающих определенной структурой, строится единая схема исследования адаптивной устойчивости. Рассмотрим требования к структуре £(А, £), X). Пусть ¿7 ф 0, \0\ < оо — множество, элементы кото-

оо

рого далее будем называть структурными частями; пусть С = У О1 есть

¿=1

множество, элементы которого далее назовем представлениями, пусть, наконец, задана функция в: С —>■ Л4. Для любого а € Л4 всякое представление V е б'Ч0') с ^ имеет вид V = (вь..., € Яп, где п е N.

Возмущению А" С X поставим в соответствие непустое множество структурных частей Оа- С элементы которого далее будем называть допусти-

мыми по возмущению А'. Введем: 1) функцию, количественно отражающую влияние возмущения А —> А* на структурные части loe: Q —» К; 2) вспомогательную функцию glob: Q х М. М; и 3) «объединяющую» функцию F: R2 —> К, монотонную по первому аргументу (далее это условие будем называть Ml).

Определим специальное отношение между структурными частями и состояниями для обозначения случая, когда структурная часть «участвует в записи» представления состояния: для s € &,а & Л4 будем писать sha, если Зи = (sb...,sfc) £ а), где к £ N и Зг els¿ = з. Для В £ {А, А'} определим множество M¡¡ = {a £ Mb'- s 1- a}, Mb Ф 0-

Для формулировки критерия адаптивной устойчивости также потребуется функция Glob(s): Q —> R, где Vs £ Q Glob(s) = пппаел/д globus, a).

Пусть Ga — {s £ G I 3a £ Мл'■ s I- a},G,\ ф 0 есть множество структурных частей, «реализующихся» на начальных данных Л, то есть «участвующих в записи» хотя бы одного представления хотя бы одного состояния из Мл- Введем множество Сгд — Gл П Qл* и потребуем вновь G'\ Ф 0.

Условие расщепления. Рассмотрим ключевое для доказательства следующих ниже Теорем 1,2 условие расщепления, состоящее из двух частей:

1) будем полагать определенной функцию dis: G^ х Мл —> Мл- такую, что Vs £ Va £ А/д D(dis(s,a)) = F(glob(s,a),loc(s)), если a £ А/Д и D(dis(s,a)) = 0, иначе;

2) будем предполагать, что функция dis сюрпективна\/а* £ А/д- 3s £ G'X 3a £ А/Д: a* = dis(.s, a).

С помощью функции dis формализуем адаптирующую мультифункцию

Определение 2. В задаче Z(A, D, X) при возмущении А" С X для всякого п £ А/д Д(а) 4 {а' £ Д/д. | 3s £ G;¡': (s b a)fc(o* = dis(.s,«))}.

Введем, наконец, мультифункцию Р: G¿ х Мд —> Ga, где P(s, а) = {s £ Gf I F(glob(s, a), loc(s)) > F(glob(s, a), loc(s))}, если a e M% и P(J, a) = 0, если а € Ma \ M%-

Следующее условие, которое будем предполагать выполненным и использовать только в пределах Теоремы 1, назовем М2: Vs 6 G¿' Va,ß € Ma (D(a) < D{ß) =>■ glob(s,a) < glob(s,ß)). Отметим, что в большинстве содержательных задач glob(s,a) = 0(a), а в таком случае М2 тривиально.

Теорема 1. Пусть задана ЗКО Z(A, D, X), возмущение А* С X, структурная часть So € Gд" и оптимальное на Ма состояние £*о G МД0. Для того, чтобы состояние dis(so, ао) было оптимальным на Ма- необходимо и достаточно выполнение равенства D(dis(so,ao)) = min [F(Glob(s),loc(s))].

seP(so,ao)

Отметим, что если приведенный в Теореме 1 критерий применяется для проверки устойчивости целой серии непоследовательных возмущений (например, при численном построении областей адаптивной устойчивости [1]), то целесообразно заменить P(so,ao) на G'X■

Для формулировки достаточного условия адаптивной устойчивости в дополнение к Ml и вместо М2 введем условиеМЗ: VA с X, Va, ß € Ма, Vsi, s2 € Ga ■ si b a,s2 b ß (D(a) < D(ß)) (glob{s\,a) < glob{s2, ß)); а также условие M4: Ухих2,уиу2 G К ((orí < x2)k{yx < у2)) => F(xuyi) < F(x2,y2).

Теорема 2. Пусть задана ЗКО Z(A, D, X), возлщщение А* С X, структурная часть So € G¿ и оптимальное на Ма состояние ао € Тогда

состояние dis(so, ао) оптимально на Ма-, если loc(sa) = min loc(s).

seGi'

Прикладной интерес при применении условий Теорем 1 и 2 представляет случай, когда число структурных частей G'{ , с помощью которых «реализуются» состояния Ма, «мало»: |С?4*| << |Л/д|. В NP-трудных ЗКО множество состояний «не менее», чем экспоненциально зависит от мощности множества

входных данных |Л|, а значит предложенные в Теоремах 1 и 2 условия адаптивной устойчивости для таких задач эффективны в прикладном отношении в случае, когда мощность множества структурных частей полиномиально зависит от |Л|. Примером такой задачи служит ЗК, где |Л|! маршрутов реализуются за счет комбинирования |Л|2 ребер, при этом проверка достаточного условия Теоремы 2 обладает полиномиальной трудоемкостью [1, 3, 5|.

Необходимые условия адаптивной устойчивости в ЗКО, удовлетворяющих принципу Беллмана, строятся в весьма общем виде: если некоторый «участок» оптимального состояния не позволяет адаптации к заданному возмущению, то адаптивной устойчивостью к тому же возмущению не будет обладать и все состояние. В зависимости от «размера участка» изменяется и трудоемкость проверки таких условий, варьируясь от константной до трудоемкости решения исходной ЗКО [1, 21].

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

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

Определение 3. Областью адаптивной устойчивости оптимального состояния е*о Е Na при добавлении элемента z Е X \ А будем называть множество О(а0) = {z Е X \ А | А(а0) П ф 0}.

Предложение 1. Пусть задана весовая функция р: X —»• К, определяющая значимость» элементов «потенциальных» начальных данных (например, вероятность появления в будущем), тогда следует предпочесть

Qo G Argmax ^^ р(х)-

Построение О(а), как правило, связано с существенными вычислительными затратами, зачастую превосходящими затраты на решение исходной ЗКО. Для оптимизации трудоемких вычислений удобно использовать теорию, развитую в разделе 1.7.1, главах II и III, а также в ряде работ, например,

[1, ю].

Во второй главе рассматривается понятие адаптивной устойчивости в ЗК при изменении множества посещаемых вершин. В разделе II.1 вводятся базовые обозначения, необходимые для формулировки и дальнейшего исследования ЗК. Рассмотрим множество X, X ф 0 и функцию: d : X х X —>■ К. Пусть далее S = {ai,..., ап} с X (далее везде полагаем п = |S|), которое мы будем называть далее исходным множеством вершин. В S зафиксированы различные: s — вершина старта и i — вершина финиша (в связи с чем считаем |5| > 2). Без ограничения общности считаем, что s = a,\,t = ап. Пусть G(n) = {7 : 1, п 1, п | 7(1) = 1,7(п) = гг}, тогда введем множество маршрутов M'(S) = M£(S) 4 {(a,(1),... ,a,(n)): 7 € G(n)} С X", где n = |S| и согласно определению а^ = ai = s; a7(n) = an = t. Длину всякого маршрута а = (bi,...,bn) Е Mls(S) зададим функцией D(а) = Y11=i d{bi,bi+l). Все маршруты a<) Е Л/'(5), длина которых совпадает с minae.\/i(s) D(a) будем называть оптимальными на Л/](5).

Введем операции вставки, удаления и перемещения одной вершины в маршруте. При этом sut остаются неизменными. Пусть а = (bi,... ,bn) G Mç(S), где п — |5|, i G l,n — 1 и г £ X \ S, тогда Ins (z, i, (b\,..., bn)) = (bi,..., bi, z, 6l+i,... ,bn) G A/j(S'U{z}). Если для оптимального ao = (61,... ,bn) € Mj(5) и добавляемого элемента z E X \ S найдется г о G l,n — 1 такой, что маршрут Ins(z,io,ao) G Ms'(5 U {z}) - оптимален, будем говорить, что элемент г может быть устойчиво добавлен к маршруту ao. Аналогично введем Del(i,(bl,...,bi-1,bi,bi+l,...,bn)) 4 (Ьь ... Л-ьЪ+ь • • • А) e Ml(S \ {Ь,-}). Если для оптимального ao = (bi,... ,bn) G и удаляемой позиции

i G 2, n — 1 маршрут Del(i,a0) G \ {&,}) - оптимален, будем гово-

рить, что элемент bi может быть устойчиво удален из маршрута ao. Наконец,

Moi>(z,i,(6i,... A_iAbi+1,... А)) - (Ьь...Л-ь-гЛ+ъ---A) G Mls(S\

{öj} U {2}). Если для оптимального маршрута ao = (61,..., bn) G Mj(5), замещаемой позиции г Е 2, тг — 1 и замещающего элемента z E X \ S маршрут Mov(z,i,a0) G Mj((5\{6i})u{z}) - оптимален, будем говорить, что вершина bi может быть устойчиво замещена на элемент 2 в маршруте ao-

Определим 5* ^ {(х,у) E 52\{(s,i)} | (х ф у) & (х ф t) & {у ф s)} и (5\ {z})* = S*\{(x, у) | z G (ж, у}} Vz G S\{s,t} и введем удобные обозначения для длин измененных маршрутов. Пусть a = (61,...,bn) G Mj(5), тогда Vz G X \ 5, Vi G l,n- 1 D(Ins(z,i,a)) = D{a) + A/(z, bh 6i+1), где Vw G X \ S, V(x,y) G 5* A¡(w,x,y) = d(x,w) + d(w,y) — d(x,y). Аналогично Vî G 2, n — 1 D(Del(i, a)) = D(a) + AD(bi; Ь;_ь 6i+1), где V(x, y) G S', Vu G S \ {x,y,s,t} Ad(w,x, y) = d(x,y) — d(x,v) — d(v,y). Наконец, Vz € X \ 5, Vi G 2, n — 1 D(Mov(z, i, a)) = D(a) + A,u(z, Ь,-, 6г_ь 61+1), где Vw E X \ S, V(x, y) G 5*, Vu G 5 \ {.t, y, s,i} Ад¡(w,v,x,y) = d(x,w) + d(iu,y) — d(x,v) —d(v,y). Операцию перемещения можно представить как композицию операций удаления существующей и вставки в маршрут новой вершины.

Определение 4. Областью адаптивной устойчивости (ОАУ) оптимального маршрута «о = (¿1,..., Ьп) £ при 1) добавлении элемента будем называть множество 0[{ао) = {г £ X \ 3 | Зг £ 1, |5| — 1: 1пз(г,{,ао) — оптимален на М^(5'и{2})}; 2) удалении элемента — множество Оо(ао) = {х £ 5 I Зг £ 2, |5| - 1: {х — Ьг)&(.Ое/(г, а0) - оптимален па М*(3\{я}))}; 3) замене элемента — множество Ом(г, ао) = {г £ X \ 5 | Моу(г, г, а-д) — оптимален на М^((3 \ {х}) и {-г}))}.

В разделе 11.2.1 на основе принципа Беллмана рассматриваются необходимые условия адаптивной устойчивости в ЗК. Для всякого маршрута (а7(1), ■ - - ,а7(п)) £ М^Б) и пары г,^ £ 1,п, где п = |5|, введем операцию взятия подмаршрута ЗиЬ({^,а) = (а7(ф..., а7(7)) при г < ^ и ¿ш&(г, а) = (а7у),...,а7Й) при г > ].

Пусть ¿"(г,.?', а) - множество всех вершин, находящихся в маршруте а = (а7(!),... ,а7(„)) между г-той и той позициями включительно: 5(г,7, а) = {а1{к) | к £ шт{г,^},шах{г,^}}, тогда ЗиЬ(г^,а) £ Ма^{3^,],а)). Далее без ограничения общности г < j.

Предложение 2. Пусть заданы множество X, функция стоимости с/: X2 —»■ К, исходное множество вершин в С X: 2 < |5| < оо, начальная и конечная вершины (в, £) £ 52, маршрут а = (а7(1), - - -, а7(п)) £ ^(5), тогда если

1) задан произвольный элемент г £ Х\3 и для некоторого ¿о £ 1, п — 1 маршрут а'0 = 1пз(г,^, а) является оптимальным на множестве М13(3 и {г}), то а) О(1пз(г,10,а)) = 0(1пз(г^, а)); б) У],к £ 1 ,тг: ] < ¿о < к маршрут виЬ^, к + 1, ад) оптимален на к, а) и {г});

2) задана произвольная позиция го £ 2, п — 1, маршрут ад = £>е/(г о, а) является оптгшальным на мноэ/сестве {а. (г„)}), тоУ],к £ 1 ,п. ] < ¿о < к маршрут ЗиЬ(3,к — 1,а(,) оптимален на М"^ (3(], к, а) \ {а-^,,)}),"

3) заданы произвольные позиция г'о £ 2, га — 1 и элемент г £ X \ 5,

маршрут ckg = Mov(z,io,a) оптимален na множестве Mls(S \ {a7(¿0)} U {z}), mo Vj,k £ l,n: j < io < к маршрут Sub(j,k,a'0) оптимален na

В разделе II.2.2 рассматриваются алгоритмы, использующиеся для построения областей, содержащих ОАУ (или, иначе, выявление областей «адаптивной неустойчивости»), с помощью приведенных выше необходимых условий и проводится оценка их трудоемкости. В разделе II.2.3 приводятся примеры использования полученных алгоритмов для построения ОАУ и «неустойчивости» для оптимальных маршрутов в ЗК на евклидовой плоскости. Так, при последовательном добавлении новых вершин в области, отмеченные на рис. 1 белым цветом, порядок оптимального обхода изменяется.

В разделе II.3.1 рассматриваются необходимые и достаточные условия адаптивной устойчивости оптимальных маршрутов в ЗК. Для всякой (х, у) £ S* зададим Mls{S,x,y) = {(а7{1),..., а7(п)) е M',(S): ЗА 6 l,n- 1 (х = a7(fc)) & (у = a7(fc+1))}. Далее для всякого S: 2 < |5| < оо с заданными s и í и фиксированной парой (х, у) £ S' введем длину оптимального на Mls(S,x,y) маршрута: D^'f^S) = D(ñ). При фиксированном

z £ S \ {s, í} для всякой упорядоченной пары (х, у) £ (S \ {г})* введем: AfJ(S, х, г, у) = {(а7(1),..., а7(п)) £ Mj(S): ЗА; £ 2^1 (х = а^^) & (z = a-,(к)) & (у = a-)(fc+i))}- Для всякого S: \S\ < оо с заданными s и i, удаляемой вершиной г £ 5\{s, í} и фиксированной парой (х, у) £ (^{z})* введем длину оптимального на MLs(S,x,z,y) маршрута D^'^S) = m'nñ£.í7í(s,i,^.v)

Теорема 3. Пусть заданы множество X, стоимость d: X2 М, исходное множество вершин S С X: 4 < |5| = п < оо, начальная и конечная вершины (s,t) £ S2, оптимальный маршрут а^ £ Mj.(S), тогда

1) для произвольного элемента z £ X\S маршрут Ins(z, i, о0) £ Mg(SU

{z}), где г Е l,n — 1, оптимален тогда и только тогда, когда

D(Ins(z, i, а0)) = min + Д/(г, х, у)); (1)

(х,у)еS' v ' '

2) для произвольного г Е 2, n— 1 маршрут Del(i,a0) Е Mj(5 \ {г}) оптимален тогда и только тогда, когда

D(Del(i, а0)) = min (6^(5) + АD(z, х, у)) ; (2)

(x,y)6(S\{i})' \ > > /

3) для произвольных г 6 2, тг — 1 и z Е X \ S маршрут Mov(z, г, «о) Е Mj((5'\ {a7o(i)}) U {л}) оптимален тогда и только тогда, когда

D(Mov(z,i,a0)) = min u (Ö^(i)'y)(5) + AM(z, alo(i), x, yj) .

Практический интерес полученные в Теореме 3 условия представляют в случае, когда необходимо проверить адаптивную устойчивость для целого множества непоследовательных возмущений (примером такой задачи служит построение ОАУ, см. рисунок 26). В разделе II.3.2 приводятся алгоритмы проверки сформулированных необходимых и достаточных условий в целях построения соответствующих ОАУ, проводится оценка трудоемкости этих алгоритмов, например,

Предложение 3. Верхняя асимптотическая оценка трудоел1Кости алгоритма проверки условия 1 Теоремы 3 для каждого z Е X \ S записывается как 0(гг42п + п2|Х|).

В разделе II.3.3 рассматриваются примеры ОАУ для ЗК на евклидовой плоскости, соответствующих рассмотренным выше необходимым и достаточным условиям (рисунок 26).

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

Теорема 4. Пусть заданы лтоэкество X, функция стоимости d: X2 —>■ К, исходное мноэ/сество вершин S С X: 4 < |5| = п < оо, (s,t) G S2, оптимальный маршрут ао = (Щ,... ,6°) £ Л/'(,5), тогда

1) Vz € X \ S, Vi G 1, п — 1, маршрут Ins(z, г, ао) G Mj(5 U {z}) оптимален, если выполнено условие

A/(z,6-,6-+1)= min A/(z,x, у);

(x,y)eS-

2) Vi G 2,n - 1 Del(i,a0) G Mj(5 \ {6?}) оптимален, если

(Зхо € S\ {i,6°}: Ао{Ь1ъиЛ+х) < min AD(6°,x0, y))V

(i0,y)s(5\{b?})-

(3j/o eS\{s,b»}: Ьо{ЪЪъи,Щ+1) < min Aß(b»,xl№));

(i,y0)6(5\{6?})-

3) для всякого Ь- 6S \ {s, i}, где i G 2,n — 1, и произвольного элемента z G X \ S маршрут Mov(z, г, а0) G Mls((S \ U {z}) оптимален, если

Дл/М?,Ь?_1,Ьй.1)= min Ам(г,Ь°,х,у).

Рассмотренные выше достаточные условия могут использоваться для численного построения ОАУ, однако в некоторых случаях такие области могут быть построены аналитически [5]. В разделе II.4.2 рассматривается пример аналитического построения ОАУ в ЗК на евклидовой плоскости при замене вершины.В разделе II.4.3 приводятся алгоритмы, реализующие полученные достаточные условия для построения соответствующих ОАУ, и проводится оценка трудоемкости этих алгоритмов, например,

Предложение 4. Верхнюю асимптотическую оценку трудоемкости алгоритма проверки ус.говия 1 Теоремы 4 для каждого z G X \ S можно записать как 0(п2|Х|).

В разделе II.4.4 приводятся примеры таких областей устойчивости для оптимальных маршрутов в ЗК на евклидовой плоскости, построенные с помощью условий Теоремы 4 (один из таких примеров приводится на рис. 2а).

В разделе II.5 рассматривается численный метод дискретизации и сведения бесконечномерной задачи последовательного управления к обобщенной ЗК [26], а также обсуждается возможное приложение излагаемой теории адаптивной устойчивости в задачах последовательного управления. В разделе II.6 приводятся примеры, демонстрирующие существенность отличия изучаемой в диссертации адаптивной устойчивости оптимальных маршрутов в ЗК при изменении множества посещаемых вершин от известного понятия устойчивости, связанного с изменением функции веса на ребрах; экспериментально исследуется асимптотика площадей ОАУ в Евклидовой ЗК; демонстрируется

Предложение 5. Если (X, D) - метрическое пространство, то ОАУ в ЗК при добавлении или замене вершины - замкнутые множества.

В третьей главе рассматривается понятие адаптивной устойчивости в РЗ при изменении множества исполняемых заданий. В разделе III-1 вводятся обозначения и формулируется задача РЗ с равносильными исполнителями. Пусть X — конечное множество всех потенциально возможных заданий с фиксированной на подмножествах X функцией трудоемкости: d: V{X) —> К+, где d(0) = 0, а под V{X) традиционно понимается множество всех подмножеств X. Пусть S С X', зададимся числом работников iVeN:l<7V<|5|. Функция d зависит только от подмножества заданий и не зависит от исполнителя. Постановка с равносильными исполнителями характерна, например, для МРЗ [2, 24]. Для любого К С X введем MN(K) = {{KU...,KN} С V{X) | (U?=lKi = К) & (Vi, j е T^N (i -ф j) (К{ П Kj = 0))}.

Всякое а £ Mrv(K) будем называть распределением заданий из К по N работникам. Стоимостью распределения элементов из К среди N работников будем называть функцию D: AI у (К) —» Ж', определяемую как максимум «трудоемкости» по составляющим распределение подмножествам: VAT е N, V/v С X, Vq = {Ки..., I<N) е MN(K) D{a) 4 maxieTjfd(Ki).

Оптимальным распределением заданий из К С X среди N работников будем называть всякое распределение «о Е М^(К), обладающее минимальной на М^(К) стоимостью а?о: D(ao) = minuemn(k) D(a). Далее, считая, что N фиксировано, будем называть такое распределение ао оптимальным на К.

Пусть в X задано исходное множество заданий S. Пусть для всяких zEX\S, а = {Kl, ...,Kn}€ Mn(S), Ki Е а Ins{z, Ки а) 4 (а\ {К{}) U {Ki U {z}} Е Mn(S и {z}), откуда имеем D(Ins(z, Ki,a)) = max{£)(a \ {Ki}),d(Ki U {z})}. Если функция d монотонна (МК С X \/х Е X d(K) < d(K U {а;})), то полученное выражение можно упростить D(Ins(z, Ki, а)) = max{D(a), Если для оптимального а0 = {^i > - • Mn(S)

и добавляемого задания z Е X\S найдется г Е 1, N: {К®,..., Kf U{z},..., KaN} Е M]v(5u{z}) - оптимально, будем говорить, что задание z может быть устойчиво добавлено к распределению ао- Для х Е S через Кх будем обозначать всякое подмножество из S, содержащее задание х. Зададим для всяких х £ S, а = {Ki,..., Кх,..., KN] Е MN(S) Del{x, а) ^ (а \ {/f1}) U {Кх \ {х}} Е Mjv(5\{x}), откуда согласно определению D(Del(x, а)) = max{D(a\ Кх), d(Kx \ {х})}. Если для удаляемого задания х Е S и оптимального ао = {Kl ...,КХ,...,К%} Е MN(S) распределение {К°и ...,КХ\ {х}, ...,К%}е Mn(S\{x}) - оптимально, будем говорить, что задание х может быть устойчиво удалено из распределения ао- Наконец, для всякихх Е S, z Е X\S, а = {KU...,KX,...,KN} Е MN(S) Mov(z, х, а) ^ (a\^)U{(/^\{x})U{z}} £ MN((S \ {х}) и {z}), откуда D(Mov(z,x,a)) = max{D(a \ {Kx}),d{Kx \ {х} U {z})}. Если для оптимального а0 = {К..., Кх,..., /Сдг} Е удаляемого задания х Е S и добавляемого задания z Е X \ S распределение ..., (Кх \ {х}) U {г},..., К%} Е MN{(S \ {х}) U {z}) - оптимально, будем говорить, что задание х может быть устойчиво заменено на задание z в распределении ао- ОАУ оптимального распределения ао = {Ку,..., Км} Е M.\-(S) при 1) добавлении элемента будем называть множе-

ство 0/(с*о) = {z G X \ S | ЭК Е а0: Ins(z, К, ао) — оптимально на U

{л})}; 2) удалении элемента — множество Оо(ао) = {г £ S | Del(x,aо) — оптимально на Л/дг(5\{х})}; 3) замене элемента — множество Om{z, х, с*о) = {гбХ\5| Mov(z, х, а0) — оптимально на Мдг((5 \ {х}) U {.г}))}.

В разделе III.2 рассматриваются необходимые условия адаптивной устойчивости в РЗ. Рассмотрим добавление нового задания к начальным данным. Пусть а = {Ки KN}, тогда J (а) С TJf: (Vj G J{a) d(Kj) = D(a*0)) & (Vj 6 TJÍ\J{a) d(Kj) < D(a'0)).

Предложение 6. Пусть заданы X ф 0, d: V{X) R+, S С X: |S| < oo, N G N: 1 < N < |S|, оптимальное распределение ао = {Ki,..., Kn} € M(N, S) и добавляемое задание z G X \ S, тогда если распределение

a* á: Ins(z, Ki, a0) = {^J,..., K'N}, zdeVj G TjV\{¿} Я] = Kj, a K[ = KiU{z},

оптимально na M(N, Sl^z}), то для всякого подмножества L С 1, TV: J(aJ) С L, распределение a'Q = {/£¿}fceL оптимально tía Мщ{LíkeL^'f.).

Необходимые условия адаптивной устойчивости оптимального распределения в случае удаления и замены задания формулируются и доказываются в том же разделе по аналогии с предложением 6. Отметим, что, чем больше величина L, тем ближе необходимые условия к соответствующим необходимым и достаточным и тем сложнее в вычислительном отношении их проверка. Завершается раздел рассмотрением алгоритмов, реализующих полученные необходимые условия для построения соответствующих областей «адаптивной неустойчивости» и рассмотрением трудоемкости данных алгоритмов.

В разделе III.3 приводятся критерии адаптивной устойчивости оптимального распределения в РЗ. Пусть УК С S Одг.^/^) = miii,ysA/v_,(.s\a:) {£>(»')}.

Теорема 5. Пусть даны непустое множество заданий X, функция трудоемкости d: V{X) —> IR+, начальное множество S С X: |5"| < оо, ко-

личество работников 7VeN:l<Ar<|5|w оптилшлъное распределение ао = {Ki,..., KN} £ Mn(S), тогда

1) для z £ X \ S распределение Ins(z, Ki,ao) при i G l,N является оптимальным na Mn(S U {г}) тогда и только тогда, когда

D(/ns(z, Ki, а0)) = min [тахр^^/С), d(K U {z})}] ;

/С c5

2) для произвольного задапияУх G S распределение Del(x,aо) является оптимальным па множестве Mn(S \ {х}) тогда и только тогда, когда

D(Del(x, а0)) = min [тахр^Д/П, d{Kx \ {х})}] ;

3) для произвольных х G S, z G X \S распределение Mov(z, х, »о) оптимально па Mn((S \ {х}) U {z}) тогда и только тогда, когда

D(Mov{z, х, ао)) = min [max{DsN_i(Kx), d({Kx \ {x}) U {z})}] .

В разделе III.4 в рамках общего подхода Теоремы 2 изучаются достаточные условия адаптивной устойчивости в РЗ. Рассмотрим случай добавления нового задания к распределению.

Теорема 6. Пусть X ф 0, монотонная функция трудоемкостиd: V(X) —»• R+, начальное множество S С X: |5| < оэ, количество исполнителей N G N: 1 < N < |5| и оптимальное распределение ао = {^ь ■ ■ ■ > К^} G Mn(S), тогда для произвольного задания z G X \ S, для всякого i £ I, N распределение Ins(z, Ki, ао) является оптимальным на Mn(SU {z}), если выполняется условие d(Ki U {z}) = min {d(Kz)\

K*csu{z}

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

III.5). В разделе III.6 приводятся алгоритмы, реализующие специфические достаточные условия адаптивной устойчивости, проводится оценка трудоемкости данных алгоритмов, в частности показано

Предложение 7. Верхняя асимптотическая оценка трудоемкости МДП решения ММРЗ может быть записана какО(п222™).

Предложение 8. Верхнюю асимптотическую оценку трудоемкости алгоритма проверки условия 1 Теоремы 5 для всех z £ X \ S можно записать как 0(22nd+d2n\X\+23n), гдеп = |5|, d - максимум трудоемкости расчета d(L U {z}) по всем L £ S, всем z £ X \S.

В разделе III.7 на модельных задачах рассматривается сравнение ОАУ, полученных с помощью простых специфичных для аддитивной РЗ достаточных условий адаптивной устойчивости с областями, полученными с использованием для той же задачи критерия следствия 3. Результаты второй и третьей глав опубликованы в работах [1, 3, 5, С, 9, 15, 20, 21, 23, 24].

В четвертой главе в интересах последующих приложений рассматривается несколько разнородных способов уменьшения трудоемкости МДП в ЗК и РЗ. В разделе IV. 1 проведена оценка эффективности конструктивного использования условий предшествования при реализации схемы МДП в задаче курьера. Сам метод предложен А.Г. Ченцовым.

Предложение 9. Введение одной адресной пары (отправитель-получатель) в ЗК, связанную с посещением п городов, позволяет сократить число операций сравнения в МДП на (п — 2)2"~3.

Раздел IV.2 посвящен исследованию применения «встречного» МДП в ЗК и РЗ. Построение усеченного МДП для симметричных постановок различных задач комбинаторной оптимизации, по-видимому, может вестись по схеме, прослеживающейся на примере двух рассмотренных задач. Для замкнутой ЗК, связанной с обходом элементов множества Xu {х<>} с симметричной

2G

функцией стоимости перемещений d, в разделе IV.2.1 разработана следующая итерационная схема МДП (здесь п = ¡AT U {xo}j, m = \{п — 1)/2] + 1)

Усеченная схема МДП для симметричной ЗК

0) Ух е X vQ(x, 0) = d(x,xо);

1) УК С X: \К\ = 1, УхеХ\К v1(x,K)±mm{d(x,y)+v0(y,K\{y})}-,

m) УК С X: \К\ = т, Ух е X \ К vm(x,K) = min{d(x,y) + vm^i(y, К \ {у})};

уек

т + 1) v' ^ min {vm(y, К) + un_m_i(y, X \ (К U {у}))}.

КсХ: |А'|=т

уеХ\К

Предложение 10. 1) Величина v* совпадает с длиной оптимального замкнутого маршрута обхода элементов X U {хд} в ЗК. 2) Отношение числа операций в полученной схеме к числу операций в классической схеме МДП в ЗК при тг —> оо стремится к 1/2.

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

В разделе IV.2.2 рассматривается аналогичная вариация «встречного» МДП в задаче, связанной с распределением заданий множества X среди N равносильных исполнителей (оригинальный МДП предложен А.Г. Ченцо-

вым). Пусть V = [(ЛГ - 1)/2] + 1.

Усеченная схема МДП для РЗ с равносильными исполнителями 1) VКСХ Уг(К) = ¿(К);

2) \/К С X ь2(К) = <

тт (тах{(1(£),«1(К\Ш, > 2;

¿СК: |£|<[А'|/2 I V ^ V \ П) I I -

\к\ < 2;

V) \/К С X уу{К) = {

Уу^(К), \К\ < V;

Предложение 11. Величина идг(Х) совпадает со стоимостью оптимального распределения заданий из X среди N исполнителей.

Приведенная схема требует меньшего числа операций сравнения, чем классическая схема МДП для РЗ. Так при \Х\ — 14 достигается выигрыш в « 4 раза, а при |Х| = 40 - в и 5 раз.

В разделе IV.3 предложен новый эвристический метод декомпозиции ЗК (в том числе с условиями предшествования) с помощью последовательного применения оригинального алгоритма кластеризации множества вершин ЗК. Пусть задано множество вершин А = {ах,... функция стоимости пере-

мещений <1\ А2 —> М, начальная и конечная вершины «,ебЛ (предполагаем в ф е) и параметр п е К: п > 1. Начальными условиями считаем кортеж ({й}, А\ {я, е}, {е}). Пусть, кроме того, заданы транзитивно замкнутые и совместные условия предшествования Р С А2 (нестрогий порядок) и для всякой а £ Л задано множество «левых» Р,(а) = {а* £ А : (щ,а) £ Р} и «правых» Ре(а) = {а7- £ А : (а, а,) £ Р} вершин. Наконец, пусть задана функция сто-

имости вставки, характеризующая «удаленность» вершины от пары вершин: 5(а, (6, с)) = ¿(6, а) + ¿(а, с) - <¿(6, с).

Алгоритм кластеризации в ЗК

Пока в кортеже ({я}, Хь {гс2}, -.., {а:;}, Хи {^¿+1},..., {хк}, Хк, {е}) существует подмножество X,-: |Хг| > п, применяем к X; описанную ниже функцию ОгорВу({ц},Хг,{х1+1}) = ({х{},Х},{хй},Х?,{хш}), гдеХ/и{х0}иХг2 = Х{ и, следовательно, |Х/| < |Х;|, |Х2| < |Х,|.

Если п = 1, то в результате применения алгоритма получим эвристическое решение задачи. Если п > 1, то в результате итераций шага 2 получим кортеж подмножеств : ({в}, Хь {х2},..., {х*}, X;, {^¿+1},..., {а^}, Хк, {е}), где \/г е 1 ,к |Х*| < п. Всякую упорядоченную тройку X,,

можно считать входными данными для отдельной подзадачи по обходу элементов Х{, с заданной точкой старта х, и точкой финиша Хг+ь По построению |Х,| < п, а значит, при достаточно малом п такую подзадачу можно решить точными методами.

Функция ЮгорВу

1) Вход функции: ({61}, В, {Ь2}), где |В| > 1; 6Ь 62 € А; В С А.

2) Пусть 60 € В: 5(60, (6Ь 62)) = тах1бВ{5(х, (6Ь 62))}.

3) Разделим множество В \ {60} на два подмножества Вх и В2 так, чтобы не нарушить условий предшествования. Для всякого 6 £ В \ {6о}:

а) если (6, 60) € Р, то разместим Р8(Ь) С Вь

б) если (60,6) € Р, то разместим Ре(Ь) С В2;

в) если {(60,6), (6,60)} П Р = 0, то разместим Р3(Ь) С Вх в случае, когда К6о,62)), и Ре(6) С В-2, иначе.

4) Выход функции: ({А}, В\, {60}, В2, {6>}); если какое-либо из подмножеств

В1, £?2 пусто, то оно опускается в записи.

Предложение 12. 1) В маршруте, полученном с применением Алгоритма кластеризации в ЗК с функцией БгорВу, не нарушены условия предшествования Р; 2) трудоемкость построения такого маршрута 0{\Р\Ы2).

Результаты четвертой главы опубликованы в работах [7, 11, 12, 16, 17].

Пятая глава посвящена различным приложениям, связанным с решением ЗК и РЗ в интересах прикладных задач атомной энергетики, а также экологии и таксономии животных. В разделе VI дан пример применения теории адаптивной устойчивости в задаче оптимизации грузоперевозок.

Раздел V.2 посвящен рассмотрению приложений минимаксной маршрутно-распределительной задачи (ММРЗ). В разделе V.2.1 приводится формальная постановка задачи где N исполнителям требуется посетить множество пунктов X с заданной функцией стоимости перемещения X2 —> К, стартуя из хо е X, таким образом, чтобы стоимость максимального среди исполнителей маршрута была минимальной

где (J Xt = X \ {х0}; Vi е 1, N (г ф j) => (Х{ П Xj = 0); 7i: 1, <->■ X;. ¿=i

В разделе V.2.2 рассматриваются приложения ММРЗ с обобщенными внутренними ЗК (посещаются конечные множества) и различными моделями работ на посещаемых множествах к задачам оптимизации перемещений бригады исполнителей в агрессивной внешней среде. В разделе V.2.3 рассматривается ММРЗ в постановке «location problem» (поиск оптимальной базы Хо G argminF(x), либо области для некоторого Т е М: Т > F(x0), неко-

xeG

торого конечного множества G найти {хёС: F(x) < Г}), которая может трактоваться как задача поиска наиболее правдоподобного местонахождения

^тЦ | min [d(xо, 7l(l)) + £ </(7.-(Д 7i(j + 1))] j

1*1-1

N

гипотетического «предка» заданных п объектов в предположении, что эволюционная изменчивость проходила в рамках N «русел», либо как обратная задача поиска области наиболее вероятной гибридизации.

Наконец, в разделе У.З рассматривается задача оптимизации перемещения в процессе перестановки средств наблюдения. Пусть задано множество исходных позиций Х{ = {1,...,п}, множество целевых позиций Х2 = {п + 1,..., 2п}, точка старта О, X = Хх и Х2 и 0, й\ X2 М

V/CcX 70')=<

зек

— 1, если j £ п + 1, 2п;

0, если j = 0;

1, если j £ 1, п;

G={y:X<*X | 7(0) = 0, Ук £ X /({7(0),..., 7(*=)}) > 0}; 2/1-1

d(y(2n), 0) + V d(7(i), 7(г + 1)) -> min.

¿=о ~'eG

Предложен МДП для решения этой задачи

МДП для задачи перестановки средств наблюдения

1)Х'^Х\{0}, Ух£Х' v{x,0) = d{0,х);

2) УК сХ':1< \К\ < Ух £ X' \ К /

min{d(y, х) + v(y, К \ {у})}, если f(K U {х}) > 0;

у£К

v(x, К) = <

d(x,y), иначе;

3) «(0, X') = min{d(y, 0) + v(y, X' \ {y})}, уел'

Предложение 13. Величина v(0, X') совпадает со стоимостью опти

пого маршрута перестановки элементов множества Х\ па позиции

жесгпва Х2 при старте из позиции 0.

Результаты пятой главы опубликованы в работах [2, 4, 18, 19, 22|.

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

Рисунок 1. Последовательное разрушение оптимальных маршрутов со свободным концом при добавлении вершим из областей «адаптивной неустойчивости»

40 Шк. Щ ^ \Я 50 40 941

Рисунок 2. Примеры областей, соответствующих условиям (а) - Теоремы 3 и (б) - Теоремы 4 при добавлении вершины, |5| € {20,30,40,50}

Заключение

Отмстим основные положения диссертации, выносимые на защиту:

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

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

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

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

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

Работы автора по теме диссертации

Монография

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

Статьи из списка ВАК

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

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

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

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

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

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

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

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

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

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

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

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

14. Ivanko Е. Е. On one approach to tsp structural stability // Advances in Operations Research. — 2014. 8 pages.— URL: http://uww.hindaMi.com/journals/aor/2014/ 397025/.

Сборники, труды и тезисы конференций

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

16. Иванко Е. Е. Эмпирический метод dropby распараллеливания приближенного решения задачи коммивояжера // Материалы международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение.» СКТ-2010. - Т. 1. - Таганрог-Москва : Изд-во ЮжФУ, 2010. - С. 229-236.

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

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

19. Григорьев А. М., Иванко Е. Е., Ченцов А. Г. Решение задач маршрутной оптими зации применительно к радиационно-опасным объектам с использованием суперкомпью-

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

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

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

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

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

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

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

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

27. 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.

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

Подписано в печать 06.07.2015. Формат 60x84/16. Бумага писчая. Печать плоская. Усл. печ. л. 7,3. Тираж 100 экз. Заказ 5398.

Отпечатано в типографии ООО «Издательство УМЦ УПИ» 620078, Екатеринбург, ул. Гагарина, 35а, оф. 2, тел.: (343) 362-91-16, 362-91-17