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

В отчетном докладе ЦК КПСС ХХУ1 съезду КПСС, в ноябрьском 1982 года и июньском 1983 года пленумах подчеркивается важность ускорения научно-технического прогресса, широкого и быотрого внедрения результатов науки и техники с использованием вычислительной техники для успешного решения задач народного хозяйства.

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

Взяв овое начало от классических работ Л. В. Канторовича, Дк. Данцига, Р. Е. Гомори /I — 3/ дискретное программирование в настоящее время переживает бурное развитие, на что указывает большое количество появляющихся публикаций и докладов на международных симпозиумах /4/. Этой молодой науке постоянное внимание уделяют и творчески ее развивают такие известные советокие ученые как Л. В. Канторович, А. А. Дородницын, Н.Н.МоисееЕ, В. С. Михалевич, Ю.И.ЖуравлеЕ и целый ряд других /5 — II/.

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

Выходом из создавшегося положения может быть более широкое внедрение и разработка приближенных методов и алгоритмов, е том числе локальных. При разработке приближенных методов получено немало результатов. В последнее время создано первое поколение пакетов прикладных программ (1ШП) ДО, включающих как точные так и приближенные методы" Но по прежнему остается проблемой решение задач большой размерности, особенно комбинаторных, так как решение практических задач, как правило обладающих большой размерностью, пока не стало регулярным явлением. Не менее важной задачей, тесно связанной с проблемой большой размерности, является создание развитого алгоритмического обеспечения методов ДО, составляющих предметную область пакетов, по пути универсализации структур данных. Такой подход снизу — Еверх от прикладных программных модулей пакета к управляющей его части облегчает задачу разработки пакетов, их усовершенствования и меньшую зависимость от професо-нального уровня программистов, а в некоторых случаях, просто позволяет сделать реализации методов досягаемыми не только для их авторов. & тому же Еажно заметить, что при решении практических задач оптимального планироЕания и автоматизации Проектирования часто используются ЭВМ с небольшой (ограниченной) памятью (порядка 64 Кбайт). Поэтому современным и актуальным является решение следующих вопросов ДО:

1. Универсализации структур данных решаемых задач;

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

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

Одним из подходов, решающих постановленние Еопросы, может быть выделение классоб практических задач на основе изучения их структуры и последующим выбором модели ее представления. В ряде случаев углубление моделирования, на основе более детального изучения структуры решаемых задач, позволяет построить новые более универсальные алгоритмы и модификации существующих с лучшими вычислительными характеристиками. Из задач ДО можно выделить и объединить в класс сетевых такие задачи как транспортную задачу с невыпуклой разрывной функцией цели, разновидности квадратичной задачи о назначениях (КЗН), задачу минимизации гамильтоноЕа цикла, моделирующих многие прикладные задачи маршрутизации и размещения. Структуру некоторых из этих задач можно объединить и представить ввиде единой универсальной — ввиде структурных деревьев (корневых деревьев — прадеревьев). Математическая модель таких задач запишется ввиде следующей графо-топологической модели: fu) z е Z с Z ScU где аддитивная функция цели (суммарные расчетные затраты, суммарная стоимость проектируемого объекта), Z — вектор дискретных переменных, — допустимое конечное множество дискретных точек на гранях многогранника Z., заданного линейными ограничениямиS — множество корневых деревьев, соответствующих дискретным точкам множества Z — U — список дуг графа-сети 5 (W > U), где W — множество Еершин графа-сети, определяющего топологию множества L. .

Для решения данной общей задачи используется локальный метод дискретной покоординатной оптимизации (ДПО) со случайно заданных rrn п I начальных точек. Для решения некоторых частных задач, например минимизации гамильтонова цикла, метод ДПО является расширением известного метода покоординатной оптимизации (ПО), предложенного И. Б. Моцкусом /12/, и позволяющего найти локальные минимумы невы-пуклах задач производственно — транспортного типа.

