Наследственные структуры и оптимизационные задачи в булевых и геометрических решётках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

ВЫПЛОВ Михаил Юрьевич

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

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

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

005567924

Екатеринбург — 2015

005567924

Работа выполнена в Институте математики и информационных технологий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского».

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

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

Титов Сергей Сергеевич, доктор физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уральская государственная архитектурно-художественная академия», г. Екатеринбург, заведующий кафедрой прикладной математики и технической графики,

Шенмайер Владимир Владимирович, кандидат физико-математических наук, Федеральное государственное бюджетное учреждение науки «Институт математики им. C.JT. Соболева СО РАН», г. Новосибирск, старший научный сотрудник лаборатории дискретной оптимизации в исследовании операций.

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина».

Защита состоится «18» марта 2015 года в 14.00 часов на заседании диссертационного совета Д 004.006.04 при Учреждении Российской академии наук «Институт математики и механики им. H.H. Красовского УрО РАН» по адресу: 620990, Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики им. H.H. Красовского УрО РАН и на сайте ИММ УрО РАН: http://wwwrus.imm.uran.ru/Cl6/Diss/default.aspx.

Автореферат разослан « 13 » февраля 2015 года.

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

В.Д. Скарин

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

Актуальность темы. Наследственные структуры — объекты, наделённые свойствами наследственности — широко распространены в дискретной математике. К ним относятся, в первую очередь, наследственные системы и матроиды, а также порядковые идеалы решёток и их частные случаи — L-матроиды. Они объединяют в себе черты многих известных комбинаторных объектов и являются адекватными моделями множеств допустимых решений большого числа дискретных оптимизационных задач. Рассматриваемые в диссертации оптимизационные задачи являются, как правило, NP-трудными, поэтому актуальным направлением исследований является разработка и анализ алгоритмов приближённого решения этих задач и получение гарантированных оценок их точности. Исследования указанных задач активно ведутся в России и за рубежом.

Пусть V — непустое конечное множество, А С 2У — непустое семейство его подмножеств, удовлетворяющих аксиоме наследственности:

(А1) (А<еЛ,А' СА)=>А' еА.

Множества семейства А называются независимыми, а само семейство А в литературе обычно называют системой независимости или наследственным семейством;г.

Наследственная система Я на множестве V определяется2 как разбиение семейства 2V всех подмножеств V на два непересекающихся семейства А и V, где Л — система независимости, а V = 2У\Л. Множества семейства V называются зависимыми . Очевидно, что V обладает свойством наследственности "вверх": (D € Т), D1 D D) => D' £ V.

Через В обозначается семейство всех баз, т. е. максимальных по включению независимых множеств, через С — семейство циклов, т. е. минимальных по включению зависимых множеств.

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

max{/(X) : X € В} или min{/(X) : X € В}, (1)

таx{f(X):XeC} или min{f(X):XeC}, (2)

где / : 2V R+ — монотонная неотрицательная функция множеств.

iQrotschel М., LoviLsz L. Combinatorial optimization. In: Handbook of Combinatorics. Graham R.O., Grotschel M., LovjSsz L., eds. Amsterdam: Elsevier Science B.V. 1995. V. 2. P. 1341-1598.

JIl'ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132, № 1-3. P. 137-148.

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

Наследственные системы и их частные случаи — матроиды — естественным образом возникают в различных областях математики, таких как линейная алгебра, теория графов, теория трансверсалей и других разделах комбинаторного анализа3.

Наследственная система Н = (У,Л) называется матроидом на V, если выполняется аксиома пополнения:

(А2) (АЛ'еЛ|Л'|НЛ| + 1)=>ЗаеЛ'\у1(Ли{а}еД). Хорошо известно также эквивалентное определение матроида в терминах замыкания4.

Отображение р : 2У —^ 2У называется оператором замыкания, если для всех X, У С V выполняются условия: (</з1) X С. X (направленность), (<р2) X СУ => X СУ (монотонность), (<рЗ) X = X (идемпотентность), где X = <р{Х). Множество X С V называется замкнутым, если X = X.

