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

ВВЕДЕНИЕ

ГЛАВА I. МЕТОД АНАЛИЗА СТРУКТУРЫ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И ЕГО ПРИМЕНЕНИЕ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИИ.

1.1. Интегральные характеристики 03 и их оценка.

1.2. Применение методов многомерного статистического анализа для обработки результатов оценки интегральных характеристик 03.

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

1.2.2. Метод экстремальной группировки параметров и его применение.

1.3. Оценка степени влияния переменных и их групп на точность решения задачи.

1.4. Методы оптимизации и анализ структуры 03.

1.4.1. ЛП-поиск, учитывающий структуру задачи.

1.4.2. Покоординатный поиск, учитывающий структуру задачи.

1.4.3. Метод локальной оптимизации, основанный на анализе структуры задачи.

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

ГЛАВА II. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДА АНАЛИЗА

СТРУКТУРЫ 03 И С НИМ СВЯЗАННЫХ МЕТОДОВ ОПТИМИЗАЦИИ.

2.1. Тестовые задачи.

2.2. Экспериментальное обоснование наличия для

03 оптимальной системы координат.

2.3. Исследование качества оценки интегральных характеристик задачи и определения оптимальной системы координат.

2.4. Исследование эффективности реализации метода экстремальной группировки параметров.

2.5. Сравнение эффективности методов анализа структуры 03.

2.6. Исследование качества оценки степени влияния переменных и их групп на точность решения 03.

2.7. Пример использования метода анализа структуры 03.

2.8. Исследование методов оптимизации, связанных с анализом структуры 03.

2.8.1. Эффективность ЛП-поиска, учитывающего структуру задачи.

2.8.2. Исследование эффективности покоординатного поиска, учитывающего структуру задачи.

2.8.3. Эффективность реализаций метода локальной оптимизации, основанного на анализе структуры задачи.

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

ГЛАВА III. ПАКЕТ ПРИКЛАДНЫХ ПРОГРАММ И ЕГО ПРИМЕНЕНИЕ

ДЛЯ РЕШЕНИЯ ПРАКТИЧЕСКИХ 03. ИЗ

3.1. ППП для решения и анализа структуры в диалоговом режиме задач оптимизации при наличии многих экстремумов (МИНИМУМ). ИЗ

3.I.I. Основные характеристики ППП. ИЗ

3.1.2. Функциональное наполнение ДПП.

3.1.3. Диалоговое взаимодействие пользователя с ППП.

3.1.4. Пример работы с ППП.

3.2. Синтез внешней цепи генератора импульсов на ТРАПАТТ-диоде

3.3. Исследование функционирования технологического комплекса оборудования при травлении печатных плат в железо-меднохлоридных растворах.

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

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

На настоящем этапе развития народного хозяйства электронные вычислительные машины (ЭВМ) находят все большее применение в научных исследованиях,в управлении предприятиями, в производстве и в других областях. Сложность решаемых задач быстро возрастает, что требует дальнейшего совершенствования вычислительной техники, ее математического обеспечения. В документе партии и правительства "Основные направления экономического и социального развития СССР на 1981-1985 годы и на период до 1990 года" указывается, что "совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации" является одним из важнейших направлений социально-экономического развития СССР.

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

В [Л замечено, что численные методы оптимизации — бурно развивающийся в настоящее время раздел вычислительной математики. Им посвящена обширная литература. Это вызвано тем, что, как показано в [2], расширение приложений и совершенствование вычислительных средств приводят к резкому усложнению задач оптимизации.

Увеличение сложности 03 вызвало необходимость создания методов анализа этих задач для их рационального изменения.

Анализ методов решения задач математического программирования СЗ-И], особенно задач большой размерности, приведенный в С91, позволяет сделать вывод, что в последнее время все большее внимание уделяется методам, основанным на релаксации ограничений задачи и фиксации ее переменных. Это связано с тем, что математические модели выбора решения для различных производственных и технических задач включают и такие ограничения и переменные, которые не влияют или мало влияют на выбор решения. В [31 рассмотрены необходимые и достаточные условия, позволяющие определить существенные и несущественные ограничения для модели, которая описывается системой линейных неравенств и равенств. В ходе итерационного алгоритма поиска оптимума целевой функции часть ограничений и переменных может также не влиять на дальнейший ход итерационного процесса. Поэтому не только объединяются различные способы релаксации ограничений с методами оптимизации £41, но и разрабатываются итерационные алгоритмы, в основу которых положены различные способы и схемы релаксации ограничений и фиксации переменных. Общий подход к релаксации ограничений в задачах выпуклого программирования изучен в Г51, а в Сб1 применен на квазивогнутые задачи математического программирования. Процедуры сокращения размерности задачи линейного программирования предложены в £7-11]. Их использование дает возможность значительно сократить размерность решаемых задач линейного программирования, после чего получить точное решение, применяя, например, симплекс метод [121.

В общем случае, когда имеется задача ^ rala f(X), •••,xri)€AcR , где А ~ замкнутое множество, и целевая функция, являясь непрерывной, обладает более сложной структурой, упрощение задачи затруднительно. Возможны следующие подходы к упрощению задачи:

- аппроксимация целевой функции сушами функций меньшей размерности;

- трансформирование целевой функции в сепарабельную форму с вводом дополнительных переменных и ограничений;

- отображение точек п-мерного пространства в пространство меньшей размерности;

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

Вопросы аппроксимации функций суммами функций меньшей размерности исследованы в [13,14,151. Для проведения аппроксимации необходимо знание аналитического выражения функции. Например, используя метод аппроксимации, предложенный в [141, проводя аппроксимацию целевой функции .,ха) , определенной на п -мерном единичном гиперкубе, сепарабельной функцией 4 п. где функция ^ аппроксимирует функцию .,ХП), а ик(хк)> К" П., - функции от одной переменной, получается: икСхк) = { (хк) -М- те) \0 > где - среднее значение целевой функции ^ С X ^,., X (О ,а г К \ \( (Хк) = ].1 }(х1,.)хп)с1х^.с1х1<1 ¿х .с(ха о о

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

Многие функции (но не все) могут быть трансформированы в сепарабельную форму с вводом дополнительных переменных и ограничений. В [1б] приведены две стратегии, многократное сочетание которых позволяет реализовать эту трансформацию:

Ь. 2. 2. ^ (Х-О• П.21*2) трансформируется в -у у4 , у^ "" дополнительные переменные); к задаче добавляются дополнительные ограничения:

Ьм

2. Конструкция НГЬГХ)) трансформируется в Н(у) (у -дополнительная переменная); к задаче добавляется ограничение:

КСх)

Например, задача гггса х,еГХ-> + Хг) , однократно применяя первую стратегию и двухкратно вторую, может быть трансформирована в следующую задачу: г 2. тип у, - у2 при ограничениях + = е уз

•А'Чз

К1 + х2 =

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

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

Третий способ упрощения задачи приводится в [17-21]. Используется нелинейное отображение выборочных точек в пространство меньшей размерности в некотором смысле наименее искажающее их геометрическую конфигурацию. Критерий степени искажен-ности геометрической конфигурации, используемый в 117], приводит к простому и эффективному вычислительному алгоритму [18, 19]. В [20,21] применяется незначительно видоизмененный критерий искаженности.

Пусть даны координаты гл. точек в п-мерном пространстве: X = (• • •, Х^ ), I = А, ГЛ. • Пусть в результате некоторого однозначного отображения координаты точек. X преобразованы в координаты соответствующих т точек V - ( у., , ■ ■ ■, у р) , , в пространстве меньшей размерности р (р ^ гь) . При этом расстояния л

X (Хс - х; )

X и X преобразуются между исходными точками А ил преобразуются в расстояния

4; между точками У и .В качестве меры искажения геометрической конфигурации исходных точек введена величина , являющаяся функцией от переменных V Ч

Ее/; с ^

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

Полученная задача оптимизации является многоэкстремальной. В [18] приведена итерационная процедура поиска локального минимума. Использование такого способа сокращения размерности позволяет контролировать и наблюдать за "поведением" алгоритмов многомерного поиска. Такие наблюдения полезны при всестороннем исследовании и сравнении различных поисковых алгоритмов. Кроме того, большая размерность не дает возможности использовать человека для принятия решений на некоторых этапах решения задачи.

Интерес представляет возможность однозначного отображения п п^1 отрезка [0,1] вещественной оси на п.-мерный гиперкуб и с К. Отображения такого рода обычно называют кривыми Пеано [221. Пусть ),гб [ 0,11 есть кривая Пеано. Тогда из непрерывности | (X) и X (%) и равенства 0 = {Х(2); 0 следует, что т.е. решение многомерной задачи минимизации целевой функции

22 , 23 , 24].

Приближенные методы сведения многомерных задач к задачам меньшей размерности на основе некоторого конечного числа известных значений целевой функции и им соответствующих точек аргумента позволяют оценить степени влияния отдельных переменных и в некоторых случаях их групп на точность решения 03. Задачи упрощаются, фиксируя переменные или их группы с наименьшей степенью влияния. тьп {СХ) = тСп } Ш^;), ХеБ 2еМ сводится к минимизации одномерной функции

Для грубой оценки степени влияния переменных или их групп на точность решения 03, в принципе можно использовать методы планирования эксперимента. Оптимизируемая функция в терминах планирования эксперимента представляется как функция отклика, а переменные - как входные и управляемые переменные, которыми исследователь может варьировать по своему усмотрению [25]. К числу методов, которые можно использовать для достижения вышеуказанных целей относятся:

1. Дисперсионный анализ [26] для ввделения линейных эффектов и парных взаимодействий дискретно изменяющихся переменных.

2. Насыщенные дробные факторные планы [27] для ввделения существенных переменных при условии, что доминирующими являются линейные эффекты.

3. Метод случайного баланса [28] для выделения существенных переменных из множества переменных и их парных взаимодействий.

4. Методы отбора переменных в регрессионном анализе:

- метод всех возможных регрессий [29];

- метод исключения [30];

- метод включения [30];

- метод шаговой регрессии [31].

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

Для анализа 03, целевые функции которых имеют сложную структуру, предложен метод ввделения существенных переменных

32]. Созданию этого метода предшествовали работы [33,34]. Результаты исследования метода выделения существенных переменных приведены в [35,36]. Метод предназначен для выявления переменных или их групп, оказывающих наибольшее влияние на точность решения оптимизационной задачи. Его модификация применяется и в задачах планирования экстремальных экспериментов ГЗб]. Метод использует структурные характеристики экстремальных задач [34] и ряды Фурье-Хаара [37]. На основе разложения целевой функции на конечное число членов ряда Фурье-Хаара в [32] показана возможность приведения задачи выделения существенных переменных к ряду задач типа случайного баланса [28].

Как показано в [34] для функции а переменных ( определенной на п-мерном единичном гиперкубе К = { 0 ^ Х^^ -■ 0-6 Ха ^ А } , непрерывной во всех точках, координаты которых недвоично рациональны, существует единственное разложение на "разноразмерные" ортогональные слагаемые: а

•«1 1 2 со свойствами

I 1: : ÍX¿ ,.Хи)с[Х; . с1Х; = 0 К для всех возможных непустых подмножеств

Принимая за меру разброса для составляющих разложения

Dc . £ =f [ft -L .dxL

J LS Ц > ) 4 c, t5 К для ц < * . < ¿s ¿л- f^s^ а) и полагая, что они не равны нулю, совокупность величин D; ; называют структурными ха

1 { s рактеристиками целевой функции ffx1,.jxn)• Характеристики являются оценкой степени влияния отдельных переменных и их групп на точность решения задачи. Здесь под оценкой степени влияния переменных и их групп на точность решения задачи понимается оценка погрешностей, возникающих при упрощении задачи, фиксируя отдельные переменные и их группы, а также при приближенном сведении задачи к ряду задач меньшей размерности.

Примером удачного использования метода ввделения существенных переменных служит анализ структуры при оптимальном проектировании магнитной отклоняющей системы (МОС) [38]. Задача оптимального проектирования МОС состоит в минимизации целевой функции f(xit.-.,xi3) , алгоритм определения значений которой сравнительно сложный, содержащий численное интегрирование системы дифференциальных уравнений движения электронов в магнитном поле МОС. Машинное время определения значения целевой функции в одной точке равно 21 секунде для БЭСМ-6, что усложняет решение задачи, выбор алгоритма оптимизации. Анализ структуры проводился по 150 результатам испытаний целевой функции. Установлено, что задача близка к сепарабельной - анализ показал, что взаимодействия переменных малы. При сравнении пяти известных алгоритмов оптимизации [39], наилучщим оказался покоординатный поиск, сконструированный на базе алгоритма одномерного поиска [40],т.е. учет специфики структуры оптимизационной задачи помог эффективно выбрать алгоритм оптимизации.

