автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Дискретные модели и методы решения задач типа коммивояжера большой размерности

1 о ~ 9 О

АКАДЕМИЯ НАУК СССР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

СИГАЛ Израиль Хаимович

УДК 519.688 : 519.854

ДИСКРЕТНЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДА? ТИПА КОММИВОЯЖЕРА БОЛЬШОЙ- РАЗМЕРНОСТИ: ИССЛЕДОВАНИЕ,КОМБИНИРОВАННЫЕ АЛГОРИТМЫ, ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ, ПИШЕНЕНИЯ

Специальность: 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

дереартации на соискание ученой степени доктора технических наук

Москва - 1990 г.

Работа выполнена в Вычислительном центре АН СССР.

Официальные оппоненты: доктор технических наук, профессор В.Н.Бурков доктор физико-математических наук В.И.Цурков доктор физико-математических наук, профессор В.В.Шкурба

Ведущая организация - Ордена Ленина Институт кибернетики АН УССР имени В.М.Глушкова.

Защита состоится " 1990 г. в че

на заседании Специализированного Совета Д 002.32.04 при Вычислительном центре АН СССР (117967, Москва, ул.Вавилова, 40).

С диссертацией можно ознакомиться в библиотеке Вычислитеш ного центра АН СССР.

Автореферат разослан »1990 г.

Ученый секретарь Специализированного Совета,

доктор физико-математических наук

А.А.Белолипецгай

/¡.;1:кш Отдел сертаций

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Дискретные оптимизационные модели широко 1рименяются при решении задач, возникающих в экономике, технике, /правлении и других областях. Разработка методов решения задач декретной оптимизации началась в конце 50-х и начале 60-х годов 1 интенсивно ведется в настоящее время. В последнее время в разработке алгоритмов решения задач дискретной оптимизации акценты зущесгвенно сместились на разработку программных средств, направленных на решение прикладных задач. Отметим, что основополагаю-цими в дискретной оптимизации являются работы В.С.Михалевича, О.Сергиенко, Н.З.Шора, Ю.И.Журавлева, В.К.Леонтьева, В.ПЛере-тана, В.Р.Хачатурова, Д.А.Супруненко, В.А. Емеличева, В.С.Танаева, З.В.Шкурбы, В.И.Буркова, Р.Гомори, Н.Кристофидеса, Э.Балаша, Р.М.Карпа, М.Хелда, А.Ленд, А.Дойг и ряда других советских и зарубежных авторов.

Среди дискретных оптимизационных моделей важное место зани-лают модели для задач типа коммивояжера. Задачи типа коммивояжера встречаются во многих прикладных задачах, среди которых можно этметить следующие: упорядочения, классификации, ранжирования, расписания, радиотехники, очередности ввода объектов при освоении территории и т.д. Большинство встречающихся в приложениях задач сарактеризуются большой размерностью. Поэтому разработка алгоритмов, допускающих их эффективную реализацию на ЭВМ для задач больной размерности, важна и актуальна.

Применение дискретных оптимизационных моделей для решения 1рикладных задач предполагает использование программных средств. 1ля многих моделей (общего типа) разработаны общедоступные программные средства, которые успешно применяются. Решение задач шециального типа связано с разработкой программного обеспечения, эриентированного. на эти задачи.

В то же время известно, что при реальном, применении разра-5отанных средств для решения задач дискретной оптимизации возни-<ают большие вычислительные трудности. Предложены некоторые из возможных подходов для преодоления вычислительных трудностей, :реди этих подходов отметим следующие: переход от поиска точных решений к поиску приближенных; применение комбинированных алгорит-

- г -

мов различных типов; применение диалоговых процедур; комбинирова ние указанных выше подходов; применение многопроцессорных ЭВМ и другие.

Ограниченность возможностей каждого из методов (точных или приближенных) решения задач дискретной оптимизации (особенно бол шой размерности) естественным образом приводит к идее разработки комбинированных алгоритмов, в которых объединялись бы преимущест ва методов и, по возможности, отсутствовали бы их недостатки. По комбинированными понимаются переметризованные алгоритмы, управля щие параметры которых определяются в процессе решения задачи. Ко бинированный алгоритм решения конкретной задачи формируется в пр цессе решения этой задачи; в этом принципиальное отличие комбини рованного алгоритма от алгоритмов, применявшихся ранее.

Глубокое общетеоретическое исследование комбинированных эвристических алгоритмов выполнено Ю.И.Журавлевым. Необходимость разработки комбинированных алгоритмов для решения задач теоретической и прикладной кибернетики впервые отмечена А.А.Ляпуновым. Применительно к задачам оптимизации (доя функций многих переменных) этот подход предложен Н.Н.Моисеевым.

В диссертационной работе рассматриваются дискретные задачи большой размерности типа коммивояжера, для решения которых приме няются разработанные комбинированные алгоритмы различных типов. Разработанные подходы могут применяться для решения различных классов задач дискретной оптимизации. Актуальность темы определяется необходимостью решения широкого класса прикладных задач, сводящихся к задачам типа коммивоядера.

Цель и задача исследования. Целью работы является разработка дискретных математических моделей и комбинированных алгоритмов для решения задач дискретной оптимизации типа задачи коммивояжера и их применение для решения широкого класса прикладных задач указанного типа, характеризующихся большой размерностью.

Метод исследования. Для исследования применяются комбинатор ные методы решения задач дискретной оптимизации, комбинированные алгоритмы различных типов, моделирование прикладных задач типа коммивояжера.

- з -

Научная новизна результатов.

1. Предложена общая схема разработки комбинированных алгорит-юв ветвей и границ для решения задач дискретной оптимизации. Вычлени основные управляющие параметры комбинированных алгоритмов

[ сформулированы .эвристические правила определения значений зтих гараметров. Схема реализована для задачи коммивояжера и применяйся для решения задач большой размерности в декомпозиционном гадходе.

2. Предложен подход, позволяющий в процессе решения задач искретнрй оптимизации определить наилучшую последовательность лгоритмов приближенного решения этих задач из заданного списка лгоритмов их решения при известном начальном приближении. Ука-ана область применения разработанного подхода, описана его еализация для задачи коммивояжера на плоскости.

3. Предложена единообразная схема организации информации дереве подзадач для алгоритмов с древовидной схемой поиска

ешения задач дискретной оптимизации. Выделены основные группы нформации, описаны операции, выполняемые на дереве в процессе оиска решения. Предлокенная схема применяется в работе при рвении всех задач с древовидной схемой поиска решения.

4. Предложен декомпозиционный подход для приближенного реше-ш задачи коммивояжера большой размерности. На основании этого эдхода разработаны две системы комбинированных алгоритмов:

оя решения симметрических задач и задач на плоскости. Системы заменялись для определения последовательности обхода точек на зчатных платах. Выделен класс задач дискретной оптимизации, 1я которых может быть применен предложенный подход.

5. Приводятся постановки, разработы и реализованы алгоритмы зшения следующих прикладных задач дискретной оптимизации: опреде-зние радиуса устойчивости в задачах выбора; определение опти-ш>ноЙ очередности обслуживания объектов с учетом замены обору-)вания| поиск на графе ограниченного по длине пути с максимадь-ш весом; выбор оптимального варианта транспортного манипулято-

I на складе; выбор оптимальных параметров развития магистраль->го нефтепровода. Алгоритмы решения первых четырех задач разметаны на основании различных версий комбинированных алгорит->в решения задачи коммивояжера; алгоритм решения последней за-1чи близок к комбинированному алгоритму в идейном откошенш.

6. Разработаны математические модели и алгоритмы решения задач компоновки. На их основании разработана Диалоговая система проектирования схемы генплана (ДИСП СГП).

7. Разработана подсистема для определения очередности ввода скважин в "Системе проектирования генеральных схем проектирован! обустройства нефтяных месторождений на ЭВМ". Построена математическая модель и разработаны алгоритмы решения, основанные на декомпозиционном подходе и комбинированных алгоритмах решения задг чи коммивояжера большой размерности,

8. Эффективность всех разработанных подходов экспериментал! но подтверждена при решении больших серий задач. Основные элеме! ты этих подходов Могут быть применены для решения широких классс задач дискретной оптимизации.

