Разработка и исследование графо-топологических алгоритмов покоординатного метода для решения сетевых задач дискретной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Ленцевичюс, Раймондас Анатолиевич

• Ленцевичюс, Раймондас Анатолиевич
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Ленцевичюс, Раймондас Анатолиевич

ВВЕДЕНИЕ.

ГЛАВА I. СОСТОЯНИЕ ВОПРОСА.

IЛ. Краткая классификация методов дискретной оптимизации и прикладные задачи

1.2. Методы структурного представления и преобразования графа - сети, прикладные задачи .•••••••••••••

1.3. Приближенные методы решения невыпуклой транспортной задачи размещения • . . •

1.4. Методы решения задачи минимизации гамильтонова цикла и квадратичной задачи о назначениях «•••••

1.5. Методы случайного поиска и оценки точности приближенного решения задач ДО

1.6. Выводы по глаге I

ГЛАВА II. СТРУКТУРНО - ТОПОЛОГИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ ГРАФА - СЕТИ. ПРИМЕНЕНИЕ

ДЛЯ РАСЧЕТА НАДЕЖНОСТИ ЭЛЕКТРИЧЕСКИХ

СЕТЕЙ.

2.1. Постановка задачи, структура данных.

2.2. СТП для выделения и изменения прадерева и циклов графа.

2.3. Вычислительная сложность и способы повышения эффективности методов и алгоритмов

2.4. Внедрение методики выделения леса для расчета надежности электрических сетей.

2.5. Алгоритмы APCG. Эффективный алгоритм выделения леса прадеревьев

2.6. Тестовый пример, вычислительная эффективность, практические расчеты

2.7. Выводы по главе II.

ГЛАВА III. ГРАФО-ТОПОЛОГИЧЕСКИЙ АЛГОРИТМ ПОКООРДИНАТНОГО МЕТОДА да РЕШЕНШ ШОГОЭКСТРЕ

МАЛЫШ СЕТЕВОЙ ТРАНСПОРТНОЙ ЗАДАЧИ

РАЗМЕЩЕНИЯ С РАЗРЫВНОЙ ФУНКЦИЕЙ ЦЕЛИ.

3.1. Графо-топологическая модель

3.2. Графо-топологический алгоритм покоординатной оптимизации

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

3.4. Решение прикладных задач

3.5. Выводы по главе III

ГЛАВА 1У. ГРАФ0~Т0ШЛ0ГИЧЕСКИй АЛГОРИТМ ЗАМЕНЫ

ДУГ ДИСКРЕТНОЙ ПОКООРДИНАТНОЙ ОПТИМИЗАЦИИ ГАМИЛЫОНОВА ЦИКЛА БОЛЬШОЙ РАЗМЕРНОСТИ.

4.1. Графо-топологическая модель.

4.2. Метод дискретной покоординатной оптимизации.

4.3. Графо-топологические преобразования гамильтонова цикла и допустимость решения

4.4. Алгоритм и программа минимизации гамильтонова цикла . ЮО

4.5. Алгоритм ДПО для квадратичной задачи о назначениях.Ю

4.6. Внедрение модели и алгоритма ТЛ: построение минимального маршрута обхода сверления печатных плат

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

ГЛАВА У. КОМПЛЕКСНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ

СЛУЧАЙНОГО ПОИСКА С ЛОКАЛЬНОЙ ОПТИМИЗАЦИЕЙ СЕТЕВЫХ ЗАДАЧ ДО.

5.1. Постановка задачи

5.2. Тестовые задачи гамильтоновой цепи

5.3. Вычислительная сложность

5.4. Алгоритмы приемлемые в среднем.

5.5. Непараметрическое оценивание числа локальных минимумов алгоритмов случайного поиска с локальной оптимизацией

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

Введение диссертации (часть автореферата) на тему «Разработка и исследование графо-топологических алгоритмов покоординатного метода для решения сетевых задач дискретной оптимизации»

В отчетном докладе ЦК КПСС ХХУ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. Разработанная графо-топологическая модель и конструктивный алгоритм, реализующий метод покоординатной оптимизации, решения невыпуклой многоэкстремальной сетевой транспортной задачи размещения позволяют решать задачи большой размерности без применения агрегирования, что позволяет получить реальные маршруты обслуживания потребителей. Решена реальная задача размерности 2468x3071 с 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. Предложенный графо-топологический подход к решению сетевых задач ДО открывает путь к расширению класса задач, решаемых на УСД, и конструктивной реализации многих существующих алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Ленцевичюс, Раймондас Анатолиевич, 1984 год

