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

Задачи оптимизации сложны, так как часто приходится ис­кать значения большого количества переменных величин; искомые величины могут иметь несколько оптимумов. Напри­мер, может потребоваться найти глобальный оптимум F{x₁,x₂) в пространстве двух искомых переменных величин (рис. 11,6); необходимо учитывать большое число ограничений, выделяю­щих в пространстве область допустимых значений, например, трехмерную область допустимых значений (рис. 11,в); крите­рии, используемые для выбора решений, имеют сложную форму, например, когда критерий, соответствующий каждому решению,

которое представлено в виде точки в плоскости х_х 0х₂, зависит не только от координат этой точки х₁ и x₂, но и оттого, какой путь S от начала координат до этой точки выбран (рис. 11, г); задача может носить так называемый дискретный характер, например, выбирается способ обработки из четырех возможных (рис. 11, д), характеризующихся длительностью обработки t, мин, и стоимостью обработки С, к, которые должны быть как можно меньше, что делает непригодными большинство методов оптимизации.

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

где А, В, С, a, b — эмпирически (опытным путем) полученные положительные коэффициенты и показатели степени. Опти­мальное значение скорости v, обеспечивающей минимальное значение штучного времени Т, получают из условия по формуле

В частности, если a = b =1, A = 9*10³, B = 10^-3, получаем, что v = 3000 м/мин.

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

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

Найти оптимальный набор способов обработки А, Б, В, Г, Д, для каждого из которых возможно по два или три альтернативных варианта, отличающихся один от другого длительностью обработки (штучным вре­менем) t(мин) и стоимостью обработки С (к).

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

Конкретные значения величин t и С, соответствующих рассматри­ваемым альтернативным способам, приведены в табл. 2.

Необходимо найти такой набор способов, чтобы

где tj и С: — параметры используемых способов, выбранных по табл. 2 для каждой из операций А, Б, В, Г и Д.

Задача, вообще говоря, может быть решена методом полного перебо­ра. Однако этот метод весьма трудоемок даже для данного случая, когда возможно всего 2 • 2 • 3 • 2 •2 = 48 решений.

Эта задача может быть решена методом динамического про­граммирования на основе следующих правил:

1.Общее решение задачи в виде набора АБВГД (с указанием номеров вариантов каждого способа) находится по шагам путем постепенного наращивания: сначала находятся решения АБ, затем решения АБВ и т.д., dплоть до решения АБВГД.

2.
На каждом шаге выявляются все перспективные решения, т.е. от

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

Принцип выявления конкурентоспособных решений: реше­ние № 1 конкурентоспособно к решениям № 2, 3, 4, если оно лучше их либо по длительности обработки, либо по стоимости, либо по тому и другому. Из схемы (рис. 11,6), где стрелки вдоль осей координат указывают направление улучшения кри­териев, видно, что все решения, которым соответствуют точки решений № 2—4 в системе координат t0С, лежащие не левее и (или) не ниже точки, которой соответствует решение № 1, неконкурентоспособны. Решения, которые конкурентоспособны ко всем прочим решениям, называют доминирующими.

На каждом шаге выявляют все допустимые доминиру­ющие решения, которые затем рассматривают на следующем шаге.

3. На каждом шаге параметры, характеризующие данное решение, находят путем применения арифметических операций. Например, для решения А1Б1 получаем (табл. 2), что

Поскольку рассматривается n =5 операций, решение задачи находится за (п — 1) = 4 шага.

Вычисления сводятся в таблицы (табл. 3 — 6), построенные по принципу: находят сочетания всех допустимых доминирую­щих решений предыдущего шага и всех вариантов фактора (т.е. способа), добавляемого на данном шаге, а затем подсчитывают их параметры. Процесс носит ветвящийся характер. На рис. 12 в качестве примера приведена схема, соответствующая пред­последнему и последнему шагам. Нумерация точек совпадает с нумерацией возможных решений в табл. 5 и 6. Точки 1, 10, 13,

16, 11 и 17, составляющие множество доминирующих решений 3-го шага, образуют "юго-западную" границу множества точек, соответствующих всем возможным решениям этого этапа.

Точки 3, 6, 9, 12, 15 и 18, соответствующие недопустимым решениям, на схеме не показаны, поскольку для них

Точки 2, 4, 5, 7, 8 и 14 соответствуют неконкурентоспособ­ным решениям 3-го шага.

Из схемы видно, как на основе доминирующих решений 3-го шага путем их ветвления формируются возможные решения 4-го шага. Например, решение № 1 3-го шага используется для получения решений № 1 и № 7 4-rotuara.

Точки /', 2', 4', 5¹, 11', 3^/, 6^’ и 12' составляют множество доминирующих решений 4-го шага. Точки 7', 8', 9' и 10' -неконкурентоспособные решения 4-го шага.

Из рисунка также видно, что оптимальным решением яв­ляется решение № 12 (точка 12'). т.е. решение А1Б2ВЗГ2Д2, для

которого

В результате получают файл 10 (см. рис. 4,6), в котором представлены либо одно оптимальное решение, либо набор ре­шений-лидеров — лучших решений (например, в виде оптималь­ного решения и ближайших к нему подоптимальных решений). Из набора решений-лидеров затем выбирают лучшее решение, руководствуясь соображениями, которые формализовать было либо невозможно, либо нецелесообразно.