Пусть V — непустое конечное множество, а (р — оператор замыкания. Пара М = (V, ф) называется матроидом (или комбинаторной предгео-метрией) на V, если для всех X С V и для любых и,у £ V выполняется аксиома замены:

{<рА) {и$Х, и€ X и {и}) V £ X и {и}.

Можно дать определение и для случая бесконечного V, при этом требуется также выполнение аксиомы конечного базиса-. (<р5) УХСУВВСХ (|£| < оо и В = X).

Матроид называется обыкновенным (или комбинаторной геометрией), если 0 = 0 и {и} = {и} для любого элемента V £ V.

3 Леш ¡он М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб: Лань. 2010.

4Айгнер М. Комбинаторная теория. М.: Мир. 1982.

Матроиду М = (V, ip) сопоставим решётку L(V) замкнутых подмножеств V, упорядоченных по включению. Операции определяются следующим образом: X AY — X (lY, XVY = X UY для любых X,Y€ L(V).

Высотой h(x) элемента х € L, где L — решётка конечной длины, называется точная верхняя грань длин цепей решётки между нулём и х. Говорят, что элемент решётки у покрывает элемент х (обозначается х < -у), если х < у и из соотношения х < z < у следует у = z. Атомами решётки называются элементы, покрывающие 0. Решётка называется атомарной, если каждый её элемент является точной верхней гранью атомов. Решётка называется полумодулярной, если для любых её элементов х,у выполняется соотношение х А у <■ х => у <• х V у-. Решётка называется геометрической (матроидной), если она является атомарной, полумодулярной и не содержит бесконечных цепей.

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

Теорема Биркгофа-Уитни. 1) Решётка L{V) замкнутых множеств любого матроида M=(V,<p) — геометрическая.

2) И обратно, для любой геометрической решётки L с непустым множеством атомов V существует обыкновенный матроид М = (V(р), решётка замкнутых множеств которого изоморфна L.

Подмножество I решётки L называется порядковым идеалом, если для любых х,у € L выполняется условие (Л) {xel,y<x)=>yel.

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

Дунстан, Инглтон и Уэлш5 ввели понятие суперматроида как обобщение понятия матроида в частично упорядоченном множестве с нулём. Для конечной решётки L это определение приобретает следующий вид. Пусть I— порядковый идеал в L. Он называется суперматроидом или L-матроидом, если для любого х в L все максимальные элементы из IП [0, х] имеют одинаковую высоту h.

'Dunstan F., Ingleton A., Welsh D. Supermatroids // Combinatorics, Southend-on Sea. 1972. P. 338-353

Функция / : L R+ называется супермодулярной на решётке L, если для любых х,у 6 L выполняется неравенство

f(x V у) + f(x Л у) > Дх) + f{y). В случае равенства функция / называется модулярной на решётке L.

Рассмотрим оптимизационные задачи

max{w(x) : х — максимальный элемент (база) I}, (3)

min{/(x) : х — максимальный элемент (база) I}, (4)

в конечной геометрической решётке L, где I — порядковый идеал, w : L —> R+ — модулярная функция, w(0) = 0, / : L —»• R+ — неубывающая супермодулярная функция, /(0) = 0.

Одним из методов, традиционно используемых для приближённого решения задач типа (3) и (4), является жадный алгоритм.

