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

— о Я о

4 ' АКАДЕМИЯ НАУК УКРАИНЫ

ИНСТИТУТ КИБЕРНЕТИКИ ИМЕНИ В.М.ГЛУИКОВЛ

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

КОВАЛЕВ МИХАИЛ МИХАЙЛОВИЧ'

ВЫПУКЛО-МАТРОИДННЕ СТРУКТУРЫ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ И ЭФФЕКТИВНОСТЬ ГРАДИЕНТНЫХ АЛГОРИТМОВ

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

Автореферат

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

Киев - 1992

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

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

профессор ТАНАЕВ B.C.

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

член-корреспондент АН Украины, • • доктор физико-математических наук,

профессор ШОР Н.Э.

Ведущая организация: Киевский университет

Защита состоится 199 г. в __ часов

на заседании специализированного совета Д 016.45.01 Института кибернетики им. В.М.Глушкова АН Украины по адресу: 252207, Киев-207, проспект академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан

^ ¿У 199 Л,

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

СИНЯВСКИЙ В.Ф.

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

Актуальность темы. Дискретная оптимизация (ДО) - раздел на стыке дискретной математики и математического программирования, связанный с исследованием методов нахождения экстремумов функций на "дискретных", в частности, конечных множествах. Класс задач ДО весьма многообразен "и включает целочисленное программирование, экстремальные комбинаторные задачи, задачи комбинаторной геометрической оптимизации, оптимизационные задачи на графах и гиперграфах, булево программирование. Источником задач ДО являются такие области, как исследование операций и системный анализ, автоматизация проектирования и компьютерная графика, интегрированные производственные системы и оптимальное управление, информационные и нейронные сети. Обширностью приложений методов ДО объясняется тот факт, что за 30 лет систематического изучения задач ДО число публикаций превысило 20 тысяч (данные четырехтомного библиографического указателя серии Lecture Notes in Economics and Mathematical .Systems).

В начальной стадии развития ДО сводилась, в основном, к целочисленному программированию и большинство работ было посвящено распространению на дискретные задачи проблематики линейного программирования. Типичный пример - методы отсечения. Даже метод ветвей и границ изначально был сформулирован, как обобщение методов линейного программирования. Однако еще в период становления была осознана специфика ДО по сравнению с другими направлениями математического программирования. С одной стороны были созданы универсальные схемы решения задач ДО: последовательный анализ варнантдв (В.М.Михалевич и Н.Г.Шор), метод построения последовательности планов (В.А.Емеличев), метод вектора .спада (И.В.Сергиенко). С другой стороны, благодаря фундаментальным работам Ю.И.Журавлева, О.Б.Лупанова, А.А.Ляпунова, С.В.Яблонского, по теоретической кибернетике было положено начало качественным исследованиям градиентных и локальных алгоритмов. Существенный прогресс в решении экстремальных задач на перестановках связан с алгебраическим подходом Д.А.Супруненко. Значительный вклад в качественную теорию ДО положен работами Эдмондса, указавшего пути применения матроидов в ДО, Фулкерсона, заложившего основу теории

двойственности в ДО и Кука, Карпа, предложивших одну из наиболее распространенных моделей слояшости и сводимости задач. Дальнейшее развитие качественная теория ДО получила в работах Б.Л.Береснева, В.П.Грншухина, В.К.Леонтьева, В.А.Перепелицы, В.П.Солтана, В.С.Танаева, В.А.Трубина, Ю.Ю. Червака, В.И.Шевченко, С.В.Яковлева. Качественная теория ДО есть по существу теория анализа. алгоритмов: исследуются условия оптимальности алгоритмов и устойчивости решений, оценки точности и трудоемкости, ведутся работы по созданию выпуклого дискретного анализа, теории полиэдральной комбинаторики.

Принципиальная трудность задач ДО . делает, по-видимому, невозможным' построение эффективных точных алгоритмов для большинства классов задач. К тому же задачи ДО, как математические модели практических ситуаций ' выбора наилучших решений не тождественны ситуации, а являются ее приближенным описанием, поэтому и решать задачи ДО разумно с той же степенью приближения к оптимуму. Перечисленные обстоятельства привели к тому, что в последние десять лет исследование эффективности алгоритмов стало магистральным направлением в ДО, в котором можно выделить следующие проблемы: выбор меры эффективности приближений (различные метризации либо области . значений критерия, либо допустимой области, либо пространства данных), вероятностный анализ алгоритмов (пионерские результаты в этом направлении получены Э.Гимади и В.А.Перепелицей. Несмотря на все больший размах исследований по эффективности приближенных алгоритмов ДО, эта проблематика находится все еще в стадии становления.

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

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

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

Научная нобизна работы состоит в следующем:

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

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

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

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

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

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

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

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

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

Практическая значимость. Результаты работы использовались при создании банков алгоритмических знаний решения практических задач ДО и легли в основу семейства инструментальных комплексов ДИСКОГРАД-ФИЛИН, на основе которых создан ряд промышленных систем для персональных компьютеров класса IBM PC. Важнейшие среди них следующие:

ДИСКОГРАД - комплекс оптимизации проектных и планово-экономических решений (серебряная медаль ВДНХ Республики Беларусь, 1990 г.);

МЕДИАНА - ППП проектирования оптимальных двухуровневых сетей, включая региональные информационно-вычислительные сети (использован при проектировании крымских СЭС);

ТРАССИРОВЩИК - САПР топологии матричных БИС (серебряная медаль ВДНХ СССР, 1991 г.);

ГЕОМАСТЕР - интегрированная система автоматизированного проектирования шахт (внедрена^ на калийных рудниках);

САПР-РАСКРОй - система автоматизированного проектирования оптимального раскроя промышленных материалов .

ФИЛИН - инструментальная оболочка экспертных систем динамической классификации состояний объектов.

Часть результатов диссертации вошла в книгу Дискретная оптимизация. Минск, 1977, рекомендованную в 19 г. типовыми

программами Минвуза СССР при изучении курсов "Исследование операций", "Дискретная оптимизация", "Логико-комбинаторные задачи проектирования", а также в учебное пособие: Моделирование и оптимизация в схематическом ц топологическом проектировании (в соавторстве с Н.Н.Писаруком), Минск, 1991. Электронный учебник - ДИСКОГРАД со курсу "Методы оптимизации" используется в вузах стран СНГ, Германии, Кубы, Голландии.

Матроидный подход к анализу эффективности градиентных алгоритмов нашел продолжение в работах зарубежных математиков: Франции (Minoux), Германий (Girlich, Körte, Faigle, Dempe, Bachman, Hoppe), НРБ (Миланов, Димов), СРВ (Н.Нгиа, Д.Чинь, Тхо), а также в шестнадцати кандидатских; работах учеников автора.

Апробация работы. Изложенные d работе результаты неоднократно докладывались на минском семинаре по математической кибернетике, которым руководил академик АН Беларуси Д.А.Супруненко, на семинарах Института кибернетики АН Украины, конференциях по теоретической кибернетике (Новосибирск, 1980,' Саратов, 1986, Горький, 1988, Волгоград, 1990), семинарах по дискретной математике (Москва, 1984', 1987), II-ой школе-семинаре 'по дискретной оптимизации (Кишинев, 1983),. I, 11-м Украинских семинарах по дискретной оптимизации (Ужгород, 1983, i935), II, II1-м совещаниях "Методы и программы решения оптимизационных задач на графах и сетях"' (Улан-Уде, 1981, Ташкент, 1984), I, III-й конференциях по исследованию операций (Минск, 1974, Горький, 1978), на семинарах по графам, гиперграфам и задачам дискретной оптимизации (Одесса, 1979, 1980, 1981, 1991). Результаты докладывались также за рубежом на семинарах Бержа по теории графор в Парижском университете^ на семинарах Эдмондса по теории матроидов в университете Ватерлоо, на научных семинарах университетов Германии (Иена, Браушвейг, Магдебург, Фрайберг, Ильменау, Берлин, . Веймар), Канады (Монреаль, Квебек, Шербрук), Голландии (Еншеде), на международном коллоквиуме по теории графов и комбинаторике (Марсель, 1981), международных конференциях "Математические методы в исследовании операций" (София, 1976, 1980, 1990), _21, 24, 27, 30-х международных научных коллоквиумах (Ильменау, ГДР, 1976, 1979, 1982, 1985), международных конференциях по математической оптимизации (Айзенах, 1977, 1986, 1987, 1989,

1990), международной конференции математика, и кибернетика в экономике (МКО - 1975, Дрезден).

Публикации. Основные результаты опубликованы и монографиях [1 - 6] и статьях [7 - 52]. Конкретный вклад соавторов публикаций указан во введении к диссертации.

Структура работы. Диссертация состоит из введения, 5 глав (16 параграфов), объем 308 страниц. Список литературы включает 186 наименований. '

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

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

Глава 1.- МЕТОД ЧАСТИЧНЫХ ПОРЯДКОВ

Методом частичных порядкоь назван подход, основанный на идее "погружения" допустимого множества В задачи ДО в частично упорядоченное . множество Н (далее просто упорядоченное множество), относительно порядка которого критерий оптимальности £ и (или) скорость его изменения (градиент) монотонны (изотонны или антитонны). Под градиентом понимается конечно-разностный оператор йгас! ¿(х.х*) - £ (х*)-£ (х)., где х+ -элемент, непосредственно следующий за х в Н. Градиенты могут служить дискретными аналогами производных по направлениям, а их монотонность влечет ряд свойств, присущих выпуклым функциям. Более того, функции с монотонными градиентами имеют тесную связь с порядково-выпуклыми множествами и субмодулярными функциями, ныне широко изучаемыми. Различаем два способа применения метода частичных порядков: первый требует мотонности критерия (изотопные задачи), а второй - монотонности градиентов (выпуклые задачи). Следует отметить, что отношения частичного порядка в задачах с монотонными функциями используются широко. Так, В.А.Емеличевым предложен подход к исследованию локальных экстремумов на основе отношения мажоризации, Д.А.Супруненко построена единая концепция необходимых условий оптимальности в экстремальных задачах на подстановках, В.С.Танаевым применены частичные порядки в теории расписаний, Робинсон и Сеймур с помощью частичного упорядочения получили ряд тонких результатов в теории графов.

Изотопные задачи. Метод частичных порядков позволяет, не прибегая к сложным процедурам теории полезностей формализации критерия, использовать отношение предпочтения для построения паретовених оптимумов. Даие в случае, когда критерий задан, при построении методов для классов задач ДО необходим формализм описания информации, вытекающей из свойств критерия. Задание информации о классе F критериев f или о классе G резольвент g допустимого множества в форме частичного порядка удобно как для построения единой схемы алгоритмов, так и для выделения нетрадиционных классов задач ДО. Частичный порядок < на Н называется информацией о классе F функций на множестве Н, если каждая функция f из F является изотопной на Н. Если, кроме того, из несравнимости х,у ¿'И следует существование таюк функций f,,f 6 F, что fi(x) < ft(у), a f2(x) > f2(y). то отношение < называем полной информацией о классе F.

Теорема 1.1 Со полной информации)

