Геометрические методы системного анализа в комбинаторной оптимизации тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

РГ6 00

~ 1 МАЯ 1993 На п{1авах РУ,с0,шси

БОНДАРЕН КО Владимир Александрович

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

(Специальность: 01.01.11 — Системный анализ и автоматическое управление)

Автореферат

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

Д\оскг.а — !!Ш

Работа выполнена и Ярославском

государе теином университете.

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

доктор физико-математических наук Н. Л. Б о б и л с в, доктор физико-математических наук Е. Г". Голь штейн, доктор физико-матема гнческих наук, действительный член РАН Ю. II. Жура влей.

Ведущая организация: Нижегородский государственный университет им. II. И. Лобачевского.

Защита состоится <; » 1993 г. на заседа-

нии специализированного совета Д 002 68.03 при Институте проблем управления РАН по адресу: 117806, Москва, Профсоюзная, 65.

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

Автореферат разослан « » 1993 г.

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

С. А. Власов

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

Актуальность работы. Многие вопросы, связанные с исследованием сложных конечных систем и управлением в таких системах, приводят к моделям и задачам комбинаторной оптимизации. В последние десятилети интерес к методам комбинаторной оптимизации значительно ' вырос благодаря многочисленным приложениям, а такке в связи с появлением совершенных вычислительных средств. Основные направления исследований в области комбинаторной оптимизации связаны с разработкой и анализом эффективных а^'орииов, с создание?* прибликенных методов, о изучением структурных характеристик задач. В последние „ода особое ■внимание привлечено к вопросам сложности задач комбинаторной оптимизации (ЙЬяогагз J., Grütschel П., Padberg П.П., Cook S.A., Karp R.U.). '

Большое число работ посвящено изучению геометрических свойств задач": основой таких рассмотрений слушт формализация их в виде задач - оптимизации линейных функций на конечных мнокествах в евклидовом пространстве, В этой связи естественно возникали описания алгоритмической сложности задач в терминах свойств ассоциированных многогранников (Kuhn В.ff., Heller 1 , HorâveR J.. Елеличев BU., Леонтьев. B.K.. Сарванов В.И., Papaäinttrtou. C.B.). Основная цель такого рода построений заключается в отыскании аффективно описываемых характеристик задач, количественно свидетельствуют!! об их т£уднорешаемости.

Теория и практика. приближенных методов комбинаторной

оптимизации далеки от своего ' завершения. Следу-" отметить относительное разнообразие • приемов и эвристических идей, используемых при создании приближенных ' алгоритмов, соответствующая библиографы включа >т несколько тысяч названий работ; большинство разработанных алгоритмов направлено на решение за/пч цри ограничениях достаточно произвольного характера, либо жестко связаны спецификой задачи. Поэтому возникает нрослема качественной оценки приближенных методов; традиционные подхода, основанные в большинстве случаев на вычислительном вксперименте, обладают очемдяши н достатками. •

Эти обстоятельства объясняют 'актуальность разработки новых направлений системного анализа задач- и алгоритмов комбинаторной оптимизации. '■' .

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

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

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

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

- з -

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

В работе обнаружены и 8фиктивно . описаны выпуклые шюгограшппот, плотность графов которых экспоненциальна, но внешнее описание которых включает полиномиальное количества лилейных ограничений. Существование таких многогранников дает возмонгостъ использования полиномиальных алгоритмов линейного программирования (Хачиян Л.Г., Кагтгкаг Ы.А.) для комбшаторно труднсрешаемых задач.

Разработан метод объективного анализа приближенных (эвристических) алгоритмов, оспованныЯ на исследовании качества использования исходной информации; о его помощью проведено подробное исследование "надного"-(^геэЗу) алгоритма.

Теоретическая и пршетчеекпя ценность. Работа теоретическая. Иетодц, разработанные в диссертации, применимы к анализу широкого класса задач комбинаторной оптимизации, возникающих при разработке различных слоеных систем (окономичемсих, вычислительных и т.п.) л при оппЕЯзации управление в ппх. Результаты работы дают ответ на ряд пркпцгашалышх качественных вопросов относительно причин труднорэшаемости' задач»' позволяют объективно характеризовать прлблкяешше метода реаения. Разработанные в диссертации методы анализа эффективно реализуег.ш; в частности, для большого числа классических задач я алгоритмов они позволили установить ряд новых фактов. .

Апрсбащя рсДсет. Результата диссертации докладывались на Международной конференции "Математические методы в исследовании операций" ( ..ля, 1993 г., 1987 г.), па Всесоюзной конференции "Проблемы теоретической шберютпкп" (Иркутск, 1985 г.; Волгоград, 1990 г.), на сеютюрах Института проблем управления РАН, Центрального вкономико-матенатнчоского института РАН, . Института

проблем передачи информации РАН,' Вычислительного центра РАН, Воронежского, , государственного университета, . Ярославского .государственного университета.

Публитици. Основные результаты диссертации опубликованы в 16 печатных работах.

Структура и объел работы. Диссертация состоит из. введения, четырех глав и списка литературы. Диссертация' изложена на 148 страницах. Библиография содержит.72 наименования.

СОДЕРЖАНИЕ РАБОТЫ-Во введенju приводится обзор' литературы, примыкающей . к содержанию диссертации, обосновывается . целесообразность исследований, проводимых в диссертации, и излагается ее' краткое содержание. ','••"

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

задач. ...

/ В разделе 1.1 вводятся, определения 1.1.1-1.1.3, назначение' ' которых заключается в уточнении понятия задача комОшиторной' ; оптимизации в зависимости от степени массовости.

. Определение 1.1.1, Задаче? комбинаторной опшмизагщи назовем последовательность конечных множеств X с В, где т - т(п),

I) в