Алгоритм Gr (жадный алгоритм). Шаг 0. хо 0, перейти на шаг 1. Шаг i (г ^ 1). Выбрать такой Xi ■> X{-i, что

w{xi) = max w{x) (для задачи (3)) или min f{x) (для задачи (4)). xel, xel,

X->Xi—i Х- >X,_ 1

Перейти на шаг г + 1.

Если такого Xi • > Xi-\ нет, то sGr <- Xi-i.

Конец.

Одним из центральных результатов теории матроидов является теорема Радо-Эдмондса6'7, которая утверждает, что жадный алгоритм гарантированно находит оптимальное решение задачи (3) на системе независимости А в конечной булевой решётке 2V для любой аддитивной целевой функции в том и только том случае, если А является матроидом.

Несложно показать, что эта теорема верна для любой модулярной функции в булевой решётке 2V.

Известны обобщения теоремы Радо-Эдмондса, как правило сопровождающиеся расширением допустимой области. В 1973 г. Н.И. Глебов8 независимо, не используя аппарат теории матроидов, доказал более общий, чем теорема Радо-Эдмондса, результат для задачи максимизации вогнутой сепарабельной функции на системе целочисленных векторов, обладающей свойством наследственности. Данное направление (расширение

®Rado R. Note on independence functions // Proc. London. Math. Soc. 1957. V. 7, JY« 3. P. 300-320.

7Edmonds J. Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and their Applications. Proc. Calgary Int. Conf. June 1969. Guy R.K., Hanani H., Sauer N., Schonheim J., eds. New York: Gordon and Breach. 1970. P. 69-82.

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

области действия условий оптимальности жадного алгоритма) получило дальнейшее развитие в работах Н.И. Глебова и В.В. Шенмайера9,10.

Пусть А — система независимости на множестве V, с(А) — кривизна системы независимости, определяемая как

, А\ ■

с[А) = nun —Т-Г7Г, хсur{X)

где lr(X) и иг(Х) — минимальная и максимальная мощности баз множества X, соответственно. Кривизна с{А) характеризует близость системы независимости А к матроиду. Очевидно, что с(А) € (0,1] для любой системы независимости, причем с(Л) = 1, если и только если А — матроид.

В работах Дженкинса11, Корте и Хаусмана12'13 получена следующая гарантированная оценка точности жадного алгоритма для задачи максимизации аддитивной функции на произвольной системе независимости:

ш(5Сг) > c(.AMs0), (5)

где so — оптимальное решение задачи, sGr — решение, найденное жадным алгоритмом.

Задача (4) минимизации супермодулярной функции на L-матроиде является обобщением задачи минимизации супермодулярной функции на базах матроида, к которой, например, сводятся известная задача о р-медиане и задача аппроксимации графа.

Задачи оптимизации супермодулярных функций возникают в различных областях дискретной математики и изучались в течение ряда лет многими авторами. Так, задача минимизации супермодулярной функции на булевой решётке рассматривалась В.П. Черениным14. В.Р. Хачатуро-вым вместе с соавторами предложено большое количество теоретических результатов и методов решения задач оптимизации супермодулярных функций на решётках различных типов, что позволяет говорить об

»Глебов Н.И., Шенмайер В.В. О применимости алгоритма покоординатного подъема к задачам целочисленного'программирования // Дискрет, анализ и иселед. операнд». Сер. 1. 2000. Т. 7, № 4. С 38—47.

10Шенмайер В.В. Максимизация линейной целевой функции с помощью жадного алгоритма // Дискрет, анализ и исслед. операций. Сер. 1. 1999. Т. б, if« 4. С. 104-120.

uJenkyns Th.A. The efficacy of the "greedy" algorithm // Proc. 7th Southeastern Conf. on Combine tories, Graph Theory and Computing. Hoffman F., Lesniak L., Mullin R., Reid K.B., Stanton R., eds. Winnipeg: Utilitas Math. 1976. P. 341-450.

"Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. V. 24, № 3. P. 261-276.

"Korte В., Hausmann D. An analysis of the greedy heuristic for independence systems // Annals ot

Discrete Math. 1978. V. 5. P. 65-74.

"Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов // Научно-методические материалы экономико-математического семинара Лаборатории экономико-математических методов АН СССР. М. 1962. Вып. 2.

открытии нового направления в математическом программировании — супермодулярного программирования15.

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

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

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты диссертации могут быть использованы в научных исследованиях, а также в учебном процессе. Кроме того, рассмотренные в главе 3 алгоритмы могут быть применены для приближённого решения практических задач достаточно большой размерности.

Апробация работы. Основные результаты диссертации докладывались на 40-й Всероссийской молодёжной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2009), на IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2009), на X Международном семинаре «Дискретная математика и её приложения» (Москва, 2010), на XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011), на Всероссийской научно-практической конференции «Статистика. Моделирование. Оптимизация - 2011» (Челябинск, 2011), на Международной конференции «Дискретная оптимизация и исследование операций (DOOR-2013)» (Новосибирск, 2013), на Международной школе-конференции «Математические проблемы информатики» (Омск, 2013), а также на научных семинарах в Институте математики им. C.JI. Соболева СО РАН и его Омском филиале, в Институте математики и механики им. H.H. Красовского УрО РАН.

