Green-sell.info

Новые технологии
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Математическая постановка задачи оптимизации

Математическая постановка задач оптимизации и ее интерпретация

В общем виде математическая постановка задачи оптимизации состоит в определении наибольшего или наименьшего значения целевой функции f(x1…,xn) при условиях gi (x1…,xn)≤ bi (i=1,…,m), где f и gi — заданные функции, а bi — некоторые действительные числа. Если все f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.

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

z — оптимизационная цель экономической системы;

f(x1,…,xn) — соответствующая ей целевая функция;

x1,x2,…,xn — показатели степени использования средств достижения цели, могут характеризовать выпуск продукции разных видов, загрузку оборудования, использование ресурсов и т.п.

gi(x1…,xn) — функция совокупных затрат средств i-й группы, используемых для достижения целей;

bi — лимиты, предельные границы совокупных затрат средств i-й группы, фиксируются ограничением на gi(x) сверху.

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

Среди этих предпосылок основными являются следующие:

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

2) признание ограниченности («дефицитности») средств достижения целей;

3) наличие взаимозаменяемости средств и многовариантность их использования для достижения одних и тех же целей.

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

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

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

Концепция ограниченности средств достижения целей в экономике обычно сводится к признанию ограниченности («дефицитности») ресурсов в производственной и непроизводственной сфере.

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

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

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

С использованием математических моделей

Оптимизация химико-технологических процессов

Лекция 7

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

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

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

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

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев — невозможно. Особенно большие трудности возникали при решении задач оптимизации процессов в химической технологии из-за большого числа параметров и их сложной взаимосвязи между собой. При наличии ЭВМ задача заметно упрощается.

Читать еще:  Многокритериальная оптимизация парето

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

— количество продукции – расход сырья;

— количество продукции – качество продукции.

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

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

Ошибка заключается в том, что ставится задача поиска оптимума 2-х величин, противостоящих друг другу по своей сути.

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности.

В первом случае критерий оптимизации – производительность, а во втором –себестоимость.

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

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

4. Учет ограничений.

Как правило, формулировка задачи оптимизации включает:

1) выбор критерия оптимальности;

2) установление ограничений;

3) выбор оптимизирующих факторов;

4) запись целевой функции.

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

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

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

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

Наиболее общей постановкой оптимальной задачи является выражение критерия оптимальности в виде экономической оценки (производительность, себестоимость продукции, прибыль, рентабельность). Однако в частых задачах оптимизации, когда объект является частью технологического процесса, не всегда удается или не всегда целесообразно выделять прямой экономический показатель, который бы полностью характеризовал эффективность работы рассматриваемого объекта. В таких случаях критерием оптимальности может служить технологическая характеристика, косвенно оценивающая экономичность работы агрегата (время контакта, выход продукта, степень превращения, температура). Например, устанавливается оптимальный температурный профиль, длительность цикла –«реакция-регенерация». Но в любом случае любой критерий оптимальности имеет экономическую природу.

Рассмотрим более подробно требования, которые должны предъявляться к критерию оптимальности.

1. Критерий оптимальности должен выражаться количественно.

2. Критерий оптимальности должен быть единственным.

3. Критерий оптимальности должен отражать наиболее существенные стороны процесса.

4. Желательно, чтобы критерий оптимальности имел ясный физический смысл и легко рассчитывался.

Любой оптимизируемый объект схематично можно представить следующим образом (рис. 7.1).

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

Так как Y=f(U), то при фиксированных Х можно записать:

При этом всякое изменение значений управляющих параметров двояко сказывается на величине R:

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

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

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

а) необходим реальный объект;

б) необходимо изменять технологический режим в значительных пределах, что не всегда возможно;

в) длительность испытаний и сложность обработки данных.

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

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

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

Итак, для решения задачи оптимизации необходимо:

Читать еще:  Оптимизация системной памяти

а) составить математическую модель объекта оптимизации:

Y=f(X,U)

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

R=φ(Y)=F(X,U)

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

в) установить возможные ограничения, которые должны накладываться на переменные:

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

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

1. Целевая функция / (х) и-мерного векторного аргумента

  • 2. Ограничения в виде неравенств g (х) > О.
  • 3. Ограничения в виде равенств hk(x) = 0.
  • 4. Область допустимых значений хе D с R».

Задача оптимизации в общем виде:

ограничения II рода gy(x) S 0, j = 1, J;

Классификация задач оптимизации

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

Существует несколько признаков классификации. Основные критерии следующие:

1. По типу параметров задачи оптимизации. Различают непрерывные задачи оптимизации (continues optimization), дискретные (discrete) и целочисленные (integer optimization).

