Введение к работе
Актуальность темы. Дискретные оптимизационные модели широко ірименяются при решении задач, возникающих в экономике, технике, /правлении и других областях. Разработка методов решения задач цискретной оптимизации началась в конце 50-х и начале 60-х годов s интенсивно ведется в настоящее время. В последнее время в разработке алгоритмов решения задач дискретной оптимизации акценты зущесгвенно сместились на разработку программных средств, направленных на решение прикладных задач. Отметим, что основополагаю-цими в дискретной оптимизации являются работы В.С.Михалевича, О.Сергиенко, Н.З.Шора, Ю.И.Журавлева, В.К.Леонтьева, В.ПЛере-тана, В.Р.Хачатурова, Д.А.Супруненко, В.А. Емеличева, В.С.Танаева, З.В.Шкурбы, В.И.Буркова, Р.Гомори, Н.Кристофидеса, Э.Балаша, Р.М.Карпа, М.Хелда, А.Ленд, А.Дойг и ряда других советских и зарубежных авторов.
Среди дискретных оптимизационных моделей важное место зани-яают модели для задач типа коммивояжера. Задачи типа коммивояжера встречаются во многих прикладных задачах, среди которых можно этметить следующие: упорядочения, классификации, ранжирования, расписания, радиотехники, очередности ввода объектов при освоении территории и т.д. Большинство встречающихся в приложениях задач сарактеризуются большой размерностью. Поэтому разработка алгоритмов, допускающих их эффективную реализацию на ЭВМ для задач больной размерности, важна и актуальна.
Применение дискретных оптимизационных моделей для решения прикладных задач предполагает использование программных средств. Іля многих моделей (общего типа) разработаны общедоступные программные средства, которые успешно применяются. Решение задач шециального типа связано о разработкой программного обеспечения, зриентированного.на эти задачи.
В то же время известно, что при реальном, применении раара-5отанных средств для решения задач дискретной оптимизации возни-<ают большие вычислительные трудности. Предложены некоторые из возможных подходов для преодоления вычислительных трудностей, :реди этих подходов отметим следующие: переход от поиска точных решений к поиску приближенных; применение комбинированных алгорит-
- г -
мов различных типов; применение диалоговых процедур; комбинирова ние указанных выше подходов; применение многопроцессорных ЭВМ и другие.
Ограниченность возможностей каждого из методов (точных или приближенных) решения задач дискретной оптимизации (особенно бол шой размерности) естественным образом приводит к идее разработки комбинированных алгоритмов, в которых объединялись бы преимущест ва методов и, по возможности, отсутствовали бы их недостатки. По комбинированными понимаются переметризованные алгоритмы, управля щие параметры которых определяются в процессе решения задачи. Ко бинированный алгоритм решения конкретной задачи формируется в пр цессе решения этой задачи; в этом принципиальное отличие комбини рованного алгоритма от алгоритмов, применявшихся ранее.
Глубокое общетеоретическое исследование комбинированных эвристических алгоритмов выполнено Ю.И.Журавлевым. Необходимость разработки комбинированных алгоритмов для решения задач теоретической и прикладной кибернетики впервые отмечена А.А.Ляпуновым. Применительно к задачам оптимизации (для функций многих переменных) этот подход предложен Н.Н.Моисеевым.
В диссертационной работе рассматриваются дискретные задачи большой размерности типа коммивояжера, для решения которых приме няются разработанные комбинированные алгоритмы различных типов. Разработанные подходы могут применяться для решения различных классов задач дискретной оптимизации. Актуальность темы определяется необходимостью решения широкого класса прикладных задач, сводящихся к задачам типа коммивояжера.
Цель и задача исследования. Целью работы является разработка дискретных математических моделей и комбинированных алгоритмов для решения задач дискретной оптимизации типа задачи коммивояжера и их применение для решения широкого класса прикладных задач указанного типа, характеризующихся большой размерностью.
Метод исследования. Для исследования применяются комбинатор ные методы решения задач дискретной оптимизации, комбинированные алгоритмы различных типов, моделирование прикладных задач типа коммивояжера.
Научная новизна результатов.
1. Предложена общая схема разработки комбинированных алгорит-
юв ветвей и границ для решения задач дискретной оптимизации. Вы
члени основные управляющие параметры комбинированных алгоритмов
[ сформулированы .эвристические правила определения значений зтих гараметров. Схема реализована для задачи коммивояжера и применяйся для решения задач большой размерности в декомпозиционном гадходе.
2. Предложен подход, позволяющий в процессе решения задач
искретнрй оптимизации определить наилучшую последовательность
лгоритмов приближенного решения этих задач из заданного списка
лгоритмов их решения при известном начальном приближении. Ука-
ана область применения разработанного подхода, описана его
еализация для задачи коммивояжера на плоскости.
3. Предложена единообразная схема организации информации
дереве подзадач для алгоритмов с древовидной схемой поиска
ешения задач дискретной оптимизации. Выделены основные группы нформации, описаны операции, выполняемые на дереве в процессе оиска решения. Предлокенная схема применяется в работе при рвении всех задач с древовидной схемой поиска решения.
4. Предложен декомпозиционный подход для приближенного реше-
ия задачи коммивояжера большой размерности. На основании этого
эдхода разработаны две системы комбинированных алгоритмов:
ая решения симметрических задач и задач на плоскости. Системы рименялись для определения последовательности обхода точек на зчатных платах. Выделен класс задач дискретной оптимизации, ія которых может быть применен предложенный подход.
5. Приводятся постановки, разработы и реализованы алгоритмы
зшения следующих прикладных задач дискретной оптимизации: опреде-
зние радиуса устойчивости в задачах выбора; определение опти-
альной очередности обслуживания объектов с учетом замены обору-
)вания| поиск на графе ограниченного по длине пути с максималь-
ш-весом; выбор оптимального варианта транспортного манипулято-
t на складе; выбор оптимальных параметров развития магистраль->го нефтепровода. Алгоритмы решения первых четырех задач раз-ібстанн на основании различных версий комбинированных алгорит->в решения задачи коммивояжера; алгоритм решения последней за-ічи близок к комбинированному алгоритму в идейном откошенш.
-
Разработаны математические модели и алгоритмы решения задач компоновки. На их основании разработана Диалоговая система проектирования схемы генплана (ДИСП СГП).
-
Разработана подсистема для определения очередности ввода скважин в "Системе проектирования генеральных схем проектирован! обустройства нефтяных месторождений на ЭВМ". Построена математическая модель и разработаны алгоритмы решения, основанные на декомпозиционном подходе и комбинированных алгоритмах решения задг чи коммивояжера большой размерности,
-
Эффективность всех разработанных подходов зксперименталі но подтверждена при решении больших серий задач. Основные злемеї ты этих подходов могут быть применены для решения широких классе задач дискретной оптимизации.
Внедрение. На основе предложенных подходов разработано программное обеспечение для ЭВМ БЭСМ-6 как для решения отдельных оі тимизационных задач, так и систем автоматизированного проектирования.
Разработанные системы комбинированных алгоритмов для решен задачи коммивояжера большой размерности применялись для определения последовательности обхода точек на печатных платах для Ж АН УССР (г.Киев) и ШІ АН CQCP (г.Москва).
Разработанное программное обеспечение для решения задачи -коммивояжера применялось на предприятии п/я М-5836 (г.Куйбышев) для определения машрутов кратчайшей длительности транспортно-складских роботов (TCP). На основе проведенных исследований на предприятии были разработаны и внедрены TCP повышенной произ водительности.
Разработана система для определения очередности ввода скважин на нефтяном месторождении. Система работает как модуль Системы проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ (СПГСО). Система применялась для одного из месторождений на территории Коми АССР по информации института ПечорНИПИнефть. Полученные варианты очередности ввода одобрены специалистами института.
Алгоритмы решения задачи коммивояжера, разработанные в дис сертации, реализованы при разработке специального штематическс обеспечения для решения оптимизационных задач и задач машинной
'рафики в. рамках научно-исследовательских работ, выполняемых на jhhom из предприятии (г.Калинин) .
Под руководством диссертанта разработана Диалоговая система [проектирования схемы генплана (ДИСП СГП), которая применялась зовместно с ЦНИИПградостроительства (г.Москва) для решения задач функционального зонирования территории в районной планировке б зоне влияния Чебоксарской ГЭС. По заключению специалистов система шляется перспективной и может широко применяться для решения юдобных задач.
Под руководством диссертанта разработан алгоритм для реше-тоя задачи определения оптимальных параметров развития магистраль-іого нефтепровода, программа разработана и применяется в институте ГИПР0ТРУБ0ПРОВ0Д (г.Москва).
Апробация работы. Результаты, полученные в работе, докладывались на Всесоюзной конференции "Экстремальные задачи и их при-гожения к вопросам планирования, проектирования и управления сложными системами" ( У симпозиум по экстремальным задачам, г.Горький, 1971 г.), Ш Всесоюзной конференции по исследованию шераций (г.Горький, 1978 г.), Всесоюзной научной конферении 'Декомпозиция и координация в сложных системах" (г.Челябинск, [986 г.), IX Всесоюзном симпозиуме "Системы программного обеспе-іения решения задач оптимального планирования" (г.Минск, 1986 г.), И Всесоюзной школе "Дискретная оптимизация и компьютеры" (г.Ташкент, 1987 г.), Республиканском семинаре "Методы решения и мате-латическое обеспечение задач дискретной оптимизации" (г.Киев, Ж АН УССР, 1987 г.), семинаре ВЦ АН СССР "Теория управления" [1987 г.), УШ Всесоюзной конференции "Проблемы теоретической сибернетики" (г.Горький, 1988 г.), 71 Всесоюзной конференции " 'Методы математического программирования и программное обеспе-іение" (г.Свердловск, 1989 г.), на семинаре "Математическая кибер-іетика" института математики АН БССР (г.Минск, 198Э г.).Результаты работы освещались в циклах лекций по прикладному дискретно-іу программированию, которые читались автором в КМ с ВЦ АН Мол-цавской ССР (1981 г.), в Горьковском Государственном университете (1981 г.), в Челябинском политехническом институте (1984 г.), га, летней школе по исследованию операций, организованной в г.Варна Інститутом математики с вычислительным центром Болгарской Академии наук (1989 г.).
Публикации. По теме диссертации опубликовано 35 работ.
Структура работы. Диссертация состоит из введения, 7 глав, заключения, списка литературы, изложенных на 295 страницах, 33 рисунков, 222 наименований литературы.