Публикации. По теме диссертации опубликовано 10 научных работ, из них 3 статьи в рецензируемых журналах из списка ВАК. Конфликта интересов с соавторами нет, в совместных работах соискателю принадлежат доказательства результатов, включенных в диссертацию.

Структура и объём работы. Диссертация состоит из введения,

15Хачатуров В. Р., Хачатуров Роман В., Хачазуров Рубен В. Оптимизация супермодулярных функций (супермодулярное программирование) // Журнал вычислительной математики и математической физики. 2012. Т. 52, № 6. С. 999-1000.

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

Содержание работы

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

В главе 1 исследуются решётки замкнутых множеств наследственных систем.

Замыкание может быть определено и для наследственных систем, не являющихся матроидами. Как и в случае матроидов, замкнутыми множествами наследственной системы Н на множестве V называются такие подмножества X СУ, что X = X. Однако, в отличие от матроидов, в наследственных системах аксиома идемпотентности (у?3) X = X может не выполняться, т. е. замыкание X не обязательно является замкнутым множеством. Замкнутые множества наследственной системы образуют решётку, в которой X ЛУ = X П У, а X V У — это минимальное по включению замкнутое множество, содержащее X и У.

Основным результатом главы 1 является аналог теоремы Биркгофа-Уитни для наследственных систем. Главная трудность состоит в том, что решётки замкнутых множеств наследственных систем могут не быть атомарными или полумодулярными, и прямое сопоставление атомов решёток элементам систем уже не работает. Следовательно, необходимо предложить и обосновать принципиально иной способ построения по заданной решётке Ь наследственной системы с изоморфной ей решёткой.

При анализе свойств наследственных систем будет удобно оперировать их наглядным представлением в виде гиперграфов. Пусть V — непустое множество, £ С 2У— семейство его подмножеств, причём 0 $ £. Пара О = (V, £) называется гиперграфом, элементы множества V называются вершинами гиперграфа, а элементы семейства £ — рёбрами гиперграфа. Ребро гиперграфа мощности п называется п-ребром.

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

Будем называть замкнутыми множествами клаттера замкнутые множества соответствующей ему наследственной системы.

В разделе 1.2 рассматриваются конечные наследственные системы. Предложен алгоритм А1, который для заданной конечной решётки Ь, \Ь\ > 1, строит гиперграф С? = (V, £), решётка замкнутых множеств которого изоморфна Ь.

Алгоритм А1.

1. Условимся обозначать вершины С? парами индексов вида (и, к), где и е Ь и к е {1,2,3}. Положим V = где ~ подмножества

вершин, определённые следующим образом:

2. Положим £ — £\ и 62 и £3, где

£\ — множество всех 2-рёбер вида {(и, 1), (г£,2)} и {(и, 1), (и, 3)}, и — элементы решётки, не являющиеся нулём или атомами;

