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

запорожский государственный университет

О ч . 1 .

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

козина галина леонидовна

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

05.13.16. - Применение вычислительной техники математического моделирования и математических методов в научных исследований.

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

Запорожье - 1994

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

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

профессор ПЕРЕПЕЛИЦА В.А. Официальные оппоненты: доктор физихо - математических наук,

профессор ШЕЛИЧЕВ В.А. кандидат физико-математических наук, доцент ДЕИНЕКО В.Г.

Ведущая организация: С.-Петербургский институт информатики и

автоматизации РАН.

Защита диссертации состоится " " 199 У г. в.

на заседании специализированного совета К 063.52.02 при Запорожском государственном университете по адресу: 330600, г.Запорожье, ул. Жуковского, 66 ауд.

ЯГ

С диссертацией мохно ознакомиться в библиотеке Запорожского государственного университета.

Автореферат разослан " .м^Ла^л 1Э9У"г.

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

*

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

АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. Диссертационная работа посвящена исследованию математических моделей и методов решения оптимизационных задач с векторными целевыми функциями на многоцветных графах, а также исследованию оптимизационных задач на графах о интервальными параметрами.

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

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

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

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

- А -

основном=праменитвльна к задаче^линеййОго"=г^грашированИя .- В -настоящей работе предлагается исследование дискретных оптимизационных задач о интервальными параметрами.

ТП^лт. РАБСКИ. Основные направления настоящей работы состоят в следующем:

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

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

3. Исследовать приближенные алгоритмы для решения оптимизационных задач* на многоцветных графах.

4. Исследовать сложность и полиномиальную разрешимость оптимизационных задач на ■ графах с интервальными параметрами.

МЕТОДИКА ИССЛЕДОВАНИЯ. В работе используются аппарат теории комбинаторного анализа, теории, разбиений при отыскании оценок мощности множеств альтернатив многокритериальных задач, аппарат теории вероятностей при исследовании применимости приближенного алгоритма решения задачи коммивояжера.

ААУЧНАД НОВИЗНА. В диссертационной работе "получены нижниеоценки максимальной мощности множеств альтернатив для векторной задачи коммивояжера на многоцветных графах при различных соотношениях числа цветов и допустимого, расстояния, для векторных задач об остовных деревьях и о совершенных паросочетавиях на многоцветных графах. Исследована сложность указанных задач в случав весовых критериев. Установлены условия, при которых невозможно построить полиномиальные алгоритмы для решения векторных задач на многоцветных графах, т.е. задачи оказывается труднорешаемыми.

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

Исследована применимость алгоритма "иди в самый удаленный

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

Исследована сложность интервальных оптимизационных задач на графах- Установлена труднорешаемость интервальных задач о коммивояжере,' об остовных ' деревьях, о совершенных паросочетаниях. Найдены постановки интервальных задач на графах, при которых достигается полиномиальная разрешимость.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Разработанные в диссертации модели и. методы могут быть использованы для решения задач автоматизированного проектирования, при конструировании радиоэлектронных систем, задачи землепользования.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Предложенные в работа метода использованы при разработке математического обеспечения для решения задач с интервальными параметрами в Запорожском машиностроительном институте.

ПУБЛИКАЦИИ И АПРОБАЦИЯ РАБОТЫ. По теме диссертации-опубликовано 16 печатных работ. Основные результаты настоящей диссертации докладывались и обсуждались на школе-семинаре "Дискретные модели в теории управляющих систем" (Москва, 1991), школе-семинаре "Синтез и сложность уйравляющих систем" (Ташкент, 1991), Совещаниях по интервальной математике (Абакан, 1989, Абрау-Дюрсо, 1992), школах-семинарах "Дискретная оптимизация" (Алушта 1983,1991), 12-й научной конференции "Системы программного обеспечения решения задач оптимального планирования" (Нарва-Лыэссу, 1992), школе - семинаре "Комбинаторная оптимизация" (Миргород, 1992), Международной конференции по интервальным и стохастическим методам в науке и техника (Москва, 1992), Международной школе "Проектирование автоматизированных систем контроля и управления сложными объектами" (Туапсе, 1992), IV Межгосударственном семинаре по дискретной математике и ее приложениям (Москва, 1993), научной конференции "Математическое программирование и приложения" (Екатеринбург, 1993), Международной конференции "Теория приближений и задачи вычислительной математики (Днепропетровск,

- б -

1993), Международном Конгрессе по компьтерным системам и прикладной математике (С.-Петербург, 1993), Международной конференции по моделированию и имитационному моделированию (Львов, 1993), научно-исследовательском семинаре по теории графов и их приложениям (Одесса, 1993), а также на научных семинарах Института кибернетики АН Украины (Киев) и др.

. СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, трех глав, заключения, приложения и списка литературы из 80 наименований. Общий объем работы - 110 страниц.

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

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

ПЕРВАЯ ГЛАВА диссертации посвящена исследованию нижних оценок сложности задач на многоцветных графэх. Рассматриваются задачи о коммивояжере, об остовннх деревьях, о совершенных паросочетаниях.

В общем случае постановка векторной оптимизационной задачи состоит в следующем: дан граф 0(У,Е), в котором множество вершин V, |У|=п, разбито на т непересекающихся подмножеств Ук ,

т

|7к|=пу, е г\=п, где 7к состоит из вершин, окрашенных в цвет к. к =1

В этом случав граф С называют я-цветным и обозначают через

.....7т,Е).

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

•о совершенных пэросочетаниях являются соответственно остовное дерево и совершенное паросочетание, состоящие из ребер, инцидентных вершинам разного цвета. Таким образом, допустимое решение я в каждом случае представляет собой остовный подграф ^-(Y.E,), Es Е.

Обозначим через х = {*} множество всех допустимых решений. Кзздое .ребро &=Е графа G взвешено N весами т»у(е)5:0, v=»1 ,N, т.е. задано N-взвешивание графа С.

На мноадстве х определим Еекторную целевую функцию (ВЦО)

?fï)»t?,W.....

состоящую из критериев весового вида

Fv<*)- Z wv(e) — min, v-T7ïï.

e«E

X

Векторная целевая функция ?(х) определяет собой паретовское множество (ПМ) X. Искомым решением задачи является полное множество альтернатив (ГШ). ГОДА называем подмножество X s X. удовлетворягщее условии: мощность }Х| минимальна при выполнении равенства ?(Х) =» ?(Х), где ?(Х ) => { ?(*) : х*Х ) V X's X . .

Введем обозначения:

S(n) - множество всех n-вершинных графов С; jj.(G,N) -

максимальная мощность ПМА, которая определяется по всевозможным

N-взвешиваниям графа G; ц =» max u(G,N). .

п)

Большой интерес предстааляэт вычисление в явном виде максимальной мощности ПМА ц, которую мохно рассматривать в качестве нижней оценки вычислительной сложности исследуемой

задачи.

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

А

мощность ПМА р. растет экспоненциально с ростом размерности • задачи, то задача является труднорешаемой.

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

А

следующие значения исследуемых максимальных мощностей 1ША ц..

Теорема i.а. Если допустимое расстояние i=m, то при Ífe2 для векторной задачи коммивояжера на m-цветных графах

G=(Vt.....Vm,E) в s(n), таких что 1VJ = | = р а г v k=T"7^

максимальная мощность ГШ достигает значения

Í* = 2р (р1Г(«-1)1.

Теорема i. з. Если допустимое расстояние i=m-1, то при №:2 для векторной задачи коммивояжера на и = j - цветных графах

G-(V4.....vm>E> е 5(П), 2 е г, таких что |VJ=2 v

максимальная мощность ПМА достигает значения • ц - г-1 («-DI (u^, + u^),

где um- in—й член последовательности чисел Фибоначчи и

1 г / лЧ"1» \ 1+-Г5

и = —— ( а - (-а) ), а => —у—.

-/15 ¿

Для трехцветных графов с допустимым расстоянием г =2

справедлива

Теорема i , s. Если допустимое расстояние г»2, то при №=2 для векторной задачи коммивояжера на трехцветных графах G-(VitVa,Vt,B) * S(n), таких что |VJ =. § = р е г, k=l,2,3, максимальная мощность ПМА достигает значения

С 1зКП+3Н2з3)гР-гз,

з-0

где есть наибольшее целое, не превосходящее а.

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

Для векторной задачи об ос товных деревьях получено значение максимальной мощности ПМА при любых соотношениях числа вершин одного цвета п^ > О, к=И

Теорема 1.11. При для векторной задачи об остовных деревьях на т-цветных графах ,... Лт,Б) а $(п), 1=гцс>0, к=1 ,т, максимальная мощность ПМА достигает значения

Л ™ п.-1

ц » п • п (п-а )

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

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

Во ВТОРОЙ ГЛАВЕ предлагаются алгоритмы решения задачи коммивояжера на многоцветнных графах. Алгоритмы применяются к

задаче коммивояжера на «-цветном полном графе .,Ут,Е)

