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

ОД АКАДЕМИЯ НАУК РЕСПУБЛИКИ БЕЛАРУСЬ „ ИНСТИТУТ МАТЕМАТИКИ

:ЛАР ^

УДК 510.854

ЗАПОРОЖЕЦ Александр Александрович

ПОЛИМАТРОИДНЫЙ ПОДХОД ПРИ ИССЛЕДОВАНИИ

ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ, МНОГОГРАННИКА АЛЬТЕРНИРУЮЩИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И КОНУСА СУБМОДУЛЯРНЫХ ФУНКЦИЙ

01.01.0!) - математическая кибернетика

АВТОРЕФЕРАТ

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

Минск - 1996

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

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

профессор Ковалев М.М.

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

профессор Метельский H.H.,

- доктор физико-математических наук, профессор Сотсков Ю.Н.

Оппонпрущая организация - Вычислительный Центр АН России.

Защита диссертации состоится 12 апреля 1996 г. в Ля— часов на заседании совета по защите диссертаций Д 01.02.02 в Институте математики АН Беларуси по адресу:

220072. Минск, ул.Сурганова, 11, Институт математики АН Беларуси, конференц-зал

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

Автореферат разослан " ".¿^^^¿Лл-ШЭ6 г.

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

Астровский А.И.

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

Актуальность темы.

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

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

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

характеризацни экстремальных лучей конуса Л(к) была поставлена еще Эдит сом в 1971) году. Ее решение тесно связано с дальнейшим развитием теор декомпозиции субмодуллрных функций, играющей важную роль при ' сшт алгоритмов решения оптимизационных задач с полиматроидпой допустим областью. В общем виде данная проблема чрезвычайно сложна и полност! решена только для п = 2,3,4,5. Поэтому актуальной становится задача вы; ления возможно более широких подконусов конуса А(п) и характеризацни экстремальных лучей.

Связь работы с крупными научными программами и темами. .

Диссертация выполнялась с 11)91 по 1995 год на кафедре МО САПР Белг< университета в соответствии с плановыми научными исследованиями по те "Разработка моделей, методов и программного обеспечения решения дискретш задач оптимизации проектных решений в САПР изделий микроэлектроники вычислительной техники'', а также на кафедре математической оптимизац: Магдебургского университета (Германия) в рамках гранта ОоШеЬ ОатНег-иш! К Вепг-НШ'Пш? N 2.9:5.22.

Цели и задачи иследования.

Конкретные цели работы, с учетом вышесказанного, состоят в следующем:

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

• найти линейное описание МАП и исследовать его комбинаторные свойств

• построить эффективные алгоритмы решения задач линейной и сепарабельн оптимизации на МАП:

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

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

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

1) Получен ряд новых свойств и указаны способы построения нижних и верхи оценок градиентного решения ЗРР.

!) Разработан дихотомическим .алгоритм (ДЛ) дли решении ЗРР и доказана, ого полнномнальность. Показано, что алгоритм ДА имеет сложность, практически совпадающую с рекордной.

!) Построены эффективные комбинаторные реализации алгоритма ДА для однородных, обобщенных симметрических, цепочных и древовидных полн-матрондоп.

1) Предложены новые простые доказательства оптимальности трех известных алгоритмов для ЗРР (в общей постановке, на полпматроиде, заданном точным списком ограничении, и на, древовидном полпматроиде).

1) Получено линейное описание МАП и доказано, что он является обобщенным полиматроидом.

(?) Определены многие комбинаторные характеристики МАИ (диаметр, критерий смежности вершин, /-вектор, комбинаторный тип).

7) Разработаны эффективные алгоритмы для линейной и сепарабелыюй оптимизации на МАП.

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

9) Установлено соответствие между экстремальными функциями (функциями, задающими экстремальные лучи) конуса Цп) и конуса матроидных ранговых функций Л/(п). Доказана вырожденность небулевых экстремальных функций конусов М(ч) и 1(п).

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

Дихотомический алгоритм решения ЗРР, разработанный в диссертации.

