Одним из наиболее важных научных и практических классов задач, для решения которых необходимо использовать все более совершенные электронно вычислительные машины, являются оптимизационные задачи. Параллельно с усовершенствованием ЭВМ, происходит разработка новых методов математической оптимизации. Многие прикладные оптимизационные задачи имеют существенно дискретный характер и не позволяют их решать непрерывными оптимизационными методами. Именно по этой причине, в классе оптимизационных задач выделился подкласс дискретных оптимизационных задач.
Алгебраический метод исследования задач дискретной оптимизации является одним из наиболее эффективных методов. Алгебраический подход к решению задач дискретной оптимизации, в сочетании с другими методами, разрабатывался в работах Биксби, Гомори, Журавлева Ю. И., Емеличева В. А., Ковалева М. М., Леонтьева В. К., Ловаса, Рыбникова К. А., Корте, Сеймура, Сергиенко И. В., Супруненко Д. А., Трубина В. А., Ху, Шора Н. З., Здмондса и ряда других авторов, см. [601, [S3 j ,.
ГШ, [4 63, ГШ, [231, №, [80], [5Л, [31], 1331, гл], WJ, [36]. №, ft 6] .
В последнее время, среди алгебраических методов, применяемых к решению дискретных оптимизационных задач, широкое распространение получили методы теории матроидов и теории групп.
Теория матроидов, так называемая «линейная алгебра» комбинаторного анализа, применяется к самым разнообразным задачам дискретной математики.
Впервые понятие матроида возникло в работе Уитни как формализация линейной независимости для специальных структур в теории графов. Применение теории матроидов к дискретным оптимизационным задачам началось несколько позже в работах Рдмондса, Татта, см. [S01, [S3], в которых матроидам отводилась роль структур, лежащих в основании всей дискретной оптимизационной теории. Такая точка зрения оправдала себя только частично. Был построен так называемый (^ZttcL^ -алгоритм для нахождения множества максимального веса относительно действительной положительно-значной функции, заданной на элементах матроида (/И .Построены эффективные алгоритмы для решения задач о максимальных многопродуктовых потоках для более широких классов сетей [И], [И], [61] .Усовершенствованы алгоритмы минимального разбиения множества с весами [4 3], 15П. Построены полиномиальные алгоритмы для решения задач декомпозиции графов и распознавания полной унимодулярности целочисленной матрицы, см. & J, [go], выбора минимальной подсистемы уравнений Теория матроидов успешно применяется и к решению прикладных технических задач, см. а], [ей, в теории планирования эксперимента. Область приложений теории матроидов постоянно расширяется.
С другой стороны, ряд комбинаторных, в частности дискретных оптимизационных задач, обладает свойствами близкими к матроидным, но отличающимися от последних рядом особенностей. В связи с важностью решения подобных задач, см.
Hi, [tf], 163} было предпринято ряд попыток обобщения понятия матроида, с целью расширения их области применимости. Основными конструкциями, обобщающими понятие матроида, есть следующие. Понятие суперматроида, см.
16], а также [S3] .Полуматроида Ц9]. Внезависимого матроида, см. [ft] .Биматроида [И ] .Гредоида, см. [?0].
Все вышеназванные конструкции, обобщающие понятие матроида, преследуют различные цели, но все они, кроме полуматроидов и гредоидов, являются системами независимости. -независимый матроид и матро-идный спектр, а также гредоид и полуматроид, не являются, в общем случае, системами независимости. Причем, полуматроид и гредоид являются специальными случаяминезависимого матроида, а ^ -независимый матроид является частным случаем матроидного спектра. Наглядно, -независимый матроид является комбинаторной конфигурацией^ которой для множеств с мощностью не меньшей, чем некоторое фиксированное целое число о^ выполняется аксиома независимости, а для множеств мощности меньшей, чем об выполняется не всегда. В матроидном спектре необходимо, чтобы аксиома независимости выполнялась для подмножеств с мощностями лежащими внутри нескольких целочисленных интервалов. Тем не менее, о^ -независимый матроид можно представить, если он не является вырожденным, в виде поочередных применений операций взиманий матроидов и отчуждений, теорема 1.2.2.Верна и обратная теорема, причем без условия невырожденности./Соответствующие определения и теоремы смотри в § 1.2 и §-1.1/.Такие конструкции являются достаточно общими, но и естественными, так как для них доказываются ряд классических теорем теории матроидов. Такими теоремами, например, являются теорема о равномощности базисов /теорема I.1.1/, перестановочная теорема для базисов /теорема 1.3.1/, так называемая обобщенная гипотеза Рота /теорема 1.3.2/.По поводу матроидных аналогов вышеназванных теорем см. 15П, [S8], ft Я .На естественность обобщения указывают и теоремы I.I.2 и I.1.3,которые описывают частично упорядоченное множество матроидных спектров, заданных на фиксированном множестве. А также теоремы 1.4.I и 1.4.2,которые показывают возможность построения прямого копроизведения и свободного универсального объекта в категориях, являющихся аналогами категорий матроидов и свободных отображений, см. В Я, [J Я чем, эти конструкции являются практически единственными работающими в обычных матроидах, см. [?Я, [?"], ГЦ], Из] .
Достаточно полные обзоры по теории матроидов и ее приложениям содержатся в [Ш и 1гз] .
В значительном числе оптимизационных, в частности дискретных задачах, не существует единого критерия оптимизации, что привело к созданию методов многокритериальной оптимизации. По-поводу дискретных многокритериальных оптимизационных задач, см., ['Н 2 ] 5.
И J, ГЯ], ГЯ], D6 9I, [91] .
В § 2.1 и § 2.3 настоящей работы предлагаются алгоритмы решения линейной многокритериальной оптимизационной задачи /2.1.3/-/2.1.5/ над матроидом №, ГШ. Алгоритм 2.1 Л, на основании теоремы 2.1 Л, находит независимое множество заданного матроида, тлеющее максимальный вес по Парето относительно функций /2.1.1/. Оценка временной сложности /2.1.27/ алгоритма 2.1 Л показывает, что алгоритм является эффективным и тем самым пополняется список эффективных по Эдмондсу алгоритмов.
В некоторых прикладных многокритериальных оптимизационных задачах необходимо построение всех решений с целью их дальнейшего анализа. Алгоритм 2.3.1 из § 2.3 находит полное множество Парето задачи /2Л.3/-/2Л.5/.
Алгоритм 2.2.1 из § 2.2 вновь демонстрирует важность теорем из §-1.2,на основании которых он строится. Алгоритм 2.2.1 находит обнезависимое множество невырожденного обнезависимого матроида максимального веса. Оценка временной сложности /2.2.19/ указывает на эффективность алгоритма 2.2Л, который в свою очередь пополняет список эффективно разрешимых задач.
Приведение целочисленных матриц к формам Смита и форме Зрми-та применяется для решения систем линейных уравнений в целых числах [Zi 1, в оптимальном управлении динамическими системами и других задачах. Впервые были введены в работах [Si] ,.
В дискретной оптимизации формы Смита начали применяться после работы Гомори [60 ], где Оыло показано как их применять для сведения задачи линейной целочисленной оптимизации к задаче оптимизации над конечное абелевой группой, см. [35], [9], Ц0].
В § 2.4 приводятся алгоритмы 2.4.1,2.4.2 и 2.4.3,которые сводят целочисленную матрицу к соответствующим формам Смита, Ярмита и форму Смита к нормальной форме Смита. Оценки их временной сложности /2.4-.22/,/2.4.24/,/2.4.27/ лучше аналогичных оценок других алгоритмов.
3S], что в сочетании с преимуществами алгоритма 2.5.1,решающего линейную групповую задачу, позволяет построить эффективную программную реализацию решения задачи линейной целочисленной оптимизации. эффективность программной реализации подтверждается и вычислительным экспериментом, результаты которого приведены в §-3.2,решением прикладных инженерных задач животноводческого машиностроения из §-3.3,акт внедрения программной реализации алгоритма находится в приложении к данной работее.
Теперь о структуре работы.
Работа состоит из введения, трех глав, заключения, списка литературы и приложения.
Первая глава работы посвящена формализации понятия комбинаторного объекта близкого к матроиду, так называемых обнезависимых матроидов и матроидных спектров, исследованию их свойств. Доказываются теоремы, описывающие их свойства, на основании которых доказывается справедливость аналогов ряда классических теорем теории матроидов для частичных матроидов. Исследуются категорныс и структурные свойства частичных матроидов.
Во второй главе, используя результаты главы первой, строятся алгоритмы решения задачи линейной оптимизации наднезависимым матроидом, задачи линейной многокритериальной оптимизации над матроидом, а также задачи нахождения полного множества Парето линейной многокритериальной задачи над матроидом. На основании исследования свойств целочисленных матриц, а также связанных с ними задач теории чисел и теории групп. строятся новые алгоритмы сведения целочисленной матрицы к форме Смита, нормальной оюрме Смита, форме Зрмита. Строится алгоритм решения линейной групповой задачи. Для всех алгоритмов главы 2 вычисляются оценки временной сложности. Глава три посвящена программной реализации алгоритма решения задачи линейной целочисленной оптимизации, основанного на алгоритмах главы 2. Приводятся результаты вычислительного эксперимента, а ' также результаты применения программной реализации к решению практических задач.
В заключении перечисляются основные результаты диссертационной работы.
В приложенный находится акт внедрения программной реализации алгоритмов работы и вынесено ряд вспомагательных утверждений.
Таким образом, основные результаты диссертационной работы, которые выносятся на защиту, следующие.
I/Построение и исследование свойств теории частичных матроидовобъектов, для которых аксиома независимости гарантировано выполняется только для множеств фиксированной мощности, так называемых.
— независимых матроидов и матроидных спектров. Доказательство теорем 1.2Л и 1.2.2,позволяющих сводить результаты о матроидах к.
— независимым матроидам и представлять невырожденный о£ -независимый матроид в виде совокупности матроидов. А также, теорему I.2.3,которая сводит матроидный спектр кнезависимому матро-иду и обратно. В частности, получены следующие результаты: а/доказана справедливость перестановочной теоремы для базисов.
— не з ави симо г о матро ид, а б/ доказана справедливость обобщенной гипотезы Рота для обнезависимых матроидов, теорема 1.3.2. /В случае невырожденности/. 2/йсследованы категорные свойства частичных матроидов. Построены прямые копроизведения для категорий невырожденных ?? -независимых матроидов и о^ -независимых матроидов равной высоты, и свободных отображений, теоремы 1.4.I и 1.4.2.Построены свободные универсальные объекты в категориях матроидных спектров, -независимых матроидов и свободных отображений, теорема 1.4.3. З/Исследованы структурные свойства частично упорядоченных множеств с£> -независимых матроидов и матроидных спектров, упорядоченных с помощью свободного отображения, теоремы I.I.2 и I.I.3. 4/На основании исследования свойств решения многокритериальных задач над матроидом получены алгоритмы решения следующих задач: а/задачи линейной многокритериальной оптимизации над матроидом, алгоритм 2.1.I, с оценкой временной сложности.
Q (ln, ztoqyi) т), где YOмощность основного множества матроида, WO — число функций, что расширяет класс эффективно разрешимых задачб/зад, ачи нахождения полного множества Парето для линейной многокритериальной оптимизации над матроидом, алгоритм 2.3.1. 5/На основании исследования свойствнезависимых матроидов, построен алгоритм решения задачи линейной оптимизации наднезависимым матроидом, алгоритм 2.2.1,с оценкой временной сложности.
О {п (уь-к)кг), где УЬмощность основного множестванезависимого матроида^ 1>Ъмощность его спектра, в случае, когданезависимый матроид является невырожденным, пополняя класс эффективных алгоритмов. б/На основании теоретических исследований свойств целочисленных матриц, теоремы 2.4.1 и 2.4.2,получены новые алгоритмы приведения целочисленной матрицы к нормальной форме Смита, форме Смита и форме Ррмита с улучшенной оценкой временной сложности /алгоритмы 2.4.1,2.4.2 и 2.4.3/.
7/Построен новый алгоритм решения задачи линейной оптимизации над, конечной абелевой группой /алгоритм 2.5.1/ и его модификации, не зависящие от числа компонент циклических подгрупп абелевой группы, а также требующие для своей программной реализации меньший объем оперативной памяти, чем в других аналогичных алгоритмах. 8/Алгоритм решения задачи линейной целочисленной оптимизации, основанный на алгоритмах настоящей работы, эффективность которого демонстрируется результатами вычислительного экспериментам также применением к задач/ш оптимизации конструктивных параметров и раскроя материалов для животноводческого машиностроения.
Все вышеуказанные результаты являются, но вбили и принадлежат автору.
Работа выполнена в отделе экономической кибернетики Института кибернетики АН УССР им. В. М. Глушкова.
ЗАКЛЮЧЕНИЕ
В заключении перечислю/! основные результаты диссертационной работы.
I/Построена и исследована теория частичных матроидов, т. е. матроидов, для которых аксиома независимости гарантировано выполняется только для множеств фиксированной мощности, так называемыхнезависимых матроидов и матроидных спектров. Доказаны теоремы, позволяющие сводить теоремы для частичных матроидов к соответствующим теоремам для матроидов и применять теорию матроидов к исследованию частичных матроидов. В частности получено: а/доказана справедливость перестановочной теоремы для базисов.
С, -независимых матроидовб/доказана справедливость обобщенной гипотезы Рота длянезависимых матроидов. /В случае невырожденности сС-н.м./. 2/йсследованы категорные свойства частичных матроидов. В частности, построены прямые копроизведения и свободные универсальные объекты, соответственно, ^ -независимых матроидов /невырожденных/ и свободных отображений, и с£ -независимых матроидов и матроидных спектров.
З/Исследованы структурные свойства множеств обнезависимых матроидов и матроидных спектров, упорядоченных с помощью свободного отображения. В частности показано, что множество Ох К-Х) всех матроидных спектров фиксированной сигнатуры и над фиксированным множеством ОС является выпуклым подмножеством множества всех матроидных спектров той же сигнатуры, определенных над тем же множеством, но произвольного ранга S. (0^/4,., о^к") .Построены максимальные и минимальные элементы соответствующих частично упорядоченных множеств.
4/На основании исследования свойств решения линейных многокритериальных задач над матроидом получены алгоритмы решения следующих. задач: а/задачи нахождения независимого множества матроида, имеющего максимальный вес по Парето относительно положительных действительнозначных функций, заданных на матроиде, с оценкой временной сложности.
0((уьг locf Уь) Wb), где УЬмощность основного множества, Wjчисло функцийб/нахождение полного множества Парето для линейной многокритериальной оптимизационной задачи над матроидом. 5/На основании исследования свойств ^ -независимого матроида построен алгоритм нахождения ^ -независимого множества максимального веса для невырожденногонезависимого матроида с оценкой временной сложности.
О (иЛи, — к) кг), где УЬмощность основного множества ^ -независимого матроида, a Pbмощность его спектра.
6/Построен новый алгоритм решения задачи линейной оптимизации над конечной абелевой группой. Его эффективность демонстрируется результатами вычислительного эксперимента и оценками временной сложности, а также величиной объема необходимой оперативной памяти. 7/На основании исследований алгебраических свойств целочисленных матриц получены алгоритмы приведения целочисленной матрицы к нормальной форме Смита, форме Смита и форме Ррмита с оценкой временной сложности лучшей, чем у известных алгоритмов.
8/На основании алгоритмов из б/ и 7/ построен алгоритм решения зец-дачи линейной целочисленной оптимизации. Проведен вычислительный эксперимент, показавший эффективность программной реализации данного алгоритма.
9/С помощью программной реализации алгоритма из 8/ решались задачи оптимизации конструктивных параметров и раскроя материалов для животноводческого машиностроения.
— юо.
