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

р г «АКАДЕМИЯ НАУК БЕЛАРУСИ ^ " Институт математики

2 ^ СЕН т5

УДК 519.1

БФИМЧИК НАТАЛЬЯ ЕВГЕНЬЕВНА

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННЫХ АЛГОРИТМОВ РЕШЕНИИ ЗАДАЧ'ДИСКРЕТНОЙ ОПТИМИЗАЦИИ И УСТОЙЧИВОСТИ ШЮГОКРИТЕЙМЛЬНЬК ТРАЕКТОРИЮ ЗАДАЧ

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискашэ ученой степени кандидата физико-математических наук

МИНСК - 1995

Работа выполнена в Белорусском государственном университете

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

профессор Вюличев В.А.

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

профессор Сотсков D.H. кандидат физико-математических наук, старший научный сотрудник Кравцов М.К.

Оппонирующая организация - Запорожский государственный университет

Защита состоится "cLD" Qtc7~J?SbJ{ 19$£"р. в /г часов на заседании совета по защите диссертаций Д 01.02.02 при Институте математики АН Беларуси (220072, Минск, ул.Сурганова,11)

О диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси

Автореферат разослан - / " с ем 199^"г.

Ученый секретарь совета по защите диссертаций кандидат физ.-мат. наук

JWcTwJveS- Астровский

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

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

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

Проблема выбора наиболее рациональных решений в реальных-задачах автоматизированного проектирования, планирования, экономики я других ваЕзшх областей неизбежно приводит к необходимости учета многих противоречивых требований. В результате адекватные математические постановки задач оказываются многокритериальны)® задача-ш (МКЗ) оптимизации. Особенность таких задач состоит в оценке качества решений по многим критериям. В этих условиях выбор наиболее целесообразного решения осуществляется из множества тесравнимых альтернатив. При этом необходимо учитывать такие ректоры, как неточность построения математических моделей реальных процессов, погрошость вычисления на ЭВМ, появление .лго-ритмов, состоящих из решения последовательности "близких" задач. Зсе это требует исследования устойчивости к таким возмущениям гараметров ШСЗ, которые сохраняют искомое множество яльторнптип.•

«

Подобные исследования проводятся, например, в ВЦ РАН, ИК АН Украины, Запорожском государственном университете.

Связь работы с крупными научнши программами, темами. Работ! выполнена в соответствии с темой "Изучение проблем дискретной ма тематики и математической кибернетики" N 451/28, включенной к I991-1995 г.г. в план НИР, выполняемой на кафедре УМФ мехашшо математического факультета Белгосуниверситета.

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

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

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

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

- исследовать разрешимость МКЗ о k-медаане графа в классе алге ритмов линейной свертки критериев.

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

- найти радиус и ядро устойчивости траекториях МКЗ.

Научная новизна. Найдены более точные (по сравнению с ран« известными) оценки качества градиентных екстремумов в задач! максимизации строго выпуклых функций на координатных решетка: Построен и обоснован ряд статистически аффективных алгоритм! решения задач размещения медиан и центров на взвешенном графе, доквзаны теоремы об асимптотической оптимальности и оптимальное в типичном случае получаемых решений. Доказана неразрешимое векторной задачи о k-медиане графа в классе алгоритмов лшюМк свертки критериев. Риервно исследована устойчивость множест: сильно пф^ктиип1х и множества слабо аффективных траекторий tu

малых возмущениях целевых функций в многокритериальной траекторией задаче с частными критериями вида MINSUM, Ы1МАХ и MINMIN. Выделено ядро устойчивости такой задачи, и найдены нижние достижимые оценки для радиуса устойчивости и радиуса ядра устойчивости.

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

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

Основные поло: ?ншг диссертации, выносише на защиту. В настоящей диссертационной работе получены и выносятся на защиту следующие результаты :

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

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

3. Доказана неразрешимость МКЗ о k-медиане графа в классе

алгоритмов линейной свертки критериев.

4. Исследовано поведение множеств сильно, слабо и собственно эффективных траекторий МКЗ при малых возмущениях целевых функций в векторной траекторной задаче с критериями вида mihsum, ышмах и ЫХЖШ. Найдены необходимые и достаточные условия, при выполнении которых малые изменения коэффициентов целевых функций, составляющих векторный критерий, не приводят к появлению новых эффективных траекторий.

