1.2. Оптимизация

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

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

1.2.1. Общие понятия.

Если область оптимизации ограничить задачами инженерной прак­тики, то можно отметить два основополагающих правила технического действия:

• получение желаемого эффекта при минимуме затрат;

• получение максимального эффекта при использовании задан­ных ограниченных ресурсов.

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

Наше поведение к техническому действию обуславливается отно­шение (целевой функции) к критерию:

• минимизация затрат;

• максимизация эффекта.

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

Рисунок 1.27 – Формальная схема организации

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

Задачей оптимизации в математике называется задача о нахождении экстремума (минимума или максимума) вещественной функции в некото­рой области. Как правило, рассматриваются области, принадлежащие R^п заданные набором равенств или неравенств.

Постановка задачи оптимизации.

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значения параметров объ­ектов. Такая задача называется оптимизационной. Если оптимизация свя­зана с расчетом оптимальных значений параметров при заданной струк­туре объекта, то она называется параметрической. Задача выбора опти­мальной структуры является структурной оптимизацией.

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

1. Допустимое множество – множеств .

2. Целевую функцию – отображение .

3. Критерий поиска (max или min).

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

Если допустимое множество , то такая задача называется за­дачей безусловной оптимизации, в противном случае – задачей условной оптимизации.

Классификация методов оптимизации.

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• Локальные методы: сводятся к какому-нибудь локальному экстре­муму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максиму­мом/минимумом.

• Глобальные методы: имеют дело с многоэкстремальными целе­выми функциями. При глобальном поиске основной задачей является выяв­ление тенденций глобального поведения целевой функции.

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

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

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

• Задачи оптимизации, в которых целевая функция и огра­ничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.

В противном случае имеют дело с задачей нелинейного программи­рования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

• если и – выпуклые функции, то такую за­дачу называют задачей выпуклого программирования;

• если , то имеют дело с задачей целочисленного (дискрет­ного) программирования.

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

• прямые методы, требующие только вычислений целевой функ­ции в точках приближений;

• методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

• аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

• численные методы;

• графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации) – если X конечно или четно;

• задачи целочисленного программирования – если X является подмножеством множества целых чисел;

• задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.

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

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

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем как получить математическую модель, нужно вы­полнить 4 этапа моделирования:

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

2. Выбор управляемых переменных. «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные).

3. Определение ограничений на управляемые переменные (равенства и\или неравенства).

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