п

1. Для класса линейных функций £ с х , у каждой из кото-

J = i 3 1

рых 'коэффициенты с ,, , г ... г с , а О упорядочены одинаково,

till Ь(п)

полная информация есть канонический порядок х <г у:

в а

£ хх,п 3 Е Уто- 3 6 Ы-

2 (Шур-Мирский). Полная' информация для класса погнутых симметрических функций f на Zn есть канонический порядок х < у (е-тождествениая подстановка) на множестве разбиений Yn (иногда его распространяют на R" и называют отношением маторизации).

3 (Фукс). Полная информация для класса вогнутых квазисим-

п ■

метрических функции f (х)= £ a[cCxi), где с(х[) - погнутая функция, .....сО е R", есть канонический порядок с растяжением

х у, где перестановка х такова, что

х г ... г х , v г: ... a v

Г( 1 ) Г(п ) ' 1 ) >

3 Аа1ут(.>-s е [п_11- £ a.xi= £ «tyt-

на

п

4. Для класса линейных форм fin)- £ 01 bn(t, , с^г...г с

множестве S^ перестановок из чисел [п] при фиксированном векторе b е R" полная информация есть частичный порядок тс < v, инду-

цированный на S каноническим порядком на множестве {b :n е S ):

« п п

Дь™>* k е Сп~1Ь

Структура множества (Z",< ) исследована с помощью инъек-тивного вложения в решетку Юнга, которая есть упорядоченное множество Y разбиений ir целых неотрицательных чисел ш=0,1,... на слагаемые: ш- ni+...+nk, n^-..г: п^ь О, причем (ni+. . .+11^) < < (у1+...+и>) » к з s и u^, i-l,...k. Выделим в Y подмножество Уп лишь тех разбиений, слагаемые которых не. превосходят п.

Теорема 1.2:- 1° Упорядоченные множества (Z",< ) и (Yn,s) •

■*• X"

изоморфны. :.....

2° Упорядоченное множество (2",< ) изоморфно идеалу

h4 h h he

id(n \(n-») z...l n) решеткиY_. ;

П

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

Множество всех максимальных элементов упорядоченного множества (D.O называем максимальной базой и обозначаем 0пах.

При решении алгоритмом А задачи максимизации с критерием f из класса F обращение к f-оракулу необходимо лишь" в точках максимальной базы DBax, т.е. для трудоемкости верно <p(A,f,g)= — |DmBX|+(f>(A,g), где «>(A,g) - число обращений к g-оракулу для локализации множества D™a*.

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

Теорема 1.3. Перестановка (цикл) п , является максимальным

элементом множества С всех циклов относительно порядка <, в * п

том и только в том случае, когда отвечающий ей цикл - унимодальный, т.е. С"**—{1~я.<...< л — п >п >...> п },|С*ах|-2п"2.

п 1 ■ п 1 п '

Описаны классы задач, -в которых максимальный элемент единственный, и следовательно является оптимумом в любой задаче ДО из класса (F.g) не зависимо от критерия f е F.

Теорема 1.4. 1° Множество D с Rn(Zn,Bn), упорядоченное каноническим порядком <х , обладает единственными максимальным и минимальным элементами для любой перестановки * тогда и только тогда, когда D - обобщенный полиматроид (суперматроид.матроид).

2° Множество D s Bn (Rn,Zn) является натроидом (полиматро-

+ n

идом, супврматроидом) в тон и только том случае, когда D совпадает с множеством нулей функции g: Bn(R",Z") В изотопной в

каноническом порядке < дли всякой т с S .

п о

Выпуклые задачи. Под порядковой окрестностью 0(х ) точки

х°е Н будем понимать множество элементов, непосредствен-

но следующих за х° и п~(х°) непосредственно предшествующих х°. Введенное понятие окрестности задает порядковую топологию на множестве Н. Элемент х° е Н называется локалышм максимумом (порядковым), если f(x°) s f(x) для любого х « 0(х°). Функция f:Н R называется порядково-выпуклой на Н, если 2f(y) г f(x)+f(z) vx<y<z. На 2П эти условия трансформируются в 2f(x+et) г f(x) + +f(x+ei+ej) Vi,je[n], Vxe'Z", а на булеане 2tr2f(Xui)t f(X)+ +f(Xuiuj) vi.je [n]\X, VX s [n] порядково-выпуклые функции подкласс субмодулярных. Критерий локального максимума субмодулярной функции на булеане дан еще в 1962 году В. П. Черешпшм и нашел широкое применение в методе последовательных расчетов и аппроксимациопно-комбинаторном методе В.Р.Хачатурова.

Предложение 1.5. Для трудоемкости <р(A°pl) оптимального алгоритма a°pt поиска всех локальных максимумов выпуклой функция справедливо

SCH) log(-iaJL) * KAopt; t шах | (гг~(С)С)} u (С,гг+(С))| г= S(H),

где С - антицепь упорядоченного множества II, S(Ii) - его ширина.

Проблема оптимального поиска всех локальных (порядковых)

максимумов выпуклой функции на произвольном упорядоченном

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

Е(Н) - множество ребер диаграммы Хассе множества (Н,<). На Е(Н)

зададим частичный порядок: (х ,у ) <'(х ,у ) « у <х . Множество

11 2 2 12

(Е(Н),<*) называется реберно-инДуцироваиным. Определим на Е(Н) изотопную булеву функцию правилом g(z)=0 « signgrad(z)=l. Задача поиска всех локальных максимумов порядково-выпуклой функции на Н эквивалентна задаче построения максимальной базы подмножества tz е Е(Н): g(z)=0) реберно-индуцированного множества

Е(Н) (идентификации идеала D ). Для конкретных классов множеств

• я

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

максимумов, типичный пример следующая «

Теорема 1.7. Инояество локальных максимумов порядково-

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

может быть найдено методом центрального элемента не более чем

за 3.73 log i(Е{1!)) обращении к sgf-оракулу, где i(Е(Н)) -число идеалов реберио-иидуцпровашого множества Е(Н) .

Многие задачи ДО формулируются иа решетках Нп, являющихся произведением п линейно-упорядоченных множеств Н. Такие решетки назвали координатными. Естественно, что координатная решетка изоморфна реаетке Zj|=[h ]х. . .x[h ] ,h «=|Н | . Однако, класс задач с дискретными переменными удойно выделять из класса задач с целочисленными переменными. Отметим, что любая дистрибутивная решетка с О нзонорфна некоторой подрешетке координатной решетки.

Множеству (!!",<) сопоставим а реСерио индуцированных множеств (Е (Hn),<J) - элементами Е (Кп) являются пары (х.п'Чх) и

J „.. , J J

при этом (x,nj(x)<J(y,jij(x)> « xsy. Доказано, что (Е (H"),<J) к

[h ] х .. x[n ]x[h -l]x[h jx.Y.x[h ], в частности "(E (B1,),'=sJ)

1 l-i 1 »♦1 П J

а (Вп"\з).

Теорема 1.8. Задача поиска всех локальных максимумов ■ эквивалентна п задачам идентификации идеала в координатных решетках (Е (Hn),<J), j е [п] .

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

(П ч

г т I вызовов sgf-оракула. Проведен сравнительный анализ f- и sgf-оракульнои трудоемкости других алгоритмов как для субмодулярной, так и для выпуклой оптимизация.

ГЛАВА 2. ВЫПУКЛОСТЬ В ЧАСТИЧНО-УПОРЯДОЧЕННЫХ МНОЖЕСТВАХ

Исследуются две модели выпуклости: порядковая и координатная. Подмножество D упорядоченного множества II называется по-рядково-выпуклым, если для любых x,zs D, ye Н из условия х<у<2 следует, что у е К. Эпиграф {(х,с) е HxR: f(x) к с] порядково-выпуклой функции является порядково-выпуклым множеством на IIxR (на R определен естественный порядок з ). Порядково-выпуклое множество с единственным минимальным элементом называется УВН-ножеством. УВЕ-множество есть порядково-выпуклое множество с единственным максимальным элементом. Каждое порядково-выпуклое множество ест пересечение УВН-множества и УВЕ-множества. Пусть h(x,y)-h(y)-h(x), где h(a) - высота элемента а в (Н,<).

Теорема 2.1. 1) Следующее неравенство эквивалентно определению порядково-выпуклой функции на Н:

-Е&ё-^) vx < у <■ z.

2) Всякая порядково-выпуклая на модулярной решетке Н функция является субмодулярной.

Класс порядково-выпуклых функций недостаточно обширен. В частности, линейная функция (с,х) является порядково-выпуклой лишь в случае, когда с —..с^. Функция £:Hn R называется ко-ординатно-выпуклой, если grad^fix)* о Vi,j и vx. Пусть V*f(x), 7~f(x) - векторы в Rn, i-я координата которых есть соответственно правый и левый i-градиент. На Нп определим функцию N(x,y)- Ii б [n]:-. х <-у , x^yj и вектора х v у и х * у в Zn с координатами max {Xj.y,] и min fx^.y^}:

Теорема 2.2. Для функция f, на Н°, следующие высказывания эквивалентны:

1° f(х)-кординатяо-выпуклая функция; 2° grad*f(x) - антитонная функция для каждого i; 3° grad'f(х) - изотопная функция для каждого i; 4° f(x) - субмодулярная функция и grad*f(x) - антитонная функция на координатной цепи Hf ;•

5° f(y)-f(x) а £ h(x у )grad*f(x) + .

1€Н<х,у>

+ Е h(y ,х )grad"f(x V у); 1ем(у,х)

6° х < у, то f(y) - f(x) s E h(x у )grad*f(x).

KH(x,yl

Примеры координатно-выпуклых функций:

1) порядково-выпуклые функции;

2) линейные функции;

3) полиномы первой степени

f(x> »xif;(xi,..,xi.i,xi^,..,xn) -V f°(xi,..,xi_i,xitl,..,xn),

лишь тогда и только тогда, когда f1 антитонные функции; полиномы £ а х ... х , если a ¿0;

____ _ _ 1 ... 1

1 k 1 k 1

4) суперпозиции £((х ,..,х ,g(y ,..,у )) изотопных

1 1 го

наординатно-зыпуклых функций £(х.....х^) и g(y ,..,Уя) на Z" и

Zm соответственно, например, суперпоз;:цнч f.(f2(x)) координат-но-зыпуклой Функции : Zn R и неубывающей выпуклой функции fi : R' И;

п

5} сепарабелыше функции fix)- Е f (* ), если f, (х ) -*вы-

1 *= 1

пуклые функции на R (заметим, что класс сепарабельных функций на координат>:сй роиетке совпадает с классом модулярных).

Теорема 2.3 (об отделимости). Если fг и f - соответственно координашо-выпуклан и координатно-вогнутая функции на Ii", причем ft(х) s f^Cx), то существуют такие сепарабельиые коорди-натно-випуклая f з л координатио-вогнутая f4 функции, а также линейная функция с(х), что f (х) S f„(x) а с(х) =! f (х) а f (х).

13 4 2

6) функции меры f(I) - д( и А ), где ц - аддитивная и

KCl

изотонная на кольце множеств (Afc) ;

7) функции энтропии

f(I) = Е • • • Е -р(х = О- , i с X) log р(х » <г1 , i е I).

<Г €Х CT 6Х

linn

8) р-координатно-выпуклые функции, т.е. функций для которых числа -р ....,-р , рz О являются верхними границами диаго-

1 п 1

нальных элементов матрицы [grad* f(x)] - дискретного аналога гессиана. Например, если f ^(х^сильно выпуклые функции на Р. с

п

параметром р , то Е ^ (х ) есть (р,...,р)-координатно-вьшуклая. 1 i=i 1 1 Теорема 2.4. Следующие утверждения эквивалентны:

1° f - р-коордипатно-выпуклая функция;

2° f(y)-f(x) s ((у-х)°: V*f(x-p) + ((х-у)е, V"f(xvy)-p))+

П

+ Ер,;

i=I

3° f (у) - f(x) з ((у-х)е, v'f(x-p) + Е р , х < у.

i=i

9) симметрические функции, значения которых не зависят от перестановки координат. Каждая симметрическая функция на Вп определяется градиент-вектором (а ,...,а ) по правилу

I ж I

f(I) Е а » а = grad (I) Vk, |I| i. Симметрическая функция 1-1 1 1

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

1 п

Теорема 2.5. Кяаос всех симметрических субмодулярных изо-тонных функций является конечнопорожденным полиэдральным конусом с остовом f1..... fn, где f"(I)«|I| при |I| < к и Gk(I)~k

при I X J t k, k=l.....n.

10) матрицы Монжа, т.е. матрицы со свойством с '*"(;t<il J<.13 s ctJ+ c^jj Vi.j « [n-1], как функции двух переменных i и j на [n]x[n] являются субмодулярными, а при дополнительном свойстве

з c|j + 1 + ~ координатно-выпуклыми.

11) функции свертки. Показано, что эпиграф {х<зНп: f(x)=s а} изотопной координатно-випуклой функции f(x) является порлдково-випуклнм множеством.

Теорема 2.6. Множество D s Нп является порядхово-пилуклым тогда и только тогда, когда оно совпадает с множеством точек максимума некоторой координатно-випуклой функции g: Hn R, т.о. можество D £ Н" порпдково-выпукло тогда и только тогда, когда оно совпадает с множеством нулей некоторой координатно-согнутой функции g: F" R^.

Теорема позволяет каждое ' пор'ядково-в'ыпуклое множество "кодировать" как множество Dg нулей некоторой координатно-вогнутой функции g (резольвента).

Следствие 2.7. ' Множество D= tx 's Z" : Ь'"а'Ах * b"}, где элементы матрицы А и'векторов b', Ь" - неотрицательные числа, совпадает с множеством нулей следующей координатно-вогнутой функции (функция свертки)

в» п п

g(x) = Е min(0, b| - £ а х ) + гаах(0, £ а х - Ьр) i = i j=i 11 j = i 1 3

Следствие положено в основу метода коррекции несовместных

систем диофантовых неравенств идейно восходящего к методам И.И.Еремина. '

Кривизной УВН-множества D в H называется число

1(D )

0(D) - min -— , D -Da [О,a],

а е н h(D ) a * о a

гле 1(D ) = min {h(x): x й Draa*}, h(D ) = raax fh(x): x e Draax}.

а а а а

УВН-множество кривизны 1 называется суперматроидом, а в Вп - матроидом. Пусть G класс резольвент со. свойством

et *

grad*g(x)s a Vx.g s G^.

Теорема 2.8. 1) если g e G , то 0(D ) a a"1;