1. Канторович Л.В. Математические методы организации и планирования производства. - Л.: ЛГУ, 1939.

2. Данциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966. - 600 с.

3. Gomory R.E. Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc., 1958, vol, 64, No 5, p. 275-276.

4. Канторович Л.В., Михалегич B.C., Рубинштейн Г.Ш., Третьяков Н.В., Шор Н.З., Якимец В.Н. XI Международный симпозиум по математическому программированию. Изв. АН СССР. Техн. кибернет., 1983, № I, с. 197-201.

5. Канторович Л.В., Романовский И.В. Оптимизационные методы в экономике: результаты, трудности, перспективы. Кибернетика, 1977, № 2, 68-72.

6. Дородницын А.А., Каспшицкая М.Ф., Сергиенко И.В. Об одном подходе к формализации классификации. Кибернетика, 1976, № 6, с. 132-140.

7. Моисеев Н.Н. Численные методы в теории оптимальных систем. -М.: Наука, 1971. 424 с.

8. Моисеев Н.Н. (ред. серии). Современное состояние теории исследования операций. М.: Наука, 1979. - 464 с.

9. МихалеЕНЧ B.C. Последовательные алгоритмы оптимизации и их применение. I, II. Кибернетика, 1965, № I, с. 45-56; В 2, с. 85-89.

10. Куравлев Ю.И. Об одном классе алгоритмов над конечными множествами. ДАН СССР, 1963, т. 151, I 5, с. 1025-1028.

11. Журавлев Ю.И., Финкелыитейн Ю.Ю. Сфера применения методов дискретного программирования. В кн.: Применение исследоЕания операций е экономике. М.: Экономика, 1977, с. 29-69.

12. Моцкус И.Б. Многоэкстремальные задачи е нроектироЕании. М.: Наука, 1967. - 215 с.

13. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программироЕание. -М.: Наука, IS69. 368 с.

14. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

15. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.

16. Беллман Р. Применение динамического программирования к задаче о коммивояжере. В кн.: Кибернетический сборник. М.: Мир, 1964, J6 9, с. 218-222.

17. БуркоЕ В.Н., ЛоЕецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор). Автоматика и телемеханика, 1968, В II, с. 68-93.

18. Гене Г.В., ЛеЕнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор). Изв. АН СССР. Техн. кибернет., 1979, J& 6, с. 9-20.

19. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. В кн.: Проблемы кибернетики. М.: Наука, 1976, вып. 31, с. 35-42.

20. Глушков В.М. О системной оптимизации. Кибернетика, 1980, Ш 5, с. 89-90.

21. ГлушкоЕ В.М., Каспшнцкая М.Ф., Сергиенко И.В. Вопросы формализации и решения одного класса задач дискретной оптимизации. Журн. вычисл. математики и мат. физики, 1980, т. 20, $ 6, с. 1384-1399.

22. Глушков В.М., Капитонова Ю.В., Каспшицкая М.Ф., Сергиенко И.В. Алгоритмическое обеспечение пакета программ BEKT0P-I, предназначенное для решения одного класса задач проектирования ЭВМ.

23. Кибернетика, 1978, № 4, с. 1-5.

24. Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.Н. Диалоговый пакет программ ВЕКТОР-2. Киев: ИК АН УССР, 1981. - 55 с. -/АН УССР. Ин-тут Кибернетики. Препринт - 81 - 63/.

25. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

26. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, 1981. - 208 с.

27. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). -М.: Наука, 1981. 342 с.

28. ЕмеличеЕ В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации. Изв. АН СССР. Техн. кибернет., 1982, 6, с. 25-45.

29. Ермольег 10.М. Методы стохастического программирования. М.: Наука, 1976. - 239 с.

30. Журавлев Ю.И. Локальные алгоритмы вычисления информации. I, II. Кибернетика, 1965, JS I, с. 12-19; 1966, В 2, с. 1-10.

31. Карп P.M. Сяодимость комбинаторных проблем. Кибернетический сб., 1975, вып. 12, с. 16-36.

