Введение к работе
",.)\
І ..::'::'диссертационная робота поспякепа разработке алгоритмов ^'-'р^идния экстремальное задач коміїюіаторггаго типа, т.о. задач "-'вмбЦїв наядучш&го по олродолешіому критерию подмножеств» из заданного конечного миохпства допустимых подмножеств. Класе задач этого типа чрозвачпФю обширен. Экстремальные задачи комбинаторного типа появляются в чистой или усложненном вздэ во шюг.и практических оптимизационных модолях.
Актуальность тома. Значительная часть задач рассматриваемого класса н& изучена к настояному нремони в достаточной море, о чом соадето^ьстнуот огромное количество !іуо\я-»ка;щЯ, посватанных эти* задачам. Ксслепования по теории сложности дискретных оптллызвциопннх задач и методов их рояанип, шполнвшыэ Яблонским СВ.. Журанловчм П.11. , ЛОВЛЯМ А.А., Куком С. Д., Карпом Р.Н. и др., лрип&лд it шделі>;іжз двух вішмх гслзссов: NP-труданх зздяч и задач, для которых суп;с-ст -вууг ьфіоктишшо алгоритмы. В последних трудоемкость ре к: о пи я растет как полином с ростом длины пхс-да задачи. Болы.шстно нетривиальных зкстрональшх задач комбинаторного типа относится к классу NP-трудшх, а п&рспектикч. создания оадих аМ'чктивних (и с вычислительной, н с информационной точок зрения) методов юс роЕвітая риська пессимистична. В связи с этим особо» значение прноорвтаот рязрозотка точних а прноли-геиных алгоритмов и программного обеспечения решения задач определенных талон. .
В работе исследуются следующие задачи: 1 ) задача о максимальном Фронта ориентированной сети; _' 3) задача о наибольшем множоство попарно несравнима верглі ори&нтировекного гргфз;
-
задача рнзоаеная «ачоясос-твя;
-
задача оптимизация вариа.чтішх моделей.
Понятие» Фронта ориентированной сети (частіша пид рязре:ш)чвпдано в работах Корниловой Д.Е. в связи с рассмотренном задачи о минимальном потока. Там an ігсквзапо, что величина милимлльж го потока оуиня пропускно* способности максимального фронта. С іюмоаіьм изйг-ютішх алгоритмов можно рс-уиті» зада <у о максимальной фронта допустим .'Я сети, т.о.
сета, для которой задача о минимальном потока вмеет хотя бы одно решение, причем для этих алгоритмов не даїзі оценки трудоемкости. Вместе с том, для близкой задачи - задачи о минимальном разреза - в работах Эдмондса Дж. и Карпа P.M., Дичина Е.Д.., Карданова А.В. и др. разработаны методы, имеющие полиномиальную оценку трудоемкости. Поэтому представляет интерес построенло полиномиальных алгоритмов для задачи о максимальном фронте допустимых еатеЯ, о такко алгоритмов нахождения максимального Фронта в сетях общего вида и ориентированных графах. Кроме того, как показано в диссертационной работе, технике решения задачи о максимальном фронта можвт Сыть восьма плодотворно использована при разработке алгоритмов решения таких "грандов" ко.чйинаторной оптимизации, кш. задача упаковки вершин графа, задача разбиения кноаества, задача .назначения экипажи самолетов и др.
Задача о наибольшем множество попарно несравнимых (т.о. не принадлежащих одному пути) взвешенных вершин оривнтиро-вагаюго графа рассматривается в двух формулировках. Порвал -в обычной постановке, а вгоряя с дополнительными ограничениями, суть которнх соста;гг в следующем. Пусть множество вершин графа разбито на два подмножества !/ и Q. W - bto множество "обычных" вершин, 8 й- множество пар вершин. При этом произвольная вершина может входить лишь в одну пару и вершини любой пари должны бить несравнимыми. Для каздои пари задается обцлй СбС &э вериин, в не вес каждой пэ та. Требуется, чтобы в искомом множество лзобая пара была бы представлена либо двумя вершинами, либо ни одной из входящих в нее вершив. Й диссертационной рчооте показано, как известная NP-трудная задача упаковки вершин графа (в литературе часто называемая задачей о наибольшем внутренне устойчивом множества) моаэт быть сведена к исследуемой задаче с дополнительными ограничениями.
Задача разбионкя множества принадлежит к классу NP-трудных задач и можот быть сформулировала в вида задачи целочисленного программирования с булевыми переменными специального вида (кааудай элемент матрицы ограничения имеет значение 0 либо 1). Свойства задачи и алгоритми ее решения исследовались в работах Трубила В.А., Бадана Е., Падберга М. Пирса да;., Ласки Дк., Гарфидкеля Р., Исмхаузера Дії., Иэрото-
на ?., Мулвея Дж., Вебера Аж. я др. С помопьга известных алгоритмов иногда удается решить задачу разбиения множества с несколькими сотнями ограничений и весколысми тисячами переменных, но чсто задачи значиталыю менызих размерен (десятки ограничений и сотни поромашшх) но реиа.отся за приемлемое время.
- Рассматриваемы» в диссергациошюа работа вириантшо модели могут бить сфэрчулирова.ти в в.чдо задач цалочяслоіглого программирования с Оулешмї горекенними и (наряду с оОіджсі) узкоблочішми ограігиченишя вида У г,
Целью работы является разработка алгоритмов решения экстремальных комбинаторных задач специальных типов, исследование их эффективности и создание соотввтетвуицэго программного обеспечения.
Методика исследовании базируется на методологии решения звдач дискретной л сетевой оптимизации.
Научная новизна. Результаты диссертационной работы можно квалифицировать как направление в теории оптимизация,
связанное с разработкой косых численных методов решения задач сетевой и дискретной олтишоации специальных классов.
Изучены свойства фронтов сети, проанализировано их взаимное расаапохиииэ. Доказано утверждение о пересечении и объединении максимальних фронтов. Получено оценка наибольшого количества мэксгаиальнях фронтов и разработан алгоритм веденоішя всох максимальних фронтов сети. Известило алгоритмы решения задачи о минимальном потоке шдифпцироваїш с использованием аппарата справочных, применяемого для решения задача о максимальном потоке. Показана некорректность алгоритма решения задача о шштаахыюм потоке, првдлогдэшюго Бераам К. Разработай алгоритм с полиномиальной оценкой тру-доемкости решения задачи о максимальном фронте произвольной ориентированной сота, а также ориентированного графа. Показана возмошэсть ислользования максимального фронта сети для решения некоторая задач на ориентированных графах. Доказано утверждение, обобщащее теорему Дилворта на случай пронзволь-шх ориентированных Грефов.
Разработан алгоритм решения задачи о наибольшем множестве полярно по сравнимых взвезенных перлин ориентированного графа, в котором, в отлична от способа сведения к задаче о максимальном фронте, техника штода пометок применяется цо-поервдетввшю к исходному графу.
Оформулироввна задача о наибольшем множестве попарно несравнимых взвеїаеннцх вериин ориентированного графа с дополнительными ограничениями. Указан способ сведения к этой' задаче задачи упаковка вершин графа. Разработаны два алгоритма мато да ветвей и границ решения задача с дополнительными ограничениями. В первом алгоритме используются эвристические оценки, а во втором - двойственные, вычисленные с помощь» методов негладкой оптимизации. Результаты вычислительного эксперимента показала, что оба алгоритма "аффективно" (по крайней море по количеству вершин дарове вьтвлвний) решают рассматриваемуш задвчу. Проведано экспериментальное исследование эффективности метода решения упаковки вершин графа путем сведения ее к задаче с дополнительными ограничениями.
Разработаны два метода сведения задачи разбиения множества к сетевым оптимизационным моделям. В первом методе исходная задача сводится к задаче о максимальном фронте сети
с дополнительными ограничениями. Во втором мзтоде используется сведение к задаче о наибольшем множестве попарно несравнимых взвешенных вервин ориентированного графа с дополнительными ограничениями. Вычислительный эксперимент, проводоцныя для сравнения второго метода с другими извэстны-ми способами, позволяют сделать вывод о целесообразности применения этого метода, особенно для задач рязбиешія множества с плотность» матриця ограничений больше или равной 0.2.
На примере задачи назначения экипажей самолетов показана возможность применения сетевого подхода для вичислений оценок при решении практических задач, э которых наряду с ограничениями задачи разбивная множества есть ограничения общего вида.
Разработан алгоритм решения задача разбиения множества, основании!! на ндвях симплекс-метода и неявного перебора. Проведенный вычислительный эксперимент показал достаточно внсокуо эффективность алгоритма для задач с большой стьпанью заполненности матрицы ограничений.
Разработаны алгоритмы метода ветвей и границ оптимизации вариантных моделей,' использующие двойстве:ишэ опэшш, вычисленные с помощью методов негладкой оптимизации. Алгоритми позволяют решать задачи большой размерности; уменьшать количество априорно заданных вариантов (переменных); формировать область оптимизации модели. Провэдепо экспериментальное несладоваїшо эффективности алгоритмов.
Практическая цопность. Данная работа яаляотся состяо-иой часть следущдх 'исследования, проводимых в Ипституте ки-берпетихи им. В.И. Глушкова АН Украины:
і. Разработать и юиэстн в эксплуатацию ППП для решения на ЕС ЭВМ различных типов задач дискретной олтимизацлл (ДИСПРО-3).
-
Разработать и ввести в эксплуатации ППП для решения на ЕС ЭВМ оптимизациошпії задач производственно-транспортного планирования большой размерности (ПЛАНЕР).
-
Разработка и обоснование методов решения а программно -алгоритмического обеспечения отделышх классов задач дискретной оптимизации для ПЭВМ.
4. Разработка методов и программного обеспечения ПЭВМ для решения некоторых !сл8ссов экстремальных комбинаторных задач.
В указанный шкеты программ включен ряд оптимизационных модулей, реализующих описанные вша алгоритмы. Результаты работы использовались в ряде хоздоговоров, выполненных институтом.
Апробация. Основные результаты работа были представлены на седьмом Всесоюзном ситош^ае "Системы программного обеспечения решения задач оптимального планирования" (г. Нарва-йизсуу, 1982 г.), на втором Всесоюзном совещании "Метода и програшу решения оптимизационных задач на графах и сетях" (г. Улан-Удэ, 1982 г.), на республиканской школе -семинаре "Вопроси оптимазатш вычислений" (г. Киев, 1ЭЭ0 г.). а также на научных семинарах "Теория оптимальных решений" Института кибернетики 'им. В.М. Глуїикова АН Украины.
Публикации. Основное содержание работы отражено в 24 публикациях.
Объем и структура работы. Работа состоит из введения, четырех глав, зшитчения и списка литература из 98 наименований. Общий объем работы 2\і страниц, включая один рисунок и 9 таблиц.