Введение к работе
- З -
Актуальность теиы. Ряд результатов, полученных за послед-ше годы в области дискретной оптимизации, посвящен нсследова-шю классов задач, выделяемых на основе некоторого свойства сритерия и ограничений. В частности, получил распространение юдход, основанный на описании априорной информации о классах зункций в виде частичного порядка, относительно которого крите-зии из данного класса или их градиенты изотонны. Информация о їзотснности критерия широко используется для получения необходимых условий оптимальности в задачах на подстановках, в зада-tax теории расписаний, в задачах выпуклой симметрической опти-мзации. Использование информации о изотонности градиентов ле-сит в основе субмодулярной оптимизации.
В диссертационной работе поставлена цель исследовать сблзь іетода частичных порядков и традиционных методов выделения аіассов. Основным объектом исследования язляетея отношение -<а :анонического частичного порядка и связанные с ним оптишзаци-ішше задачи. Канонический порядок изучался ранее рядом авторів. В частности, описан класс-линейных функций, изотонных отно-ттельно <а, исследовались обобщения канонического порядка и их вязь с оптимальними градиентныш решениями на магроидных стру-:турах. Однако, открытой остается проблема полного описания :ласса непрерывно-дифференцируемых функций и функций дискрет-'ого аргумента, изотонных относительно <а. Требуют дальнейшего :зучения условия оптимальности градиентного ревения для задач с ;елевыш функциями из данного класса. Не изучены комбинаторные арактеристики целочисленных множеств, упорядоченных каноничео-іш порядком, позволяющие установить шенноновскую сложность ал-'оритмов вычисления локальных оптимумов.
Цель работы:
'- описать класс непрерывно-дифференцируемых функций, изо-онных относительно канонического порядка;
исследовать условия оптимальности градиентных решений адач с целевыми функциями из этого класса;
установить комбинаторные свойства подмножеств 1+, упоря-оченных отношением <а\
- исследовать задачу нахождения локальных оптимумов изотопных функций на (Z,<a). Научная новизна:
-
Полностью описан класс 5а непрерывно-дифференцируемых функций, изотонных относительно каношіческого порядка <а,
-
Установлено, что гтггиыальноеть градиентного решения в задачах с целевой функцией из класса 5а определяется единственностью максимального элемента допустимого множества относительно порядка <а.
-
Получены критеріш существоваїшя единственного максимального елемента' относительно <а для вшіуїишх полиэдральных множеств.
-
Исследовано отношение вложимооти канонических порядков. В частности,.показано, что координаткий и лексикографический порядки являвтея честными случаями порядка <а.
Ь) Описано множество S.(D) векторов а, определяющее семейство всех канонических порядков <а, относительно которых данный выпуклый полиэдр D обладает единственным максимальным элементом; тем самым описано максимальное по включению семейство клас-сав 2а, гарантирующих оптимальность градиентного решения любой задачи с целевой функцией из отого семейства.
-
Введено понятие обобщенного нелинейного канонического порядка и в его терминах получены результаты, аналогичные доказанным ранее для порядка <а.
-
Установлена связь подмножеств (,z",4C; с решетками раз-
биений и списаны их комбинаторные характеристики.
8) Описан вффективный алгоритм построения минимального
цепного разлоаения множеств (Єр,<а), (Ф'т,<а) и fz",ni,-<aj при
некоторых о.
Практическое значение. Предложенные в диссертации подходы к решению оптимизационных задач реализованы в системе топографического проектирования и используются в ряде ВУЗов и предприятий J
Публикации и ьпробация работы. По теме диссертации опубликовано 7 работ. Основные результаты докладывались на школе-семинаре по дискретной оптимизации (Алушта 1990,1991), на международном семинаре "Discrete Optimization" (Магдебург 1992,
_ 5 -
Мішок 1993), на 4-й конференции математиков Беларуси (1992).
Структура и объем работы. Диссертация состоит из введения, двух глав и списка цитируемой литературы из 82 наименований. Общий объем работ» 101 страница машинописного текста.