£2 — множество всех 3-рёбер вида {(и', 1), (и, 2), (и, 3)}, и и и' — пары элементов решётки, такие, что и' <-и, и' ф 0;

£з — множество всех 3-рёбер вида {(их, 1), (иг, 1), {и\Уи2,1)}, и и2 — пары несравнимых элементов решётки.

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

Теорема 1.2. Для любой непустой конечной решётки Ь существует такой клаттер = (V, £), что решётка замкнутых множеств клаттера (3 изоморфна Ь.

Таким образом, любая конечная решётка изоморфна решётке замкнутых множеств некоторой конечной наследственной системы.

В разделе 1.3 рассматриваются решётки замкнутых множеств бесконечных наследственных систем. На основе алгоритма А1 предложен усовершенствованный алгоритм А2, строящий для заданной бесконечной решётки Ь, не содержащей бесконечных цепей, клаттер С = (V, £), решётка замкнутых множеств которого изоморфна Ь.

Имеет место следующий аналог теоремы Биркгофа-Уитни.

Теорема 1.3.1) Решётка замкнутых множеств любой наследственной системы не содержит бесконечных цепей.

2) И обратно, для любой непустой решётки Ь, не содержащей бесконечных цепей, существует наследственная система, решётка замкнутых множеств которой изоморфна Ь.

если и = 0,

если и — атом решётки,

Конец.

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

Возникает естественный вопрос: если отказ от аксиомы (Л2), представляющей собой вариант свойства замены Штейница, приводит к переходу от определения матроида к определению наследственной системы в терминах независимых множеств, то не можем ли мы аналогично определить наследственную систему в терминах замыкания, отказавшись от аксиомы замены (</з4)?

Как показано в данной главе, сходную с аксиомой (А2) роль играет не аксиома замены (<^4), а аксиома идемпотентности (у>3): свойство (у?3) нарушается для любой наследственной системы, отличной от матроида. Это обстоятельство вынуждает нас перейти к рассмотрению операторов слабого замыкания, для которых требуется только выполнение условий и {<р2). Однако, чтобы получить определение наследственной системы в терминах замыкания, мы не можем просто отбросить аксиому идемпотентности (</?3). Это привело бы к определению более широкого класса гиперграфов, нежели клаттеры, взаимно однозначно соответствующие наследственным системам, как показывает следующая теорема, доказанная в разделе 2.2.

Теорема 2.2. 1) Пусть <р : 2У -> 2У — оператор слабого замыкания, удовлетворяющий аксиоме (<р4). Тогда гиперграф С = (У, £), определенный по правилу _

£ = {ЕСУ :иеЕ\{и} Уи€Е

и такая, чтоу£Е\{у,и)}\/ги£Е\{у}}, (6)

обладает следующим свойством: для любого Е 6 £

Е Ф е £ : ^ С Е}, (7)

причем имеет место равенство

X =Хи{и £ £ такое, что V £ Е и X и {и} 5 Е}. (8)

2) И наоборот, если С = (V, £) — гиперграф, обладающий свойством (7), то отображение X X множества 2У в себя, определенное по правилу (8), обладает свойствами [<р1), (<^2) и (<^4), причем имеет место равенство (6).

Данное соответствие является обобщением соответствия между мат-роидами и операторами замыкания, удовлетворяющими аксиоме замены.

В разделе 2.3 рассматривается эквивалентное определение наследственной системы в терминах замыкания, для получения которого аксиому идемпотентности (<рЗ) нужно заменить более слабым требованием: для любых и,«£Уи любого ХсУ