, п = 1,2,>.. . • •

Определение 1.1.2с Задачей с фиксированным параметром п назовем ' X в X являющееся одним из множеств в , определений

. i.'i.ii •-';'.' ; :

Определение 1.1.3. Индивидуальной задачей с вектора* с « Ет

исходных даншх и фшсалравшшил п назовел задачу оптлизации. иа множестве X = Хп иицейной фушщии {С,х). , .

Задачи, соответствующие этим определениям, обозначаются

I

(X ), X (или X) !в [X ;с1 (шш [Х;с}); при втом в содержательном

п п п

плане задача X представляет собой совокупность всех задач [Х;с], с е Е , а задача {X } - совокупность всех задач Л „ п = 1,2,...

ГО п п

К указанному виду приводятся многие задачи с "весами"; задача выбора из п чисел наибольшего, задача коммивояжера, задача о максимальном разрезе, задача о полном подграфе, задача о максимальном взвешенном паросочетании, задача о кратчайшем пути, задача о минимальном остовном дереве, задача о назначениях, задача о максимальном ' трехмерном сочетании, задача' сортироша! (упорядочения) и другие.

Для задачи X (в смысле определения 1.1.2), где 1с Ея» в п. 1.2 вводятся две геометрические конструкции: многогрсаосшс задачи

. М(Х) = сот X

я совокупность лногогранных конусов вида

К(х) = (сеЕ^: (х-у,с) а о ^ри любом уеХ) , теХ- (1)

(Заметим, что задача 1Х;с) на максимум заключается в отыскании такого х € X, для которого с е К(х)») Связь мекду ниш устанавливает следующее утверждение г пусть хс ,хе X и пуалъ г - штленъиая размерность граней лногограюшю. Н(Х), содержащих адно&релет^ . Тогда

(11т К(х, )гК(х) = т - г.

1 л

Частный случай этого утверздения при г = 1 позволяет сводить

анализ системы конусов (1) к' исследованию графа многогранника МСХ) .

Центральным понятием раздела 1.3 является линейное разделящвэ дерево.

Определение 1.3.1. Минейныл разСэляхщл деревол задачи X, 1 X с Е ,называется ориентированное дерево, обладающее следующим.

Ю • -

сво^вствали!

а) в каждый узел, за исклхзчениел одного, шзываелого кор.ел, входит ровно одна дуга; дуг, входяиг'т в корень, нет;

0). для юхдого узла либо илеется две■ выходящие из него дуги, либо таких ¿¿г нет Зоабце; в первол случае узел называется Ьнутрттил, во второл - внешни*, ила лисюл', .

в) каждолу внутреннелу узлу сослветствует некоторой линеФшй функционал (вектор) / в Вщ-

з) ихтиолу листу соответствует некоторый элелент лнохества X;

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

е) для каждой цеш ш = ••• Л * ' ооеШашцвй корень I- лист, и для любого с € Еа из неравенств о, I = 1,2,...,г, следует включение с € К(х). •

Линейные разделяюсще деревья служат естественной моделью вычислительных алгоритмов комбинаторной оптимизации, основанных на линейных сравнениях. Геем трически такие деревья можно интерпретировать как способ построения конусного разбиения специального вида (бинарного разбиения), вложенного в разбиение, ■определяемое системой конусов (1) - теорела -1.3-5. Другое утверждение етого пункта - теорела 1.3.' - дает полное опиошш? множества функционалов, иотоашзуемых любым линейным разделяют» деревом вадачи X.„

- ? -

• В конца п.1.3 подробно аргументируется целесообразность рассмотрения класса деревьев, более узкого, чем множество всех линейнчх разделяете« деревьев. Это сужение определяется в разделе 1.4 на основе факта геометрического характера 5 ;

Теарет 1.4.1. Пустъ Я = ,...,<}• } - селейство т-лерных выпуклых лногогратшх .тожеств в , любые два из которых илет обтра гипергрань и не илет обеда внутренних точек. Тогда для лзсОой гиперплоскости Я в Е^ хотя Ои одно из открытых полупространств Н* и Я"' пересекается по леныией лере с р - Т лножествали селейсява

Определение 1.4.2. Линейное разделяющее дерево Т задачи X назовел назови.' деревол прялого типа, если для лхСого внутреннего узла / и Оля .исСого под.гноясества У попарно слезмт, тачек .тожества X вълолняется неравенство

|ХглГ| - 1 * пах (|ДГ*лУ|,|Х;лКГ}.

Здесь Хг - множество пометок всех листьев дерева Т , который предшествует узел ./','в.Х* и Х~ - подмножество Хг , соответствущие двум выходящим из / дугам. Смеэзгасть точек х и у г»3 , X означает, что отрезок является ребром

многогранника Ы(Х).

Обозначим через р(Х) плотность графа многогранника Х(Х,, то есть максимальное число его попарно смежих веркта; а через Ь(Т) - высоту дерева Р.

Теореяп *.4.3. Пусть Г - дерево прялого типа задачи X.

Тогда

ЫТ) г р(Х) - 1. (2)

Принципиальный характер, теоремы 1.4.3 -усиливается хорош

известным фактом существования в ' Ея при т а 4 выпуклых многогранников с произвольно' большим числом попарно смежных вершин. ' !

Во второй части раздела 1.4 ..ассматривается подмножество линейных, разделяющих деревьев, которое определяется также с использованием теорлш 1.4.1, интерпретируемой , однако, в ином аспекте (определение 1.4.4). В содержательном смысле отличие определений 1.4.2 и 1.4.а можно охарактеризовать так: в первом случае уточняется условие разделения системы конусов (1) Н£.> отдельн л шаге алгоритма, во втором случае вводится ограничение на процедуру исключения из числа претендентов н_. решение задачи [Х;с] всех елемеыов множества X , кроме одного - искомого. .

Для деревьев, соответствующих определению 1.4.4, справедлива оценка, совпадающая о оценкой (2), - теорем 1.4.5.

Вторая глава диссертации содержит . анализ

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

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

о

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

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