а у(п), |Ук| • | « р « г, к=>Т7£, взвешенном весами я(е), е«Е, с допустимым расстоянием 1=я и целевой функцией (ЦФ)

?(х)- е я(е). (I)

е«Е

3

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

Кроме точного алгоритма для задачи коммивояжера на многоцветных графах, рассматривается приближенный алгоритм "иди в самый удаленный город" с весовым критерием (I) на максимум. Указанный алгоритм исследовался в работах Э.Х. Гимади для обычных нераскрашенных графов. В предлагаемой постановка веса ребер я(е), е«Т5, являются независимыми случайными величинами, одинаково распределенными на отрезке Сап, Ъп1, ап > О.

?£ (х> - непрерывная функция распределения случайной

«Се) -а_

величины 5 - -к-е^Е.'

Алгоритм а называется асимптотически точным, если существуют последовательности (нп> и (0П), стремящиеся к нулю с ростом размерности задачи, для которых выполняется неравенство

X

где - значение Ц3> (I), полуденное в результата работа

алгоритма а, х* - оптимальное значение Щ> (I)..

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

Теорема 2.4. Алгоритм л. имеет трудоемкость 0 (п(я+р)). Теорема 2.5. Если р » р(п) —► то алгоритм л является асимптотически точным при условии ip= о(р) и в случае т => conat

требуется дополнительное условие i <m г = где

р —»оо р

t

'7 **

X sa I -------------

Р 1 -

Теорема 2.6. Если р = conat, то при условии = о(пг) алгоритм л не является асимптотически точным.

ТРЕТЬЯ ГЛАВА посвящена исследовании экстремальных задач на графах с неточно заданными параметрами. Неточный характер данных можно описать с помощью интервалов.

В общем случае рассматриваемые нами задачи описываются следующим образом: дан п-вершинный граф в котором

каждому ребру в«В .приписан вес юса), задаваемый интервалом и>г»;«(«> (а>,На множестве допустимых решений этой

задачи определим интервальную целевую функцию (ИЦФ)

т(х> Ж Е »r»J « [wt (X),va(s)1. (2)

*еВ я

и введем отношение порядка.

Решение х предпочтительнее решения у, я { у, если ^fij ä w^iy;, 1-1,2, при этом хотя бы одно неравенство строгое.

Введенный на X порядок поровдает ПИ I s X, состоящее из паретовских оптимумов (ПО).

Решение s « X называется ПО для задачи с ИЦф (2), если не существует х « X, такого что i { х.

В качестве решения задачи с ИЦФ (2) можно рассматривать как ПМ X, так и используемое в многокритериальной оптимизации

А * »»

ПМА X. ПМА X определяется следующим образом: это подмножество X минимальной мощности, содержащее по одному представителю на каждое интервальное значение ВД& (2). Описанная выше задача в интервальной постановке сводится к задаче многокритериальной оптимизации с тем же множеством допустимых решения X и ВЦФ

» { ь>х(х), уег(х) ), (3)

где vj fx} —» min , 1-1,2. (4)

1

Теорема 3.1. Паретовские множества задач с ИЦФ (2) и ВЦФ (3)-(4) совпадают.

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

Теорема 3.6. Интервальные задачи с ИЩ> (2) о коммивояжера, об остовных деревьях, о кратчайшей цепи между парой вершин, о совершенных паросочетаниях являются труднорешаемыми.

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

С точки зрения приложений, особый интерес представляет обоснование условий, которые определяют собой полиномиально разрешимые классы интервальных задач. Такие классы удалось установить для двукритериальных постановок, используя результаты работ Сергивнко И.В., Емеличева В.А., Перепелицы З.А..

Если содержательная постановка интервальной задачи такова, что имеет значение не интервальный критерий (2), а нижняя граница u>t(х) интервального веса (2) и максимальная ширина интервалов л(е> = ш2 <• э; - u»i весов ребер, входящих в допустимое решение, то такие задачи являются полиномиально разрешимыми.

Если ВЩ> имеет вид

= (Pt (х), Р2 (х)).

= Е —► min, (5)

eäB

м

p (x) =max d(s) —» min, (6)

z ei£

*

то справедливы

Теоремы 3.9-3.10. Проблема нахождения полного множества альтернатив для задач о цепях между парой вершин, о совершенных паросочетаниях и об остовных деревьях с критерия™ (5), (6) разрешима с полиномиальной трудоемкостью.

3 ЗАКЛЮЧЕНИИ сформулированы основные результаты и вывода диссертации, которые выносятся на защиту:

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

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

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

3 ПГЛТОаЕгШ описаны методы решения интервальных систем линейных алгебраических уравнений. Исследованы границы применимости интервальной схемы метода Гаусса и итеративного метода Гея. Описано используемое программное обеспечение.

Основные результата диссертации опубликованы в следующих работах:

I. Гомакюк Д.М., Козина Г.Л., Онищенко З.Ф. Программа связи САП? ПРАМ-5.3 / ДПП и АСОШНА-Ы // Автоматизированные

системы обеспечения надежности радиоэлектронной аппаратуры: Тезисы докладов Вссесоюзной научно-технической конференции, Львов - Москва, 1990. - 0.21.

2. Козина Г.Л., Василега Н.М., Крищук В.Н. О проблемах применения интервальной математики к задаче обеспечения динамических характеристик конструкции печатных узлов радиоэлектронных средств // Труды семинара'по интервальной математике, Саратов, 29-31 мая 1990 г.- Саратов, 1990. -0.76-78.

3. Крищук В.Н., Козина Г.Л., Василега Н. М. Учет допусков входных параметров при анализе динамических характеристик конструкций РЭС // Опыт разработки и применения приборнотехнологических САПР: Тезисы докладов к школе семинару, Львов. - Львов:.1991. - С.91.

4. Крищук В.Н., Козина Г.Л., Василега Н. М. Прогнозирование прочностных характеристик конструкций РЭС с помощью интервального анализа // XLVI Всесоюзная научная сессия, посвященная Дню Радио: Тезисы докладов - М: Радио и связь, 1991. - С. 76-77.

5. Козина Г.Л. Исследование векторной задачи коммивояжера на многоцветных графах // Методы решения и анализа задач дискретной оптимизации: Сборник научных трудов / Под ред. A.A. Колоколова; ОмГУ. - Омск, 1992. - С.52-60.

6. Козина Г.Л. Исследование векторной задачи коммигояжера на многоцветных графах. - Запорожье, 1992. - 30 с. - Деп. в УкрИНТЭИ"09.01.1992 N 10 - Ук92.

7. Козина Г. Л. О сложности многокритериальной задачи коммивояжера с хроматическими условиями // Системы программного обеспечения решения экономических задач: Тезисы докладов. - Москва ВЦ РАН, 1992. - С. 45-46.

8. Козина Г.Л., Борковских-Винцер О.М. Исследование сложности векторных задач на многоцветных графах // Проектирование автоматизированных систем контроля и управления сложными объектами: Программа и аннотации докладов Мевдународной школы. - Харьков - Туапсе, 1992. - С.26.

9. Крищук В.Н., Василега Н.М., Козина Г.Л. Библиотека

интервальных операций и функций для системы программирования Фортран 77 // Международная конференция по интервальным и стохастическим методам в науке и технике (ИНТЕРВАЛ - 92): Сборник трудов - Москва, 1992. -T.I. - С. 74-75.

10. Krishchuk V.N., Vasllega N.H., and Kozina G.L. Interval operations and iunctlona library for Fortran 77 Programming System and lta practice using// Interval Computations 4(6),

. 1992. - pp. 2 - 8.

11. Козина Г.Л. Оценки сложности задач о коммивояжере и. о совершенных паросочетаниях на многоцветных графах // Математическое программирование и приложения: Тезисы докладов научной конференции - Екатеринбург: Ин-т матем. и механики УО РАК, 1993. - С.

12. Козина Г.Л., Перепелица В.А. О вычислительной сложности интервальных задач на графах // Теор1я наближення та задач1 обчислювально1 математики: Тези м1зкнародноХ конференцИ -Днепропетровск, 1993. - С.102.

13. Perepelltsa V.A., Kozina G.L. Interval Spanning Тгеез Problem: Solvability and Computational Complexity // International Congress on Computer Systems and Applied Mathematics (CSAM'93): Abstracts - St. Petersburg, 1993. -p. 99.

14. Козина Г.Л., Перепелица В. А. Интервальное и многокритериальное моделирование в задачах проектирования радиоэлектронных устройств // Машинное моделирование и обеспечение надежности электронных устройств: тезисы докладов научно-технической конференции - Бердянск, 1993. -С. 73.

15. Perepelltsa V.A. and Kozina G.L. Interval Calculus In Mathematical Modelling of Discrete Problems // Applied Modelling & Simulation (AKS'93) : Sumarlea of Accepted Communications of International 93 Lvlv Conference - Lvlv, 1993. - pp. 11-12.

16. Perepelltsa, V.A. and Kozina, G.L. Interval discrete models and multiobjsctlvlty. Complexity estimates // Interval Computations!(7), 1993.- pp.74-82.