Внедрение. На основе предложенных подходов разработано программное обеспечение доя ЭВМ БЭСМ-6 как для решения отдельных oi тимизационных задач, так и систем автоматизированного проектирования.

Разработанные системы комбинированных алгоритмов для решен задачи коммивояжера большой размерности применялись для определения последовательности обхода точек на печатных платах для Ж АН УССР (г.Киев) и № АН CQCP (г.Москва).

Разработанное программное обеспечение для решения задачи -коммивояжера применялось на предприятии п/я М-5836 (г.Ку#бышев) доя определения машрутов кратчайшей длительности транспортно-складских роботов (TCP). На основе проведенных исследований на предприятии были разработаны и внедрены TCP повышенной произ водительности.

Разработана система для определения очередности ввода скважин на нефтяном месторождении. Система работает как модуль Системы проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ (СПГСО). Система применялась для одного из месторождений на территории Кош АССР по информации института ПечорНИПИнефть. Полученные варианты очередности ввода одобрены специалистами института.

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

'рафики в. рамках научно-исследовательских работ, выполняемых на >цноы из предприятии (г.Калинин) .

Под руководством диссертанта разработана Диалоговая система зроектирования схемы генплана (ДИСП СГП), которая применялась совместно с ЦНИИЙградостроительства (г.Москва) для решения задач функционального зонирования террииорш в районной планировке в зоне влияния Чебоксарской ГЭС. По заключению специалистов система гвляется перспективной и может широко применяться для решения юдобных задач.

Под руководством диссертанта разработан алгоритм для решетя задачи определения оптимальных параметров развития магистраль-юго нефтепровода, программа разработана и применяется в институте ГИПРОТРУБОПРОВОД (г.Москва).

Апробация работы. Результаты, полученные в работе, докладывались на Всесоюзной конференции "Экстремальные задачи и их при-гожения к вопросам планирования, проектирования и управления зложными системами" ( У симпозиум по экстремальным задачам, г.Горький, 1971 г.), Ш Всесоюзной конференции по исследованию зпераций (г.Горький, 1978 г.), Всесоюзной научной конферении 'Декомпозиция и координация в сложных системах" (г.Челябинск, [986 г.), IX Всесоюзном симпозиуме "Системы программного обеспе-1ения решения задач оптимального планирования" (г.Минск, 1986 г.), И Всесоюзной школе "Дискретная оптимизация и компьютеры" (г.Ташкент, 1987 г.), Республиканском семинаре "Методы решения и мате-латическое обеспечение задач дискретной оптимизации" (г.Киев, Ж АН УССР, 1987 г.), семинаре ВЦ АН СССР "Теория управления" [1987 г.), УШ Всесоюзной конференции "Проблемы теоретической сибернетики" (г.Горышй, 1988 г.), У1 Всесоюзной конференции " 'Методы математического программирования и программное обеспе-1ение" (г.Свердловск, 1989 г.), на семинаре "Математическая кибер-1етика" института математики АН БССР (г.Минск, 1989 г.).Результаты работы освещались в циклах лекций по прикладному дискретно-1у программированию, которые читались автором в КМ о ВЦ АН Молдавской ССР (1981 г.), в Горьковском Государственном университете (1981 г.), в Челябинском политехническом институте (1984 г.), 1а летней школе по исследованию операций, организованной в г.Варна 1нститутом математики с вычислительным центром Болгарской Академии наук (1989 г.).

Публикации. По теме диссертации опубликовано 35 работ. Структура работы. Диссертация состоит из введения, 7 глав, заключения, списка литературы, изложенных на 295 страницах, 33 рисунков, 222 наименований литературы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В главе I "Комбинированные алгоритмы в Задачах дискретной оптимизации" приводится описание комбинированных алгоритмов различных типов. Основное внимание уделяется комбинированным алгор] мам типа ветвей и границ. Излагается вычислительная схема формирования комбинированных алгоритмов типа ветвей и границ, описаи основные элементы алгоритмов, приведена их параметризация и цре; ложены эвристические правила определения параметров. Здесь же га сана схема формирования наилучшей последовательности алгоритмов (при ограниченной ее дайне) приближенного решения задачи из заданного списка алгоритмов при известном начальном решении задач! дискретного программирования.

В § 1.1, приводятся общие сведения о комбинированных алгоритмах, показана необходимость их разработки, указано их место среди алгоритмов решения задач дискретной оптимизации. Под комбинированным понимается алгоритм, в котором на различных этапах вычислительного процесса имеется возможность выбора на программном уровне одного из нескольких вариантов для решения исходной задачи или ее подзадач .

В § 1.2 описаны комбинированные варианты алгоритма ветвей и границ дая решения задачи дискретной оптимизации:

{(Х°) = гп1л.^сл), Х&&, / (I)

Под методом ветвей и границ понимается любой метод последователе ного разбиения множества допустимых решений на подмножества, имеющий древовидную структуру поиска и использующий в процессе поиска результаты решения оценочных задач на подмножествах.

В п.1.2.1 описаны основные элементы комбинированных алгоритмов типа ветвей и границ. Приведем эти элементы: выбор множес ва для ветвления; выбор способа ветвления; выбор алгоритма вы-

шсления нижних оценок; выбор алгоритма формирования приближении решений в процессе ветвления; изменение точности в процессе решения задачи; правила отсева.

Среди правил выбора множества для ветвления наиболее часто «¡пользуются: ветвление по наименьшей нижней оценке среди всех ¡адач; ветвление по наименьшей нижней оценке среди задач, пост-зованных на данном шаге; ветвление в зависимости от разности зна-1ений оценок, указанных выше; ветвление в зависимости от порядка >бразования подзадач;, одностороннее ветвление; комбинация правил шбора.

Способ ветвления, как правило, фиксирован, он не меняется i процессе решения задачи; наиболее часто используется дихотоми-гаское ветвление.

Предполагается, что известен список Р~ \Pi> Рг>-- •> Ре)

1лгоритмов вычисления нижних оценок di (i , £) >

[ри этом дая одного и того же подмножества d'f ^ d'z i- - ^ •

1 процессе решения возможен переход от алгоритма р^ к алгоритму ps-n

Предполагается также, что известен список алгоритмов

2 - { ^/> ^г, — * ^ % } для формирования приближенных решений в

[роцессе ветвления, алгоритмы перенумерованы в порядке улучшения ;аваемых ими значений, целевой функции. В процессе решения возможен :ереход от алгоритма ^ к алгоритму

Точность, с которой решается задача, может изменяться в

роцессе ее решения, ^ .

При формировании правил отсева вместе с правилами отсева -отсева) метода ветвей и границ могут использоваться прави-а отсева, использующие специфику задачи.

В п.1.2.2 описана параметризация комбинированного алгорит-а в соответствии с его элементами, описанными в п.1.2.1. На are ветвления с номером К вводятся следующие параметры:

- точность, с которой решается задача, ^ ■■•

О _ параметр, определяющий правило выбора множества для ветвления;

[О - отсев с учетом специфики задачи не производится} ~ [I - отсев с учетом специфики задачи производится;

ГО - приближенные решения в процессе ветвления не строятся! к \1 - приближенные решения в процессе ветвления строятся;

рк е.Р - номер алгоритма дал вычисления нижних оценок;

Ь

&0. - номер алгоритма формирования приближенных решений в процессе ветвления;

1 - ресурсы ЭВМ, выделенные для решения задачи (время, память).

Задание значений этих параметров на каждом шаге процесса ветвления полностью определяет комбинированный алгоритм решения задачи, . . , # я .

А - А(£*> ак,*к> Р*> ^х > ч).

Стратегиейрёшения задачи будем называть правило выбора значений I раметров с учетом ресурсов ЭВМ. С формальной точки зрения можно поставить•задачу о таком выборе значений параметров, при котором за заданное число ветвлений достигается наибольшая точность или заданная точность достигается за минимальное число ветвлений. Решение этой задачи может оказаться более трудным, чем решение исходной задачи.

В п.1.2.3 описаны эвристические правила дня определения зна чений этих параметров в зависимости, от ресурсов ЭВМ. Стратегия их выбора может быть реализована: путем априорного задания; путе: выбора на программном уровне; выбора в режиме диалога; комбинаци ей описанных выше способов.

Для выбора значений управляющих параметров каждой стратегии ставится в соответствие оценка ее качества, эта оценка в каждом случае определяется конкретно. В качестве примеров таких оценок можно привести следующие: число ветвлений, машинное время, полученная точность и т.д. Очередной акт выбора значений'параметров реализуется, если в процессе решения число ветвлений превосходит заданное ограничение, не достигнута заданная точность и т.д. Стратегия основана на эвристических правилах и направлена на усиление отсева. Эти правила предполагают снижение точности реше ния задачи, переход к алгоритмам вычисления оценок и формировали приближенных решений в процессе ветвления с большими номерами в

списках Р и (3. (в соответствии с введенным упорядочением алгоритмов), учет специфики задачи при отсеве. Далее обсуждается конкретная реализация процедуры выбора параметров комбинированного алгоритма.

В § 1.3 описана схема взаимодействия алгоритма динамического программирования с алгоритмом ветвей и границ.

В § 1.5 обсуждаются некоторые вопросы формирования комбинированных алгоритмов и их информационной согласованности.

В § 1.6 описан подход, позволяющий определить последовательность работы приближенных алгоритмов в комбинаторном алгоритме решения задачи (I). Пусть ,А = {0/> } - множество алго-

ритмов локальной оптимизации для решения этой задачи, <-£*<£ <5 -начальное приближение. Обозначим через (2^ (Л) результат примене-аия алгоритма а. е /I в точке X е & . Каждой последовательности алгоритмов

ставится в соответствие последовательность точек л'..., <£ 13 множества . & :

л'-а^Лх*;, с**'').

Множество последовательностей указанного вида обозначим П . Саадой последовательности ЗГ<а П и начальной точке £ поста-5им в соответствие значение' ГСТГ, Я ) • Ставится

¡адача определения такой последовательности ТС0 & Л > что

л*) ~ тьп/ Гл*), SFe.fl. )та задача является задачей дискретной оптимизации на множестве юследовательностей -П ; если П - множество всех пересгано-юк Р алгоритмов из А , то эта задача является аналогом откры-:ой (незамкнутой) задачи коммивояжера с неизвестной матрицей рас-¡тояний. Поэтому алгоритмы, основанные на идеях оценивания и доми-шрования, не применимы к ее решению.

Для решения поставленной задачи предлагается комбинаторный иггориты перебора последовательностей из П на специальным >бразом построенном дереве алгоритмов.

Основная идея, позволяющая избежать полного перебора всех юследовательностей, состоит в следующем. При очередном приме-[ешш алгоритма а- в точке х £. & проверяется, было ли

такое применение на построенной части дерева алгоритмов. Результат проверки сводится к проверке выполнения условия & = Ц. для двух точек л,у из в- , полученных в результате применеЕ алгоритмов из А к точкам из От . Если указанное применение было, то результат 0.-с (¿с') фиксируется без выполнения алгоритма , что и позволяет избежать полного перебора. На основании этой идеи сформулированы правила сокращения и отсева.

Правило отсева. Пусть решение <£ получено г результате работы алгоритма ^ . Если для всех <*к \ имеет

место X то поддерево применения алгоритмов с началь-'

ной вершиной, соответствующей решен*® х , должно быть отсеянс т.е. исключено из дальнейшего рассмотрения.

Правило сокращения. Пусть последовательность алгоритмов

а. , ( а.1(г. ^ = О, I применялась

к решению X, . Тогда следующий в последовательности алгоритм

л- . не применяется, если последовательность ,

а- а. применялась к решению ■Х хотя бы

один раз. "

Предложенный подход применим к полностью целочисленным задачам дискретной оптимизации. Его целесообразно применять к тем задачам, для которых трудоемкость указанной проверки ниже трудоемкости очередного применения Сек).

В гл.1У описано применение разработанного подхода к задаче коммивояжера на плоскости.

В § 1.7 дано описание вычислительной реализации алгоритме* с древовидной схемой поиска решения. Для описания этой ^..чализа-ции выделены следующие группы информации: информация о структуре дерева; указатели и ссылки; информация о множествах, полученных в процессе разбиения (ветвления); значения функций в вершинах дерева вариантов. Выделены операции на дереве, применяемые при работе с ним: просмотр дерева; наращивание дерева; чистка дерев£ поиск путей на дереве. Разработанная схема организации информации о дереве и операции на нем применяются при решении всех заде из глав П, Ш, 1У с древовидной схемой поиска решения В § 1.8 приведены основные результата главы I.

В главе П "Комбинированные алгоритмы ветвей и границ для решения задачи коммивояжера" предложенный в первой главе подход применяется к решению задачи коммивояжера.

В § 2.1 дана постановка задачи коммивояжера в точной и £ - постановках и приведет основные элементы комбинированного алгоритма. Пусть' Р = Ii2,..., а} - конечное множество точек,

С = (c--)t Р, Р - матрица расстояний, CL ■ ? О ,

V . '

£ - (i ьг ■■-1 <- п) - произвольная перестановка п, точек

( I, 2, ..., ть ), именуемая в дальнейшем маршрутом обхода точек п

длина маршрута в замкнутой задаче и

его длина в незамкнутой задаче, 2;0 - множество всех возможных маршрутов. В этой главе рассматривается замкнутая задача. Ставится задача о поиске маршрута Ле е. jLe , такбго, что

= rn-uv I (Я), .

Рассматривается также £. -постановка задачи: найти маршрут

2+ <=. , такой, что

"" .Ц2.)-1(ъ) 4€t euj>0, его.

С ( )

Основные элементы разработанного подхода следующие: построение алгоритмов.приближенного решения задачи до начала процесса зетвления; параметризация комбинированного алгоритма; выбор уп-завляшщих параметров.

В § 2.2 описаны алгоритм решения задачи, схема перебора и-церево вариантов. Алгоритм ветвей и границ для решения задачи эснован на следующих построениях: вычисление оценок, ветвление, 1ересчет оценок, нахождение приближенных решений, признак опти-лальности, оценка точности приближенных решений, правила отсева [или € -отсева).

Схема перебора вариантов является традиционной для метода зетвей и границ. Неформально эта схема может быть описана следую-

щкм образом: из первой точки, принимаемой в качестве начальной, рассматриваются все переходы, для полученных подмножеств вычисляются нижние оценки; в дальнейшем берется подмножество с наименьшей оценкой и для него строятся все переходы и т.д. Такая схема требует большой памяти, поэтому рассматривается следующая модификация. Пусть 2), <, 2/пк - неотсеянные множества, хранящиеся на шаге к в памяти ЭВМ и си ( ), I = /, 2,..., тк - их

нижние оценки, и)( Л;.) = т-ш а) . Множество.^ разбивается

-у 4 Ьк 4 I

на подмножества л.■ , 4 = /.Ък . и = .

Ч > 7 ' ' 4'У Ч /■>

Пусть ос = юЛл; -р-<*п*гг, ш (£• ) .

* . » ' Рассмотрим три случая:

а) $ ^ <ь , в этом случае для ветвления выбирается множеств! соответствующее оценке / ;

б) р * и , , (Г 5 0 .- заданный параметр, в этом случае также выбирается множество, соответствующее оценке ]5> •

в) ^ ^ , р- , для ветвления выбирается множест-. во, соответствующее оценке .

При больших значениях 8" выбор всегда производится-среди множеств, построенных на данном шаге, § * О соответствует ветв' лению по наименьшей нижней оценке, промежуточные значения соотве ствуют комбинации этих выборов.

Каждому множеству соответствует вершина на дереве вариантов начальная вершина соответствует исходной задаче. Для каждой из вершин уровня К указаны связанные с ней вершины уровня к-<--/.

В § 2.3 описаны алгоритмы нахождения приближенных решений до начала процесса ветвления: переход в ближайшую точку и локал нал оптимизация (алгоритм 2.3.1)} разбиение маршрута на группы, формирование задачи коммивояжера для групп и оптимизация по груп пам (алгоритмы 2.3.2 и 2.3.4); полный перебор заданного числа всех подряд расположенных точек маршрута (алгоритм 2.3.3); сшивание подциклов решения задачи о назначении (алгоритм 2.3.6); построение многоугольника для симметричных задач с правилом треугольника (алгоритм 2.3.5).

В § 2.4 описаны алгоритмы нахождения приближенных решений " в процессе ветвления: переход в ближайшую точку (алгоритм 2.4.1

ветвления "вправо" .по схеме ветвей и границ (алгоритм 2.4.2); многоугольника для симметричных задач с правилом треугольника (алгоритм 2.4.3).

В § 2.5 описаны алгоритмы: вычисления нижних оценок: приведения (алгоритм 2.5.1); решения задачи, о назначении (алгоритм 2.5.2); построение кратчайшей связывающей сети для.симметричных задач (алгоритм 2.5.3).

В § 2.6 описан алгоритм генерации лексикографически упорядоченных перестановок и его применение для нахождения приближенных решений. Этот алгоритм позволяет по номеру перестановки

1 ^ х £ п ! восстановить перестановку ^(л). При лексикографическом упорядочении перестановок перестановка п имеет

номер I, а перестановка Л, П-/,имеет номер «Х-Л'У. Для построения перестановки К^) по ее номеру ¿С используется разложение ОС. в сумму факториалов, перестановка восстанавливается однозначно по коэффициентам этого разложения. Разработанный алгоритм применяется в алгоритме 2.3.3.

В § 2.7 описан комбинированный алгоритм решения задачи коммивояжера, разработанный на основании подхода из главы I. Основные элементы алгоритма такие же, как описанные в главе I, отметим лишь, что отсев с учетом специфики задачи предполагает отсев по доминированию (как в методе динамического программирования). Список Р алгоритмов вычисления нижних оценок состоит из алгоритмов 2.5.1, 2.5.2 и 2.5.3 в указанном порядке. Список О. алгоритмов формирования приближенных решений в процессе ветвления состоит из алгоритмов 2.4.1, 2.4.2.и 2.4.3 в указанном порядке.

Параметризация алгоритма выполняется по общей схеме, под ресурсами ЭВМ понимается массив памяти длины 1 , выделенный для хранения одновременно запоминаемых подзадач, получаемых при ветвлении.

Выбор управляющих параметров производится в соответствии с правилами, описанными в главе I. Очередной акт выбора реализуется, если не хватает места для записи информации об очередной группе подзадач, полученных при ветвлении.

Приведем конкретизацию правил выбора параметров для задачи коммивояжера.

а) по гистограмме распределения значений нижних оценок на отрезке Мглах! Для неотсеянных подзадач и наилучшему

из приближенных решений на шаге К определяется

где 4 - есть первое из значений П^. 1-, пг -2,.. ,2 , при котором запись информации об •очередной группе подзадач возможна. Задача решается с этим значением ;

в) если запись снова невозможна, то определяется новое значение и переходим к следующему алгоритму вычисления

нижних оценок;,

с) если реализация шагов а и £ снова приводят к невозможности записи, то реализуем снова шаги от и £ и вводим первый из алгоритмов списка О для формирования приближенных решен в процессе ветвления, или вводим следующий из них;

<1) если шаги а , ё , с снова привели к невозможности зал си, то реализуем эти шаги снова и вводим отсев по доминированию.

На каждом шаге процесса, на котором запись оказалась невозможной, вводятся все операции предыдущего шага и одна новая. Воз можносш шагов а, /, с могут быстро исчерпаться, но шаг а. позволит получить решение с той точностью, которая возможна при заданных ресурсах Z .

В § 2.8 рассмотрены вопросы, связанные с вычислительной реализацией описанного выше подхода. На основании § 1,7 предложе на схема организации информации о дереве подзадач и описан порядок работы с этой информацией.

В § 2.9 приведены результаты решения известных тестовых задач, опубликованных в литературе для л- = 20 (2 задачи), 25, 42, 48. Для первых четырех получены точные решения, для п а 48 решение, близкое к точному. Сформулированы основные выводы по этой главе.

В главе Ш "Декомпозиционный алгоритм решения симметричной задачи коммивояжера большой размерности" излагается декомпозиционный подход, позволяющий свести решение симметричной задачи к решению последовательности задач существенно меньшей размерное и сформировать решение исходной задачи из решения подзадач.

В § 3.1 дано уточнение постановки задачи из главы П для рассматриваемого здесь случая: C¿j = Cj¿ и приведены общие сведения об алгоритме. Алгоритм состоит из следующих, основных элементов: формирования приближенного решения до начала разбиения; последовательное разбиение множества Р на подмножества; формирование дерева подзадач коммивояжера; решение задач коммивояжера на подмножествах; формирование решения задачи из решения подзадач на всех уровнях разбиения.

Существенным элементом разработанного подхода является работа в режиме диалога.

В § 3.2. рассматривается задача о разбиении конечного множества точек Р на непересекающиеся подмножества. Приведем постановку задачи. к

В,s-'р-

Каждому разбиению Ss (, SK)можно поставить в соответствие значение функции ¥(Sf> $а >••'•> , характеризующей качество разбиения. Необходимо найти разбиение

3° - (Szf's ^к) г при котором f( S ) принимает минимальное значение: ,Л/„в1 . ,/> , е \ Y(S ) - гпкти Y(S).

' S

1редполагается, что к

ns) =

где $ ( есть значения функции близости точек, принадлежащих эдному подмножеству. В работе рассмотрено несколько таких функций, в которых точки группируются либо по минимуму расстояния, ибо так, чтобы минимизировать максимальное расстояние между точками в каждом из подмножеств.

Алгоритм приближенного решения задачи о разбиении (задачи кластеризации) основан на построении начальных значений подмножеств Sf, Sir- •> 3н , при котором в каждом из них оказываются зве точки, и отнесении всех оставшихся точек к этим подмножествам в соответствии с выбранной функцией близости точек для одного подмножества. При этом может оказаться, что для некоторых под-

множеств 15; / ^ /' ^т^п' , Для этих подмножеств снова применяется описанный выше алгоритм разбиения.

В результате применения такого подхода формируется дерево подзадач, концевые его подмножества удовлетворяют условию

^т^гу - I I ^ ?' '

В § 3.3 описан алгоритм решения задачи коммивояжера в соответствии с основными его элементами.

При формировании приближенного решения до начала процесса разбиения применяются алгоритмы локальной оптимизации. Эти же алгоритмы применяются для решения задач коммивояжера на подмножествах точек.

Процесс формирования решения задачи из решения подзадач начинается с максимального уровня -6тах на дереве подзадач. Решение конкретной подзадачи на уровне 4гпа*~ ^ формируется из "подвеше: ных" к ней подзадач уровня Циклы на уровне. 6тах объедини

ются в последовательности, определяемой полной перестановкой заданного числа подряд расположенных циклов. К полученному маршрут применяются алгоритмы локальной оптимизации. Затем процедура повторяется для формирования решения подзадач уровня - И. и из "подвешенных" подзадач уровня " I и т.д.

Бри оценке точности получаемых приближенных решений задачи и подзадач строятся кратчайшие связывающие сети, С(20)^ I(■£,

<?0 - длина кратчайшей сети. Известно, что точность комбинировав ного алгоритма не ниже точности алгоритмов, из которых он формируется.

В § 3.4 описаны дерево подзадач, его структура, информация о подзадачах и операции на дереве применительно к рассмотренной в этой главе задаче. Описание разработано на основании общей схемы, изложенной в § 1.7.

В § 3.5 описан процесс решения задачи, приведены результата эксперимента и сформулированы некоторые выводы.

Отмечены основные элементы режима диалога: задание начального решения, начального разбиения, изменение последовательности работы алгоритмов локальной оптимизации в процессе работы, и: менение правила формирования и "мощности" окрестности в этих алгоритмах, продолжение или прекращение решения в зависимости от полученных результатов и затраченных ресурсов ЭВМ и т.д.

В качестве тестовых"решались задачи с !Ь- = 48,57,74,100, 105,318 с известными опубликованными решениями: задача с П = 179 сформирована из двух задач с Л к 74. и ти = 105; задача с rv - 279 сформирована из трех задач 1г = 74, 72-= 100 и 72= 105.

Во всех задачах (кроме /1= 57) получены решения не хуже опубликованных или близкие к опубликованным ко времени выполнения эксперимента, для 1Ь = 74, 100, 318 они оказались лучше опубликованных.

В главе 17 "Алгоритмы решения задачи комиивояжера большой размерности на плоскости" излагается подход, основанный на декомпозиции и агрегировании.

В § 4.1 приводится постановка задачи и излагаются общие сведения об алгоритмах. Значения C¿• определяются координатами

<7

> У-i ) и ( ^у > Vj ) точек на плоскости, для выполнены аксиомы расстояния. Основные элементы предлагаемого подхода следующие: последовательное разбиение множества точек на подмножества, агрегирование подмножеств и формирование задач коммивояжера для подмножеств и их агрегатов, для агрегатов можно снова применить процедуру разбиения; приближенное решение задач коммивояжера для подмножеств и их -агрегатов на всех уровнях разбиения; формирование решения задач коммивояжера из решения подзадач на всех уровнях разбиения; устранения пересечений переходов в полученных приближенных решениях для подмножеств и агрегатов на всех уровнях разбиения (корректировка решения).

Существенным элементом разрабатываемого подхода является работа в режиме диалога.

В § 4.2 рассматривается задача о разбиении и приводятся краткие сведения об алгоритмах ее решения. Пусть течки множества Р находятся в прямоугольнике:

^nr^v £ х * ^тал , ^min, ^ У ^ ¡¿мал >

где = т^ x.j, &тасс,- = таге Jy, *

у тал ~ . Для разбиения применяются сетки с равно

и неравноотстоящими узлами по осям координат, множество прямоугольников со сторонами, параллельными осям координат, разрезание множества точек на полосы заданной ширины и набор точек в полосе по возрастанию значений абсцисс.

Каждому из полученных при разбиении подмножеств ставится в соответствие его точка - агрегат (представитель), для агрегатов можно снова применить процедуру разбиения и агрегирования и т.д. В результате многократного применения процедуры разбиения и агрегирования получается многоуровневая система задач коммивояжера, на каждом уровне системы сформированы множества точек, их разбиение на подмножества, агрегаты подмножеств и задачи коммивояжера для подмножеств и их агрегатов. Если на уровне к &/ множество -.г*/.-л/; , пш

г (Р = Р) разбито на Л„ подмножеств Р Я ,

р<и Р1"> о<">по"> л /• • 'Л .

то в качестве точки-агрегата точек множества Р^к> можно взять, например, его "центр тяжести".

Если П ■> ^гп^ъ, » гДе ^-¿л- ~ заданный параметр, то к

агрегатам применяется процедура разбиения и агрегирования и т.д.

В § 4.3 описан алгоритм решения задачи коммивояжера. Для решения подзадач коммивояжера и задач для агрегатов применяются алгоритмы локальной оптимизации, для формирования начального марш рута применяется выпуклая оболочка.

Формирование решения зада*ш из решения подзадач на уровне

разбиения к'? / состоит в следующем. Пусть Щ ^ Р Р^ -

подзадачи, полученные на максимальном уровне разбиения Г ? У ,

Ч , Г 'п± -их агрегаты, Т- к ? у. ' ).

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

та) ю „(^

у '6 '4Л ~ Решение Для агрегатов и

I 1 ■!■••> К -маршруты, соответствующие решениям

задач для подмножеств. Каждая из точек-агрегатов заменяется маршрутом по множеству, которая она представляет, решения для подмножеств сшиваются в последовательности, определяемой решением задачи для агрегатов. К полученному после сшивания маршруту могут применяться алгоритмы локальной оптимизации. Если t -V , то формирование окончено, если í , то полагаем t равным £-У и продолжаем процесс.

Смысл описанного подхода состоит в том, что при группировании точек по геометрической близости выполняется оптимизация по агрегатам множеств. Вместо определения последовательности точек определяется последовательность агрегатов их подмножеств, полученных при разбиении; вторая задача имеет существенно меньшую размерность.

При устранении пересечений необходимо найти все пары переходов, точка пересечения которых является внутренней для каждого из переходов этой пары. Точка пересечения можут быть внутренней в том и только в том случае, если пересекаются проекции этих переходов на каждую из координатных осей. Если пересекаются проекции на каждую из сетей координат, то находим точку пересечения переходов и, если она является внутренней для обоих переходов, устраняем пересечение. Один просмотр маршрута требует (п-г)(П-3) /Z применений процедуры определения пересечения, все пересечения устраняются за конечное число просмотров маршрута.

Получена оценка трудоемкости процедуры объединения под-циклов в один с помощью алгоритмов сшивания подциклов. Показано, что трудоемкость максимальна, если число точек в каждом из подмножеств равно 1р/к , при этом количество вычисляемых значений Соценивается как '/к) .

При построении начального маршрута для каждого из подмножеств точек строится выпуклая оборочка, исподьзуемая в качестве начального многоугольника в алгоритме многоугольника. Строится также система "вложенных" выпуклых оболочек, которые объединяются в один маршрут по алгоритмам сшивания подциклов. Выпуклая оболочка используется для вычислений нижней оценки, которая необходима для определения границы отклонения полученного приближенного решения от оптимального.

Элементы диалога, применяемые при решении задач, описаны при изложении содержания главы Ш.

В § 4.4 описаны результаты вычислительного эксперимента при решении задач с Л = 318,532,1010,1620 и сформулированы основные выводы. Задача для 318 точек - известная тестовая задача, для 532 точек - задача о городах на карте СМ, задачи для 1010 и 1620 - задачи о поиске маршрута на печатных платах, первая

из них поставлена в ИФП АН СССР, вторая - в ИК АН УССР. Результат! решения задач на ЭВМ БЭСМ-6 приведены в таблице, в первой строке -

п - размерность} во второй С0 - дня первых двух задач -опубликованные дайны маршрутов, для третьей и четвертой.-результаты ®П АН СССР и ИК АН УСССР в прямоугольной метрике; в третьей 1А - полученные нами результаты (в той же метрике), в четвертой - время 6 в минутах.

Таблвда

' п 318 532 1010 1620

4 420,29 27686 18798 6338

433,57 27715 16?34 6158

ь 30 60 150 300

Далее сформулированы основные выводы по применению разработанного подхода для решения задач большой размерности на плоскости.

В § 4.5 описано применение предложенного в главе I подхода о формировании наилучшей последовательности алгоритмов для задачи коммивояжера ца плоскости.

Здесь конкретизируется постановка задачи о выборе наилучшей последовательности для задачи комиивояжера, излагается схема построения дерева.применения алгоритмов.

В вычислительном эксперименте- список алгоритмов А состоит из следующих алгоритмов: ОТ/ - оптимизация по всем парам точек;

оптимизация по всем перестановкам заданного числа подряд рас положенных точек; О^ - оптимизация по всем вставкам фрагментов длины,изменяющейся от до ¿тах •

Для формирования начального маршрута строились выпуклые оболочки, которые использовались в качестве начальных многоугольни-К9В в алгоритме многоугольника. Решались задачи для /I = 74,100, 105, душна последовательности алгоритмов ограничена числом 4.

Из 46 вершин дерева применения алгоритмов отсеяно соответственно 37, 28 и 30 вершин. Для каждой из решенных задач получена оптимальная последовательность алгоритмов при следующих предположениях: зафиксирован список А , длина последовательности ограничена и указан способ формирования начального маршрута; при этих предположениях длины маршрута уменьшена быть не может. Зависимость результата от начального приближения может быть преодолена увеличением длина последовательности или расширением списка А. Изменение начального приближения может, вообще говоря, улучшить результат при том же списке А и длине последовательности.

В главе У "Дискретные оптимизационные задачи": модели, алгоритмы, применение, эксперимент" описано применение разработанных подходов к решению трех задач-дискретной оптимизации: нахождение радиуса устойчивости в задачах выбора; определение оптимальной последовательности обслуживания объектов с учетом замены оборудования; нахождение на графе ограниченного по длине пути с максимальным весом. Для этих задач сформированы математические модели; для решения применяются рассмотренные в предыдущих главах варианты комбинированных алгоритмов (или близкие к ним). Приводятся результаты вычислительных экспериментов, указаны области применения моделей. Базовой для рассматриваемых в этой главе задач является задачи коммивояжера.

В § 5.1 описаны вычислительные алгоритмы для нахождения радиуса устойчивости в траектории/ задачах выбора.' Понятие радиуса устойчивости в задачах дискретной оптимизации -введено В.К.Леонтьевым. Радиус устойчивости является инвариантом, который со раняется при небольших возмущениях матрицы расстояний, поэтому он может быть использован для решения задач в том или ином смысле близких к исходной.