Рис. 1.3. Классификация задач оптимизации

  • 2. По критерию размерности допустимого множества параметров D. Задачи оптимизации по этому критерию делятся на задачи одномерной и многомерной оптимизации.
  • 3. По критерию наличия или отсутствия ограничений на допустимое множество D. Различают задачи условной (constrained) и безусловной (unconstrained) оптимизации. Этот признак классификации имеет место как для одномерных, так и для многомерных задач оптимизации.
  • 4. По характеру ограничений. Различают детерминированную оптимизацию и стохастическую. Если множество допустимых значений включает случайные компоненты, то имеет место стохастическое программирование. При этом стохастическая оптимизация может относиться и к дискретной задаче.
  • 5. По виду целевой функции и виду ограничений. Различают линейное и нелинейное программирование.

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

При нарушении линейности целевой функции или ограничений имеет место нелинейная задача оптимизации. Классификация задач нелинейного программирования в основном определена видом целевой функции и приведена на рис. 1.4.

Ниже представлены постановки основных задач оптимизации в соответствии с рис. 1.3.

Задача одномерной безусловной оптимизации

Ограничения отсутствуют, К = J = 0, D = R’, т. е. задача без ограничений с одномерным вектором. Вид f(x) произвольный.

Задача многомерной безусловной оптимизации

Ограничений нет, K = J = О, D = R», хе[-оо,оо]./(х) — любого вида.

Задача условной многомерной оптимизации

Задача линейного программирования

Целевая функция — линейна, ограничения тоже линейны.

Наиболее известные классические задачи линейного программирования: транспортная задача, задача о диете и другие.

целочисленного программирования

В задачах целочисленного программирования компоненты вектора <х>принимают только целые значения. Известны классические задачи целочисленного программирования: задача о коммивояжере, раскраски графов, теории расписания.

Задача нелинейного программирования

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

Рис. 1.4. Классификация задач нелинейного программирования

Математическая постановка оптимизационной задачи

1. Дать словесную формулировку задачи.

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

3. Выбрать критерий и определить его зависимость от варьируемых переменных.

4. Определить множество «D», т.е. составить все математические соотношения между варьируемыми переменными, определяющие возможность их выбора.

Оптимизационная задача классифицируется:

Задачи определения max функции одной переменной

Постановка задачи: Для функции нужно определить max при условии

(1)

Множество «D», заданное (1) всегда выпуклое.

Определение: функция называется выпуклой на множестве «D», если она имеет на нем единственный max .

Для решения оптимизационных задач применяются методы, которые условно делятся на две группы:

1) аналитические, которые используют необходимое или достаточное условие максимума

2) численные методы

Необходимое условие, это условие при невыполнении которого событие невозможно, однако при его выполнении событие не обязательно имеет место.

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

Необходимое и достаточное условие максимума функции одной переменной

— необходимое условие

— достаточное условие

Метод золотого сечения

; помножим на

;

На каждом шаге расчета внутри интервала неопределенности определяют положение двух точек (№3 и №4), которое должно удовлетворять условиям (*). Вычисляют значение функции в этих точках, сравнивают их между собой и сокращают интервал неопределенности «L» до значения « », так , чтобы внутри « » сохранялась точка с наибольшим значением функции. Внутри сокращенного интервала неопределенности оставшаяся точка располагается в соответствии с соотношением (*). Поэтому на каждом шаге расчета, кроме первого, требуется вычислять значение целевой функции только один раз.

и

— погрешность (допустимая ошибка)

Расчет продолжается до тех пор, пока интервал неопределенности (L) не будет меньше погрешности .

Необходимое и достаточное условие max функции многих переменных (безусловного)

Определение условного максимума

функции многих переменных

(задача нелинейного программирования)

Определить максимум функции функции для .

(1)

Метод неопределенных множителей Лагранжа

Рассматривается подзадача определения max, заданная только условиями (2) и (3)

D: (5)

Составляем новую функцию.

L

-неопределенный множитель Лагранжа

При выполнении уравнения связи (5) функция Лагранжа совпадает с функцией (1).

Читать еще:  Linux mint команды терминала

Если вычислить max функции Лагранжа при произвольной , то (6)

Из (6) следует, что: максимум функции Лагранжа по « » при произвольной « » максимуму той же функции по « » при оптимальном « », т.е.в точке решения [ , ] функция Лагранжа достигает max по « » и min по « ». Это седловая точка функции Лагранжа.

L( , )= (7)

Теорема Куна-Такера – дает условие оптимальности для решения задачи условного максимума (1) ¸(4).

Функция Лагранжа общего вида:

L( (8)

Если — решение задачи (1) ¸(4), то найдутся такие , и такие одновременно не равные нулю, что при функция (8) достигает максимума по , минимума по , а также все а .

L( =

1) если , то д.б.

2) если , то д.б.

Введение

Оптимизация — целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

количество продукции — расход сырья

количество продукции — качество продукции

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

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

При постановке задачи оптимизации необходимо учесть:

  • 1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
  • 2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
  • 3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
  • 4. Учет ограничений.

Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой — критерием оптимальности. Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

Линейное программирование — один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и в нашей литературе стали общепринятыми.

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

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

рационального использования сырья и материалов;

задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

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

В работе используются методы линейного программирования для решения производственной задачи

число ресурсов, затрачиваемых на изготовление единицы продукции

Ссылка на основную публикацию
Adblock
detector