a g

2) если g e G , то 0(D ) ь'(a .,+a )_1.

1 a • g * . . . *g 1 n

U 1 «1

3) если e(D.) e a., TO e(D n ... n D ) s (a-1 ,....a"1);

11 1 ra Ira

'4) кривизна пересечения га суперматроидов в Нп не меньше шах (m_t,(п-1)-1).

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

вами из формально введенного множества отрезков. Значение координатной выпуклости проясняет теорема 3.2 которая устанавливает ее сзязь с матроиднымн структурами. Пусть d(x,y)-=(h(xAy,xvy)+ +|h(x)-h(y)|)/2 - метрика на координатной решетке Н". Последовательность х=> х°,...,хк=»у элементов из Нп обладающая свойством d(xl,х')«1, i~0,...,k, k=d(x,y) называется d-цепью. -Пусть fes<1(x)={C: £(х) e 0(x)nD] - множество допустимых направлений в

точке х из шара О (х) радиуса 1, в Zn: fes*(~'(x) «• ti е [n]: .d

x±et e DJ, fes (x) = [(i.j): x±el±e e DJ. Множество D s Hn назовем коордииатио-вьшуклым, если между любыми его элементами

х.У существует d-цепь х°......хк, элементы которой обладают

свойствами :clcD, х1*1= £ (х*), £ е fesd(x). Каждое координатно-выпукяое множество является но только порядково-выпуклым, но и г—выпуклым.

Примеры координатио-выпуклых множеств:

1) пересечение координатно-выпуклого множества с d-интер-валом [а,b]d/минимальный шар 0d, содержащий а и h^J

2) слои .координатно-выпуклого множества;

3) декартово произведение координатно-выпуклых множеств DjXDjj- С (х1 ,х2) е НгхН8: х1 d Dt, х2 е D2J;