32. Ковалев М.М. Дискретная оптимизация. Минск: ИГУ, 1977. -191 с.

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

34. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Метод ветвей и границ. (Обзор теории, алгоритмов, программ и приложений). -Math. Operationsforsoh. Statist. Ser. Optimiz., 1977, Bd. 8,2, с. 253-280.

35. Корбут А.А., Финкельштейн Ю.Ю. Приближенные методы дискретного программирования. Изе. АН СССР, Техн. кибернет., 1983, й I, с. 165-176.

36. Левин Л.А. Универсальные задачи перебора. Проблемы передачи информации, 1973, т. IX, еып. 3, с. II5-II6.

37. ЛеонтьеЕ В.К. Дискретные экстремальные задачи. В кн.: Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М.: ВИНИТИ, 1979, т. 16, о. 39-101.

38. ЛеонтьеЕ В.К. Устойчивость в линейных дискретных задачах. -В кн.: Проблемы кибернетики. М.: Наука, 1979, вып. 35, с. 169-184.

39. Михалевич B.C., Шор Н.З. Численное решение многовариантных задач по методу последовательного анализа вариантов. Научно - метод, матер, экономике - матем. семинара ЛЭМИ АН СССР. М., 1962, вып. I, с. 15-42.

40. МнхалеЕИЧ B.C., Сергиенко И.В., ЛебедеЕа Т.Т., Рощин В.А., Стукало А.С., Трубин В.А., Шор Н.З. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования. Кибернетика, 1981, $ 3, с. II7-I37.

41. РадашеЕИЧ Ю.Б. Метод построения правил останова для алгоритмов поиска субоптимальных решений в задачах дискретной оптимизации. Проблемы случайного поиска. Рига; Зинатне, 1983, вып. 10, с. 31-42.

42. Растригин Л.А. Системы экстремального управления. М.: Наука, 1974. - 630 с.

43. Романовский И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977. 352 с.

44. Рубинштейн М.И. Разрешимость в комбинаторном программировании. Препринт. М.: Институт проблем управления, 1980. - 32 с.

45. Сергиенко И.В. 0 некоторых направлениях е развитии методов дискретной оптимизации и их программного обеспечения, Кибернетика, 1982, № 6, с. 45-53»

46. Сергиенко И.В. Некоторые вопросы разработки и использования приближенных методов решения задач дискретной оптимизации.- В кн.: Кибернет. методы планирования, проект, и управления. Киев: ИК АН УССР, 1982, с. 45-62.

47. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981. - 288 с.

48. Слисенко А.О. Сложностные задачи теории вычислений. Успехи мат. наук, 1981, т. 36, вып. 6, с. 21-103.

49. Сулруненко Д.А. О значениях линейной формы на множестве подстановок. Кибернетика, 1968, J& 2, 59-63.

50. Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев: Нау-коЕа думка, 1980. - 208 с.

51. Танаев B.C., Шкурба В.В. Введение е теорию расписаний. М.: Наука, 1975. - 256 с.

52. Трубин В.А. Эффективный алгоритм решения задачи размещения на сети в форме дерева. Докл. АН СССР, 1976, т. 231, 3, с. 547-550.

53. Фридман А.А, 0 некоторых современных направлениях в дискретной оптимизации. Экономика и матем. методы, 1977, т. 13,5, с. III5-II3I.

54. Хачатуров В.Р. Аппроксимационно комбинаторный метод и некоторые его приложения. - Журн. вычисл. математики и мат. физики, 1974, т. 14, № 6, с. 1464-1487.

55. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. Докл. All СССР, 1979, т. 244, В 5, с. 1093-1096.

56. Черенин В.П. Решение некоторых комбинаторных задач методом последоЕательных расчетов. В кн.: Материалы конф. по опыту и перспективам применения мат. методов и ЭВМ. Новосибирск: СО АН СССР, 1962, с. 41-54.

57. Черенин В.П., Хачатуров В.Р. Решение методом последовательных расчетов одного класса задач о размещении производства. В кн.: Экономило - математические методы. М.: Наука, 1965, еып. 2, с. 279-290.

58. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. КиеЕ: Наукова думка, 1979. - 200 с.

59. Юдин Д.В., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ. М.: Радио и сеязъ, 1982. - 288 с.

60. Golden В., Ball М., Bodin L. Current and future research directions in network optimization. Comput. and Ops. Res., 1981, vol. 8, p. 71-31.