Недостатком метода вьщеления существенных переменных является большая зависимость времени работы на ЭВМ алгоритмической реализации метода от числа вццеляемых структурных характеристик и от числа испытаний целевой функции, предъявляемых для анализа. Это затрудняет проведение оптимального разбиения задачи на несколько задач меньшей размерности, т.е. нахождение такого разбиения переменных на m непересекающихся групп Ал,., Аm , чтобы минимизировать i . ZDt,.ts-i:r. . , где mL- число переменных в группе > Dir.i5 - структурные характеристики задачи, целевая функция которой ^ (Х^ е А^) получена из функции f fX1,.■., Хп) , фиксируя переменные, не принадлежащие группе А^ .

Обзор методов оптимизации, эффективность которых зависит от структуры решаемой задачи.; Для решения 03 широкое применение нашли методы случайного поиска [4I,42j. Для определения "первого приближения", начиная с которого решение уточняется локальными методами, часто применяют глобальный поиск. Простейший

У min глобальный поиск точки минимума Л состоит в выборе в обла

У* Vm сти определения каких-то точек Л,.» Л , вычислении в каждой из них значений целевой функции fiX) и отборе точки Х° в которой мгмоо, i - . Точка Л служит приближе уmin г, нием к точке минимума л • При простейшем случайном поиске [43J в качестве X выбираются независимые случайные точки, равномерно распределенные в области определения.

Чем более равномерно распределены точки, тем лучших результатов можно ожидать от поиска. Можно построить системы таких точек, которые расположены более равномерно, чем случайные как в п-мерном единичном гиперкубе, так и в проекциях меньшей размерности. Перечисленным требованиям удовлетворяют точки ЛП-пос-ледовательности построенной в [ 37].

Если двоичное разложение номера то расчет точки у П.) проводится следующим образом: где V заданы таблично, знак Ж означает поразрядное сложе

-V ние по модулю 2 в двоичной системе.

В [37] приведена таблица для вычисления точек в единичном гиперкубе К П размерностью п= 13, а в [44] - размерностью о.= 51. В [44,45] приведены тексты программ на языке программирования ФОРТРАН для определения точек ЛП-последователь-ности.

ЛП-поиском называется простейший поиск, в котором пробными

А й точками служат точки , образующие ЛП-последовательность, т.е. ЛП-поиск является детерминированным аналогом простейшего случайного поиска. Сравнение ЛП-поиска с простейшим случайным поиском проводилось на многих задачах [46,47,48] и неизменно ЛП-поиск оказывался более эффективным.

Эффективность ЛП-поиска зависит от структуры задачи, где под структурой понимается степень влияния отдельных переменных или их групп на точность решения. Как установлено в [49], ЛП-поиск без учета структуры задачи не всегда эффективен. Это относится особенно к задачам с выраженными взаимодействиями переменных. Основанием для исследования зависимости ЛП-поиска от структуры задачи служило следующее

49]:

I. ЛП-последовательности задаются на п-мерном единичном гиперкубе К П • В С37] показано, что для размерности Я * 4 в принципе нельзя построить последовательности, различные проекции которых на всех разноразмерных гранях , где Кц.^

5-мерная грань гиперкуба К п> С< С5 £ 5$ п , были бы расположены равномерно. Поэтому возникает вопрос, для каких проекций ДП-последовательности наиболее равномерны.

2. "Качество" начальных участков ЛП-последовательностей, длина которых для д>5 достигает тысяч чисел, зависит от выбора таблицы так называемых направляющих чисел в генераторе ЛП-последовательностей.

3. В [37] указывается, что направляющие числа подобраны так, чтобы проекции ЛП-последовательности на двух- и трехмерные грани вида + 1 и ^¿,¿ + >1,1 + 2. ^ыли Х0Р0ШИМИ ПРИ малых I .

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

В [49] доказано, что в случаях хорошего распределения проекций точек на грани существенных переменных ЛП-поиск бывает более эффективным. Ввдвинуто два требования к рациональной нумерации переменных:

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

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

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

Другой метод оптимизации, эффективность которого зависит от структуры решаемой задачи - покоординатный поиск. В общем случае метод покоординатного поиска минимума оптимизируемой функции может быть записан как последовательность точек аргумента [501: где {£ }г 6 п } - стандартный базис в ^ [ 100]: 61 = (1,0,.,0), е2= (0,1,.,0),., £Л= (0,0,.,1);1пк+1 лк+l--/

-te-,

I ' выбирается так, чтобы минимизировать fix) по прямой/

L- номер малой итерации метода; к - номер большой итерации метода.

Возможно два варианта покоординатного поиска в зависимости от тогоД+ i выбирается во всей области изменения переменной Х1 или в окрестности точки аргумента X" +L : глобальный и локальный.

Метод покоординатного поиска не вызвал большого "интереса в связи с малой скоростью сходимости [51]. По сравнению с методом наискорейшего спуска [52], метод покоординатного поиска сходится в п. раз медленнее. Преимущество покоординатного поиска заключается в том, что он не требует вычисления градиента целевой функции и, что одномерный поиск, в многократное повторение которого сводится покоординатный поиск, является наиболее развитой частью методов оптимизации.

