- •Программная реализация алгоритмов оптимизации методические указания
- •Введение
- •1. Постановка задачи оптимизации
- •2. Классификация задач оптимизации и методов их решения
- •3. Использование современных программных средств для решения задач оптимизации
- •4. Структура курсовой работы
- •5. Варианты курсовых работ
- •Библиографический список
- •Содержание
- •396026 Воронеж, московский просп., 14
ФГБОУ ВПО “Воронежский государственный технический
университет”
Кафедра систем автоматизированного проектирования
и информационных систем
Программная реализация алгоритмов оптимизации методические указания
по выполнению курсовой работы по дисциплине
“Оптимизация в системах автоматизированного проектирования” для подготовки студентов по направлению 230100.62 «Информатика и вычислительная техника» (профиль «Системы автоматизированного проектирования») очной формы обучения
Воронеж 2015
Составители: д-р техн. наук, проф. Я.Е. Львович, канд. техн. наук Ю.В. Литвиненко
УДК 681.3
Программная реализация алгоритмов оптимизации: методические указания по выполнению курсовой работы по дисциплине “Оптимизация в системах автоматизированного проектирования” для подготовки студентов по направлению 230100.62 «Информатика и вычислительная техника» (профиль «Системы автоматизированного проектирования») очной формы обучения / ФГБОУ ВПО “Воронежский государственный технический университет”; сост. Я.Е. Львович, Ю.В. Литвиненко. Воронеж, 2015. 18 с.
Методические указания посвящены рассмотрению вопросов разработки алгоритмов оптимизации и их программной реализации.
Методические указания подготовлены в электронном виде в текстовом редакторе MS Word XP и содержатся в файле ОптимизацияКурсовая.doc.
Ил. 1. Библиогр.: 4 назв.
Рецензент канд. техн. наук, доц. Э.И. Воробьев
Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. Я.Е. Львович
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
ФГБОУ ВПО “Воронежский
государственный технический
университет”, 2015
Введение
В настоящее время одним из наиболее интенсивно используемых и наиболее важных инструментариев повышения эффективности управления и оптимизации сложных систем являются математические методы оптимизации. Успешному применению этих методов способствует современная вычислительная техника, интенсивное развитие которой стимулирует внедрение теоретических разработок в инженерную практику.
По содержанию задачи оптимизации весьма разнообразны. Они могут быть связаны с проектированием технических устройств и технологических процессов, с распределением ограниченных ресурсов и планированием работы предприятий и т.д. Это обусловливает актуальность изучения и практической реализации методов оптимизации.
Курсовая работа посвящена углубленному изучению теоретических и алгоритмических основ принятия оптимальных решений. Она заключается в построении и типизации математических оптимизационных моделей и разработке алгоритмического и программного обеспечения для решения различных классов задач оптимального выбора.
1. Постановка задачи оптимизации
В процессе проектирования сложных систем ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией.
При решении задач автоматизированного проектирования технических устройств и технологических процессов разработчику приходится иметь дело с построением двух типов моделей проектируемого объекта:
- структурной, отражающей состав элементов объекта и их связи между собой;
- математической, описывающей с помощью математических понятий (чисел, матриц, множеств, отображений и т.д.) и отношений между ними количественные свойства объекта, существенные с точки зрения решаемой задачи проектирования. В дальнейшем будем считать, что структурная модель проектируемого объекта задана.
Несмотря на всю сложность и разнообразие объектов проектирования, процесс построения их математических моделей содержит следующие общие этапы:
- формализация задачи проектирования;
- анализ и выделение существенных свойств объекта,
- построение математического описания объекта, отражающего взаимосвязь значений существенных свойств друг с другом.
Исходной информацией при этом являются данные о назначении, условиях применения и режимах функционирования проектируемого объекта задаваемые с помощью технического задания. Эти данные позволяют определить основную цель (задачу) проектирования и формализовать технические требования, предъявляемые к объекту проектирования.
Предположим, что конкретный объект может быть охарактеризован конечной совокупностью каких-то свойств, которые соответствуют целям проектирования и могут быть объективно измерены (или вычислены). При выделении существенных свойств необходимо пренебрегать теми свойствами, которые не влияют на решение поставленной задачи проектирования. Количественная оценка существенных свойств объекта, режимов его работы или внешней среды, в которой он должен функционировать, осуществляется с помощью величин, называемых параметрами.
Различают внешние, внутренние и выходные параметры.
Внешние параметры — величины, характеризующие свойства внешней по отношению к объекту среды и оказывающие влияние на его функционирование. Обычно они считаются постоянными величинами (температура окружающей среды, внешнее давление, напряжения источников питания т.д.). В том случае, когда внешние параметры не являются постоянными величинами, они называются внешними переменными, например, приложенные к объекту извне силовые или кинематические воздействия, изменяющиеся с течением времени. Обозначим внешние параметры вектором:
Внутренние параметры (проектные параметры) — величины, характеризующие свойства отдельных элементов проектируемого объекта, определение значений которых является одной из целей проектирования. Обозначим их вектором:
Геометрической интерпретацией пространства внутренних параметров является n-мерное векторное пространство, в котором для каждого из п внутренних параметров хi, выделена координатная ось.
В свою очередь, внутренние параметры подразделяются на электрофизические, топологические, электрические и режимные (концентрация примесей в подложке, коэффициент теплопроводности, модуль упругости, твердость, геометрические размеры, электрическое сопротивление резистора, емкость конденсатора, параметры транзисторов и т.д.).
Совокупность внешних и внутренних параметров называется входными параметрами.
Величины, характеризующие свойства объекта проектирования в целом, как системы, и определяющие степень выполнения объектом своего функционального назначения, называют выходными параметрами. Обозначим их вектором:
Выходные параметры можно только измерять (наблюдать или контролировать), но непосредственно изменять нельзя (мощность рассеяния, коэффициент усиления, расход топлива, КПД двигателя и т.д.).
Внутренние и выходные параметры определяют свойства проектируемого устройства (процесса) как объекта проектирования, а внешние параметры характеризуют внешнюю среду, в которой функционирует рассматриваемый объект.
Входные параметры играют роль независимых переменных, а выходные параметры являются зависимыми от них величинами. Соотношения, выражающие эти зависимости, будем называть математическим описанием объекта проектирования:
или в векторной форме
(1 )
Вид функциональных зависимостей (1) определяется структурной моделью объекта проектирования. В общем случае выражение (1) представляет собой отображение между двумя множествами параметров: , которое может быть получение с помощью одной из следующих математических моделей объекта проектирования:
- функциональной модели, представляющей собой систему уравнений, которая отображает физические или информационные процессы в объекте проектирования;
- аналитической модели, представляющей собой совокупность аналитических выражение и зависимостей входных и выходных параметров;
- алгоритмической модели, представляющей собой алгоритм вычисления выходных параметров по значению входных параметров;
- имитационной модели, частном случаю алгоритмической модели, отражающей поведение проектируемого объекта при заданных меняющихся во времени внешних параметрах.
В дальнейшем нас не будет интересовать вид математической модели, реализующей математической описание объекта проектирования (1). В связи с чем, будем рассматривать выражения (1) как «черный ящик», по численным значениям внешних параметров и внутренних параметров на входе которого получаются численные значения выходных параметров .
Решение задачи оптимизации начинается с формирования математической оптимизационной модели. Обобщенно такая модель может быть записана следующим образом:
(2)
Здесь – вектор варьируемых параметров объекта; f(X) – целевая функция, т. е. функция, характеризующая наиболее важные и существенные свойства объекта и являющаяся критерием оценки качества каждого из вариантов. Целевая функция в оптимизационной модели может стремиться к максимуму или к минимуму. Ее еще называют критерием оптимальности, критерием эффективности, показателем качества объекта и т. д. На основании вычисления значений целевой функции f(X) анализируются и сравниваются между собой различные варианты объектов.
В процессе оптимизации объект должен удовлетворять различным требованиям (конструктивным, техническим, экономическим), которые формализуются в виде системы ограничений. Ограничения на варьируемые параметры называют прямыми ограничениями. Здесь и – нижние и верхние допустимые значения для управляемого параметра , которые зависят от решаемой оптимизационной задачи.
Ограничения вида , называют функциональными ограничениями. Функциональные ограничения являются какими-либо функциями от варьируемых параметров и формулируются в виде системы равенств и неравенств.
Совокупность функциональных и прямых ограничений образует допустимую область или область допустимых решений D.
Таким образом, решение задачи оптимизации сводится к определению значений управляемых параметров , обеспечивающих оптимальное значение (максимум или минимум) целевой функции f(X) и удовлетворяющих системе ограничений. Такой вектор называется оптимальным решением.
Рассмотренная математическая оптимизационная модель является обобщенной и конкретизируется при решении практических задач оптимизации. При этом в зависимости от вида оптимизационной модели задачи оптимизации и методы их решения делятся на классы.