4) лифт [Сх.х )' е К""1: х б D, h(x)+h(x )= et) коорди-

n»l п*Ь

катно-выпуклого множества D в Н".

Конструкции из примеров легли в основу предложенгя 2.9 и, доказанной с его помощью теоремы 2.10 - 2.12.

Предложение 2.9. Для любых элементов х,у координатно-выпуклого множества D £ Н" существуют такие векторы

f в s *(х) Гав*(х) Г««*' (х)

Л* е Z , i" б 2 , А е Z , что

♦ ■ + +

у-Х-'Е - + Е Ао(в|- вл>:

1еГв.*(х> l€f«»"(*l tl,J)6r»m*'""(*>

■ |X*| + |л-| - |Л| - da(x,y).

Теорема 2.10. Локальный максимум каждой сепарабельной координатно-гылуклой функции на множестве D с Z" совпадает с глобальным тогда и только тогда, когда D -координатно-выпуклое множество.

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

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

Теорема 2.10 обобщена на несепарабельные функции.

Теорема 2.11. Пусть f - сужение на Zn выпуклой на Rn функции и D - однослойное множество. Тогда бикоордшттиое решение задачи шах Cf(x): х e D] является ее глобальным максимумом, если выполнено следующее условие: для любого разбиении " (N ,N )

о 1 .2

множества [п] существует такой субградиент . х функции f .в точке х9 для которого для всех таких (i,j) с К i х N2, что :с°-х°*0, выполняется неравенство (х°- x°)grad*~f(x9)) > О.

Теорема 2.12. Множество D* точек максимума координатно-выпуклой сепарабельной Функции f на координатно-выпуклоы. множестве D является координатно-выпуклым множеством.

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

ГЛАВА 3. МАТРОИДНЫЕ СТРУКТУРЫ

Термин матроиды лвел Уитни в 1935 году, заметив, что некоторые алгебраические свойства графов аналогичны свойствам векторных пространств. Ранее, в 1930 году Бан-дер-Варденом был изложен аксиоматический подход к линейной алгебраической независимости. После работ Биркгофа, Радо и Татта исследования матро-идов идут широким фронтом. Результат Эдмондса (1971) о том, что градиентный (greedy) алгоритм является оптимизационным аналогом свойства замены Маклейна-Штейница послужил толчком к приложению матроидов в ДО: субмодулярные и полиматроидные потоки, абсолютная унимодулярность и двойственная целочисленность, теория двойственности и минимаксные теоремы.

Понятие матроид неоднократно обобщалось. Так появились ориентированные матроиды, полиматроиды, суперматроиды, гридои-ды, g-полиматроиды, антиматроиды. Нами были введены и изучены новые матроидные структуры: неограниченные полиматроиды, обобщенные суперматроиды, полуматроиды. Основной результат главы -

характеризация обобщенных суперматроидов с помощью координатной

выпуклости и установление связи выпуклости и условия замены

Маклейна-Штейница.

Теорема 3.1. УВН-мнотество D в Нп

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

любая из следующих эквивалентных аксиом

Io (аксиома баз) множество максимальных элементов Бпахудо-

влетворяют условию замены.- Vx,y eDmax,Vp e N(x,y) 3j e N(y,x)