Малая скорость сходимости обусловлена тем, что не оптимально выбирается система координат для покоординатного поиска. Например, система координат для минимизации целевой функции-ffx., jj^-^fx«,- х2)2+('х1+х2)2 методом покоординатного поиска выбрана неудачно. Если сделать преобразование системы переменных X в новую систему , уп) следующего ввда: V? № ! где X и У векторы-столбцы, составленные из элементов векторов-строк X и У , то минимум целевой функции можно найти за одну большую итерацию локального покоординатного поиска, начиная его из любой точки области определения. Как следствие, одним из направлений к развитию анализа структуры 03, является создание методов, позволяющих найти оптимальную систему координат. Используя метод вьщеления существенных переменных [32], этого сделать невозможно.

Преобразование системы координат нашло применение в локальной оптимизации. В [53] предложено семейство методов для решения задач выпуклого программирования, основанных на применении линейных преобразований пространства для симметризации областей локализации точек минимума, возникающих при использовании схем отсечений. Новая система координат вводится в зависимости от формы области, где локализован минимум и которая представляет собой выпуклую фигуру, высекаемую в шаре некоторой совокупностью плоскостей. В [54,55,56] развит подход, комбинирующий схемы отсечений и линейные преобразования в пространстве переменных для получения эффективных методов решения задач выпуклого программирования. В [57] предлагается процедура введения криволинейных координат для повышения эффективности некоторых методов минимизации выпуклых функций, использующих собственные векторы матрицы вторых производных, на случай невыпуклых функций. Минимизация осуществляется вдоль векторов, являющихся собственными по отношению к матрице вторых производных во вновь введенных координатах. В исходных же координатах спуск осуществляется вдоль некоторых кривых.

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

Группировка параметров на основе корреляционной матрицы осуществима используя метод корреляционных плеяд [59-61] и селективный метод автоматической классификации Г 62,63]. Метод экстремальной группировки параметров [58,64] и эвристический алгоритм разбиения параметров на группы, предложенный в [65], позволяют проводить группировку параметров на основе как корреляционной, так и ковариационной матрицы. Метод корреляционных плеяд и метод экстремальной группировки параметров в [66] отнесены к эвристическим методам снижения размерности. Селективный метод автоматической классификации допускает возможность одновременного попадания классифицируемых параметров в разные группы.

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

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

Требования к программному обеспечению для решения 03. В настоящее время разработано большое количество численных методов оптимизации. Но, как замечено Ю.Г.Евтушенко в приложении к книге [67], сейчас не существует, да, по-видимому, и не будет существовать наилучшего во всех отношениях универсального метода оптимизации. Разумное сочетание разнообразных методов, а не поиск универсального метода, позволяет с наибольшей эффективностью решать поставленные задачи. Поэтому необходимо объединение в пакеты прикладных программ (ППП) разнообразных программ оптимизации, что облегчает осуществление перехода от одного метода решения задачи к другому.

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

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

Решение действительно больших задач требует неформальных действий вычисляющего, возможности вмешиваться в процесс счета — так называемого диалогового режима. Эффективность диалогового режима решения задач оптимизации экспериментально доказана в [69].

Из вышесказанного вытекают следующие требования к программному обеспечению для решения 03:

1. Программы, реализующие методы решения и анализа структуры 03, должны быть объединены в ППП.

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

3. Необходимо наличие в ППП средств ведения диалога пользователя с ЭВМ.

Программы пункта I в [70] отнесены к функциональному наполнению (ФН) ППП, а программы пунктов 2 и 3 - к системному наполнению (СН) ППП.

В [71] приведены следующие общие требования к прикладному программному обеспечению, которые могут быть отнесены и к пакетам оптимизационных программ:

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

2. Эффективность реализованных алгоритмов.

3. Простота и удобство в эксплуатации.

4. Надежность алгоритмов и программ.

5. Расширяемость состава алгоритмов и программ.

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

Особенно важно последнее требование, так как постоянно усовершенствуются операционные системы существующих ЭВМ, разрабатываются новые типы ЭВМ. Транспортабельности программного обеспечения посвящена обширная литература (см., напр., [72,73]).

Примером разработки, которая заранее предполагает распространение произведенной программной продукции на ряд заранее определенных вычислительных систем, может служить port -библиотека [74,75]. Программы написаны на языке, являющемся общим подмножеством всех диалектов, включенных в проект системы (подмножество стандарта языка программирования ФОРТРАН). Учет машинной зависимости сводится к возможности замены вручную в теле трех функций-подпрограмм значений машинно- и операционно зависимых констант.

Таким образом можно обеспечить транспортабельность ФН ППП для решения 03, программы ФН составляя на стандартном языке программирования ФОРТРАН [76].

