автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмический и постоптимальный анализ устойчивости решений задач дискретной оптимизации

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

ГОРДЕЕВ Эдуард Николаевич

АЛГОРИТМИЧЕСКИЙ И ПОСТОПТИМАЛЬНЫЙ АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЙ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

05.13.17 - теоретические основы юрматики

Автореферат Диссертации на соискание ученой степени

доктора физико-математических наук

Москва - 1992

Работа выполнена в Вычислительном Центре Российской Академии наук

Официальные оппоненты:

доктор физико-математических наук Емеличев В.А.

доктор технических наук Солодов В.М.

доктор физико-математических наук Трубин В.А.

Ведущая организация - Институт математики АН Велоруси.

в ¿£_ час. ОО мин. на заседании Специализированного совета Д002.32.06 при Вычислительном Центре РАН по адресу: 117967, Москва ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке МИ РАН.

Защита состоится

Автореферат разослан " М " _ I99JL г.

Ученый секретарь Специализированного совета, к.ф.-м.н.

Швартин С.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

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

Актуальность исследования поведения решений возмущенной задачи и их связи с решениями исходной задачи объясняется рядом факторов.

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

Во-вторых, с появлением теории НР-полноты и огромного числа последующих публикаций в этом направлении надежда на полиномиальную разрешимость КР-полных задач довольно мала, а существующие алгоритмы их решения экспоненциальны, то есть требуют больших затрат, поэтому естественно стремление увеличить эффективность решения таких задач за счет исследования их качественных свойств. При исследовании устойчивости мы по решению одной задачи получаем практически бесплатно решение континуума задач, лежащих в шаре устойчивости. При этом подобный подход эффективен не только для Ш5-полных задач.

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

Кроме того, внимание к исследованию устойчивости задач

-г -

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

Цель работы

- создание общего метода исследования устойчивости в задачах на узкие места и получение с его помощью формул и алгоритмов вычисления радиуса устойчивости для конкретных норм в и" и типов возмущений;

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

- изучение вопроса о вероятности единственности решения (в случае конечного набора весов) в зависимости от размерности задачи и мощности этого набора;

получение оценки мощности е-покрытия шарами устойчивости;

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

- построение и анализ алгоритмов вычисления радиуса устойчивости в ЫР-полных задачах.

- изучение качественных свойств параметрических задач дискретной оптимизации, связанных с понятием устойчивости.

Методы исследования

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

матроидов, теории графов, математического анализа.

Научная новизна

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

Степень достоверности результатов.

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

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

Теоретическая и практическая ценность.

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

конечнозначности параметрических задач дискретной оптимизации. Возможности для приложений обуславливаются следующими очевидными факторами: на практике параметры задач заданы с некоторой степенью точности, поэтому построенные методы и алгоритмы позволяют более адекватно разрабатывать и анализировать математические модели в экономике и производстве, которые используют задачи дискретной оптимизации. Кроме того, как уже указывалось выше, теоретические построения и алгоритмы, разработанные в диссертации, позволяют строить процедуры ориентированные на решение не одной задачи, а некоторого множества близких задач с уменьшением трудоемкости решения этих задач. Построение и исследование таких моделей проводятся, например, в ВЦ РАН, ИМ АН Белоруссии, ИК АН Украины.

Апробация работы. Основные результаты работы были доложены на международных конференциях: I Советско - итальянская конференция "Методы и приложения математического программирования" , Четрвре, Италия, 1992; II Международная конференция "Комбинаторные методы и приложения" , Нойбранденбург, ГДР, 1989, "8 ПсЫапй соПодиет", Вустров, ГДР, 1988, "Дискретная математика и вопросы математической кибернетики", Мегдешпрунг, ГДР, 1988, "Дискретная математика и приложения в математической кибернетике", Иена, ГДР, 1986, на четырех советско-германских семинарах по комбинаторике и дискретной оптимизации ( Москва (1980), Самарканд (1984), Алма-Ата (1986), Ереван (1989)), на Всесоюзной конференции по теоретической кибернетике, Новосиб1фск, 1980, Всесошом симпозиуме " Статистический анализ нечисловой информации. Экспертные оценки. Дискретная оптимизация" , Алма-ата, 1981, на двух Всесоюзных конференциях по теории графов и дискретной оптимизации ( Батуми, 1981, Батуми, 1990), на Республиканском семинаре "Методы дискретной оптимизации и их программное обеспечение", Ужгород, 1985, а также еще на семи всесоюзных и республиканских семинарах и конференциях и на ряде семинаров в институтах АН СССР и зарубежных институтах.

Публикации.

По теме диссертации опубликовано 26 работ, из них 17 - в центральных научных журналах и периодических сборниках. Основное содержание диссертации отражено в публикациях Ш-[19].

Структура и объем диссертации.

Диссертация состоит из введения, пяти глав, заключения и библиографии (108 наименований). Общий объем работы 247 стр.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Так как объектом исследования являются задачи дискретной оптимизации, то описывается формальная схема , в которую укладывается большинство рассматриваемых в работе задач. Пусть задано конечное множество Е = {е1 ,...,еп } и система его подмножеств = ,...,тз}, Элементам из Е приписаны

веса u(e1 )=u1____,со(еп)=шп. Будем считать, что указанные веса

задаются вектором А = {а1 } и AcRn- n-мерному

векторному пространству. Заметим, что традиционно иногда вектор весов А удобнее трактовать как матрицу размеров pxq, в этом случае можно считать, что pxq=n, и элементы А перенумерованы в виде Hj-jJ, i=1,...,р; 3=1,...,q. Для краткости будем называть

элементы множества Бп траекториями. Некоторым образом определяется длина траектории т при взвешивании, задаваемом вектором А. Обозначим этот функционал через т(А). Наиболее известные функционалы т(А) = 2 ы,,

т(А) = тах ш1 е^т

Первый функционал будем называть линейным и соответствующую задачу - линейной задачей, а второй - минимаксным, а соответствующую задачу - задачей на узкие места. Под дискретной же оптимизационной задачей в широком смысле будем понимать проблему выбора некоторой траектории , на которой достигается экстремум функционала .Траектории, доставляющие экстремум функционалу, будем называть оптимальными траекториями или решениями задачи. Таким образом, тройка (Е,БП,А) и способ задания функционала определяют некоторую массовую задачу выбора, если же Е, Бп и функционал фиксированы, то вариацией А задаются различные индивидуальные задачи. Таким образом А служит для индексации индивидуальной задачи, поэтому для краткости индивидуальную задачу фиксированной массовой задачи будем обозначать иногда через Ъ^.