(<¿3') {и е х\х, у аи{ц}\(1и {и})) ЗгибХи £1и{и}\ {и;}).

Пара Н = (V, <р) является наследственной системой на V, если она удовлетворяет аксиомам (<р1), (<р2), (<рЗ') и (<р4).

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

Теорема 2.4. 1) Оператор слабого замыкания, удовлетворяющий (<рЗ') и (<р4), может быть определён в терминах циклов следующим образом:

1 = 1и{ие^:3 С еС такой, что V € С и Хи {«}ЭС}.

2) Обратно, семейство циклов наследственной системы Н = (V, ф), где ¡р : 2У 2У — оператор слабого замыкания, удовлетворяющий аксиомам (</?3') и (<^4), можно определить следующим образом: С={ССУ : цеС\{ц} Vиес и Зг> е С такой, что V ^ С\{и, ги} Уи> е С \ {г;}}.

В главе 3 рассматриваются задачи оптимизации модулярных и супермодулярных функций на порядковых идеалах и ¿-матроидах в конечных геометрических решётках.

В геометрической решётке, учитывая ее атомарность, можно определить аналог матроида, напрямую обобщив аксиому пополнения (А2) для независимых множеств. Обозначим А1(Ь) — {а Е Ь : а • > 0}, АЬ(х) = {а е АЬ(Ь) : а < х} для любого х € Ь.

Лемма 3.1. Пусть I — порядковый идеал в конечной геометрической решётке Ь. Если для него выполняется условие

(12) (х, у € /, А(®) > Л(у)) За € Аг(х) \ АЦу) (у V а 6 I), то I является Ь-матроидом.

В.А. Баранским доказано следующее утверждение, обобщающее теорему Радо-Эдмондса в части, доказанной Радо: для любой модулярной целевой функции жадный алгоритм гарантированно находит оптимальное решение задачи (3) на любом Ь-матроиде в конечной геометрической решётке16.

1бБаранский В.А., Выплов М.Ю., Ильев В.П. О задаче максимизации модулярной функции в геометрической решётке // Известия Иркутского государственного университета, Серия "Математика". 2013. Т. 6, № 1. С. 2-13.

Интересен вопрос, выполняется ли для Ь-матроида аналог теоремы Радо-Эдмондса в части, доказанной Эдмондсом? А именно, верно ли, что если жадный алгоритм С?г для любой модулярной целевой функции гарантированно находит оптимальную базу порядкового идеала I конечной геометрической решётки, то I является ¿-матроидом? Оказывается, что это в общем случае неверно (соответствующие примеры решёток и порядковых идеалов построены и приведены в разделе 3.1).

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

Рассмотрим параметр, характеризующий близость порядкового идеала/к Х-матроиду: . . 1г( х)

С{1) = Ш1П -т-г,

хеЬ,ХуЬ0 иг(х)

где 1г(х) и иг(х) — минимальная и максимальная высота баз элемента х, соответственно. Очевидно, с(1) € (0,1], причём с(1) = 1, если и только если порядковый идеал I является ¿-матроидом. Величину с(1) будем называть кривизной порядкового идеала I.

Получено следующее обобщение оценки Дженкинса-Корте-Хаусмана (5).

Теорема 3.4. Пусть Ь — конечная геометрическая решётка, I — порядковый идеал решётки Ь,ш — модулярная функция на Ь, ги(0) — 0. Тогда для приближённого решения вСг задачи (3), найденного алгоритмом Сг, справедлива оценка

гфСг) > с(7)гф0).

где 50— база максимального веса порядкового идеала I, с(1)— кривизна I.

В разделе 3.3 рассматривается задача (4) минимизации супермодулярной функции на Ь-матроиде.

Элемент х' 6 Ь называется дополнением элемента х € Ь, если хУх' =1 и х А х' = 0. Обозначим йх(у) = /(х) - /(у), где х, у е Ь, х-> у.

Кривизна с/ неубывающей супермодулярной функции на конечной решётке характеризует ускорение возрастания функции и определяется следующим образом:

с/ = тах

- сЦО)

аеМ(Ь), ^х(а') «¿1(а')>0

где АЬ{Ь) = {а 6 Ь : а- > 0}.

Получена следующая гарантированная оценка точности жадного алгоритма для задачи (4) в терминах кривизны целевой функции. Ранее подобная оценка была доказана для булевой решётки17.

Теорема 3.5. Пусть я0 — оптимальное решение задачи (4), заг — решение, найденное жадным алгоритмом. Если Ь-матроид I обладает свойством (12), то справедлива оценка (1 — с/)/(зСг) < /(в0).

Основные результаты