Транспортабельность GH ППП обеспечить трудно, так как СН обладает большой привязанностью к конкретным ЭВМ и операционным системам. В случае транспортабельности ФН, при переходе к новому типу ЭВМ, СН приходится переделывать. Это не очень трудно, создавая СН с помощью инструментально-базовых систем, включающих наряду со средствами формирования СН и средства, используемые в ходе эксплуатации ППП. К таким системам относятся ПРИЗ [77J, СПОРА [78], ИСП [79], ПУПМ [80], ДИАЛОГ [81]. Используя последнюю систему, разработана известная диалоговая система оптимизации ДО СО для решения задач безусловной минимизации функций многих переменных, нелинейного программирования и оптимального управления (см.,напр.,[82,83]). Применение инструментальной системы (ИС) ДИАЛОГ облегчает изменение стандартных возможностей системы ДИ[СО и расширение их новыми диалоговыми возможностями.

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

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

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

2. Разработка и исследование модификаций методов оптимизации — ЛП-поиска и покоординатного поиска, учитывающих структуру решаемой задачи, и метода локальной оптимизации, основанного на анализе структуры решаемой задачи.

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

Для решения первой задачи необходимо решение следующих подзадач:

1. Ввод для 03 интегральных характеристик, описывающих их структуру.

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

3. Исследование возможностей применения методов многомерного статистического анализа — метода главных компонент и метода экстремальной группировки параметров для анализа результатов оценки.

- 24

4. Разработка и исследование новой реализации метода экстремальной группировки параметров.

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

- ввести для задачи новую, в некотором смысле оптимальную, систему координат;

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

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

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

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

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

Во второй главе приводятся результаты экспериментального исследования эффективности разработанного метода анализа структуры 03 и связанных с ним методов оптимизации.

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

- качества оценки интегральных характеристик 03 по результатам испытаний целевой функции и определения оптимальной системы координат;

- реализации метода экстремальной группировки параметров;

- качества оценки степени влияния переменных и их групп на точность решения 03;

- сравнительной эффективности методов анализа структуры 03;

- эффективности ЛП-поиска, учитывающего структуру задачи;

- эффективности покоординатного поиска, учитывающего структуру задачи;

- эффективности реализаций метода локальной оптимизации, основанного на анализе структуры задачи.

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

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

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

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

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

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

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

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

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

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

ДР.

Связь с научной тематикой института. Настоящая работа выполнена в отделе теории оптимальных решений Института математики и кибернетики АН Литовской ССР в соответствии с научно-исследовательскими плановыми темами: "Исследование методов глобальной оптимизации и их применение для задач проектирования" (№ гос.регистрации 81025172), "Разработать и сдать в ШАЛ пакет прикладных программ многоэкстремальной оптимизации для решения задач автоматизированного проектирования" (№ гос. регистрации 0181.4013792).

Основные результаты диссертационной работы опубликованы в [84-97] и докладывались на:

- республиканских семинарах "Теория оптимальных решений" (г.Вильнюс, 1980, 1981, 1982, 1983, 1984гг.);

- республиканской конференции "Программное обеспечение ЭВМ" (г.Молетай, 1981 г.);

- республиканской научно-технической конференции (г.Каунас, 1982 г.);

- XXIII конференции Литовского математического общества (г.Каунас, 1982 г.);

- республиканском координационном совещании "Црограммное обеспечение ЭВМ" (г.Молетай, 1983 г.);

- ХХ1У конференции Литовского математического общества (г.Вильнюс, 1983 г.);

- ХХУ конференции Литовского математического общества (г.Шяуляй, 1984 г.).

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

1. Пакет программ для решения и анализа оптимизационных задач (МИНФОР).

2. Пакет прикладных программ для решения многоэкстремальных задач проектирования на МВК ЭЛЬБРУС (ОПТИМУМ).

3. Пакет прикладных программ для решения в диалоговом режиме задач оптимизации при наличии многих экстремумов (МИНИМУМ).

Программа Г.Дземиды ЬРМПГ, реализующая метод ЛП-поиска, учитывающего структуру оптимизационной задачи, включена в состав методоориентированного ППП для решения задач проектирования и управления. Пакет разрабатывается в Институте технической кибернетики АН БССР в соответствии с планом СП-1 Совета по применению средств вычислительной техники в 1981-1985 гг. (тема 1.12).

Тульский политехнический институт использует разработанные Г.Дземидой алгоритмы и программы при создании диалоговой ситемы многокритериальной оптимизации параметров машин и конструкций (М0ПТ1), которая применяется при выполнении темы: "Исследовать и разработать методики расчета и выбора основных параметров струговых агрегатов для безлюдной выемки тонких и пологих пластов" (№ 0113207000). Использование этих программ в пакете М0ПТ1 позволяет сократить время поиска оптимальной совокупности параметров на 20 %.

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

Результаты диссертационной работы использованы при исследовании и разработке макетов генераторов испульсов на ТРАДАТТ-дио-де. Разработанные на кафедре радиофизики Вильнюсского госуниверситета им. В.Капсукаса макеты применялись для проведения бюджетных научно-исследовательских работ по теме № 81054128.

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

Экономический эффект, полученный от внедрения результатов работы, составляет 28,15 тысяч рублей в год.

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

1. Разработанный пакет прикладных программ МИНИМУМ позволяет решать многоэкстремальные задачи оптимизации и анализировать их структуру в диалоговом режиме.

2. Достоинствами пакета являются:

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

- транспортабельность основных программ функционального наполнения;

- удобное общение с ППП, что позволяет расширить круг его пользователей;

- возможность сочетания диалогового режима работы с пакетным в одном сеансе работы;

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

- возможность расширения пакета.

3. ППП МИНИМУМ применялся для решения следующих практических задач:

- синтеза внешней цепи генератора импульсов на ТРАПАТТ-диоде;

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Применение результатов работы позволило с большей эффективностью решить ряд практических задач. Решены: задача синтеза внешней цепи генератора импульсов на ТРАПАТТ-диоде; задача расчета параметров электрохимической адсорбции по данным измерений частотной зависимости модуля электродного импеданса; задача определения доли экстенсивного компонента в равновесном эстансе; задача исследования функционирования технологического комплекса оборудования при травлении печатных плат в железо-меднохлоридных растворах с целью выбора оптимального состава раствора и режима работы комплекса; задачи, возникшие в Тульском политехническом институте при выполнении работ по теме "Исследовать и разработать методики расчета и выбора основных параметров струговых агрегатов для безлюдной выемки тонких и пологих пластов".

Экономический эффект, полученный от внедрения результатов работы, составляет 28,15 тысяч рублей в год.

1. Ццин Д.Б., Горяшко А.П., Немировский A.C. Математические методы оптимизации устройств и алгоритмов АСУ. — М.: Радио и связь, 1982. - 288 с.

2. Немировский A.C., ЛЦцин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. - 384 с.

3. Benders J.P. Minimal representation of convex polyhedrol sets. Techn.hoolesh. Eindhoven, onderafdel. wisk.rept., 1980, No 5, p. 1-11.

4. Ащенков Л.Т., Константинов Г.Н. Эффект "срезки" в задачах нелинейного программирования. Журнал вычислительной математики и математической физики, 1976, т.16, № 4, с.1047--1051.

5. Лэсдон Л.С. Оптимизация больших систем. М.: Наука, 1975. - 431 с.

6. Алексейчик М.И., Калюжный Г.В. Теоретическое обоснование и алгоритмы релаксации для задач квазивогнутого программирования. — Известия АН СССР. Техническая кибернетика, 1980, с.37-43.

7. Йослович И.В., Макаренков Ю.М. О методах сокращения размерности задач линейного программирования. — Экономика и экономические методы, 1975, т.XI, вып.З, с. 516-524.

8. Данильченко И.А., Макаренков Ю.М., Пшенова Э.Ф. Метод предварительного сокращения размерности задачи линейного программирования с неотрицательной матрицей условий. Кибернетика, 1980, № 3, с. 103-106.

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

10. Михалевич B.C., Волкович В.Л., Волошин А.Ф. Метод последовательного анализа в задачах линейного программирования большого размера. Кибернетика, 1981, № 4, сЛ14-120.

11. Нервозванский А.А., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. М.:Наука, 1973. - 342 с.

12. Юдин Д.Б., Голыптейн Е.Г. Задачи и методы линейного программирования. — М.: Сов.радио, 1964. 736 с.

13. Diliberto S.P., Straus E.G. On the approximation of a function of several variables by a sum of functions of fewer variables. — Pacific Journal of Mathematics, 1951, Ho 1,p. 195-210.

14. Golomb M. Approximation by functions of fewer variables. — In: On numerical approximation: Proceedings of a Symposium

15. Conducted by the Mathematics Research Center. Madison: Univ. of Wisconsin press, 1959, p. 275-327.

16. Kelley C.T. A note on the approximation of functions of several variables by Sums of functions of one variable, — Jour^ nal of Approximation theory, 1981, No 33, p. 179-189*

17. Cooper L., Cooper M.W. Introduction to Dynamic programming. — Pergamon international library: International series in modern applied mathematics and computer science. Pergamon press pranklin printing House, 1981, vol. 1, 289 p.

18. Sammon H. A nonlinear mapping for data structure analysis IEEE Trans.Comp., 1969» vol. C-18, Ho 5, p.401-409.

19. Шалтянис В. Об интерпретации результатов многомерной оптимизации. — В кн.: Теория оптимальных решений. Вильнюс, 1975, вып.I, с. 43-52.

20. Шалтянис В.Р. Отображение точек многомерного пространства в пространство меньшей размерности. ШАЛ П001298, Вильнюс, 1975. - II с.

21. Kruskal J,В. Multidimensional scalling Ъу optimizing goodness of fit to a nonmetric hypothesis. — psychometrica, 1964, vol.29, По 1, p. 1-27.

22. Kruskal J.B. Nonmetric multidimensional scalling: a numerical method. Psychometrica, 1964, vol.29, Ho 2, p.115-129.

23. Стронгин P.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). — М.: Наука, 1978. 240с.

24. Стронгин Р.Г. 0 сходимости одного алгоритма поиска глобального экстремума. Известия АН СССР. Техническая кибернетика, 1973, № 4, с. 10-16.

25. Стронгин Р.Г. Непрерывное отображение отрезка на гиперкуб (СП-0170 для ИС-2, Алгольная процедура, фортран-подпрограмма). Г$АП П002187, Горький, 1977. - 59 с.

26. Красовский Г.И., Филаретов Г.Ф. Планирование эксперимента.- Мн.: Изд-во БГУ, 1982. 302 с.

27. Шеффе Г. Дисперсионный анализ. М.: Наука, 1980. - 512 с.

28. Хартман К., Лецкий Э., Шефер В. Планирование эксперимента в исследовании технологических процессов. М.: Мир, 1977.- 552 с.

29. Мешалкин Л.Д. К обоснованию метода случайного баланса. — Заводская лаборатория, 1970, № 3, с. 316-318.

30. Schatzoff M., Fienberg S., Tsao R. Efficient calculation of all possible repressions. — Теchnometries, 1968, vol.10, По 4, p. 769-779.

31. Дрейпер H., Смит Г. Прикладной регрессионный анализ. М.: Статистика, 1973. - 321 с.

32. Efroymson М.А. Multiple repression analysis. In: Mathematical methods for digital computers. ITew York: Wiley, I960, p. 191-203.

33. Шалтянис В., Радвилавичюте Я. Вьщеление существенных переменных в задачах оптимизации. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1977, вып.З, с.57-71.

34. Шалтянис В., Варнайте А. Об одном методе уменьшения размерности при решении многоэкстремальных задач. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1975, вып.1, с. 23-42.

35. Шалтянис В., Варнайте А. Вопросы структуры многоэкстремальных задач оптимизации. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1976, вып.2, с. 67-78.

36. Шалтянис В.Р., Радвилавичюте Я.Г. Исследование алгоритма выделения существенных переменных. — В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1980, вып.6, с.41-47.

37. Соболь И.М. Многомерные квадратурные формулы и функции Хаа-ра. М.: Наука, 1969. - 288 с.

38. Zilinskas A. Results of the application of Multimodal optimization of algorithms of statistical models. In: proceedings of the 5-th Sympos ium held at Toulouse 1982, COMPSTAT, 1982, p. 457-462.

39. Zilinskas A. Two algorithms for one-dimensional multimodal minimization. Math. Oper. Stat., ser. Optimization, 1981, vol.12, p. 53-63.

40. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. - 376 с.

41. Растригин Л.А. Структурная адаптация алгоритмов случайного поиска. — В кн.: Вопросы кибернетики. М.: Научный совет по комплексной проблеме "Кибернетика" АН УССР, 1978, вып. 45, с.5-12. (Случайный поиск в задачах оптимизации).

42. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973. - 312 с.

43. Соболь И.М., Левитан Ю.Л. Получение точек, равномерно распределенных в многомерном кубе. М.: ИПМ, препринт № 40 за 1976 г. - 20 с.

44. Sobol' I.M. On the Systematic search in a hypercube. SIAM J.Numer.Anal., 1979, vol.16, No 5, p. 790-793.

45. Соболь И.М., Статников P.Б. ЛП-поиск и задачи оптимального конструирования. В кн.: Проблемы случайного поиска. Рига: Зинатне, 1972, № I, с. II7-I35.

46. Шалтянис В. Исследование эффективности ЛП-поиска на классе многоэкстремальных задач. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1976, вып.2, с. 59-66.

47. Сакалаускас Л. Сравнение одной последовательности псевдослучайных точек и ЛП -последовательности. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1981, вып.7, с. I06-II5.

48. Шалтянис В. Эффективность ЛП-поиска и структура задач оптимизации. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1982, вып.8, с. II5-I23.

49. Abatzolgon T., Donne11 Б, Minimization Ъу coordinate olescent. — Journal of optimization theory and applications, 1982, vol. 36, No 2, p. 163-174.

50. Luenherger D.G. Introduction to linear and nonlinear programming. — Massachucetts: Addison-Wessley, 1970.-243 p.

51. Dimitri P. Bertsekas. Projected Newton methods for optimization problems with Simple constraints. SIAM J.Control and Optimisation, 1982, vol.20, No 2, p. 221-246.

52. Шор Н.З. Методы отсечения и растяжения пространства для решения задач выпуклого программирования. — Кибернетика, 1977, № I, с. 94-95.

53. Скоков В.А. Замечание к методам минимизации, использующим операцию растяжения пространства. Кибернетика, 1974, № 4, с. 115—117.

54. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач выпуклого программирования. — Кибернетика, 1979, № 4, с. 62-67.

55. Гершович В.И. Об одном методе минимизации, использующем линейное преобразование пространства. В кн.: Теория оптимальных решений. Киев: ИК АН УССР, 1980, с. 38-45.

56. Редковский H.H. Использование криволинейных координат для минимизации невыпуклых функций. Кибернетика, 1982, № 2, с. 117—118.

57. Браверман З.М. Методы экстремальной группировки параметров и задача вьщеления существенных факторов. Автоматика и телемеханика, 1970, № I, с. 123-132.

58. Терентьев П.В. Метод корреляционных плеяд. Вестник ЛГУ, Л.: ЛГУ, 1959, № 9, с. I37-I4I. (серия биологии, вып.2).

59. Терентьев П. В. Дальнейшее развитие метода корреляционных плеяд. — В кн.: Применение математических методов в биологии. Л.: ЛГУ, i960, с. 27-36.

60. Выхаццу Л.К. Об исследовании многопризнаковых биологических систем. В кн.: Применение математических методов в биологии. Л.: ЛГУ, 1964, с. 19-22.

61. Расчубкин В.Г., Дубровский С.А., Бобриков Э.Л. Селективный метод автоматической классификации. Изв.высш.учеб.заведений. Черная металлургия. 1978, № 6, с. 160-163.

62. Дубровский С.А. Прикладной многомерный статистический анализ. — М.: Финансы и статистика, 1982. 216 с.

63. Браверман Э.М., Дорофеюк A.A., Лушельский В.Я., Мучник

64. И.Б. Диагонализация матрицы связи и выявление скрытых факторов. — В кн.: Проблемы расширения возможностей автоматов. М.: ИПУ, 1971, вып.1, с. 42-49.

65. Лушельский В.Я. Группировка параметров на основе квадратичной матрицы связи. — Автоматика и телемеханика, 1970, № I, с. 133-143.

66. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика, 1974. - 240 с.

67. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978. - 352 с.

68. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982. 432 с.

69. Шалтянис В.Р. Анализ задач в диалоговых системах оптимиза— ции. — В кн.: Применение методов случайного поиска в САПР: Материалы всесоюзного научно-технического совещания, ч.1. Таллин, 1980, с. II8-I23.

70. Корягин Д.А., Мартынюк В.В. Развитие проблематики системного обеспечения пакетов прикладных программ в СССР. — В кн. : Пакеты прикладных программ: Проблемы и перспективы. М.: Наука, 1982, с. 124-139.

71. Ершов А.П., Ильин В.П. Пакеты программ как методология решения прикладных задач. В кн. : Пакеты прикладных программ: Проблемы и перспективы. М.: Наука, 1982, с. 4-18.

72. Мобильность программного обеспечения (ред. П.Браун). М.: Мир, 1980. - 336 с.

73. Арушанян О.Б., Волченскова Н.И. Общие проблемы транспортабельности фортранных программ. — В кн.: Вычислительные методы и программирование. М.: МГУ, 1980, вып.33, с. 144-160.

74. Fox Р.А., Hall A.D., Schryer N.L. The PORT mathematical subroutine library. ACM Transactions on Mathematical software, 1978, vol.4, Ho 2, p. 104-126.

75. Fox P.A., Hall A.D., Schryer N.L. ALGORITHM 528. Framework for a Portable Library — ACM Transactions on Mathematical software, 1978, vol.4, No 2, p. 177-188.

76. Язык программирования ФОРТРАН. ГОСТ 23056-78.

77. Кахро M.И., Мяннисалу М.А., Саан Ю.П., Тыугу Э.Х. Система программирования ПРИЗ. — Программирование, 1976, № I, с. 38-46.

78. Мельников И.А., Мяртин К.О., Прууден Э.В. и др. Метасистема для создания информационно-связанных специализированных систем программирования. — Кибернетика, 1974, № 6, с.69-73.

79. Шалтянис В. Программа управления пакетами модулей на проблемно-ориентированном языке. — В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1981, вып.7, с. II6-I32.

80. Веселов E.H. Инструментальная система для построения диалоговых пакетов программ. Дис. . канд.физ.-мат.наук. — М.: ВЦ АН СССР, 1980.

81. Бурдаков О.П., Веселов E.H., Голиков А.И. и др. Диалоговая система оптимизации. ГМП П004649, М.: ВЦ АН СССР, 1980. - 142 с.

82. Веселов E.H., Евтушенко Ю.Г., Мазурик В.П. Диалоговая система оптимизации ,ЩС0-2. — В кн.: Пакеты прикладных программ: Проблемы и перспективы. М.: Наука, 1982, с. 46-57.

83. Дземида Г. Портативность программных библиотек. — В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1981, вып.7, с. 41-48.

84. Дземида Г. К вопросу об экстремальной группировке параметров. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1982, вып.8, с. 46-53.

85. Шалтянис В., Дземида Г. Анализ структуры оптимизационных задач с использованием аппроксимации характеристик. — В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1982, вып.8, с. 124-138.

86. Валявичене Ю.-Т.П., Дземида Г.А., Жилинскас А.Г., Тешис

87. В.А., Шалтянис В.Р., Моцкус Й.Б. Пакет программ для решения и анализа оптимизационных задач (МИНФОР). ШАЛ П005760, Вильнюс, 1981. - 27 с.

88. Дземида Г.А., Шалтянис В.Р. Применение анализа структуры оптимизационных задач при их решении. В кн.: ХХ1У конф. Лит.матем.общ.: Тез.докл. Вильнюс, 1983, с. 73-74.

89. Дземида Г. Исследование метода анализа структуры оптимизационных задач и его применение в локальной оптимизации. -В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1983, вып.9, с. 21-38.

90. Дземида Г. ЛП-поиск, учитывающий структуру оптимизационной задачи. В кн.: Теория оптимкльных решений. Вильнюс: ИМК АН ЛитССР, 1983, вып.9, с. 77-82.

91. Дземида Г. Характеристики пакета прикладных программ для решения в диалоговом режиме задач оптимизации при наличии многих экстремумов (МИНИМУМ). В кн.: Программное обеспечение ЭВМ: Тез.докл. координационного совещания. Молетай, 1983,с. 128-130.

92. Дземида Г.А. Алгоритм ЛП-поиска, учитывающий структуру оптимизационной задачи. — В кн.: Разработка и внедрение АСУП и АСУ ТП. Иркутск, 1983, с. 5-7.

93. Шалтянис В., Дземида Г. Исследование структурных характеристик оптимизационной задачи. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1983, вып.9, с. 77-82.

94. Дземида Г. Методы оптимизации, связанные с анализом структуры задачи. — В кн.: ХХУ конф. Литов.матем.общества: Тез. докл., Шяуляй, 1984, с. 102-103.

95. Дземида Г. Пакет прикладных программ МИНИМУМ. В кн. : Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1984, вып. 10, с. 64-76.

96. Дземида Г. и др. Решение задач оптимального проектирования и выбора значений параметров модели с использованием пакета прикладных программ МИНИМУМ. — В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1984, вып.10, с. 77-98.

97. Петрий О.А., Малышева Ж.Н., Казаринов В.Е., Андреев В.Н. Адсорбция катионов цинка на платиновом электроде. Электрохимия, 1971, т.7, вып.II, с. I689-1694.

98. Лоули Д., Максвелл А. Факторный анализ как статистический метод. М.: Мир, 1967. - 144 с.

99. Шилов Г.Е. Математический анализ: Конечномерные линейные пространства. — М.: Наука, 1969. 432 с.

100. Растригин Л.А. Случайный поиск в задачах оптимизации многопараметрических систем. — Рига: Зинатне, 1965. 209 с.

101. Dixon L.C.W., SzegO G.P. The global optimisation problem:

102. An introduction. — In: Towards global optimisation 2. North-Holland, 1978, p. 1-15.

103. Лучанская Х.И., Хевролин В.Я. Решение задачи Л.И.Мандельштама. — Радиотехника, 1974, № 12, с. 1-5.

104. Химельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975. 536 с.

105. Вентцель Е.С. Теория вероятностей. М.: Гос.изд.физ.-матем. лит., 1958. - 464 с.

106. Небылицин В.Д. Основные свойства нервной системы человека. М.: Просвещение, 1966. - 383 с.

107. Кведарас Б., Сапаговас М. Вычислительные методы. Вильнюс: Минтис, 1974. - 516 с.

108. Голенко Д.И. Статистические модели в управлении производством. М.: Статистика, 1973. - 368 с.

109. Mifflin R.A. A superlineary convergent algorithm for minimization without evaluating derivatives. — Mathematical Programming, 1975, No 9, p. 100-117.

110. Пасынков И.Г. М0НИТ0Р-80: Описание языка управления заданием. Инструкция для пользователей ЦВК по оформлению задания для счета на ЭВМ БЭСМ-6. М. : ИАЭ им.И.В.Курчатова, 1981. - 15 с.

111. Моцкус Й.Б. 0 байесовых методах поиска экстремума. Автоматика и вычислительная техника, 1972, № 3, с. 53-62.

112. Torn A.A, A search clustering approach to global optimisation. - In: Towards global optimisation 2. North-Holland, 1978, p. 49-62.

113. Zilinskas A. Axiomatic approach to statistical models and their use in multimodal optimisation theory. — Mathematical Programming, 1982, vol.22, No 1, p. 104-116.

114. Hull Т.Е., Dobell A.R. Random number generators. SIAM Review, 1962, vol.4, No 3, p. 230-254.

115. Тешис В.А. Метод переменной метрики для локальной минимизации функций многих переменных с прямоугольными ограничениями. В кн.: Вычислительная техника: Материалы конф. Каунас, 1975, с. III-II4.

116. Бараускас А.В. Оптимально обусловленный класс методов переменной метрики. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1982, вып.8, с. 9-19.

117. Biggs M.C. Constrained minimisation using recursive quadratic programming: some alternative subproblem formulations. — In: Towards global optimisation. North-Holland, Americal Elsevier, 1975, p. 341-349.

118. Лавров С.С. Универсальный язык программирования (АЛГОЛ-60). М.: Наука, 1972. - 183 с.

119. Карпов В.Я. Алгоритмический язык ФОРТРАН. М.: Наука, 1976. - 192 с.

120. Джермейн К. Программирование на IBM/360. 3-е изд., стереотипное. - М.: Мир, 1978. - 870 с.

121. Бардин В.В., Поминов П.В., Руднев А.П. М0НИТ0Р-80: Ввод/ /вывод в мониторной системе "ДУБНА". — М.: ИАЭ им.И.В.Курчатова, 1982. 57 с.

122. Вайтекунас Ф., Вишняускас Ю., Сакалаускас Л. Оптимизация параметров внешней цепи ТРАПАТТ генератора. В кн.: Перспективы развития технических наук в республике и использование их результатов: Тез.докл. республиканской конф. Каунас, 1982, с. II8-II9.

123. Коцержинский Б. А. Параметрический синтез ШЩ на ЭВМ. — В кн.: Электроника сверхвысоких частот: Тез.докл. X всесоюзной научной конф.^ т.2. Минск, 1983, с. 375-376.

124. Вайтекунас Ф.К., Вишняускас Ю.Б., Камальдинов Ш.А., Филатов Н.Ю., Шилинас Г.Э. Анализ внешней цепи генератора импульсов на ТРАПАТТ-диоде. Техника средств связи, 1981,35, с. 11-17. (серия "Радиоизмерительная техника", вып.З).

125. Юзефович Д.К. и др. Исследования условий регенерации желе-зо-меднохлоридных растворов травления меди с помощью алгоритма вццеления существенных переменных. В кн.: Теория оптимальных решений. Вильнюс: ИМК АН ЛитССР, 1984, вып.10.

126. Пропоров A.M. и др. Расчет себестоимости операции травления печатных плат в рецикле с регенерацией. Обмен опытом в радиопромышленности, 1979, вып.10, с. 61-63.

127. Гохштейн А.Я. Поверхностное натяжение твердых тел и адсорбция. М.: Наука, 1976. - 400 с.

128. Sluyters J.H., Oomen J.J .С. On the impedance of galvanic cells. Recueil, I960, vol.79, p.1101-1110.

129. Иошида Т., Осака Т. Исследование адсорбции водорода на платиновом электроде с помощью динамических импедансных измерений. Электрохимия, 1978, т.14, вып.5, с.692-694.