Книга
← К списку книгЗагрузка разделов…
активнаАктивные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.
Книга
АКАДЕМИЯ НАУК СССР ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М. В. КЕЛДЫША
И. М. СОБОЛЬ, Р. Б. СТАТНИКОВ
ВЫБОР ОПТИМАЛЬНЫХ ПАРАМЕТРОВ
В ЗАДАЧАХ СО МНОГИМИ КРИТЕРИЯМИ
в
ИЗДАТЕЛЬСТВО «НАУКА» МОСКВА 1981
УДК 518.5
Соболь И. М., С т а т н и к о в Р. Б. Выбор оптимальных параметров в задачах сомногими критериями. М.: Наука, 1981.
Книга содержит разработанную авторами методику постановки, изучеппя и решения задач, в которых необходимо выбрать иаи- лучшим образом несколько параметров с учетом нескольких критериев качества. Наиболее примечательная особенность этой методики — использование ЭВМ не только для решения задачи, но и для ее постановки. Приведен численный метод приближенного построения компромиссных кривых. Отдельная глава содержит краткие сведения об Л ^-последовательностях, с помощью которых выбираются многомерные пробные точки.
Книга рассчитана на широкий круг инженеров, конструкторов и научных работников, имеющих дело с многопараметрическпми системами.
Ответственный редактор доктор физико-математических наук Н. И. КАЛИТКИН
20204-504
С л^/п9< яТ 24-81 (кн, 2) 1702070000 WUU(v^y"*Ol
О ИздеСтсльство «Наука», 1981 г.
ПРЕДИСЛОВИЕ АВТОРОВ
Книга возникла в результате нашего многолетнего сотрудничества и выражает наши взгляды на проблему выбора оптимальных параметров. Во-первых, мы считаем необходимым рассматривать задачи оптимального проектирования как многокритериальные, а пе сводить их к однокритериальным, так как это, как правило, приводит к серьезному огрублению задачи, искажению ее существа, а следовательно, к неоправданной замене одной задачи другой. К такому же выводу в настоящее время приходят многие исследователи, занимающиеся разработкой математических методов для оптимального проектирования. Что же касается конструкторов, то они всегда были рады поддержать такую точку зрения, но, к сожалению, достаточно эффективных математических методов для изучения многокритериальных задач не было.
Во-вторых, мы считаем также, что не следует стремиться к полной автоматизации процесса выбора оптимальных параметров: выбор должен осуществлять сам конструктор, но с помощью ЭВМ. Поэтому наиболее рациональными мы считаем алгоритмы, содержащие диалог человека с вычислительной машиной. И эта наша точка зрения также соответствует тенденции, наметившейся в последние годы Ч
Проектирование реальных объектов с учетом многих критериев качества обычно имеет характер эвристического итерационного процесса: конструктор, рассматривая различные варианты модели, оценивает результаты, уточняет постановку задачи, затем снова решает ее и анализирует новые варианты. В процессе проектирования нередко меняются взгляды на значимость отдельных критериев. И это продолжается до тех пор, пока конструктор не решит, что пришло время остановиться: найдено то, что ему нужно.
См., например, книгу «Современное состояние теории исследования операций». М.: Наука, 1979; серию статей П. С. Краснощекова, В. В. Морозова и В. В. Федорова в журнале «Техническая кибернетика» за 1979 год и др.
Нам удалось 6 Какой-то море аЛгоритмйзйробатЬ это? процесс, представи в его в форме диалога конструктора с ЭВМ: при помощи ЭВМ формируется мно жество допустимых решений, среди которых конструктор выбирает наилучшее.
Мы старались сделать книгу доступной возможно более широкому кругу читателей и ради этого пожертвовали кое-где математической общностью. Вопросы, связанные . с теорией ЛП^-последовательностей, вынесены в Дополнение, написанное И. М. Соболем. В качестве дополнительной литературы указаны работы, в которых испрль- зованы методы, изложенные в настоящей книге. Список этих работ не претендует на полноту.
Мы считаем своим приятным долгом вспомнить с благодарностью покойного И. И. Артоболевского, который всячески стимулировал нашу работу и в большой степени способствовал внедрению этих методов в практику проектирования механизмов и машин. Мы благодарны Г. В. Крейнину за участие в получении первой таблицы испытаний, Р. П. Федоренко, В. В. Подиновскому и П. С. Краснощекову, прочитавшим рукопись и сделавшим ряд ценных замечаний, и С. И. Фридман, которая составила программы для расчета примеров, приведенных в книге.
ВВЕДЕНИЕ
Задачи проектирования машин. Они всегда многокритериальны, так как при выборе паилучшего варианта приходится учитывать много различных требований, предъявляемых к машине, и среди этих требований встречаются противоречащие друг другу. Однако почти все математические методы оптимизации предназначены для отыскания оптимального значения одной функции — одного критерия. Поэтому чаще всего пытаются неоправданными упрощениями свести многокритериальную задачу к однокритериальной. По нашему убеждению, большинство неудачных решений связано именно с этим этапом, так как если сформулированная математическая задача не адекватна исходной задаче, то никакой метод оптимизации положения не спасет: найденное «оптимальное решение» будет плохим.
Кто же должен давать математическую постановку задачи? Обычно считают, что это дело конструкторов х, которые хорошо разбираются в существе задачи. Однако в действительности, когда речь идет о задачах со многими параметрами и с несколькими критериями, поставить математическую задачу очень трудно, ибо конструктор обычно имеет достаточно хорошее представление о допустимых пределах изменения каждого параметра, но не знает возможностей всех критериев, и необходим предварительный расчет для выяснения этих возможностей. Как сказал И. И. Артоболевский [1], «поиск оптимального решения означает одновременно и поиск правильной постановки задачи».
В данной книге приведен простой алгоритм, позволяющий конструктору осуществлять разумную постановку математической задачи в процессе диалога с ЭВМ. С помощью этой методики была осуществлена постановка и найдено решение ряда важных задач, связанных с проек-
1 Мы будем использовать как синонимы слова «конструктор»,- «проектировщик», «совет специалистов». В таком же смысле в некоторых работах используют термин ЛПР (лицо, принимающее решение).
тированйем новых и усовершенствованием существующих механизмов и машин..
Особенности предложенного метода. Отличительная черта разработанного метода — систематический просмотр . многомерных областей: в качестве пробных точек в пространстве параметров используются точки равномерно распределенных последовательностей. Для этих целей были применены так называемые ЛП^-последова- тельности, которые обладают наилучшими характеристиками равномерности среди всех известных в настоящее время равномерно распределенных последовательностей. Заметим, что волюнтаристический выбор пробных точек в многомерных областях, как правило, приводит к плохим результатам из-за отсутствия у человека многомерной геометрической интуиции.
Другая особенность метода состоит в том, что диалог конструктора с ЭВМ протекает в очень благоприятных для конструктора условиях: он оперирует привычными для него величинами — значениями критериев — и не должен «комбинировать», то есть гадать, какой выигрыш по. одним критериям могут дать уступки по другим критериям; это выясняется в процессе диалога.
Приближенная характеристика задач, которые можно решать предложенным методом:
количество параметров не превосходит нескольких десятков;
количество критериев любое (в решенных задачах оно достигало 14);"
требования к гладкости областей, функциональных ограничений, критериев — минимальные;
отношение n-мериого объема множества допустимых решений, расположенного внутри заданного n-мериого параллелепипеда в пространстве параметров, к п-мериому объему этого параллелепипеда не должно быть чрезмерно малым.
Последнее из этих требований может быть проверено в ходе расчета. Однако более или мепее ясно, что оио исключает задачи с очень большим количеством функциональных ограничений.
О дальнейших возможностях метода. Очевидно, что область применения метода не ограничивается машиностроением: задачи со многими критериями, в том числе, удовлетворяющие требованиям а—г, встречаются в самых различных областях науки и техники. От таких задач обычно старались избавиться, ио, думается, причина как раз в том, что не было достаточно простого и эффективного метода для их постановки и решения.
В самом деле, в общей схеме вычислительного эксперимента А. А. Самарский [13] выделяет пятый этап:
анализ полученных результатов и уточнение математической модели. Ясно, что судить о достоинствах и недостатках используемой математической модели следует, вообще говоря, не по одному, а по многим критериям. Если модель зависит от нескольких параметров, то, естественно, возникает проблема наилучшего их выбора. Следовательно, можно надеяться, что методика, изложенная в настоящей книге, окажется полезной при осуществлении вычислительных экспериментов, связанных с самыми различными областями науки и техники. Первые шаги в этом направлении уже делаются.
Глава 1
СИСТЕМАТИЧЕСКИЙ ПОИСК
■ В МНОГОМЕРНЫХ ОБЛАСТЯХ
В дальнейшем изложении не раз используется метод зондирования пространства параметров, который мы назвали ЛП-поиском [16L Название это объясняется тем, что в качестве пробных точек в единичном многомерном кубе используются точки ЛПт-последовательностей. Математическая теория таких последовательностей достаточно сложна, и поэтому краткие сведения об ЛПТ- последовательностях перенесены в Дополнение. Здесь же по возможности элементарно разъясняются трудности, связанные с многомерностью рассматриваемых областей, заставившие нас отказаться от традиционных решетчатых сеток и воспользоваться ЛП-поиском.
■ Читатель, которому эта глава покажется трудной, может перейти прямо к главе 2, приняв на веру, что имеется эффективный алгоритм выбора пробных точек, равномерно расположенных в конечных многомерных областях (размерности п ^ 51).
1.1. Поиск в многомерном кубе
Рассмотрим единичный п-мерный куб Хп, состоящий из точек Р с декартовыми координатами xlt ..., жп,
Р = (®1, • • ч zn)«
удовлетворяющими неравенствам 0 ^ X; ^ 1 при / = = 1,2п.
Кубические решетки. Обычно полагают, что наиболее равномерный просмотр такого куба обеспечивает кубическая решетка (рис. 1.1), состоящая из N = М" точек с координатами „
/ й + ’/г ’а + ’/г*n + Vi
\ М ’ М * * " ’ М'
где in. . ., in независимо принимают все значения0,1, ...
. . ., М — 1. Однако зто неверно. Такая решетка опти-
Рис. 1.1. Кубическая решетка при п = 2 (^ = 16)
Рис. 1.3. Улучшенная сетка при п = 2 (7V = 16)
мальна только в одномерном случае, при n = 1 (рис. 1.2). Уже при п = 2 она не очень хороша, а с увеличением п «равномерность» ее быстро ухудшается. Строгая формулировка этого утверждения приведена в Дополнении. Впервые вывод о том, что кубические решетки в Кп — это плохие сетки при больших п, был сделан в 1957 году в работе [141.
Впрочем нетрудно привести элементарные соображения, разъясняющие такое, на первый взгляд парадоксальное, положение.
Сравним двухмерную сетку, изображенную на рис. 1.1, с сеткой, изображенной на рис. 1.3, которая также состоит иэ 16 точек. В обоих случаях каждому из 16 малых
’«■«■■■■и1,о • # X,
Рис. 1.2. Кубическая решетка при n = 1 (^ — 8)
квадратиков принадлежит одна и только одна точка сетки, так что, казалось бы, равномерность расположения точек обеих сеток примерно одинакова. Ситуация, однако, резко изменится, если потребуется исследовать функцию / (zIt z2), определенную в К?, которая сильно зависит лишь от одного аргумента: например, / = / (Zj). В этом случае, вычислив значения функции / в точках сетки рис. 1.1, мы получим лишь четыре различных значения, каждое повторенное четыре раза; а при расчете / в точках сетки рис. 1.3, мы получим 16 значений, дающих гораздо лучшее представление о диапазоне изменения функции /.
В многомерном случае кубическая решетка оказывается еще хуже, так как «потеря информации» при вычислении / (хп . . ., х„) может еще больше возрасти: вы- числив_Л = М" значений функции / (xj, мы получим всего М = Nli” различных значений!
Конечно, приведенные рассуждения с рассмотрением / (zi) — эт0 Крайний, самый неблагоприятный случай. В действительности функции / (xlt . . ., хп), встречающиеся на практике, сильно зависят от нескольких переменных, но не от всех. И мы никогда не можем быть уверенными, что нельзя представить / (хп . . ., х^ в форме
/ (хп . . ., xn) = g (xh, . . ., XfJ + h (zv _. . ., z^, где т<ви g^>h. Если же такое представление имеет место, то упомянутая выше потеря информации будет налицо: сосчитав N = Мп значений /, мы получим всего Мт = jVm/n существенно различных значений функции. Количество «лишних» точек N — Nm/n с увеличением М катастрофически растет; например, если п = 5, тп = 3 и М = 10, то
N — Nmfn = Мь - М3 = 99000
из общего числа N = Мь = 100 000.
; Отсюда вывод: проекции точек хороших многомерных сеток в К" на m-мерные грани этого куба должны представлять собой хорошие тп-мерные сетки, и это должно быть верно при любых тп = 1, 2, . . ., и — 1.
Равномерно распределенные последовательности точек в Кп. Пусть Pi, .■. ., Р,, ...—последовательность точек, принадлежащих Кп. Выберем в /Г* произвольный п-мер- ный параллелепипед П со сторонами, параллельными координатным граням (рис. 1.4). Обозначим через Sn (П) количество точек Pj с номерами 1 ^ i -^ N, принадлежащих П.
Определение. Последовательность точек Рп ... ..., Pt,. . . называется равномерно распределенной (р.р.) в К?, если для любого П
(П)
Кт-^- = Уп,(1)
где Fn — объем (n-мерный) параллелепипеда П.
Можно доказать, что если G — произвольная область, расположенная в Кп и имеющая объем Vq, то из (1)
вытекает
(2)(2)Ит^=1,с.
(2)
(2)
Соотношение (2) показывает, что при достаточно больших N количество точек последовательности, принадлежащих G, пропорционально объему G:
(3)(3)SN (G) оэ MVG.
(3)
(3)
Легко также доказать, что проекции точек р.р. последовательности на любую zn-мерную грань куба Кп при
т*С п образуют р.р. последовательность в Кт. Таким образом, требование, сформулированное в конце предыдущего пункта, в какой-то мере выполняется для точек Plv . . . . . , PN, составляющих начальный участок р.р. последовательности.
| Несмотря на то, что определение и первые примеры р.р. последовательностей были указаны Г. Вейлемещев 1916 году,
использование таких последовательностей в вычислительной математике началось только в 60-х го
дах, когда удалось построить последовательности, для которых скорость сходимости в (1) при N -> оо близка к наилучшей, а равномерность расположения наблюдается начиная с небольших N. (Заметим, что определение (1) зависит только от асимптотических свойств последовательности: если изменить, выбросить, добавить любое конечное число любых точек последовательности, то предел (1) не изменится.)
Использование в качестве сеток начальных участков Рх, . ... Ри р.р. последовательности имеет еще одно достоинство: количество точек сетки может быть удвоено добавлением еще N точек Рц*1> • • •• P»n« (При использовании кубических решеток удвоение М вынуждает увеличить количество точек сразу в 2" раз; а замена М на М + 1 заставляет все точки новой сетки считать заново.)
Простейший поиск. Предположим, что функция F (Р) кусочно непрерывна в Ки и требуется приближенно найти точку Р такую, что
Р(Р) = min F(Py
Рекп
Приближенных методов отыскания минимума функции очень много (см., например, (8, 12, 18]), но в большинстве своем это все локальные методы, сходимость которых гарантируется лишь в достаточно малой окрестности минимума. Если же речь идет о нахождении глобального минимума, то выбор методов поиска гораздо более ограничен.
Рассмотрим простейший случайный поиск, который состоит в следующем. В Кп выбираем N независимых случайных точек Гц . . ., Г#, равномерно распределенных в Кп (здесь равномерное распределение в теоретиковероятностном смысле). Среди значений F (Г^, . . . .. ., F (Гн) находим наименьшее
Р(ГЬ) = min >(Г1)
(если таких несколько, то выбираем любое из них). И считаем, что F (Fie) » min F (Р), Г(, %; Р.
Сходимость такого поиска доказывается достаточно просто. Пусть Н — произвольная окрестность единственной точки Р, и объем Ун положителен. Так как вероятность Р {Г е Н) = Ун> то вероятность того, что хотя бы одна из точек Гц . . ., 1\ попадет в Я равна 1 — (1 — —Ph)n и, при N-^oo, стремится к 1. Следовательно, при достаточно больших N вероятность попадания хотя бы одной пробной точки в любую окрестность точки минимума Р как угодно близка к 1.
Легко показать, что в качестве пробных точек в простейшем поиске можно использовать точки Рп . . . . . ., Рц . . ., образующие р.р. последовательность. В самом деле, так как согласно (3)
SN (И) со NVH,
то при N -*- оо количество пробных точек, попавших в Н, окажется гак угодно большим.
Поиск будет тем лучше, чем более равномерно расположены в К” пробные точки (если, конечно, нет никакой -предварительной информации о положении минимума). Случайны ли они, или нет — не столь важно. Нам не раз приходилось слышать от вычислителей, что в их экспериментах при п > 4 случайный поиск оказывался лучше неслучайного. Однако во всех этих экспериментах в качестве неслучайных пробных точек использовались точки кубической решетки, а, как мы уже знаем, расположение этих точек следует расценивать как плохое.
ЛП-поиск. Мы предложили использовать в качестве пробных точки Лиг-последовательностей, которые являются наиболее равномерно распределенными среди всех известных в настоящее время последовательностей. Многочисленные эксперименты, проведенные с целью сравнения ЛП-поиска с простейшим случайным поиском, неизменно показывали преимущество ЛП-поиска, хотя количественные характеристики «выигрыша» меняются в зависимости от рассматриваемых задач.
Пример [16]. Максимум весьма сложной функции Ф, Зависящей от девяти переменных, оценивался по значениям в случайных точках Гх, . . ,,TN и в точках Л Непоследовательности Qt, . . ., QN. Результаты, полученные при различных N, приведены в таблице 1.1.
Таблица 1.1
■ Поиск максимума Ф
N
512
1024
2048
max Ф(Г;)
42,29
.42,29
43,52
max Ф(9<)
48,12
48,61
48,61
Можно указать два класса задач, при решении которых ЛП-поиск оказался очень полезным. Во-первых, это задачи, в которых одновременно требуется оценить максимумы и (или) минимумы нескольких функций, заданных в К^; ибо это можно сделать по одним и тем же пробным точкам. Во-вторых, это задачи, в которых для отыскания глобального экстремума многоэкстремальной функции используют локальные методы оптимизации: для того.
чтобы не попасть вместо глобального в какой-нибудь из локальных экстремумов, приходится повторять локальный поиск много раз, начиная из различных начальных точек; очевидно, что начальные точки должны быть равномерно расположены в Яп. Самым эффективным способом выбора начальных точек оказалось использование точек ЛПт-последовательностп.
В заключение заметим, что ЛПт-последовательно- сти — это наилучшие среди известных в настоящее время р.р. последовательностей. Если в будущем удастся построить еще лучшие последовательности (с достаточно простым алгоритмом расчета и с более равномерным расположением точек), то все алгоритмы, изложенные в книге, станут еще более эффективными, так как можно будет использовать эти новые последовательности вместо ЛПт-последовательностей.
Поиск в произвольной ограниченной области
В этом параграфе рассмотрены некоторые достаточно простые преобразования р.р. последовательностей, которые используются в дальнейшем. Все приводимые здесь результаты имеют весьма прозрачный геометрический смысл.
Равномерно распределенные последовательности точек в ограниченной области G. Обозначим через G произвольную n-мерную ограниченную область, имеющую конечный объем Pg > 0.
Определение. Последовательность точек Pv ... . . ., Pi, . . ., принадлежащих G, называется равномерно распределенной в G, если для любого П, принадлежащего G (обозначения см. в разделе 1.1):
Чтобы убедиться в том, что (1) есть частный случай (4), достаточно вспомнить, что объем Кп равен 1, так что в (1) вместо Рп можно было бы написать Рп/Ркп.
Многочисленные приемы, используемые в методах Монте-Карло для моделирования различных случайных величин, позволяют находить точки Pv . . ., Р,, . . . р.р. в произвольной области G путем преобразования точек Qv • • ч Qb • • •• Р-Р- в К”- Эти вопросы достаточно подробно освещены в (151, и мы не будем на них останавли- 14 '
ваться. Ниже нам понадобятся только формулы для
расчета последовательности точек, р.р. в заданном параллелепипеде П со сторонами, параллельными координатным граням (рис. 1.5).
Лемма 1. Если точки Qt с декартовыми координатами (g,, J,..., qi,^ образуют р.р. последовательность в Кп, то точки А, с декартовыми координатами (аг-1,•«<,>)>
где при j = 1, 2, . . ., п
“i. j = ai + <bj — a-) qt, h (5) образуют р.р. последовательность в параллелепипеде П, состоящем из точек (ап. . ., ап), координаты которых удовлетворяют неравенствам aj ^ а/ ^ bj.
Доказательство. Выберем произвольный параллелепипед По С П, который опреде
ляется неравенствами aQ < а^ Рис. 1.5. К доказатель- ^ by Точкам По в силу преобра- СТВУ леммы 1 зования(5) взаимно однозначно соответствуют точки параллелепипеда П С.Кп, который определяется неравенствами
(«3 — Oj№ — ОЙ < ^ < (bj — aj)/(bj — aj).
Поэтому количество точек А < еПа, которое мы обозначим через SN (По), равно количеству точек Qt ell, которое мы обозначим через SN (П). А так как объемы этих параллелепипедов равны соответственно
тотоИп. = П(Ь"-а"):Ип. = П(Ь"-а"):п .о О Пп .о О Пfl.fl.пп
то
то
Ип. = П(Ь"-а"):
Ип. = П(Ь"-а"):
п .о О П
п .о О П
fl.
fl.
п
п
.. ^м (По) .. пт —й= птN—эо ПN—oo.. ^м (По) .. пт —й= птN—эо ПN—oo^(П) -V - Гп-^(П) -V - Гп-
.. ^м (По) .. пт —й= пт
N—эо ПN—oo
.. ^м (По) .. пт —й= пт
N—эо ПN—oo
^(П) -V - Гп-
^(П) -V - Гп-
что и требовалось доказать.
Метод отбора для равномерно распределенных последовательностей. Более или менее очевидно, что если среди точек Ап . . ., Аь . . ., образующих р.р. последовательность в П, отбирать все точки, принадлежащие некоторой области GC П, то получим последователь-
ность точек р.р. в G. Так как этот прием неоднократно используется в дальнейшем, то приведем строгое доказательство.
Лемма 2. Пусть Лп . . ., Аь ... — последовательность точек р.р. в П, а СсП — произвольная область с положительным объемом Уд > 0. Если среди точек At отобрать все точки, принадлежащие G, то получим последовательность точек р.р. в G.
Доказательство. Пусть А},, . . ., Ain— первые N среди отобранных точек. Если номер последней из них равен N' (то есть AtN = An-), то легко видеть, что Sn« (G) = N. Выберем теперь произвольный параллелепипед Пв С G и обозначим через Л N (По) количество точек, принадлежащих По, из числа отобранных точек А1И . . ., А^. Тогда sN (По) = SN« (По), ибо те из точек Лп . . ., Ик», которые не попали в G, тем более не могли попасть в По. Значит,
^N (Во) _ ^N" (Во) N' ^N' (Во) N' ^П.
NN"'№N"'(G) VG >
когда N, а вместе с ним и N’, стремится к оо. Тем самым лемма доказана.
Отношение объемов
У = Ес/Уп
в теории методов Монте-Карло называют эффективностью отбора, так как в среднем для получения одной точки в G приходится рассмотреть 1/у точек в П. При у ^ 1 метод отбора становится малоэффективным.
Глава 2
ВЫБОР КРИТЕРИАЛЬНЫХ ОГРАНИЧЕНИЙ
Задачи проектирования в действительности многокритериальны: чем больше критериев качества вводится в рассмотрение, тем более полную характеристику достоинств и недостатков проектируемой машины можно получить. Однако, техническое задание на разработку машины с указанием требований, предъявляемых к ней,— это еще не
математическая задача. Сформулировать корректную М3' тематическую задачу в реальных условиях достаточно трудно.
Именно эта ситуация рассмотрена в разделе 2.1, а в разделе 2.2 изложена методика [17, 21, позволяющая конструктору с помощью ЭВМ выбирать разумную постановку задачи. Мы считаем нужным подчеркнуть оригинальность этой методики, так как обычно ЭВМ используется только для решения математических задач, а постановка задачи предполагается вне математики.
Некоторые особенности предложенной методики обсуждаются в разделе 2.3, а пример ее использования приведен в разделе 2.4.
Исходные данные
Предположим, что задана математическая модель исследуемой или проектируемой системы, и модель эта зависит от п параметров ап . . ., о„. Слова «задана математическая модель» означают, что имеются формулы (или -готовые программы), позволяющие по заданному набору^,... . . ., On вычислить любые интересующие нас характеристики системы. Сами ап ... ., а„ могут быть естественными физическими величинами, например, массами, радиусами, жесткостями и т. п., или, если единицы измерения этих величин фиксированы, могут считаться безразмерными. Если функционирование системы описывается дифференциальными уравнениями, то в качестве параметров можно выбирать коэффициенты или начальные значения этих дифференциальных уравнений.
Пространство параметров. Пространством параметров называется n-мерное пространство, состоящее из точек А с декартовыми координатами (ап . . ., ап). Таким образом, каждой точке А пространства параметров соответствует конкретный набор параметров (ап .... ап) и наоборот.
Как правило, проектировщики могут указать разумные пределы изменения каждого из параметров, которые мы будем называть параметрическими ограничениями
«?<«,<«** (/=1,2, .... n). (1)
Ограничения (1) выделяют в пространстве параметров параллелепипед (рис. 2.1). П = (Л | (1)), объем кото-
рого (n-мерный объем) равен произведению
Кп = (аГ-а*)...(аГ-а*)-
В дальнейшем нас будут интересовать только точки Л, принадлежащие П: им и только им соответствуют системы, параметры которых удовлетворяют ограничениям (1).
Так как наш метод основан на зондировании параллелепипеда II конечным числом пробных точек, то без не- обходимости расширять гра-
Рис. 2.1. Параллелепипед П в пространстве параметровРис. 2.1. Параллелепипед П в пространстве параметровницы (1) не рекомендуется: при этом объем возрастает, и для просмотра может потребоваться больше точек.
Рис. 2.1. Параллелепипед П в пространстве параметров
Рис. 2.1. Параллелепипед П в пространстве параметров
Функциональные ограничен ния. Кроме параметрических ограничений обычно в условия задачи включаются функциональные ограничения
£ < fl (Л) < сГ
(Z=.l, 2, . . ., 0. (2)
Здесь ft (Л) — некоторые функции от параметров Л = = (ап . . ., On). Они могут быть заданы явно. Но если, например, функционирование системы описывается дифференциальными уравнениями, то /, (Л) часто представляют собой функционалы, зависящие от интегральных кривых этих уравнений. Мы предполагаем, что все функции ft (Л) непрерывны в П.
Обозначим через G подмножество параллелепипеда П, состоящее из точек Л, удовлетворяющих ограничениям (2) (рис. 2.2):
G = (Л | (1), (2)}.
Множество G, вообще говоря, может быть любым замкнутым множеством. Единственное ограничение: объем G должен быть положительным (VG > 0).
С математической точки зрения требования, предъявляемые к G, должны быть несколько более жесткими: множество G должно совпадать с замыканием множества своих внутренних точек. Именно это требование обеспечивает отсутствие в G компонент меньшей раз- мерностп, чем п.
Однако с точки зрения практики последнее требование излишне: такого положения всегда можно добиться сколь угодно малым изменением величин с* и (или) с**.
Рис. 2.2. Множество G в параллелепипеде ПРис. 2.3. Множество допустимых точек DРис. 2.2. Множество G в параллелепипеде ПРис. 2.3. Множество допустимых точек D
Рис. 2.2. Множество G в параллелепипеде П
Рис. 2.3. Множество допустимых точек D
Рис. 2.2. Множество G в параллелепипеде П
Рис. 2.3. Множество допустимых точек D
Можно сказать, что требование Fg / 0 исключает из рассмотрения задачи с функциональными ограничениями в форме равенств, например, / (Л) — с.
Впрочем в некоторых случаях удается разрешить систему ограничений вида
fi («1, . . ., о„) = cz (I = 1, 2, . . ., t, t < п),
относительно а<+1, . . ., ап:
а> = ф> (ап . . ., а(; cv . . ., с,)(/ = Z + 1, . . ., п).
Тогда можно рассматривать задачу в <-мерном пространстве параметров (ап . . ., а() без этих ограничений, а значения а1+ц . . ., ап считать известными функциями ct; = = Ф; от ап . . ., а(.
Критерии качества. Критерием качества называется характеристика системы, которая связана с ее качеством монотонной зависимостью. Иными словами, при прочих равных условиях система тем лучше, чем больше (меньше) критерий.
Для простоты записи мы всюду в дальнейшем будем предполагать, что вбе заданные критерии Фх (Л),..., Ф* (Л) желательно уменьшить:
Фу (Л) -► min.
Следовательно, чем меньше ФУ(Л), тем лучше система (при прочих равных условиях).
Формально, любой критерий можно привести к такому виду, заменяя, если это нужно, Фу на 1/Фу или на
—Фу. Однако делать это совсем не обязательно: конструктору удобнее оперировать привычными реальными величинами. А-как видно будет из дальнейшего, алгоритм выбора критериальных ограничений легко реализовать и тогда, когда некоторые из критериев желательно максимизировать. Относительно функций Фу (А) мы также будем предполагать, что они непрерывны в П.
Сформулировать математическую оптимизационную задачу при наличии нескольких критериев качества совсем непросто, ибо критерии зти часто противоречат друг другу. Например, уменьшая вес машины (что часто очень желательно), мы в то же время уменьшаем ее прочность (что как раз не желательно). Или, чрезмерное снижение стоимости изделия может обернуться ухудшением других его качеств.
Инбгда полагают, что все дело в удачном выборе решающего критерия качества Ф (А), который «должен» соединить в себе (то есть учесть) значения и важность каждого из индивидуальных критериев Фг (А), . . ., Фк (А). Однако замена нескольких критериев единым — проблема сложная и не всегда разрешимая. В большинстве реальных задач такой подход себя не оправдывает, так как при грубом выборе Ф (А) решение математической за-, дачи об отыскании точки А, в которой
Ф (А) = min Ф (А), Лес
оказывается практически плохим из-за того, что некоторые из значений Фу (А) превышают допустимые (по мнению проектировщиков) пределы. Чтобы избежать такой ситуации необходимо ввести критериальные ограничения
ФУ(А)<Ф$* (v = 1, 2Л).(3)
Критериальное ограничение Фу* — это худшее значение критерия Фу (А), которое проектировщик считает приемлемым.
Пусть D — множество точек А, которые удовлетворяют всем ограничениям (1), (2) и (3) (рис. 2.3):
D - {А | (1), (2), (3)},
так что D С GC П; если множество D непусто, то оно замкнуто. Естественно назвать D множеством допустимых точек, ибо если сформулировать задачу об отыскании
точки А такой, что
Ф(Л)=гШ1пФ(Л), (4)
Аеп
то решение этой задачи всегда существует и конструктора устраивает: как бы ни был выбран решающий критерий Ф (Л), все значения Фу (Л) удовлетворяют ограничениям (3).
Таким образом, мы видим, что главная трудность при переходе к математической задаче (4) состоит в выборе критериальных ограничений Фу ** и в обеспечении не- пустоты множества допустимых точек D. Требования, предъявляемые нами к множеству D, такие же, как требования к множеству G (см. выше «Функциональные ограничения»).
По нашему убеждению, обоснованный выбор критериальных ограничений невозможен без предварительного исследования системы: необходимо определить возможности системы по каждому из критериев в области G и, в частности, представлять себе диапазоны изменения каждого из критериев. В следующем параграфе изложен численный алгоритм, позволя!ощий выбирать Ф** в процессе диалога конструкторов с ЭВМ, гарантируя при этом непустоту множества D.
Диалоговый алгоритм
В основе нашего алгоритма лежит численное исследование (зондирование) пространства параметров проектируемой системы. Исследование проводится в три этапа.
1-й этап: составление таблиц испытаний. Этот этап выполняется ЭВМ без вмешательства человека. Последовательно выбираются N пробных точек Аи . . ., An, равномерно расположенных в G (как это делается см. ниже). В каждой из точек А,, рассчитывается 'система и вычисляются значения всех критериев Ф!^), . . , Фк (А^. По каждому критерию составляется таблица испытаний, в которой значения Фу (41), • • Фу (4^ расположены в порядке возрастания
ФУ (4J < Фу (А^ <. .. < Фу (А^) (5) и указаны номера in ie, . . ., In соответствующих пробных точек (свои для каждого v). Такие таблицы представляют
собой аналог статистических вариационных рядов. Как следует из разд. 1.1, при N -► оо наименьшее значение Фу (Лг.) стремится к min Фу (Л), а наибольшее —
AGG
Фу (Л;„) — стремится к max Фу (Л). Но таблица испыта-
AeG
ний показывает не только приближенные значения максимума и минимума Фу (Л) в области G: по таблице можно судить о частоте тех или иных значений Фу (Л).
Фрагменты настоящих таблиц испытаний приведены в табл. 2.3 (на с. 33).
2-й этап: выбор критериальных ограничений. Этот этап предполагает вмешательство проектировщика. Просматривая поочередно каждую из таблиц (5), он должен назначить ограничение Ф^* для каждого критерия.
Стоит подчеркнуть, что наш диалог очень удобен для проектировщика: он не должен «комбинировать», уменьшая одни критерии за счет других; ему показывают одну таблицу испытаний и предлагают назначить одно ограничение; затем повторяют то же с другой таблицей испытаний. Конечно, конструктор заинтересован в том, чтобы все Ф** были по возможности меньше, но он понимает, что если выбирать Ф** неоправданно малыми, то множество допустимых точек окажется пустым...
3-й этап: проверка непустоты I). Этот этап также выполняется автоматически, без вмешательства человека. Фиксируем какой-нибудь из критериев, например, Фг (Л), и рассмотрим соответствующую ему таблицу испытаний (5). Пусть s — количество значений в этой таблице, удовлетворяющих выбранному критериальному ог. раничению Ф?*, так что
ФНЛьХ... <Ф1(Л,;<Ф**.
Путем перебора значений всех критериев в точках Л^,.., . . ., Л^ нетрудно проверить, есть ли среди этих точек хотя бы одна такая, в которой справедливы одновременно все неравенства (3)
Фу(4,р<ФГ (v = 1, 2, . ... к\,
(при v = 1 можно, конечно, не проверять). Если такая точка Л^ существует, то множество D, определенное неравенствами (1)," (2) и (3), непусто, и задача (4) разрешима (при любом выборе Ф!).
В противном случае следует вернуться ко второму этапу и потребовать от конструктора уступок при назначении Ф**. Если такие уступки невозможны, то необходимо вернуться к первому этапу и увеличить количество N пробных точек, чтобы повторить второй и третий этапы с таблицами испытаний большего объема.
Наконец, если при неоднократном увеличении N точки А$., принадлежащие D, не обнаруживаются, то есть все основания считать, что выбранные критериальные ограничения Ф** несовместны. Конечно, нельзя категорически исключить возможность того, что в некоторой точке А', отличной от всех пробных точек Аи . . ., An, все неравенства (1), (2) и (3) выполнены; однако, если даже такая точка А' существует, то ее окрестность, в которой эти неравенства сохраняются, очень мала (объем ее порядка j VgIN) и практически система, соответствующая точке А', будет неустойчивой (не конструктивной).
Замечание. Можно сказать, что на первом этапе вычисляется матрица критериев fl Фу (Л t) |, размер которой к х N, и ЭВМ просматривает по одной все к строк этой матрицы. На третьем этапе ЭВМ просматривает з столбцов этой же матрицы.
Выбор пробных точек. Во всех расчетах мы использовали точки ЛПх-последовательности Q6, Qn. . ., Qt, . . ., сведения о которых изложены в Добавлении. Согласно Лемме 1 из раздела 1.2, мы по декартовым координатам очередной точки
Qi = (9i, и • • •> 91,п)
вычисляем декартовы координаты точки ЛФ = (о^,. . .■ . . ., «пЬ» принадлежащей параллелепипеду П
а^ = at + («Г - «*) ^Л 0 = 1,2,..., п\ (6)
При А = ЛФ рассчитываем проектируемую систему и проверяем выполнение функциональных ограничений (2). Если они выполнены, то точка А = ЛФ отбирается в качестве пробной точки в G и вычисляются все Фу (Л); в противном случае точка А = ЛФ отбрасывается. Используемые на первом этапе пробные точки Av . . ., Л# — это первые N отобранных таким образом точек. Согласно' лемме 2 пз раздела 1.2, эти пробные точки при N -*■ со образуют последовательность, равномерно распределен? ную в G.
Пусть N' — количество точек Л(<> в П, которые надо проверить для того, чтобы отобрать N пробных точек в G. Так как NIN' ^ VG!Vn = у (см. раздел 1.2), то N' ~ ~N!4.
Пусть т — время расчета системы в одной точке ли\ а Тц — полное время расчета N пробных точек в G. Из равенства Tn = Л^т получаем, что
TN ^ Nx/4. (7)
На практике величины т и у, входящие в формулу (7), численно оцениваются по сравнительно небольшому количеству испытаний. После этого формула (7) позволяет оценить время Tn, необходимое для составления таблиц испытаний любого заданного объема N. При решении сложных задач объем таблиц испытаний N обычно ограничен из-за ограниченности машинного времени TN. Однако следует иметь в виду, что если выбираются параметры машины, предназначенной для серийного производства, то любые (разумные) затраты времени Tn будут оправданы.
Нередко задают «конкретный» вопрос: каким должно быть № Однозначно ответить на такой вопрос нельзя: это Зависит не только от т и у, входящих в формулу (7), но и от характера изменения функций Фу (Л). Во многих решавшихся нами реальных задачах, связанных с проектированием различных машин, достаточно было выбирать N' = 128 или N' = 256 — даже при количестве параметров л, достигавшем 30. В некоторых задачах, где время т расчета одного варианта малб, количество испытаний доводилось до N' = 4096, хотя существенных уточнений это, как правило, не давало.
Напротив, в двух сложных задачах пришлось ограничиться значениями N* ^ 60; и хотя при этом N были всего лишь около 20, полученные результаты вызвали у проектировщиков большой интерес.
Последовательность Dy. На третьем этапе мы находим не одну, a q точек, принадлежащих D. Очевидно, q ^ N. Множество этих точек обозначим через Dn.
Способ построения и отбора точек Dn (см. лемму 2, раздел 1.2) гарантирует, что q-*- оо, когда N -> оо, и последовательность этих точек равномерно распределена в D.
Эти точки чрезвычайно полезны для последующего решения оптимизационной задачи (4). Об этом подробнее сказано в гл. 3.
Схема алгоритма
На схеме изображен диалоговый алгоритм. Последний блок, приведенный под названием «оптимизация», обсуждается в гл. 3. ■
Некоторые особенности алгоритма
Функциональные ограничения и псевдокрптерпи. При традиционном подходе к многокритериальным задачам нередко пытаются сократить количество критериев, заменяя их функциональными ограничениями. Например, встречается рекомендация выбрать один из критериев в качестве решающего, а на остальные наложить ограничения (при этом предполагается, что эти ограничения задаются априорно, хотя, как мы уже отмечали, обоснованно задать их совсем непросто).
С точки зрения нашей методики выгоднее поступать наоборот: если функциональное ограничение
сТ < fl (Л) < сГ
не абсолютное, т. е. если конструктор допускает, что с* и (или) cf* могут быть изменены, то стоит вместо этого ограничения ввести псевдокритерий, например,
Ф«+1 = ft (Л).
Это не критерий, ибо здесь нет монотонной зависимости от качества. Однако разумные ограничения для Ф^+1 (Л) можно будет выбрать, изучив таблицу испытаний этой величины.
Если по мнению конструктора значение ct для величины ft (А) было бы «весьма хорошим», то в качестве псевдокритерия удобно ввести величину
Ф«« = |Ь (Л) — «г |.
Тогда для Ф*+1 можно будет выбрать лишь одностороннее ограничение вида Ф;щ (Л^^Флй» и при этом окажется, что
с^-Ф^, сГ^ + Ф^.
Возможность использования псевдокритериев важное достоинство данного метода. Во-первых, это позволяет во многих случаях выбирать не произвольные, а обосно- вапные функциональные ограничения. Во-вторых, когда количество априорных ограничений уменьшается, то уве-
личиваетСя объем области 6 и вместе с ним возрастав* величина у, входящая в формулу (7).,
Параметрические ограничения и псевдокритерии. Мы .всегда считаем, что параметрические ограничения (1) жестко заданы. Однако в некоторых случаях конструкторов интересует возможность сужения основного параллелепипеда за счет уменьшения вариации каких-нибудь из параметров. .
Для исследования таких вопросов можно использовать те же расчеты, описанные в § 2.2, если предварительно включить исследуемые параметры в число псевдокритериев.
Пусть, например, ставится вопрос: чем придется пожертвовать, если ограничить изменение ар, так, что а* ^ ар ^ а'р, где ар •< а^*? В зтом случае следует ввести псевдокрнтерий Ф»н = ар. Введя «критериальное» ограничение Ф*« = ар, мы получим множество допустимых точек D*, соответствующее ограниченному изменению ар, и сможем сравнить наилучшие пробные точки в D' с наилучшнми пробными точками в D.
О таблицах испытаний. Таблицы испытаний нередко встречаются в инженерной практике. Особенность используемых нами таблиц в том, что испытания равномерно распределены в области G пространства параметров. Благодаря этому таблицы позволяют получить правильное представление о распределении значений каждой из функций Фу (Л) при Л Еби гарантируют достаточно подробный просмотр любой наперед заданной части G, когда .А^оо. '
Если количество пробных точек N велико, то вместо просмотра всей таблицы испытаний (см. формулу (5)) можно ограничиться просмотром ее части, содержащей М наилучших значений ^М < Ny
Фу (Л6) < Фу (Л^ < . . . < Фу kAiMY
Такую таблицу мы называем усеченной таблицей испытаний. Чрезмерное усечение таблиц может оказаться причиной пустоты множества D; по зто будет обнаружено на третьем этапе диалога и тогда, возвращаясь ко второму этапу, следует увеличить объем таблиц.
Нормированные критерии. Предположим, что все рассматриваемые критерии Фу (Л) строго положительны: Фу.№>0. Обозначим панлучшее значение Фу в (5)
Через Ф*^ = Фу(Д11). Ёслй вместо Фу (Л) раССматрй- вать нормированный критерий
^(Л) =ФУ(ЛЖ„,
то вместо (5) получим таблицу испытаний вида
1<Х»(Л^<^(ЛЬ)<...<ХУ(Л^).(8)
Выбор критериальных ограничений можно осуществлять по таблицам вида формулы (8), которые позволяют ориентироваться на относительные изменения значений критериев.
Необходимо, однако, подчеркнуть, что такая нормировка может считаться обоснованной только тогда, когда N достаточно велико, и значение Ф* n достаточно близко к ^ = min Фу (Л). Это же замечание относится к другим лей
возможным способам нормировки критериев.
Пример: оптимизация параметров редуктора1
Исходная модель. В качестве исходного был выбран реально существующий механизм — одноступенчатый редуктор [6]. Редуктор состоит из двух косозубых шевронных колес в подшипниках скольжения (рис. 2.4). Модель имеет 6 степеней свободы. Обобщенные координаты: «и х4 — углы поворота колес I и II (в направлении вращения); z2, хь — перемещения колес I и II в направлении линии зацепления; _z3, хв — перемещения подшипников колес I и II в направлении линии зацепления. Источником возмущающих сил считается накопленная погрешность А колеса I с амплитудой 10 мкм.
Колебательные процессы в редукторе описываются системой обыкновенных дифференциальных уравнений
тД + с^у -f- к^у = — с^А,
т4ха 4- c^Zg — z3) 4- с6у 4- к^—±3) 4- к6у = — с6Д, m3z3 — c^z, — z3) 4- c3z3 — k^ — i3) -f- k3i3 = 0, m4z4 — Сьг»У — k6riV = сег2Д,1 ;
m6zE 4- ca(z6 — ze) — csy 4- A:2(z6 — ze) — k6y = c6A, mA — c2(z6 — ze) 4- c4ze — k^ib — re) + Me = 0.
В диалоге с ЭВМ участвовал специалист по динамике машин П. И. Зинюков.
Рис. 2.4. Динамическая модель редуктора
Здесь гь г2 — радиусы основных окружностей колес I и II; и^, т4 — их моменты инерции; pi2, m6 — их массы; т3, т» — массы подшипников колес I и II; сп с2 — жесткости колес I и II; с3, с4 — жесткости стула подшипников колес I и II; с6 — жесткость зацепления; у = г^ + + ж, — г3х4 — х6; kt — коэффициент демпфирования в соответствующей жесткости.
Численные значения всех параметров приведены в табл. 2.1. Значения kt указаны при двух частотах / (в герцах), так как предполагается, что In kt есть линейная функция от /.
Накопленная погрешность А представляется в виде А — Ао sin 2лД, где / — частота вращения колеса I — меняется в рабочем диапазоне /иач /кою пред-
'Таблица 2.1
Параметры*исходной модели
Параметры
1 = 1
2
3
4
5
1 = 6
Ш|•
2 кгм2
300 кг
300 кг
75кгм2
1000кг
300 кг
10’ С{ [н/м]
0,50
0,25
0,50
0,50
3,0
—
Гнс]
10в^ (50)[— ]
0,5С0
6,250
0,167
0,167
0,500
—
Гн-сП 10^(150)[^]
0,167
0,083
0,056
0,056
0,167
—
П [мм]
91,41
355,71
—
—
—
—
полагается, что /нач = 5 гц, /кон = 300 гц. При каждом фиксированном / установившееся решение системы (9) ищется в виде ij = at sin (2лД 4- ф,).
По имеющимся программам на ЭВМ вычисляются амплитудно-частотные характеристики at(f) при 1 ^ i ^ ^ 6, ускорения ut(J) (в децибеллах) при 1 ^ i ^ 6 и динамические усилия Pi(f) в жесткостях ct при 1 i 5. Вычисляются также собственные частоты системы (9) при А = 0 и i( = 0.
В качестве варьируемых рассматривались И параметров:
(ап . . ., аи) = (znn . . ., zne, cv . . ., се).
Критерии качества. Редуктор был построен для виб- роакустических исследований. Одна из основных задач такого исследования — снижение виброактивности по различным выходным характеристикам, в различных точках механизма, на различных частотах. Естественно, что задача эта оказалась многокритериальной. Проектировщиком были сформулированы 14 критериев Ф„, значения которых желательно уменьшить.
Для сокращения записей введем обозначения
.1 коп
р=——L-— ( F^d,}, max'F= max F^y 'кон 'нач^нач^^кон
иач
Тогда нетрудно записать все критерии:
средние и максимальные значения амплитуд перемещений (в микронах) подшипников колес I и II соответ-
ственпо:
Фх = а3, Ф2 = max а3, Ф3 = ав, Ф4 = max ав;
средние и максимальные значения амплитуд ускорений (в децибеллах) подшипников колёс I и II соответственно:
Ф5 = й3, Ф6 = max н3, Ф7 = йв, Фа — max ue;
средние и максимальные значения амплитуд динамических усилий (в ньютонах), передаваемых с подшипников колес I и II на фундамент:
Ф9 = Р3, Ф10 = max Р3, Фи = Р4, Ф12 = max Р4;
масса деталей вращения: Ф13 = т3 + т5;
число собственных частот, попавших в рабочий диапазон
/нач ^ / ^ /кон» Фи-
Проектировщик высказал также предположение, что первые 12 критериев могут быть разбиты на тройки критериев, примерно равноценных. Первая тройка состоит из наиболее важных критериев Фп Ф6, Ф9; вторая — из критериев Ф2, Фв, Ф10; третья — из критериев Ф3, Ф7, Фы; и, наконец, четвертая — из наименее существенных критериев Ф4, Ф8, Ф^. Как мы увидим в дальнейшем (разд. 4. 2), расчеты в основном подтвердили это предположение.
Составление таблиц испытаний. Допустимые пределы варьирования каждого из параметров были указаны проек-
, Таблица 2.2 Значения параметров
3
“1./
а?
a«ej
=1
1
1
2
3
1,042
1,00
1,00
2
150
300
450
360
360
375
3
150
300
450
247
247
242
4
50
75
100 £
94,6
100
100
5
650
1000
1390 *
720
720
700
6
200
300
400 ;
210
200
200
7
0,40
0,50
0,60
0,459
0,459
0,440
8
0,20
0,25
0,30
0,275
0,275
0,263
9
0,40
0,50
0,60
0,588
0,600
0,600
10
0,40
0,50
0,60
0,599
0,600
0,600
И
2
3
4
3,89
4,00
4,00
тировщиком так, чтобы отличие их от параметров исходной модели, приведенных в табл. 2.1, не превосходило 20%—50%. Все значения а;* и а,** имеются в табл. 2.2; здесь же записаны координаты aL; точки Av соответствующей исходной модели и помещенной в центр параллелепипеда П.
В параллелепипеде П было проведено 512 испытаний. Продолжительность одного испытания т х? 1 цин на ЭВМ Минск-32. Мы приводим фрагмент таблиц испытаний (табл. 2.3), содержащий лишь начало, средний участок и конец таблиц для первых семи критериев.
Первый диалог с ЭВМ. Целью этого диалога было выяснить, существуют ли модели, ле худшие, чем Аг по всем 14 критериям? Иными словами, в качестве критериальных ограничений Ф^* были выбраны значения, соответствующие точке AJ, то есть Ф^* = Фу (Л4) при всех V.
В таблице испытаний оказалось неожиданно много таких точек — 45. Причем нетрудно было заметить, что среди этих точек много существенно различных. Вероятно это связано с тем, что перед конструкторами редуктора не ставилась задача оптимального проектирования.- нужна была «достаточно хорошая» работающая модель.
Второй диалог с ЭВМ. Обычно считается очень желательным уменьшение количества резонансов в рабочей зоне. Исходя из этого, было решено сохранить все Ф** при 1 ^ v ^ 13 и уменьшить Ф** до минимального значения min Ф14(Л,-) = 2, то есть выбрать Ф** = 2.
Количество пробных точек, удовлетворяющих новым критериальным ограничениям, сразу резко уменьшилось до четырех — А31в, Азв0, Л416, Л4М (табл. 2.4). Ни одна из этих точек не является наилучшей по всем четырнадцати критериям ’.
Выбор наилучшей пробной точки. Эта, вообще говоря, сложная задача (см. гл. 3), решается в рассматриваемом случае очень просто: сравнивая значения критериев для найденных четырех точек, легко заметить, что точка Л41в — наилучшая по всем критериям, кроме Ф6, Ф, и Ф13, причем значения Ф6 (Л41в) и Ф,(Л416) отличаются от наилучших всего на 0,3%. Из табл. 2.5 видно, что точка
§се<четыре точки приближенно эффективны в смысле определе- НЮ^риведецного в гл. 3,
to
Таблица 2.3 Таблицы испытаний
Номер п/п ‘ фТочТ"! i Ф«(А<) i Ф, (А{) i Ф,(А(Т1 * Ф,(А<>< Ф.(А«)< ФЛаТТ
*фя-<смсоь*оосмсосо*фю<оь*ь-ь*ооо>*< СО ОО СИСИ СП О О О О ОООсГоОО^ 1Л1ЛЮЮ1Д1ОФСОФСОФФФФСОФФ(Р
Г-00 00 00 00 00 00 *Ф MD
co co co co co co co • *Ф *ф
CO COCOCOCOCOCO • b- ь»
*g*srOCMCM*M*OCMOOCMCO'M*OCDCMsrcDO <^QO'rAC0CQC0b-»,M<0>UDCDCM*rACMCM-vSsr CO *Ф co CM co CM CM co co co cm co cm sr co
CO Ь* О 00 CD яга MD »ЮЬ» •OCOQ^CMOO -COST • co *Ф-vs cm cm co md • co
<DOO0>O*M,UDb*OOOssCM«M<*^CDOOOOssis
CO 00 Op O> О О О О» О О О О ОО О О -*s*s ООООООООООООООООООООО)0>0>0>0>Сд
CM CM CM co co sr sT UD00
OOOOOOO «-Vi^ V< V< ЯГА ТА ЯГА ЯГА ягАягА ягА
СМ О CM CM CM CM 00 ФЬ#ФОО) СО и 00*Ф CD CD **Op**C*OC>^COOCOsrOCDMDCMOO*A-^ *га см СО СО СО *Ф -vs сосо sr *а *ф *ф см
О> О> СО Ь» О> 00 см • Ь-Ъ> • СОСОФСОСМЮСО -ООО • -VI сО со sTcOcO • sT
0)юсосмсо*Ф1лооо>ягасм«фююсосоь*ь*
<D^t*oooooooooooocncncnG>cncncncncn CD ф CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD СО
ЯГА ЯГА -rt ЯГА ЯГА ЯН ягА О>Ь»
•ЮЮЮЮЮЮЮ • ягА СМ
Ь* Ь- Ь» Ь* Ь» Ь» ь- - 00 00
<оуоосмооо**оосм'*смо*»смсмоо**о1 -HO**-r*oO-*<DOCRC<lr~OcO-*t~OOOOQ ** СО СО "I см *» СМ СО СМ СО** СМ -п**сО
О> Ь* ** VA ЯГА 00 00 *Ю*А
С) Ь* МОЮ г- Ь" • ягА с*
sr is сосо sr• СМ
^н'гАЬ-О'ФЮСОСООчИЮЮФ-'-'СМ'*#*»*# со*ф*Ф1йюсософс*ь»ь»ь»ь*оооооооооо
Ш Ья. Ь- СП О О ^ *Ф см • sr sr *# sr ю Ю MD »ою
«ИягАягА^^ягАягА^А^АягАягАягАягАягАягАягАягАягА
«^ «^ *<Г *4* *4* *d* *4* • b* Ь*
*Ф*ФОоОСОСОСМОСМСОСрСМФСМО*ФОСМ С0С*Ф^Г10<00>*Ф00Ь-О1ГЭС0С0СМ-^»ФСМ со со СМ СМ со со sT^sTsT СМ СО CM
-т-А CM ST СМ 00 to U0 • соь»
СМ *а ЯГА СО Ь- 00 Щ • sr о sT со sr -vs CM • ю
ООМОО>*ФСОЬ-ФФООЬ-ОягаСМсОСОСОЮ сосоююсос*г*о>о5смсососо<осососог* Ю UD Ю Ю uD Ю MD Ю UD CD CD CD CD CD СО CD CD CD оооооооооооооооооо *ф*фоо*фоосмсосмо*фсм*ф*фсмсоосм ООСООСОО^СОЮОСМСМ-гАСО^С*1»-**#*? СО *Ф см со см СМ СО со СМ СМ со STCOCO
00 00 СМ СО 00 о> СП юо • г» ь-орарорФор «ь-яю • со со со со со со со • СМ-Ф
V ЯГА «н ЯГА ЯГА -VS Н СОСО
ю со Q ю оо *А << . г- аэ •СМСООЬ-СО СО я*ФЮ
*Ф-^смсо СО • СОСО
COCDCDCMCMt-CDOCOO-nCMCO-glOO^CMQ *н СО ** Ю О О -г* ** Ю Ф ф ф ф СО CD Г» t-* 00 СО СО СО СО ****** ************ **********
sr см о? а? см со мосмsy
см со со со sr sr sT•00CM
•vs ^А ЯГА ЯГА ЯГА ягА яН•СМ*Ф
•н ЯГА ЯГА ЯГА ЯГА ЯГА ЯГАСОСО
СОООСМООСМСМОООЬ»*ФСМСОоО;ФСМСМО*Ф -s-M*-vs*»O СО MD CO CM CM CH CM cd sT b* *Ф MD *ф co -vs -Ф co CM та СМСО-гАята COvACM
• ю ь» ю со ю со ю • о>ь* • о> Ю SS о> СМ Ю UD • ООО • ЯГА ST IS -VS СО я ST
-гасМСМ 4 и) ОО 00 со со
iscMco*^uD<Db»ooo>OsscMco^2SbS5 * SooooSSeoS ‘^2
Таблица 2.4
Значения Фу (-4,) в четырех точках
i
V = 1
2
3
4
5
6
7
216
2,55
8,07
0,714
3,22
2,43
70,6
91,1
60,7
390
3,17
9,28
0,903
72,9
93,3
63,0
416
1,46
3,13
0,663
1,96
66,9
91,1
60,9
484
1,99
5,43
0,740
2,30
69,7
90,8
62,0
Лае оптимальна среди всех 512 пробных точек по критериям Ф1 и Ф& из первой группы и по критерию Ф2 из второй группы. Из табл. 2.3 видно также, что она входит в число двадцати наилучших по критериям Фа, Фа и Ф7. Поэтому наилучшей пробной точкой была объявлена точка Лав- Значения координат этой точки приведены в табл. 2.2.
Улучшение точки Лае- Сравнив координаты точки Лае с границами параллелепипеда П (см. табл. 2.2), нетрудно заметить, что шесть из координат близки к границам П, а именно cCae,i,-®a*,a ®а*.*1 ®a*.#> ®ei*,io в ®а*.и близки к а?, а**, а?, а?*, а??, ац. В соответствии с рекомендацией, высказанной в конце раздела 3.1, была рассчитана пробная точка Л', у которой зти шесть коор-
Таблица 2.5
Значения критервев
V
mln Фу(Ар
Фу (At)
max Фу(Ар
Фу (А««)
Фу (А')
Фу (А)
1
1,46
3,99
10,01
1,46
1,37 2,98
1,29
2
3,13
12,97
34,24
3,13
2,66
3
0,530
1,389
3,450
0,663
0,577
0,578
4
1,31
4,37
17,52
1,96
1,43
1,38
5
66,9
75,1
82,7
66,9
66,3
66,0
6
- 88,6
103,7
111,8
91,1
90,3
89,9
7
58,4
67,0
74,5
60,9
59,9
60,0
8
77,7
91,8
106,1
87,3
83,9
84,3
9
664
2000
5452
861
825
777
10
1502
6490
19550
1850
1796
1601
11
231
697
1735
398
352
353
12
568
2186
10035
1175
948
845
13;
846
1300
1775
1080
1080
1075
^
3
4
2
2
2
8
9
10
11
12
13
v = M
91,6
1253
3978
426
1920
1025
2
89,2
1502
4415
505
1355
983
2
87,3
861
1850
398
1175
1080
2
88,7
1054
2881
420
1302
1202
2
цинат заменены граничными значениями, а остальные совпадают с координатами точки Л41в. Из табл. 2.5 видно, что по всем критериям точка А* оказалась лучше точки Л41». По-видимому, минимальные значения большинства из функции Фу (Л) достигаются на границе П.
ЛП-поиск в окрестности А*. Точка А' была помещена в центр пятимерного параллелепипеда
0,95aj ^ ay ^ 1,05a} (/ = 2, 3, 5, 7, 8);
значения a}, а4, а), а), а)0 и а)] были закреплены. Выбрав и рассчитав в этом параллелепипеде 128 пробных точек, мы убедились, что
улучшить точку А' по всем критериям невозможно;
значения Фу (Л') устойчивы при малых изменениях точки А в окрестности А';
среди 128 пробных точек проектировщик выделил одну (с порядковым номером 67), которую следует считать наилучшей. Эту точку мы обозначим Л; координаты ее приведены в табл. 2.2, а значения Ov (Л) — в табл. 2.5.
Так как численные значения Фу (Л) сравнительно мало отличаются от Фу (Л'), то на этом поиск решено было прекратить. Оптимальной точкой была объявлена точка Л. Из табл. 2.5 легко видеть, насколько улучшились значения всех критериев Фу (Л) по сравнению со значениями Фу (Л J для исходной модели.
Замечание. Из табл. 2.4 видно, что если возникнет задача об уменьшении массы редуктора, то наилучшее решение придется искать не в окрестности точки Л416, а в окрестности Лзв0.
Глава 3
ВЫБОР ПАРАМЕТРОВ
После того как множество допустимых точек D определено традиционная схема выбора оптимальных параметров весьма проста: выбирается решающий критерий качества Ф (А) и формулируется задача об отыскании точки А такой, что
Ф(Л) =пппФ(А).
AeD
Координаты точки А и будут оптимальными параметрами Такая постановка задачи обсуждается в разделе 3.1.
Однако весьма часто конструкторы не могут или не хотят вводить один решающий критерий: по их мнению, решение о выборе параметров должно приниматься с учетом нескольких критериев, или даже всех Фъ. . . , Фк, а как сравнивать ценность различных критериев — не ясно. В этой ситуации приходится отыскивать множество возможных оптимальных точек, то есть решать гораздо более сложную задачу. Этому посвящен раздел 3.2.
А в разделе 3.3 рассмотрен важный частный случай, когда заданы два решающих критерия, противоречащих друг другу, и вместо оптимальной точки следует определить так называемую компромиссную кривую.
Один решающим критерий
Мы не будем давать рецептов, как выбирать решающий критерий Ф (А): в разных задачах это делают по-разиому [101. Приведем только несколько, как нам кажется, нестандартных соображений.
О роли Ф (А). В ходе расчета ряда задач мы обнаружили, что после определения, множества D, конструкторы теряли интерес к выбору функции Ф. Они утверждали, что любое решение, удовлетворяющее всем найденным в гл. 2 критериальным ограничениям, является отличным решением задачи. И в качестве «оптимальной» предпочитали выбрать по своему усмотрению одну из найденных точек (ср. пример в разделе 2.4).
Конечно, с математической точки зрения такое решение ЯВ^зя назвать оптимальным. Но именно так нередко при- йаимают;,решение на практике.
Я
О выборе Ф (Л). При использовании нашей методики, когда количество рассматриваемых критериев качества не ограничивается, трудно представить себе, чтобы решающий критерий Ф не зависел ни от одного из Ф1(. . . .’. ., Ф*: так как Ф учитывает какие-то реальные (физические) характеристики проектируемой системы, то ничто не мешало нам включить их в число критериев качества. В частности, решающий критерий может либо совпадать с одним из Ф1Э. . ., Фк, либо зависеть от нескольких из них, так что Ф = F (Ф1М . ., Фк).
Нетрудно понять, что в этой ситуации изучение таблиц испытаний помогает выбрать зависимость F: при этом учитываются не только предварительные указания о роли каждого критерия, но и их действительные возможности.
Пример. Иногда Ф выбирают в форме
к
Ф = 5 СуФу(Л),
V=1
где все cv > О, а сумма их ct -}• . . . + ck = 1. Если из таблицы испытаний видно, что в пределах D изменение значений критерия Фр (Л) не существенны, то естественно положить в последней формуле ср = 0.
О вычислении Ф(Л^. Если решающий критерий Ф есть функция от Фх,. . ., Фк, то, после выбора функциональной зависимости F, значения Ф (Л^ во всех пробных точках At, принадлежащих D, легко вычисляются по имеющимся значениям Фу (Л ():
фио = f (ф^л^, ..., Фк (л^).
Следовательно, сразу после выбора Ф, не пересчитывая всей системы, мы можем найти зцачения Ф (Л{).
В гл. 2 доказано, что последовательность Dn пробных точек, принадлежащих D, представляет собой начальный участок последовательности, равномерно распределенной в D, Поэтому значения Ф(Л^вэтих точках очень полезны для численного решения задачи об отыскании пнпФ (Л) при ЛеО. Можно воспользоваться любым методом локального поиска экстремумов (8, 12, 18], выбирая в качестве начальных точек поиска все точки Л^ принадлежащие Dn или только лучшие из них. Если множество D несвязно (см. рис. 2.3), то только такой глобальный подход может гарантировать, что поиск захватит любые части множества D.
Об использовании ЛП-поиска. При расчете ряда задач мы на этой стадии использовали простейший ЛП- поиск: несколько лучших (по мнению проектировщиков) точек из Dr помещались поочередно в центр малого параллелепипеда, в котором выбирались от 16 до 128 «пробных точек. Если в какой-нибудь из этих точек, назовем ее Л', значение Ф (Л') оказывалось лучше, чем значение в центре (и при этом А'е D^ то иногда выбирался следующий параллелепипед с центром в Л'. Если какая-нибудь из координат точки А' оказывалась близко к границе П, то размер малого параллелепипеда соответственно уменьшался.
Общих рекомендаций на этот счет мы дать не можем. Однако если наилучшая точка А' оказывается вблизи границы П, то мы считаем, что, как правило, имеет смысл сделать еще пробный расчет системы, передвинув эту пробную точку на границу II: наименьшие и наибольшие значения функций часто оказываются на границе.
Мы не утверждаем, что в этих условиях ЛП-поиск эффективнее других методов поиска экстремумов: просто, все необходимое для его реализации (генератор пробных точек, алгоритмы просмотра и отбора) используется в гл. 2 и, следовательно, имеется в отлаженном состоянии. .
Несколько решающих критериев
Предположим теперь, что конструктор желает сам осуществить окончательный выбор параметров системы, принимая во внимание несколько важнейших критериев, например, Фъ. . . , Фт, где, естественно, т ^ к. В этом случае можно облегчить ему выбор, исключив из числа пробных точек, попавших в множество D, такие точки, которые заведомо не могут оказатьсяи наилучшими.
Эффективные точки. Пусть в n-мерном замкнутом множестве D заданы га непрерывных функций Фг(Л), . . . • • ч Фщ(Л). Условимся говорить, что точка А' безусловно лучше, чем точка А, если при всех v = 1, 2, . . ., т
Ф^ (Л') < ф ЛЛ)
и хотя бы при одном v имеет место строгое неравенство. В этом случае можно также сказать, что точка А безуслов- нохуже, чем точка А*.
Дпре деление. Если не существует точки A'eD, безусловно лучшей, чем А, то точка А называется эффек-
тивной а; если существует точка А', безусловно лучшая, чем А, то точка А называется неэффективной. , )
Очевидно, при окончательном выборе параметров нужно принимать во внимание только эффективные точки: неэффективная точка не может оказаться наилучшей.
Множество всех эффективных точек обозначим Е. Важнейшие свойства Е сформулированы в известных теоремах 1 и 2.
Теорема 1. Если множество D замкнуто и все функции Фг(Л),. . . , Фт(Л) непрерывны, то множество эффективных точек Е непусто.
При доказательстве этой теоремы мы воспользуемся следующим простым свойством непрерывной функции / (А), определенной на замкнутом множестве: подмножество, состоящее из всех точек А, в которых / (Л) = с, либо пусто, либо замкнуто. В самом деле, если последовательность точек Ai, . . ., At, . . ., в которых / (Ai) = с, сходится к точке Ао, то из непрерывности / (А) следует, что / (Ао) = = с; следовательно, точка Ао принадлежит тому же подмножеству.
Перейдем к доказательству теоремы. Рассмотрим множество Di С D, состоящее из точек А таких, что
Ф1(А)=ш1п Ф2(А).
AeD
Это множество непусто. Если оно состоит из одной точки Ао, то эта точка эффективна, ибо в любой другой точке А' значение Ф, (А) > > Ф1 (А 0). В противном случае рассмотрим множество ^СДр состоящее из точек А таких, что
Ф2(А) = min Ф3(А).
Множество D, также непусто. Если оно состоит из одной точки Ао, то эта точка эффективна (ибо в любой другой точке А' е Di значение Ф2 (А') > Ф. (Ао), а в любой точке А' е D — Вг значение Ф1 (А') > Ф1 (Ао))- В противном случае рассмотрим множество Ds С Ь4, состоящее из точек А таких, что
Ф3 (А) = min Ф3 (А) и т. д. .
Леп,»
Если на каком-то этапе множество D. состоит иэ одной точки, то эта точка окажется эффективной. В противном случае мы придем к множеству Dm, состоящему из точек А таких, что
Ф„(Л) = ^i*1 ®mM).
Докажем, что все точки множества Dm эффективные. Пусть Ао е Dm. Точка A' eD — Dx не может быть безусловно лучше,
Рис. 3.1. Множество допустимых точек D и множество эффективных точек Е в пространстве параметров и соответствующие множества возможных значений D и паретовскнх точек Е в пространстве критериев
чем Ло, так как Ф! (Л')>Ф1 (Ло); точка А' е Di—Dt также не может быть безусловно лучше, чем Ло, ибо Ф2 (Л')>Фа (Ло); и т. д. Наконец, точка А' е Dm не может быть безусловно лучше, чем Ло, ввиду того, что Фv (Л') = Фv (Ло) при всех v = 1, 2, . . ., m.
Таким образом, иепустота множества Е доказана.
Пространство критериев. Рассмотрим m-мерное пространство точек с декартовыми координатами (Фц. . . . • •> Фт)- Каждая точка Л пространства параметров отображается в точку В = (Ф^Л),. . ., Фт(Л)) пространства критериев. Множество всех точек В, соответствующих всевозможным Лей, назовем множеством возможных точек D в пространстве критериев. Если выполнены условия теоремы 1, то множество D замкнуто. Если часть границы множества D определяется критериальным ограничением Фv (Л) Ф**, то соответствующая часть границы D состоит из куска гиперплоскости Фу = Ф**.
Множество всех точек В, соответствующих всевозможным эффективным точкам Л Е £, назовем множеством паретовскнх точек Е.
Нетрудно доказать, что паретовские точки расположены на границе множества возможных точек D (рис. 3.1). Это вытекает из следующего свойства, которое часто называют минимальным свойством эффективных точек.
Теорема 2. Предположим, что множество Е непусто, точка Ло ЕЕ Е й Фу (Ло) = 6V прим = 1,2,... . . ., т. Для каждого фиксированного vb, - min Фу (Л), при условии, что A G D и Фи (Л) = Ь^ при всех р, отличных от v.
Доказательство. Фиксируем для определенности v = 1. Теорема утверждает (см. рис. 3.1), что
^ = min {Фх (Л) | Ф2 (Л) = 62Фт (Л) = Ьт} (Л е Л).
Если допустить противное: что в какой-то точке А' значение Ф1 (Л') <( Ь, и в то же время все остальные значения Ф2 (Л') = Ь2, . . ., Фт(Л') = Ьт, то окажется, что точка А' безусловно лучше, чем Ло; а зто противоречит предположению об эффективности Ло.
При любом другом фиксированном v рассуждения аналогичные, так что теорема 2 доказана.
Заметим, что минимальное свойство представляет собой необходимый признак эффективности точки. Из рис. 3.2 легко усмотреть, что этот признак, вообще говоря, не достаточен: не только эффективные точки обладают этим свойством.
Действительно, если и гипербола ВВ'В", и отрезок В^В* принадлежат изображенному на рис. 3.2 множеству возможных точек D, то из всех точек отрезка лишь его конец В0 будет паретовской точкой. Однако свойством минимума (по обоим критериям) обладают все точки А, отображающиеся в отрезок BqB'.
В общем случае размерность множества паретовских точек Е равна m — 1. Это видно из следующего рассуждения: фиксировав произвольные возможные значения Ь2, • - ., Ьт1 мы получим одну соответствующую им паре- товскую точку (Ьп Ь2, . . ., 6т), в котрой Ьх определяется как условный минимум Фх (А).
Рис. 3.3. К алгоритму исключения неэффективных точек. Приближенно паретовскне точки обведены кружками
Приближенно эффективные точки. Предположим теперь, что в результате расчета, описанного в гл. 2, мы получили конечное множество Dr, состоящее из q пробных точек А,, принадлежащих О, и в этих точках известны все значения Фу (Л/) при v = 1, 2, . . ., т.
Определение. Точка At из Dr называется приближенно эффективной, если не существует такой точки Л; из Dr, которая была бы безусловно лучше, чем At.
Множество всех приближенно эффективных точек из Dr обозначим Er. Очевидно все точки из Dr, которые не принадлежат Er, не эффективны и неэффективность их может быть обнаружена сравнением значений ФУ(Л^ в различных точках.
Простейший алгоритм выделения приближенно эффективных точек. Пометим какую-нибудь точку Аииз Dr. Сравнивая ее со всеми остальными точками из Dr, исключим все точки Aj, которые безусловно хуже, чем А,. Затем из оставшихся точек выберем непомеченную точку, например. Л,, и пометим ее. Сравнивая ее со всеми оставшимися точками (включая At^, исключим те из них, которые безусловно хуже, чем Л(, и т. д. После конечного числа шагов останутся только помеченные точки. Докажем, что все оставшиеся точки приближенно эффективны.
В самом деле, пусть Л, — какая-нибудь неэффективная точка из Dr — Er. Значит, существует хотя бы одна безусловно лучшая, чем Л„ точка At. Если точка Af в процессе исключения уцелела, то, очевидно, точка Л, была исключена: самое позднее — на том шаге, на котором выбиралась и помечалась точка Av Если точка Л{ сама была исключена, то на том же шаге должна была быть исключена и точка Л, (так как если А^ безусловно лучше, чем Av a At безусловно лучше, чем А„ то Aj также безусловно лучше, чем Л,); опять же — при условии, что точка Л, не была исключена еще раньше.
Геометрическая интерпретация этого алгоритма особенно наглядна, если рассматривать изображения пробных точек в пространстве критериев (рис. 3.3.): выбрав точку А(„ мы исключаем все точки Лj, образы которых попали в* квадрант (в многомерном случае — гипероктант) с вершиной в точке Bit — образе точки At,.
Рис. 3.4. Специальная е-окрестность аффективной точки (а) и неэффективной точки (б)
Используя приведенный алгоритм, нетрудно исключить из множества -Фн заведомо неэффективные точки и получить множество Ен, состоящее из q0 ^ q приближенно эффективных точек. Как правило, для поиска приближенно наилучших точек конструктор может ограничиться изучением множества Ен- О возможных исключениях из этого правила см. в замечании в конце раздела 3.3.
О сходимости. В общем случае вопрос сходимости EN к Е при N —♦ со достаточно сложен. Мы ограничимся здесь сравнительно простой теоремой, которая тем не менее потребует введения специального аппарата. Мы будем предполагать, что
1°. Условия теоремы 1 выполнены;
2°. Среди точек множества Е нет двух таких, в которых все критерии совпадают.
Для каждой точки Ло из Е определим специальную г-окрест- ность S (Ло, е), как множество точек AeD таких, что при всех 'V = 1, 2, . . ., т
Фу W < фу М + 81 W
Пример такой окрестности при m = 2 изображен на рнс. 3.4, а.
Докажем, что при е —• 0 множества S (Ло, е) стягиваются к точке Ло. В самом деле, очевидно Ло е S (Ло, е) при любом е > 0. Если допустить, что точка А' также принадлежит всем S (Л0, е), то из (1) при е — 0 получим, что Фу (Л’) < Фу (Ло) для v = 1, 2,... • ..,т. Так как точка Ло эффективная, то отсюда вытекает, что Фу (Л') = Фу (Ло) при всех v. Ясно, что этот вывод противоречит допущению У-
Заметим, что если точка А* е В — Е, то множество S (Л', е) может иметь весьма странный (для «окрестности») вид (рнс. 3.4, б) и при е —♦ 0 не обязано стягиваться к А*.
Если точка Ло е Е представляет собой внутреннюю точку множества В, то можно построить шар с центром в Ло столь малого радиуса, чтобы в этом шаре I Фу (Л) — Фу (Ло) | < е при всех v.
Тогда весь этот шар принадлежит £ (Ло, е), и объем (п-мериый) специальной е-окрестности положителен.
Если точка Ло е Е представляет собой граничную точку множества Д, и в любой ее окрестности имеются внутренние точки В, то аналогичные рассуждения показывают, что объем S (Ло, е) также будет положительным.
Следовательно, если множество В совпадает с замыканием множества своих внутренних точек (как это предполагалось в гл. 2), то для любой точки Л о е Е объем S (Ло, е) положителен.
Рис. 3.5. Специальная е-окрестность в пространстве параметров и ее образ в пространстве критериев
Напротив, если Ло е Е — изолированная точка множества В, то при всех достаточно малых е множество 5 (Ло, е) содержит лишь одну точку Л о и объем S (Ло, е) равен нулю. Так что, если не делать предположения о совпадении В с замыканием множества его внутренних точек, то положительность объема специальной окрестности S (Л о, е) следует оговаривать особо.
Теорема 3. Предположим, что выполнены требования 1° иУ, В ыберем любые точки А®, . . ., А® из Е с окрестностями положительного объема S (А®, е), . . ., 5 (Л°, е). Можно указать такое Wo, что когда количество пробных точек N превосходит Пй, то в каждой из этих окрестностей найдется хотя бы по одной точке из En.
Доказательство. Так как последовательность пробных точек равномерно распределена в G, то можно выбрать N» столь большим, чтобы в каждую из s фиксированных окрестностей попала хотя бы одна пробная точка. Тогда в каждой S (Л®, е) найдется хотя бы одна точка А^ из BN1.
Если эта точка приближенно эффективна, то она и будет искомой точкой из Ем; в противном случае должна существовать другая приближенно эффективная точка Л,к е BNl, безусловно лучшая, чем А^. Но в этом случае Фу (Л.р < Фу (Л^), и точка Л^ также принадлежит S (Л^ е).
Следовательно, в каждой окрестности S (Л°, е) найдется приближенно эффективная точка из BN , то есть точка из ENi.
При дальнейшем увеличении N приближенно эффективная точка A j может перестать быть таковой, но только в том случае, когда появится новая приближенно эффективная точка, безусловно лучшая, чем At . Вышеприведенное рассуждение показывает, что эта новая точка принадлежит той же специальной е-окрестносиг S (Л°, е),что и точка At . Таким образом, утверждение теоремы полностью доказано.
Замечание. В пространстве критериев специальной е- окрестности 5 (Ло, е) эффективной точки А 0 соответствует односторонняя пирамидальная окрестность паретовской точки BQ = (Ф1 (Ло), . . .,-Фт (Ло)); на рис. 3.5 обе эти окрестности заштрихованы.
Компромиссная кривая
Особый интерес для практики представляет частный случай, когда заданы два решающих критерия, m = 2. В этом случае множество паретовских точек представляет собой, вообще говоря, одномерное многообразие на плоскости и допускает удобное графическое представление.
Рис. 3.6. Компромиссные кривые с разрывом (а) и с изолированной точкой (б),
Компромиссная кривая. Множество паретовских точек в двухмерном пространстве критериев называют компромиссной кривой. Хотя, строго говоря, это не всегда кривая: она может состоять из несвязных кусков и содержать изолированные точки (рис. 3.6).
Легко, однако, доказать, что компромиссная кривая строго монотонно убывает в следующем смысле. Пусть В и В' — произвольные точки, принадлежащие компромиссной кривой. Обозначим их координаты В = (Ьи Ь,),
В* = (bl, bl). Тогда,
(2)(2)если Ъх ■< bl, то Ьа > Ь*
(2)
(2)
В самом деле, если бы оказалось, что ^ < bl и Ь, ^Ы, то прообраз точки В' был бы безусловно хуже, чем прообраз точки В, и не мог бы принадлежать множеству эффективных точек Е.
Как следствие неравенств (2) можно сказать, что компромиссная кривая не содержит ни горизонтальных,- ни вертикальных отрезков, и уравнение ее может быть представлено и в форме Ф2 = и (Ф^, и в форме dj = v (Ф,).
, позволяет среди, позволяет средиОФ,абОФ,абПриближенная компромиссная кривая. Алгоритм, приведенный в предыдущем naj
, позволяет среди
, позволяет среди
ОФ,
аб
ОФ,
аб
Рис. 3.7. Пробные точки и приближенные компромиссные кривы е соответствующие рис. 3.6
Приближенно паретовские точки обведены кружками
g пробных точек Dn отобрать конечное число д0 приближенно эффективных точек, составляющих множество Er.
Назовем приближенно паретоеской точкой образ приближенно эффективной точки в пространстве критериев. Повторяя рассуждения, приведенные в предыдущем пункте, легко доказать, что если В=(Ьц Ь2) и В' = (Ьп Ъ^ — две приближенно паретовские точки, то справедливо свойство (2): если Ьх ■< bl, то Ь2 > Ь'г.
Легко также проверить, что если В' =/= В, то и Ъх =5^ bt и Ь2 Ф Ьа (ибо, в противном случае, один из прообразов точек В и В’ был бы безусловно хуже другого и не мог бы быть приближенно эффективной точкой). Следовательно, все приближенно паретовские точки можно упорядочить по возрастанию абсцисс или, что то же, по убыванию ординат.
Приближенной компромиссной кривой называется ломаная, соединяющая по порядку все приближенно паре- товские точки (рис. 3.7).
. Из вышесказанного следует, что приближенная компромиссная кривая строго монотонно убывает, и уравнение ее может быть записано как в форме Ф, = и^ (Ф^ так и в форме Ф! = Vn (Ф1). Мы докажем, что когда количество пробных точек N возрастает, то приближенная компромиссная кривая в некотором смысле приближается к точной компромиссной кривой.
Теорема о сходимости.-
Теорема 4. Предположим, что множество D замкнуто, и функции Ф1 (А) и Ф, (А) непрерывны. Предположим, что множество Е или какая-то его часть, состоящая из течек со специальными окрестностями положительного объема, взаимооднозначно отображается на простую дугу компромиссной кривой. Пусть В = = (Ьп Ь,) — произвольная точка, расположенная внутри етой дуги. Тогда'
Um и„ (ЬЛ = b2,lim vN = bx.
N—xN—»
Доказательство. Мы будем доказывать только первое утверждение теоремы, так как. второе доказывается в точности так же.■■
Сперва докажем, что приближенная компромиссная кривая Ф, = uN (ФО определена для фиксированного нами значения Ь2 при всех N "> Пй. В самом деле, обозначим
6* -- min Ф! (Л), Ъ* = min Ф2 (А)
AeDAgD
и пусть приближенные значения минимумов равны
Ф*м = min Ф2(Л),ф*^= min Ф2(Л).
*- A^D^* A^D^.
При N -♦ оо, как следует'из главы I, Ф* N -» Ь*, Ф* N -♦ Ь . Следовательно, при увеличении N, среди точек последовательности BN найдутся точки со значениями Ф2 как угодно близкими kJ Ь* и со ■ значениями Ф„ как угодно близкими к Ъ*. Легко видеть, что точки множества Д№ с минимальными значениями Ф2 или Ф, приближенно эффективны и принадлежат EN. Поэтому при N ^ No среди точек EN найдутся точки А, и Ау со значениями, удоэлетворяющимн неравенствам
6*<Ф1(А,)<Ь1,Ь*<ФгИ^<Ь*."
Так как точка В паретовсиая, то Ф, (A j) > Ь,; и отрезок существования приближенной компромиссной кривой Ф2 (А,)СФ^Ф! (А у) накроет значение bv•
Рис. 3.8. К доказательству теоремы 4
Выберем теперь сколь угодно малое число е > 0 п докажем, что при всех N ^. Ni^. No
1“к(М —М<е.
Для доказательства проведем на плоскостп критериев (рис. 3.8, а) прямые Ф2 = 62 — е и Ф2 = ^2 + 8 и построим криволинейный треугольник KLM. В пределах полосы | Ф, — 62 I < < е выше и ниже точки В выберем на дуге точки В' и В”, и пусть А' и А" — их прообразы в множестве Е.
Фиксируем 6 > 0 так, чтобы специальные окрестности 8 (Л', 6) и 8 (А", 6) отображались внутрь KLM. Согласно теореме 3 можно указать Nx такое, что при всех N "> Nxe каждой из этих двух окрестностей найдется хотя бы по одной точке из EN. Соответствующие этим точкам приближенно паретовские точки попадут в треугольные окрестности точек В' и В (рис. 3.8, б). Как бы пи располагались соседние с точкой В приближенно паретовские точки, оии не могут выйти за пределы криволинейного треугольника К'L'M', расположенного внутри KLM. Следовательно,
62 — е < uN (6t) < 62 + е, что и требовалось доказать.
Изучение приближенной компромиссной кривой. Приближенная компромиссная кривая — ломаная, и поэтому всегда непрерывна. Если точная компромиссная кривая имеет разрывы, то при увеличении количества пробных точек можно обнаружить участки приближенной кривой, которые стремятся к вертикальным отрезкам, и приближенно оценить эти разрывы. .
Несколько сложнее выделить участки, на которых компромиссная кривая не определена: для этого одних приближенно паретовских точек недостаточно (см. рис. 3.7, я). Лишь нанеся на график образы всех пробных точек, можно получить представление о форме области возможных значений D и догадаться, что на каком-то участке компромиссная кривая не существует.
Обнаружить нашим методом изолированную точку компромиссной кривой, как правило, нельзя, хотя изучение расположения всех точек и в этом случае позволяет иногда догадаться, что, возможно, такая-изолированная 1*очка и существует (рис. 3.7, б).
Впрочем, на практике обычно используют не участки приближенной компромиссной кривой, а лишь полученные приближенно паретовские точки, которым всегда отвечают реальные приближенно эффективные варианты системы.
Замечание. Пример, изображенный на рис. 3.7, б, показывает также, что в некоторых задачах непаретовские точки (например, точки, расположенные в окрестности изолированной паретовской точки) могут представлять определенный интерес для конструкторов. Наша рекомендация: если в интересующей конструкторов эоне приближенно эффективных точек нет (или мало), то следует проанализировать лучшие из неэффективных точек в этой зоне. -
Примеры расчета
приближенных компромиссных кривых
В этом параграфе рассмотрены две простые задачи, в которых компромиссные кривые могут быть найдены аналитически, и сосчитанные приближенные компромиссные кривые сравниваются с точными.
Аналитический подход [31. Если функции Фх (А) и Ф2 (А) дифференцируемые, то можно попытаться найти геометрическое место точек соприкосновения поверхностей уровня Фл (А) = Ъх и Ф2 (А) = Ь2. В таких точках
grad Фл = —X grad^g.
Последнее векторное уравнение равносильно п скалярным алгебраическим уравнениям
дФл/до, = —ХдФ81да} (j = 1, 2, . . ., п), которые, вообще говоря, определяют кривую в пространстве параметров:
«1 = Ф1 М» • • •. «п = Фп W-
Если участок этой кривой, на котором X > О, принадле- • жит множеству D, то он принадлежит й множеству Е.
Рис. 3.9. Линии уровня Ф! = const и Ф2= const и множество точек соприкосновения А А'А* Множество аффективных точек — дуга ДА*
Например, на рис. 3.9, который соответствует приведенному ниже примеру 1, дуга А А* состоит из эффективных точек, а дуга А'А* — из точек соприкосновения, не являющихся эффективными точками, хотя обе эти дуги описываются одним уравнением а, = = 4а1/(3а1 — 1).
Участок компромиссной кривой в этом случае определяется лараметрическими уравнениями
Фу = Фг (Ф1 (X). • • •» ф„ (X)),'’
Ф, = Ф2(ф1(Х), • • ..Ф„(Х)), (Х>0).
Вдоль этой кривой'
пп
dФ1 = 2 (дФ1[да^ dtp,- = — X ^ (дФ2/да,) dtp, = — XdФ2 j=ij=i•
откуда для наклона компромиссной кривой получается выражение dФ1ldФ1 = —1/Х.
Пример 1. В квадрате D = {—1 ^ ах < 1, —1 «^ а2 ^ 1} заданы два критерия
Фх = 4а? + а? и Ф2 = (ах + I)2 + (а2 — I)2,
которые желательно минимизировать.
Абсолютные минимумы функций Фх и Ф2 реализуются соответственно в точках (0, 0) и (—1, 1), принадлежащих D. Поэтому линия Е должна соединять эти точки. Вышеуказанным аналитическим методом получаем участок А А* гиперболы а2 = 4ах (Зах — I)-1, изображенный на рис. 3.10.
Рис. 3.10. Пример 1. Множество допустимых точек D в пространстве параметров и множество возможных точек 5 в пространстве критериев
Множество Я — дуга АА', множество Я — дуга ВВ'
Рис. 3.11. Пример!. Точная и приближенная (пунктир) компромис
сная кривая при N = 63
Крестика — приближенно паретовские точки при N •= 255
Часть/?, расположенная правее линии А А 'А", отображается на плоскости критериев в криволинейную фигуру ВВ'В’В"Впр, а часть D, расположенная левее линии А А 'А', отображается в фигуру ВВ’В'Влеъ, таким образом, точки средней части множества D имеют в D по два' прообраза. Компромиссная кривая — это линия ВВ*.
Рис. 3.12. Пример 1. Пробные точки в D и в В при ^ = 63
Приближенно эффективные и приближенно паретовские точки обведены кружками
Рис. 3.13. Пример 2. Множество допустимых точек В в пространстве параметров и множество возможных точек В в пространстве критериев
Множество Е состоит из дуг АА'А* и А*А*А*. множество Е — из дуг В В1 В* и В‘В*В*
Результаты расчета этой задачи приведены на рис. 3.11 и 3.12. На первом из них построена точная компромиссная кривая Ф2 = и (Ф1) и приближенная линия Ф, = = un (Ф1). (При N = 511 точная и приближенная компромиссные кривые совпадают с точностью до 0,01). На рис. 3.12 построены все пробные точки в D и в D. На этом рисунке заметна повышенная плотность точек в средней
Рис. 3.14. Пример 2. Точная и приближенная'(пунктир) компромиссная кривая при ^ = 63" ■
Крестики — приближенно паретовские точки при N = 255
Рис. 3.15. Пример 2. Все о пробных точек в пространстве критериев при ^ = 63 и при N = 255
части D. Видно также, что Е^ приближается к Е. быстрее, чем En к Е. »
- Пример 2. В квадрате П = {— 0,5 ^ а, ^ 0,5, 0 < а2 < 1} заданы два критерия
Ф1 = а® + 4а3 и Ф2 = (ах + I)2 + (а2 — I)2 , которые желательно минимизировать с учетом функционального ограничения
| а3 — ах — 0,375 | > 0,125.
Множество D в этой задаче представляет собой квадрат П с вырезанной полосой (рис. 3.13). Множество Е состоит из двух участков АА1 и А4А® гиперболы а3 = = — ах (Зах + 4)-1, из отрезка 4’4* границы ах = —0,5
и из отрезка А\А6 границы а$ — ат = 0,25. Здесь же изображена область D на плоскости критериев. Однако части D, состоящие из точек, имеющих по два прообраза в D, в этом примере гораздо меньше, чем в примере 1.
Точная компромиссная кривая изображена т.кже на рис. 3.14. На рис. 3.15 построены пробные точки в D. По картине, полученной при N = 63, нельзя с уверенностью сказать, что множество D состоит из двух раздельных частей; но из картины, полученной при N = 255, это уже вполне ясно.
Глава 4
НЕКОТОРЫЕ ВОЗМОЖНОСТИ МЕТОДА
В этой главе рассмотрены некоторые вопросы, которые можно решать используя метод, изложенный выше. В разделе 4.1 приведен автоматизированный вариант диалогового алгоритма, хотя мы считаем, что на этой стадии исключать вмешательство проектировщиков нецелесообразно. В разделе 4.2 изложен метод изучения зависимости критериев, а в разделе 4.3 речь пойдет о возможностях изменения постановки задачи с целью улучшения характеристик оптимального решения.
Автоматизированный вариант диалога
Алгоритм, изложенный в разделе 2.2, можно полностью автоматизировать так, чтобы критериальные ограничения выбирались без вмешательства человека.
Простейший вариант. Фиксируем произвольное целое число М > 1. Первый этап диалогового алгоритма оставим без изменений. На втором этапе для каждого критерия Фу вычисляется шаг
где Фу (Aj,) и Фу (A 1N)— наименьшее и наибольшее значение Фу (А{) или, иными словами, наибольший и наименьший элементы v-й строки матрицы ЦФу(А1)|. В качестве критериальных ограничений выбираем значения
Ф** = Фу (А,,) + Ay.(1)
Если на третьем этапе множество D окажется пустым,
Рис. 4.1. Автоматический выбор критериальных ограничений: процесс заканчивается на 4-м шаге
то возвращаемся ко второму этапу и увеличиваем все критериальные ограничения
Фу (новое:= Фу (старое 4" ^v-.
Очевидно, при таком повторении второго и третьего этапов потребуется не более, чем М, повторений, и множество допустимых точек D окажется непустым.-
Геометрическая интерпретация этого алгоритма в пространстве критериев дана на рис. 4.1, где 6V = min Фу (Л <), i
cv = max Фу (Л f) и М = 10.
Недостатки такого варианта довольно очевидны: коли- четство шагов по всем критериям одинаково, все критериальные ограничения увеличиваются одновременно, хотя среди критериев есть более существенные и менее существенные. Можно пытаться устранить эти недостатки, вводя приоритеты критериев, различные шаги для различных критериев, прибавление некоторых Л^ не при каждом повторении второго этапа. Однако все такие заранее задаваемые тактики, по нашему убеждению, гораздо менее эффективны, чем рекомендации специалистов, основанные на изучении таблиц испытаний.
Кроме того, полная автоматизация диалога может привести к неоправданному сужению множества допустимых точек D, что также весьма нежелательно. Поясним зту ситуацию несколько подробнее. Допустим, что при первой же проверке критериальных ограничений (1) множество D оказалось непустым и в него попала одна точка Ль. Процесс выбора критериальных ограничений на этом закончится. Хотя вполне возможно, что среди точек Л,, не
удовлетворяющих ограничениям (1), есть такие, в которых значения Фу (А^ при некоторых v вполне приемлемы, а при других (более существенных) — значительно лучше, чем Фу (Ait).
Сопоставление с другими методами. Автоматизированный вариант нашего метода имеет некоторое сходство с методом последовательных уступок [51 и с методом ограничений [41. Но сходство это скорее внешнее. Не вдаваясь в подробности упомянутых методов *, заметим, что в каждом из них приходится многократно решать задачи на отыскание экстремумов каждой из функций Фу (А) при различных ограничениях.
В нашем методе минимумы и максимумы всех функций Фх (А), . . ., Ф* (А) в G оцениваются приближенно по одному и тому же набору пробных точек А^ Ясно, конечно, что совсем не обязательно знать точное значение минимума Фу (А) для того, чтобы выбрать ограничение сверху —Ф^*-
Исследование зависимости критериев
Мы уже отмечали, что при нашем методе выбора критериальных ограничений и определения множества допустимых значений (гл. 2) число критериев качества может быть произвольным. Конструктор может указать любые критерии, не заботясь об их независимости. Лишние критерии не мешают выбору критериальных ограничений.
Однако выделение важнейших критериев представляет интерес при построении различных аналитических методов приближенного изучения исследуемой системы.
Оказывается, матрица |ФУ(А()| позволяет сравнительно просто оценить степень линейной зависимости между любыми двумя критериями. Для этого можно использовать одно хорошо известное свойство коэффициента корреляции случайных величин.
Коэффициент корреляции — мера линейной зависимости случайных величин. Предположим, что ц и — произвольные случайные величины, у которых существуют конечные математические ожидания Мц и М£ и дисперсии 2 Оц > 0 и D£ > 0. Тогда существует коэффициент
См.: Повиновений В. В., Гаврилов В. М. Оптимизация по последовательно применяемым критериям. М.: Сов. радио, 1975.
• Напомним, что £>ц = Мц2 — (Мц)2.
корреляции этих величин
г(чЛ) =г(чЛ) =м^^м^м^м^^м^м^(2)(2)
г(чЛ) =
г(чЛ) =
м^^м^м^
м^^м^м^
(2)
(2)
Как известно, г (5, ч) = г (ч, В) и —1 ^ г (ч> I) ^ !• Если ч и £ независимы, то г (4, |) = 0.
Мы воспользуемся следующим свойством коэффициента корреляции, которое можно найти в большинстве курсов теории вероятностей:
условие | г (ч, ^) | = 1 необходимо и достаточно для того, чтобы существовали постоянные с^О и с, такие, что с вероятностью 1
6 = с0Ч + cv(3)
Случай се> 0 соответствует условию г (4, £) = 1, а случай с0 < 0 — условию г (ч, £) = — 1.
Корреляция критериев. Пусть Г — случайная точка, равномерно распределенная в G, так что плотность вероятностей ее в G постоянна: р (Л) = MVq. Каждому критерию Фт (Л) поставим в соответствие случайную величину £v = Фу (Г), определенную в G.
Определение. Коэффициентом корреляции критериев Фц (Л) и Фу (Л) в области G назовем число
Гцу Г (£ц, ^у).
Если функции Фц (Л) и Фу (Л) кусочно непрерывны и отличны от постоянных, то все условия существования Гцу выполнены. А вышеприведенное свойство коэффициента корреляции г (ч, I) может быть сформулировано в виде теоремы.
Теорема. Условие | гцу | = 1 необходимо и достаточно для того, чтобы,- существовали такие постоянные соу= 0 и clt что во всех точках А, в которых Фц (Л) и Фу (Л) непрерывны, выполняется равенство
Фц (Л) = СдФу (Л) -J- cv (4)
Случай с0> 0 соответствует условию гцу = 1, а случай Со < 0 — условию Гцу = —1.
Доказательство. Если | rgv | = 1, то, переводя утверждение (3) с языка теории вероятностей на язык теории функций, можно сказать, что соотношение (4) имеет место почти всюду в G. Пусть Л' — точка непрерывности Фц (Л) и Фу (Л). В любой окрестности точки Л' найдутся точки Л, в которых справедливо (4). Выбрав последовательность таких точек, сходящуюся к Л', мы, нс-
Рис. 4.2. Тридцать две пробные" точки в плоскости критериев (Ф1, Фа), (Фц Ф«), (Фц Фи) и соответствующие значения коэффициентов корреляции критериев
пользуя определение непрерывности функций, получим, что (4) справедливо также в точке А*.
Легко видеть, что обратное утверждение не требует доказательства: если (4). имеет место во всех точках непрерывности Фц н ФУ1 то тем самым (4) имеет место почти всюду в G. Впрочем, равенство | гЦу | = 1 легко проверить непосредственно, исходя из (4): так как
МЕд == CgM^v Ч~ ^ъ ^^g^v ™* М^у — CqD^v, то из (2) сразу следует, что гцу = cj | се | и | гцу | = 1.
Итак, если Гду близко к 1, скажем, гИу ^ 0,9, то можно считать, что между функциями Фц (Л) и Фу (Л) в области G существует зависимость, близкая к линейной, и один из этих критериев можно из рассмотрения исключить.
Случай близости rgv к —1 практически не реален, так как это означало бы, что в числе критериев, которые желательно минимизировать, фигурирует и величина Фу, и величина — Фу, равносильная — |с0| Фу + cv
Другие значения ruv не позволяют делать столь решительных выводов о характере зависимости между критериями Фц и Фу.
На рис. 4.2 построены 32 пробные точки в плоскости критериев (Фц, Фу) при rgv равных соответственно 0,92, 0,51 и —0,10. Легко видеть, что в первом случае наилучшая точка для обоих критериев Ф, и Ф2 одна и та же, а во втором и третьем случаях имеются четыре приближенно
паретовские точки (рис. 4.2 соответствует примеру, рассмотренному в разделе 2.4).
Вычисление Гц у* Введём в рассмотрение интегралы вида
^ = J- Фр (Л) dA,Iw = -A- f Фр (Л) Фу (Л) dA.
G ЙG 5
Все величины, входящие в определение (2) коэффициента корреляции г (^ц, U, легко выражаются через такие интегралы:
М^ц = ^ Фр (Л) р (Л) dA = /ц,
M^v = ^ Фр (Л) Фу (Л) р (Л) dA = 1^,
М^ = ^Ф»(Л)р(Л)ДЛ = 1цц.
Используя эти выражения, можно записать новую формулу для rgv, в которую входят только интегралы по G (и никаких математических ожиданий):
^v ~ Vv• ■/г\
Гру—,.— ж
Далее, так как последовательность пробных точек At равномерно распределена в G (в смысле раздела 1.1), то из теоремы 8 Дополнения следует, что все такие интегралы являются пределами:
N
/ц=Иш А.уФц(Л,),
N—оо и
1=1N
/цу = Ива -^ У| Фц (Ла Фу (Л{).
001=1
Поэтому при достаточно больших N можно считать, что
NN
^ ~ 4 Е ф^ (лЛ’ ^ ~ 4- Е фц (Ла °v (Л,)- (6) i=li=l
Все величины, входящие в эти формулы, имеются в матрице в Фу (л а
Чтобы убедиться в том, что N достаточно велико, мож-
но сравнить приближенные значения г^, полученные при нескольких значениях N, например, при N = 64, 128, 256.
Выделение' лишних критериев. Процесс выделения лишних критериев может быть организован следующим образом. По формулам (6) и (5) вычисляем приближенную корреляционную матрицу | гМУ Ц« в которой 1 р, v<^ к. Если мы хотим сохранить критерий Фи, то просматриваем р-ю строку этой матрицы; обнаружив элемент rgv ^ 0,9, зачеркиваем столбец номер v и строку номер v; если в р-й строке есть несколько элементов, близких к 1, то повторяем эту процедуру несколько раз.
Затем повторяем то же самое с какой-нибудь другой из уцелевших строк, например, со строкой номер р', если мы хотим сохранить критерий Фц>.
После конечного числа шагов останется матрица, не содержащая элементов г^ ^ 0,9. Строки и столбцы, соответствующие лишним критериям, будут зачеркнуты.
Заметим, что симметрия матрицы || r^v | и равенство единице всех г№ = 1 позволяют ограничиться рассмотрением треугольной матрицы, в которой 1 ^ р < v ^ к.
Замечание. Точно так же можно оценить коэффициент корреляции критериев ,ФД (Л) и Фу (Л) в области D. Для этого следует в формулах (6) осреднять значения Фц (Лг) и Фц (Л{) Фу (Л,) не во всех точках Л{ G G, а лишь в тех q точках, которые попали в D, и использовать ту же формулу (5).
Пример. В задаче, рассмотренной в разделе 2.4, проектировщик сформулировал 14 критериев качества, которые принимались во внимание при выборе оптимального решения. Треугольные матрицы r^v, сосчитанные при N = = 256 и при N = 512, приведены в табл. 4.1 и 4.2. Очевидно, последние значения можно считать достаточно точными.
• В табл. 4.3 приведена матрица r^v после исключения зависимых критериев. В этой задаче оказалось всего шесть независимых критериев. В качестве таковых можно выбрать критерии Фп Ф3, Ф4, Фв, Ф13, Ф^ Необходимо пояснить, что такой результат связан отнюдь не с некомпетентностью проектировщика. Наоборот, он подтверждает характеристику критериев, данную проектировщиком (см. с. 31), ибо оставшиеся критерии Ф,, Ф3, Ф4, Ф, принадлежат как раз различным группам.
Из табл. 4.3 вытекает также, что если встанет вопрос
о»
1»
v-2
3
4
5
6
7
8
9
10
и
12
13
v —14
1
0,92
0,59
0,51
0,95
0,82
0,58
0,41
0,94
0,88
.0,58
0,49
—0,09
0,26
2
0'53
0,48
0,83
0,89
0,51
0,38
0,88
0,96
0,51
0,46
—0,07
0,29
з
0^83
0,65
0,49
0,95
0,73
0,56
0,50
0,95
0,77
—0,45
0,20
4
о;5з
0,45
0,67
0,91
0,48
0,45
0,86
0,98
-0,29
0,09
5
0,77
0,67
0,44
0,87
0,76
0,64
0,50
—0,08
0,19
6
0,48
0,39
0,77
0,85
0,48
0,43
—0,05
0,31
7
0,58
0,56
0,49
0,86
0,59
—0,44
0,19
8
0,39
0,35
0,78
0,90
-0,27
0,03
9
0,92
0,54
0,46
—0,09
0,19
10
11
11
13
0,48
0,43
—0,08
0,24
—
—
—
г—
—
—
—
—
—
—
0,86
-0,44
—0,28
0,15 0,05 0,02
Таблица 4.2.
Матрица гцу при ^ =
= 512
. 1»
v-2
3
4
5
6
7
8
9
10
и
12
13
v ш 14
0,92
0,60
0,51 х
0,95
0,82
0,58
0,41
0,94
0,87
0,60
0,49
—0,10
0,29
2
0^54
0^49
0,82
0,89
0,52
0,38
0,89
0,97
0,54
0,47
—0,08
0,31
0^84
0^65
0,51
0,95
0;73
0,58
0,52
0,95
0,77
—0,45
0,20
0^53
0j47
0,68
0,91
0,49
0,46
0,87
0,97
—0,30
0,11
0J8
0,67
0,45
0,87
0,75
0,65
0,51
—0,08
0,25
g
0,50
0,40
0,77
0,85
0,50
0,45
—0,05
0,33
7
0,59
0,57
0,50
0,87
0,60
—0,44
0,20
8
—
—
—
—
—
0,39
0,36 0,93
0,78 0,57
0,89 0,47
—0,27
—0,09
0,04 0,23
9
—*
0,52
0,45
-0,08
0,26
10
11
12
13
—
—
—
—
—
—
—
—
—
0,86
-0,44
—0,28
0,17 0,09
0,03
Таблица 4J. Матрица гцу при №ткяг
Таблица Н.З
Матрица гц> v для независимых критериев
Ц
v = 3
4
6
13
v = 14
1
0,60
0,51
0,82
—0,10
0,29
3
— •
0,84
0,51
-0,45
0,20
4
—-
i—
0,47
—0,30
0,11
6
—
—
-0,05
0,33
13
—
—
—
—
0,03
о дальнейшем сокращении числа критериев, то в первую очередь отказаться надо будет от критериев Ф4 и Фв и сохранить Фх, Ф3, Ф13, Ф14, ибо значения гХЛ и г3>4 весьма значительны.
4.3. О возможностях улучшения оптимального решения
Заглавие настоящего раздела звучит немного парадоксально: если решение оптимально, то, казалось бы, улучшить его нельзя... В действительности, однако, такие слова произносят довольно часто. В самом деле, предположим, что, решив задачу о наилучшем выборе параметров, кон- струйтор тем не менее не удовлетворен решением и хочет попытаться «улучшить» его за счет ослабления каких-то ограничений. Став на формальную точку зрения, следует сказать, что речь идет о новой задаче, так что ставить и решать ее нужно заново. Такой подход, конечно же, возможен, но часто связан с большими затратами времени.
Поэтому рассмотрим коротко, как можно использовать информацию, полученную в ходе расчета решенной задачи, для более рациональной формулировки и решения новой задачи. Конечно, речь идет о сравнительно небольших нарушениях ограничений, ибо в противном случае задачу необходимо решать заново.
Определение ресурсов точки (модели). Очевидно, улучшение оптимальной точки может быть достигнуто путем отказа от
1° параметрического ограничения a* ^aj или
«у ах ,
2° функционального ограничения с* ^ /, (Л) или fi (А) < сГ*
3° критериального ограничения ФУ(Л)^Ф**.
Условимся называть ресурсом точки At по ограничению Фу ^ Ф** разность Ф^* — Фу (Л^). Точно так же ресурсом точки А г = (afi n . . ., ai n) по ограничению a*^aj назовем разность afij — а*, а ресурсом точки Ai по ограничению/{(Л i) ^ с**—разность с**—fi(At) и т. д.
Для любой точки Лг из Dm легко определить ресурс по любому критериальному ограничению: для этого достаточно взглянуть на соответствующую таблицу испытаний, где имеется Фу (Лг) и выбранное значение Ф**. Не сложно вычислить также ресурс точки A t по любому параметрическому ограничению, ибо координаты точек At обычно сохраняются в памяти ЭВМ (а если даже не сохраняются, то расчет их заново затруднений не представляет). Хуже обстоит дело с оценкой ресурсов по функциональным ограничениям, так как значения /, (Л() часто не сохраняются и восстановление их требует повторного расчета проектируемой системы при А = At.
Это обстоятельство с новой стороны показывает важность рекомендации (см. раздел 2.3) о замене функциональных ограничений псевдокритериями: если соответствующее ограничение было заменено псевдокритерием, то ресурс по нему можно оценить при помощи соответствующей таблицы испытаний.
Оценка возможностей улучшения произвольной точки. Предположим, что ставится задача об улучшении значения Фц (Л), исходя из найденной точки Л = Л|. Мы не будем приводить здесь количественных значений, так как они вряд ли имеют практическое значение, и ограничимся качественными соображениями.
Мысленно представим себе, что точка Л в условиях решенной задачи движется в направлении улучшения значения Фц (Л). Движение это. чаще всего прекращается из-за того, что точка натыкается на какое-то ограничение. Ресурс остановившейся точки А = Лi по задержавшему ее ограничению равен нулю. Ясно, что дальнейшее улучшение Фц (Л f) возможно только при отказе от этого ограничения.
Если точка Л остановилась из-за достижения функцией Фц (Л) локального минимума А = Л,, то ресурсы At по всем ограничениям положительны. В этом случае отказ
от какого-либо ограничения не позволяет улучшить значение Фц (Л,) в окрестности точки Л£.
На основании этих рассуждений можно дать следующие рекомендации:
если точка Л£, в которой значение Фц (Л£) минимально, имеет большие ресурсы по всем ограничениям, то пытаться улучшить (уменьшить) это значение в окрестности точки Л{, путем ослабления некоторых ограничений, бесполезно;
если точка Л£ имеет малые ресурсы по каким-нибудь ограничениям, то поиск в окрестности Л £ перспективен только при ослаблении этих ограничений;
среди нескольких точек Л£ из D, удовлетворяющих условиям (б), лучшим кандидатом на улучшение следует считать ту из них, у которой ресурсы по ненарушаемым ограничениям больше (независимо от того, принадлежит ли эта точка Ем или нет).
Для разъяснения последней рекомендации заметим, что если ресурс точки Л по какому-нибудь ограничению мал, то есть основания опасаться, что ее движение (в направлении улучшения Фц (Л)) будет остановлено этим ограничением.
Улучшение оптимальной точки без нарушения параметрических ограничений. Если ставится задача об улучшении найденного значения Фц (Л) путем ослабления некоторых критериальных ограничений (3°), то можно, не рассуждая о ресурсах Л, воспользоваться уже имеющимися таблицами испытаний. Достаточно заново повторить второй и третий этапы диалогового алгоритма; повторять первый этап и вычислять новые таблицы испытаний не надо.
Улучшение оптимальной точки за счет нарушения параметрических ограничений. Если ставится задача об улучшении найденного значения Фц (Л) путем отказа от некоторых параметрических ограничений (1°), то, вместо того чтобы полностью решать новую задачу (как об этом говорилось в начале параграфа), можно поступить так: выбрать несколько «лучших» точек из Dm, и в окрестности каждой из них организовать ЛП-поиск. Слово «лучших» означает не просто лучших в смысле значений Фц, но еще с учетом рекомендаций, высказанных выше.
Пример. На рис. 4.3 построено множество эффективных точек А А' в пространстве параметров и соответствующая ему паретовская кривая ВВ* в пространстве критериев.
Рис. 4.3. Оптимальная точка Л может быть улучшена путем ослабления параметрического ограничения а, ^а2, так как при замене а, иа «2 — 6 паретовская кривая В В' превращается в В В"Рис. 4.3. Оптимальная точка Л может быть улучшена путем ослабления параметрического ограничения а, ^а2, так как при замене а, иа «2 — 6 паретовская кривая В В' превращается в В В"
Рис. 4.3. Оптимальная точка Л может быть улучшена путем ослабления параметрического ограничения а, ^а2, так как при замене а, иа «2 — 6 паретовская кривая В В' превращается в В В"
Рис. 4.3. Оптимальная точка Л может быть улучшена путем ослабления параметрического ограничения а, ^а2, так как при замене а, иа «2 — 6 паретовская кривая В В' превращается в В В"
В качестве оптимальной была выбрана точка В, прообраз которой обозначен А.
Ставится вопрос: нельзя ли путем нарушения параметрических ограничений- уменьшить Фх (Л), не увеличив при этом Ф2 (Л)? Так как точка Л расположена на границе аг = а*, то попытку улучшения можно предпринять, отказавшись от ограничения а2 > а*.
Выбрав новое ограничение at> а* — 5, мы получим частично новую паретовскую кривую ВВ”, на которой действительно можно выбрать «улучшенную» точку. Из рис. 4.3 видно, что улучшение возможно даже по обоим критериям.
О количественно? оценке ресурсов. Приведенное выше определение ресурсов точки Лг, как например, Ф$* — —Фу (Лг) или а1%1 — а*, очень удобно для проектировщика, так как выражается в естественных (физических) единицах. Однако если возникнет вопрос об автоматизации попыток улучшения точки Лг, то потребуются другие характеристики ресурсов, которые позволили бы сравнивать ресурсы по различным ограничениям и (на основе заранее заданных допусков) судить о том, какой ресурс мал, какой велик.
В качестве такой характеристики можно предложить относительный ресурс (в процентах по. отношению к величине ограничения). Например, вместо разности ax,j — af
65653 Заказ М 546
65
65
рассматривать величину 100 (аг ; — af)/af, если только а*>0.
Другой возможный подход к определению относительных ресурсов состоит в следующем. Пусть среди всех g пробных точек, попавших в D, оказалось д+ точек, худших, чем Ах, в смысле рассматриваемого ограничения. Обиемиым ресурсом точки А^ по этому ограничению назовем отношение qjq.
В вышеприведенном примере, где рассматривается ограничение aj^a*, число д+— это количество пробных точек А„ попавших в D, у которых /-я координата as, ■ ближе к границе а^, чем а^ ^.
Легко видеть, что
lim (д+^ = V+(V D,
N—oo
где VD — объем множества допустимых точек D, а Г+ — объем части D, состоящей из таких точек А = (а„ . . ., ап), у которых /-я координата удовлетворяет неравенствам aj ^ ^ а^. Очевидно также, что всегда 0 ^ g+/g •< 1.
Замечание. Если для улучшения оптимального решения предпринимается новый расчет в параллелепипеде ГТ ~i П, то следует различать два случая. Во-первых, случай, когда Гц- ^> Рп- Тогда естественно выбирать новые пробные точки в П', не обращая внимания на то, принадлежат ли они П, или нет. Во-вторых, случай, когда объем Ун- не на много превосходит объем Рп. Тогда можно сократить время расчета путем исключения пробных точек, попавших в П, и использовать только те пробные точки, которые принадлежат ГР — П.
Глава 5
ПРИМЕР: ОПТИМАЛЬНОЕ ПРОЕКТИРОВАНИЕ РЕЗОНАНСНОЙ ВИБРОПЛОЩАДКИ
В последние годы в различных отраслях промышленности применяются резонансные вибромашины технологического назначения. Современные машины такого типа создаются на базе нелинейных упругих систем, позволяющих обеспечить технологическую стабильность и регулировать законы колебаний рабочих органов с целью их оптимизации. Синтез резонансных вибромашин представляет дос-
таточно сложную проблему и в общем случае сводится к определению наиболее рациональной динамической структуры и выбору параметров нелинейной системы и привода, при которых периодические движения рабочего органа наилучшим образом удовлетворяют технологическим требованиям и целому ряду конструктивных ограничений. Эти задачи всегда многокритериальны. И во многих практически важных случаях конструктор именно на основании анализа таблиц испытаний выбирает наиболее предпочтительную («оптимальную») модель.
В настоящей главе описано решение двух задач такого типа, выполненное при нашем участии. Обе задачи связаны с проблемами синтеза резонансных асимметричных виброплощадок для формования железобетонных изделий [9]. В диалоге с ЭВМ участвовал главный конструктор виброплощадки ВРА-8 Л. М. Литвин.
Исходные данные
В качестве исходной модели была взята существующая виброплощадка ВРА-8 грузоподъемностью 8 т. Расчетная схема такой виброплощадки изображена на рис. 5.1. Ее колебания описываются системой нелинейных дифференциальных уравнений
тгхг 4- / (х)£ + рА^ 4 Р (i) + к^ = йдр (sin vt 4- 4* pv cos vt),
mafa — / (я) £ + рЛа£а — P (z) 4* kaxa = —tgp (sin vi 4*
4- pv cos vt),(1)
где zx и za — смещения масс m0 и m2; i = z, — x^
P (z) = (^ 4- k^x 4- о (x)kB (z 4- e);
/ (z) = pi [^ 4- k6 4- о (х^квА;
о (z) = О при x > e, a (z) = 1 при x •< e. Смысл величин, входящих в уравнения (1), разъясняется ниже.
Варьируемые параметры. Их всего десять:
ai =— жесткость приводных упругих связей
(кН/см);
аа = &а — жесткость линейных основных упругих связей (кН/см);
а3 = кв — жесткость буферов (кН/см);
а« = &, — жесткость опорных амортизаторов под рамой (кН/см);
Рис. 5.1. Расчетная схема асимметричной реаоиаисиой виброплощадки
а 5 = &з — жесткость опорных амортизаторов под рабочим органом (кН/см);■
ав = р — эксцентриситет привода (см);
а7 = тп0 — масса рабочего органа (т);
ae = т2 — масса уравновешивающей рамы (т);
а9 = ^нач — зазор в буферах без технологической нагрузки (см);'
а10 = v — рабочая частота (с-1).
Остальные величины.
тц — масса полезной нагрузки;
кт — коэффициент присоединения массы полезной нагрузки;
тщ = т0 + кттК — приведенная масса рабочего органа;
р. — коэффициент внутренних сопротивлений ■ в резиновых упругих связях; .
kw — коэффициент приведения сопротивления;
Pi = И + ^цтп — приведенный коэффициент внутренних сопротивлений;
е — зазор в буферах.
Техническое задание на проектирование включает данные о диапазоне изменения полезной нагрузки (в нашем случае—^т<^тп^8т), о диапазоне рабочих частот (в нашем случае — 50 с-1 ^ v ^ 100 с-1), о пределах изменения ускорений рабочего органа при движении вверх и вниз— wx» и и>1н. Рабочие режимы необходимо реализовать на восходящей ветви частотной характеристики (в дорезонансной области).
Динамика и методы расчета (1) рассмотрены в [9], где для построения приближенных периодических решений используется метод Крылова—Боголюбова.
Функциональные ограничения. Для формулировки функциональных ограничений вводятся следующие функции:
/1 М) ~ ^IBi /2 М) = ^IH, /3 М) = Адр,
h W = m,-VM- (kt + ад (gk'V,
h (A) = m0 + m2 + M - (k4 + ад (gk’)'1,
7б И) — к1кг + к^з + ^ евач,
/7 (Л) = v — ю (Л),
где М — максимальная величина полезной нагрузки (в нашем случае — 8 т), к* — жесткость одного резинового амортизатора (кН/см), Q — предельная нагрузка на один амортизатор (кН), и (Л) — собственная частота линеаризованной системы (с-1).
Функции /1 (Л) и /2 (Л) зависят от решения системы (1), а /3 (Л) — /, (Л) выражаются непосредственно через параметры а$, . . ., а10.
Функциональные ограничения задаются неравенствами
9 < А (Л) < 22; 40 < /а (Л) < 100; /3 (Л) < 120 (2) и
А (Л) < 0; /6 (Л) < 0; /, (Л) < 0; /7 (Л) < 0.(3)
Первые два ограничения обеспечивают соответствие закона колебаний рабочего органа требованиям технического задания, третье — ограничивает величину возму- . щающей силы, четвертое и пятое — ограничивают нагрузки на резиновые амортизаторы, шестое — связано с нагрузкой на упругую подвеску, а седьмое — обеспечивает реализацию рабочих режимов в дорезонансной области.
Ограничения /х — /3 не являются «жесткими»: в зависимости от конкретных условий производства и требований, предъявляемых к железобетонным изделиям, их можно в некоторой степени варьировать. Ограничения /4 — /7 нарушать нельзя.
Критерии качества. Качество проектируемой виброплощадки предлагается оценивать по шести критериям, которые желательно уменьшить. Первый критерий — масса машины — вычисляется непосредственно по параметрам: Фх = а7 + а8. Остальные пять критериев выражаются через решение системы (1), которое зависи-
от массы полезной нагрузки тпп. В соответствии с принятой методикой [91, система (1) решалась четырежды: при тп = 2, 4, 6, 8 т. Символы max и min в следующих формулах означают, что выбираются соответственно наибольшие или наименьшие значения величин, полученные при таких четырех расчетах. Итак, критерии качества:
Масса машины Ф, (Л) = m0 -f- m2.
Асимметрия закона колебаний рабочего органа Ф2 (Л) = max (ш1в1ш1и\
Динамическое усилие в приводе Ф3 (Л) = max к(<а0, где а0 — деформация приводных упругих связей.
Динамическая нагрузка на фундамент Ф4 (Л) = = max | | &2д21 — | к1а1 11, где а, и д2 — амплитуды колебаний рабочего органа и уравновешивающей рамы.
Характеристики стабильности «верхнего» и «нижнего» ускорения
шахш,.,max ш
ф5(Л)= ——^1—1/J Ф6(Л) = -гi2- — 1.
Проектировщик предложил считать наиболее важным критерий Фп затем идут критерии Ф3 и Ф4, за ними критерий Ф2 и, наконец, наименее важные критерии Ф5 и Ф,. Однако при этом было оговорено, что в зависимости от конкретных результатов ранжирование критериев может измениться.
Первая задача: исследование возможностей модернизации исходной модели
Ставится вопрос: возможно ли за счет сравнительно небольших отклонений от параметров действующей модели найти лучшую модель (которую можно было бы реализовать без принципиальных конструктивных изменений)?
Для решения этого вопроса конструктор указал небольшие пределы вариации параметров, приведенные в табл. 5.1. Они определяют девятимерный параллелепипед П, в центре которого расположена точка Аг с параметрами действующей модели ВРА-8. В качестве критериальных ограничений были назначены значения критериев в точке Ад, то есть Ф** = Фу (Ai) при всех l^v^6.
Пробный расчет и изменение постановки задачи. В параллелепипеде П при функциональных ограничениях (2) и (3) было проведено N' = 256 испытаний. Количество
точек, удовлетворяющих функциональным ограничениям, оказалось равным N = 24, так что у я; 0,093. Время расчета одного испытания т я; 10 сек на ЭВМ «Минск-32».
Чтобы увеличить количество анализируемых вариан- ’тов (иными словами, чтобы увеличить у), было решено заменить первые три нежестких ограничения псевдокритериями. Сделано это было следующим нестандартным образом. Во-первых, эти ограничения были ослаблены
8,5 < к (Л) < 22,5,37 < /2 (Л) < 103, /э (Л) <
<123.(4)
Во-вторых, были введены псевдокритерии
Ф7 = max /з (Л),
Ф»п = min /х (Л),Ф,г> = max ft (Л),
Фд11 = min /4 (Л),Ф,а) = max /2 (Л);
Таблица 5.1 Значения параметров
Первая задача
Вторая задача
%*
“1./
“248,/
®475, /
“/
<
“ив, 5
“12./
1
44
48
52
44,96
50,85
20
100 .
31,79
48,87
2
92
96
100
99,03
99,42
30
150
59,04
83,12
3
1400
1600
1800
1758
1490
400 .
3000
1449
2396
4
20
25
30
22,07
20,09
20
60
20,42
20,00
5
20
25
30
29,49
26,54
20
60
48,64
46,87
6
0,5
0.7
0,9
0,848
0,830
0.5
2,0
0,971
1,065
.7
3
3
3
3
3
3
7
3
3
8
3
5
7
4,02
5,34
3
7
3
3
9
0.0
0,2
0,4
0,398
0,110
-0,3
1,5
0,438
0,637
10
94
97
100
95,10
94,20
50
100
91,48
90,63
смысл символов max и min тот же, что в п. «Критерии качества». Правило использования этих псевдокритериев: если точка Лг удовлетворяет ослабленным ограничениям (4), но не удовлетворяет ограничениям (2), то конструктор сам решает, включить ли точку Лi в число допустимых точек. Ясно, что такое решение будет приниматься в тех случаях, когда нарушение ограничений (2) компенсируется достаточно большим выигрышем в других критериях. Таким образом, случай, когда (4) выполнены, а (2) нет, оказывается как бы «зоной размышления» для конструктора.
Таблица 5.2
Значения критериев
Первая задача
Вторая задача
5*
е
е
■ч
е
■ч
■ч
С
X
>
й
Ё
е
S **
е
е
а"
е
е
7,02
8,00
9,04
7,02
8,34
6,95
6,00
6,00
1
0,233
0,256
0,313
0,283
0,241
0,147
0,234
0,240
2
28,25
31,72
70,62
28,34
30,94
19,54
26,44
28,21
3
3,70
6,70
12,51
6,36
3,70
4,63
5,68
5,40
4
0,047
0,421
1,143
0,768
0,357
0,050
0,895
0,674
5
6
0,051
0,359
1,222
0,871
0,227
0,054
0,953
0,749
Решено было также вычислять ресурсы Ду точек Л, по введенным псевдокритериям Фу относительно ограничений (2) (см. раздел 4.3). Если точка At не удовлетворяет какому-то из ограничений (2), но удовлетворяет ослабленному ограничению (4), то соответствующий ресурс полагался равным нулю; Av = 0.
Второй пробный расчет. Вновь было проведено N' = = 256 испытаний, причем в таблицы испытаний попало N = 33 точки. При этом были обнаружены интересные точки Л40 и Лыа- Они по ряду важных критериев лучше, чем Лп и это компенсирует некоторое ухудшение величины других критериев. Обе эти точки попали в таблицы испытаний только благодаря ослаблению функциональных ограничений (2). Наиболее интересной конструктор счел точку Л24в (см. табл. 5.1 и 5.2). Он обратил также внимание на то, что ресурсы этих точек по Ф8 (для Л40) и по Ф9 (для Л24д) исчерпаны, а некоторые координаты этих точек близки к границам П. Попытки улучшить эти точки не предпринимались.
Диапазон изменения Ф, оказался 7,02 ^ Ф, ^ 8,89, хотя из исходных ограничений следует, что <&j может меняться от 6 до 10. Конструктор решил, что нужно проанализировать причину такого ограниченного изменения Фп чтобы выяснить возможности дальнейшего уменьшения Фи
Продолжение расчета первой задачи. В том же параллелепипеде П при ограничениях (3) и (4) испытания были продолжены до N' = 1024. В область G попало N = 108 точек, так что в конечном счете у ~ 0,105 — увеличение
незначительное. Таблицы испытаний приведены в табл. 5.3. Нарисованные в таблице критериальные ограничения определяют допустимое множество D, содержащее одну единственную точку — Av
При решении аналогичных задач у проектировщиков нередко появляется желание «поиграть» критериальными ограничениями: попытаться понять, что дают те или иные уступки, во что обходится ужесточение тех или иных ограничений. В настоящем эксперименте конструктор рассмотрел семь наборов критериальных ограничений. Мы опишем три из них.
Первый диалог конструктора с ЭВМ. Среди всех 108 точек, попавших в таблицы испытаний, конструктор попросил выделить эффективные \ С учетом всех шести критериев, оказалось 59 эффективных точек и среди них точка Av Следовательно, модель А у не представляется возможным улучшить по всем шести критериям. В определенном смысле данный вывод следует считать естественным, так как исследуется весьма хорошая конструкция машины.
Второй диалог конструктора с ЭВМ. Конструктор решил сделать уступки по наименее существенным критериям Ф5 и Фв: были выбраны ограничения Ф** = 1, Ф?* = 1. А по первым четырем критериям, по-прежнему, Ф** = Фv (AJ, 1 ^ v ^ 4.
В этом случае в допустимое множество D попали три точки: Ап А794 и Ат, из которых две последние — эффективные. Обе эти точки конструктор счел примерно эквивалентными: лучшее значение Фт (Ат) уравновешивается лучшими значениями Фэ (А784) и Ф4 (А7в4). Любопытно, что точку Aj оказалось возможным улучшить по всем четырем важнейшим критериям.
Третий диалог конструктора с ЭВМ. Конструктор решил поискать точки, которые по одному из первых четырех критериев несколько хуже, чем Ап зато по всем другим критериям — заметно лучше. С этой целью по таблицам испытаний были выбраны ограничения
Ф,** = Ф, (Aw) =- 8,34, . ФГ = Ф2 (Л8И) = 0,291, Ф3** = Ф3 (А445) = 33,62, ФГ = Ф4 (А847) = 7,61.
По-прежнему, Ф** •= 1, Ф** = 1.
Для краткости в этой главе приближенно эффективные точки будем называть эффективными.
^ Таблица 5.3
** Таблицы испытаний
i
Ф1 (Ар
1
Ф. (Ар
i
Ф» (Ар
i
Ф« (Ар
i
Ф. (Ар
г
Ф« (Ар
248 '
7,02
445
0,233
319
28,25
475
3,70
588
0,047
214
0,051
353
7,04
475
0,241
248
28,34
1022
3,74
418
0,106
295
0,120
132
7,17
141
0,241
794
28,46
957
4,10
910
0,133
853
0,120
673
7,30
40
0,241
47
28,94
593
4,15
863
0,144
910
0,122
47
7,31
78
0,242
935
29,38
253
4,37
214
0,155
231
0,130
528
7,32
831
0,242
176
29,52
768
4,52
134
0,170
807
0,163
905
7,37
183
0,243
498
29,59
143
4,55
853
0,176
819
0,177
733
7,39
667
0,243
13
30,15
643
4,62
295
0,180
445
0,183
379 .
7,41
925
0,243
40
30,34
116
4,60
637
0,197
40
0,186
836
7,42
433
0,243
528
30,62
204
4,77
947
0,214
116
0,188
141
7,42
655
0,244
922
30,82
588
4,91
347
0,233
637
0,214
690
7,43
396
0,245
475
30,94
552
4,93
396
0,236
588
0,217
620
7,47
7,49
319
0,246
905
31,62
176
5,10
203
0,243
406
0,221
421
913
0,246
682
31,08
733
5,20
231
0,256
475
0,227
922
7,50
819
0,248
141
31,69
. 607
5,27
925
0,256
790
0,243
498
7,52
682
0,248
819
31,70
661
5,42
406
0,256
655
0,245
787
7,57
794
0,248
1
31,72
379
5,43
116
0,271'
362
0,260
218
7,58
498
0,249
1022
31,83
224
5,54
819
0,281
203
0,266
78
7,59
176
0,250
831
32,00
368
5,63
019
0,283
36
0,260
181
7,01
935
0,250
433
32,41
619
5,68
153
0,294
619
0,274 .
552
7,63
619
0,250
421
32,54
406
5,69
913
0,298
78
0,279
990
7,05
134
0,252
379
32,80
433
5,70
648
0,298
224
0,281
319
7,70
922
0,252
445
33,62
794
5,77
807
0,303
149
0,282
768
7,70
015
0,252
181
33,95
682
5,78
5,81
224
0,303
667
0,285
330
7,73
879
0,252
368
34,77
533
40
0,305
48
0,286
879
7,73
. 115
0,255
353
34,79
13
5,81
445
0,305
628
0,286
13
7,75
1
0,256
218
35,01
408
5,87
628
0,310
925
0,287
831
7,76
243
0,256
787
35,06
874
5,89
183
0,316
418
0,294
605 ■
7,79
600
0,258
874
35,18
498
5,92
520
0,322
706
0,304
153
7,80
990
0,260
643
35,34
859
5,96
996
0,335
615
0,306
40
7,81
143
0,261
768
35,64
637
5,96
362
0,336
847
0,313
293
7,82
103
0,261
688
35,70
913
5,97
78
0,342
1022
0,313
794
7,82
643
0,262
836
35,75
922
6,03
115
0,343
347
0,315
643
7,86
368
0,262
341
36,43
293
6,13
48
0,346
513
0,324
433
7,87
874
0,262
847
36,43
' 787
6,18
1022
0,352
336
0,332
910
7,87
13
0,-262
253
36,62
879
6,25
667
0,354
880
0,339
952
7,93
163
0,263
132
36,67
248
6,36
475
0,357
1
0,359
192
7,95
661
0,203
879
36,69
935
6,37
36
0,366
115
0,360
767
7,96
990
0,203
224
37,06
615
6,58
790
0,374
408
0,380
619
7,97
421
0,233
192
37,18
295
6,62
149
0,375
688
0,383
418
7,99
853
0,264
103
38,11
243
6,67
513
0,385
668
0,390
925
8,00
347
0,264
655
38,20
1
6,70
615
0,386
35
0,393
1
8,00
293
0,265
143
38,44
690
6,82
706
0,380
600
0,402
819
8,01
204
0,265
78
38,85
319
6,82
655
0,395
957
0,431
593
8,04
48
0,265
243
39,08
905
0,90
336
0,399
103
0,432
149
8,05
224
0,266
185
39,15
78
7,01
847
0,400
368
■ 0,451
682
8,05
149
0,266
733
39,27
218
7,03
600
0,417
293
0,463
408
8,05
203
0,266
406
39,57
47
7,08
35
0,420
948
0,474
935
8,06
787
0,267
990
39,63
790
7,16
1
0,421
183
0,481
36
8,06
520
0,267
513
■39,82
853
■ 7,17
668
0,439
863
0,485
790
8,07
253
0,268
593
40,05
48
7,17
880
0,441
253
0,486
■
•
• *
•
•
•
•
•
-
•
•
•
•
♦
*
•
•
•
•
•
Таблица 5.3 (окончание)
i
Ф»(Ар
i
Ф. (Ар
г
Ф. (Ар
i
Ф. (Ар
i
Ф. (Ар
i
Ф. (Ар
214
8,33
673
0,276
605
45,84
421
8,51
831
0,649
243
0,626
475
8,34
231
0,276
948
45,91
353
8,55
767
0,687
947
0,660
996
8,34
690
0,276
790
46,01
528
8,63
859
0,687
176
0,665
637
8,35
768
0,277
35
46,30
990
8,71
421
0,696
682
0,719
•
•
•
•
•
•
•
•
•
•
35
8,56
767
0,282
153
50^85
"362
9,44
353
0,844
528
0,891
183
8,61
248
0,283
859
52,01
153
9,59
218
0,849
768
0,894
• 648
8,61
593
0,283
418
54,35
170
9,59
733
0,881
733
0,897
807
8,64
952
0,284
957
54,73
880
9,64
787
0,886
913
0,903
347
8,98
605
0,305
231
64,18
35
11,82
13
1,118
498
1,164
863
9,04
620
0,313
947
70,62
600
12,51
498
1,143
13
1,222
В допустимое множество попало всего 15 точек, из них 12 эффективных (если считать решающими только 4 первых критерия). Среди них конструктор отдал предпочтение эффективным точкам Д248, Аиь и Авм (см. табл. 5.1 и 5.2).
Наиболее интересным и даже неожиданным результатом оказалась точка Д476, которая несколько хуже точки At по критерию Фп но зато лучше ее по всем критериям ф2 — Фв; значение Ф< (Д475) минимально и значительно лучше, чем значение Ф4 (Дх). Об интересных соображениях конструктора, связанных с этой точкой, сказано ниже в выводах.
Последующие диалоги конструктора с Э В М существенно новых результатов не дали. Нетрудно заметить, что именно третий диалог более всего соответствует методике, изложенной в разделе 2.2.
Попытки улучшить точку Д475. Координаты a47S-4 = = 20,09 и «47 5.10 = 94,20 близки к границам параллелепипеда «* = 20 и «?о = 94. Поэтому, в соответствии с рекомендацией, приведенной на с. 38, был проведен расчет точки А', отличающейся от Л476, этими двумя координатами: aj = a47S, ,• при / 5^ 4, j Ф 10; а4 = 20, ajo = 94. Значения всех критериев остались практически теми же и только Ф4 (Д') = 3,65 несколько лучше, чем Ф4 (Д475) = = 3,70.
Был проведен ЛП-поиск в небольшом параллелепипеде, границы которого отличаются от координат Д475 не более, чем на ±5%. После 32 испытаний точку Д475 практически улучшить не удалось.
Руководствуясь динамическими соображениями, конструктор предложил провести ЛП-поиск в плоскости параметров «8 и «10 (при .3,00 ^ «8 ^ 5,33, 94 ^ а10 100), фиксировав остальные координаты точки Д475. При 128 испытаниях был получен ряд интересных, по мнению конструктора, точек, но ни одной из них отдать предпочтение перед точкой Д475 он не решился.
Анализ зависимости критериев. Методом, изложенным в 4.2, были сосчитаны коэффициенты корреляции критериев в области G, содержащей 108 пробных точек. Результаты, приведенные в табл. 5.4, показывают, что среди всех Фу при 1 ^ v ^ 6 только Ф5 и Фв сильно зависимы: г6,в = 0,89. Внимательный анализ таблиц испытаний подтвердил этот вывод: группы лучших (и худших) точек по отношению к обоим критериям состоят, в основном, из тех же точек, хотя и расположенных в другом порядке.
Таблица 5.4
Коэффициенты корреляции критериев r|lv
в
v= 2
3
4
5
v = 6
1
—0,14
0,60
0,00
—0,63
—0,56
2
—
0,24
0,05
0,17
0,14
3
—
. 0,32
—0,64
—0,47
4
—
—
—0,32
—0,24
5
—
—
—
—
0,89
Некоторые выводы.
Действующая модель ВРА-8, которой соответствует точка Аи по всем шести критериям неулучшаема. Однако существуют модели, соответствующие Aw и Аям, которые несколько превосходят исходную по четырем важнейшим критериям Фх — Ф4.
Найдена интересная модель, соответствующая точке А248, оптимальной по критерию Ф,. Ее масса примерно на 1 тонну меньше, чем масса исходной модели, а значения остальных критериев, по мнению конструктора, приемлемы.
Обнаружена точка А475, оптимальная по критерию Ф4. Модель, соответствующая этой точке, по массе на 0,34 т тяжелее, чем исходная модель, но по остальным пяти критериям превосходит ее. Динамическая нагрузка на фундамент (критерий Ф4) у найденной модели почти вдвое меньше, чем у исходной! Для вновь проектируемых заводов и особенно заводов будущего предполагается строить многоэтажные здания, в которых виброплощадки можно устанавливать не только на первом, но и на более высоких этажах. Тогда уменьшение нагрузки на перекрытия приобретет первостепенное значение, и критерий Ф4 станет главным критерием.
Как уже указывалось, из N' = 1024 пробных точек в П, всего N = 108 точек попали в G. Анализ ресурсов позволил выяснить, что среди точек, не удовлетворяющих функциональным ограничениям, 72% точек не удовлетворяют ограничениям, связанным с ft (А), 7% — с /, (А), 3% - с /в (А) и 18% - с /7 (А).
В постановке задачи предусматривалось, что а8 (масса уравновешивающей рамы) заключена в пределах 3 ^ а8 ^ 7. В действительности из-за функциональных
ограничений пределы оказались более узкими: ■ 4,02 ^ ^ а8 ^ 6,04. Этим вызвано фактическое ограничение изменения массы Фп обнаруженное при втором пробной расчете.
В целом, возможности улучшения существующей модели ВРА-8 за счет сравнительно небольших изменений параметров весьма ограничены.
5.3. Вторая задача: эскизное проектирование машины с минимальной массой
Ставится задача: существенно улучшить значение критерия Oj (масса машины) и, если зто возможно, улучшить также значения других критериев. Так как предыдущее исследование показало, что в параллелепипеде П такая задача неразрешима, то было решено резко увеличить область поиска."
Глобальное исследование. Конструктор определил новый параллелепипед IT при помощи параметрических ограничений а* и а^*, приведенных в той же табл. 5.1. Здесь пределы изменения а, и а, определены из условий динамической прочности. Нетрудно проверить, что при фиксированном а, отношение девятимерных объемов Уп- к Уп превосходит 10е.
При тех же функциональных ограничениях (3) и (4) в П' было выбрано N' = 4096 пробных точек, из которых в таблицы испытаний попало только N = 100 точек. Значит, у ^ NIN' = 0,025; такое уменьшение у (по сравнению с у ~ 0,1 в первой задаче) вполне естественно, так Как там поиск велся в окрестности точки Av которая всем ограничениям удовлетворяет.
Вопреки ожиданиям, минимальные значения некоторых критериев в этом опыте оказались больше, чем минимальные значения в П (табл. 5.2). Это указывает на недостаточно подробный просмотр большого. параллелепипеда П'. Стоит, впрочем, отметить, что коэффициенты корреляции критериев, сосчитанные по этим 100 точкам, близки к полученным в разделе 5.2.
Конструктор перепробовал шесть вариантов критериальных ограничений; при этом количество точек, попавших в допустимое множество, колебалось от 0 до 20. После анализа всех 100 точек] было принято решение продолжить исследование по локальному пути. "
Локальное исследование. Были отобраны семь лучших
точек. Забегая вперед, отметим, что наилучшие результаты были получены в ходе поиска вблизи каждой из четырех точек, у которых ресурсы по Ф8 и по Ф9 оказались большими. Именно такое предсказание было сделано конструктором на основе вывода 4 в разделе 5.2. Наоборот, поиск вблизи каждой из трех точек, у которых ресурсы Д9 = 0, существенно новых результатов не дал, хотя зти три точки и были аффективными.
С некоторым опозданием мы решили перенести локальный поиск на границу П', а именно фиксировать минимальные возможные значения а7 = 3 и а8 = 3. Дело в том, что при таких предположениях Ф, = а7 + а3 будет минимальным: Ф7 = 6 т.
Вот как, например, был организован поиск вблизи точки Л1452 = (36,8; 61,5; 1430, 22,2; 46,4; 0,954; 4,52; 5,12; 0,425; 80,6): рассматривался восьмимерный параллелепипед, определенный условиями
0,9 < а, < 1,0, а7 = 3,0, а8 = 3,0, 0,40 < а» < 0,45, 90 < а10 < 100;0,9 < а, < 1,0, а7 = 3,0, а8 = 3,0, 0,40 < а» < 0,45, 90 < а10 < 100;30 < а, < 40,
0,9 < а, < 1,0, а7 = 3,0, а8 = 3,0, 0,40 < а» < 0,45, 90 < а10 < 100;
0,9 < а, < 1,0, а7 = 3,0, а8 = 3,0, 0,40 < а» < 0,45, 90 < а10 < 100;
56 <С «2 -С 66, 1400 < а3 < 1450,
20 < а4 < 25,
44 ^ а5 ^ 49,
в этом параллелепипеде было проведено N' = 128 испытаний, из которых N = 71 удовлетворили функциональным ограничениям; наилучшие точки определялись на основе изучения таблиц испытаний.
После этих экспериментов конструктор отобрал две наилучшие, по его мнению, точки Аив и Л12, которые были найдены вблизи точки 4ий и, соответственно, вблизи точки А2406- Параметры наилучших точек приведены в табл. 5.1, а значения критериев — в табл. 5.2.
Некоторые выводы.
Найдены две модели, соответствующие точкам А И8 и Л12, достаточно хорошие по всем критериям и абсолютно минимальные по массе (по сравнению с точкой Л248, найденной в разделе 5.2, массу удалось уменьшить еще на 1 т).
Низкое значение у указывает на сложность поставленной вадачи.
Возможно, решение задачи упростилось бы, если бы значения О; = 3, а8 = 3 были фиксированы перед глобальным исследованием.
Заключение. Значение критериев для всех наиболее интересных моделей, найденных в разделах 5.2 и 5.3, а также для исходной модели (точка Л]) имеются в табл. 5.2.
Результаты проведенных расчетов расцениваются специалистами как очень интересные. Во-первых, доказано, что металлоемкость машины можно уменьшить на 2 т,. и при этом снизить усилия в приводе и динамические нагрузки на основание на 10—20% (точки Л1М и Ли). Во- вторых, доказана возможность значительного снижения динамической нагрузки на фундамент с одновременным улучшением всех других критериев за счет увеличения массы машины менее, чем на 5% (точка Л«5).
Полученные результаты стимулируют дальнейшее совершенствование конструкций резонансных виброплощадок для формования железобетонных изделий,
Дополнение
НЕКОТОРЫЕ СВОЙСТВА
ЛП^ПОСЛЕДОВАТЕЛЬНОСТЕЙ
У читателей, которые впервые узнайт про ЛП^последо- вательности, часто возникают вопросы: что означает сайо название, в каком смысле говорят о равномерном расположении точек, сложно ли вычислять такие последовательности и др. Дополнение ставит своей целью по возможности коротко ответить на некоторые из этих вопросов. Лица, заинтересованные только в формулах расчета ЛПх-последовательностей, могут обратиться прямо к Д.7.
Первые публикации об ЛПт-последовательностях относятся к 1966 году [24, 25[. Более подробно теория ЛП^ . последовательностей изложена в статье [261 и в монографии [271. Ниже все результаты, содержащиеся в этой монографии, приводятся без ссылок, а все более поздние результаты — с ссылками. В этой связи можно также указать на обзорную статью [231.
Д.1. Геометрическое определение
Этот параграф содержит вполне строгое геометрическое определение Л Непоследовательностей.
Двоичные параллелепипеды. Назовем, двоичными отрезками все отрезки, которые могут бить получены рри
* Заказ N 546Щ
делении отрезка 0 ^ z <; 1 на 2т равных частей; т = = 0, 1, 2, . . . Для определенности все двоичные отрезки считаем замкнутыми слева и открытыми справа, если только правый конец отрезка отличен от 1; если правый конец равен 1, то отрезок замкнут также и справа. При таком определении сумма всех двоичных отрезков длины 2-т составляет отрезок [0, 1].
Например, двоичными отрезками являются отрезки [О, 1], [О, V2), Vh, И, №. ‘А), РА, г1* I1/,, ’/4), . . . Отрезки [V4, 3/4) или Р/8, ’/8) двоичными не считаются..
Перенумеруем все двоичные отрезки и обозначим их Z,; s = 1, 2, . . .. Пусть к = (А:п . . ., к^3 где некоторые (или даже все) kj могут совпадать. Назовем двоичным. параллелепипедом Пк множество точек с координатами (zlt . . ., zn) такими, что z^ ЕЕ 1ц j при / = 1, 2, . . ., п.
Очевидно, любой такой двоичный параллелепипед принадлежит единичному «-мерному кубу Кп.
Пт-сетки. Сетку, состоящую из N = 2V точек куба К", назовем По-сеткой, если каждому двоичному параллелепипеду Пе с объемом Ущ. — WN принадлежит одна точка сетки.
Например, сетка, изображенная на рис. 1.1, не является По-сеткой, а сетка, изображенная на. рис. 1.3, — П0-сетка. (Поясним, что в число двоичных прямоугольников с площадью 1/18 входят прямоугольники с размерами 1 х Ч1е, Ч. х V8, V4 х V4, V8 x V2, V18 x 1).
Нетрудно доказать, что точки П0-сетки расположены в каком-то смысле равномерно в К ”. К сожалению, такие сетки существуют только при п = 1, 2, 3; в четырехмерном кубе невозможно построить П0-сетку с числом точек ^ > 4. Поэтому требование к распределению точек сетки приходится ослабить и ввести более общее определение.
Определение. Сетка, состоящая из N == 2V точек куба К”, называется Пх-сеткой, если каждому двоичному параллелепипеду Пе с объемом УПк = 2T/^V принадлежат 2х точек сетки. При этом всегда предполагается, что v > т.
Например, сетка, изображенная на рис. 1.1, представляет собой П2-сетку.
Пх-сетки существуют в К” при любых п, однако значения т с ростом п приходится увеличивать. Проекции точек, образующих Пт-сетку в К”, на любую т-мерную грань куба К* образуют m-мерную Пгсетку. Более того, эта m-мерная сетка может оказаться Пт-сеткой с т' < т.
ЛПт-последойа*ельй06ти. Расскотрик йрОийвОлййуй последовательность точек Ро, Pv . . ., Pi, . . ., принадлежащих К”. Назовем двоичним участком этой последовательности множество членов Pt с номерами I, удовлетворяющими неравенству вида
k2‘<i< (к + 1)2* (к = 0, 1, 2, . . .; s = 1, 2,...).
Например, участки 0^i<8, 8^i<16, 16-Ci«С < 24, . . . двоичные, а участок 4 ^ » < 16 двоичным не является.
Определение. Последовательность точек Ро, Pv . . ., Pt, . . . куба Кп называется Л Непоследовательностью, если любой ее Двоичный участок, содержащий не „менее, „чем 2t+1, точек, представляет собой П<-сетку. А ■
Название «ЛП^-последовательность» появилось как сокращение фразы «последовательность, любой двоичный участок которой представляет собой Пт-сетку».
Д.2. Количественные оценки равномерности распределения
Рис. Д.1. К определению отклоненияРис. Д.1. К определению отклоненияВ этом параграфе определены две количественные характеристики равномерности распределения, перечислены некоторые их свойства и оценки этих характеристик для ЛП<пос- ледовательностей.
Рис. Д.1. К определению отклонения
Рис. Д.1. К определению отклонения
Отклонение. Рассмотрим в К" произвольную сетку, состоящую из N точек Pv . . ., Рм- Как и в главе 1, обозначим чеГрез Sn (G) количество точек Pi (с номерами 1 ^ i < N), принадлежащих G. Произвольной точке Р из К* поставим в соответствие параллелепипед Пр со сторонами, параллельными координатным плоског стям, и с диагональю ОР (рис. Д.1). Объем Пр обозначим через Упр-
Определение. Отклонением точек Pv . . ., PN называется верхняя грань
Z)(P1,...,Pw)=sup |^(Пр)-^Пр|.
Рек"
© оз © ян ©
мн © © ©
© © ям ни «v © © мм © мН мн v<mo3v< ^ —* со ям оз СО © мН ©
Таблица Д.1. Таблица числителейТаблица Д.1. Таблица числителейюммГм©о»©Оян©СОО*©ОямсООям© М4мм мм ©03 мн 03 03 03 *Н4 ЯМ 03Гм©г*яи©о©яммнт©(*.са mh©v4C*©o»©o мноа©гн©©ян©©мм©гя© ЧММ ©© ©мн 03 03-МОЗямм V< ©© мН © © © МН мН оз мммм©мм©©мчо»ф©мммм©0*0 © © © ММ ММММ ММММ ММяН©©©©©Г»О©ФяМяМ0м©©ММ©ММ©©МН0.а»©яМмМ©0мф©©©яМ© мНV*ММV<V<мНнН НИмН мНVI МН мНММ©ОмГ*©ЯМ©©0»©©О.Ом’ГМ©©Гм1о^<^<югосотиг~ют^сосог-ю'т<т<тг~г~ют1сосог-ю1гзс~г-'^<сосг)г-ю-нЯ-©ММ©мМ©мМ©©мМ©ММ©ММ©ММм-©мн©мн©мн©©мн©—4©МН©МНМН©МН©МН©МН©©МН©МН©МН©МММИ©МН7MMMMMMvIvImMmMmMvImH ММ ММ мМ ММ VI ММ V»ММмМмМмМмМнМмМмМмМмМмМмМмМмЧЯНмМмМЯНмМмММНмМмМмМмМмМмМмМнНММчИмМмМчНЯМ©©^©©0м©ф©ММ©©^©©0м мН v< ММ мН мМ v< мч мНооа» о"нмсо -» Л «з r>ooo»0'^<ojwa,u3cor«ooa»o ■rt мсо ля> из со c^cgm о н •^•кмсчсчмс4счо5счЯечсосососососо<осососО'а|м<«ч<'*'»|М'с|'М'*-*иэи55юммГм©о»©Оян©СОО*©ОямсООям© М4мм мм ©03 мн 03 03 03 *Н4 ЯМ 03Гм©г*яи©о©яммнт©(*.са mh©v4C*©o»©o мноа©гн©©ян©©мм©гя© ЧММ ©© ©мн 03 03-МОЗямм V< ©© мН © © © МН мН оз мммм©мм©©мчо»ф©мммм©0*0 © © © ММ ММММ ММММ ММяН©©©©©Г»О©ФяМяМ0м©©ММ©ММ©©МН0.а»©яМмМ©0мф©©©яМ© мНV*ММV<V<мНнН НИмН мНVI МН мНММ©ОмГ*©ЯМ©©0»©©О.Ом’ГМ©©Гм1о^<^<югосотиг~ют^сосог-ю'т<т<тг~г~ют1сосог-ю1гзс~г-'^<сосг)г-ю-нЯ-©ММ©мМ©мМ©©мМ©ММ©ММ©ММм-©мн©мн©мн©©мн©—4©МН©МНМН©МН©МН©МН©©МН©МН©МН©МММИ©МН7MMMMMMvIvImMmMmMvImH ММ ММ мМ ММ VI ММ V»ММмМмМмМмМнМмМмМмМмМмМмМмМмЧЯНмМмМЯНмМмММНмМмМмМмМмМмМмМнНММчИмМмМчНЯМ©©^©©0м©ф©ММ©©^©©0м мН v< ММ мН мМ v< мч мНооа» о"нмсо -» Л «з r>ooo»0'^<ojwa,u3cor«ooa»o ■rt мсо ля> из со c^cgm о н •^•кмсчсчмс4счо5счЯечсосососососо<осососО'а|м<«ч<'*'»|М'с|'М'*-*иэи55
Таблица Д.1. Таблица числителей
Таблица Д.1. Таблица числителей
ю
ммГм©о»©Оян©СОО*©ОямсООям© М4мм мм ©03 мн 03 03 03 *Н4 ЯМ 03
Гм©г*яи©о©яммнт©(*.са mh©v4C*©o»©o мноа©гн©©ян©©мм©гя© ЧММ ©© ©мн 03 03-МОЗямм V< ©© мН © © © МН мН оз мм
мм©мм©©мчо»ф©мммм©0*0 © © © ММ ММММ ММММ ММ
яН©©©©©Г»О©ФяМяМ0м©©ММ©ММ©©МН0.а»©яМмМ©0мф©©©яМ© мНV*ММV<V<мНнН НИмН мНVI МН мН
ММ©ОмГ*©ЯМ©©0»©©О.Ом’ГМ©©Гм
1о^<^<югосотиг~ют^сосог-ю'т<т<тг~г~ют1сосог-ю1гзс~г-'^<сосг)г-ю-н
Я-©ММ©мМ©мМ©©мМ©ММ©ММ©ММм-
©мн©мн©мн©©мн©—4©МН©МНМН©МН©МН©МН©©МН©МН©МН©МММИ©МН
7
MMMMMMvIvImMmMmMvImH ММ ММ мМ ММ VI ММ V»
ММмМмМмМмМнМмМмМмМмМмМмМмМмЧЯНмМмМЯНмМмММНмМмМмМмМмМмМмМнНММчИмМмМчН
ЯМ©©^©©0м©ф©ММ©©^©©0м мН v< ММ мН мМ v< мч мН
ооа» о"нмсо -» Л «з r>ooo»0'^<ojwa,u3cor«ooa»o ■rt мсо ля> из со c^cgm о н •^•кмсчсчмс4счо5счЯечсосососососо<осососО'а|м<«ч<'*'»|М'с|'М'*-*иэи5
5
ю
ммГм©о»©Оян©СОО*©ОямсООям© М4мм мм ©03 мн 03 03 03 *Н4 ЯМ 03
Гм©г*яи©о©яммнт©(*.са mh©v4C*©o»©o мноа©гн©©ян©©мм©гя© ЧММ ©© ©мн 03 03-МОЗямм V< ©© мН © © © МН мН оз мм
мм©мм©©мчо»ф©мммм©0*0 © © © ММ ММММ ММММ ММ
яН©©©©©Г»О©ФяМяМ0м©©ММ©ММ©©МН0.а»©яМмМ©0мф©©©яМ© мНV*ММV<V<мНнН НИмН мНVI МН мН
ММ©ОмГ*©ЯМ©©0»©©О.Ом’ГМ©©Гм
1о^<^<югосотиг~ют^сосог-ю'т<т<тг~г~ют1сосог-ю1гзс~г-'^<сосг)г-ю-н
Я-©ММ©мМ©мМ©©мМ©ММ©ММ©ММм-
©мн©мн©мн©©мн©—4©МН©МНМН©МН©МН©МН©©МН©МН©МН©МММИ©МН
7
MMMMMMvIvImMmMmMvImH ММ ММ мМ ММ VI ММ V»
ММмМмМмМмМнМмМмМмМмМмМмМмМмЧЯНмМмМЯНмМмММНмМмМмМмМмМмМмМнНММчИмМмМчН
ЯМ©©^©©0м©ф©ММ©©^©©0м мН v< ММ мН мМ v< мч мН
ооа» о"нмсо -» Л «з r>ooo»0'^<ojwa,u3cor«ooa»o ■rt мсо ля> из со c^cgm о н •^•кмсчсчмс4счо5счЯечсосососососо<осососО'а|м<«ч<'*'»|М'с|'М'*-*иэи5
5
мм©сормс*-©ян-имн©и)ми|4<эиэ©е5©©о©©©©о*©о©омне*.с»*мммммнмн©саг*©©©ямниа»о»'мо»ммоно© 00©©©©ГмО'4,ям©©ОГ»©©—*<5мчо*ямни©<о©©©©©©©©©©©©0©ям©©©^мнонО©©©С*© ©©о-©аО'*г,©©051-©о©©©*«'©©оФгн©©©©©*«<сз©©©*4’*«'о«*в’©чг*ч,*«'Гя©©©^соям©©©
ммсн©00*яМмн©©©мн©са©ОСО©ян©нн©ей©©0©0*©©0-имнмМО»0*См©ОммнмМ©©©©ммОфмчО©мн ©©©См©©©©Оян©©©©©©мн(*.©© мн'^ ^ФОЮт^ФООЗЮОЗ-^ОООСОС^ОМсООС-ФО^оОи^ © чу stf мН © v< © ©-н stf ©© © <*© ян ^ ^ ©© © © © мН © s# sy мн ^ 03 03 03 ку ^ СО 03 СО Т^ 03 Ю 03 *^ со со
г* Ю С) F* -« 0) © © О) ifl tf) (*. Д о- С» ян tfi С> СО 1Л krt С- Ю Г* С» С) С) С) © © © © мН ifi tfl © f Г> © С> 1Л *• С* «С> © СО С) © v (н © о* © о* ну оз о о о ю оз о сосо о *4* со ю е> ю о* со чу оз со © г* со о v* со © © © о ям
© мм мНмНнН© 03 -HV<r< мм мН мН © мН © мн мН мНмм vt мН мН мм мН © ©
г* © г»С5 Ю ©С5 ©Ci О-СО Ен ©£м fO t*>©CO >©©©мчС5 С»С5 Л ©©Ю >05 ©-л©© чнО ©>© ©О нф ©Г* н® CJ со © ** оз 03 © ну СО © мн ну © ОСО © © 03 мм со ЯН ну о» ММ 03 ЯН О» О» © Л© 03 янф©^О©мн МН СО © О ММ со О
МН МНММV<мНМММНММММмН МММЧ
яМмМчмсОянС>Г*0*©СО©янммГяеОГя©янС»СОО*0*©©ОСОямсОяниОО©СО©0»ммОСм©^АСОянммС»©©ямОСмСОС*© © ну 1ГЗ © ну © СО © ЯМ ю © со СО мН ео © 03 мН V4 оз 03 ОЗМНОЗОЗ *4* СО ЯМ 03 ян ММ 03 ЯМ оз 03 ©мн 03 COCO‘S
13
14
15
16
18
18
19
1 = 20
1
1
1
1
1
1
' 1
1
4 369
13 107
21845
65 535
65 537
196611
327 685
983 055
4125
4141
28 723
45 311
53 505
250113
276231
. 326 411
5 889
6915
16 647
49 925
116487
83 243
116529
715 667
6 929
16241
16 565
17 139
82 207
50979
252 717
851901
8913
11643
18 777
35 225
102401
45059
36865
299 009
6211
2147
3169
35 873
33841
99 889
247 315
1032 727
1731
11977
7 241
63609
81003
15 595
144417
685 617
1347
4417
5 087
12 631
103445
152 645
130 127
775 365
6197
14 651
2 507
27 109
5205
91369
302 231
172 023
2817
9997
7 451
12 055
44 877
24 895
508 255
574 033
5 459
2 615
13329
35887
97 323
83 101
320 901
810 643
8119
13 207
8965
9 997
75 591
226 659
187 499
628 265
5121
13313
19 457
1033
62487
250 917
234 593
308 321
7 669
2671
18 391
31 161
12111
259781
36159
232 401
2 481
5 201
3123
32 253
78 043
63447
508 757
974 837
7 101
11469
11699
15 865
49 173
147 489
81991
802 875
2 677
14855
721
26 903
100419
206 167
241 771
987 201
1405
12 165
709
41543
57 545
77 163
357 231
378135
7 423
5 837
20481
12 291
86017
12303
299 025
774 207
725
5 387
19 285
5 165
27 985
69 809
128 325
164 575
2 465
12 483
13057
28 931
54 019
21 251
62 233
248081
471
12 945
32 321
29377
127 427
103 759
472541
1008 719
2887
1279
4865
64 771
24321
42 247
338 691
599 831
1715
187
12 285
53631
110 851
4 357
153347
671033
5 595
8133
4 929
10817
8 261
189901
255 947
734 787
5 689
11819
15 889
48083
67 537
63993
336 469
749 285
441
14 471
12 625
8881
34 707
85105
479 495
911 133
3169
7 615
8405
41135
106823
107 847
339031
977 907
4 485
2 981
12 593
60 913
15 703
26967
507 907
■ 344 073
6 311
4 081
28637
60 935
94129
109 273
475921
281389
3 557
7 223
13425
58 577
69521
217 151
424 277
789 985
483
11843
28285
12 029
86 021
217 093
348165
176 165
3 781
10799
15893
959
19793
213491
377 941
414 943
3195
9 277
15405
19 637
87 283
186143
343 297
1041185
5 213
2 031
4 677
26 607
20 931
54 345
259163
74108?
5 085
15 371
19493
56445
26 369
27 399
521499
132 383
185
6603
1129
36087
66817
98051
451841
175 36i
7 323
7 563
25 321
52 563
37 745
81777
235 347
539 89s
1713
11617
14 979
5 455
68 289
209 987
346 179
521289
/■
4021
4129
4 099
12 345
102 733
21287
128115
2068g
5 875
12061
25469
47 423
29 505
124 097
444613
430 92ч
5 363
3471
17 589
50 131
33137
98739
361365
42673?
4 977
15 919
6 731
43 771
23 313
151281
270 519
И 187
5 441
1097
13483
58 779
36 561
116819
420 599
998 391
1779
10369
15 325
33 331
118321
59 665
498 897
494 137
6777
14343
18465
63615
43349
30 799
322 567
939 017
287
8475
6929
46013
52 785
75 249
14 035
50716c
6 919
16139
16 677
34 579
120981
239 693
73299
863 54c
1517
305
21765
45 827
91157
113 679
204881
7619Ц
1875
7 621
4 381
9 079
94 533
37 261
431301
176 455
(В литературе часто отклоненной называют отношение DIN, которое для случайных точек Plt . . ., Pn превращается в отклонение выборочной функции распределения этих точек Sn (lip)IN от теоретической функции распреде
ления УПр.)
Чем меньше D, тем более равномерным следует считать расположение точек Рх, . . ., Pn в Кп. Легко видеть, что всегда D (Рх, . . ., Pn) < N, но точная нижняя граница неизвестна.* (При n = 1 она равна Ча.)
Теорема!. Для того чтобы, последовательность Рх, . . . ...,Pt, . . . была равномерно распределенной в К*, необходимо и достаточно, чтобы при N со
D (РхPN) = о (N).
Специалисты полагают [22, 23],
ОIX, что наилучший возможный поря
док отклонений при N -* со ра- Рис. Д.2. К определе- В0Н о (lnn N).
тельных» октантов.тельных» октантов.нию неравномерности Неравномерность. Выберем в /С* произвольный двоичный параллелепипед П& и перенесем начало координат в центр Пе. Координатные плоскости разобьют Пе на 2" равновеликих октантов (точнее — гипероктантов) (рис. Д.2). Обозначим через У* совокупность всех «положительных», а через У* — совокупность всех «отрица
тельных» октантов.
тельных» октантов.
Если в К” заданы N точек Рх, . . ., Pn, то равномерность их расположения в Щ можно характеризовать величиной | Sn (Vk) — Sn (Vk) |. Верхняя грань этой величины по всем двоичным параллелепипедам
зир^У^-Я^У;))
есть целое число, как-то характеризующее расположение точек Рх, . . ., Pn в К*.
Определение. Неравномерностью точек
Рц . . ., Pn называется максимальная верхняя грань
ф- (Ръ ..., PN) = max sup | SN (У?) - SN (У?) |, ns
где максимум берется по всем сеткам, которые состоят из проекций точек Pv . . ., Рц на какую-нибудь т-мерную грань куба Кп (Рассматриваются всевозможные грани при всевозможных 1 ^ т ^ п).
Нетрудно доказать, что 1 ^ ф™ (Рц . . ., Pn^ ^ ^- хотя значение ф» = 1 реализуемо только в одномерном случае. (В двухмерном случае (и = 2) точная нижняя граница фо,, = 2, а при п > 2 точная нижняя граница неизвестна).
Теорема. 2. Для того чтобы последовательность Ри . . ., Рь . . . была равномерно распределенной в К", необходимо и достаточно, чтобы при N оо
Ф=о(Р1,...,Р1у) = о(Л0.
Наилучший возможный порядок неравномерностей при N -► оо равен О (1).
Оценки отклонений и неравномерностей. Обозначим, как обычно, через 1,1 биномиальный коэффициент, так что ( д ) = т (m —- 1) . . . (т — к + 1)Ш
Теорема 3. Для любой Песетки в К*1, состоящей из N> 2п-1+т точек, справедлива оценка
п—1
/)(Р1,...,Р„)^ 2 3=4 х 1’
где v = log2 N.
Теорема 4. Для произвольного начального участка любой Л Непоследовательности в К", содержащего не менее, чем 2”-1+т точек, справедлива оценка
п—1Т 4- 1 \ Т
D(Po,...,PW-i)<2«[l +2
где vx = Е (log2 TV) — целая часть логарифма N.
Теорема 5. Для произвольного начального участка любой Л Непоследовательности в К*1 справедлива оценка
<рго(Ро,...,Рн-1Х2"-1«
Пусть теперь Qo, " Qu . . ., Qt, . . .— какая-нибудь ЛПгпоследовательность в К?. Так как оценка неравномерностей 9 теореме 5 ие зависит от N, то очевидно, при
N -> ОО
ф« (Со, • • •, Qn-i) = О (1);
это наилучший возможный порядок.
Из теоремы 4 вытекает, что при N -* оо
Р(Со,...,ек-1) = О(1п"Л);
как упоминалось выше, это, по-видимому, наилучший возможный порядок для всех N. Однако, если ограничиться только значениями N вида N = 2V, то зту оценку можно усилить. Дело в том, что любой начальный участок Со, Со • ■ ч Qn-i при N = 2V представляет собой Пт-сетку (если только v > т), и для оценки неравномерности можно воспользоваться теоремой 3, откуда вытекает, что при N = 2V
P(Co,---,Cn-i) = 6»(1b"-W).
Последняя оценка показывает, что при практическом использовании ЛПт-последовательностей, вообще говоря, целесообразно выбирать количество точек вида N = 2V. Тогда можно удваивать N, сохраняя эту оценку и не пересчитывая уже имеющиеся точки.
Из теорем 1 и 2 и оценок Р и фк для ЛПгпоследова- тельностей следует, что все ЛПгпоследовательности равномерно распределены в К".
Случай кубических решеток. Для кубических решеток (см. раздел 1.1 и рис. 1.1), которые состоят из N = Мп точек с координатами
\ ММ ) ’
где q, . . ., in независимо принимают все значения О, 1, . . ., М — 1, величины Р и ф» можно вычислить точно:
Р = 4" ^1-1/"’Ф” = и1-^ •
Из этих формул видно, что при n = 1 отклонение и неравномерность таких решеток минимальны: Р = %, ф^, = 1. Однако с увеличением п порядки этих формул быстро ухудшаются и приближаются к наихудшему порядку 0^.
Для случайных сеток, состоящих из N независимых случайных точек, равномерно распределенных в К\ с большой вероятностью Р = О (^NY Поэтому асимцто-
Тика отклонений для таких Сеток лучше, Чем абимпТотика отклонений для кубических решеток, при п ^> 3, когда V, < 1 - 1/п.
Д.З. Алгебраическая теория
Этот раздел Дополнения — самый сложный. Здесь очень коротко описан эффективный способ построения ЛПгпо- следовательностей, у которых все координаты всех точек двоично рациональны.
ДР-последовательности. Выберем бесконечную треугольную матрицу вида
которую будем называть направляющей матрицей. Элементы vsj) расположенные ниже главной диагонали, могут быть нулями и единицами.
Задание матрицы (vsj) равносильно заданию последовательности двоично рациональных дробей (в двоичной системе)
V, = 0, vAusl . . . и,,,
которые называются направляюгцими числами.
Последовательностью двоично рационального типа или ДР-последовательностъю называется последовательность чисел г (0), г(1), ..., г(<),.. ., вычисляемых по следующим правилам:
1°. г (0) = О, г(2у=У<п;
2°. Если 2* < i < 2<+1, то г (i) = г (2*) ♦ г (i - 2’), где ♦ означает поразрядное сложение по модулю 2 в двоичной системе. Эта логическая операция, называемая также «исключающее ИЛИ», осуществляется во всех современных ЭВМ одной командой и часто используется для сравнения кодов (вычислители называют ее обычно командой «сравнение»). Например, 7/13 ♦ 6/за = п/за, ибо 7А« = 0,0111,6/за = 0,00101, а «сумма» 0,0111 ♦ 0,00101 = = 0,01011.
Нетрудно доказать, что правила 1° и 2° равносильны следующему определению: если в двоичной системе / = »т . . . e#v то
г (i) = e1V1 ♦ еаИа * . . . ♦ emVm.
Лемма. ДР-последоваШелЬНоеть Г (0), г (1), ... . . ., г (i), . . ., соответствующая направляющей матрице (v,j), есть одномерная ЛП ^последовательность, составленная из всевозможных двоично рациональных дробей.
Пример. Пусть v,j = 6,^ то есть все v„ = 1, а при s =# ] все vsj = 0. Тогда соответствующая ДР-после- довательность представляет собой последовательность вап дер Корпута: если i = em---e1e1, то
Р (0 = О А«1* ••«,».
Ниже строятся многомерные ЛПгпоследовательности, каждая координата которых представляет собой ДР-по- следовательность. Основная трудность такого построения — обеспечить в каком-то смысле независимость этих координат.
Моноциклические операторы в поле GF (2). Поле GF (2) состоит из двух элементов: 0 и 1. Правила умножения — обычные; правила сложения: 0 + 0 = 14-1=0, 0 + 1 = 1 + 0 = 1.
Рассмотрим линейное разностное уравнение порядка т с постоянными коэффициентами
Lu^ = 0,
где разностный оператор L определен выражением
Lux = Uj+m + Cm-lUi+m-1 + * * * + +^1+1 + U^
здесь все ut и at принадлежат GF (2).
Решением уравнения Lut = 0 назовем бесконечную последовательность
. . ., U-j, U_tl Uo, Uu U$, . . .,
определенную при всех —оо <; i <; оо и удовлетворяющую уравнению при каждом I.
Определение. Оператор L называется люно- циклическим, если уравнение Ли, = 0 имеет решение о наименьшим периодом 2,п — 1.
Так как существует всего 2т —1 различных нетривиальных групп (ии . . ., um), состоящих из нулей и единиц, то нетрудно доказать, что все нетривиальные решения мо- ноциклического уравнения различаются между собой лишь сдвигом нумерации. В литературе иногда такие решения называют ЛГ-последовательностями (последовательностями максимального периода).
Таблица всех моноциклические операторов до поряд-
ка 9 включительно приведена в [271, где, однако, имеется" опечатка: вместо кода оператора 207 должен стоять .код 203.-
Пример. Оператор и1+4 4- и|+3 4- и1+а 4- «, пе мо- ноциклический, так как уравнение
°i+4 4* «t+з 4* Wj+a 4- «« = 0.
имеет решение U( = 1 с периодом 1.
Оператор uj+4 4* Ui+i 4- «j моноциклический, так как любое нетривиальное решение уравнения
ui+4 4* u«+i 4- u« = О
имеет период 45. Например, решение
. . ., 1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,. . .
Построение ЛПт-последовательностей. Условимся говорить, что направляющая матрица (р,Д принадлежит, оператору L порядка т, если выполнены два условия:"- > а) Каждый из первых т столбцов матрицы является решением уравнения Lut = 0:
Lu^ = 0
при каждом фиксированном /; 1 ^ j ^ т. б) Каждый из последующих столбцов матрицы является решением неоднородного уравнения:-л "
Lvtj = vt> j_m
при каждом фиксированном j; m < / < оо?
Про ДР-последовательность, соответствующую? такой направляющей матрице (vs/), будем также, говорить/.что она принадлежит оператору L. Так как элементы т^'егбя- \ щие ниже диагонали в первых т столбцах; могут/выби-4 раться произвольно/то одному оператору могут принадлежать разные ДР-последовательности. . . \
Теорема 6. Пусть Ьг, . . ., L^ — различные мо- ноцихлические операторы, порядки которых равны т^, . . . . . ., тп. Пусть pj (0), pj (1), . . ., Р) $, . . .— какая- нибудь ДР-последовательность, принадлежатцая оператору Lj. Тогда последовательность точек Qo, Qu . . ., Qt, ... с координатами•
Qt = (P (0. Pi (0Рп (0)
есть Л Непоследовательность в К? со значением
т = 3 (mj — 1).
Здесь в качестве первой координаты использована определенная выше последовательность ван дер Корпута, о которой формально можно сказать, что она принадлежит оператору Lut = uj+1 и единичной матрице (v,j).
О значениях т. Из последней формулы видно, что для того, чтобы уменьшить т, следует выбирать моноцикличе- ские операторы Lj возможно низких порядков m^. G помощью теоремы 6 построены ЛПх-последовательности, для которых т = 0 при и = 1 и 2 и т = 1 при и = 3; доказано, что эти значения т — минимальные. При п = 4 получается значение т = 3, однако минимальность этого значения не доказана. Вообще, при и оо
т = О (п log п).
Д.4. О дополнительных свойствах равномерности
Оценки, полученные в разделе Д.2, показывают, что по своей асимптотике все ЛПх-последовательности относятся к числу наилучших. Однако для практики важно, чтобы равномерность расположения устанавливалась быстро, а не только при N —» оо. С этой целью в статье [34] были сформулированы некоторые дополнительные требования, которые можно удовлетворить путем выбора неопределенных пока элементов v,, в направляющих матрицах.
Свойство А. Разобьем куб Ки плоскостями ij = 1/а при j = 1, 2, .■. ., и на t = 2" октантов, которые будем считать двоичными параллелепипедами. Разобьем последовательность точек Ро, Ръ . . ., Рп . . . на двоичные участки, длина которых равна t:
Ре,..., Рц; Pt,... ,Р4t-i", P»h • • •»Рэм! • • •
Если в любом из этих участков все точки принадлежат различным октантам, то мы говорим, что последовательность обладает свойством А.
Теорема 7. Последовательность Q6, Qv. . ., Qb ..., построенная в теореме 6, обладает свойством А тогда и только тогда, когда определитель размером п X п, составленный из первых столбцов всех направляющих матриц, равен 1 (mod 2).
Существование ЛПгпоследовательностей, обладающих свойством А, в любом К? доказано в [34). Недавно И. Б. Матусов доказал, что Л ^-последовательность, обладающую свойством А, можно построить, используя все моноциклические операторы низших порядков подряд.
В табл. Д.1, приведенной ниже, использованы все моноциклические операторы подряд, а направляющие числа выбраны так, что свойство А выполняется при любом и 16.
Свойство А'. В кубе К" проведем Зп плоскостей z; — 4V zj = г/г, Zj = 3/4 при у = 1, 2, . . ., и. Они разобьют Кг на t* = 4" кубиков, которые мы также будем считать двоичными параллелепипедами. Разобьем последовательность Ро, Pv . . ., Рь . . . на двоичные участки, длина которых равна t':
Рд, . . . , Рt'_iJ Pf, ... , Рgf-ii Pgt'i • • • » Р3*'—1 i • • •
Если в любом из этих участков все точки принадлежат различным кубикам, то мы говорим, что последовательность обладает свойством А*. .
Свойство А' также исследовано в статье [34]. Мы отметим только, что направляющие числа, приведенные ниже в табл. Д.1, выбраны так, что свойство Л' выполняется при каждом и 6.
Можно ли, используя все моноциклические операторы низших порядков подряд, выбрать направляющие,матрицы так, чтобы при каждом п были выполнены и свойство Л, и свойство А* — неизвестно.
Свойство А в какой-то мере гарантирует разумное расположение точек 2о» 2i> • • •» Qn-i при N <. 2", так как каждая следующая точка попадает в один из свободных октантов. Более того, при N = 2"-1 можно доказать, что половина точек расположена в области Zj ■< %, а другая половина — в области Zj > Vi, каково бы ни было / = 1, 2, . . ., и. '
Д.5. Вычисление интегралов
Точки ЛП-г-последовательностей используются в качестве' узлов кубатурных формул для вычисления интегралов по К”. В некоторых случаях такой способ вычисления интегралов обеспечивает наилучший порядок сходимости.- Мы ограничимся минимальными сведениями из этой об-* ласти. При этом будем обозначать точку fo,. . ., 2^) = Р и dz1. . . dzn = ДР. '
Предположим, что требуется вычислить интеграл
= J tUW-
к"
Теорема 8. Если последовательность Pv . . . . . ., Рь . . . равномерно распределена в Кп, то для любой ограниченной интегрируемой по Риману функции f (Р)
. N
^yHPiW.
Рассмотрим теперь класс функций И^ (С), непрерывных в Кп и имеющих кусочно непрерывные частные производные, содержащие не более одного дифференцирования по каждому переменному, которые по абсолютной величине не превосходят С.
Более подробно, в определение класса функций Wx (С) входят все производные вида dfldxj, все производные вида d^ldxjdix при ] Ф к и т. д. до самой старшей среди них З^^дхудх^ . . . дхп включительно. И все эти частные производные по абсолютной величине не превосходят С.
Теорема 9. Если Qo, Qt, . . ., Qtl . . .— ЛПх-по- следователъностъ в К", то при N = 2? и v ->- со
N-1
sup 1У ^^ ”11 = 0 W1 In"'1 NV
В статье [20] доказано, что этот порядок сходимости оптимальный для класса И^ (С).
Примеры вычисления интегралов высокой кратности при помощи ЛПт-последовательностей имеются в [30, 38, 39].
Вычисление несобственных интегралов [28, 291. Предположим, что 1° функция / (Р) и все ее частные производные, входящие в определение класса И^ ((7), непрерывны при 0 < х} ^ 1; / = 1, 2, .... и; 2° при xt. . . хп 0 функция имеет интегрируемую особенность вцца
Теорема 10. Если Qo, Qt1 . . ., Qtl . . . — ЛП<по- следовательность, построенная согласно теореме 6, то для любой функции f (Р), удовлетворяющей требованиям!0 и 23,
N
Д.6. Некоторые Другиё свойств
Отлично распределенные последовательности. НаряДС с равномерно распределенными пОследовательностями^ас^ «матривают также гораздо более узкий класс последовав тельностей, который называют ОтлиДно распределенными (well-distributed [221). Чтобы определить такие йбёлед^ вательности, необходимо наряду с исходной пОследОВаг-i тельностью Рп . . ., Р^, . . . рассмотреть всевозможны^ достаточные» последовательности вида Pt+1, . . .;J^^§^ Пусть Sn,* (П) — количество точек с номерами /с^1>^^ ^ i < к + N, принадлежащих П (определение$ПДрм£ раздел 1.1). '
Определение. Последовательность' Pii* .... . . . ., Pt, . . . называется отлично распределенной^выгЕ^ для любого П_ . '
SN,k№ V ■
равномерно относительно к = 0, 1, 2, . . .
Если в качестве Pt выбирать независимые случайные, точки, равномерно распределенные в ^, то с-вёрря^ ностью 1 последовательность Ръ . . ., Pt, . . .„будёщ^Й Но вероятность того, что последовательность .эта^кё^ жется отлично распределенной, равна 0: . Теорема И [351. Все ЛП<последоват^ън5ср^ отлично распределены."/—
Корреляционные свойства ЛПт-послсдовательностейй В алгоритмах Монте-Карло, с конструктивной^аа!^^ ностью п можно использовать точки ЛЛгПоследов^^!^ ности Qt = (?».!,V., qlin) вместо случайныХ^т^ёк^ (Тх* • • ч Yn)i гДе . Y/ — независимые случайные^пгсла ‘ [15, 321. При этом вместо сходимости по вероятности "со скоростью 1/[/Жгарантируется сходимость в классическом смысле, иногда со скоростью lW1-e, где е > 0 как^угод- но мало.,
В таких расчетах роль независимых случайныхиисел' Yj и ^ играют последовательности координат ^j;. . . • • ч qt /1 • • • и г, . .1, . . . Вместо соотношения
Г (Yy, yO = 0
(определение коэффициента корреляции приведено^^.2);_
имеем соотношение
N-1 lim ЛГ У, ZV-.cc " A-J ' 1=0
Скорость сходимости в последней формуле исследовалась эмпирически Б. Г. Ситниковым и А. П. Шагуи. На основании этих экспериментов в [381 была высказана гипотеза, что при А = 2V
N-t
N У, (<7и — 4") (чм — 4") = 4 + ^i-1 ^’ i=0
где все 6j (v) — целые неотрицательные числа.
Несмотря на то, что многочисленные расчеты подтверт ждают эту гипотезу, а для 61Л (v) в [381 даже подобрана аналитическая формула, строгого доказательства (или опровержения) этой гипотезы нет.
Бесконечномерные ЛПт-последовательности. Так как количество моноциклических операторов бесконечно, то теорема 6 позволяет рассматривать бесконечномерные точки
Xt = (р (0. Ра (0. • • -, Рп (0. • • •),
проекции которых на Кп при каждом и представляют собой ЛЩ-последовательности в Кп. Изучению последовательностей точек Xv Xs, . . ., Xt, . . . посвящена работа [301. С помощью таких точек можно вычислять бесконечномерные интегралы, решать интегральные уравнения, моделировать цепи Маркова (см. также [31, 331). Исследованию бесконечномерных равномерно распределенных последовательностей посвящена также статья [21].
Д.7. Формулы расчета
Таблица числителей. В табл. Д.1 приведены числители rj° направляющих чисел при 1 ^ / ^ 51, 1 ^ i ^ 20- Хотя в расчетах точек Qi удобнее использовать сами направляющие числа
V^ = r^2~l, мы табулировали числители, чтобы уменьшить объем таблицы. По таблице Д.1 можно вычислять точки Qt с номерами 0 ^ i < 2м в кубе К? размерности и ^ 51. 96
Если требуются точки размерности п<^51, то Следует? использовать лишь первые п строк таблицы; если; количество используемых точек заранее ограничено Г<<2'м, где 1м <? 20, то можно ограничиться ^первыми 1м столбцами этой таблицы..'
Исходный алгоритм. Перед началом расчета над’6; заменить таблицу zf таблицей Уу\
Далее, если в двоичной системе номер точки I "записывается в форме i = ат . . . е4еъ то все декартовы коорди-. ваты точки Qt = (qt.i, . . ., Qi,я) вычисляются по единой, формуле (/ = 1, 2, . . ., п):/
где • означает поразрядное сложение по модулю два ; ■ в двоичной системе (операция «исключающее <ИЛИ>). ' Подробнее о ней сказано в разделе Д.З. - .*
В формуле (1) умножать е, на У^1 не надо: если е^=?1^ . то соответствующее значение У^1 войдет в (1)^к^&сли? с, = 0, то соответствующее У^ надо пропуститьЖГакйм; образом, для расчета по формуле (1) нужны тольк&^йга^. ческие операции.•-;
Блок-схема программы для такого расчетадимеется?- в [27], программа для ЭВМ типа М-20 прйведена^^^^С^
Арифметический алгоритм. Для реалийацйй|^ормуйы»? (1) удобно использовать машинные команды.^Есл^^&дйу? ■ возможности нет или использование процедур в'м&инн^ коде нежелательно, то можно прибегнуть к рас^гужнепОтК' средственно по таблице г) . Для этого по >заданномуt- номеру i вычисляем
тп = 1 4- [In i/lnk2],
а затем для / = 1, 2, . . ., п
тпm,
qij = £ 2-**i {4- £ I2 <i2^l I2 (гУ’2^}]} л
В последних двух формулах [z] — целая часть ;?a?{z}j дробная часть числа z.'
Расчет по арифметическому алгоритму гораздо^еддё нее, чем расчет по формуле (1), но если количество исй зуемых в расчете точек Qt не превосходит 104,тоонрп не приемлем. Составленная по этому алгоритму?поД1
грамма на языке ФОРТРАН, опубликованная н [371 н [361, использовалась во многих расчетах.
Подпрограмма на языке ФОРТРАН.
Целые числа NR {J, Е^ берутся из табл. Д.1. I — номер точки, N — ее размерность. Используются две встроенные функции, имеющиеся во всех версиях ФОРТРАНА: ALOG (X)— натуральный логарифм X и INТ (X)— целая часть X, а также функция, описанная в программе, D (X) = X — INT (X). Значение In 2 принято равным 0,693147. Выходные данные — массив Q.
SUBROUTINE LPT AU {NR, I, N, Q) , DIMENSION Q{N), NR (N, 20) D {X) = X - INT (X) A =1
M = 1 + INT {ALOG (A)/0.693147)
DO 1 J = 1, N
S =0
DO 2 X = 1, M
NS =0
DO 2 L = К, M
В = NR {J, X)
NS = NS +
- INT {2*D {AI2**L^*INT {2*D{B!2** {L 4-1 - X)))
2 S = S 4- D {0.5*NSy2**{K - 1)
Q (J) - s
RETURN
END
Сверхбыстрый алгоритм. В статье [19J предложен способ сверхбыстрого расчета ЛП<последовательностей. Для этого порядок следования точек Qt меняется так, чтобы каждая следующая точка Qt легко вычислялась по предыдущей точке Qt-i и чтобы при этом двоичные участки новой последовательности ^0, Qx, . . ., ф4, . . . совпадали с двоичными участками последовательности @0, Qu . .. • • •» Qh • • • Последнее условие гарантирует сохранение всех основных и дополнительных свойств равномерности.
Пусть Г (i) — так называемый код Грея, соответствующий номеру i. По определению
Г (0 - i ♦ [i/21, где [zl — целая часть z.
Например, Г (3) = 2, так как ж двоичной системе 1 = И, [i/21 = 1, i » [i/21 = 10; или Г (10) = 15, так как i = 1010, [i/21 = 101, i » [i/21 = НИ.
Два соседних кода Г (i) и Г (i — 1) всегда различаются в одном и только в одном разряде I *» I (i), номер которого можно вычислить по формуле
Z = l + log4ir(i)*r(i-l)l(2)
Поэтому, полагая Q\ = @Г(ф получаем для расчета Q*t следующий простой алгоритм:
Iе- 9о,1 =... = gojn — 0;
2°. ^/«дй.^ (/=1,2n).
Так как вычисление по последней формуле и по формуле (2) может быть осуществлено при помощи одних логических операций, то при больших п этот алгоритм оказывается быстрее, чем стандартные алгоритмы получения псевдослучайных чисел, в которых для получения п чисел надо затратить п умножений.
Сверхбыстрая подпрограмма на языке ФОРТРАН. Необходимо сразу же подчеркнуть, что расчет по этой программе возможен только в том случае, когда транслятор позволяет использовать простейшие логические функции, описанные в конце параграфа. Расчеты [381 выполнены с помощью транслятора FOREX, составленного Ю. М. Банковским в Институте прикладной математики им. М. В. Келдыша АН СССР. Составитель подпрограммы — Ю. Л. Левитан.
Вспомогательная подпрограмма, пр едназначенная для перехода от г] к V].
Будем считать известным двумерный массив NR (JM, LM), содержащий таблицу числителей Д.1 или ее часть. Размер массива должен быть указан: например, DIMENSION NR (51, 20), если JM = 51, LM = 20.
Программа NRIV вычисляет таблицу направляющих чисел IV, исходя из таблицы числителей NR.
SUBROUTINE NRIV (NR, IV, JM, LM) DIMENSION NR (JM, LM), IV (JM,LM)
DO 1 L = 1, LM
LL = L — 40
DO 1 J - 1, JM
1 IV (J, L) = ISIS (NR (J, L), LL)
RETURN
END
Подпрограмма для расчета точки Qt п о Qi-v
Все координаты нулевой точки равны 0. Величина NG полагается равной 0. Это необходимо сделать в главной программе.
После этого в цикле по I можно обращаться к подпрограмме LPTAU, которая вычисляет координаты7-й точки Qt. Эти координаты заносятся в массив ^, и их нужно сразу использовать, так как при следующем значении I туда же заносятся координаты следующей точки.
В подпрограмме вычисляются N компонент 7-й точки ЛЩ-последовательности Q,.
SUBROUTINE LPTAU (IV, NG, I, N, Q, IQ)
DIMENSION ()(51), IV (51, 20) t IQ (51)
NA = 32 000 000 000 000 00 В
NB = 64 000 000 000 000 00 В
NC = 17 777 777 777 777 В
ND = 40 000 000 000 000 00 В
NT = 100B
NGN = IEOR (I, ISL0 (I, 1), NA)
A = IEOR (NG, NGN, NB)
L = IOR (ISIS (A, 41) - NT, NB)
DO 1 J = 1, N
IQ (J) = IEOR (IAND (IQ (J), NC), IV (J, L))
1 Q (J) = IOR (IQ (J), ND)
NG = NGN
RETURN
END
Использованные логические функции. В приведенной программе использованы четыре логические функции: ISIS, IAND, IOR, IEOR.
1°. Функция ISIS (X, 7) — сдвиг кода на количество разрядов, равное | 7 |. Если 7 < 0, то сдвиг влево; если 7 > О, то сдвиг вправо.
2°. Функция IAND (av at, :. ., «„) = ax Д я4 Д . . . ...Де» — логическая операция «И», выполняемая поразрядно.
3°. Функция ЮН (an аа, . . ., a„) = a, V °«V - • • . . . V °п — логическая операция «ИЛИ», выполняемая поразрядно.
4°. Функция IEOH (а^ а2, . . ., aj = Й1 ♦ ®i* • • • . . . * On — логическая операция «Исключающее > ИЛИ»,: выполняемая поразрядно.
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
К главам 1—5
Артоболевский‘И. И. Успехи советской школы теории машин и механизмов. М.: Знание, 1977.
Артоболевский И. И., Сергеев В. И., Соболь И. М., Статников Р. Б. Об использовании ЭВМ при постановке задач оптимального проектирования машин. Докл. АН СССР, 1977, 233, № 4, с. 567-570..’
Bartel D. L., Marks R. W. The optimum design of mechanical systems with competing design objectives.— J. of Engineering for Industry, Trans. ASME, 1974, N 2, p. 171—178. .
Бенайюн P., Ларичев О. И., Монгольфье Ж., Терни Ж. Линейное программирование с многими критериями; Метод ограничений.— Автоматика и телемеханика, 1971, № 8, с. 108—115.
Вентцель Е. С. Исследование операций. М.: Сов. радио, 1972.
Гринкевич В. К., Зинюков П. И., Статников Р. Б., Сухоруков Л. В., Фридман С. И. Определение оптимальных параметров механизма по нескольким локальным критериям,— В кн.: Методы создания машин в малошумном исполнении. М.: Наука, 1978, с. 44—49.-
Гуткин Л. С. Оптимизация радиоэлектронных устройств. Мл Сов. радио, 1975.
Калиткин Н. Н. Численные методы. М.: Наука, 1978.,
Крюков Б. Н., Литвин Л. М. Динамика резонансных вибромашин с нелинейными основными и приводными упругими связями.— Вибротехника, 1973, № 3 (20).
Озерной В. М. Принятие решений. Обзор.— Автоматика и телемеханика, 1971, № 11, с. 106—121.
Подиновский В. В. Методы многокритериальной оптимизации. М.: изд. ВИА им. Ф. Э. Дзержинского, 1971, выл. 1.
Растригин Л. Д. Системы экстремального управления. М.: Наука, 1974.•■
Самарский А. А. Теория разностных скем. М.: Наука, 1977.
Соболь И. М. Многомерные интегралы и метод Монте-Карло.— Докл. АН СССР, 1957, 114, № 4, с. 706—709.
Соболь И. М. Численные методы Монте-Карло. М.: Наука, 1973.
Соболь И. М., Статников Р. Б. ЛП-цоиск и задачи оптималь. ного конструирования.— В кн.: Проблемы случайного поиска.
Рига: Зинатне, 1972, № 1, с. 117—135.
Соболь И. М., Статников Р. Б. Постановка некоторых задач оптимального проектирования при помощи ЭВМ. Препринт № 24. М.: Ин-т прикладной математики АН СССР, 1977.
Федоренко Р. П. Приближенное решение задач оптимального управления. М.: Наука, 1978.
R Дополнению
Антонов И. А., Салеев В. М. Экономичный способ вычисления Л ^-последовательностей.— Ж. вычисл. матем. и матем. физ., 1979, 19, № 1, с. 243—245...
20. Бахвалов Н. С. Оценки снизу асимптотических характеристик . классов функций с доминирующей смешанной производной.—
Матем. заметки, 1972, 12, № 6, с. 655—664.
Каневский В. А., Лев Г. Ш. Последовательности точек распре. деленные в бесконечномерном пространстве.— Докл. АН СССР, 1979, 248, № 1, с. 31—33.
Kuipers L., Niederreiter Н. Uniform distribution of sequences.
. New-York: J. Wiley, 1974.
■ 23. Niederreiter H. Quasi-Monte Carlo methods and pseudo-random numbers.— Bulletin Amer. math, soc., 1978, 84, N 6, s. 957— 1041...
Соболь И. M. О распределении точек в кубе и сетках интегрирования.— Усп. матем. наук, .1966, 21, № 5, с. 271—272.
Соболь И. М. О методе рядов Хаара в теории мнргомерных квадратур.— В кн.: Междунар, конгресс математиков: Тезисы научн. ■ сообщ. М., 1966, вып. 14, с. 48.
Саболь И. М. О распределении точек в кубе и приближенном вычислении интегралов.— Ж. вычисл. матем. и матем. физ., 1967, 7, № 4, с. 784—802.
Соболь И. М. Многомерные квадратурные формулы и функции Хаара. М.: Наука, 1969.■■.
Соболь И. М. Вычисление несобственных интегралов прн помощи равномерно распределенных последовательностей.—
Докл. АН СССР, 1973, 210, № 2, с. 278—281..
Соболь И. М. Использование "равномерно распределенных последовательностей для приближенного вычисления несобственных интегралов.— В кн.: Теория кубатурных формул и приложение функционального анализа. Новосибирск: Наука, 1973, с. 62-66.'■
Соболь И. М. Бесконечномерные равномерно распределенные последовательности в вычислительной математике. Препринт № 22. М.: Ин-т прикладной математики АН СССР, 1974.'
" Соболь И. М. О псевдослучайных числах для построения дискретных цепей Маркова методом Монте-Карло.— Ж. вычисл. матем. и матем. физ.; 1974, 14, № 1, с.-36—44.-
■ 32. Соболь И. М. Бесконечномерные равномерно распределенные последовательности в алгоритмах Монте-Карло.— В кн.: Методы Монте-Карло в вычисл. матем. и матем. физ. Новосибирск: Наука, 1974, с. 24—31.
Соболь И. М. О сходимости бесконечномерных кубатур и мо-- делировании цепей Маркова.— В кн.: Вопр. вычисл. и приклад. матем. Ташкент, 1975, вып. 32, с. 162—167.
Соболь И. М. Равномерно] распределенные] последовательнос- ' ти с дополнительным свойством равномерности.— Ж. вычисл, матем. и матем. физ., 1976, 16, № 5, с. 1332—1337.■
Соболь И. М. О иа и лучших равномерно распределенных последовательностях.— Усп. матем. наук, 1977, 32, № 2, с. 231—232.'
Sobol’ 1. М. On the systematic search in a hypercube. SIAM J. Numer. Analysis, 1979, 16, N 5, p. 790—793.■ :
Соболь И. М„ Левитан К). Л. Получение точек, равномерно расположенных в многомерном кубе. Препринт № 40. М.: Ии-т прикладной математики, 1976.
Соболь И. М., Левитан Ю. Л. Эксперименты по вычислению интегралов высокой кратности.— В кн.: Вопр. вычнел. и приклад. матем. Ташкент, 1978, вып. 51, с. 138—145.
Соболь И. М., Розин С. Г., Хомский Л. X. О конструктивной размерности алгоритмов Монте-Карло. — В кн.: Методы Монте-Карло в вычислит, матем. и матем. физ. Новосибирск, 1976, с. 16-23.
ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
Адаменко А. И., Кисленко В. И., Ракицкий Л. Б., Солдатова Г. В., Оноприч В. П. Задачи и методы оптимизации серий асинхронных машин малой мощности.— В кн.: Проблемы технической элект- родипампки. Киев: Паукова думка, 1975, вып. 52, с. 3—9.
Андрюшкявичюс А. И., Рагульскис К. М., ШульнЮс П. П. Оптимальный синтез ЛПМ с бесконечным кольцом магнитной леиты по амплитуде переходного процесса при старт-стопных режимах механизма,— Вибротехника, 1978, № 2(23), с. 27—32.
Артоболевский И. И., Бобровницкий Ю. И., Генкин М. Д. Введение в акустическую динамику машин. М.: Наука, 1979. •
Артоболевский И. И., Генкин М. Д., ГринкевичВ. К., Соболь И. М., Статников Р. Б. Оптимизация в теории машин ЛП-поис- ком.— Докл. АН СССР, 1971, 200, №6, с. 1287—1290.
Артоболевский И. И., Генкин М.Д., Крейнин Г. В., Сергеев В. И., Статников Р. Б. Поиск компромиссного решения при выборе параметров машин.— Докл. АН СССР, 1974, 219, № 1, с. 53—56.
Артоболевский И. И., Емельянов С. В., Сергеев В. И., Статников Р. Б., Шестаков О. А. Интерактивный метод решения задачи оптимального проектирования машины.— Докл. АН СССР, 1977, 237, № 4, с. 793—795.
Артоболевский И. И., Крейнин Г. В., Павлов Б. И. К созданию системы автоматизированного поиска параметров машин.— Машиноведение, 1977, № 5, с. 18—27.
Артоболевский И. И., Крейнин Г. В., Пронина М. А., Сергеев В. И., Статников Р. Б. Выбор оптимальных • параметров машин с помощью многомерных таблиц испытаний.— Машиноведение, 1973, № 4, с. 3—14.
Артоболевский И. И., Руссман И. Б., СерзеевВ.И., Статников Р. Б. О некоторых способах выбора интегрального критерия качества в задачах оптимального проектирования машин.— Машиноведение, 1978, № 2, с. 3—10.
Афонин А. А., Бондаренко В. И., Ракицкий Л. Б., Химюк И. В. Оптимизация электромеханических устройств бегущей волны.— В кн.: Проблемы технической электродинамики. Киев: Паукова думка, 1975, вып. 52, с. 102—104.
Бакшт В. А., Глазов Ю. Е., Зарх Я. М., Тайнер С. Я. К вопросу о выборе передаточной характеристики активного виброгасящего устройства.— В кн.: Методы создания машин в малошумном исполнении. М.: Наука, 1978, с. 94—99.
Бакшт В. А., Руссман И. Б., Статников Р. Б. Выбор оптималь-
вых параметров машин на основе интегрального критерия качества.— В кп.: Проектирование механизмов и динамика машин. М., 1977, вып. И, с. 183—187.
Генкин М. Д., ЕлезовВ. Г., Статников Р. Б., Яблонский В. В. Выбор оптимальных параметров активного виброизолятора .' с электромеханической обратной связью по относительному перемещению н суммарной силе.— В кн.: Виброакустические процессы в машинах и присоединенных конструкциях. М.: Наука, 1974, с. 76---83.
Генкин М. Д., Зиню ко в П. И., Статников Р. Б. Критерии качества и определение параметров малошумпых механизмов.— В кн.: Методы создания машин в малошумном исполнении. М.: Наука, 1978, с. 38—44.
Генкин М. Д., Руссман И. Б., Статников Р. Б., Фридман С. И. Применение методов классификации и интегральных критериев для анализа табдиц испытаний,— В кн.: Оценка характеристик качества сложных систем н системный анализ: Тез. докл. VIII межведомственного (I Всесоюзного) научно-технического семинара. М., 1978, с. 75—78.
Гринкевич В. К., Медник А. И., Сергеев В. И., Статников Р. Б. О выборе оптимальных параметров машин в многокритериальных задачах.— В кн.: Моделирование задач машиноведения на ЭВМ. М.: Наука, 1976, с. 17—26.
Гринкевич В. К., Соболь И. М., Статников Р. Б. Определение оптимальных динамических моделей в пространстве параметров.— Механика твердого тела, 1971, №4, с. 52—54.
■ Докукин А. В., Красников Ю. Д., ХургинЗ.Я. Статистическая ' динамика горных машин. М.: Машиностроение, 1978.
Захаров В. В., КочегуровВ. А., Саблин Н. И.. Оптимизация эксплуатации ускорителей заряженных частиц. М.: Атомиздат, 1977.
Захаров В. В., Смирнова В. И. Экспериментальное сравнение некоторых псевдослучайных последовательностей.— В кн.: Проблемы случайного поиска. Рига: Зннатне, 1976, вып. 5, с. 185— 190.
Зейтман М. Ф., Статников Р. Б. Поиск статистическими методами оптимальных параметров гибкого зонтичного ротора высокоскоростной ультрацентрифуги с двухступенчатой упругой подвеской,— В кн.: Колебания и уравновешивания роторов. М.: Наука, 1973, с..43-47.
Карамзин Ю. Н., Сухорукова А. К., Чернега'П. Н. Задачи оптнми- •зации в когерентной нелинейной оптике.— Тр. междунар, школы йо нелинейной оптике и голографии. Прага, 1980, с. 172.
Матусов И. Б., Статников Р. Б. Принятие оптимальных решений на основе таблиц испытаний,— В кн.: Динамические характеристики и колебания элементов энергетического оборудования. М.: Наука, 1980, с. 21—29.
Старостенко В. И. Устойчивые численные методы в задачах гравиметрии. Киев: Наукова думка, 1978.
Sergeyev V. I., Sobol I. М., Statnikov R. В. Computer aided statement of engineering optimum design problems/Proc. of the fifth World Congress on the Theory of Machines and Mechanisms. Montreal, 1979, vol. 2, p. 871—874.
Соболь И- M-v Статников P. Б., Овчинникова H. Ф. О локализа-
ции характеристических чисел матрицы.— Ж. вычисл. матем. и матем. физ., 1973, 13, № 6, с. 1581—1583.
Соболь И. М., Статников Р. Б., Пронина М. А. Испытание ЛП- поиска на некоторых тестовых функциях.— В кн.: Проблемы случайного поиска. Рига: Зинатне, 1973, № 2, с. 213—217.
Статников Р. Б. Выбор параметров проектируемых машин.—' В кн.: Динамика машин и синтез механизмов/Тр. ВЗМИ, 1975, 32, с. 266—272.
Статников Р. Б. Решение многокритериальных задач проектирования машин на основе исследования пространства параметров.— В кн.: Многокритериальные задачи принятия решений. М.: Машиностроение, 1978, с. 148—155.
Статников Р. Б., Зейтман'М. Ф. Оптимизация динамических свойств гибких вертикальных роторов статистическими методами.— В кн.: Теория и практика балансировочной техники. М.: Машиностроение, 1973, с. 212—219.
Статников Р. Б., Руссман И. Б., Фридман С. И. О некоторых методах принятия решения и задачах машиноведения.— В кн.: Динамические характеристики и колебания элементов энергетического оборудования. М.: Наука, 1980, с. 3—12.
- Статников Р. Б., Фейгин Г. Л. О коррекции параметрических ограничений в задаче улучшения оптимальных решений.— В кн.: Исследование динамических систем на ЭВМ. М.: Наука, 1980, с. 47—53.
Статников Р. Б., Фридман С. .И., Шестаков О. А. Человеко-машинная процедура выбора оптимальных параметров машин.— В кн.: Проектирование механизмов и динамика машина М., 1977, 11, с. 174—182. I
Статников Р. Б., ШеЬтаков О. А. Об одной процедуре принятия решения в задаче оптимального проектирования.— В кн.: . Проектирование механизмов и динамика машин: Межведомственный сборник научных трудов. М., 1977, 10, с. 116—124.
Сушкин В. А. Постановка вадачи оптимального проектирования системы привода исполнительного органа стругового агрегата.— В кн.: Механизация горных работ на угольных шахтах. Тула: Тульский политехнический ин-т, 1979, с. 93—99.
Сушкин В. А., Мерцалов А. Н. Распределение моделей по вероятностным зонам в диалоговой системе оптимизации выемочных машин.— В кн.: Механизация горных работ на угольных шахтах. Тула: Тульский политехнический ин-т, 1980, с. 28—39.
Шалтянис В. Исследование эффективности ЛП-поиска на классе многоэкстремальных задач.— В кн.: Теория оптимальных решений, Вильнюс, 1976, вып. 2, с. 59—65.
УКАЗАТЕЛЬ
Выделение зависимых критериев 60■
Вычислительный эксперимент 6
Двоичный ' отрезок 81 параллелепипед 82 участок 83 Диалоговый алгоритм 21 • автоматизированный 54 схема 25-
Допустимая точка 20,
ДР-последовательность 89
Интеграл 93 .■
несобственный 94
Класс функций W^C) 94 Код Грея 98 Компромиссная кривая 45 аналитическая 49 ■ приближенная 47 Корреляционные свойства ЛП- последовательностей 95 Коэффициент корреляции ,56 критериев 57 ,вычисление 59
Критериальные ограничения 20 Критерии линейно-зависимые 56.
Критерий качества 19, нормированный 27 V "' решающий 36•• "
Кубическая решетка 8-
Логические функции 100 ЛП-поиск 13,38
Л ^.последовательность 83
" бесконечномерная 96 неравномерность 87 отклонение 87
Матрица критериев 23 Метод'
Монте-Карло 16, 95 , ограничений 56 ' , -
отбора 15 последовательных уступок 56
Минимальное свойство эффективных точек 40
Многомерный куб Кп 8
Множество~
возможных точек D 40
допустимых точек D 20
паретовсиих точек Е 40■
эффективных точек Е 39
Модернизация исходной моде. ли 70
Моноциклический оператор 90 Монте-Карло алгоритм 95-
М-последовательность 90
НаправляЮщан матрица 89 Направляющие числа 89 Неравномерность 86 кубической решетки 88 Л Непоследовательности 87
Операция * 89
Оптимальные параметры 36 Отклонение 83 кубической решетки 88 " Л Непоследовательности
■87
Песетки 88.
Отлично распределенная последовательность точек 95
Параметрические ограниче- . ния 17
Паретовская точка 40 Подпрограмма 98, 100 Поиск в многомерном кубе 8 в произвольной ограниченной области 14 случайный 12
После GF (2) 90.
Поразрядное сложение по модулю два в двоичной системе 89,
Последовательность ван дер Корпута 90 двоично-рационального типа 89
BN 24
ЛЩ 83
отлично распределенная 95
равномерно распределенная 10
Приближенная компромиссная кривая 47
Приближенно паретовские точки 46 эффективные точки 42
Пробные точки 23
Простейший поиск 12 Пространство критериев 40 параметров 17
Псевдокритерии 26
Пт-сетка 82
Равномерное распределение точек в кубе 10 в произвольной - ограниченной области 14
Редуктор 28
Резонансная виброплощадка 66
Ресурс точки 63 относительный 65
Решающий критерий 36
Свойство
Л 92"
Л' 93
Случайный поиск 12
Случайные числа 95
Специальная £-окрестность 43
Сходимость 43, 47
Таблица испытаний 21, 27
время расчета 24
Таблица числителей .направляющих чисел 84
Транслятор FOREX 99
Усеченная таблица испытаний
27
ФОРТРАН 98, 99 а
Функциональные ограничения 18
Цепи Маркова 96
Эффективная точка 38
Эффективность отбора 16
ОГЛАВЛЕНИЕ
Предисловие авторов ...... 2
Введение■ 5
Глава 1. Систематический поиск в многомерных областях ■ 8
1.1. Поиск в многомерном кубе 8
1.2. Поиск в произвольной ограниченной области *14
Глава 2. Выбор критериальных ограничений16
Исходные данные . . . . . 17
Диалоговый алгоритм . . . . . 21
Некоторые особенности алгоритма 26
Пример: оптимизация параметров редуктора 28
.Глава 3. Выбор параметров.. .36
.1. Один решающий критерий . 36
3.2. Несколько решающих критериев 38
3.3. Компромиссная кривая 45
3.4. Примеры расчета приближенных компромис- ' сных кривых 49
Глава 4. Некоторые возможности метода 54
Автоматизированный вариант диалога . . ,54
Исследова'Ние зависимости критериев . . .' .56
О возможностях улучшения оптимального ' решения - 4>2
Глава 5. Пример: оптимальное проектирование резонансной виброплощадки 66
■5.1. Исходные данные 67
Первая задача: попытка модернизации исходной модели . ' 70
Вторая задача: эскизное проектирование новой модели... . . ........... . .79
818181813*8 8 8 S 88 83 8 83*8 8 8 S 88 83 8 8
81
81
81
81
3*8 8 8 S 88 83 8 8
3*8 8 8 S 88 83 8 8
Дополйепие. йекото^ые свойства Лйт-посЙедов4- тельностей . . . Д.1. Геометрическое определение . .. . .
Д.2. Количественные оценки равномерности распределения.
Д.З. Алгебраическая теория
Д.4. О дополнительных свойствах равномерности ..
Д.5. Вычисление интегралов
Д.6. Некоторые другие свойства
Д.7. Формулы расчета
Цитированная литература К главам 1—5 ..
К Дополнению•• • •
Дополнительная литература
Указатель
Илья Меерович Соболь
Роман Бенционович Статников
ВЫБОР ОПТИМАЛЬНЫХ ПАРАМЕТРОВ В ЗАДАЧАХ СО МНОГИМИ КРИТЕРИЯМИ
Утверждено к печати
Ордена Ленина Институтом пржкладно! математжкж им. И. В. Келдыша
Академии наук СССР
Редактор издательства И. М. Мататова
Художественные редактор Т. П. Поленова
Технические редакторы А. М, Сатарова, Р. Г. Грузинова
Корректоры И. И. Казарина, Л. В. Лужичева .
ИБ № 21136
Сдано в набор 11.05.81.
Подписано к печати* 05.11.81.
Т-28212. Формат Мх108>/«
Бумага типографская J4 2
Гарнитура обыкновенная
Печать высокая
Усл. печ. л. 5,88. Усл. кр-отт. 6,09 Уч.-взд. л. 5,8
Тираж 5000 эка. Тип. вак. 556
Цена 60 коп.
Издательство «Наука»
111865 ГСП-1, Москва, В-585, Профсоюзная ул., 80
2-я типография издательства «Наука»
121090, Месива, Г-88, Шубивски! в«у., 10