61. ВреднеЕ B.H. Оптимальный синтез коммуникационных сетей по критерию минимума затрат. Изв. АН СССР. Техн. кибернет., 1981, В 3, с. 100-106.

62. Трубин В.А., Гндоян А.К. Алгоритм и свойства задачи синтеза сетей с одним источником. В кн.: Теория оптимальных решений. Киев: ИК АН УССР, 1980, с. 81-87.

63. Задачи маршрутизации (вычислительный аспект). Препринт.

64. М.: Ин-т проблем управления, 1981. 48 с.

65. Magnanti Т.Ь. Combinatorial Optimization and vehi<&> fleet planning: perspectives and prospects. Networks, 1981, vol.11, № 2, p. 179-213.

66. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей. Автоматика, 1981, J5 4, с. 27-40.

67. Якубайтис Э.А. Многоканальные вычислительные сети с селекцией информации. Авт. и еычисл. техника, 1983, № 3, с. 3-9.

68. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичюс В.А. Автоматизация проектирования ЭВМ. М.: Советское радио, 1978. - 270 с.

69. Глушков В.М., Деркач В.П., Кияшко Г.Ф. Важнейшие задачи в области автоматизации проектирования больших интегральных схем. Управляющие системы и машины, 1977, Ш 6, с. 88-92.

70. Глушков Н.Г., МеркурьеЕ В.В, и др. Автоматизация размещения элементов управления на пульте. Управляющие системы и машины, 1977, Je 5, с. 130-134.

71. Матицкас И.К. Алгоритм размещения разногабаритных элементов в кратные позиции. Управляющие системы и машины, 1979,1. Ш 4, с. 120-123.

72. Половинкин А.И. (ред.) Автоматизация поискового конструирования (искусственный интелект в машинном проектировании). -М.: Радио и связь, 1981. 344 с.

73. Селютин В.А. Машинное конструирование электронных устройств. М.: Советское радио, 1977. - 384 с.

74. Штейн М.Е., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. М.: Советское радио, 1973. - 289 с.

75. Берж К. Теория графоЕ и ее применения. М.: ИЛ, 1962. -319 с.

76. Кристофидес Н. Теория графов. Алгоритмический подход. М.:1. Мир, 1978. 432 с.

77. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

78. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

79. Баррон Д. Введение в языки программирования. М.: Мир, 1980. - 190 с.

80. Хьюз Ч., Пфлигер Ч., Роуз Л. Методы программирования: курсна основе ФОРТРАНА. М.: Мир, 1981. - 331 с.

81. Турский В. Методология программирования. М.: Мир, 1981. -265 с.

82. ВеникоЕ В.А., Руденко 10.Н., Совалов С.А. Задачи исследования электроэнергетических систем.Изв. АН СССР. Энергетика и транспорт, 1973, № 5, с. 12-24.

83. Руденко Ю.Н., Чельцов М.Б. Надежность и резервирование в электрических системах. Методы и исследования. Новосибирск СО АН СССР.: Наука, 1974. - 263 с.

84. Еурба А.В., Бинкаускас Б.-Ю.Б. Расчет показателей надежности электрических сетей с использованием процессов Маркова. -Труды АН Лит. ССР, 1975, сер. Б, 2 (93), с. 173-179.

85. Зорин В.В., Недин И.В. Определение и использование минимальных сечений при оценке надежности систем электроснабжения. -Изв. Вузов СССР. Энергетика, 1974, J.: 4, с. 31.

86. Фокин Ю.А., Харченко A.M. Метод построения расчетной схемы и расчета показателей надежности сложных систем с большим числом элементов. Изв. Вузов СССР. Энергетика, 1978, 8, с • 3 о~~3£/ •

87. Мизин И.А., Уринсон Л.С., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений. М.: Связь, 1972. - 319 с.

88. Вычислительные сети (адаптивностьi помехоустойчивость, надежностъ) / С.И. Самойленко и др. Под общ. ред. 10.Г. Да-даева. М.: Наука, 1981. - 277 с.

89. Болотов А.Б. Методы и алгоритмы структурно-топологической оптимизации централизованных сетей передачи данных. -УСиМ, 1981, & 5, 11-16.