1жег быть применен при решении ряда практических задач (распределения

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

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

Предложенные в диссертации алгоритмы для решения ЗП'1> реализованы п

\ПР для автоматизации проектирования фильтров на ПАВ.

-|>-

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

Экономическое значение полученных результатов.

Экономическое значение результатов работы состоит главным образо использовании алгоритмов решения ЗПФ при создании САПР, лпллющ* коммерческим продуктом. Оценить экономическое значение других результ; диссертации в настоящее время не представляется возможным.

Основные положения диссертации, выносимые па защиту:

1. Новые свойства градиентных решений ЗРР.

2. Полиномиальный алгоритм для решения ЗРР.

•!. Линейное описание, полиматроидная и комбинаторная тракторизация М.

I. Эффективные алгоритмы для линейной и сепарабельноп оптимизации МАП.

Л. Полил я хпрлктеризацня матрондного и полумодулярного подконусоп кон субмодулярных функций.

Личный вклад соискателя.

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

Апробация основных результатов.

Основные результаты диссертации докладывались на школе-семинаре по дг ретнои оптимизации (Минск, 1 9!К! г.), на (ьп конференции математиков Белар; (Гродно. 19!)2 г.), на международной конференции 1КМ'04 (Ваймар. 191)1 г.). международном семинаре ' [НчпчЧе ОрМпшаСши" (Ваймар, 1991 г.), на мелч народной конференции 0рега(,юн5 11еяеагг1Г" (Берлин, 1994 г.), на коллокви; по комбинаторике (Гамбург. 1994 г.), на международной конференции по ком наторной оптимизации ЕССО VIII (Познань, 199") г.).

Онубллкопанность результатов.

Из совместно опубликованных раГют в диссертацию включены результаты, пученные лично автором. Отопим с результаты диссертации опубликованы в работах.

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

Диссертации состоит из введения, общей характеристик» работы, четырех гш. основных выводов и списка используемых источников из 121 наименования, [а содержит 98 страниц машинописного текста, в том числе 0 рпсункоп.

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

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

Во второй главе исследуется следующая задача

Р(г,ЛГ): ДХ)=Е№^шлх х 6 /'(г) п

/,■ : К -> К есть погнутая функция и /,(!)) = 0 для всех « С А' =

2.....»}. г : 2^ —» есть ранговая функция полимат1)опда /'(г) := {т £

' | :г(/) := ¡Г < >•(/) V/ С Л'}, т.е. г является нормализованной (г(0) — ¿6/

неубывающей и субмодуляршш (г(И I) Л) + г (Л Г) И) < г(/1) >( В) V Л.П С . Эту задачу часто называют задачей распределения ресурсов (3РI'). На цачу Р(у. А') ссылаемся как на задачу Р. Как показано в разделе 2.2. без потерн щностл можно допустить, что г 6 А', - неубывающие функции. Раздел 2.1 держит базовые факты из теории полиматроидов, субмодулнрпых (функций и пуклых многогранников. О разделе 2.2 дастся постановка ЗРР и отмечается, о несмотря на ее хорошую изученность для многих специальных полиматроидов. ществуют лишь единичные работы для общего случал, когда полимагронд задал специфической структурой, а своей ранговой функцией. Это можно объяснить м. что в этом случае задача проверки принадлежности to41.it нолнматропду

сводится к задаче минимизации субмодулярной функции. Лля последней зада* не известно эффективного комбинаторного алгоритма, хотя разработан, силы полиномиальный не комбинаторный алгоритм, основанный на методе эллипсоид» В главе '2 предполагается, что процедура для минимизации субмодулярнс функции задана. Допускается также, что функции / и г заданы не аналитическ а через процедуры, вычисляющие их значение в произвольной точке х £ R'v и i произвольном множестве / С /V, соответственно, за время 0(1).

Вводится величина V*'-'/^) = Кх + ~ J{x)i где е, есть г-ый единичны

орт, х £ Z-N, называемая правым (левым) (-градиентом функции / в точке х.

Рассматривается следующий алгоритм решения задачи Р. известный к; алгоритм координатного подъема. В дальнейшем называем его градиентным.

Градиентный Алгоритм (ГЛ)

.г1 := (0,0,...,0). Итерация t (t — 1, 2,..., .s) :

х'+' := х' + ет, где j(t) = argmax(V+/(.с') | j 6>},