Метод ДПО — прямой метод, позволяющий найти приближенное — локальное решение. Начиная с некоторого допустимого решения на каждом шагу осуществляется улучшение текущего допустимого решения следующим образом: для производственно-транспорФных задач размещения — это оптимизация на контурах, для минимизации гамильтонова цикла — это замена текущих дуг на новые, соответствующая сумма цен которых меньше текущих. Метод конечный, так как на каждом шагу рассматривается конечное число улучшений, и заканчивается, когда улучшения от текущего решения по всем следующим допустимым решениям до исходного текущего не получается. Применение такого метода требует на каждом шагу производить графо — топологические структурные преобразования корневых деревьев, соответствующих допустимым текущим решениям. Поэтому для осуществления метода ДПО необходима разработка соответствующих графо — топологических алгоритмов. Метод применяется для оптимизации со случайно заданных начальных точек с целью получения ряда локальных минимумов. Поэтому соответствующие разрабатываемые алгоритмы по определению А. А. Корбута и Ю. Ю. Финкельштейна /13 — 14/ принадлежат классу алгоритмов случайного поиска с локальной оптимизацией.

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

Для осуществления этой цели требуется решать следующие задачи:

1. Выбрать метод и алгоритмы его реализации для решения сетевых задач ДО большой размерности.

2. Разработать эффективные алгоритмы и программные модули выделения «из графа сети прадереЕа (корневого дерева) и его структурных преобразований.

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

4. Представить графо — топологическую сетевую модель минимизации гамильтонова цикла на прадереЕЬях и разработать графо — топологический алгоритм ДПО с соответствующими программными модулями преобразований цикла.

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

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

7. Провести исследование применения моделирования и алгоритмического решения практических задач большой размерности на ЭВМ с ограниченной памятью.

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

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

Во второй главе приводится новый единый подход решения задач структурно-топологических преобразований графа — сети и построения структурного дерева — универсальной структуры данных (УСД) для графо-топологического моделирования и решения сетевых задач ДО. На специально построенных графах найдены оценки трудоемкости существующих и разработанных алгоритмов и приведено сравнение их вычислительной сложности. Предложенные алгоритмические правила позволяют поеысить эффектиЕНость существующих алгоритмов и разработать ноеый конструктивный модульный алгоритм построения структурного дерева с линейной трудоемкостью и минимальной памятью по отношению известных. Разработанные новые конструктивные модульные алгоритмы автоматического распознавания состояния (определения связных компонент) граф — сети использованы в алгоритме расчета надежности для эффективного решения прикладной задачи проектирования основной электрической сети Литовской ССР.

В третей главе приводится графо-топологический подход на УСД структурном дереве к решению невыпуклой многоэкстремальной сетевой транспортной задачи размещения. Представленная конструктивная иерархическая графо-топологическая модель адекватно отражает структуру решаемых прикладных задач. Приводится разработанный конструктивный графо-топологический алгоритм случайного поиска с локальной оптимизацией, реализующий метод покоординатной оптимизации, позволяющий решать задачи большого размера без агрегирования на ЭВМ с ограниченными ресурсами по памяти (64 Кбайт). Приведены вычислительные характеристики соответствующей программы. Решена прикладная задача большой размерности 2468×3071 с 33 размещаемыми объектами (тобливохраншшщами) на реальной транспортной сети Лит. ССР. Разработанная программа также применена для решения прикладной задачи оптимального проектированияразмещения териториальных управлений (объединений) хозяйства водоснабжения и канализации Лит. ССР.

В четвертой главе приводится графо-топологический подход к решению задачи минимизации гамилътонова цикла, позволивший разработать новый конструктивный алгоритм случайного поиска с локальной оптимизациейfобобщающий метод С. Лина и решающий возникшую при реализации этого метода проблему организации памяти. Полученный существенный выигриш по памяти (для рекордной задачи с 318 точками, решенной последней алгоритмической версией метода.

С. Лина, в 35 раз) позволил расширить диапазон решаемых прикладных задач в 3-й раза (до 1000-и точек) на ЭВМ с 64 кбайто-вой памятью, что соответствует нуждам решаемых прикладных задач маршрутизации. Приводятся результаты испытательно — промышленных расчетов прикладной задачи проектирования маршрута сверления печатных плат РЭА запускаемых в серийное производство. Получен суммарный выигриш в по отношению ручных решений опытного конструктора. Приведена программная реализация алгоритма ввиде программы с древовидной модульной структурой и ее вычислительная сложность по времени и памяти. Приводится алгоритм дискретной покоординатной оптимизации (ДПО) для решения КЗН, приводящий к варианту алгоритма парных перестановок для специального случая КЗН — задачи размещения. Полученные вычислительные результаты эффективности алгоритма ДПО показывают о возможности его использования в качестве препроцессора получения решений в составных и гибридных схемах алгоритмов.

В пятой главе приводится методика комплексного исследования вычислительной сложности по памяти, быстродействию и точности приближенных алгоритмов решения задач ДО, включая алгоритмы случайного поиска с локальной оптимизацией. Введено понятие и определение алгоритма приемлемого в среднем по отношению ручных методов решения и других алгоритмов, включая алгоритмы существующих стандартных САПР. Построены теоретические оценки числа локальных минимумов при заданной точности и доверительной вероятности. Оценки позволяют определить конец счета, что связано с экономией времени ЭВМ, проверить стабильность полученных решений от размера решаемых задач. Приводится обширный вычислительный эксперимент исследования разработанного графо-топологического алгоритма минимизации гамильтоноЕа цикла (цепи) на десяти выбранных реальных (маршруты сверления печатных плат), известных и специально построенных тестовых задачах большой размерности. Получено, что теоретические оценки хорошо совпадают с экспериментом (отличие е среднем на 5%). Выявлено, что наиболее сбалансированными вычислительными характеристиками по отношению существующих обладает разработанным алгоритм. Установлено, что разработанный алгоритм является приемлемым в среднем по отношению ручных методов решений и решений существующих стандартных САПР. Выявлено хорошая стабильность точности полученных решений от размеров решаемых задач. При этом установленно, что достаточно малого количества локальных минимумов (2−3) для получения решении с точностью 0% - 3,9 $ на широкой шкале размерностей решаемых задач от 24 до 1000 точек. Полученные результаты легли в основу обоснования экономии при серийном производстве печатных плат РЭА.

Основные результаты диссертационной работы:

1. Осноеной результат — предлагаемый графо-топологический подход на УСД структурном дереве к решению выделенного класса сетевых задач ДО, открывающий путь присоединения к ним других задач с аналогичной структурой, и позволяющий разработать новые конструктивные модели и алгоритмы, расширяющие диапазон решаемых задач большой размерности на ЭВМ с ограниченными ресурсами по памяти (в настоящей работе 64 кбайт), а также конструктивно реализовать многие существующие алгоритмы.

2. Разработанный единый подход к построению УСД структурного дерева и решению других задач структурно-топологических преобразований графа — сети. Полученные оценки вычислительной сложности алгоритмоЕ Енделения дереЕа (леса) и структурного дерева (леса).

3. На осноЕе предложенных алгоритмических праЕил разработанный коиструктиЕНЫй модульный алгоритм Еыделения структурного дереЕа (леса) и автоматического распознавания состояния сети (выделения связных компонент) с линейной трудоемкостью и минимальной памятью по отношению существующих.

4. Разработанные конструктивные графо-топологическая модель и алгоритм случайного поиска с локальной оптимизацией на УСД структурном дереве решения неЕЫпуклой многоэкстремальной сетевой транспортной задачи размещения, реализующие метод покординатной оптимизации, позволяющие решать задачи больших размерностей без применения агрегирования.

5. Разработанный метод дискретной покоординатной оптимизации (ДПО), конструктивные графо-топологическая модель и алгоритм случайного поиска с локальной оптимизацией на УСД структурном дереве решения задачи минимизации ГЦ большой размерности (до 1000-и точек на '64 кбайтовой по памяти ЭВМ), обобщающие метод С. Лина и решающие до сих пор нерешенную проблему организации памяти, что позволяет расширить диапазон размерностей решаемых прикладных задач маршрутизации до практических потребностей (автоматического проектирования маршрутов сверления печатных плат РЭА, запускаемых в серийное производство). Разработанный алгоритм ДПО решения КЗН и полученный вариант алгоритма парных перестановок для специального случая КЗН — задачи размещения.

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

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

— расчета надежности основных электрических сетей Лит. ССР;

— размещения топливохранилищ на територии Лит. ССР с использованием реальной транспортной сети республики;

— размещения териториалъных управлений (объединений) хозяйства водоснабжения и канализации Лит. ССР;

— автоматизации проектирования минимального по длине маршрута сверления автоматами с ЧПУ печатных плат РЭА, запускаемых в серийное производство.

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

Связь с научной тематикой. Настоящая работа выполнена в лаборатории больших энергетических систем Института физико-технических проблем энергетики Академии Наук Литовской ССР в соответствии с научно исследовательскими плановыми темами: «Разработка математических и эвристических методов решения многоэкстремальных задач в проектировании производственно транспортных систем», «Разработка алгоритмов и программ для решения оптимизационных задач проектирования электрических сетей», «Развитие методов моделирования и оптимизации электрических сетей» .

Основные результаты диссертационной работы опубликованы в /134−140/ и докладывались на республиканских научно — технических конференциях (г. Каунас) в 1971, 1574, 1975 годах, на республиканском семинаре при Институте математики и кибернетики АН Литовской ССР «Теория оптимальных решений» (г. Вильнюс) в I960 г., на всесоюзных научно — технических конференциях «Повышение эффективности использования технологического оборудования с программным управлением» (г. Пенза) в 1980 г., «Методические вопросы исследования надежности больших систем энергетики» (г. Каунассовместно с АН СССР СО СЭИ) в 1982 г., на Vом всесоюзном совещании «Моделирование и оптимизация проектных решений в САПР» (г. Таллин — Выру) в 1983 г., на всесоюзной деловой Естрече ученых «Случайный поиск е задачах дискретной оптимизации» (г. Харьков) е 1983 г., на семинаре Научного Совета АН УССР по проблеме «Кибернетика» секция 5 — '-Методы решения и математическое обеспечение задач дискретной оптимизации" (г. Киев ИК им. В. М. Глушкова АН УССР) в 1983 г.

Внедрение работы. Результаты диссертационной работы внедрены и использованы для решения следующих прикладных задач. Разработанный метод, алгоритм и программные модули автоматического распознавания состояний сети внедрены в рамках программы расчета надежности основной, электрической сети Лит. ССР и включены в математическое обеспечение ЭВМ М-32 в Главном производственном управлении энергетики и электрификации Лит. ССР на основе выполнения работы «Разработка и внедрение программы вычисления показателей надежности узлов основной электрической сети Литовской энергосистемы». Разработанные метод, алгоритм и программа решения невыпуклой многоэкстремальной сетевой транспортной задачи размещения внедрены в рамках работы «Исследование структуры производственных объединений хозяйства водоснабжения и канализации» в Производственном объединении предприятий водоснабжения и канализации Лит. ССР для размещения территориальных управлений хозяйства водоснабжения и канализации Лит. ССР, а также использованы для определения оптимальных мест строительства и расширения топливохранилищ на територии Лит. ССР в рамках выполненой работы при. Госплане Лит. ССР. Разработанный метод, алгоритм и программа минимизации гамильтонова цикла внедрены для построения минимального по длине маршрута сверления печатных плат РЭА, запускаемых в серийное производство, в рамках САПР Каунасского радио завода. Использование результатов диссертационной работыметодов, алгоритмов и программ в перечисленных организациях позволяет получать годовой экономический эффект в размере 57 тыс. рублей.

5.6. Выводы по главе У.

I. Приведенная методика комплексного исследования вычислительной сложности алгоритмов случайного поиска с локальной оптимизацией решения задач дискретной оптимизации (ДО) позволяет определить их поведение в минимаксном, в среднем и вероятностном смыслах и оценить по найденным теоретическим непараметрическим оценкам числа локальных минимумов число шагов случайного поиска, что связано с определением конца счета и непосредственно с экономией времени ЭВМ.

2. Вычислительный эксперимент на решениях разработанного алгоритма минимизации гамильтонова цикла (ГЦ) показал, что предложенные теоретические оценки числа локальных минимумов хорошо совпадают с полученными экспериментально — среди 55-и сравнений на 8-и тестовых задачах (6-ь из них прикладные) различных размерностей от 24 до 318 точек отличие е среднем составляет 5%.

3. Комплексное исследование по приведенной методике показало, что наиболее сбалансированными вычислительными характеристиками по памяти, быстродействию и точности обладает разработанный алгоритм минимизации ГЦ:

— при аналогичных вычислительных характеристиках по быстродействию и точности позволяет получить значительный выигриш по памяти (для задачи 318 точек в 35 раз) по отношению последней алгоритмической версии метода С. Лина;

— найденные лучшие решения по суммарной длине лучше на 9% и 39% соответствующих ручных решений опытного конструктора и решений полученных в существующих САПР, а разработанный алгоритм является приемлемым в среднем (найденные решения в среднем на 7% и на 20% лучше соответствующих ручных решений опытного конструктора и полученных в существующих стандартных САПР), что дает основу обоснования экономической эффективности алгоритма при серийном производстве печатных плат РЭА.

4. Проведенные вычисления на основе оценок числа локальных минимумов показали, что точность разработанного алгоритма минимизации ГЦ мало зависит от размеров решаемых задач: достаточно нахождения небольшого числа локальных минимумов (2−3) для получения с достоверностью 0,75−0,95 точности 0% - 3,9 $ для широкой шкалы размерностей решаемых задач от 24 до 1000 точек.

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

ЗАКЛЮЧЕНИЕ

.

Разработан графо-топологический подход и конструктивные приближенные алгоритмы решения сетевых задач дискретной оптимизации (ДО) большой размерности на ЭВМ с ограниченной памятью (64 кбайт), что расширяет диапазон решаемых прикладных задач оптимального проектирования. Исследованы вопросы вычислительной сложности и практической реализации алгоритмов. Алгоритмы внедрены для решения реальных задач оптимального проектирования. При этом.

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

2. Разработанная графо-топологическая модель и конструктивный алгоритм, реализующий метод покоординатной оптимизации, решения невыпуклой многоэкстремальной сетевой транспортной задачи размещения позволяют решать задачи большой размерности без применения агрегирования, что позволяет получить реальные маршруты обслуживания потребителей. Решена реальная задача размерности 2468×3071 с 33 размещаемыми объектами (топливохранилищами) на реальной транспортной сети Литовской ССР. Среднее время нахождения¦одного локального минимума I час, а с расширением памяти на 2468 слое -10 — 12 мин на БЭСМ-6. Полученные локальные решения отличаются лишь на 1,3 $ и не уступают решениям опытных специалистов.

3. На основе разработанных графо-топологической модели и гра-фо-топологических преобразований гамильтонова цикла (ГЦ) на УСД структурном дереве решена проблема организации памяти для минимизации гамильтонова цикла, что позеолило разработать новый конструктивный алгоритм, обобщающий метод С. Лина, существенно уменьшить объем требуемой памяти (для рекордной задачи размеров 318 точек, решенной методом С. Лина, в 35 раз) и решать задачи до 1000 точек, т. е. расширить диапазон решаемых практических задач е 3-й раза.

4. Полученные теоретические оценки числа локальных минимумов для алгоритмов случайного поиска с локальной оптимизацией решения задач ДО позволяют определить конец счета, что может дать большую экономию времени ЭВМ по Есей совокупности решаемых задач.

5. В рамках предложенной методики комплеконого исследования вычислительной сложности алгоритмов случайного поиска с локальной оптимизацией для разработанного алгоритма минимизации ГЦ получено:

— найденные лучшие решения по суммарной длине для прикладной задачи проектирования маршрута сверления печатных плат ?3Afзапускаемых в серийное производство, лучше на 9 $ и 39% соответствующих ручных решений опытного конструктора и решенийtполученных в существующих САПР, а разработанный алгоритм является приемлемым е среднем (найденные решения в среднем на 7 $ и на 20 $ лучше соответствующих полученных опытным конструктором и алгоритмом используемым в существующей стандартной САПР), что стало основной обоснования экономической эффективности алгоритма при серийном производстве печатных плат РЭА;

— на основе оценок числа локальных минимумоЕ найдена малая зависимость точности разработанного алгоритма от размеров решаемых задач: достаточно нахождения небольшого числа локальных минимумов (2−3) дом получения с достоверностью 0,75 — 0,95 точности 0 $ - 3,9 $ для широкой шкалы размерностей решаемых задач от 24 до 1000 точек.

6. Разработанный метод дискретной покоординатной оптимизации для решения квадратичной задачи о назначениях (КЗН) позеолил получить Еариант алгоритма парных перестановок для решения специального случая КЗН — задачи размещения и получить в 10-ь раз быстрее решение известной тестоЕой задачи Л, Штейнберга, отличающееся лишь на 1,45 $ от известного лучшего.

7. Разработанные конструктивные методы и алгоритмы могут быть использованы в составных и гибридных схемах алгоритмов в качестве препроцессоров.

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

— расчета надежности ochoehok электрической сети Литовской ССР;

— размещения топливохранилищ на територии Литоеской ССР;

— размещения териториальных управлений (объединений) хозяйства водоснабжения и канализации Литовской ССР;

— проектирования маршрутов печатных плат РЭА, запускаемых в серийное производство.

9. Предложенный графо-топологический подход к решению сетевых задач ДО открывает путь к расширению класса задач, решаемых на УСД, и конструктивной реализации многих существующих алгоритмов.