Алгебраические методы исследования некоторых задач дискретной оптимизации

• Автор: Грицак, Валерий Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Киев
• Количество страниц: 125 c. : ил

ГЛАВА I.ИССЛЕДОВАНИЕ АЛГЕБРАИЧЕСКИХ И КОМБИНАТОРНЫХ СВОЙСТВ СИСТЕМ НЕЗАВИСИМОСТИ % ЧАСТИЧНЫХ МАТРОИДОВ.

§1.1.Системы независимости и частичные матроиды.Основные определения и примеры

§1.2.Структура £/ -независимых матроидов и матроидных спектров

§1.3.Теоремы перестановочного типа для с£ -независимого

матроида
§1.4.Категорные свойства матроидных спектров и -независимых матроидов.Построение прямого копроизведения и свободного универсального объекта

ГЛАВА 2.АЛГОРИТМ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ КОМБИНАТОРНОЙ И

ЦЕЛОЧИСЛЕННОЙ 0ПТ1ШЗАЦИЕ.

§2.1.Решение задачи нахозкдения независимого множества,максимального по Парето,для линейной многокритериальной оптимизации над матроидом

§2.2.Нахождение множества наибольшего веса для....-независимого матроида

§2.3.Построение полного множества Парето для задачи линейной многокритериальной оптимизации над матроидом
§2.4.Алгоритмы сведения целочисленной матрицы к нормальной форме
Смита,форме Зрмита,форме Смита
§2.5.Решение задачи линейной целочисленной оптимизации над конечной абелевой группой
ГЛАВА 3.ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОЙ ЦЕЛОЧИСЛЕННОЙ ОПТ/ШЗАЦЖ .ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ. ПРИЛОЖЕНИЯ.

§3.1.Программная реализация алгоритма решения задачи линейной
целочисленной оптимизации
§3.2.Результаты вычислительного эксперимента с программной реализацией алгоритма решения задачи линейной целочисленной оптимизации на РВМ ЕС
§3.3.Постановки и решения задач оптимального раскроя материалов

Заключение
Список литературы
Приложения

Одним из наиболее важных научных и практических классов задач, для решения которых необходимо использовать все более совершенные электронно вычислительные машины,являются оптимизационные задачи. Параллельно с усовершенствованием ЭВМ,происходит разработка новых методов математической оптимизации.Многие прикладные оптимизационные задачи имеют существенно дискретный характер и не позволяют их решать непрерывными оптимизационными методами.Именно по этой причине,в классе оптимизационных задач выделился подкласс дискретных оптимизационных задач.
Алгебраический метод исследования задач дискретной оптимизации является одним из наиболее эффективных методов.Алгебраический подход к решению задач дискретной оптимизации,в сочетании с другими методами,разрабатывался в работах Биксби,Гомори,Журавлева 10.И.,Емеличева В.А.,Ковалева М.М.,Леонтьева В.К.,Ловаса,Рыбникова К.А.,Корте,Сеймура,Сергиенко И.В.,Супруненко Д.А.,Трубина В.А.,
Ху,Шора Н.З.,Эдмондса и ряда других авторов,см. [60] , ,
[15] . [161 , [18] , КЗ] , [90] , [80] ,
[31] , [зг] , [зз1 , [39] , [з5] , [зб] ,
[50] , [9 6]
В последнее время,среди алгебраических методов,применяемых к решению дискретных оптимизационных зццач,широкое распространение получили методы теории матроидов и теории групп.
Теория матроидов,так называемая "линейная алгебра" комбинаторного анализа,применяется к самым разнообразным задачам дискретной математики.
Впервые понятие матроида возникло в работе Уитни Ш1 как формализация линейной независимости для специальных структур в теории графов.Применение теории матроидов к дискретным оптимизацио-

дения независимого множества матроида Л/1 максимального веса и правила /2.1.3/-/2.1.5/ вырождаются в ^алгоритм,
см. Ш ,а также [ёЗ] .С другой стороны, 1У(Й I-°у') по индуктивному предположению было максимальным среди независимых множеств матроида ЛА ,содержащих 1'{ элемент.А так как тле-

е($Ъ)» и[е1),
тогда множество с (# /) будет максимумом Парето среди независимых множеств мощности I ,из максимальности С10 и
из условия с/ теоремы 2.1.1 на выбор элемента в
Как следствие теоремы 2.1.1,получим следующий алгоритм.Пусть . задан матроид из /2.1.3/,причем й--уь, и функции вида
/2.1.1/.
АЛГОРИТМ 2.1.1.
Шаг 0.Выберем произвольное {,ИЪ и зафиксируем функцию из /2.1.1/ .Присвоим /// • —■
Шаг I.Линейно упорядочим множество Л' согласно весов его элементов относительно функции ^!о > »по возрастанию.
Пусть
/2ЛЛ8
будет необходимое линейно упорядоченное множество.
Шаг 2.Множество ^^разобьем на подмножества и запишем в виде таблицы
■. а-г,
а,.. ■ , Ч
/2.1.19
где 0 -ая строка таблицы /2.1.19/ является списком элементов множества из /2.1.6/.Дальше,присвоим & : = к