В эту схему легко вписываются все известные оптимизационные задачи на графах, а также и некоторые другие классы задач. Например, если Е - множество ребер графа, а -вес ребра е^, то в случае, когда траектории - остовные деревья, получаем задачу о кратчайшем остове, если же это гамильтоновы циклы, то задачу коммивояжера, для паросочетаний - это задача о максимальном паросочетании и т.д. В дальнейшем для краткости будем называть задачу (Е,БП,А) исходной задачей.

Обозначим множество номеров оптимальных траекторий задачи через ф(А). Через И0 будем обозначать подмножество Нп такое, что при АеИ° выполняется соотношение ф(А)={1,2.....з).

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

работы будет проведен сравнительный анализ, но мы посвятим здесь основное внимание понятию радиуса устойчивости, которое ввел В.К.Леонтьев.

Предположим, что возмущению могут подвергаться все элементы вектора А и в Rn задана некоторая норма.

Определение. Задача Z. называется е- устойчивой, если для п

любого ВеВ такого, что |В|<е выполняется соотношение ф(А+В) •= ф(А)

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

Определение. Радиус устойчивости задачи Z^eR0 положим по определению равным нулю, в противном случае радиусом устойчивости назовем число р(А)= sup е, где аир берется по всем е , для которых гд является е-устойчивой.

Определение. Шаром устойчивости задачи гд называется открытый шар в Rn с центром в А и радиуса г<р(А).

Эти же определения непосредственно переносятся на случай, когда часть элементов А стабильна.

Таким образом, при фиксированных Е и Dn радиус устойчивости определяет предел возмущений элементов А, при которых не возникает новых по сравнению с решениями задачи гд оптимальных траекторий.

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

Формулы эти носят самый общий характер, поэтому вычисление по ним радиуса устойчивости является полным перебором по ф(А) и, что самое существенное, по всему множеству D .

Радиус устойчивости в самом общем случае определяется тремя, вообще говоря, не зависящими друг от друга факторами:

1. Ограничениями на стабильность весов.

2. Типом нормы в пространстве Rn;

3. Классом рассматриваемых оптимизационных задач.

Самым общим результатом было бы получение выражения для

радиуса устойчивости для случая произвольной нормы. Однако на этом пути нет возможности получить содержательные результаты. Поэтому в §3 на класс норм накладывается одно довольно естественное и "слабое" с точки зрения исследования задач дискретной оптимизации условие "монотонности".

Норма А, рассматриваемая как функция |аj|,...,| е^ |, является монотонно неубывающей по каждой переменной, т.е. при A,B€Rn из выполнения для всех i=I,...,п неравенства [а^^Ь^ следует неравенство |А| £ |В|.

В качестве иллюстрации отметим, что чебышевская норма и норма в пространстве 1р удовлетворяют этому условию .

Обозначим через т(А) длину оптимальной траектории задачи ZA и введем вспомогательный параметр d(A) = min ( т (А) - т(А) ).

з£ф(А) 3

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

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

Пусть Од(А) - некоторое множество элементов Е, входящих в траектории из ф(А) такое, что, если веса всех элементов этого множества заменить на число а, то в полученной таким образом задаче ZA, длины всех траекторий с номерами из ф(А) станут равными а. Причем каждое такое множество обладает свойством тупиковости, то есть удаление любого элемента приводит к

появлению в Ъ^, траектории с длиной, не равной а. Таких множеств для фиксированной Ъ^ конечное число. Перенумеруем их произвольным образом 1 = 1,...,1(а) и обозначим их совокупность через Га(А), т.е.

Га(А) = < С*(А) }1=1.....,(а)

Пусть теперь А*,а- вектор из Нп с элементами

Я1'"

а , если е^ е С*(А),

а^, в противном случае.

Обозначим через 0§(А) вектор дР,а - А, а через Ь?(А) его норму. И пусть ЬД(А) - минимум таких норм по всем множествам из

Га(А), т.е.

Ь_(А) = т1п « А1,а-А | а 1=1,...,г(а)

Пусть данный минимум достигается на множестве С^(А), т.е.

Ьа(А) = Ьд(А).

Заметим, что всюду малая буква и будет обозначать именно индекс из вышеприведенного равенства, и мы не будем это особо оговаривать. Кроме того, вообще говоря, и может зависеть от а. При а=га(А) будем считать вектор 0^(А) нулевым.

Корректность следующих построений следует, в частности, из того факта, что при всех а,р > ш(А) справедливо соотношение

Га(А) = Гр(А).

Наряду с параметром 1^(А) вторым важным для дальнейшего рассмотрения является параметр Р^(А), который определяется для всех та, з^ф(А),как норма разности векторов А и Ад из йп, где элементы вектора Ад а определяются следующим образом

аэ,а = | а , если е^ € тд, а<ау, ^ 1 а^, в противном случае.

Обозначим через вектор А - Ад а через Р^(А) его

норму. И пусть Ра(А) - минимум таких норм по всем неоптимальным траекториям, т.е.

-ю -

Р_(А) = mill I A - A, I a 1*ф(А) 1'a

Пусть данный минимум достигается на траектории ту, т.е.

Pa(A) = pJ(A).

Заметим, что всюду малая буква у будет обозначать именно индекс из вышеприведенного равенства и мы не будем это особо оговаривать.

Пусть h = min а^, Н = max а^. Следующие леммы являются основными вспомогательными утверждениями в этом разделе.

Леша 1.3. Параметр L^(A) как функция от а является монотонно неубывающей функцией на интервале [т(А),Н]. Параметр Рд(А) как функция от а является монотонно невозрастающей функцией на интервале [h, m(a)+d(A)].

Лемма 1.4. Для любой задачи при условии Aj£R° справедливо соотношение

min

aeiO.oo)

min |£¿(A) + R¿(A)| = min |Q*(A) + R¿(A)|.

[O,®) a a ae[m(A),m(A)+ü(A)] a a

Основной результат этого раздела приведем в следующих двух теоремах.

Теорема 1.5. Пусть в линейном нормированном пространстве Rn норма удовлетворяет условию монотонности и A¿ Rq. Тогда для любого аХ) .любых qP(A) из/ ф(А) справедливо соотношение

р(А) ^ |Qg(A) + Й®(А)|.

Следствие. При выполнении условий теоремы 1.5 справедливо следующее неравенство.

