Основы систем автоматизированного проектирования

Математическое обеспечение (МО) включает в себя математические модели (ММ), методы и алгоритмы, необходимые для выполнения автоматизированного проектирования.

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

Обслуживающая составляющая математического обеспечения САПР содержит средства:

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

обработки информационных массивов - методы сортировки, поиска элементов, преобразования структур и поиска данных;

обеспечения вычислительного процесса САПР;

сбора статистики параметров получаемых решений.

Количество частей обслуживающей составляющей математического обеспечения САПР увеличивается вместе с прогрессом теории и практики САПР.

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

2 Общая модель объекта проектирования

Исторически известны два метода исследования: экспериментально - наблюдательный и теоретико - логический. Однако в САПР и кибернетике в целом, используют третий метод - моделирование. По сути это метод экспериментально-наблюдательный, но эксперименты проводятся не с реальным объектом, а с его моделью, которая проще и доступнее чем объект.

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

В САПР модели представляют в виде алгоритмов решения задач, а затем - в виде программ. Модели сложных объектов расчленяются на частные подмодели, разбиваются на более простые, отражающие отдельные стороны функционирования объекта (т.е. подвергаются декомпозиции на частные модели). Каждая частная модель представляет собой некоторое математическое преобразование (2.1.):

где Z = {zi, i=1..k} - совокупность выходных параметров модели;

F - оператор (модель) преобразования (F - функция от входных переменных);

Вектор Х = {xi, i=1..n} - совокупность внешних параметров, приходящих из модели более общей системы;

Вектор Y ={yi, i=1..m} - совокупность входных управляемых параметров модели, которыми может оперировать конструктор в процессе проектирования. Управляемые входные параметры могут меняться в заданных пределах, т.е. на них накладываются так называемые параметрические ограничения:

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

В дальнейшем по мере развития системы САПР математическое обеспечение будет пополняться новыми, необходимыми для описания процесса и объектов проектирования методами, методиками и алгоритмами.

3 Задачи анализа, оптимизации и синтеза

Известны три основных постановки задачи проектирования:

В первом случае заданы параметрические ограничения (2.2.) и модель (оператор) преобразования F, т.е. заданна полная система математических операций, описывающая численные или логические соотношения между множеством X и Y для получения Z. Требуется найти значение вектора Z для любого Y, удовлетворяющего ограничениям (2.2.) и вектору X. Это задача анализа. Она сводится к выполнению расчётов по формуле (2.1)

Во втором случае заданны ограничения (2.2.), математическая модель (оператор) F, а также заданы функциональные ограничения вида:

где Qj(X, Y) - некоторая функция от параметров модели, называемая критерием качества модели (оценка характеристик изделий, например по стоимости, по помехозащищённости и др.); QjH. и QjB - нижний и верхний пределы.

Каждая модель оценивается некоторой совокупностью критериев качества (их число обозначено через p). Критерии качества дают численное представление о степени соответствия изделия его назначению.

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

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

В этом случае приходим к задаче оптимального проектирования, которую можно сформулировать следующим образом. В M-мерном пространстве управляемых параметров найти такое множество точек G, которому соответствовало бы в p-мерном пространстве критериев множество точек s, причем для каждой точки множества s выполнялось бы соотношение (3.1.). При сформулированном подходе любая точка множества G допускает решение. Поэтому G называют множеством допустимых решений. В результате решения находим вектор Z, отвечающий требованиям оптимальности.

В третьем случае - задача синтеза - при заданных X и параметрических ограничениях (2.2.) не задан оператор преобразования F, не известна математическая зависимость между совокупностью входных и выходных параметров. Требуется найти такое преобразование F, при котором выполнялись бы функциональные ограничения вида (3.1.).

Синтез технических объектов нацелен на создание новых вариантов конструкций изделий, а анализ на оценку этих вариантов. Синтез и анализ выступают в процессе проектирования в единстве, итерационной последовательности. При синтезе заранее заданны: допустимый набор используемых элементов, накапливаемых в БД, либо стандартные детали механических конструкций. Различают структурный синтез, т.е. поиск оптимальной или рациональной структуры (схемы) технического объекта, говорят в рамках выбранного принципа действия. Например это задача размещения микросхем на печатной плате. Параметрический синтез - определение наилучших динамических параметров при выбранной структуре.

4 Задачи структурного и параметрического синтеза

Общая постановка задачи структурного и параметрического синтеза.

Результирующее проектное решение (при конструкторском проектировании) ищется на множестве структур А, которые способен создать проектировщик, а также на множестве варьируемых параметров Y. Здесь А и Y образуют множество альтернатив, на которых ищутся решения. Тогда общая форма задачи синтеза ставится так:

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

Процедуры структурного и параметрического синтеза.

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

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

Используются различные методы для варьирования значений параметров, в том числе:

а) полный перебор (сканирование), при котором задается верхние и нижние значения параметров и задается ∆yi

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

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

1 альтернатива проектировщика: перенос ряда независимых параметров Х (внешних ограничений) в число варьируемых параметров Y;

2 альтернатива заказчика: уступки заказчика - снижение требований на ряд некоторых качественных характеристик

Если альтернатива 1 - это уступка нам со стороны смежных проектировщиков, то 2 - это уступка заказчика.

5 Задачи оптимизации

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

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

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

Наименьшее или наибольшее значения целевой функции из всех возможных в заданной области R называются глобальными экстремумами. Значение X, при котором достигается глобальный экстремум, называется точкой глобального экстремума. Локальный экстремум функции f(X) - значение f (Х°) этой функции такое, что для любого Х из R, близкого к Х° из R, справедливо f (Х°) ≥ f (X) (локальный максимум) или f (Х°) ≤ f (X) (локальный минимум).

Обоснованное применение количественных методов для принятия решений - оптимизацию поведения структур систем называют исследованием операций (ИСО). Здесь операция - комплекс целенаправленных действий.

Задача, рассмотренная выше, решается с применением математической модели системы, объединяющей упомянутые ограничения на ресурсы и целевую функцию. Нахождение величин упомянутых параметров системы (они входят в математическую модель как неизвестные) путём решения математической задачи называют математическим программированием. Математическое программирование - важнейшая область математики, ориентированная на широкое применение компьютеров.

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

6 Задачи линейного программирования

Одним из разделов математического программирования является линейное программирование. В моделях линейного программирования так называемая <основная задача> состоит в нахождении неотрицательного решения системы линейных уравнений или неравенств (ограничений), которое минимизирует или максимизирует линейную форму (целевую функцию). Математическая задача линейного программирования записывается в сокращённом виде следующим образом:

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

Пусть необходимо найти минимум целевой функции:

Переменные x1 и x2 должны быть неотрицательными.

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

Линейная форма (линия уровня) для некоторого набора фиксированных значений переменной z представляет собой семейство параллельных прямых. Одна из них, которая пройдёт через вершину многоугольника <М>, ближайшую к началу координат и даст минимум z (для координат вершины).

Графический способ решения (перемещение графика целевой функции по симплексу) приемлем только для двухмерных задач (задач на плоскости). Но геометрическое толкование задачи линейного программирования справедливо и для общего случая (m ограничений и n переменных). Каждое из соответствующих неравенству уравнений системы определяет некоторую гиперплоскость в n - мерном пространстве. Множество неотрицательных решений образует выпуклый многогранник в n - мерном пространстве. Линейная форма z-гиперплоскость, перемещая которую параллельно самой себе, будем получать множество точек пересечения её с выпуклым многогранником. Максимальное или минимальное значение линейной формы z достигается в точках, являющихся вершинами выпуклого многогранника.

В силу трудности решения задачи графическим способом в случае m ограничений и n>2 переменных применяют другие методы решения задачи ЛП. Наиболее распространённым и удобным является симплекс метод решения задачи ЛП.

Для решения задачи линейного программирования симплекс-методом применяется специальный аппарат формальных преобразований математической модели. Рассмотрим некоторые его положения. Пусть задана основная задача линейного программирования (см. (4.6.1.) и (4.6.2)). Введя в левую часть каждого неравенства добавочную переменную, преобразуем его в уравнение и перейдём к другой, стандартной форме записи:

При этом значения bi должны быть неотрицательными. В случае bi < 0 обе части уравнения умножают на> - 1>. Заметим, что при максимизации z задача сводится к стандартной путём замены: max z = - min (- z).

Систему (4.6.3) после несложных преобразований можно привести к виду:

Здесь bi  0. Коэффициенты при переменных < FONT> равны единице (+1). Данная система представлена в канонической форме записи. Если количество переменных превышает количество уравнений, то существует бесчисленное множество решений системы.

Пусть m < n. Разделим все переменные системы (4.6.4) на две части:

а) основные переменные, количество которых должно быть равно количеству линейно-независимых переменных (m);

б) неосновные переменные, количество которых будет равно n - m.

Назначим первые m переменных (x1, x2, :, xm) в качестве основных. Тогда систему (4.6.4) можно решить относительно x1, x2, :, xm, если определитель m-го порядка, составленный из коэффициентов при переменных x1, x2, :, xm не равен нулю.

Придавая неосновным (независимым) переменным произвольные числовые значения, получим некоторое решение данной системы, причём каждому набору значений независимых переменных будет соответствовать одно определённое решение системы.

Основные (зависимые, несвободные) переменные будем называть базисными, неосновные (независимые, свободные) - небазисными переменными.

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

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

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

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

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

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

Симплекс-метод является наиболее распространенным универсальным методом. Существует несколько вариантов этого метода, рассмотрим один из них.

Необходимо предварительно выполнить следующие этапы:

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

- определить начальное допустимое базисное решение задачи;

Приведем заданную модель к каноническому виду, введя свободные переменные x3 и x4, превращающие неравенства в равенства. Переменные x3 и x4 входят в уравнение с коэффициентом единица и только один раз:

где x3, x4 - дополнительные переменные, x1, x2 - свободные переменные, A3, A4 - начальный базис, A0 -вектор ограничений.

Составим симплекс - таблицу, соответствующую каноническому виду:

Для базисных переменных оценки всегда равны нулю.

Значение критерия для данного начального базиса будет равно нулю:

Так как имеются Dj<0 приступаем к улучшению плана.

В базис вводим вектор A1, которому соответствует минимальное значение Dj. Из базиса выводим вектор A3, так как минимальное q достигается при i=3.

Таким образом, элемент a31 будет направляющим (в таблице выделен зеленым цветом).

Заполняем таблицу, соответствующую новому базисному решению.

Все элементы aij таблицы определяются по следущему рекуррентному соотношению:

где akr - направляющий элемент, l - номер итерации

Приведем расчет нескольких элементов таблицы:

Элемент a42=3 является направляющим (в таблице выделен зеленым цветом).

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

Элемент a13 =1/3 является направляющим (в таблице выделен зеленым цветом).

Поскольку все Dj?0, то план представленный в данной таблице будет оптимальным.

Если в системе ограничений имеются неравенствами вида > и / или =, начальный план не может быть найден так же просто, как в рассмотренном примере. В таких случаях начальный план отыскивают с помощью искусственных переменных.

Вводим в систему три искусственные переменные: x6, x7, x8, позволяющие получить начальный базис.

Для исключения из базиса этих переменных последние вводятся в целевую функцию с большим отрицательным коэффициентом М (в задаче минимизации - с положительным М)

Выбрав в качестве начального базиса векторы A6, A7, A8, решаем полученную задачу с помощью табличного симплекс-метода.

Если в оптимальном решении такой задачи нет искусственных переменных, это и есть оптимальное решение исходной задачи.

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

Элемент a82=4 является направляющим (в таблице выделен зеленым цветом).

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

Элемент a61=7/4 является направляющим (в таблице выделен зеленым цветом).

Направляющий элемент a73=9/ 7 (в таблице выделен зеленым цветом).

Найдено оптимальное решение, так как все оценки неотрицательные и в базисе нет искусственных переменных:

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

Табл. 0			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	0	A3	2	1	-1	1	0	2Ьmin
2	0	A4	6	2	1	0	1	3
	D		0	-3	-2	0	0
	Z		0	0	0	0	0
				Эmin

Табл. 1			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	3	A1	2	1	-1	1	0	-
2	0	A4	2	0	3	-2	1	2/3Ьmin
	D		6	0	-5	3	0
	Z		6	3	-3	3	0
					Эmin

Табл. 2			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	3	A1	8/3	1	0	1/3	1/3	8
2	2	A2	2/3	0	1	-2/3	1/3	-
	D		28/3	0	0	-1/3	5/3
	Z		28/3	3	2	-1/3	5/3
					Эmin

Табл 0		0	2	3	-5	0	0	-M	-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7	A8
-M	A6	7	2	1	-1	-1	0	1	0	0	7
-M	A7	6	1	2	1	0	-1	0	1	0	3
-M	A8	8	1	4	0	0	0	0	0	1	2Ьmin
	D	-21M	-4M -2	-7M -3	5	M	M	0	0	0
				Эmin

Табл 1		0	2	3	-5	0	0	-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7
-M	A6	5	7/4	0	-1	-1	0	1	0	20/7Ьmin
-M	A7	2	1/2	0	1	0	-1	0	1	4
3	A2	2	1/4	1	0	0	0	0	0	8
	D	-7M+6	-9М/4-3/4	0	M+5	M	M	0	0
			Эmin

Табл. 3			0	3	2	0	0
i	Csi	базис	A0	A1	A2	A3	A4
1	0	A3	8	3	0	1	1
2	2	A4	6	2	1	0	1
	D		12	1	0	0	2
	Z		12	4	2	0	2

Табл 2		0	2	3	-5	0	0	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6
2	A1	20/ 7	1	0	-4/ 7	-4/ 7	0	0	-
-M	A7	4/ 7	0	0	9/ 7	2/ 7	-1	1	4/9Ьmin
3	A2	9/ 7	0	1	1/ 7	1/ 7	0	0	9
	D	-4M/ 7 +67/ 7	0	0	-9M/ 7 +30/ 7	2M/ 7 -5/ 7	M	0
					Эmin

Табл 3		0	2	3	-5	0	0
Csi	базис	A0	A1	A2	A3	A4	A5
2	A1	28/9	1	0	0	0	-4/9
-5	A3	4/9	0	0	1	2/9	-7/9
3	A2	11/9	0	1	0	-1/9	1/9
	D	23/3	0	0	0	23/9	30/9