1. Доказан аналог теоремы Биркгофа-Уитни для наследственных систем: показано, что решётка замкнутых множеств любой наследственной системы не содержит бесконечных цепей, и обратно, любая непустая решётка, не содержащая бесконечных цепей, изоморфна решётке замкнутых множеств некоторой наследственной системы. В частности, любая конечная решётка изоморфна решётке замкнутых множеств некоторой конечной наследственной системы.

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

3. Для задачи максимизации модулярной функции на порядковом идеале геометрической решётки получейа гарантированная оценка точности жадного алгоритма в терминах кривизны порядкового идеала, обобщающая известную оценку Дженкинса-Корте-Хаусмана для задачи максимизации аддитивной функции на системе независимости. Установлено, что теорема Радо-Эдмондса, справедливая для порядкового идеала булевой решётки, не может быть обобщена на геометрические решётки.

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

17Ильев В.П., Ильева С.Д. Задачи минимизации супермодулярных функций на матроидах и ко-матроидах // Материалы IV Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск. 2009. С. 51-55.

Публикации автора по теме диссертации Статьи в рецензируемых журналах из списка ВАК

1. Баранский В.А., Выплов М.Ю., Ильев В.П. Минимизация модулярных и супермодулярных функций на L-матроидах // Известия Иркутского государственного университета, Серия "Математика". 2011. Т. 4, № 3. С. 42-53.

2. Баранский В.А., Выплов М.Ю., Ильев В.П. О задаче максимизации модулярной функции в геометрической решётке / / Известия Иркутского государственного университета, Серия "Математика". 2013. Т. 6, № 1. С. 2-13.

3. Выплов М.Ю. Обобщение теоремы Биркгофа-Уитни для наследственных систем // Труды Института математики и механики УрО РАН. Екатеринбург. 2011. Т. 17, № 4. С. 66-75.

Другие публикации

4. Баранский В.А., Выплов М.Ю., Ильев В.П. Минимизация модулярных и супермодулярных функций на L-матроидах // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН. 2011. Jft 12. XIV Всероссийская конференция "Математическое программирование и приложения" (тезисы докладов). С. 148-149.

5. Выплов М.Ю. Решётки замкнутых множеств наследственных систем // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодёжной конференции. Екатеринбург: УрО РАН. 2009. С. 10-15.

6. Выплов М.Ю., Ильев В.П. О гиперграфах, соответствующих операторам слабого замыкания // Восьмая международная конференция "Дискретные модели в

. теории управляющих систем": Москва, 6-9 апреля 2009 г. Электронный сборник материалов конференции. Москва. 2009. С. 30-34.

7. Выплов М.Ю., Ильев В.П. Системы множеств и операторы слабого замыкания // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск. 2009. С. 119.

8. Выплов М.Ю., Ильев В.П. Решётки замкнутых множеств систем независимости // Материалы X Международного семинара "Дискретная математика и ее приложения". Москва: Издательство Механико-математического факультета МГУ. 2010. С. 224-227.

9. Выплов М.Ю., Ильев В.П. Приближенное решение задачи максимизации модулярной функции в геометрической решётке // Статистика. Моделирование. Оптимизация: Сборник трудов Всероссийской конференции (Челябинск, 28 ноября - 2 декабря 2011 г.). Челябинск: Издательский центр ЮУрГУ. 2011. С. 108112.

10. Выплов М.Ю. О представлении систем множеств в терминах замыкания // Тезисы докладов и лекций Международной школы-конференции "Математические проблемы ипформатики", Омск, 20-27 сентября 2013 г. Омск: Издательство ОмГТУ. 2013. С. 13-14.

Подписано в печать 26.01.2015. Формат 60 x84 1/16. Печ. л. 1,0. Тираж 100 экз. Заказ № 12.

Издательство Омского государственного университета 644077, Омск-77, пр. Мира, 55а Отпечатано на полиграфической базе ОмГУ 644077, Омск-77, пр. Мира, 55а