90. Allan R.N., Barazesh В., Sumar S. Reliability evaluation of distribution systems using graphic-based interactive computational methods. IEEE Trans, on Power Дрр. and Syst., 1982, vol. PAS-101, No 1, p. 212-218.

91. Bertran M., Corbella X. On the validation and analysis of a new method for power network connectivity determination. « IEEE Trans, on Power APP. and Syst., 1982, vol. PAS-101,1. No 2, p. 316-324.

92. Адельсон-Вельский Г.М., Диниц E.A., Карзанов А.В. Потоковые алгоритмы. М.: Наука, 1975. - 119 с.

93. Glover F., Klingman D. Locating stepping-stone paths in distribution problems via the predecessor iridex method. « Transportation Sci., 1970, vol. 4, No 2, p. 220-225.

94. Glover P., Klingman D., Stutz J. Augmented threaded index method for network optimization. INFOR, 1974, vol. 12» No 3, p. 293-298.

95. SrinivaSan'V., Thompson G.L. Accelerated Algorithms for labeling and relabeling of trees, with applications to distribution problems. Journal of the ACM, 1972, vol. 19, N04, p. 712-726.

96. Mcllroy M.D. Generation of spanning trees (Algorithm 354)* Communications of the ACM, 1969, vol. 12, No 9, p. 511.

97. Levitt K.N., Kautz W.H. Cellular arrays for the solution of graph problems. Communications of the ACM, 1972, vol. 15,1. No 9, p. 789-801.

98. Hopcroft J.E., Tarjan R. Efficient Algorithms for graph manipulation (Algorithm 447). Communications of the ACM, 1973, vol. 16, No 6, p. 372-378.

99. Seppanen J.J. Spanning tree (Algorithm 399). Communications of the ACM, 1970, vol 1$, No 10, p. 621*622.

100. БезносоЕ Г.П., Ефименко Б.В., Загоруйко А.С., Стукалин Ю.А. FOREST АЛГОЛ - процедура построения дерена графа. - Новосибирск: ИА и Э 00 АН СССР, 1974. - 15 с.

101. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. - 323 с.

102. КантороЕИЧ Л.В., ГаЕурин М.К. Применение математических мето-дое е Еопросах анализа грузопотокоЕ. В кн.: Проблемы поеы-шения эффективности работы транспорта. АН СССР, 1949, с. II0-I38.

103. Голъштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 382 с.

104. Even SShiloach Y. An on-line edge-deletion problem.

105. Journal of the ACM, 1981,, vol. 28, No 1, p. 1«4«

106. ХачатуроЕ В.P., ВеселоЕский B.E. Решение задач размещения большой размерности. В кн.: Численные методы нелинейного программирования. Тезисы II Всесоюзного семинара. Харьков: 1976, с. 317-322.

107. Леонас В.Л., Моцкус И.Б. Об одной нелинейной задаче математического программирования. В кн.: Математические методы решения экономических задач. М.: Наука, 1969, с. 38-48.

108. Гудялис Л.П., Штарас В.М. Решение задачи оптимального размещения емкостей дистиллята е республике на осноЕе аналитических расчетоЕ. В кн.: Электротехника. Материалы конференции. Каунас: 1975, с. 77-80.

109. Кугелегичюс И.Б. Размещение топлиЕохранилищ на територии экономического района. В кн.: Проблемы разЕНТия топливно -энергетического комплекса Северо - Запада СССР (оте. ред. Я.Гелерис., И.Кугелевичюс). Вильнюс: Мокслас, 1980, с. I24-I3I.

110. Walker W.E. A heuristic adjacent extreme point algorithm for the fixed charge problem. Management science,, 1976, vol. '22, No 5» P. 5B7-596.

111. НО. СергееЕ С.И. Алгоритмы решения задачи коммиЕОяжера (обзор). -В кн.: Моделирование технико-экономических процессоЕ. М.: Экономика, 1981, с. 1-37.

112. ЛеонтъеЕ В.К. Исследование одного алгоритма решения задачи коммивояжера. Ж. еычисл. мат. и мат. физ., 1973, т. 13, № 5, с. 1228-1236.

113. Бородин В.В., Ловецкий С.Е., Меламед И.И., Плотинский Ю.М. Экспериментальное исследование эффективности эвристических алгоритмов решения задачи коммиЕояжера. Автоматика и телемеханика, 1980, I II, с. 76-84.