Раздел 2.1 содержит замечания общего характера. В п.2.2 изучается общая задача сортировки массива, которая определяется множеством Хп(а) всех векторов-перестановок начального вектора а = (а,,...,а ). отдельные компоненты которого могут совпадать. Ее

1 П

частными случаями являются классическая задача упорядочения, задача выбора "fc-ro максимального" и другие. Teopexi 2.2.1 -2.2.3 дают полное описание граничного комплекса обобгценного перестановочного многогранника Мп(а) = сопи %п(а) и, в частности, условий смежности его вершин. Это позволяет вычислить плотность графа многогранника И (a)i по теореле 2.2.4 она оказалась па единицу большей .максимального числа совпадающих между собой компонент начального вектора а. В конце раздела рассматривается класс алгоритмов сортировки,. использующих попарные сравнения елементов массива; в отот класс входит большинство применяемых алгоритмов. Устанавливает'-k

Теорема 2.2.6. Лабой алгоритм сорыровш, использующий попарные сравнения, является алгоритмом прямого шт.

В разделе 2.3 рассматриваются также классические модели комбинаторной оптимизации - матроида п "кадкне" алгоритмы. Напомним , что множество X с Еа 0,1-векторов о одинаковым числом единиц называется ашроивол, ест для любых х,у е X и для любого вектора е( стандартного базиса, удовлетворяющего неравенству ei * х, найдется такой е} , для которого е^ * у и х - Sj + в^ i JC. Термином "гавкай" алгоритм обозначается процедура решения задачи (Х;с1, заключающаяся ' в последовательном выборе среди неиспользованных координат вектора с исходных даннвт

-10т'

наименьшей с учетом долу отгости конструируемого 0,1-вектора. Среди наиболее известных реализаций: "жадного1- алгорнтмр - алгоритм Краскала построения минимального остовного дерева в графе и метод "иди в ближайший" для задачи коммивояжера. По' теореме Радо

"жадный" алгоритм точен тогда и только тогда, когда X -' матроид. В дасоертации показывается - теорела 2.3.6 - что "жадный" алгоритм на мат. оиде является алгоритмом прямого типа. С втой целью ' предварительно устанавливается характериз. ция матроидь в терминах смежности вершин . соответствующего многогранника - теорелы 2,3.3 и 2.3.4°. множество , X. состоящее из 0,1-векторов <г одинаке ым количеством единщ, „является ыатрсвдоы в . том и только том случае, если смежным? вершинами ыного^анника Г:Х)=сопиХ служат такие точки х,уеХ,.которые получаются друг из друга перемещением одной единицы, и только они. Из последнего утверждения оледует, в частности, полиномиальность плотности «графа многогранника И(Х) по размерности векторов составляющих -матроад ' X. - ' ■ . ■ . ,

В раздало 2.4 рассматриЕ .ется классическая задача о кратчайших пути, заключающаяся в нахождении пути - в графе.» соединяющего ..две фиксированные вершишь суммарный вес ребер которого минимален. В теореме 2*4.1 устанавливается ярптерий смежности вершин многогранника А'С^О втой аадачиг два дуги соответствуют смежным вершинш/ многогранника ЩХ ) в том и только

П

том случае,- когда симметрическая разность множеств образ! миг воя пути ребер составляет один простой цикл. Обметим вытекающие нз -олученного описания графа многогранника ЩХ ) его особенности -

'Л

степени его вершин имеют различные значения » максимальная степень верщшш окспоненциальна по п, где п- количество вершин исходного графа. Тем не .менее плотность р(Х ) графа многогранника М(Х )

С, * П А

оказывается полиномиальной и удается найти точное значение Р(Х^) {теорема 2.4.2):

рп: =

' 1? при п = 2&, при п = 2Й+1.

Ь завершение пункта 2.4 приводатся теорема 2-4-3 о том, что классический алгоритм Цура-Дейхстры решения задачи о кратчайшем аута яяпяетсг алгоритмом прямого типа.

