Введение к работе
Актуальность темы.
Полиматроидяый подход возник на стыке теории выпуклых многогранников, теории субмодулярных функций и дискретной оптимизации (ДО). .Важность полиматроидного подхода главным образом определлется его ролью в ДО. Задача распределения ресурсов (ЗРР) является модельной задачей ДО. К ней сводятся многие важные как прикладные (распределения инвестиций, унификации деталей, размещения предприятий), так и теоретические (минимизации субмодулярной функции на булеане) задачи. В математической постановке под ЗРР в ДО обычно понимают задачу максимизации порядково-вогнутой сепарабельной 'функции на целочисленном полиматроиде. Хорошо известно, что градиентное решение последней задачи, т.е. решение, построенное простым градиентным алгоритмом - алгоритмом координатного подъема, является оптимальным. Основной недостаток градиентных алгоритмов - большое (в общем случае полиномиально не ограниченное) число требуемых итераций. Для многих частных случаев ЗРР построены более эффективные алгоритмы решения. Однако, в общем случае, когда полиматроид задан своей ранговой функцией. ЗРР исследована слабо. Поэтому, актуальной становится проблема построения полиномиального алгоритма решения ЗРР.
Многогранник альтернирующих последовательностей (МАП) является допз'с-тимой областью важной практической задачи: задачи проектирования фильтров (ЗПФ) на ПАВ, состоящей в следующем. Необходимо найти топологию фильтра, которая наилучшим образом удовлетворяет технологическим требованиям, выраженным линейной или сепарабельной целевой функцией. Каждая возможная топология фильтра на ПАВ соответствует последовательности длины п. состоящей из 1,-1 и 0, в которой ненулевые элементы чередуют знак. Такие последовательности называются альтернирующими, а их выпуклая оболочка в R" многогранником альтернирующих последовательностей (МАП). Таким образом. для решения ЗПФ нужно решить соответствующую задачу оптимизации на МАП. Следовательно, возникает проблема линейного описания МАП, изучения его комбинаторных свойств и построения на их базе эффективных алгоритмов решения ЗПФ.
Каждый полиматроид однозначно определяется своей ранговой функцией, которая неубывает и субмодулярна. Поэтому конус ранговых функций д-мерных полиматроидов А[п) часто называют конусом субмодулярных функций. Проблема
.-1-
характерпзацни экстремальных лучей конуса ,'\(ti) была поставлена еще Эдмо! сом в 197U году. Ее решение тесно связано с дальнейшим развитием теор декомпозиции субмодуллрных функций, играющей важную роль при ' синтс алгоритмов решения оптимизационных задач с полиматроидной допустим областью. В общем виде данная проблема чрезвычайно сложна и полності решена только для п = 2.3,4,5. Поэтому актуальной становится задача вы; лення возможно более широких подконусов конуса Л(п) и характеризацпи экстремальных лучей.
Связь работы с крупными научными программами и темами.
Диссертация выполнялась с 11)91 по 1995 год на кафедре МО САПР Белп университета в соответствии с плановыми научными исследованиями по те "Разработка моделей, методов и программного обеспечения решения дискретні задач оптимизации проектных решений в САПР изделий микроэлектроники вычислительной техники', а также на кафедре математической оптимизац: Магдебургского университета (Германия) в рамках гранта Gotlieb Daimler-иші К Benz-Stil'tuiig N 2.9:5.22.
Цели и задачи иследования.
Конкретные цели работы, с учетом вышесказанного, состоят в следующем:
построить полиномиальный алгоритм для задачи .максимизации порядког вогнутой сепарабельной функции на целочисленном полиматроиде. задати своей ранговой функцией;
найти линейное описание МАП и исследовать его комбинаторные свойств
построить эффективные алгоритмы решения задач линейной и сепарабельн оптимизации на МАП:
выделить возможно более широкие подконуса конуса ранговых функц: полиматроидов и дать характеризацию их экстремальных лучей.
Научная новизна полученных результатов.
Научная новизна полученных результатов состоит в следующем:
1) Получен ряд новых свойств и указаны способы построения нижних и верхи оценок градиентного решения ЗРР.
'.) Разработай дихотомический алгоритм (ДА) дли решения 31*Р и доказана, его полпномпальноеть. Показано, что алгоритм ЛА имеет «'ложность, практически совпадающую с рекордной.
!) Построены эффективные комбинаторные реализации алгоритма ДА для
ОДНОРОДНЫХ, обобщеННЫХ СНММетрИЧОСКИХ, ЦеПОЧНЬИС И ДроПОПИДНМХ ІШЛІ1-
матрондоп.
1) Предложены новые простые доказательства оптимальности трех известных алгоритмов для ЗРР (в общей постановке, на полпматропде, заданном точным списком ограничении, и на. древовидном полпматропде).
1) Получено линейное описание МАП и доказано, что он ппллетсл сообщенным полиматроидом.
(?) Определены многие комбинаторные характеристики МАП (диаметр, критерий смежности вершин, /-вектор, комбинаторный, тип).
Т) Разработаны эффективные алгоритмы для линейной и сепарабельноп оптимизации на МАП.
-
Введен конус полумодуллрных ранговых функций L(n) и дана характерпзация его экстремальных лучей. Показано, что конус Цп) является наиболее широким среди всех полностью характеризованных до настоящего времени подко-нусов конуса субмодулярных функций Л{н).
-
Установлено соответствие между экстремальными функциями (функциями, задающими экстремальные лучи) конуса L(ti) и конуса матрондных рангопых функций .!/(».) Доказана вырожденность небулевых экстремальных функций конусов ;1/(к) и L(n).
Практическое значение полученных результатов.
Дихотомический алгоритм решения ЗРР, разработанный в диссертации, іжег быть применен при решении ряда практических задач (распределения вестпции, унификации детален, размещения предприятии), а доказанные онства градиентных решений - при разработке других методов решения задач О.
Предложенные в диссертации алгоритмы для решения ЗП'І* реализованы п \ПР для автоматизации проектирования фильтров на 11АІЗ.
-li-
Результаты исследовании конуса субмодулярных функции могут быть urn зованы при построении программ - генераторов тестовых задач.
Экономическое значение полученных результатов.
Экономическое значение результатов работы состоит главным образо использовании алгоритмов решения ЗПФ при создании САПР, лпллюни коммерческим продуктом. Оценить экономическое значение других результ; диссертации в настоящее время не представляется возможным.
Основные положения диссертации, выносимые па защиту:
-
Новые свойства градиентных решений ЗРР.
-
Полиномиальный алгоритм для решения ЗРР.
:!. Линейное описание, полиматроиднал и комбинаторная тракторизация М.
I. Эффективные; алгоритмы для линейной и сепарабельной оптимизации МАП.
а. Полная харлктершацпя матропдного и полумодулярного подконусов коп субмодулярных «функций.
Личный вклад соискателя.
В диссертации изложены результаты, полученные лично автором, а та: анализ некоторых результатов других авторов по теме исследования.
Апробация основных результатов.
Основные результаты диссертации докладывались на школе-семинаре по дг ретной оптимизации (Минск,!!)!):) г.), на (ьй конференции математиков Белар; (Гродно. Н)!)'2 г.), на международной конференции 1КМ'94 (Ваймар. 19!) I г.). международном семинаре "'Discrete Optimization" (Ваймар, 1991 г.), на меж народной конференции "'Operations Research'" (Берлин, 1994 г.), на ьоллокви; по комбинаторике (Гамбург. 1994 г.), на международной конференции по ком наторной оптимизации ЕССО VIII (Познань, 199") г.).
Оиублнкопанность рсзультатоп.
Из совместно опу5ликоппнных раґніт в диссертацию включены результаты, пученные лично автором. Основные результаты диссертации опубликованы d работах.
Структура и объем диссертации.
Диссертация состоит из введення, общей характеристик» работы, четырех гш. основных выводов и списка используемых источникоц из 121 наименования, іа содержит !)8 страниц машинописного текста, в том числі? (і рпсупкоп.