Рассмотрены следующие траекторные задачи: линейная задача коммивояжера и задачи коммивояжера и назначения на узкие места. Для определения радиуса устойчивости в линейной задаче коммивояжера модифицирован один из вариантов алгоритма ветвей и границ из главы П.

Вычислительный эксперимент проводился для задач П - 10,15, 20,25,30,40 с известными и случайно генерированными матрицами с равномерно распределенными независимыми случайными величинами на [0,1000]. Результаты эксперимента показали, что трудоемкость ал-

горитма вычисления радиуса устойчивости сравнима с трудоемкостью решения задачи коммивояжера.

Для задачи коммивояжера на узкие места показано, что он может быть вычислен по той же схеме, что и в линейной задаче коммивояжера. Предложен также алгоритм для задачи о назначении на узкие места.

Основной вывод по рассмотренным задачам состоит в следующем: трудоемкость определения радиуса устойсивости сравнима с трудоемкостью алгоритма решения задачи.

В § 5.3 рассмотрена задача определения оптимальной очередности обслуживания объектов с учетом замены оборудования. Постановка задачи состоит в следующем. Пусть <1-0(2,...,/г}- множество объектов, С- затраты на транспортировку оборудования, Н -ресурс оборудования (предполагается, что после его израсходования требуется восстановление), Ъ^ (] <£ J ) - затраты на транспортировку оборудования от объекта до базы производственного обслуживания и на восстановление израсходованного ресурса; ¡1- (с е 3)-затраты ресурса оборудования при обслуживании объекта I .

Обозначим через х- - ( ¿о 1ц, •••, Ьщ) - упорядоченное мно-. жество объектов из J , X - множество всех возможных вариантов, ^[х) - множество объектов из X , от которых оборудование наярг ляется на восстановление; это множество,-легко определяется для любой последовательности зс , Для ¿с е X определим:

пч

м+гм, ш) =. Ц . = Ь

6-о ¿еЦлГ

Здесь г (л) - суммарные затраты, затраты на транспортиров-

ку оборудования, Z (X)- затраты на транспортировку и восстановление ресурса.

Задача заключается в определении такого Хв & X , что = т<ги Мл),

Для решения задачи предлагается два подхода: использование комбинированного алгоритма ветвей и границ для задачи коммивояжер« из главы П и аппроксимационно-комбинаторного метода В.Р.Хачатуровг

В первом алгоритме модифицируются алгоритмы из главы П для вычисления нижних оценок и формирования приближенных решений в соответствии со спецификой рассматриваемой задачи, общая схема остается без изменения.

. Во втором алгоритме в качестве аппроксимирующей задачи берется задача коммивояжера с целевой функцией ¿ (^)и решается

задача отыскания , , ~ ■ , , , V

__ ' и (Л. )0 ас е X

и множества X всех х. , удовлетворяющих условию

I* (X.,) < Ь (х) £ где X - приближенное решение исходной задачи, затем находим

х.еХ , такое, что . 7

Р (лв ) = Ъп-т> Р(сс), ¿се Л.

Решались задачи с 20 £ п. ^ 50. Время их решения несущественно отличается от времени решения соответствующей задачи коммивояжера.

В § 5.3 рассматривается алгоритм типа ветвей и границ решения задачи о поиске на графе ограниченного по длине пути с максимальным весом. Задача ставится следующим образом. Пусть

Р~ (//2,, п }. - конечное множество точек, Сг ■ 2-0 -

и V

матрица

расстояний, вес, отнесенный точке

Обозначим через -3 ^••'.»£$.)путь, вое ь5 различны,

24 . Определим длину пути ¿СЯ) и его вес 3(г)г.

Путь 2 называется допустимым, виш. Я>0 . Цусть<2 -

множество всех путей и 2«- множество допустимых путей. Ставится задача о нахождении пути такого, что

3(2е) =* тасс. Лг), ге^. Рассматривается также задача поиска допустимого пути 2,£ До такого, что Т(20)- 7(2*) 4 5 О - заданный параметр.

Рассматриваемая здесь задача отличается от задачи коммивояжера, однако один из варианто1 разработанного в главе П комбинированного алгоритма можно применить для ее решения.

Алгоритм решения задачи состоит из следующих основных шагов: построение начального приближения; анализ вариантов; построение допустимого пути для любого ^ сР,

Для нахождения начального приближения.применяются алгоритмы "пожирающего типа", которые позволяют к уже построенному пути добавить один переход.

При построении схемы анализа вариантов предполагается, что для любого с Р можно решить следующую задачу: найти допустимый путь, проходящий через.все точки или показать, что такой путь не существует.

Анализ вариантов предполагает, что на первом шаге строятся все множества °(И- Р\{}» ь^-Р , каждому из них ставится в соответствие верхняя оценка и)и)* • Далее множество Р(¿.),

соответствущее оценке та ос, и) I & р, разбивается аналогичным образом на подмножества Р (¿/;у; » Р.(Л ], ] € Р (ь,) ?

вычисляем оценки

10 (-1,,])= Ок

и Т.д. . '

Схема ветвления 'является вполне традиционной с естественными правилами отсева. Дня каждого из неотсеянных множеств, начиная с множества наибольшей оценкой, решается задача о поиске допустимого пути. Поэтому исходная задача решена, как только найден первый допустимый путь.

Для решения задачи о поиске допустимого пути для любого применяется один из вариантов комЬинированного алгоритма, близкий к рассмотренному в главе П.

Приведены результаты вычислительного эксперимента для различ ных задач с 10, 15 и 20 точками. В качестве начального значения Я брались длины путей, полученные в результате решения задачи о ком мивояжере и уменьшенные на д/шну наибольшего звена в замкнутом решении, затем эти значения, уменьшались пока время решения задачи не становилось чрезмерно большим.

Для значений Я , больших половины начального значения, алгоритм оказался достаточно быстродействующим; при уменьшении (особенно при значениях, меньших половины начального) эффективность алгоритма резко падает: быстро находятся оптимальные или близкие к ним решения, однако доказательство этого требует значительных вычислительных ресурсов.

В качестве примеров прикладных задач, математической моделью которых может быть рассмотренная в данном параграфе задача, рассмотрены две задачи: задача об обработке деталей на одном станке и задача о сборе грузов. Предлагаемый в этом параграфе алгоритм

может применяться в задачах обслуживания объектов с помощью одного ресурса, когда одна из величин, характеризующих качество обслуживания (например, время) ограничена, а вторая (например, прибыль) максимизируется.

В главе У1 "Прикладные задачи: модели, алгоритмы, применения, эксперимент" рассматриваются задачи, которые были поставлены и решены в результате сотрудничества со специалистами из различных предметных областей. С формальной точки зрения эти задачи сформулированы как задачи на перестановках элементов конечного множества. Для этих задач разработаны математические модели, алгоритмы их решения и проведен вычислительный эксперимент. Разработанные алгоритмы близки в идейном отношении к алгоритмам из четырех первых глав.

В § 6.1 описана задача о выборе оптимального варианта транспортных средств при перемещении и складировании продуктов в процессе их производства. Под транспортным средств„м понимается транспортный манипулятор (ТМ) для обслуживания группы рабочих мест. При этом необходимо определить оптимальное количество захватов (или юличество рабочих мест, обслуживаемых в одном цикле) и оптимальный порядок обхода заданных в цикле рабочих мест.

Важнейший параметр ТМ - производительность, поэтому в качестве критерия оптимальности принимается среднее время обслуживания одного рабочего места.

Множество рабочих мест /V изображается узлами прямоугольной решетки на плоскости (X , у ); при наличии пь захватов манипулятор может обслужить П. = 2т рабочих мест (т грузов установить и т грузов снять). Для каждой последовательности узлов

2 - (0, £у, 1/2,..., {//% , О ) | где ( о,0 ) - начальная точка, определяется длительность маршрута п.

'¿„„-О),

о лС/

гд& С- = тал - ¿У), к )} 04 к _ коэффициент

сжатия решетки. Длительность маршрута зависит от порядка обхода П узлов решетки и их числа. Требуется найти зависимость среднего относительного времени поиска одного узла ,а)* Т(2)/п в зависимости от стратегии выбора маршрута и мощности /г множества обслуживаемых узлов при различных значениях параметра К .

С формальной точки зрения решение данной задачи сводится к решению задачи коммивояжера с запретами: запреты возникают в силу специфики задачи. Если, например, в узел ( , у^ ) следует

установить груз,а из узла ( Х^ , ) тем же захватом его снять, то узел <5, не может предшествовать узлу р4 . Эти ограничения реализуются на транспортной сети с помощью условий предпочтения и следования, эти ограничения учитываются при формировании матрицы расстояний для задачи коммивояжера.

Поскольку в ТМ реализация сложных комбинаторных алгоритмов технически затруднена, то. разработаны упрощенные алгоритмы формирования маршрутов. При этом множество узлов разбивается на два неперсекагацихся множества ^ и 5е , Р0 - множество узлов, в которые необходимо установить груз, $0 - множество узлов, из которых необходимо снять груз, сначала совершается обход узлов £ , а затем 30 .

Далее в работе рассмотрены простые стратегии обхода узлов, легко технически реализуемые в ТМ и исследованы точности этих стратегий.

Программное обеспечение для решения этой задачи разработано на основании опубликованной программы решения коммивояжера, реали зущей одну из версий комбинированного алгоритма из главы П; На основе проведенных исследований на предприятии были разработаны и внедрены транспортно-складские работы повышенной производительности.

В § 6.2 описана задача о выборе параметров развития магистрального нефтепровода. При решении этой задачи определяется последовательность ввода НПС (нефтеперекачивающих станций) в динамике. В качестве критерия оптимальности используются приведенные затраты.

Пусть N } _ конечное множество точек для уста-

новки НПС, = , последовательность различных точе

из Р . Элементы последовательности 2М определяют порядок ввода НПС. Каждой последовательности ввода 2М соответствуют приведенные затраты П требуется найти последовательность такую

что

Г112°„) = П ,

H - множество всех последовательностей ввода. Ставится также задача о нахождении последовательности _ такой, что

fr û - заданная точность.

Пуоть Q(t)~ заданная дискретно плановая производительность нефтепровода и пусть уже введены станция с номерами tf) U .

Станция ¿s вводится в эксплуатацию, если

где Q ( ¿1 ¿z , ii ) - максимальная пропускная способность нефтепровода.

Дерево вариантов строится стандартным образом (как и в главе П). При построении схемы анализа вариантов (аналогично главе П) вычисляются нижние оценки и строятся приближенные решения. Для ветвления выбирается множество с наименьшей нижней оценкой. В качестве примера рассматривается задача с шестью НПО (одна из них головная исчитается введенной). При решении было рассмотрено 18 вершин дерева вариантов.

В § 6.3 приводятся постановка задачи компоновки схемы генплана и общие сведения об -алгоритме ее решения. Задача состоит в размещении прямоугольных объектов в прямоугольной области, при размещении стороны объектов параллельны сторонам области. Для размещаемых объектов должны выполняться следующие условия: принадлежность области; попарного непересечения; выдерживания кратчайших расстояний между объектами; ограничения на максимально допустимые расстояния. В качестве целевой функции рассматривается длина сети в прямоугольной метрике.

В диссертации приведена математическая модель задачи компоновки.

Для решения задачи применяются алгоритмы последовательно-одиночного размещения, при этом задача формулируется как экстремальная на множестве перестановок размещаемых объектов. Последовательность, в которой размещаются объекты, либо фиксирована, либо определяется в процессе решения задачи: из всех еще неразмещенных объектов и всех свободных мест для размещения определяется такое размещение, при котором обеспечивается минимальное увеличе-

ние значения критерия. Для определения последовательности размещения могут быть использованы различные эвристические предположения.

Реализация алгоритмов последовательно одиночного размещения сводится к многократному решению задачи размещения одного объекта, т.е. к решению задачи минимизации функции двух непрерывных и одной дискретной переменной. К полученной последовательности размещения объектов применяются алгоритмы локальной оптимизации, аналогичные описанным в главах П, Ш, 17,

Алгоритмы решения задачи реализованы в виде Диалоговой системы проектирования схем генплана (ДИСП СТО) на роитиаы 1г БЭСМ-6. '

В § 6.4 описано применение ДИСП СТО для решения некоторых задач планировочной организации территории в районной планировке. Задача состоит в формировании принципиального варианта функционал ного зонирования территории. Разработана математическая модель, описывающая задачу планировочной организации территории в термина задачи компоновки. Целевая функция, позволяющая осуществить сравнение допустимых вариантов размещения, есть сумма локализацыонных затрат (т.е. стоимости размещения объектов на территории) и положительно и отрицательно связьевых затрат.(т.е. стоимостей, связан ных с притяжением или отталкиванием размещаемых объектов). Для ре шения этой задачи модифицирована ДИСП СГП.

Разработанная система применялась для решения задачи функцио нального зонирования территории в районной планировке в зоне влия ния Чебоксарской ГЭС. По заключению специалистов, система является перспективной и может широко применяться при решении подобных задач.

В главе УП "Подсистема определения очередности ввода скважин в "Системе проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ (СПГСО)" описывается разработанная подсистем автоматизированного проектирования;для определения очередности ве скважин.

Подсистема определения очередности ввода скважин разработав в ВЦ АН СССР, она является одним из модулей СПГСО, организованных и функционирующим так же, как и другие модули Системы.

Содержательная постановка задачи состоит в следующем. Необходимо определить года ввода всех скважин с учетом возможностей бурового оборудования таким образом, чтобы выполнить план добычи нефти по месторождению. При этом необходимо минимизировать суммарное расстояние при транспортировке бурового оборудования между скважинами.

В § 7.1 излагается постановка задачи« Предполагается, что известна следующая исходная информация о месторождении: сетка скважин; средние дебиты эксплуатационных скважин по годам и пластам на весь период эксплуатации) добыча по годам на весь период эксплуатации; количество скважин (эксплуатационных и нагнетательных) , которые могут быть разбурены в каждом году периода разбурпвания. При этих предположениях разработана математическая модель для определения очередноати ввода скважин, в качестве минимизируемого критерия рассматривается суммарная длина маршрутов перемещения бурового оборудования по всем годам периода разбурпвания. Поставленная задача является задачей целочисленного программирования с булевыми переменными.

В § 7.2 описана общая схема приближенного решения, основанная на декомпозиционном подходе. Этот подход состоит из двух основных этапов: построение допустимого разбиения множества скважин на подмножества по годам ввода; решение задач о выборе маршрутов движения бурового оборудования для множеств скважин по -годам ввода.

Алгоритмы построения допустимого разбиения основаны на модификациях алгоритмов кластеризации из глав Ш, 17.

Алгоритмы решения задач о выборе маршрутов движения бурового оборудования основаны на алгоритмах из глав П, Ш, 17. Эти алгоритмы позволяют найти точные или приближенные с оценкой отклонения от оптимума решения в зависимости от ресурсов ЭВМ, выделенных для решения задачи. Дри поиске приближенного решения алгоритм состоят из следующих основных шагов: формирование начального решения; оценка точности.

В § 7.3 изложены общие сведения об информационном обеспечении подсистемы, описаны основные результаты проектирования.

В § 7.4 приведены общие сведения о программном обеспечении подсистемы, указан список основных программ и последовательность

их работы-при решении задач определения очередности ввода скважин, В § 7.5 описано применение подсистемы для определения очередности ввода для одного из месторождений, расположенного на территории Коми АССР. Исходная информация подготовлена совместно с сотрудниками института ПечорНИПИнефть (г.Ухта).. По заключению специалистов института полученные варианты технологически допустимы.

В заключении делаются выводы о научной новизне результатов. Эти выводы приведены в разделе "Научная новизна". Работа по разработке перечисленных выше подходов выполнена в отделе методов проектирования развивающихся систем ВЦ АН СССР в соответствии с темой "Разработка математического обеспечения для формирования ЭВМ проектов долгосрочных программ развития нефтегазодобывающих регионов" (НГР 01.86.0130459). В постановке некоторых задач, разработке алгоритмов их решения и программной реализации принимали участие сотрудники отдела, ВЦ АН СССР и других организаций, что отражено в приводимом ниже списке работа