Заметный класс полиномиально разрешимых оптимизанионных задач образуют задачи о ппрасочетакиях, коте рым г^священ пункт 2.5; о частным случаем задачей о назначенгчх - связано особенпо большое количество результат т. Специфика . .указанных задач заключается в "наличии вффеютшного описания их многогранников (Еиркгоф , Здооцдс ). В диссертации устанавливается (теорема 2.5.2), что знаменитый алгоритм Эдмоздса является алгоритмом прямого типа, 'следствием слукит заключение о млиномиа/ъности плотности графов 'ассоциированных многогранников.

Дальнейшие фасс?^отрения второй главы связаны с задачами, для которые неизвзстшг полиномиальные алгоритмы? по традиции

•ля них используется словосочетание труднореиаелые • задачи.

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

Основные направления исследований, связанных с задачей

с - ^ .

коммивояжер-^, характерны для комбинаторной оптимизации в целом:

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

В первой' части пункта 2.6 проводится анализ известных алгоритмов решения задачи коммивояжера - метода динамического программирования и метода ветвей и границ - с точки зрения классификации, введенной в первой главе; устанавливается, *1ТО указанные алгоритмы принадлежат классу алгоритмов прямого типа (теорем 2.6.1 и 2.6.3). Теорема 2.6.1 дает возможность получить верхнюю опенку величины плотности р(Хп) графа многогранника ЖХп) задачи коммивояжера (теорема 2.6.2):

п-З