р(А) « min min min | qP(A)+R®(A)l= aetO ,oo ] р=1.....t(a) в£ф(А) a a

min min min i qP(A)+R^(A)i.

aeEm(A),m(A)+d(A)] p=1,...,t(a) з^ф(А) a a

Обозначим через T(A) величину

min min min i qP(A)+r!?(A) i.

a€[m(A),m(A)+d(A)] p=1,...,t(a) зд!ф(А) a a

Теорема 1.6. Пусть в линейном нормированном пространстве

Rn способ введения нормы удовлетворяет условию монотонности и Ají Rq.Тогда справедливо неравенство р(А) ? Т(А).

Из этих двух теорем получаем следующее утвервдение. Теорема 1.7. Пусть в линейном нормированном пространстве Rn норма удовлетворяет условию монотонности и к£ Rg.Тогда

р(А) = Т(А).

Теперь, используя теорему 1.7, -мы получаем метод вывода формул для радиуса устойчивости для конкретных типов норм в Rn. В качестве примеров рассмотрим чебышевскую норму и норму в пространстве 1р. Однако для этого нам потребовалось бы еще более слабое утверждение, которое является непосредственным следствием теоремы 1.7.

Рассмотрим La(A) и Ра(А) как функции от а. Пусть n={<Xj,___,a)w - множество корней уравнений

I¿(A)=I¿(A), т, 1,3=1.....t;

PJ(A)=P¿¡(A), ijíJ, i.J¿<t>(A);

лежащих на отрезке Cm(A),m(A)+d(A)].

Теорема 1.8. Пусть A^Rq и |A| = , тогда

р(А) = min { р" (A), l" (А) }. 1=1,...,w а1 а1 Приведен алгоритм вычисления радиуса устойчивости для

данного случая, в котором р(А) находится одновременно с

решением вышеприведенных уравнений, при этом показано, что

число решаемых уранений, как правило, невелико.

При Р>1 аналог этой теоремы выглядит следующим образом.

|Р)1/Р ,

тогда

Теорема 1.10. Пусть A^Rq и норма |А|=(2|а1|

р(А) = min min [ (l£(A) ,pJ(A)) |.

1=1,...,m-1 aeia ,a ] a a 1 1+1

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

Пусть m(A)B = min т.,(А)в, Sn(A)={T,:tet>(A)}, a Rn(A) -10(A) 10 1 Ъ

подмножество траекторий такое, что для всех u^eR^A)

•D ТЭ

справедливо равенство т., (А) = min .

1 кеф(А) К

Теперь для всякой пары траекторий т^еБ^А) и ts¿Sq(A) определим числа: ав1(А)=т3(А) - тг^(А), psl(A)=i;s(A)H - т1(А)в, 7sl(A) = (XS(A)B - (А)в)/2. И пусть

Р(А) = min { min (аа1(А)Дт1п {max (ßsl(A),7sl(A))}},T1eR0(A). tseV(A) ts¿V( A)

WA>

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

Teopeua I.I2. Если существует t^SqÍA), состоящая из стабильных элементов, и V(A) = 0 , то при A¿R° справедливо равенство р(А) = со.

Теорема I.I3. Если существует t^cSqU), состоящая из

стабильных элементов, и V(A) /0 , то при Aj£R° справедливо

равенство р(А) = mln cu., (А) = а(А). taeV(A)sl

Teopeua 1.14. Пусть A fi R° и в любой оптимальной траектории существует нестабильный элемент, тогда р(А) = Р(А).

Замечание I.I. Если все элементы А нестабильны, то теорема I.I следует из теоремы I.I4.

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

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

Глава 2 посвящена исследованию в общем случае вопросов сложности анализа устойчивости.

Пусть в Rn задана чебышевская норма. Будем считать, что элементы вектора А - рациональные числа, а = max ¡a^!,

i=1,2,...n, q - наименьшее общее кратное знаменателей элементов А, а Пд=тах1т;1!, 1=1,...,з. Через Р и Q будем обозначать полиномы.

Теорема 2.1. Пусть задача на узкие места разрешима за полиномиальное время P(n), A ¡L R0, тогда трудоемкость нахождения р(А) не превосходит 1ф(А)!Q(n).

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

Теореыа 2.2. Пусть линейная задача разрешима за полиномиальное время Р(п), веса - рациональные числа, А R0, тогда существует алгоритм наховдения р(А) с трудоемкостью !ф(А)!Q(n, aq).

Для вычисления радиуса ' устойчивости в траектории оптимизационных задачах с линейным функционалом необходим перебор по всему множеству оптимальных траекторий, поэтому актуален вопрос о вероятности единственности оптимальной траектории, которому и посвящен следующий параграф. При этом интересен случай, когда веса в А берутся не из множества действительных чисел, а из некоторого конечного множества 9=a,2.....N-I}.

Легко показать, что для линейной задачи в непрерывном случае (т.е. в случае, когда элементы А выбираются из отрезка Са,Ь]) решение единственно с единичной вероятностью.

Так как мы будем рассматривать набор конкретных задач, то для удобства в ряде случаев взвешивание в задаче ZA будем представлять в виде матрицы А =(а^) размеров гаи. Рассмотрим

вероятность едиственности решения фиксированной задачи p(n,N) как функцию от п и N.

В случае линейного функционала согласно вышеупомянутому факту для выбора весов из в "естественно ожидать", что для N, "больших" в сравнении с n, Ит p(n,N) = 1.(Здесь и далее все пределы при п стремящегося к <»). в то же время р(п,1 )=0. Таким образом, можно сделать качественный вывод о возможном существовании "порога" ("порогов"), т.е. такого типа

зависимости N (п), что при N>N (п) вероятность единственности решения стремится к единице, и (или) при N<N*(n) эта вероятность стремится к нулю.

Задача I. Рассмотрим самый простой случай: Е = Dn. (Данная задача является вырожденным случаем сформулированных ниже задач 5,6 и 7).

Значение точного порога для данного случая дает следующая теорема.

Теорема 2.4. В задаче I вероятность единственности оптимальной траектории стремится к единице при п2=о(Ы) и стремится к нулю при N=o(n2). Если же отношение n2/N стремится к некоторой константе с, то

bim p(n,N) = с/(ес-1).

Задача 2. Траектории - совокупности из п элементов матрицы А, лежащих в разных столбцах. Функционал линейный.

Теорема 2.5. В задаче 2 вероятность p(n,N) —>0 при N = о(п2) и p(n,N)—И при n2=o(N).

Задача 3. Здесь (E,Dn) то же, что и в предудущем случае, однако функционал минимаксный .

Теорема 2.6. В задаче 3 вероятность p(n,N) —>0 при всех

Ш.

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

Теорема 2.7. В задаче 4 вероятность p(n,N) —»0 при N=const и p(n,N)—1 при n!=o(NI/2).

Задача 5. Теперь мы рассмотрим задачу на узкие места, в которой траекториями являются столбцы матрицы А, т.е. траектории этой задачи не пересекаются.

Мы рассматриваем эту вторую из двух задач на узкие места для того, чтобы продемонстрировать существование порога.

Теорема 2.8. В задаче 5 вероятность p(n,N) —»0 при N<n/21og п и р(п,НН при n=o(N).

Задача 6. Траектории - неупорядоченные последовательности

из любых п элементов матрицы А, то есть п-элементные

подмножества множества Е. функционал линейный.

Теорема 2.9. В задаче б вероятность p(n,N) —Ю при N=o(n2) и p(n,N)—1 при n2=o(N).

Задача 7. Траектории задачи - непересекающиеся последовательности из п элементов множества Е. (Например, столбцы матрицы А), функционал линейный.

Теорема 2.10. В задаче 7 при любом N ^ 2 вероятность

p(n,N) — 1.

Таким образом, среди рассмотренных случаев дважды наблюдалось отсутствие порога, причем для задачи 7 с линейным функционалом при всех М ) 2 решение единственно с единичной вероятностью. Второй же пример отсутствия порога в задаче 3 одновременно демонстрирует противоположный случай, т.е. при всех Ю I наблюдается с единичной вероятностью присутствие по крайней мере двух решений, т.е. единственность решения здесь имеет нулевую вероятность, а , кроме того, данный пример показывает несправедливость в случав минимаксного функционала утвервдения , аналогичного вышеприведенному утверждению 2.1 для линейных задач. Второй пример задач «а узкие места - задача 5 , демонстрирует возможность существования порога и в случае минимаксного функционала. Остальные четыре задачи (задачи 1,2,4,6) демонстрируют четыре ситуации наличия порога в линейных задачах.

Другим естественным аспектом исследования сложности изучения устойчивости оптимизационных задач на базе понятия радиуса устойчивости, его свойств и алгоритмов вычисления является проблема табулирования шарами устойчивости, исследованная в §3.

Будем рассматривать случай чебышевской нормы и линейного функционала. Кроме того, будем предполагать, что рассматриваемый класс задач обладает следующим свойством. Пусть в задаче ZA вектор А не принадлежит пространству Rq и не является нулевым. Рассмотрим теперь задачу ZB, в которой

bi = ai/lAl» 1=1 »••-•п-Тогда соотношение т.. (А) > Т-ЛА) выполняется тогда и только

тогда, когда выполняется соотношение т^В) > (В). Отметим, что это условие выполняется для всех известных на практике комбинаторных задач оптимизации.

Как обычно Sr(A) - открытый шар в Rn с центром в А и радиуса г, a S*(A) - его замыкание. Основной вопрос, изучаемый в этом разделе - это исследование покрытия единичного шара шарами устойчивости задач со взвешиваниями из этого единичного шара, то есть найти такую совокупность задач W = fZA , ZA .....ZA ,...} что для любой ZB , BeS.,(0),

найдется задача из W такая, что В с SpCA^).

Известно, что никакое конечное и даже счетное покрытие невозможно.

Естественным продолжением подобного исследования является вопрос о существовании конечного е-покрытия единичного шара шарами устойчивости (с точностью до множества меры е).

Обозначим через к размерность подпространства RQ

(напомним, что это подпространство состоит из таких векторов А,

что в задаче Z, все траектории имеют одинаковую длину) ,а через k А П (А) множество 16

|в = <b±) € Rn : |Ьга1| * { J; }

Пусть riQ - максимальное число нестабильных элементов, которое может содержать траектория задачи, Ixt - наименьшее целое, большее х, ф(п) - известная в теории чисел функция Эйлера, q = тах(2пд,31/ОГ).

В теореме 2.II доказано существование конечного покрытия W * k

множества Sj(0)\ П?0(А) шарами устойчивости и .получена верхняя оценка мощности этого покрытия. В качестве следствия из этой теоремы получено следующее утверадение.

Следствие 2.1. Для любого е>0 существует е-покрытие W множества S*(0) шарами устойчивости такое, что