5. Выделено ядро устойчивости векторной траекторной задачи. Получены нижние достижиые оценки для радара устойчивости и рада-уса ядра устойчивости.

Публикации, апробация работы, личный вклад. По теме диссертационной работы опубликовано 11 печатных работ. Основные результаты диссертации докладывались на VI конференции математиков Беларуси (Гродно, 1992), на международном семинаре "Discrete Optimization" (Веймар, 1994), на Пятом Межгосударственном семинаре "Дискретная математика и ее приложения" (Москва, 1995), на Conference of the European Chapter on Combinatorial Optimization (Познань 1995), на научных семинарах в ИТК АН Беларуси, Белорусском государственном университете.

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

Структура и объем работы. Диссертация состоит из введения, трех гл"в и списка использованных источников, включающего 98 наименований. Общий объем работы 80 страниц машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе на основе введенной меры строгой выпуклости целевой функции,заданной на координатной решетке (КР),исследуются некоторые свойства такой функции (раздел 1.1) и улучшаются ранее известные оценки погрешности градиентных максимумов (раздел 1.2).

В разделе 1.1 введены и исследованы два класса строго выпуклых функций, заданных на КР и обобщающих хорошо известные коор-динатно-выпуклые функции. Мера выпуклости вводимых здесь функций

определяется границами изменения элементов гессиана этих функций. Пусть н=(н,-<) - линейное упорядоченное дискретное множество

(цепь).Тогда КР нМхЧ^.....хп):х4е н, i=T7n) можно рассматривать как частично упорядоченное множество,в котором задано отношение порядка : хч у <=> z^-i ус, i=T7n. Будем считать, что каадая цепь н имеет минимальный элемент, т.е. нуль о, и поэтому точка

6= (о.....о)с нп является минимальным элементом КР Нп.

•Будем говорить, что функция f(x), определенная на КР нп,принадлежит классу 31q = 3tQ(Hn), если существует такое действительное

„ г г

число р>0, что

Ди КхК-р V 1бНл, i,d=T7n, (1)