р(Х\ « 01-1/ Е (к-и С*1) + 1.

к«а .

Центральным результате» втого раздела является теорем 2.6.5 об експоненциальности величины р("ХпЛ при хюйол натурально* п справедливо неравенство

Ыа - 91/3

р(Х ) > 2 (3)

Содержательной интерпретацией этого утверждения служит вывод о том, что любой комбинаторный алгоритм решения задачи ком! лвояжрт» {X } имеет временную трудоемкость, превышающую правую часть в

(I ,

неравенстве (3). г

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

оптимизации, которые в варианте задач распознавания фигурируют в монографии Гври и Джонсона . Для каждой из рассматриваемых задач Останавливается критерий смежности вершин ассоциированного многотанника и 'доказывается експоненциалыпст! плотности его графа.

31дача КЛИКА заключается в отыскании в полном графе полного подграфа, суммарный вес ребер которого максимален. Любые две вершины многогранника втой задачи являются смевашми -теорем 2.4.1; следствием теоремы является результат Грепшева о многограннике для подграфов с одинаковым числом вершин, а также полнота графов многогранников, двух близких задач - НЕЗАВИСИМОЕ МНОЖЕСТВО и ВЕИШННПТг ПОКРЫТИЕ .

• Еще одна задача выбора подграфа о заданными свойствами, суммарный вес ребер которого максимален, - задача РАЗБИЕНИЕ НА ТРЕУГОЛЬНА-31; она заключается в разбиении множества вершин исходного полного реберпо-взвешечного графа на к "троек" (л = Зк - количество воршин исходного графа), чтобы сумма периметров образующихся треугольников была наибольшей . . Полученный в работе критерий смежности воршин много! ранника сопи Хп втой задячи (лелла 2.7.2) позволяет установить експоненциальность плотности его графа:

Творела 2.7.3. Платность Р(%п) графа лногогранниха задачи рлзаишив НА ТРЕУГОЛЬНИКИ удовлетворяет неравенству

Л /я - а

рав; = раэк'а2 . (4)

Хорошо известная задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ, взвешенный вариант которой называется также тр хиядексной задачей назначений, ^акпг'эски гтляется частный случаем предыдущей задачи; ето

позволяет легко сф^рмудшроввть критерий смежности вершин соответствующего многогранника {лелла 2.7.4), и получить оценку плотности его графа, аналогичную неравенству (4) (яесрела 2.7.5).

Задача ПОЛНЫЙ ДВУДОШШ ПОДГРАФ заклотается в отыскании полного двудольного подграфа, суммарный вес ребер которого максимален, а общее число вериги в долях равно эаданноау числу й (к л п, где п - число версии исходного полного реберго-взвешенного графа). При к = п ега задача превращается в хорошо известную задачу НАКСИШЬШЯ РАЗРЕЗ , граф многогранника которой является паники . в обцем счучвв - при к а п - сизгэосиь вершин многогранника сопи Хпк задачи ШЛШ5! ДВУДОЛЫЮ ПОДГРАФ описывается. леммой ^.7.6: вве берегши лиогограттт сопи Хпк не слех,А1 в тол и только тол случав, когда соответствующе двудольные подграфа илеют по одной общей доле, а вторые их воли отличаются по леныпей ларе двуля вершнош. Следствием леммы служит теорема '".7.7: плотность р(Хок) графа многогранника . сопи X ^удовлетворяет неравенству

р(Х у) ь [л/йКа*"1- V.--'

•ПК

Оптимизационный вариант задачи ПОКРЫТИЕ Ш.ТРВД' заключается в следующем. Задана пхл-матрица с = (с,^, строки и столбцы с одннаковыш номерами которой можно одновре-енио умножать на -1 . Требуется так выбрать номера умножаемых строк (и столбцов), чтобы суша влементов получившейся в результате матрицы оказалась максимальной. Многогранником етой задачи служит сопиХп, где Х^ - множество матриц вида

х = х(б) = (В^р. 5 = (6г...,Бв), « 1-1.1). {€»п Показывается - теорема 2.7.8- что граф многогранника сопи Х^

является полным. ■ •

Последнее утверждение аналогично теорема 2.7.2 для задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО п ВЕРШИННОЕ ПОКРЫТИЕ, а также результату Белошевского о полноте графа задачи МАКСИМАЛЬНЫЙ • РАЗР13. Для 8тих задач попытки создания алгоритмов хотя , бы какой-то мера более эффективных полного перебора варгнтов связаны с пр.одолением' принципиальных трудностей; вто вытекает из перечисленных утверждений и результатов первой главы.

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

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

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

П

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

П П

полиномиальные алгоритмы линейного программирования .

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

Многогранник ы' , п « N , задается в пространстве Б , где

П Я)

т - Апа , системой линейных ограничений, содержащей О(па) уравнений и неравенств. 2" целочисленных вершин втого-многогранника являются попарно смежными, то есть

р(Хп) а 2" ,

причем все . вершины, в том числе, и нецелочислешше, 'из X допускают аффективное описание.

П

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

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

A : Е —«- X i

иными ловрчи, для любого a € г и для любого с е а алгоритм А '.'выдает" приближенное решение А(а) е X , заменяющее искомое точное решение индивидуальной задачи .Х;с] Качество алгоритма А относительно Е естественно харак зризовать его способностью "угадывать" точное решение задачи IX; cJ . хотя бы для некоторых о'е б ; на основе втих соображений в разделе 4.2 вводится понятие E-точного алгоритма (определение.4.2.2): А называется Е-точныл, ■ если для любого а е £

a л К (А(0)) Фа.

В разделе .4.3 проводится • анализ известных ввристических алгоритмов с целью обнаружения среди н: z E-точных; основное внимание уделено "жадному" алгоритму и локальному поиску. В частности, доказана неулучшаемость "жадного" алгоритма при использовании информации об упорядоченности координат вектора исходных данных (теорем 4.3.2), получено теоретическое объяснение того, что алгоритм "иди в ближайши"" приемлем для задачи коммивоя-. хера, но лв приемлем для задачи о кратчайшем пути с неотрицательными весами (теорела 4.3.3). относительно локального поиска установлено, что популярный алгоритм Лива для задачи коммивояаера, •основанный на 2-зсиенах, не является E-точным (теарелс 4.3.4).'

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Для классических задач комбинаторной оптимизации - задачи коммивояаера, задачи о назначениях, задачи о кратчайшем пути и других - установлены оценки плотности графов их многогранников; полученные оценки, в частности, дают объяснение трудаорешаемостн известных задач тради: ионными' комбинаторными методами.

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

4. Разработан новый метод анализа приближенных ' алгоритмов, основанный на учете качества использования неполной информации. С его помощью проведено исследование ряда известных вврисхкческпх алгоритмов; показано, в частности, что классический Чшднкй" алгоритм является наилучшим среда всех алгоритмов, использующих упорядоченность ..¿ординат вектора исходных данных.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ- ДИССЕРТАЦИИ

I. Бовдаренко В.А., Короткий A.A. Анализ алгоритмов дискретной оптимизации., использующих неполную информацию // ЖВМ и МФ. -IbSI. - Ü 3. - С. 783 - 786.

2; Бондаренко В.А. Соседние вершины многогранников, лорождаомнх

' матровдами // Вопросы теории групп п гомологической алгебры. -- Ярославль, 1982. - С. 66 - 68.

3. Богдаренк В.А. Неполиномиальная яияняя оценка сложности задачи коммивояжера в одном классе алгоритмов // Автоматика и телемеханика. - 1383. - ¡5 9. - С. 45 - íj.

4. Бондаренко В.А. Экспоненциальная -.ияняя оценка плотности полиэдрального rpuía задачи коммивояжера-// Тезисы мевд. конф.

'"Матем. метода в исследовании операций". - София, 1983. - С. 17.

5-, Бондаренко В.А,, Шуншсова Е.В. Обобщенные перестановочные многогранники и свойства алгоритмов сортировки // Модели исследования операций в-вычиолительшгс системах. - Ярославль,

•.. 1985. - С. Ю5 - 113.

6. Бондаренко В.А. Неполпномиальнне шшша оценки сложности оптимизационных задач о клике и вершинном покрытии в классе -рядах алгоритмов // Комбинаторно-алгебраические методы в прикладной математике. - Горький, 1985. - С. 59 - 65.

7. Бовдаренко В.А. Экспоненциальность плотности графа многогранника задачи о трехмерном сочетании // Тезисы УН Всосоюзн. конф. "Проблемы теоретической кибернетики". - Иркутск, 1985. - С. 29.

8. Бондарэнко В.А. Полиномиальная верхняя оценка плотности графа многогранника бистохастических матриц // Тезисы межд. конф. "¡«атем. метода в исследовании операций". - София, 1987. - С. II.

9. Бондаренко В.А. Об одном комбинаторном многограннике //

, Моделирование l анализ вычислительных систем. - Ярославль, 1987. - 0. 133 - 134.

10. Бордаренко В.А. О сложности дискретных задач и комбинаторных свойствах их многогранников // Труда семинара по дискр. матем,

• и ее приложениям. - М., ЖУ, 1989. - С. 277.

11. Бондаренко В.А. О многогранниках с высокой плотностью графа // , Вычислительные системы. - Ярославль, 1990. - С. 136 - 139.

12. Бондаренко В.А. О многогранниках о высокой плотностью графа // Тезисы Всесоюзн. конф. "Проблемы теоретической кибернетики". -

; Волгоград, 1990. - С. 15.

13. Бондаренко В.А. О проблеме трудчорешаемости и анализ эвристик , -. в дискретной оптимизации. I •// Автоматика и телемеханика. -

1992. - № 12. - С. 20 - 24.

14. Бощпренко В.А. О чроблеме труднорешаемости и анализ эвристик в дискретной оптимизации. II // Автоматика и телемеханика. - •

1993. - if I. - С. 27 - 32.

15. Бондаренко В.А. Оценки слокности задач комбинаторной оптимизации в одном классе алгоритмов // Докл.' АН. - 1993. -, Т. 328, Я I. ' • ' ■ ' ' '

16. Бондаренко В.А. Об одном классе многогранников и их использовании в комбинаторной оптимизации // Докл. АН. - 1993. -Т. 328, й 3.

Формат 60x84 .Бумага газетная. Офсетная лечеть. Печ.л.1. Тираж 100. Заказ 237. Типография Ярославского политехнического института. Ярославль ул.Советская, 14а.