IW| < 2n (2t2/*? + 0(t ln t)), где

t = (max (2n0>]1/s'/<'Tl~JS-> [))".

Полученные результаты носят теоретический характер. Далее рассматривается градиентный алгоритм покрытия,

проиллюстрированный на примерах двух задач. В первом примере для s=I/2 следует оценка

|W| < 2б5/3.

Используя же градиентную процедуру, получаем покрытие из 80 шаров. В следующем примере для е=3/8 вышеприведенная теорема

TffO

дает оценку мощности покрытия 6 2/3, а алгоритм дает 16 шаров.

Далее приводится обсувдение практического значения предложенной процедуры.

В §4 рассматривается еще один пример, иллюстрирующий связь между решением задачи и исследованием ее устойчивости. Он демонстрирует ситуацию, в которой знание радиуса устойчивости позволяет в некоторых случаях за полиномиальное время получить решение NP-полной задачи. Аргументация такого подхода изложена в предыдущем разделе. Общая схема подхода выглядит следующим образом. Решается некоторая конкретная индивидуальная задача Ъ^, затем находится ее радиус устойчивости. Далее за полиномиальное время можно проверить некоторое условие и в случае его выполнения получить решение вновь возникающих задач. В общем виде такой метод обсуздался при введении понятия устойчивости и в предыдущих разделах этой главы. Здесь же рассмотрена одна его конкретизация на примере задачи коммивояжера.

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

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

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

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

Обозначим через Сили для краткости - число

ч^А) - ч^А) -

|а{| + |т,| - 2|т( п

Известно, что в случае линейного функционала, всегда найдется пара, состоящая из оптимальной т^ и неоптимальной т для. которой справедливо равенство р(А) = Гц. В этом случае будем говорить, что р(А) достигается на этой паре траекторий.

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

Леша 3.3. Для любой траектории %т , тефМ), (Тр, )

найдется "напарник" Тр, р£<р(А), (тт , теф(Х)) такой, что, если

р(А) достигается на паре (т,р), то либо |тт| = |Тр|, либо тр^т:.

т

а множестве 2е можно ввести метрику

й(А,В) = (¡(А\В} и (В\А)\ + |И| - |В\\)/2.

Далее введем окрестность

0(А) = (Ва^: й(А,В) « 1),то есть

ОСА) = ( и (Аие) ) и ( и (А\е) 1 и'( и и (А\еи/) ) . I ее£\4 ) { ей ) -»

Определение. Траектория %j называется вторым решением задачи, если из условия задачи следует, что при т^М) < т{ (.^выполняется соотношение: {ефМ.).

Определение. Траектория %J называется з-вторым решением задачи, если из условия задачи следует, что при т<

и |т{|=з выполняется соотношение: 1^<р(А).

Утверждение 3.8. Пусть г{ - оптимальная траектория, а -второе решение задачи, находящееся от на минимальном

расстоянии в пространстве (2Е,(3). Тогда

Леша 3.4. Пусть оптимальная траектория, = з, а

%J - з-второе решение задачи, находящееся от на минимальном расстоянии в метрическом пространстве (2е, й) . Тогда

Следствие 3.1. Пусть ij и х^ - соответственно з-второе и m-второе решения задачи, тогда для любых s,v&t справедливо равенство:

%j(A) = хр(А).

Пусть р (А) - длина э-второго решения задачи , а 7{А) -наименьший вес ненулевого элемента оптимальной траектории задачи.

Рассмотрим некоторую оптимальную траекторию

Тр = (a1ta2,...,d3).

Для кавдого из ее а элементов через c(d^) обозначим

min (u(dt) - w(e)), где минимум берется по всем таким элементам множества Е\%р, что ojfdjJ Ф ш(е) и Tp\djUe является траекторией задачи. Если же множество таких элементов пусто, то полагаем указанную величину c(dt) неопределенной. Очевидно, что cfd{J>0 либо неопределено.

Пусть

= min c(d,), Р i 1

где минимум берется по всем таким элементам множества fI,2,...,sJ, для которых cfdjJ определено. Множество таких элементов не пусто по предположению о том, что |Х> | >-1 и определению матроида.

На основании этих вспомогательных утвервдений доказывается теорема 3.7.

Теорема 3.7. Для оптимизационной задачи на матроиде значение ар(А) не зависит от р.

Данная теорема является основной в этом разделе, так как позволяет игнорировать перебор по оптимальным траекториям.

Следующая теорема дает дальнейшее уточнение этого результата.

Теорема 3.8. Пусть в оптимизационной задаче (E,Dn,A), где (E,Dn)~ матроид, элементы А неотрицательны и AfLRQ, тогда

р(А) = mln{j(A),а(А)/2).

Таким образом, из двух доказанных теорем следует, что основой для вычисления радиуса устойчивости служит алгоритм

поиска а(Л), который далее подробно описан и проанализирован.

Teopeua 3.9. Радиус устойчивости задачи (E,Dn,A) в случае, когда (E,Dn) - матроид, 4£Яд и элементы А неотрицательны, может быть вычислен за время 0(гга(п)).

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

Teopeua ЗЛО. Радиус устойчивости в задаче о кратчайшем остове в случае единственности решения может быть найден с трудоемкостью 0(та(т,п)), где а(m,nj - функция, обратная функции Аккермана.

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

В §4 исследуется устойчивость оптимизационных задач на пересечении двух матроидов, в частности, задачи о назначениях.

Пусть Mj=(E,Fj) и М2=(Е,Р2)- матроиды и Dr=F1nFz. Рассмотрим теперь оптимизационную задачу (E,Dn,A). В этом разделе вновь предполагается, что функционал задачи линейный и норма в пространстве Я71 чебышевская.

Пусть 1сЕ. Мощность максимального независимого в Jij множества, содержащегося в I, называется рангом I в tfj и обозначается через Rg^(I). Максимальное по мощности подмножество Е, такое, что оно содержит I и имеет в Jfj тот же ранг, что и I, называется замыканием I в Jfj и обозначается через ap^I). Заметим, что ap^(I) единственно. Далее, пусть

Я = min {BgjW.Eg^E)).

Пусть дана некоторая траектория I и элемент е(£Г. Через С^1 ■'обозначим цикл в Ы^, содержащий только элементы множества IUe^. Из свойств матроида следует единственность такого цикла. Аналогично через •'обозначим цикл в Jfg' содержащий только элементы множества ILle j.

Через BG(I) обозначим двудольный граф следующего вида. Два его множества узлов - это I и Е\1.

1. Для любого е,еЕ\1, в качестве ребер берутся для всех

2. Для любого е,е£\1, е^ар2(1) в качестве ребер берутся для всех е^еС^

Если е^ар^си, то этот узел называется стоком, а при е^ар^(1) - истоком.

Граничным путем графа ВО(1) (г.п.) называется либо контур в ВС(1), либо простой путь между вершинами а и Ь такой, что Ь - это либо узел из I, либо сток в ЕМ, в свою очередь а - это либо узел из I, либо исток в ЕМ.

Пусть ,...- некоторый граничный путь в Вй(1).

Говорят, что Б допускает разрез, если в ВС(1) существует ребро (d}¡,dJ) такое, что

Пусть ___г-п- в ВС(1). Назовем элементы й^и

крайними элементами этого пути.

Пусть Б=((21,...,с1т)- г.п. в ВС(1). Тогда 5 можно некоторым

образом разбить на совокупность граничных путей ,___

которые попарно либо не пересекаются, либо пересекаются только по крайним элементам.

Пусть т = (е?.....е^) - оптимальная траектория

задачи.

Рассмотрим По определению в этом графе конечное

число граничных путей

' • • • 'Ри>

таких, что множества {=1,___являются пересечениями, а

следовательно, и траекториями задачи. Обозначим эти траектории через У1,...,!3".

Пусть и - множество траекторий, состоящих только из элементов траектории т, и таких, что при РеУ выполняется соотношение

= к-I.

Заметим, что это множество не пусто, что следует из определения матроида, единственности оптимальной траектории и предположения о мощности множества Вп (\Вп\>1).

Определим теперь два основных параметра, необходимых для вычисления радиуса устойчивости:

а (А) = min г(1,Р1) 1=1,...,w

В(Л) = min r(%,F ) FzU

Далее доказывается основная теоремы этого раздела.

Теорема 3.II. Пусть ) и Jf^fE.FrjJ- матроиды и

D^PjflPg. Рассмотрим теперь оптимизационную задачу (E,Dn,A) с единственным решением и неотрицательным взвешиванием А. Радиус

устойчивости этой задачи равен min (а(А),ф(А)}.

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

Теорема 3.12. Алгоритм находит радиус устойчивости задачи (E,Dn,A), где Dn=F1QF2, а K^fE.F^, U^(E,F2) - матроиды, с единственной оптимальной траекторией и неотрицательным взвешиванием за время 0(n?R + nRc(n)), где с(п) - время проверки независимости подмножества из Е в любом из матроидов Ы(То есть максимальное из времен Oj(rc), o2(n).)

Сравнивается трудоемкость решения задачи и время поиска радиуса устойчивости.

Ниже мы отдельно рассматриваем задачу о назначениях и ее частные случаи. Строятся алгоритмы исследования устойчивости задач с линейным и минимаксным функционалом. Сравниваются и анализируются различные подходы к понятию устойчивости.

В качестве примера приведем следующее утверждение.

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

Утверздение 3.II. Радиус устойчивости вышеопределеннной задачи о назначениях равен г/2.

В последнем параграфе исследуется устойчивость задачи о кратчайшем пути.

Нам будет удобнее считать, что траектории - упорядоченные совокупности ребер, поэтому под множеством будет

пониматься упорядоченная совокупность ребер, в которой в

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

таким же образом ребра траектории ij (то есть ребра множества

Разобьем теперь все множество неоптимальных траекторий на два непересекакщихся подмножества BR = Р U Q, где Р - множество всех путей из з в t такое, что для любой найдется

оптимальная траектория т{ такая, что множество является

циклом в графе G. А множество Q - множество оставшихся неоптимальных траекторий.

Теорема 3.12. В задаче о кратчайшем пути радиус устойчивости может быть вычислен по формуле

т¡(А) - %t(A)

р(А) = min тпах

i^P 1аф(А) |т{| + \ij\ - 2|т{Пт;^|

Из доказательства теоремы сразу следует алгоритм нахождения радиуса устойчивости при |ф(Л)|=1. Этот алгоритм 0(п2) раз использует процедуру нахождения кратчайшего среднего цикла, имеющего непустое реберное пересечение с фиксированным путем, в графе G.( Под кратчайшим средним циклом мы понимаем цикл минимальной длины, если за длину принимается отношение суммы весов ребер этого цикла к числу ребер).

Теорема 3.13. Пусть имеется алгоритм поиска кратчайшего среднего цикла , проходящего через фиксированный путь в графе, и трудоемкость этого алгоритма f(n). Тогда в задаче о кратчайшем пути с единственной оптимальной траекторией радиус устойчивости может быть найден с трудоемкостью 0(п2 f(n)).

Последние две ' теоремы позволяют сократить перебор при поиске радиуса устойчивости в задаче о кратчайшем пути по сравнению с вычислением по общей формуле. Однако, вычисление радиуса устойчивости оказывается ЯР-трудной задачей, о чем свидетельствует следующая теорема.

Сформулируем задачу РАДИУС.

Вход. Граф G, матрица А, фиксированное действительное число R.

Выход. Ответ на вопрос, существует ли пара траекторий т^ и Тр, kç.<p(A), р£ф(А), такая, что выполняется неравенство

Очевидно, что последний вопрос эквивалентен следующему. Верно ли, что р(А) $ Я ?

Теорема 3.14. Задача РАДИУС №Р-полна, даже если в графе нет циклов отрицательной длины.

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

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

Четвертая глава посвящена исследованию устойчивости решений ЫР-трудных задач.

В §1 анализируется общая проблематика и подход к исследованию устойчивости.

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

На основе той же схемы, но уже на базе более совершенных алгоритмов для задачи коммивояжера была проведена другая серия экспериментов с задачей коммивояжера. Однако здесь речь уже идет о пакете программ, который ориентирован на точное решение и исследование устойчивости задачи коммивояжера с различными функционалами и различными нормами в й71 при некоторых ограничениях, которые практически всегда выполнялись. (Для нормы в 1р при этом предполагалось, что |ф(А)|^5).

Подробное описание пакета программ с блок-схемами приведено в П67. Численные эксперименты проводились на БЭСМ-6 и ЕС-1061. Причем они проводились как с пакетом в целом, так и с отдельными процедурами. Они показали сравнительную эффективность пакета и подтвердили обоснованное выше предположение о том, что для ИР-трудных задач трудоемкость

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

§3 посвящен задаче Штейнера на графах.

Пусть, как обычно, в = (У,Е) - простой неориентированный граф с множеством вершин 7, |7|=гг, и множеством ребер Е, \Е\=т, веса которых заданы с помощью матрицы А = Фиксировано

множество вершин 7', |У'|=&. Деревом Штейнера называется любой подграф С, являющийся деревом и имеющий среди своих вершин все вершины множества V. Таким образом, в задаче Штейнера (Е,Вп,А) множество Е - ребра графа в, траектории - деревья Штейнера, А -матрица весов ребер графа. Мы будем рассматривать линейную задачу Штейнера и под решением понимать дерево Штейнера минимальной длины. Так как в литературе рассматривается только линейная задача, то мы ею и ограничимся. Мы обратились к примеру этой задачи, потому что она занимает наибольшее внимание исследователей последнего десятилетия среди всех известных 2УР-полных задач. Однако в этом рассмотрении мы приведем не примеры конкретных программ и численных экспериментов, а обратим основное внимание на весь спектр подходов к исследованию устойчивости, включая и эвристические методы. Заметим, что с той же точки 'зрения можно было бы рассмотреть и задачу коммивояжера, однако определенная специфика задачи Штейнера позволит проиллюстрировать и некоторые особенности подхода к исследованию устойчивости.

Далее рассматриваются и сравниваются три подхода к построению точных алгоритмов для поиска р(А): на базе теоремы 2.2; на основе топологического алгоритма решения и на основе метода ветвей и границ. Построены также два эвристических алгоритма.

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

Пятая глава посвящена устойчивости решений и анализу

качественных свойств параметрических задач дискретной оптимизации.

В §1 даются необходимые понятия и определения, а также обсувдается общая проблематика.

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

Задачу (Е,БП,А) мы параметризуем, то есть вместо постоянных компонент вектора весов мы определяем вектор функцию

А(и) = (а1(и),...,ап(и)), иеИ^,

где параметры (координаты вектора и) и^____, и^ изменяются в

многомерном "параллелепипеде" «Г*1:

х.^ « ^ Ур 1=1.....к.

При этом "парллелепипед" не обязательно конечен, то есть х1 может обозначать -<», а у^ соответственно да.

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

Таким образом, при каждом фиксированном ид^Н мы получаем обычную задачу оптимизации 2д(ид) , то есть для всех т^,

3=1,___,ш, т^(А(ид)) определяется только комбинаторикой задачи,

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

задачи, под которым понимается нахождение решений во всех точках из <1^.

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

В параграфе 2 мы рассморим случай, когда матрица весов зависит только от одного параметра 1;еСа,Ь], где Са,Ь] -конечный или бесконечный интервал. Основное внимание будет уделено следующему свойству задачи, тесно связанному с понятием устойчивости.

Определение. Праметрическая задача оптимизации называется конечнозначной на [а,Ы, если существует такой набор открытых непере секающихся интервалов 1=1.....N-1, что он

вместе с концами интервалов покрывает (а,Ь), т.е.

N N-1

[а,Ь] = {а} и СЬ) и И,) и (^,1;.,^ ), 1=1 1 1=1 1 1+1

и любое решение задачи в любой точке является ее решением на всем интервале ), 1=1.....N-1.

Сформулируем теперь свод определений, необходимых при дальнейшем рассмотрении.

Всюду далее, если не оговорено обратное,' говоря об интервале [а,Ъ], мы включаем в рассмотрение также случаи а=-оо и Ь=оо. Кроме того, предполагается, что все интервалы, о которых ниже идет речь принадлежат [а,Ь].

С фиксированной параметрической задачей оптимизации свяжем подмножество из ш2 функций ф^(А(1;)) таких, что

Ф1Л(А(1>) = т1(А(г)> - (А(г>). Каждая из этих функций определена на интервале [а,Ь]. Для краткости будем обозначать их просто Множество всех

таких функций обозначим через Ф .

Под знаком функции в точке ^[а.Ы будем понимать один из трех знаков : "+", или 0.

Определение. Точка Са,Ы называется точкой перемены знака функции ф^(1;), если для любого е>0 в интервале (г0-еД0+Е) найдется точка ^ такая, что знаки функции Ф-ц^) в точках и различны.

Определение. Множество точек М = (а^____»аа^> а^сЕа.Ы,

1=1,...,s, называется решающим множеством для задачи ZA при взвешивании a(t) на интервале [а,Ь], если решение задачи в любой внутренней точке интервала 1=1,...,8-1,

является ее решением на всем этом интервале.

Определение. Решающее множество называется простым, если никакое его подмножество не является решающим.

Определение. Точка aeía.b], где а и Ъ - действительные числа, называется точкой сгущения точек перемен знака функции (J^-jCt), если для любого е>0 функция ф^ (t ) меняет знак бесконечное число раз либо на интервале [а,а+е], либо на интервале [а-е,а].

Аналоги этого определения приведены для полубесконечных интервалов.

Определение. Точка сгущения а точек перемен знака функции ф^Ю называется устранимой точкой сгущения для этой функции, если существует интервал [7,р]с[а,Ь], ае(7,р), и такие индексы к и р, что 1^к,р^п, для которых выполняются соотношения

фэд(-Ь)<0, ^(tHO при всех te[7,oc);

фрj(t)<0, Фр1(t)<0 при всех tç(a,p]. (На случай бесконечных интервалов это определение трансформируется следующим образом. Если а=оо, то вместо [7,р] берется интервал [7,00) и требуется существование только индекса к. Если а=-оо, то вместо [7,(3] берется интервал (-00,7] и требуется существование только индекса к.)

Определение. Точка сгущения а называется устранимой точкой задачи, если она является устранимой точкой сгущения точек перемен знака для всех функций из Фп.

Приведем теперь сновные результаты этого раздела.

Теорема 5.1. Если каждая из функций ф^Ш меняет знак конечное число раз на ta,b], то параметрическая задача оптимизации Z¿ с матрицей A(t) = |a1;j(t)| является конечнозначной на С а ,Ы.

Следствие. Если каждая из функций Ф-цШ непрерывна на (а,Ь) и имеет конечное число нулей на [а,Ь], то параметрическая задача оптимизации с матрицей A(t) = (t)| конечнозначна на [а,Ы.

В теоремах 5.2,5.3, 5.5 приводятся примеры достаточных

условий конечнозначности и оценки мощности решающего множества для задач с линейным функционалом.

Перейдем теперь к основному результату этого раздела -критерию конечнозначности в общем случав.

Теорема 5.4. Для того, чтобы параметрическая задача была конечнозначна на 1а,Ь] необходимо и достаточно, чтобы любая точка сгущения точек перемен знака любой функции из Фп была устранимой точкой задачи.

С понятием конечнозначности тесно связано понятие устойчивости задачи по параметру.

Определение. Траекторная задача гА=(Е,Бп,А(1;)) называется устойчивой по параметру в точке [а,Ь], если существует открытый интервал (а,р), содержащий Ъд и такой, что любое решение задачи в любой точке этого интервала является ее решением в точке tQ.

Утверздение 5.2. Для того, что бы параметрическая задача оптимизации (Е,БП,А(1;)) на интервале [а,Ы была устойчивой в точке необходимо и достаточно, чтобы tg не

принадлежала никакому простому решащему множеству.

Наряду с рассмотренным понятием конечнозначности могут быть введены и другие близкие по смыслу понятия. Приводятся и анализируются примеры аналогов свойства конечнозначности, а также алгоритмы и подходы к решению и исследованию параметрических задач на базе понятий устойчивости и конечнозначности. Исследуется связь полученных результатов с алгоритмами вычисления радиуса устойчивости в задачах на узкие места (§3 главы I).

В §3 мы приводим результаты, касающиеся понятия конечнозначности решения параметрической задачи в некоторой многомерной области. (Под областью будем понимать множество, гомеоморфное шару в Н^).

Определение. Параметрическая задача оптимизации называется конечнозначной на параллелепипеде <Тк, если этот параллелепипед можно разбить на конечное число областей

.....таким образом, что решение задачи в любой внутренней

точке области является решением этой задачи во всех точках области.

Пусть а1(и) = а1(и1 ,...,ик), где и=(и1.....ик)€,т •

Вновь с фиксированной параметрической задачей оптимизации ? '

свяжем подмножество из m функций ф^(А(и) ) таких, что

ф13(А(Ю) = ^(АОд)) - Tj(A(u)). Приведено достаточное условие конечнозначности через ограничение на функции ф.ц(А(и)) й более жесткий критерий в виде следующего утверждения.

Теорема 5.7. Если функции а^(и) являются полиномами, то линейная параметрическая задача оптимизации является конечнозначной на любом параллелепипеде Jk.

Анализируется и сравнивается с приведенным и еще одно понятие конечнозначности.

В заключение рассмотрено несколько иллюстративных примеров для случая к=2.

Публикации по теме работы.

1. Гордеев Э.Н. Устойчивость в задачах на узкие места в случае возмущения части элементов траекторий. В сб. Сборник работ по математической кибернетике.- М., ВЦ АН СССР,1981, с.121-142.

2. Гордеев Э.Н. Алгоритмы полиномиальной сложности для вычисления радиуса устойчивости в двух классах траекторных задач.- Журнал вычислительной математики и математической физи-ки. 1987,Т. 27, N 7, с. 984-992.

3. Гордеев Э.Н. Полиномиальные алгоритмы вычисления радиуса устойчивости для двух классов задач выбора.- Доклады АН СССР, 1987, Т. 297, N5, с.1040-1043.

4. Гордеев Э.Н. Полиномиальные алгоритмы вычисления радиуса устойчивости для широкого класса задач выбора.- В сб.: Методы исследования сложных систем., М., ВНИИСИ, 1988, с.4-7.

5. Гордеев Э.Н. Устойчивость решения в задаче о кратчайшем пути на графе.- Дискретная математика. 1989, т. I, N 3, с.39-46.

6. Гордеев Э.Н. Трудоемкость исследования устойчивости задач дискретной оптимизации. В кн.: Вопросы кибернетики: Дискретная математика. Методы и применение. M., НСК АН СССР, 1989,с. 41-87.

7.Гордеев Э.Н. Об оптимальных решениях некоторых задач

дискретной оптимизации.- Тезисы 5-й Гор. Конф. МУиС по проблемам киб. и выч. тех., М., ШО АСУ "Москва", 1986, с.51.

8. Гордеев Э.Н. Исследование устойчивости двух дискретных оптимизационных задач. В сб.: Проблемы вычислительной математики и автоматизации научных исследований. Алма-ата, Наука,1988, с. 39.

Э.Гордеев Э.Н., Леонтьев В.К. Оценки сложности табулирования траекторных задач.- Журнал вычислительной математики иматематической физики. 1985, т. 25, N 5, с. 1272-1275.

Ю.Гордеев Э.Н., Леонтьев В.К. Устойчивость в задачах на узкие места.- Журнал вычислительной математики и математической физики. 1980, т. 20, N 4, с. I07I-I075.

П.Гордеев Э.Н., Леонтьев В.К. Оптимизационные задачи на узкие места.- В сб.: Вопросы кибернетики. Комбинаторный анализ и теория графов. М., Сов. Радио, 1980, с. 5-29.

12.Гордеев Э.Н., Леонтьев В.К. Траекторные параметрические задачи.-Журнал вычислительной математики и математической физики. 1984, N 1, с. 37-46.

13.Гордеев Э.Н., Леонтьев В.К. Использование исследование устойчивости для решения задач выбора.- В сб.: Математические методы распознавания образов и дискретной оптимизации. М., ВЦ АН СССР, 1987, С.36-51.

14.Леонтьев В.К., Гордеев Э.Н. Качественное исследование траекторных задач. Кибернетика, 1986, N5, с. 82-90.

15.Гордеев Э.Н., Леонтьев В.К., Сигал И.Х. Вычислительные алгоритмы для нахождения радиуса устойчивости в задачах выбора.- Журнал вычислительной математики " и математической физики.1983, N 4,с. 973-979.

16.Гордеев Э.Н., Леонтьев В.К., Мамутов К.Х., Уразаев Р.П. Программная реализация методов исследования устойчивости для двух типов задачи коммивояжера в различных метриках.-В кн.:Вопросы кибернетики: Дискретная математика. Методы и применение. M., НСК АН СССР, 1989, с. 134-142.

17.Гордеев Э.Н. Исследование устойчивости некоторых задач выбора.- Тезисы 6-й Гор. Конф. МУиС по проблемам киб. и выч.тех., М.,НПО АСУ "Москва", 1987, с.44.

18.Гордеев Э.Н., Мамутов К.Х. Устойчивость в задачах на

зкие места в некоторого типа метриках.- Тезисы Респ. Семинара по дискретной оптимизации. Киев, 1985, с. 28-29.

19.Гордеев Э.Н., Липкин Л.И. О единственности решения некоторых комбинаторных задач выбора.- В кн.: Методы дискретного анализа в оптимизации управляющих систем. Новосибирск, 1989,вып. 49, с.13-31.

20. Гордеев Э.Н. Алгоритм вычисления радиуса устойчивости в задаче о кратчайшем пути.- Тезисы Респ. семинара по дискретной оптимизации. Киев, 1990, с. 13.

21. Гордеев Э.Н. Устойчивость в дискретных экстремальных задачах.- Дис.на соискание уч.ст.к.ф.-м.н., М., ВЦ АН СССР,1980.

22.Gordeev E.N., Leont'ev V.K. Estimations of the complexity of the tabulation for discrete extremal problems.-Proc. 12-th IFIP Conf. on System Modeling and Optimization. Abstr.1, Sept. 2-6, 1985, Budapest, 1985, p.207-208.

23. Гордеев Э.Н. Задачи выбора и их решение. - В кн.: Компьютер и задачи выбора. М., Наука, 1989, с. 5-49.

24.Гордеев Э.Н., Леонтьев В.К. Дискретные параметрические задачи.-Тезисы Всес. конф. по теор. киб., Новосиб.,1980, с.54-55.

25.Гордеев Э.Н., Леонтьев В.К. Задача выбора в условиях неопределенности. - В кн.: Компьютер и задачи выбора. М., Наука, 1989, с. 120-143.

26.Гордеев Э.Н., Леонтьев В.К., Тарасов С.П. Вычислительные алгоритмы нахождения радиуса устойчивости в задачах выбора.- Тезисы Всес. Симп. "Стат. и дис. анализ нечисловой информации. Экспертные оценки. Дискретная оптимизация". Алма-ата,1981, с. 251-252.

Э.Н.Гордеев Алгоритмический и постоптимальный анализ устойчивости решений задач дискретной оптимизации Подписано в печать 20.11.92 Формат бумаги 60x80 1/16 Тираж 100 екз. Заказ 132. Бесплатно Отпечатано на ротапринтах в ВЦ РАН.

117333, Москва, ул.Вавилова,40.