Л" = {je,v|.r' + eie /'С')}. Stop (i = л): yV' = 0 .

Через ГА ЛI обозначим ГА со следующим условием остановки: ".V = 0 ил

?+<„/(*•)< о".

Точка х', построенная алгоритмом ГА. называется градиентным решение, задачи Р и обозначается через хГА.

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

Свойство 1 Пусть Р(г) есть целочисленный полиматроид. Алгоритм ГА/ГА1 строит глобальный максимум неубывающей/произвольной сепарабельной вогнуто функции на целых точках P{i').

Пусть г- : 2,v —> R+ есть ранговая функция полиматроида Р(г). Тогда функции . '2Ч такую, что ¡) = r(N) — r{N\I) для всех / С Лг, назовем двойственно

к г. а многогранник P(r#) = {х £ R'];' | .r(/) > г*(1) V/ С jV} двойственные пплнматроидом к /'(/•).

Рассматривается следующий алгоритм решения задачи /\ известный ка; алгоритм координатного спуска в направлении допустимой области. I дальнейшем называем его двойственным градиентным.

!l-

вонстненный Градиентный Алгоритм (ДГЛ) := ;•({«}) для всех t 6 N.

терация (' = 1,2.....-ч) :

:= .г' - ет, где >(<) = argmaxlVj/V) | j 6 /V'}, Л" = {; б Л' | .г' - с} 6 /'(г*)}. op(t= s) : Л/' = 0 .

Хорошо известно, что ДГА строит оптимум задачи Р.

Последовательность точек,, построенную алгоритмом ГА (ДГА) для задачи , назовем градиентным (двойственным градиентным) путём. Отмстим, что >адиентный путь, также как и двойственный градиентный путь, не является цнозначно определенным, так как индекс j(t) не определен однозначно на каждом are I алгоритмов ГА и ДГА. Поэтому при разном выборе индекса j{l) в алгоритме А (ДГА) могут быть получены разные оптимальные решения задачи Р. Чтобы збежать многозначности положим, что индекс j(t) на каждом шаг«; i алгоритма А (ДГЛ) определяется по следующему правилу

j{t) = L(R) arsmax{V;(-'/(i') \j € -V'},

оторое означает, что выбирается наименьший (наибольший) возможный индекс, •то правило назовем L (Л)-правилом, и далее, говоря об алгоритме ГА (ДГА), удем иметь в виду алгоритм ГА (ДГА), использующий L (Я)-правило.

Свойство 2 Алгоритм ГА с L-нравилом строит то же оптимальное решение, для адолп Р. что и алгоритм ДГА с R-прпвилом.

Так как число итераций алгоритма ГА (ДГА) может быть произвольно велико, о в общем случае он не является полиномиальным.

Троблема 1 Построить полиномиальную реализацию алгоритма ГА для задачи рас-1редсления ресурсов.

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

Свойство 3 Пусть jrA есть градиентное решение задачи Р. Пусть у 6 Р(г) П i j(.!/) = ¿argniax{V+/(y) | j £ А'}. Тогда ут + 1 < если у + е» 6 J'(r), n Ш ^ ¿jill- wa'ie-

Свойства 2 и S влекут

Свойство 4 Пусть ,пГЛ есть градиентное решение задачи Р. Пусть у Ç /'(»■*) f « Д.,/) = /? arg max{ VJ/(y) | j 6 /V}. Тогда уЯу) - 1 если у - ej(s) 6 P(r*

им > ■'•[(')/)•

Пусть i\í - многогранник в Е^ и Í Ç N. Тогда через M\¡ обозначим проек M на гиперплоскость x{N\I) = 0. Очевидно, что (/'(г))|/ есть полиматроид Р(г Hj.. где функция г|; : 2' —» R обозначает сужение г на множество /, т.е. r|/(,S') = для всех S С /. Двойственную функцию к г|/ обозначим через r|f.

Пусть X есть вектор в Через х\i обозначим.сужение вектора х на множе! /, т.е. у = .гI/ тогда и только тогда, когда у 6 R' и y¡ = x¡ для всех ¡6 /.

Теорема 1 Пустъ 0 С I С N. Пусть х' и х° есть градиентные решения задан P(i \l,I), соответственно. Тогда > x'¡ для всех i G I.

Следствие 1 При условиях теоремы I можно заменить в задаче Р поламатр нше ограничения x(S) < ''(•Í) для всех S С I неравенствалт X; < x®, i 6 /.

Пусть г : 2Л —> Е+ есть ранговая функция полиматроида. Для произволы непустого множества I С N определим функцию r¡ : 2' —» R+ следующим обра |''/(5) = r(S-U (Л*\/)) — r(N\I) для всех S Ç I. Известно, что f¡ - ранговая фуш полиматроида. Двойственную функцию к fj обозначим через ff.

Теорема 2 Пусть 0 С / Ç /V. Пусть х" и есть градиентные решения задач Р(г/.1). соответственно. Тогда х® < x"¡ для всех i I.

Следствие 2 При условиях теоремы. 2 можно за.иенить в задаче Р полиматр ные ограничения x[J) < r{J) для всех J таких, что N\I Ç J с N, неравенств Xi > X" для всех i 6 /.

• Пусть X 6 R'v есть произвольнал точка полиматроида Р[г). По определе положим sat(r.x) :— {г 6 N | х + Ac, £ P(r) V А € R+}. Множество sal(r,x) сос: из тех координат точки .с, которые нельзя увеличить, сохраняя принадлежи' X полн.матроиду /'(г). Отметим, что если функция г целочисленная и i S Z' .S«<(r,.r) = {i e -V| i + e;(! P(r)}.

В разделе 2.4 приводится следующий алгоритм для решения задачи Р.

отомический Алгоритм (ДА) О, II- >'({'}) для всех г £ N.

К'; + »! )/ 'J ■Злп i 6 /V, где [uj есть максимальное целое, которое ше либо равно «.

>ация < (t = 1,2,____fc) :

¿.1. Найти = i)iax{y|y < л',.у £ P(r)}. t..2. Найти = sat(r,

t.i. Если (x< = :') и {P\FIX' ф N\FIX'), то на шаг t.l. Иначе на шаг t.5.

t I /1 + 1 ._ _! i 1 „1+1 ._ „I

t.l. 1Л1) .- JJ((| + I. um ujU).

где j(t) = ¿arg max{ Vj"J{x')\j £ N\(P UF/.V1)), и на шаг /.(i. t.5. := := /},„, где Л0 = «arginax{V;/(r«)|; € P\FIX'}.

'•«••^Î-U^! + »ÎÎ,Î)/2J. ■

/.Г. Если /j+j = uj+|, то FIA"+1 := F/A" U {j(<)}. ¿.S. < := t + 1.

(i = t): »' = /' (F/.V = .V). .глл := /'.

Усматривается выполнение алгоритма ДА на конкретном примере. Отнеся, что х' = zl (/' = Л") тогда и только тогда, когда .г' Ç Р(г) (.г1 6 Р{''*))-дующая теорема показывает, что алгоритм ДА строит оптимальное решение чи Р.

нема 3 Точка построенная алгоритмом MA, есть градиентное решение.

■m Р.

[оказывается, что число итераций «алгоритма ДА равно 0(ri log//ср), а общая даость - 0(»(Л' + п) log /Д-р), где К есть сложность нахождения точки ■южества /' на каждой итерации /. алгоритма ДА, //,,, = »'({'})/"•

взывается полиномиальная ограниченность величины Л*. Тем самым решена >лема 1 - построения полиномиальной реализации алгоритма ГА для задачи :ределения ресурсов.

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

> разделе 2.) выполнение алгоритма ДА рассмотрено для однородных. >щенных симметрических, цепочных и древовидных полиматроидов. Во всех случаях показано, что величина /\ не превосходит 0(п). В итоге получены

алгоритм сложности 0(n log п log //ср) для задачи Р на однородном полпматро] алгоритмы сложности 0(нг log Яср) для задачи Р на обобщенном симметриче( цепочном и древовидном полиматропде. Дается сравнительный анализ пол} ных алгоритмов и наилучших из известных.

Новые доказательства оптимальности (т.е. факта построения оптималь решения) трех известных алгоритмов, разработанных для ЗРР в общем ел} на древовидном полиматроиде и на полиматроиде, заданном точным списком < ничений. приводятся в разделе 2.6. Они основаны на свойствах градиентных р нии. полученных в разделе "2.3. Приводится новая рекурсивная формулир алгоритма ДА, разработанного в разделе 2.1. С её помощью получено б простое доказательство его оптимальности.

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

Проблема 2 Паи,та линейное, описание МАП.

Проблема 3 Построить эффеюпивные алгоритмы решения задачи проектпр ния фильтров ни. 1IAD с различными целевыми функциями, учитывающие спецт МАП.

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

Множество + l.....»¡} обозначим через [к. и], а вместо :c([fc,j]) будем записьп

•r[k._/]. В разделе .'¡.1 приводится следующая теорема, в которой дпно реше проблемы 2.

Теорема 4 Многогранник Р задается следующей системой линсйны.х неравенст

-1 < x[k,j) < 1 VfceiV Vj е [fc,n] := {k.k+ 1,...,»}.

Следствие 3 Вершинами многогранника Р являются только точки множеа D\0. где б = (0.0.....0).

Следствие 4 Многогранник Р имеет 2n+1 — 2 вершин.

Грани максимальной размерности называются фасетами многогранника. Следствие 5 Число фасет многогранника Р равно п(п ■+■ 1).

-1:1-

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

Георема 5 МАП есть обобщенный. полиматроид.

На Пазе теорем '1 и 5 в разделе :).2 устанавливаются многие комбинаторные войства и характеристики МАП.

Обозначим через Д-^С]) множество точек из /), у которых первая ненулевая оордината равна -1(1).

Георема 6 Точка х является вершиной многогранника заданного системой

mi.rv.uhrx неравенств

-1 < ■'•[[, л < о

гогда и только тогда, когда .г 6 .

Рассмотрим многогранник 1\ = /'_| -|-С|.

/Ледстпие 6 Многогранник /'| задастся условиями 0 < ./:[!,_/| < I V/ Г; /V и имеет качестве вершин точки множества 1)\ и только них.

Следствие 7

юсН(Р) = (ие|7(Я_|)и исг((/7|))\Г|, иег/(;'_,) Л «ег«(/',) = ("),

)е сс; /.(/') есть множество вершин многогранника V.

Два многогранника называются комбинаторно-эквивалентными, если изоморф-ы их решетки граней. Если многогранники А и В комбинаторно-эквивалентны, о записываем /1 ~ В. Отметим, что Р_ 1 ~ .

'еорема 7 /', ~ С", где С" есть п-мерпый гиперкуб.

Следствие 8 Диаметр многогранника Г\ равен п.

Следствие 7 и теорема 7 влекут следующую теорему - критерий смежности •ршин МАП.

еорема 8 Верхаины х' и х" многогранника Р смежны, тогда и только тогда, когда ыполнястся одно из следующих условий :

(!) (¡¡)

| х' — х" | == е! или | ,с' - .с" |= е,,. где |,| = (|,,|, |,2|,.... |,„|). 3} £ [1. л — 1] : .с' — .г" = е,- - еу+1 или х.' — х" — —е.; +

-l-t-

Следствие 9 Диаметр многогранника I' равен и -f 1.

Через f(M) обозначим структурный вектор многогранника Л/, компонент которого /,(Л/) (i £ [0. н — 1]) есть число ¡-мерных граней многогранника M.

Теорема 9

= /.(<?") + /,-,(Я""') vie М-il,

где Р"~[ - МАЛ размерности п — 1, 67" - гиперкуб размерности п. Следствие 10

к=0 4 ' где ( " ) - число сочетаний из п по т.

С)

С использованием комбинаторных свойств МАП, полученных в разделах 3.1 3.2. в разделах 3.3 и 3.4 построены алгоритмы сложности 0{п) и O(nlogii) дл нахождения максимума линейной и вогнутой сепарабельной функции на МАГ соответственно. Эти алгоритмы максимально учитывают свойства МАП. и выполнение рассмотрено на конкретных примерах. Тем самым решена проблема для случаев, когда целевая функция в задаче проектирования фильтров на ПАВ линейная или сепарабельная.

Если С есть множество всех линейных комбинаций функций /¡(i £ 1 с неотрицательными коэффициентами, то С назовем конусом, порожденны; функциями fj (/ £ I). Конус, порожденный ранговыми функциями (заданными на 2Л полиматроидов (далее, просто ранговыми функциями), обычно обозначается чере .-II н). Четвертая глава посвящена исследованию конуса Л(п). Многие автор] называют его конусом субмодулярных функций. Рассматривается следующа проблема.

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

По аналогии с ранговыми функциями полиматроидов, функции г. которы заданы на подрешетке L решетки 2,v и являются нормализованными (r(0(£)) = f где 0(L) = min{/|/ £ L}). неубывающими и субмодулярнымп на ней. также назове: ранговыми.

-1Г>-

Булевые ранговые (функции гз (.1 С Л') определяются по следующему правилу

I,

,,, / I, .-ели 1С\.1 ф 0, = { I), иначе.

Множества Пулевых и матрондных ранговых функций порождают булепый //(н) матроиднып Л/(н) конуса, соответственно. Очевидно, что //(?г) С М(п) С /!(»)• е. //(и) и ЛЦп) являются подконусами конуса /1(н). С разделе 1.1 вводится ещё цин подконус конуса А(п) следующим образом.

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

шбольшей нижней А и наименьшей верхней V граней.

Пару элементов а и Ь решетки Ь назовем -интернамш и обозначим и|/>. если ^ Ь. Интервал «[!) назовем простым, если !> покрывает «, т.е. не существует темента с 6 Ь такого, что а < с ^ Ь. Интервалы н Л й|и и 1>\и V Ь назовем ;рснсктивны.ми. Транзитивное замыкание отношения перспективности задает гношенпе тождества на множестве всех простых интервалов решетки Ь. Назовем ■о отношением про сктпвпостл. Решетку Д назовем сия.тноЛ, если все её простые тгервалы принадлежат к одному классу проективности.

{1,2,3.4}

{1.2}

Рис. 1

Например, решеткана рис. 1а связна, а решетка на рпс. 1 б не является связной, ж как существуют два класса проективности: 0|{2}, {1 }|{ 1,2} и 0|{ 1}, {2}|{ 1,2}.

Решетка £ называется полу модулярной, если существование простых интерва->в а Л й|а и а Л 4|Л влечет существование проггЬ1Х интервалов Ь\а V 1> и а|н V Ь.

Пусть г есть ранговая функция на 2,у. Рассмотрим отображение '. 2Л — 1.г. ц>еде ленное по правилу ,(/) = так{./ е 2,у | >■(.]) = !'(/)}. Через г обозначим ■жение функции г на решетку £г. Назовем функцию г полумодулзрнпи . если Д, =

-l(>-

V?r(2,v) есть полумодулярная решетка и г = Л. где h - функция высоты решеть Назовем функцию г свя:топ, если L, есть связная решетка.

Через L(n) обозначим конус, порожденный полумодулярными pauroi функциями, заданными на 2'v. Назовем его полумодулярним конусом.

Пусть С ееть конус, функция / называется экстремальной функцией ki С, если она принадлежит минимальному множеству функций, порождающи. Через EFn{M) и EFn(L) обозначим множества экстремальных функций koi М(п) и £("), соответственно.

В раздело -4.'2 доказываются следующие теоремы, в которых дана характе ция множеств EF„(M) и EFn(L).

Теорема 10 г 6 EFt¡(.\!) тогда, и только тогда., когда г есть ранговая фуг связного матро ltda.

Теорема 11 г 6 EFn(L) тогда и только тогда, когда г есть связная полумодул^ функция.

В этом же разделе доказывается следующий результат. Теорема 12

(i) М{п) С Цп) С А{п). если п > 3, (ii) М(п) = L(n) = Л(».)> если п = 2,3.

Тем самым показано, что конус. L(n) является наиболее широким среди полностью характеризованных до настоящего времени подконусов конуса /l(i есть найдено решение проблемы 4.

В разделе 4.3 исследуется связь между экстремальными функциями koi L(n) и М(п). Показано, что любая экстремальная функция конуса ¿(tí) может получена из некоторой экстремальной функции конуса М(к) (к < п) с пом< операции лифтинга. Суть операции лифтинга состоит в том, что рассматрпв пространство большей размерности, а исходная функция г доопределяете* чтобы решетка r-замкнутых множеств осталась (структурно) той же.

Многогранник размерности п назывется простым, если каждая его вер принадлежит ровно п фасетам, и вырожденным, в противном случае. Ранг функцию г : 2'v -+ Е+ назовем вырожденной (простой), если полиматроид I вырожденный (простой). В разделе 4.4 доказывается вырожденность небу! экстремальных функций конусов М{п) и L(n).

-IT-

ВЫВОДЫ

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

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

Предложены новые простые доказательства оптимальности трех известных алгоритмов для ЗРР (в общей постановке, на полиматроиде, заданном точным списком ограничений, и на древовидном полиматроиде).

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

Определены многие комбинаторные характеристики МАП (диаметр, критерий смежности вершин, /-вектор, комбинаторный тип).

Разработаны эффективные алгоритмы для линейной и сепарабельной оптимизации на МАП.

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

Установлено соответствие между экстремальными функциями (функциями, задающими экстремальные лучи) конуса i,(n) и конуса матропдных ранговых функций М(п). Доказана вырожденность небулевых экстремальных функций конусов jl/(n) и Цп).

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

1. Запорожец Л. А. Применение целочисленного линейного програм] рованил при проектировании фильтров на ПАВ// Вестник Белорусск университета. Серия 1: Физ. Мат. Мех. - 1 (J!)3. -N 1. - С. 47-Г>().

2. Запорожец А. А.. Ковалев М. М. Полиномиальный алгоритм максимиза1 вогнутой сепараоельной функции на целых точках полиматропда // Т докл. бой конференции математиков Беларуси. Гродно, 21) сентября октября 19!>2г,- Часть 4. - Гродно. 1992.- С.П.

3. Запорожец А. А.. Ковалев М. М. Многогранник альтернирующих после вательностен // Доклады АН Беларуси.- 1!Ш.-Т.3й, N 9-10.--С. 786-781).

4. (iirlicti Е.. Sihneidrrpit С!., Zaporozliets A. Non-simple Polymatroids and (ли respo ins; Subiuoiluliir Functions/ Preprint Matli 20/SJ.j Otto-vou-CUiericke-Uuiversilat Magdeburg. 19!):!. - 28p.

5. .Sclineidercit (!.. Zaporoshetc A. Non-simple Polymatroids ami Corresponding S modular Functions// Operations Research '!)•!. Extended Abstracts of the IS. Sj piis'mni <m Operations Research in Cologne. - Heidelberg: Pliysir.a-Vcrlag, 1991. -405-457. • '

(>. Kovalev M.. Zaporozliets A. The Fast (¡reedy Algorithm for Resource Allocation I'r lenis with Polyinatroidal Constraints/ Preprint Nil) Otto-von-Ciuericke-Universita Magdeburg, 11)91. - Kip.

7. Ciirlich E.. Zaporozliets A. The Cone of Rank Functions: Properties of .Subcou Preprint .N17 Otto-von-Giiericke-Universitat. - N.lagdeburg, 199-1. - Kip.

S. Oirlich E.. Kovalev M.. Zaporozliets A. Subcoues of submpdular functions (subclai of Monge matrices)/ Preprint N29 Otto-von-Giiericke-Universitat. - Magdeburg. l'J - 28p.

!J. Kovalev M.. Zaporozliets A. Polynomial Algorithm for Maximization of a Separa Concave Function over Base Polyhedron of a Siibmodular System// Abstracts Workshop on Discrete Optimization. Weimar. May 30-Jiiue 3.1994. - Weimar.19!

Ill

(Jirlicli K., llüilitij; M., Si hnciilcreit (!., 7,apoi o/.licts A. Tin' Cone of .Sciiiimoiliil.it' Haul; Functions // Operations Hcsrnnh ProrceiliiiRS 1991, Selected Papers ol tlie-liitcni.itioii.nl Conference on Operations lieseaicli, Merlin, AiirusI .'ID - September 1!)!M. - Oeilin, Heidelberg: .Springer-Vorlag, l!)!).ri. - P. 98-11)2.

tlirlicli Ii., Kovalev. M., Zaporozhets A. A Polynomial Algorithm lor liesoiirio Allocation I'rohleins witli I'olyiiiatroiil Constraints/ Preprint N2 Otto-voii-( iueiii ke-t .Universität. - Magdeburg, 1995. - 21|i.

Ciirlicli E.. Kovalev M., Z.'iporozliets A. About Pioperties of Optimal Solutions of Resource Allocation Problems/ Prepiiiit, N.'i OUo-von-(biericke-l;niversit;it. Magdeburg, I99.r). - Kip.

-21] -PE3IOME Запорожец Александр Александрович

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

субмодулярных функций

Ключевые слова: полиматроиды, субмодулярные функции,- градиент] алгоритмы, задача распределения ресурсов, выпуклые многогранники, выпук. конуса.

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

Найдено линейное описание многогранника альтернирующих последоватс постен (МАП) -- допустимой области задачи проектирования фильтров (ЗПФ] поверхностных акустических волнах. Определены многие комбинаторные ха] терпстикп MAII (диаметр, критерий смежности вершин, /-вектор', комбинатор! тип! и доказана его принадлежность к классу обобщенных полиматрондов. этой игезе разработаны эффективные алгоритмы для решения ЗПФ с линейно сепарабельной целевой функцией.

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

РЭЗЮМЭ

Занарожац Аляксандр Аллксаидратч

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

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

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

Атрымана лпгейнае ашеанне мнагаграшнка альтэршрумчых паеллдо\-насцей \П) - дапушчальнаи вобласщ задачы праектавання ([мльтрау (3ПФ) на паверх-ых акустычных хвалях. Вызначана шмат к.чмбшаторных характлрыстык МАП яметар. крытэрый сумежнасц\ вяршын. /-вектар, камб'шаторны тып) 1 даказана прыналежнасць да класу абагульненных пал1мат]хпдау. На гэтан падставе працаваны эфекты\"ныя алгарытмы рашэння ЗПФ з лшейнай н сепарабельнай авай функцыяй.

Уведзен конус палумадз'лярных рангавых функцьш1 атрымана характарызацыя экстрэмальных праменя\'. Паказана, што сн з'яС'ляецца найбольш шыромм од уах цалкам хараюгарызаваных да гэтага часу падканусоу конуса мад\'лярных функцый.

SUMMARY

Zaporozhets Alexander Alexandrowitch

Polymatroidnl approach in investigation of resource allocation problem, alternating sequences polytope and cone of submodular functions

Key words: polymatroids, submodular functions, greedy algorithms, resource allot tion problems, convex poly topes, convex cones.

We have constructed a polynomial algorithm for problem of convex separable fundi maximization on integer polymatroid defined by raiik functions (resource allorati problem).

We have found the linear description of ?lternating sequences polytope (ASP) feasible region of problem of acoustic waves filters design (PAWFD). Many combinatoi characteristics of ASP (diameter, criterion of vertices adjacency, /-vector, combinatoi type) are determined. It is also proved that ASP belongs to the class of genernli: polymatroids. Oil this base there were developed efficient algorithms for solving PAW with linear and separable cost function.

The rone of semimodular rank functions was introduced and the characterization of extremal rays was given. It is shown that this cone contains all up to now complet characterized subcones of the submodular functions cone.

c-