114. Минина Т.Р., Перекрест В.Т. Аппроксимация решения задачи коммивояжера С циклами. - Аетомэтикэ и телемеханика, 1975, № 10, с. 79-89.

115. Автоматизированная система проектирования печатных плат Draft. Проспект фирмы quest, 1980, с. 1-54.

116. Christofides N*, Eilon S. Algorithms for large-scale travelling salesman problems, Oper. Res, guarterly, 1972» vol. 23, No 4, p. 511-518•

117. Crowder tt.„ Padberg M»W« Solving large-scale symmetric travel** ling salesman problems to optimality. Management science, 1980,, vol. 26» No 5» P. 495-509.

118. Steinberg L. The backboard wiring problem: a placement algorithn • SIAM review, 1961, vol. 3» No 1» p, 37-50.

119. Burkard R.E.» Stratmann K.H. Numerical investigations on guad-ratio assignment problems. « NavaL Res. Log. Quart., 1978, vol. 25, No 1, p, 120-148.

120. Моцкус И.Б. О байесоЕЫх методах поиска экстремума. Авт. и еыч. техника, 1972, Л 3, с. 53-62.

121. Устюжанинов Б.Г. Возможности случайного поиска е решении дискретных экстремальных задач. Кибернетика, 1983, № 2, с. 6471, 77.

122. Golden В.Ь. A statistical approach to the TSP. Networks, 1977» vol. 7, P. 209-225.

123. Уолш Дж. E. Непараметрические доверительные интервалы и толерантные области. В кн.: Введение в теорию порядковых статистик. ГЛ.: Статистика, 1970, с. 128-134.

124. Пирсон К. Таблицы неполной бета функции. М.: ВЦ АН СССР, 1974. - 538 с.

125. Ленцевичюс Р.А., Гирдзияускас И.И., Качинскас Ш.А. Практическое применение алгоритма покоординатной оптимизации для размещения модулей РИА. В кн.: Радиоизмерения. Материалы III респ. научн.-техн. конф. по радиоизмерениям. Вильнюс, 1969, с. 30-32.

126. Ленцевичюс Р.А., Моцкус И.Б. Исследование эффективности алгоритмов решения одной задачи размещения. Авт. и вычисл. техн., 1970, с. 47-51.

127. ЛенцеЕИчюс Р.А. Некоторые алгоритмы для квадратичной задачио назначениях и ее специальных разноЕидностей. В кн.: Математика. Материалы докладов XXI республиканской научно-технической конференции. Каунас, 1971, с. 25-33,

128. Леонас В.Л., Ленцевичюс Р.А. Алгоритмы выделения и изменения дерева и циклое графа с использованием прадеревьев. Деп. е ВИНИТИ, 1974, В 117-74. - II с.

129. ЛенцеЕИчюс Р.А., Леонас В.Л., Алишаускас А.В. О решении нелинейной многоэкстремальной сетеЕой транспортной задачи большой размерности в сеязи с размещением нефтебаз на территории Литовской ССР. Деп. в ВИНИТИ, 1978, В 1408-78. - 12 с.

130. Ленцевичюс Р.А. Топологический алгоритм замены дуг оптимизации гамильтоноЕа цикла большой размерности. В кн.: Теория оптимальных решений. Вильнюс, 1980, еып. 6 (Ин-т математики и кибернетики АН Лит. ССР), с. 107-124.

131. АРСС автоматическое распознавание состояния сети;

132. ЭДСД внутренняя динамическая структура данных;1. ГЦ гамильтоновый цикл;

133. ДО дискретная оптимизация;

134. ДПО дискретная покоординатная оптимизация;

135. КЗН квадратичная задача о назначениях;

136. ПО покоординатная оптимизация;

137. ППП пакет прикладных программ;

138. Префикс предыдущая вершина (ее номер) в структурном дереве;

139. Рефикс послеидущая вершина (ее номер) в структурном ГЦ;

140. РЭА радиоэлектронная аппаратура;

141. САПР система автоматизации проектирования;

142. СТП структурно-топологические преобразования;

143. ХП графо-топологический алгоритм замены дуг;

144. УСД универсальная структура данных;

145. ЦЯП целочисленное линейное программирование;

146. ЧПУ числовое программное управление;1. ЭС электрическая сеть.