Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Методы оптимизации технических решений. Параметрическая оптимизация. Оптимизационные задачи на графах. Комбинаторные алгоритмы оптимизации.





Оптимальное проектирование - это процесс принятия наилучших (оптимальных в некотором смысле) решений с помощью ЭВМ. Данная проблема возникает и требует решения на всех этапах проектирования и во многом определяет технико-экономическую эффективность и технологичность проектируемых изделий. Большинство задач принятия решений можно сформулировать в терминах теории математического программирования, то есть в виде совокупности критериев качества и ограничений. В соответствии с общепринятыми обозначениями выделим управляемые (внутренние) параметры объекта проектирования X=(x1,…,xn) и выходные параметры Y=(y1,…,ym).

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

Выбор управляемых параметров осуществляют либо по результатам анализа чувствительности, либо в интерактивном режиме по желанию проектировщика / 2 /.

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

Y = F (X), (1.1)

где вектор F = (f1,f2.,…,fm) в качестве компонент может включать как функциональные, так и алгоритмические зависимости. В скалярном виде формула (1.1) примет вид:

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

На каждом этапе проектирования конструкции или технологии РЭС в начале работы приходится принимать решения в условиях неопределенности. Чаще всего это относится к построению или выбору варианта структуры объекта проектирования в рамках блочно-иерархического подхода /2, 3,7,8/, то есть к задачам структурной оптимизации.

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

Один из разделов дискретной математики, часто используемый при принятии решений - теория графов (см., например, учебное пособие [8]). Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.5.

Рис.5. Примеры графов.

На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных графов.

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

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

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

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

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

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

Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

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

Табл.8. Исходные данные к задаче о кратчайшем пути.

Пункт отправления Пункт назначения План перевозок Пропускная способность
       
       
       
       
       
       
       
       
       

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4.

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена.

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


 

Date: 2016-08-31; view: 1047; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию