Материал: САПР технологического оборудования. курс лекций. Новокщенов С.Л., Бойко А.Ю

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

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

Изначально под программированием под Windows подразумевалось программирование на C с использованием Windows Application Programming Interface, на основе чего было создано множество приложений, однако написание работоспособного приложения по этой методике – задача не из легких.

С++ явился огромным шагом вперед в отношении новых возможностей по сравнению с исходным языком. Одной из наиболее распространенных библиотек в C++ является библиотека MFC (Microsoft Foundation Class), который представляет собой дополнительный уровень над Win32 API, который значительно упрощает работу программиста за счет использования готовых классов, макросов и мастеров.

При работе с приложениями Microsoft Office и создании на их основе собственных приложений, используется язык программирования Visual Basic, которым позволяет работать с достаточно сложными элементами интерфейса пользователя, библиотеками кода и средствами доступа к данным при минимальных затратах времени и сил.

6.2. Решение больших разреженных систем линейных уравнений

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

Основным источником разреженности являются модели, в которых существуют локальные связи или локальные воздействия. Многие приложения приводят к матрицам, которые не только разрежены, но и имеют особую структуру расположения ненулевых элементов. Наиболее простые из них - ленточные матрицы, в которых a_ij=0 для |i-j| > ширины ленты. Если ширина ленты равна 1, то такие матрицы называют трехдиагональными.

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

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

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

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

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

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

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

, (6.2)

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

, (6.3)

где L – нижняя треугольная матрица с положительными диагональными элементами. Матрица М называется нижней (верхней) треугольной, если m_ij=0 для i < j (i > j). Верхний индекс T указывает на операцию транспонирования. Разложение ( ) всегда существует, если матрица А положительно определена.

Подставляя ( ) в ( ), имеем

. (6.4)

Замена показывает, что x можно получить, решая треугольные системы

(6.5)

и

. (6.6)

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

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

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

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

1. выбор надлежащего упорядочения;

2. формирование подходящей схемы хранения;

3. реальные вычисления могут быть разделены как самостоятельные объекты исследования и как разные модули программного обеспечения.

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

6.3. Программирование оптимизационных задач

Для непосредственного поиска минимума функции f(x) в некотором интервале a < x < b, в котором, как предполагается, лежит минимум, используются различные численные методы.

Однако, как уже упоминалось выше, большинство оптимизационных задач относятся к классу задач нелинейного программирования, с целью успешного решения которых применяются модифицированные методы прямого поиска. При этом было выдвинуто предположение, что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там, где нарушаются ограничения. К тому же такую идею просто реализовать с точки зрения программирования. Необходимо проверить, каждая ли точка, полученная в процессе поиска, принадлежит области ограничений. Если каждая, то целевая функция вычисляется обычным путем. Если нет, то целевой функции присваивается очень большое значение. Таким образом, поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области. В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице:

Таблица 2

Часовая производительность станков

Составить программу работы станков, при которой в течение смены (8 часов) будет выпускаться максимальное количество комплектов деталей.

Построение аналитической модели

Составим аналитическую модель задачи. Для этого сначала введем переменные, которые требуется определить:

X1 – время, которое работал токарный станок над деталями типа 1 в течение рабочей смены;

X2 – время, которое работал токарный станок над деталями типа 2 в течение рабочей смены;

X3 – время, которое работал токарный станок над деталями типа 3 в течение рабочей смены;

X4 – время, которое работал станок-автомат над деталями типа 1 в течение рабочей смены;

X5 – время, которое работал станок-автомат над деталями типа 2 в течение рабочей смены;

X6 – время, которое работал станок-автомат над деталями типа 3 в течение рабочей смены.

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

Ограничение времени работы токарного станка:

X1 + X2 + X3  8;

Ограничение времени работы станка-автомата:

X4 + X5 + X6  8.

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

5X1 + 15X4 - будет произведено за смену деталей типа 1;

5X2 + 15X5 - будет произведено за смену деталей типа 2;

10X3 + 10X6 - будет произведено за смену деталей типа 3.

Теперь введем сами ограничения:

2(5X1 + 15X4) = 5X2 + 15X5;

2(5X1 + 15X4) = 10X3 + 10X6.

Очевидно, что все переменные в задаче неотрицательные (объем продукции не может быть отрицательным):

X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.

Целевая функция в нашей задаче должна выражать количество комплектов деталей, выпускаемых за смену, поэтому сложим все выпускаемые детали и поделим на 5 (в комплект, как уже упоминалось, входят 1 деталь типа 1 и по 2 детали типа 2 и 3):

E= (5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6)/5  max

или, если упростить это выражение, то получим:

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6  max

Целевую функцию надо максимизировать.

Таким образом, формальная постановка задачи оптимизации имеет следующий вид:

X1 + X2 + X3  8;

X4 + X5 + X6  8;

2(5X1 + 15X4) = 5X2 + 15X5;

2(5X1 + 15X4) = 10X1 + 10X6;

X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6  max

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

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥ 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E = C1X1 + C2X2 + … + CnXn  max

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

Bj ≥ 0, j=1,…,n

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

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

- изменить знаки правых частей ограничений;

- перейти от ограничений-неравенств к равенствам;

- избавиться от переменных, не имеющих ограничений на знак.

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