По теме диссертации опубликованы следующие работы:

1. Абайылданов К.Н., Астахов Н.Д., Сигал И.Х. Задача определения оптимальной очередности обслуживания объектов с учетом замены оборудования // Изв. АН СССР. Техн.кибернетика.- 1986.- № 4,-С.37-39.

2. Ахмедов И.С., Исаев A.A., Неймарк Н.И., Сигал И.Х. Использование методов математического моделирования для решения задачи планировочной организации территории в районной планировке // Автоматизация региональных градостроительных исследований. Сб. научн.тр.- М.: ЦКИИЛГС, 1988,- C.I&-30.

3. Ахмедов И.С., Сигал И.Х. Задача компоновки схемы генплана предприятий и некоторые подходы к ее решению.- (ВЦ АН СССР).-М., 1983.- 57с,- Деп. в ВИНИТИ 3.01.83, * 270-83.

4. Беккер Л.М., Крылов И.А., Сигал И.Х. Метод решения задачи выбора оптимальных параметров развития магистрального нефтепровода // Автоматизация и телемехайизация в нефтяной промышле] ности.- М.: 1982.- Вып.5.- С.23-25.

5. Беккер Л.М., Крылов И.А., Сигал И.Х. Постановка вопроса выбор! оптимальных параметров развития магистрального нефтепровода // Автоматизация и телемеханизация в нефтяной промышленности.-М.: 1982.- Вып.4.- С.17-19.

6. Ботвинник А.Х., Сигал И.Х. Выбор оптимального варианта транспортных средств // Экономика и матем.методы.- 1973.- № 6.-C.II30-II36.

7.. Гордевв. Э.Н., Леонтьев В.К., Сигал И.Х. Вычислительные алгоритмы для нахождения радиуса устойчивости в задачах выбора // Е.вычисл.матем. и матем.физ.- 1983.- Т.23.- № 4.- С.973-979.

8. Корбут A.A., Малков У.Х., Сигал И.Х., Финкелыптейн Ю.Ю. О современном состоянии и перспективах развития вычислительных методов

и программ решения задач целочисленного линейного программирования// Принятие оптимальных решений в экономич.системах.-Горький: Изд-во Горьковск.ун-та, 1983.- С.3-30.

9. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Гибридные алгоритмы в дискретной оптимизации // Изв. АН СССР. Техн.кибернетика.-1988.- № I.- С.65-77.

iO. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Гибридные методы в дискретной оптимизации // Системы программного обеспечения решения задач оптимального планирования. IX Всес.симпозиум (г.Минск, 23 февраля-3 марта 1986 г.), Тезисы докл.- М.:1986.-С.86-87.

[I. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений // Uath.Operatlonfornch. Statist. Ser.Optimizat. - 1977. - Bd.8, №2. - S.253-280.

[2. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Об эффективности комбинаторных методов в дискретном программировании // Тезисы доклад. Ш Всес.конф. по иссл.операций. Горький, 1978.- С.26.

[3. Корбут A.A., Сигал И.Х., Финкелыптейн Ю.Ю. Об эффективности комбинаторных методов в дискретном программировании // Современное состояние теории иссл.операций.- М.: Наука, 1979.-С.283-310.

[4. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемехан.- 1989.- Л 9.-С.3-33.

[5. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемехан. - 1989.10.-С. С.3-29.

16. Меламед И.И., Сергеев С.И., Сигал. И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемехан. - 1989.-№11.- С.3-26.

17. Сигал И.Х. Алгоритмы и диалоговая система для решения задачи коммивояжера большой размерности на плоскости.- М.: ВЦ АН СССР 1988.

18. Сигал И.Х. Алгоритмы приближенного решения задачи коммивояжера большой размерности на плоскости // Ж.вычисл.матем. и матем физ.- 1988.- Т.28, Л 8,- С.1268-1272.

19. Сигал И.Х. Алгоритм решения задачи о коммивояжере с оценкой точности // Алгоритмы и алгоритмич.языкиМ.: ВЦ АН СССР, 197 Вып. 6.-С. 49-61.

20. Сигал И.Х. Алгоритмы приближенного решения задачи коммивояжер большой размерности и его вычислительная реализация // Ж.Вычис матем. и матем.физ.- 1987.- Т.2Г7, № 8.-"С. 1145-1153.

21. Сигал И.Х. Вычислительная реализация комбинированного алгорит ма ветвей и границ для задачи коммивояжера // Ж.вычисл.матем. и матем.физ.- 1986.- Т.26, № 5.- С.664-672.

22. Сигал И.Х. Декомпозицонный алгоритм для решения задачи коши-вояжера большой размерности // Тезисы докл. Всесоюз. научн. конф. "Декомпозиция и координация в сложных системах".-Челябинск, 1986.- Ч.1.- С. 106-107.

23. Сигал И.Х. Декомпозиция и агрегирование в диалоговой системе решения задачи коммивояжера на плоскости // Ш Всесоюз. школа-семинар "Дискретная оптимизация и компьютеры" (теория, методы, программное обеспечение и приложения в экономике, информатике, технике). Тезисы докл. (г.Таштагол, 2-9 декабря 1987 г. ).-М.: ЦЭМИ АН СССР, 1987.- С.139-140.

24. Сигал И.Х. Диалоговые системы для решения задачи коммивояжере Проблемы теоретической кибернетики // Тезисы докл. УШ Всесоюз. конф. (июнь, 1988 г.). Ч.2.- Горький, 1988,- С.112.

25. Сигал И.Х. Задача коммивояжера большой размерности,- М.: 'ВЦ АН СССР, 1986.

26. Сигал И.Х. Комбинированные алгоритмы решения задачи коммивояжера.- М.: ВЦ АН СССР, 1985.

27. Сигал И.Х. 0 методе последовательного анализа вариантов в задачах дискретного программирования // У Симпозиум по экстремальным задачам. Тезисы докл.- Горький, 1971.- С.141.

28. Сигал И.Х. О формировании комбинированного алгоритма для решения задач дискретной оптимизации .// Методы матем. программирования и программное обеспечение. Тезисы докл. У1 научн. конф.-Свердаовск, 1989.- С.188-189.

29. Сигал И.Х, Последовательный анализ вариантов в задаче о нахождении на графе ограниченного по длине пути с максимальным весом// Изв. АН СССР. Техн.кибернетика,- 1970.- № 6.- C.4I-47.

30. Сигал И.Х. Последовательный анализ вариантой при решении экстремальных задач // Системы распределения ресурсов на графах.-М.: ВЦ АН СССР, 1970,- С.63-84.

31. Сигал И.Х. Последовательность применения алгоритмов приближенного решения в комбинированном алгоритме решения задачи коммивояжера // Е.вычисл. матем. и матем. физ.- 1989.- Т.29, J6 II.-C.I7I4-I72I.

32. Сигал И.Х. Решение задачи коммивояжера: ГФАП, ВНИТИЦентр, 14.06.1985. № 50850000504.

33. Сигал И.Х., Абайылдавов К.Н. Задача определения оптимальной последовательности ввода объектов производства при заданной приоритетности на порядок ввода объектов // Системы программного обеспечения решения задач оптимального планирования.

X Всес. симпозиум (г.Минск, 23 февраля - 3 марта 1986 г.).-Тезисы докл.- 1J., 1986,- C.I06-I09.

34. Хачатуров В.Р., Аржанов Ф.Г., Астахов Н.Д., Борисенко В.К., Веселовский-В.Е., Донгарян Ш.С., Дунаев Н.П., Злотов A.B., Крылов И.А., Кузоваткин Р.И., Николаев Б.А., Сигал И.Х., Фила-новский B.C. Система проектирования генеральных схем обустройства нефтяных месторождений на ЭВМ и опыт ее использования // Нефтяная промшшенность. Сер."Нефтепромысловое строительство". Обзорная информация. М.: БНИИОЭНГ, 1980.

35. Khachaturoy V.R., Astakhov N.D., Veselovsku V.E., Zlotov A.V., Kryiov I.A., Sigal I.H. Computer-aided oilfield assimilation design ayaten; purpose- and major capabilities // Comput. and Graphics. - 1988. - V.12, № 3/4. - P.467 - 475.