где ди г(х)» д{ i(x), д[ t(x)=£(%*(x))-f(x),

n*(x)=(xi.....xi l,x*,xut,...,xn), x* - элемент из КР Нп,

непосредственно следующий за г. .т.е. такой,что 3 x'eHsx^-t х*-< х*.

При р=о получаем известный класс координатно-выпуклых функций 13].

Отметим, что величину д* t(x) принято называть (правым) i-

градиентом функции f(x):Hn-» к, а неравенства (1) определяют верхнюю границу изменения элементов гессиана функции i(x).

Найдено несколько эквивалентных определений функций из клас-

п

са ЭТр (теорема 1.2 К а также предложен способ конструирования таких функций.

Teopeua I.I Для всякого ne m функция f(x) принадлежит классу 3tp тогда и только тогда, когда она представила в виде

f(x)=g(x)- |р Е £h(*.)h(x.) Vi6H\ i=i j=t 3

где g(x)e <Jt£, h(x.)=|{zt -.СИ z.-( x.)|-1.

Будем говорить, что функция x(x):Hn- R принадлежит классу Кр = Ю1р(нп), если существует такое действительное число р>о, что

ди*(хК-р V хе Нп, i=T7n,

i^fliX О V xe Hn. i.MTn.

В разделе 1.2 рассматриваются задачи максимизации неубывающих функций i(x) (хч у * f(x)<f(y)) из классов Sip и Bip на множестве PC Н".

Конечное множество рс нл будем называть р-множеством, если оно обладает следующими свойствами:

1. ве Р.

2. [9, x]={ze Нп: z-к х}с Р V хе'р.

Пусть х* - глобальный максимум функции f (х) на р-множестве

Р, а х3 - градиентный максимум этой функции на том же р-множестве

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

Ниже будем использовать широко известные понятия высоты, ко-высоты и кривизны частично упорядоченного множества (см., например, [3]).

Теорема 1.3 Глобальный максимум х* и градиентный максимум х9 всякой неубывающей на р-множестве р функции i(x)e ftp связаны соотношением Г(х*) $ A(r,h)i(x3)+(1-A(r,h))i(e)-B, где A(r,h)= = (1-(1-1/h)rrl, В = *''0(3h-1-2rA(r,h)), h=h(P) и r=r(P) -соответственно высота и ковысота р-множества Р.

Те рема 1.4 Глобальный максимум х* и градиентный максимум х9 всякой неубывающей на р-множестве р с кривизной а = а(р) функции

f(x)e Кр (Г(в)=0) связаны соотношением f(xa)4f(x3)(l+ -п),

если ctn, где г=г(Р) - ковысота р-множества Р.

При р=о оценки, приведенные в теоремах 1.3 и 1.4, совпадают с известными оценками из [31, а в случае строгой выпуклости целевой функции f(x) (р>0) оценки из [3] улучшаются, когде 3h>l+2rA(r,h) (теорема 1.3) и г>ап (теорема 1.4).

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

В разделе 2.1 рассматривается следующая задача. Задан полны!

n-вершинный взвешенный орграф о с множеством занумерованных вершин YG={i,2,...,n), п>з. Это значит, что кавдой упорядоченной

паре вершин (i,i), i.j=TTn ставится в соответствие дуга орграфа с,которой приписан вес w(i,j)e ш, если и w(i,i)=o.

Пусть к - фиксированное число из множества Q(n)={l....,п-1>, VkcYG, |vk|=k.

Введем функции b(V. )= £ w(i,V ), t(Y ) * max{w(i,V ):ie VO), ieva

где w(i,Vk) = min {w(l,j)t Je Vk>.

Задачу нахождения подмножества v"c vg, |v*|=k, такого что ß(V*)« s(vk/ V Vkc yg (t(v*)< t(vk) V vkc yg) назовем задачей Afc (Bfc) размещения k медиан (центров) в орграфе о. Элементы множества v* называются медианами (центрами) орграфа g. Задачи ак и вк являются NP-трудными, поскольку к ним легко сводятся известные HP-трудные задачи о k-медиане и к-цепгре реберно и вершинно взвешенного графа [6].

Рассмотрим следующий алгоритм фк. Множество вершин орграфа

YG разобьем на два подмножества V1 и Y2 так, что |V1 |=И. |V2|=n-k. Алгоритм состоит из n-k шагов. На каждом шаге фиксируется новая вершина i из Y2, и выбирается дуга (i,J), Je v1 минимального веса. Трудоемкость алгоритма - 0(nz), а результатом его работы является псрытиа орграфа G к звездами, которое можно рассматривать как допустимое решение задач Ак и Вк. Оптимальное

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

Пусть 3t(n,R) - множество всех полных n-вершинных взвешенных орграфов, у которых каадая дуга (i,j), имеет вес w(i,

e{i,2,...,R), а Jtk(n,R) - множество всех орграфов из 3t(n,R), для каждого из которых алгоритм фк строит покрытие к особыми звездами. Под особой звездой будем понимать либо изолированную вершину, либо звезду, которая состоит из дуг, заходящих в центр

звезда и имеющих вес, равный единице.

При асимптотическом подходе (при п - со ) будем предполагать, что число медиан (центров) к растет вместе с ростом числа п. Поэтому множество возможных значений для числа к имеет вид множества функций от п : Qg(n)={ [g],[g]+l,...,n-l }, g=g(n)<n, g(n) -» «о при п. - оо.

Как обычно, (см., например, [7]) будем говорить, что алгоритм фк, ke Qg(n), для почти всех орграфов Ge 3t(n,R) строит

оптимальное решение задач Afc и вк, если у.ъ |3tk(n,R)|/|9Kn,R)|=l.

Пусть 7 = 7(n)< n/ln п, у(п)- «> при п - со. Теорема 2.1 Если g=xx/ln п и существует такое натуральное число п0, что R< n/(ln n(ln n+f)) V n> n0, то при любом ke Qg(n)

алгоритм фк для почти всех орграфов Ge ¡R(n,R) строит оптимальное

решение задачи Ак (Вк) размещения к медиан (центров) в орграфе.

В разделе 2.2 рассматривается вопрос существования асимптотически оптимального решения задачи размещения к медиан в полном взвешенном графе G=Kn=(VG, ^ ) с весами ребер w(e):EG - ш.

Í.JK и прежде, к - фиксированное число из множества Q(n)={1, 2,...,n-1}, Vkc VG, |Yk|=k.

Введем функцию t (v.)= £ min (w(i,J):ie v.}.

jevc

Задача Dk размещения k медиан в графе G состоит в нахождении

подмнож зтва v*c vg, |V*|=k, такого что r(v*)$ r(vk) v vkc vg,

Элементы v*, как и раньше, - медианы графа G.

Множество Q(n) разобьем на два подмножества Q1(n)={i,2,..., [n/2]} И Qjj(n)={[n/2]+1,...,n-1}.

Алгоритм фк, ke Qt(n) основан на принципе "иди в ближайшув

медиану" и состоит из [n/k] шагов, на каждом из которых находиэ совершенное паросочетание некоторого двудольного подграфа исходного графа G. Если ke Q2(n), то алгоритм фк состоит из п-]

шагов. На каждом шаге q фиксируется непокрытая на предыдущи: шагэх вершина iqe vg и выбирается ребро (iq,jq), j4*{ilP...,iq)

минимального веса. Трудоемкость алгоритма - о(пг). Результата работы алгоритма фк, ke q(n) является покрытие полного граф

с, состоящее из к звезд, которое можно рассматривать как допустимое решение задачи Как и прежде, под оптимальным решением

задачи Бк будем понимать покрытие полного графа 0 к звездами с

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

Фк

его ребер), построенного с помощью алгоритма фк обозначим ъ (О),

а вес оптимального покрытая - и*(О).

Пусть и (п.и) - множество всех полных п-верпшнных взвешенных графов, у которых кавдое ребро имеет вес *(е)е {1,2,...,Н}.

Как обычно [7]. будем говорить, что алгоритм фк для почти '

всех графов ее и(п,Ю строит асимптотически оптимальное решение задачи э., если существует такая последовательность е »

К Г»

ф

= еп(11,к)> о, 1^8 еп= О, для которой свойство г к(0)<(1+еп)а*(О

выполняется для почти все графов и (п.и).

Теорема 2.4 Алгоритм фк для почти всех графов <3€Ц(п,11) строит асимптотически оптимальное решение задачи Г,, размещения к медиан в графе, если выполняется одна из следующих альтернатив :

(a) ке (Э^п), й $ к/(ф(п)1п к),

(b) ке а2(п), И ^ (п-к)/(<р(п)1п (п-к)),

где ф = ф(п) - монс энно возрастащая функция, ф(п)= «>.

В третьей главе рассматриваются многокритериальные задачи (МКЗ) дискретной оптимизации.

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

Пусть Е={в1,...,вт} - конечное множество произвольной природы, т - некоторая совокупность непустых подмножеств множества Е, называемых траекториями. На множестве В зададим векторную весовую

функцию (ВВФ) Ив)=(|?,(в),...,«м(в))б к", щ> 2, а на множестве

траекторий т - векторную целевую функцию (ВЦФ) F(t)=(Pl(t),...,PN(t)),

частные критерии которой минимизируются. Будем предполагать, что ВЦФ F(t) может состоять из критериев трех видов:

МШБШ Ps(t)= Е we(e) - пф!

(линейный критерий) е€Ц

1ШШХ Pe(t)= Ws(e) -» т|д

(критерий "узкого" места)

МИШИ Fg(t)= m^ we(e) - m^n

Обозначим через I , I и I . множества тех чисел из L„=

г sum* шах min N

={1,2.....Ю, которыми занумерованы соответственно критерии

MINSUM, MINMAX И 1ШШШ.

Траектория te т называется собственно эффективной (или, иначе, парето-оптимальной), если j te т : F(t) £ F(t), F(t) * F(t). Траектория te т называется сильно (слабо) эффективной, если Jä te Т: p(t)^ P(t), t ^ t, (F(t) > F(t)). Множества сильно эффективных, собственно эффективных и слабо эффективных траекторий обозначим соответственно через Qj.Q2.Q3.

Для всякого ie l3 под N-критериальной (к^ 2) траекторной

задачей z" будем понимать задачу нахождения множества . Qe, при

условии что ВЦФ i(t)=(P (t),F (t),...,F (t)) представляет собой

произвольную комбинацию критериев вида мшбш, minuax и uinmin. ВВФ w(e) удобно представлять в виде матрицы V/=ll wglt0Nxm с

элементами wek= we(ek). Если предположить, что множества Е, т,

I ,1 , I . фиксированы, то матрица we RNm может служить для

sun max mi п * *

индексации задачи z". Поэтому в дальнейшем N-критериальную траек-торную задачу будем обозначать z"(v»), значение в-го критерия Fg(t) - через Fs(t,w), ВЦФ F(t) - через f(t,W), а множество Qt -через Q.(w).

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

метрику, т.е. под нормой матрицы в = íbgkte к"1" будем понимать число UBI = max {Jbek|:se ln, ke Ln). Пусть !B(e)={ Be o?Nn: ÍBIke }, e>0.

Задачу z"(w), ie ьз, назовем устойчивой, если существует такое число е>о,что выполняются включения Qt(w+ß)c Q¿ (W) V ве Я5(е).

Очевидно, что задача z"(w), ie ъз устойчива, если (w)=T. Поэтому в дальнейшем будем предполагать,что Q¿ <W)=T\Qi (W)*0.

Группа теорем (3.1 - 3.3) дает необходимые и достаточные условия устойчивости задач z"(w), ie ьз.Приведем одну типичную формулировку.

Теорема 3.1 Для того, чтобы N-критериальная траекторная задача z"(w ) была устойчивой, достаточно, а в слу^е, когда ia =bN, и необходимо, чтобы выполнялось равенство Q2(W)=Q3(W). -.

Подобные результаты ранее были получены для МКЗ целочисленного программирования с линейными частными критериями (см.обзор [8]).

Следующая теорема дает простые достаточные условия устойчивости задач z"(W) и z^(W) в случае отсутствия в ВЦФ критериев вида MINSUM.

Теорема 3.4 Пусть lmQXu lni =IN. Если каадая строка матрицы

w состоит из попарно различных элементов,то каадая из задач z"(W)

и z"(w) устойчива.

В разделе З.з исследуется радиус устойчивости МКЗ z"(w), ie

е l , под которым по аналогии с [9], где введено понятие радиуса устойчивости однокргериальной задачи дискретной оптимизации, понимаем число p.(W)=sup {e>0:Qi (W+B)c Q^W), V Be ®(e)}, если

задача z"(w) устойчива и p (w)=o в противном случае.

Введем обозначение Ф.(W)= min шах rain £g(t1»t2)»

ttdS.(W) tzeT(tlfff) вёГ^

ie L3, где T(tl(W)={te T : ?(t,WK P(tltW)},

E^VV = sup{ s>0:Pg(t1.W+B)>Pg(t2,W+B) V Be ®<e) >.

если Ps(tlPw)> pg(t2,w). Причем будем считать, что ?g(tt,t2) = о, если Pe(t1,w)=Ps(t2,w).

Теорема 3.5 Для радиуса устойчивости р.(W)' задачи z"(w), We RNm, ie ьз справедлива оценка снизу

р. (w)£ fl^w), достижимая при igum=bN.

Теорема 3.6 Если Inoxu Imin-Lw (lgum=<s), то для радиуса устойчивости задачи z"(W), We RNm,ie L3 справедлива оценка

р. (W)> ^ min min |w . - w . I. 2 ^ *j<k«i 1 SJ ak'

В разделе 3.4 исследуется вопрос сохранения свойства эффективности траектории при "малых" возмущениях весовых функций задачи.

Доказана теорема 3.7 о том, что для любой задачи z"(w), tos rnm, Ig l , найдется такое число e=e(w,i)>o, что q^w+b) л П at(W)*0 V ве а$(е).

Для всякого ie L3 под ядром устойчивости задачи z"(w) будем понимать множество Ji(V))=tte Qt(W): 3 e=e(t)>o, te q^w+b), V Be e»(6)}.

Теоремы 3.8 - 3.10 устанавливают критерии принадлежности траектории ядру устойчивости ie L3. Приведем формулировку

следствия из .этих теорем.

Следствие 3.2. Для любой матрицы w е rNi" справедливы соотношения 'Jt (W) 2 Qt (W), ie I>3, причем

^WQ^w).

J1(W)=J2(W)' 9СЛИ 1вит* ®»

J1(W)=J2(W)=J3(W). если Ieu,,=v

Пусть е>0. Ядром е-устойчивости задачи z"(w), 1еъз будем называть множество J®(W)={te q (w):te Q.(W+B) V Be S(e)>.

Очевидно, что J®(W)C Q.(W), V ie Ьэ, 6>0, We R14™. Найдены необходимые и достаточные условия принадлежности траектории из Q.(w) ядру е-усгойчивости df(W) задачи Z?(W), ie L3 (теоремы 3.11 - 3.13).

Радиусом ядра устойчивости задачи Z^(ff), ie ьз назовем число

p*(W)=sup { е>0 : J®(W)* 0 }. Если J?(W) = 0 V s>0, то p*(W)=0. Введем обозначение

Ф*(W)= max min max .t^), ie L3.

txeQ.(W) t eOMt^} s€Ln

Теорема 3.14 Для радиуса ядра устойчивости p*(w) задачи z"(w), v? е rn™, ie ьз справедлива оценка снизу

p*4w) » Ф*(W),

причем р*(»)=Ф*(Ю v w е rnn,

p*(w)=®*(w) v w е RNm, если I * 0.

z z sun

р!(1/?)=ф!(и) V w e rNm, если I =ь„.

r3 3 sum N

В разделе 3.5 рассматривается асимптотический подход к решению МКЗ покрытия полного графа определенным количеством звезд по аналогии с подходом к решению однокритериальной задачи (см. раздел 2.1).

Пусть G=Kn=(v,E) - полный п-вершинный граф, у которого каждое ребро взвешено N (ы>1) натуральными числами wa(e), в=Т7П.

Такой граф назовем и-взвешенным.

Пусть T=Ct> - множество всех остовных лесов графа G, состоящих к звезд. На множестве т определим ВЦФ F(t) с любой комбинацией критериев вида МНЕ UM, mikmax, мшш (см. раздел 3.1). Под N-критериальной задачей ск покрытия полного п-вершинного

N-взвешенного графа G к звездами (1<кСп-1) будем понимать задачу

нахождения полного множества альтернатив (ПМА) i, которое определяется как подмножество паретовского множества т = {te т : ¡4 t е е т, P(t)£ F(t), F(t) * F(t)} минимальной мощности и такое, что

Р(т)=р(5), где F(T*)={F(t): te Т*}, Т*С Т.

Алгоритм ак действует аналогично алгоритму фк (см. раздел

2.1), за исключением того, что на каздом шаге алгоритм а. выби-

N

рает ребро ее е, у которого суммарный вес £ w (е) минимальный.

~ 3=1 3

Трудоемкость алгоритма afc - o(Nn ).

Пусть 3t(N,n,R) - множество всех полных п-вершинных N-взве-шенных графов с весами ws(e)e {1,2,...,R}, в=Т7И, где R=R(n) -либо константа, либо неограниченно растущая функция от п. Введем также функцию <p(n)=o(Vn/ln п )-» со при n - а>.

1 Теорема 3.15 Если g=g(n)=n/<p(n) и функция R=R(n) такова, что rrj$p(n) v ne in, то при любом ke q (п) (см. раздел 2.1) алгоритм

о

ак для почти всех графов 3t(N,n,R) строит одноэлементное ПМА т

МКЗ Ск с ВЦФ, состоящей из любой "комбинации критериев вида

minsum, м1шах, м1шш.

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

Известную задачу о k-медиане реберно взвешеного графа G [6] можно интерпретировать как задачу оптимального размещения на атом графе к пунктов обслуживания, при котором сумма кратчайших расстояний от вершин графа G ; ближайших к ним пунктов принимает минимально возможное значение. Если каздое ребро графа с взвешено несколькими числами, то естественно возникает многокритериальная постановка задачи о k-медиане графа G с линейными критериями. В разделе 3.6 доказывается неразрешимость этой задачи в классе алгоритмов линейной свертки критер"ев.

ВЫВОДЫ

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

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

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

3. Установлено, что МКЗ о k-медиане графа неразрешима в классе алгоритмов линейной свертки критериев.

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

5. Выделено ядро устойчивости векторной траекторной задачи, и найдены нижние достижимые оценки для радиуса устойчивости и радиуса ядра устойчивости.

Список цитированной литературы

1. Глебов Н.И. Об одном классе задач выпуклого целочисленного программирования // Управляемые системы.-1973-вып.11.-С.38-42.

2. Емеличев В.А., Овчинников И.Г, К теории экстрен ма на координатных решетках // Докл. АН БССР.-1933.-Т.27, N 7.-С.581-583.

3. Ковалев М.М. Матроиды в дискретной оптимизации. - Минск : Изд-во Университетское, 1987. - 222 с.

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

5. Перепелица В.А. О двух задачах из теории графов // ДАН СССР. - 1970. - Т.194, N 6. - С. 1269-1272.

6. Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978. - 432 с.

7. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика.- 1994.- Т.66, н 1. - С. 3-33.

8. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Исследование устойчивости задач дискретной оптимизации // Кибернетика и системный анализ. - 1993. - И 3. - С. 78-93.

9. Леонтьев В.К., Гордеев Э.Н. Качественное исследование троекторных задач // Кибернетика. - 1986. - И 5. - С. 82-89-

Основные положения диссертации опубликованы в работах

1. Ефимчик Н.Е. К оценке погрешности градиентного решения в

одной задаче дискретной оптимизации // Тез. докл. vi конференции математиков Беларуси. - Гродно, 1992. - С. 73.

2. Ефимчик Н.Е. О неразрешимости многокритериальных задач о k-медиане графа в классе алгор—гмов линейной свертки критериев // Ред. »урн. "Изв. АН Беларуси. Сер. физ.-мат. наук".- Минск, 1993.

- 18 е.- Деп. в ВИНИТИ 30.03.93, N 771-В93.

3. Ефимчик Н.Е. Оценка погрешности градиентного решения в дискретной задаче максимизации строго выпуклой функции на множестве с заданной кривизной // Вести. Белорусского ун-та. Сер.1:физ. мат. мех. - 1993. - N 3. - С. 41-44.

4. Emelicev V.A., Efimchik N.E. Ein asymptotischer Zugang zur Losung des k-Median-Problem über Graphen //Preprint der Otto-von-Guericke-Universitat Magdeburg,Fak. fur Math.-1994.-N 2.-16 в.

5. Ефимчик Н.Е., Рамазанов А.Б. О погрешности градиентного экстремума строго выпуклой функции дискретного аргумента // Ред. журн. "Изв. АН Беларуси. Сер. физ.-мат. наук".- Минск, 1994.

г- 11 е.- Деп. в ВИНИТИ 10.03-94, И 572-В94.

6. Emelichev V.А.,Efimchik N.E. Greedy Algorithm for Solving in Typical Case Problems of Location of Medians and Centers on a Graph // Workshop on Discrete Optimization. - Weimar, 1994.

7. Ефимчик Н.Е. Асимптотический подход к решению многокритериальной задачи покрытия графа звездами // Ред. журн. "Изв. АН Беларуси. Сер. физ.-мат. наук". - Минск, 1994. -юс.- Деп. в ВИНИТИ 24.06.94, N 1580-В94.

8. Girlich Е.,Emelicev V.A..Efimchik U.E. Uber einen schnellen Algorithmus, der das Median-vmd Zentren-Problem über einem vollständigen Orgraphen fast immer lost // Preprint der Otto-von-Guericke-Universitat Magdeburg, Pak. fur Math.-1994-- N 24.- 8 e.

9- Емеличев В.А., Ефимчик Н.Е. Асимптотический подход к задаче о k-медиане графа // Кибернетика и систеный анализ. - 1994.

- N 5. - С. 109-117.

10. Ефимчик Н.Е., Подкопаев Д.П. Некоторые виды устойчивости траекторных задач векторной оптимизации // Ред. журн. "Изв. АН Беларуси. Сер. физ.-мат. наук".- Минск, 1994 . - 15 с. - Деп. в ВИНИТИ 06.12.94, N 2799-В94.

11. Ефимчик Н.Е., Подкопаев Д.П. Ядро устойчивости траектор-ной задачи дискретной оптимизации // Тез. докл. Девятой Всероссийской конференции "Математическое программирование и приложения". - Екатеринбург, 1995. - С. 92-93.

РЕЗЮМЕ

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

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

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

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

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

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

- найдены необходимые и достаточные условия устойчивости множеств сильно, слабо и собственно эффективных траекторий при малых возмущениях целевых функций в многокритериальной траекторной задаче с частными критериями вида шмзш, Ы1ШАХ и М1Ш1Ы.

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

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

РЭЗШЭ

дасертацыйнай работы Яф1мчык Наталл1 Яугенауны "Даследванне эфектыунасЩ прыбл1каных алгарытмау рашэння задач дыскрэтнай аптым!зацы1 1 устойл1васц± многакрытэрыяльных траекторных задач" Югочавыя словы: градыентны алгарытм, ыедыяна 1 цэнтр графа, многакрытэрыяльная (вектарная) задача, парэтауск1 оптымум, устой-л1васць задачи, радыус 1 ядро устойл1васЩ.

Мэтай дасертацыйнай работы з'яуляецца распрацоука статыстыч-на эфектыуных матадау рашэння задач аптым!зацы1 на дыскрэтных структурах 1 знаходасанне умоу, пры выконванн! як!х многакрытэрыяльная задача з'яуляецца усто1Ш.вай да узбурэнняу некаторых яе параметрау.

У дысертацы! выкарыстаны метады матэматычнага праграм!раван-ня, выпуклага 1 камб1наторнага анал1за, таорЩ графау, тэоры1 1мавернасцей, Еектарнай аптым!зацы1. Асноуныя еынзлс1 дысертацыз.:

- атрыманы новып ацэнк! ,якacцi градыентных экстрэмумау у задачах макс1м!зацы1 строга выпуклых функцый на каардынатных рашотках.

- пабудаваны 1 абгрунтаваны статыстычна эфектыуныя алгарытмы рашэння задач размяшчэння медыян 1 цэнтрау на узважаным графе.

- выяулена, што многакрытэрыяльная задача аб к-медыяне графа невырашалька у класе алгарытмау лзлейнай звертк1 крытэрыяу.

- знойдзены неабходаыя 1 дастатковыя умовы устойл1В8сщ "мноствеу моцна, слаба 1 уласна эфектыуных траекторий пры малых узбурэннях мэтавых функцый у многакрытэрыяльнай траекторнай задачы з асобны-м! крытэрыям1 В1ДУ М1ШиМ, Ы1КМАХ 1 ЫХШШ.

- вылучына ядро устойл1васц1 вектарнай траекторнай задачы, 1 знойдзены Н1Ш1я дасягальвдя ацэнк! для радиуса устойЛ1васц1 1 радыуса ядра устойл1васц1.

1дэ1 доказу статыстычнаГ эфектыунасц! распрацаваных алгарытмау ыогуць быць ужыты пры пабудове 1 абгрунтаванн! новых метадау камб!наторнай аптым1зацы1. Магчымасц1 для прымянення вын1кау дысертацыЛ, як!я датычацца устойл!васц1 многакрытэрыяльнай задачы, абумоул1ваюццэ такШ1 фактарам1, як недакладнасць зыходных даных, • неадэкватнасць матэматычт эй мадэл1 рэалышм працэсам, х!бнасць выл!чэнняу на ЭВМ 1 1нш. ' 1

RESUME

of the thesis "Investigations of the efficiency of the approximate algorithms for solving dificrete optimization problems and investigations of the multicriterion trajac-tory problemB stability" by Yefimchik Natalya Yevgenyevna Key words: gradient algorithm, median and center of a graph, multicriterion (vector) problem, Pareto optimum! stability, stability radius, stability kernel.

The purpose of the thesis is to create the efficient methods for solving optimization problems on the discrete structures and to find the conditions under which the multicriterion trajectory problem is stable to perturbations of some its parameters.

The methods of mathematical programming, convex and combinatorial analysis, graph theory, probability theory and vector optimization have been used in the theBis.

The main results of the thesis are following

- the new qvUity estimates of gradient extrema in maximization problems with strictly convex functions on the coordinate lattices have been obtained.

- the statistically efficient algorithms for solving problems of median and center location on weighed graph have been created.

- it is established, that multicriterion k-median problem is unsolved in the class of linear convolution algorithms.

- the necessary and sufficient conditions of stability of the Btrongly, weakly and properly efficient trajectories Bets to email perturbations of objectiva function in vector problem (with UINSUM, MINMAX and MINMIN criteria) have been found.

- the stability kernel of multicriterion trajectory problem has been separated, and the attainable lower bounds for stability radius and stability kernel radius have been obtained.

The proof ideas 3f the developed algorithms statistical efficiency can be used in the creation of new combinatorial optimization methods. The possibilities for application of thesis results, which touch to stability of multicriterion problem, are conditioned on such factors as" initial data inaccuracy, inadéquation of mathematical model to real processes, computer calculation error etc.