<& (p,j) 6 fes*,-(x,Dm"));

2 все максимальные элементы множества D имеют один и тог

те ранг и для каждого слоя D1 справедливо условие замены;

3° множество максимальных элементов Dmax удовлетворпег

условию замены в симметрической форме Vx,y е Dma*,Vp е N(x,y)

• 3j 6 N(y,x) & (p.j) 6 fes'*P'~(x,D'!lax) П fes*'-(y,Dmax);

4o D = D(r) = íx g Hn: £ h(x ) s r(I) VI £ [пЗЗ, где i -

íei

некоторая изотопная субмодулярная функция, г (и) = 0.

Для матроидов утверждение 3° есть известная теорема Грини, впервые в сформулированной форме оно доказано автором и Н.Н.Писаруком. Начиная с 1978 г., автор изучал пересечения двух суперматроидов, один из которых рассматривается в двойственной решетке Н*. Чтобы различать понятия суперматроидов в Н и Н* будем называть первый -нижним, а второй - верхним суперматрои-дом, точнее верхний суперматроид есть УВЕ-множество D'1 £ Н, обладающее свойством: для произвольного элемента а е Н все минимальные элементы множества D* п [а,1] имеют одинаковую высоту. Обобщенный суперматроид есть пересечение верхнего Dír*) и нижнего D(r~) суперматроидов в координатной решетке, ранговые функции которых связаны соотношением

grad* r"(A) s grad* г"(В) VA и В = [n]\i, А л В = в. С)

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

Теорема 3.2.-Следующие утверждения эквивалентны определению обобщенного суперматроида' D:

Io D = ix € Н": г"(1) з £ h(x ) s r*(I) VI £ [п]}, где

leí

г" - субмодулярная иг* - супермодулярная изотопные функции, удовлетворяющие соотношениям Франка:

г"(А) - г*(В) г r"(A\B) - r*(B\A) ' VA,В £ [п], 2° для любых х,у е D из условия h(x) a h(y) следует непу-

стота множества fes*(x,D ) n fes~(y,D „ ); (аксиома дсбавле-

xVy xVy

имя) и существует слой, который удовлетворяет аксиоме замены;

3° D - пересечение верхнего D* и нижнего D" суперматрои-дов, при этом каждый слой Dk удовлетворяет аксиоме замены, а из условия х,у s D, л*тг*л~(х) е D следует, что либо ie £es*(x,D) n л fes~(y,D), либо k е fes*(x,D) л fes~(y,D);

4° D -проекция базового слоя некоторого суперматроида. 5° D - координатно-выпуклое множество. Примеры обобщенных суперматроидов.

1. Целые точки обобщенных ' целочисленных полиматроидов -многогранников PC г",г*): [х е Rn : г"(1)а £ х =s r*(I), I е 2е"',

ICI

гдё супермодулярная й субмодулярная. функции г",. г* принимают целые значения и связаны соотношениями (*).

Теорема 3.3. Точка х° е R" является вершиной обобщенного полиматроида Р(г~,г*) тогда и только тогда , когда существуют такие перестановка п е S я число О s k s п, что

х° ■

*ÎI(i>

grad*(l)r-(n[i-l]). i=l,..,k grad*(i)r*(n[i-l]\n[k]), i=k+l,

2. Многогранник размещений P(r~,r*) есть выпуклая оболочка упорядоченных n-выборок без повторений множества из m чисел

а >. . . > а >0 при г~(1)=а +..,+а. . , r*(X)«= а +а +. . .+а , .

1га 1 J X J m ю-1 ra- | I | +1

3. Многогранник размещений при n = m называется перестановочным. Если а — n-i+1, то перестановочный многогранник есть выпуклая оболочка всех перестановок чисел . 1,2,...,п (пермута-эдрон Рп). Описание пормутаэдрона в виде системы линейных неравенств ■ 11I Í l"1"1^ =s Е х. а Zn-\l\+l I J-1 независимо давалось

îei

многими авторами (Balas, Gaina & Gupta, Ковалев & Исаченко).

4. Симметрический обобщенный полиматроид. Обобщением многогранника размещений является пересечение верхнего и нижнего полиматроидов с симметрическими ранговыми функциями г",г*. Такое пересечение является обобщенным полиматроидом тогда и только тогда% когда их градиент-векторы а~г ...ь а" и a*s...га* связаны

1 n 1 n

соотношениями а" а а* , i=l,...,n.

1 n-i »1' ' '

5. Обобщенным полиматроидом является пересечение верхнего Р(г*) и нижнего Р(г~) полиматроидов в случае, когда функции' г* (г-) есть суперпозиция Hey6nBániqefi выпуклой f* (вогнутой f") и

модулярной с при условии ?£*(. £ с ) а £ с ).

161 1 € X 161

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

v

функцией пропускных способностей <3:Е Н задано множество Р а И 1.

Пусть множество Р (предложений) с помощью потока ч> переносится

в множество Р = р(Р ) на стоках V .

2 12

Теорема 3.4. Если ? — обобщенней полиматроид, то Ра= р'(Р ) также обобщенный полиматроид.

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

V

графе, при этом Р есть точка (Ь: К *). Отображение *>(Р1)

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

В заключении главы изложено еще одно обобщение матроидов -полуматроиды. Матроиды возникли как обобщение линейной независимости, а полуматроиды - конической. Напомним, что векторы а1,...,а" называются конически зависимыми, если существуют неот-

п

рицательные х не все одновременно равные нулю, что £ х^1» О.

1 1=1

Полуматроидом ранга <1 называется пара (И,В), где N - непустое

множество и В - семейство его непустых подмножеств мощности <1 (кобаз), удовлетворяющих аксиоме: для любого элемента е из каждой кобазы V существуе™ единственный 1 е такой, что У\е и £. также кобаза.

Теорема 3.5. Если Р - невырожденный <1 -мерный многогранник и N - множество его фасет, а В - множество вершин, то пара М(Р)=(И,В) является полуматроидом (полиэдральным полуматроидом).

Полиэдральный'полуматроид есть аналог векторного матроида: у векторного матроида множества V е В интерпретируются как базисы, а у полиэдрального (конусного) - как допустимые базисы. Два полуматроида М' и М" называются изоморфными, если они изоморфны как гиперграфы. Говоря об изоморфизме помеченных полуматроидов, имеем в виду изоморфизм помеченных гиперграфов.

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

Теорема 3.6. Многогранники ?' л Р" комбинаторно эквивалентны тогда и только тогда, когда их полуматроиды М(Р') и М(Р") изоморфны.

Основной аппарат для установления эквивалентности помеченных многогранников - спектральная теория (см. нашу совместную с В.А.Емеличезк:-! и М.К.Кравцовым монографии. Спектром S(bitb2) многогранников Р(Ь ) и Р(Ь ) из класса 3(А) невырожденных многогранников Р(Ь) з Rn, заданных условиями Ax=b, х г О, при фиксированной (тхп)-матрйце А ранга и назовем множество всех чисел а е [0,1] таких,-что многогранник P(xbi + (l-x)b2) - вырожденный. :

Теорема 3.7. Полиэдральные полуматроиды М(Р ), М(Р2), Р1 е Э(А), изоморфны, а следовательно многогранники Р и ?г комбинаторно эквивалентны тогда и только тогда, когда их спектр, i

Теорема 3.8.1° Многогранник размещений Р(г",г") с Rn комбинаторно эквивалентен пермутоэдрону Р

п ♦ 1

2° Многогранник задачи стандартизации с треугольной (пхп)-матрицей смежности двудольного графа комбинаторно эквивалентен (п-1)-мерному кубу.

3° Многогранник задачи стандартизации с сингулярной (пхш)-матрицей смежности двудольного графа комбинаторно эквивалентен пермутаэдрону.

4° Полиматроид Р(г) в R", ранговая функция которого строго субмодулярная и строго изотопная, комбинаторно эквивалентен перестановочному полиматроиду.

5° Класс симметрических полиматроидов в R" состоит из 2п-1 комбинаторно не эквивалентных многогранников.

ГЛАВА 4. АНАЛИЗ ГРАДИЕНТНЫХ МЕТОДОВ

Принципиальные трудности, связанные с решением, задач ДО, проявляются в методе частичных порядков в экспоненциальных оценках мощности множества Dmax. Представляются естественными приближенные алгоритмы, выделяющие подмножество множества D™**, например, одноэлементное. Распространение получили градиентные алгоритмы, построенные по итерационной схеме: среди элементов л'Чх1) допустимого множества D непосредственно следующих за х1 выбргть в качестве xt+1 элемент с наибольшим значением функции

grad+f(x4) и так продолжать до тех пор, пока не будет получен максимальный элемент х®. Идея градиентных алгоритмов высказана еще Монжем для специальной транспортной задачи. Алгоритмы градиентного типа широко применялись в работах школы С.В.Яблонского при минимизации Д.Н.Ф. На решетке Z" с отношением порядка xs у » «♦ х з у градиентный алгоритм есть алгоритм координатного подъема: х'*^«» х'+ el(t)> гДе eKt)~ еДиничный орт, отвечающий максимальному градиенту grad*f(x*) для i е fes^Cx*,D); на булеане (2м,с) - есть алгоритм конструирования множества пошаговым добавлением допустимых элементов (ребер,вершин), обеспечивающих максимальное приращение функции. Качествр градиентного решения зависит от стартовой точки форы, либо серии из р таких точек, затем из построенных решений выбирается' наилучшее. Построены серии градиентных алгоритмов с оценкой точности лучшей, чем у наилучшего алгоритма серии. Рассматриваем также двойственные градиентные алгоритмы (DG), которые стартуют в точке 1 и которые завершают работу как только точка х*'"1 e D. Если выбор'направления осуществляется по правилу

grad fCx'.x")

|grad g(xt,x")|

(градиент резольвенты g указывает скорость приближения к допустимой области), то такие алгоритмы, называем двойственными градиентными с растяжением (1Х5Ю.

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

В предложенной методике анализа градиентных алгоритмов А нахождение гарантированной оценки погрешности

орЬч _

е(А) - вир - f<x*)|

|f(xA)|

«eo '' k ■

сводится к оптимизационной задаче на каждой итерации t min £ Д'

t-i *"

при ограничении на величины Д' относительных приращений критерия по отношению к оптимальному его значению. Классы ограничений вытекают из описания алгоритма А и свойств монотонности градиентов критерия f и резольвенты g, методов аппроксимации величин h(x*,x°pt).

Теорема 4.1. Гарантированная оценка погрешности градиентно-

го алгоритма максимизации изотонной координатно-випуклой функции £ на множестве D равна:

1) (l--jf)r' где h = h(D) , г - r(D);

f 1/2, h i 2r

Z)-\ , „ при условии, что D - суперматроид;

[ rh (1-h) , h < 2r

3) при условии, что D - УВН-мнояество кривизны ос;

4) 1-a при условии, что D - УВН-множество кривизны се, а f -сепарабельная функция;

5) 1/2 при условии, что D=D -. множества нулей координатно-

я

вогнутой функции J е G^ (задача о g-сочетании).

Частными случаями задачи о g-сочетании являются задачи о паросочетаниях, назначениях, транспортные задачи.

Ёсли D - УВН-множество в' 2tn'(независимая система), то требование сепарабельности функции обращает ее в линейную. Для этого случая при предположении изотонности f(x) теорема 4.1 установлена Дженкинс, Корте и Хауссманом.

Следствие 4.2. Градиентный алгоритм строит глобальный максимум сеиарабелъной координатно-выпуклой функции на супер-матроиде.

Условия оптимальности градиентного алгоритма установлены еще в 1926 г. чешским математиком Борувкой, для униморфного по-лиматроида известны, как критерий Гросса, но получили широкую известность только после работ Радо и Эдмондса. Без использования матроидного аппарата Н.И.Глебов в 1973 г. установил более общий результат: градиентный алгоритм координатного подъема строит точку глобального максимума выпуклой сепарабельной функции на целых точках полиматроида. Этот результат был нами обобщен на обобщенные суперматроиды в произвольных координатных решетках. В последнее время исследовались условия оптимальности градиентных . решений в задачах на некоординатных решетках (гридоиды Корте-Ловаса, геометрии Файгла).

Градиентный алгоритм требует в наихудшем случае nh(D) обращений к f-оракулу и гарантирует получение решения х® с точностью f(x9) £ e(D)fopt. Повышение точности требует существенного увеличения трудоемкости приближенного алгоритма.

Теорема 4.3. Пусть алгоритм А строит решение хА со свойст-

вом f(xA) > eCD) fopt для каждой сепарабельной координатно-выпу-лой функции f(x) на УВН-мнояестве D^ кривизны e(D^). Тогда ширина S(Hn) есть нижняя граница для числа обращений алгоритма А к t-оракулу.

Подробнее этот вопрос исследовался Корте и Хауссманом для задач на независимых системах.

В дискретной математике идея синтеза из "ненадежных" алгоритмов эффективных,, восходящая к Нейману, получила широкое рас-■ пространение. Пути использования этой идеи в ДО указали ' Ю.И.Журавлев и В.К.Леонтьев. Один из них требует построения ' серии алгоритмов, каждый из' которых имеет свой класс "плохих" задач, Предложены три схемы построения серии градиентных алгоритмов: параметризация функций растяжения градиентов, старт из различных точек (фора), релаксация и разбиение. Схемы проиллюстрированы на модельных задачах.

Исследованы алгоритмы чередующихся замен, т.е. алгоритмы реализуемые итерационным процессом: xt<Pl= хь+ <v£t, где £ - альтернирующий вектор. Хорошо известная в теории графов теорема Бержа о сходимости такого алгоритма для задачи о максимальном паросочетании обобщена на задачи о g-сочетании, а также задачи на координатно-выпуклых множествах, задачи обобщающие субмодулярные и независимые потоки.

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

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

ГЛАВА 5. ПРИЛОЖЕНИЯ К МОДЕЛЬНЫМ ЗАДАЧАМ

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

тах с(х), а4(х) з Ь , 1=1.....га, х е 2,п ,

п

где критерий с(х) = £ с (х ), и функции в ограничениях:

а^х) = £ а^(х^) - сепарабелыш, а функции с^х^ и а^(^)

изотопны па интервале целых чисел [0,{1 ]. В зависимости от вида

функций СМ - неубывающие, С - выпуклые, и - линейные) задачу о

рюкзаке будем обозначать ХУКРП, где Х,У - классы, к которым

принадлежат,'соответственно, критерий и функций в' ограничениях'.

Если оба класса совпадают, то одна из букв опускается.

Градиентный координатный алгоритм О за 0((ш+1)Н) вызовов

градиент-оракула строит решение х° задачи СМРР с достижимой

к

п

гарантированной оценкой точности в, где Н= £ 11 . Гарантированная

1

оценка точности алгоритма А равна 1-е(А), где с(А)~ погрешность. Указаны способы вычисления кривизны О.

В градиентном алгоритме с растяжением И? используется обобщенный градиент grad*c(xt')/ЛJ (х*-) с коэффициентом растяжения Л^.

Теорема 5.1. Если \ (хь) = £гас1*а(х1) , то алгоритм для

1 J ■ J

задачи СКР имеет гарантированную оценку точности 1/2.

В задаче ЬКР* со свойством с^=1, которая извест-

на как задача поиска максимального верхнего нуля пороговой функции, алгоритм вН строит оптимальное решение. Эта задача исследована в предположении, что коэффициенты линейного неравенства ах а Ь неизвестны. Теорема 5.1 остается верной для задачи МКР1 с функциями, обладающими свойством

^гай*с(х + е ) grad'*c(x)

----— з -г-

grad*a(x + е^) grad*a(x)

Для задачи СКР1 (с ограниченными переменными) оценка точности 1/2 для алгоритма БИ не гарантируется.

Теорема 5.2. Для задачи СКР' справедливо соотношение

П

шах {с(хс"),с(11^), о е [п]} г с(хор'')/2, т.е. гарантированная оценка точности 1/2 обеспечивается для ре-

шения, являющегося лучшим в серии из n + 1 приближенных решений.

Таким образом, градиентный алгоритм с растяжением GR обеспечивает решение задачи СКР1 с гарантированной оценкой точности 1/2 за время 0(nH(logZf+logn)) его трудоемкость зависит от Н и, следовательно, он не является полиномиальным. Совместно с В.М.Котовым построен следующий полиномиальный алгоритм.

Дихотомический градиентный алгоритм PGR: 1°= О, u°= h, m* - [(1* + u* + 1) /2].

П

Если ' > b> TO ujMt> = mi-(t) -

где j*(t) - arg miri lj <u ].

Если ' ¿^"J) < b- TO " " mj.(t>

где j*(t)= arg max < u ).

Когда lt=ut, полагаем x1—l'— u1 и выбираем лучшее решение xDGR из серии {х'.И^, j б inj}.

Теорема 5.3. Алгоритм DGR строит решение xDGB с неулучшаемой гарантированной оценкой точности 1/2 за время 0(n log h log n),

op

в том числе требует 0(n log h ) вызовов градиент-оракула.

ср

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

Еще один путь уменьшения трудоемкости алгоритмов - замена исходной задачи аппроксимационной путем покрытия пространства данных или пространства допустимых решений с-сетью и реализация градиентных алгоритмов на аппроксимационной решетке {О,а1,...,а1}

log h

(а - натуральное число). Для х,у е (О,а,а2,...а J,hj), х ь у

определим конечно-разностный оператор

с (х) - с (у)

Ух'у) - V-v -

аналог обобщенного градиента.

Алгоритм AGR(et): х°- О, b°= b', x***(=xj(t),

j * j(tj, b'*1— b* - a,, - x*), где j(t),x(t) пара, на

J I v / J I t J . J

которой достигается

max {«jiXj. x*): x* < x} 6 Z(al) fl lO.h], a (x - x') < b*]. Теорема 5.4. Алгоритм AGR(a) за время O(n^log2h ) строит

OL с p

решение задачи МКР^ с неулучшаемой гарантированной оценкой точ-

П

ности 1/(2а).

Двойственный градиентный алгоритм TJGR изложен для двойственной задачи min с(х), а (х) г b , х з h, х <= Zn.

h 1.1 ♦

Теорема 5.5. Для двойственного градиентного решения xDon задачи LKPm справедливо соотношение

п

c(xDGn) 3 (1 + log Ё b + log ц) c(xopl), 1 = 1

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

В-задаче LrCPm с а е Z^ и b^ Z + имеет место ц а 1 и поэтому

га

оценка точности принимает вид: е= 1+ log £ b (Н.Н.Кузюрин) . В

i=i-

t:i

задаче покрытия Е b = m и-, поэтому, с = 1+ log ш, (Р.Нигматулин,. i = i 1

В.Хватал), а, если учесть, кроме того, что в задаче покрытия

п

с(х) = Е х , то с = 1+ log га - log с . = i J

Серия градиентных алгоритмов GR(£) построена введением в коэффициент растяжения Л параметра О з ^ s 1:

J , J '

Теорема 5.6. Для задачи LKP гарантированная оценка точности алгоритма GR(О равна 36/61 при £ = О; 4/7 при £ - 1/2 и 1/2 при Неулучшаемая гарантированная оценка точности серии из

двух алгоритмов GR(O) и GR(1) равна 2/3. Трудоемкость алгоритма GR(e) - 0(n log п).

Алгоритм с полурастяжением GRj: единственное отличие от GR -следующее определение обобщенного градиента: , если 2а^ > 3

и 5 =2с , если 2а < 5 J J J

Серия алгоритмов замен (BG^, k=l,...,s):

xk - -1 ii ei«>'+eJ '

1 =k ♦ 1 max

где j(l).....j(s).- номера ненулевых координат решения х ,

упорядоченные так, что сj(t,х cj<>/aj<> • на по~

следнее место j(s) поставлен элемент q, отвечающий шах (с^: х°н=1), jmax_ номер максимального Cj такого, что хк - допустимое решение.

Теорема 5.7. Гарантированная достижимая оценка точности серии из алгоритмов GRi+BGk< k-1, . . . ,s для задачи LKPj равна 2/3': Для задача о разбиении РР4, т.е. задачи LKPj при сх=ах.

n

b= Г с /2 построена серия алгоритмов BG : в начале градиентным

J-i i '

координатным алгоритмом строятся параллельно два решения, а

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

Теорема 5.8. Серия алгоритмов BG имеет трудоемкость

1 I 2

0(n log п) и гарантированную .оценку точности 5/6.

с-градиентный алгоритм G (к,в): выбираем и упорядочиваем

1 I 2

только ш элементов: с с t с. j-m+1,...,п; очередной эле-

1 m J

мент ct помещаем в более заполненный рюкзак, если его вес с этим, элементом не превышает Ь+е, e-b/k. Если же этот вес больше Ь+е, то помещаем элемент во второй.рюкзак и процесс повторяем до . тех пор, пока: а) вес какого-то рюкзака окажется в пределах b-с, Ь+е; б) элемент помещен в менее заполненный рюкзак и его вес превысил Ь+е. В качестве решения берем характеристический вектор множества с большим весом, если этот вес не превосходит Ь, или его дополнения, если вес превосходит Ь.

Теорема 5:9.1° с-градиентный алгоритм Gt z(7,5) для задачи о разбиении имеет трудоемкость 0(п) и неулучшаемую гарантированную оценку точности 6/7.

2° с -градиентный алгоритм Gt (9,7) с предварительным' помещением в один рюкзак элементов {1,5,6} при решении задачи о разбиении имеет трудоемкость 0(п) и гарантированную оценку точности 8/9.

Другая известная модельная задача в ДО - задача коммивояжера. Рассматриваемая задача коммивояжера на максимум есть частный случай задачи LKP™. Кривизна допустимого множества в симметричной задаче коммивояжера равна 1/(2-[п/2]), в асимметричной -1/3. Поэтому из теоремы 1 вытекает оценка точности градиентного алгоритма, трудоемкость которого 0(и3). С помощью методики анализа запретов дан прямой вывод этих оценок и доказана их достижимость. Для частного случая, когда с "»а^Ь^ (матрица весов имеет ранг 1), с помощью того se метода анализа запретов доказано, что гарантированная достижимая оценка точности градиентного алгоритма равна 1/2. Методика , анализа запретоь требует построения рекурсивных соотношений между весом очередного ребра включаемого в градиентное решение и весами некоторых ребер из

оптимального решения (незапрещешшх к текущему моменту).

Алгоритмы для задач коммивояжера в которых в качестве форы используются ацикличные фрагменты решений релаксационных полиномиальных задач оптимизации: задача о максимальном паросочетании (matching), 2-сочеташш (bi-matching), назначении (assignment), дереве (tree) обозначаем символом X+G, где X - имя задач, использованный для нахождения форы. С помощью метода анализа запретов доказана

Теорема 5.11. Для градиентного алгоритма с фороп справедливы следующие оценки-трудоемкости и точности:

1) matching + G - 0(n3), 5/8;

'2) bi-rcatching + matching + 'G - 0(n4) , 13/18; ' . . . .. Лучшие результаты да.^т серия из двух алгоритмов, у каждого из которых своя стартовая точка.

Градиентный алгоритм с форой G^:

1) находил паросочетание Mopt=[С i г,j ),...,(ik .j^)] максимального веса в исходном графе;

2) находим паросочетание М° максимального веса в графе К с

п

модифицированными весами с — О, для реб^р (i,j) е Мор ;

3) устраняем подциклы в множестве Moptv М°, выбрасывая из каждого подцнкла ребро минимального веса.

Градиентный алгоритм с форой Gz:

1) находим паросочетание 1.1' максимального веса в графе К , полученном из полного К добавлением s новых вершин

п + в п

11+1,...,n+s, со следующими весами с| j=ci ^ , (i , j ) ft U°pt, + k ^ •= «■ с ' = с , k=l, . . . , s ;

n + k , 1, 1 J, '

k k k

2) строим фору X° - (M'n Kn) и Ki^.j,) S Mopt: (n + s.j^) или (n + s,i ) 6 M*].

s

Теорема 5.12. Серия из алгоритмов G ,G имеет- трудоемкость 0(п ) и точность 2/3.

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

Релаксация. Решается серия из m полиномиальных задач оптимизации, допустимая область в i-й обладает свойством: найдутся о^ допустимых решений которые в объединении содержат оптимальное решение, например, релаксационной может быть задача о паросочетании максимального веса, так как найдутся два

паросочетания в объединении дающие оптимальный цикл. Исходя из оптимальных решений W*,...релаксационных задач строится мультимножество W = k W*.w ... и k^Vf^.

Разбиение. Семейство ребер W разбивается на s подмножеств XJ, каждое из которых есть либо гамильтонов цикл, либо фора (после устранения частичных циклов) для градиентного алгоритма. В качестве результата берется лучший из циклов.

Построены три серии для симметричной задачи коммивояжера: релаксационная задача в первой серии - задача о паросочетании, во второй - о 2-сочетании, в третьей - релаксационными являются обе эти задачи. В первой серии W - 6Mopt, во второй - W — 6Copt. Далее; множество W в двух первых сериях разбивается на четыре гамильтоновых цикла, а в третьей - на два.

Теорема 5.13. Справедливы следующие оценки трудоемкости и точности серий для метрической задачи коммивояжера

1) 6 matching/4 - 0(п3), 3/4;

2) 4 bi-raatching/4 - 0(п4), 5/6;

Для модифицированной серии 6 matching/4 Сердюковым доказана ее асимптотическая оптимальность для евклидовой задачи коммивояжера. Для серии (matching + bi-matching)/2 трудоемкостью 0(п4) Косточкой и Сердюковым доказана точность 3/4. Автором и В.Ы.Котовым построена серия matching+matching'+ G с той же точностью, но трудоемкостью 0(п3). В этой серии также две релаксационные задачи, но обе о паросочетании максимального веса: одна, как ,и ранее, на исходном графе, а вторая на'модифицированном, получаемом путем преобразования каждого ребра (i,j) б Mopt в некоторую конструкцию. Пусть Р' - паросочетание максимального веса в модифицированном графе, покрывающее все новые вершины. Множество ребер. Vi - MoptuP разбиваем на два подмножества, каждое из которых достраивается градиентным алгоритмом до гамильтонова цикла. Оценка точности серии (matching+matching')/2+G равна 3/4.

Для асимметрической задачи коммивояжера схема релаксаций и разбиений дает алгоритм, в котором релаксационными является задача о назначении и паросочетании. Такой алгоритм имеет точность 4/7. Таким образом все построенные в этой главе ^алгоритмы имеют рекордную точность в классах алгоритмов с фиксированной трудоемкостью.

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

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

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

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

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

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

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

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

7. Для модельных задач ДО - о рюкзаке и коммивояжере построены алгоритмы с рекордными оценками точности как в подклассах задач, так и в подклассах алгоритмов с фиксированной сложностью.

ОСНОВНЫЕ ПУБЛИКАЦИИ .1. Ковалев U.M.!.Дискретная оптимизация // Минск; Изд-во Белорус, ун-та, 1977. - 192 с.

2. Girlich Е. Kowäljow М. Nichtineare diskrete Optimierung // Berlin: Akademie, 1981. - 218s.

3. Емеличев В.А., Ковалев М.М., Кравцов M.K. Многогранники, графы, оптимизация // М.: Наука, 1981; англ. перевод.: Yemelichev V., Kovalev М., Kravtsov М. Polytopes, graphs and optimisation // Cambridge University Press, 1984. -243 p.; нем. перевод:. Emelicev V.A., Kovalev M.M., Kravcov M.K. Polyeder, Graphen, Optimierung // Berlin.: Wissenschaften, 1985, 356s.

4. Girlich E., Kovalev М. (ed). Diskrete Optimierung. Jena: Universität, 1985. - 155 s.

5. Ковалев М.М. Матроиды в дискретной оптимизации //Минск: Университетское 1987.' - 224 с.

6. Ковалев М.М., Писарук H.H. Моделирование в схемотехническом и топологическом проектировании. - Минск: БГУ. - 1991. -117 с.

7. Емеличев В.А., Ковалев М.М. О локальных минимумах в транспортной задаче с функцией цели, вогнутой по Шуру // -Журн. вычисл. математики, и мат. физики:- 1972. - N 5. -С. 1312 - .1316.

8. Емеличев В.А. Ковалев М.М. Полиэдральные аспекты дискретной оптимизации // Кибернетика. -1982. - N 6. - С.54 - 62.

9. Емеличев В.А., Ковалев М.М., Рамазанов A.B. Погрешность градиентных экстремумов строго выпуклой функции дискретного аргумента // Дискр. математика. - 1990. - Т.2, вып.2 -С. 127 - 137.

10. Гляков П.В., Ковалев М.М. Котов В.М. Оценка погрешности серий приближенных алгоритмов // Методы, алгоритмы и программы решения экстремальных задач. - Минск: АН БССР. -1985.

11. Димов Е.Т., Ковалев М.М. Кривизна упорядоченно-выпуклых множеств // Докл. АН БССР. - 1984, 28. - Н 1. С.9-11.

1-2. Ковалев М.М. Выпуклое симметрическое програмирование. В кн. Материалы 1 Всесоюз. конф. по исслед. операций. Минск, 1975. С.218-222.

13. Ковалев М.М. Полиэдральные полуматроида // Изв. АН БССР, сер. физ-мат н..- 1979. - N 3..- С.6-12.

14. Ковалев М.М. Метод частичных порядков ' // Докл. АН БССР, 1980, 24, N2,с. 113-116.

.....15. Ковалев М.М. ; Максимизация выпуклых'. функций.. на супер-..

матроидах // - Докл. АН БССР. - 1983, 27. - N 7. С.584-587.

16. Ковалев М.М. Новые приложения метода.частичных порядков // Кибернетика. - 1985. - N 2. С.11-16.

17'. Ковалев М.М. "Градиентные методы максимизации выпуклых функций на дискретных структурах // Кибернетика, 1985. - N 6.

18. Ковалев М.М. Конусы симметрических и потоковых субмодулярных фукций // Кибернетика, 1985, И 5. - С.122-123.

19. Ковалев М.М., Гирлих Э. Структура допустимой области задачи стандартизации // Изв. АН БССР, сер. физ.-мат.н., 1980. - N 4. - С:5-10.

20. Ковалев М.М., Горунович С.А. Переставочные полн-матроиды // Известия АН БССР, сер. физ.-мат.н., 1980. - N б. -С.9-14.

21. Ковалев М.М. , До Зуй Чинь. Анализ градиентного алгоритма максимизации дискретно-вогнутой функции // Известия АН БССР, сер. физ.-мат. наук. - 1980. - N 2. - С.69-75.

22. Ковалев М.М., До Зуй Чинь. Задача параметрической выпуклой дискретной оптимизации // Вестник БГУ, сер 1. - 1990. -ИЗ.- С.35-38.

23. Ковалёв М.М., Емеличева В.С. Экстремальные свойства частично-упорядоченного множества плоских разбиений // - В кн. Вопросы кибернетики. - М.: Сов: радио, 1975. - С.92-99.

24. Ковалев М.М., Котов В.А. Анализ градиентного решения задачи коммивояжера // Иурн. вычисл. математики и мат. физики, 1982. - N 1. - С.1035-1038.

25. Ковалев М.М., Котов В.М. Анализ алгоритмов построения

гамильтонова цикла максимального веса // Изв. АН БССР, Сер. физ.- мат. наук, 1984. - N 4. - С.45-50.

26. Ковалев М.М., Котов В.М. Субоптимальные алгоритмы в целочисленном програмировании // Докл. АН БССР,- 1982, 26. -N 11. - С.969-972.

27. Ковалев М.М., Котов В.М. Оценка погрешности серий приближенных алгоритмов // Вестник БГУ, сер. 1. - 1985.- N 3,

28. Ковалев .М.М., Исаченко А.Н., Нгуен Нгиа. Линеаризации кмбинаторных задач оптимизации // Докл. АН БССР; 1978. -т.22. - N 10. - С.869-872.

29. Ковалев М.М., Кочкаров A.M. Дискретное гиперболическое программирование // ■Сб. Математические модели и методы оптимального планирования.. Минск, НИИЭМП, 1980. - С.50-55,- ■

30. Ковалев М.М., Миланов П.Б. Минимизация дискретно-выпуклых функций на структурах Иордана-Дедекинда.// Докл. АН БССР, т.24. - 1980. - N 9. - С.784 - 787.

31. Ковалев М.М., Миланов П. Монотонные функции многозначной логики и суперматроиды // Ш. выч. мат. и мат. физика, 1984, N 5. - С.786 -790.

32. Ковалев Ы.М., Мощенский A.B. Оптимальный поиск экстремумов выпуклых функций на решетках // Дискретная математика. 1990. - т.2, вып.1. - С.133 - 141.

33. Ковалев М.М., Мощенский A.B. Поиск максимального верхнего нуля пороговой функции многозначной логики // Шурн. выч. мат. и мат физ. ■■ 1990, 29, N 4. О С.620-622.

34. Ковалев М.М.\ Писарук H.H. Обобщенные матроиды // Докл. АН БССР. - 1984, 28. - N 11. - С.972 -975.

35. Ковалев М.М., Писарук H.H. Независимые потоки и полиматроиды // Вестник БГУ, сер.1, 1984. - N 3. - С.41 - 43.

36. Ковалев М.М., Писарук H.H. Независимые потоки с дискретно-вогнутой функцией затрат //. Ж. вычисл. матем. и матем. физ., 1985, т.25. - N 5. - С.757 - 771.

37. Ковалев М.М., Писарук H.H. Градиентные методы в выпуклом целочисленном программировании // Докл. АН СССР, 1985, т.289. - N 6. - С.1322 - 1326.

\ 38. Ковалев М.М., Писарук H.H. Матроидный подход к

декомпозиции. Техническая кибернетика, 1992. - N 3, - С.122-134.

39. Ковалев М.М., Пирьянович В.А. Локально-стохастические алгоритмы дискретной оптимизации // Кибернетика, 1982. - N 1.

- С.100 -104.

40. Ковалев М.М., Рогов С.Ф. Сложностные аспекты метода частичных порядков. - Изв. АН БССР, 1987. - N 3. - С.31-36.

41. Ковалев М.М., Топчишвили Л.А. Несобственные задачи выпуклой дискретной оптимизации // Вест. БГУ. - 1991. N 1.

.42. Kovalev М. Demimatroide. In: Colloque International sur la theorie des graphes et la combinatoire - Marseille. - 1981.

- P.9.

43. Kowaljow M. Supermatroids and convexity // In: 24 Internat. Vi. Kolioqium, Ilmenau: TH, 1982. - S.215-217.

44. Kovalev M., Koppe V. Zu einigen Problemen der Reihen folgeoptitnierung der operativen Steuerung in FMS /.' Optimization, 1990..- P.109-121. . ...

45. Girlich E., Kowaliow M. Minimierung konvexen Funktionen über unbeschrankten polymatroiden // Inter, tagung "Optimierung

- Theorie und Anwendung", Eisenach, 1978. - P.22-25.

46. Kovalev M., Pisaruk N. Greedy algorithms en convex-ordered sets // Institut fur Discrete Mathematik: Bonn: Universität Report 90640 - 1990. - 11 p.

47. Girlich E., 'Kowaljow M. Zur mathematischen Theorie der optimalen Standardisierung // Math. Operations und Statist, 1980, 11. - N 3. - P.547-561.

48. Girlich E. , Kovtaljovi M. Eine Problem klasse nichtlinearen diskreten Optimierung // Vfiss Zeitchr. der FSN Jena, Math.-nat. Reiht' 28 (1980). N 2. - P.327-338.

49. Milanov P., Kovalev M. On the accuracy of gradient algorithm in solving integer optimization problems // Comptes rendu Acad. sei. Bulg., 1980. - N 11. - P.1459-1462.

50. Kovalev M., Girlich E. Uber einige Aufgaben der optimalen Standardisierung // Die Technik, 1976. - 9. - P.572-574.

51. Kovalev M., Girlich E. Zum Problem der optimalen Standardisierung /"/ Math. Operations. Statist., 1977, 8..- N 1. -P.89-103.

52. Kowaliow M., Pisaruk N. Dekompositions methode zur minimierung Submoduleren Funktionen // Internationale Tagung Mathematische - Optimierung - Theorie und Anwendungen: TH Ilmenau, 1989. - P.132-136.

Подписано в печать 22.12.92. Формат 60x84/16.■ Уел.печ.л. 2,1. Уел.кр.-отт. 2,22. Уч.-изд.л. 2,0. Тираж 100 экз. Заказ 96. Бесплатно.

Белорусский государственный университет. 220080, г. Минск, пр. Ф.Скорины, 4.

Отпечатано на ротапринте Вычислительного центра АН Беларуси. 220072, г. Минск, ул. Сурганова, 11.