pronikov_a_s_1994_t_1 (830969), страница 39
Текст из файла (страница 39)
Решение задачи трассировки сводится к определению последовательности прохождения прямоугольных площадок. Волновой алгоритм включает в себя два этапа. Этап 1 заключается в построении числовой волны (вычисление длины между элементами) от начальной точки трассы, которая находится в некоторой прямоугольной площадке. Как только числовая волна достигнет конечной точки трассы, процесс распространения числовой волны заканчивается.
Каждой площадке при- Р-~-ех1г Р (х), х~б (5.21) Рис. 5.16. Минимизация длины трубопроводов гидросистемы станка методом динамического прог- раммирования сваивается весовое значение, определяющее расстояние от этой площадки до начальной точки трассы. Для этапа 2 получают модель, аналогичную модели задачи динамического программирования (например, на рис. 5.16). Соответственно алгоритм на втором этапе будет реализовываться так же, как и алгоритм динамического программирования. Этап 2 заключается в проведении соединительной трассы с учетом запретных зон на площади размещения элементов и ограничивающих условий.
Перебор площадок начинают от конечной точки трассы так, что на каждом шаге выбирают прямоугольную площадку, имеющую наименьший вес. Волновой алгоритм связан со значительными затратами машинного времени, причем 90 % времени затрачивается на распространение волны и лишь 10 % — на проведении трассы. Лучевые алгоритмы обеспечивают сокращение затрат машинного времени за счет того, что рассматривают не все прямоугольные площадки, как это делается в волновых алгоритмах, а только те, которые расположены на некоторых направлениях (лучах).
5.5. Параметрический синтез станочных конструкций Основные задачи параметрического синтеза — назначение технических требований к объекту проектирования и расчет параметров объекта проектирования 124). Причем вторую задачу решают после того, как решена первая. Большинство задач параметрического синтеза представляет собой задачи оптимизации или задачи математического программирования. Общая формулировка задач математического программирования где х=(х1, хя, хз, ..., ха) — вектор параметров объекта проектирования, г(х) — целевая функция, 6 — область ограничений на параметры объекта проектирования.
Оптимизация производится в. соответствии со схемой алгоритма, приведенной на рис. 5.5, где блок генерирования вариантов конструкции реализуется с помощью соответствующего метода оптимизации. Для классификации задач и методов математического программирования обычно используют признаки составляющих математической модели оптимизации, описываемой соотношением (5.21): варьируемые параметры х=(х1, х2, ..., х~); ограничения 6; целевую функцию Р(х). Разделение задач математического программирования по указанным критериям показано в табл. 5.1.
В таблице наличие соответствующего признака обозначается единицей, а отсутствие (противоположное утверждение) — нулем. Так, если размерность задачи оптимизации Й = 1, то она называется одно- параметрической, при Й =2 — двухпараметрической и т. д. Задача, в которой целевая функция имеет несколько экстремумов (много- экстремальная), ставит целью поиск глобального экстремума целевой функции. При отсутствии ограничений решается задача поиска безусловного экстремума.
Целевая функция может включать несколько критериев качества (критерии точности, надежности, производительности, экономической эффективности и др.): Г (х) =(Р,(х), Р2(х), ...,Р (х)). В этом случае задача называется многокритериальной 117] . Дискретное программирование предполагает дискретное изменение с некоторым шагом варьируемых параметров.
В задачах целочисленного программирования параметры х1, х2, ..., х~ могут быть только целыми (например, х; — число станков в автоматической линии) . Задачи целочисленного программирования решаются с помощью методов полного перебора, ветвления, отсечений и т. д. Если х; меняется непрерывно, а ограничения и целевая функция линейные, то решается задача линейного программирования. Самый большой класс задач математического программирования образуют задачи нелинейного программирования, в которых одновремен- Ограниче- ния 6 Параметры х Целевая функция и ограничения Целевая функция Р Ф Ф И Ж,ф д~ О о и 47 Р Ф 63 О х о ~ Ф О х х о.
Ю Задачи и методы математичеекого программирования .!1 Д~ Д~ Ф н ~ о х Е" о щ 63 хм о о Ф й" Щ Сб л Ф (р ~Р ~о Однопараметрические Многопараметрические Однозкстремальные Многоэкстремальные . Безусловной оптимизации Условной оптимизации Однокритериальные Многокритериальные Дискретного программирования Целочисленного программирования О О О Линейного программирования Нелинейного программирования О О Выпуклого программирования Сепарабельного программирования Квадратичного программирования Ге о "о ического программирования Случайного поиска Стохастического программирования Эвристического программирования 5Л.
Задачи и методы математического программирования но нли по отдельности целевая функция и ограничения нелинейны. В зависимости от типа нелинейности различают несколько видов задач нелинейного программирования. выпуклые, сепарабельные, квадратичные, геометрические. Множество х, объединяющее значения параметров х;, называется выпуклым, если прямая, проведенная между любыми двумя точками множества, принадлежит этому множеству. Одно- параметрическая целевая функция Р(х) называется выпуклой, если для любых двух точек х; .и х; н любого ЦО~ Л~: 1) Р(Лх)+(1— — Л)х~ ~ ЛР(х;)+ (1 — Л)Р(х;) .
Гиперповерхность Р(х) является выпуклой, если отрезок, соединяющий ее любые две точки [х;, Р(х;)], [х;, Р(х;)], лежит на поверхности или выше ее. Если функция Р(х) выпуклая, то функция Р(х) — вогнутая. Выпуклость функции в точке х* означает, что х* — точка глобального экстремума функции [17). В случае квадратического программирования ограничении линейны, а целевая функция является комбинацией линейной и квадратичной формы: й й Р(х) = Х а,.х,.+ Х х,-х, с=! с,у=1 Если квадратичная форма Р(х) выпуклая (вогнутая), то имеется максимум (минимум) целевой функции Р(х). Выпуклость или вогнутость квадратичной формы определяют по критерию Сильвестра [3). Задача геометрического программирования формулируется для целевой функции и ограничений в виде позиномов (сумма показательных функций) [6]: у=1,2, ...,д. Задачи геометрического программирования широко используют.
при оптимизации режимов резания. Позиномы являются выпуклыми функ. циями. Сепарабельные ограничения и целевая функция имеют вид д(х)=д;,(х1)+д;,(х2)+ ... +у;„(х~); Ф(х)= Р~(х~)+ Р~(х2)+ ...+ Рк(хк) (5.22) Один из методов решения задач сепарабельного программирования основан на кусочно-линейной аппроксимации функции Р;(х) и д(х) [23) . Если целевая функция и ограничения пред- ставлены нелинейными зависимостями общего вида, это существенно усложняет решение задачи оптимизации. Для таких задач наиболее широко применяют методы регулярного поиска, которые реализуют многошаговый процесс поиска оптимального решения.
Если при поиске оптимума используется информация о предыдущем шаге, поисковые методы называют последовательными, в противном случае методы называют пассивными. Для целевых 'функций одной переменной поиск экстремума производят с помощью сокращения интервала, в котором находится экстремум. Для целевых функций многих переменных применяют градиентныеметоды, в которых для каждого шага или серии шагов выбирают направление движения к оптимальной точке [17]. Все эти методы предполагают, что область, в которой находится экстремум, уже получена, т. е.
предварительно должна быть решена задача поиска глобального экстремума, Для поиска глобального экстремума можно использовать метод случайного поиска. Он заключается в том, что значения варьируемых параметров задают в виде случайных величин с помощью датчика случайных чисел.
Центры группирования экстремальных значений принимаются за предполагаемые точки экстремума и в области этих точек проводится более подробный анализ и выбор области глобального экстремума. Случайный поиск может быть использован и для непосредственного решения задач нелинейного программирования. В этом случае применяются методы направленного случайного поиска, использующие результаты предыдущего шага [6, 7). Задача, в которой как ограничения, так и целевая функция выражаются случайными функциями, называется задачей стохастического программирования [6].
В некоторых случаях эти задачи сводят к детерминированным задачам нелинейного программирования, например, используя лишь математические ожидания варьируемых параметров. В некоторых случаях эта замена позволяет получить достаточно точные значения оптимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
