Оптимизационные модели

Лекция 3 Оптимизационные модели Методологические основы оптимизации В наиболее общем смысле теория оптимизации представляет собой совокупность фундаментальных математических результатов и численных методов, ориентированных на нахождение и идентификацию наилучших вариантов из множества альтернатив и позволяющих избежать полного перебора и оценивания возможных вариантов. Процесс оптимизации лежит в основе всей инженерной деятельности, поскольку классические функции инженера заключаются в том, чтобы, с одной стороны, проектировать новые, более эффективные и менее дорогостоящие технические системы и, с другой стороны, разрабатывать методы повышения качества функционирования существующих систем. Эффективность оптимизационных методов, позволяющих осуществить выбор наилучшего варианта без непосредственной проверки всех возможных вариантов, тесно связана с широким использованием достижений в области математики путем реализации итеративных вычислительных схем, опирающихся на строго обоснованные логические процедуры и алгоритмы, на базе применения вычислительной техники. Необходимые условия для применения оптимизационных методов Для того чтобы использовать математические результаты и численные методы теории оптимизации для решения конкретных инженерных задач, необходимо установить границы подлежащей оптимизации инженерной системы, определить количественный критерий, на основе которого можно произвести анализ вариантов с целью выявления «наилучшего», осуществить выбор внутрисистемных переменных, которые используются для определения характеристик и идентификации вариантов, и, наконец, построить модель, отражающую взаимосвязи между переменными. Эта последовательность действий составляет содержание процесса постановки задачи инженерной оптимизации. Корректная постановка задачи служит ключом к успеху оптимизационного исследования и связана в большей степени с искусством, нежели с точной наукой. Искусство постановки задач постигается в практической деятельности на примерах успешно реализованных разработок и основывается на четком представлении преимуществ, недостатков и специфических особенностей различных методов теории оптимизации. Определение границ системы Прежде чем приступить к оптимизационному исследованию, важно четко определить границы изучаемой системы. В данном контексте система предстает как некоторая изолированная часть реального мира. Границы системы задаются пределами, отделяющими систему от внешней среды, и служат для выделения системы из ее окружения. При проведении анализа обычно предполагается, что взаимосвязи между системой и внешней средой зафиксированы на некотором выбранном уровне представления. Тем не менее, поскольку такие взаимосвязи всегда существуют, определение границ системы является первым шагом в процессе приближенного описания реальной системы. В ряде случаев может оказаться, что первоначальный выбор границы является слишком жестким. Для более полного анализа данной инженерной системы может возникнуть необходимость расширения установленных границ системы путем включения других подсистем, оказывающих существенное влияние на функционирование исследуемой системы. Предположим, например, что на промышленном предприятии имеется красильный цех, в котором готовые изделия поступают на поточную линию и окрашиваются в различные цвета. На первой стадии изучения красильного цеха можно рассматривать его изолированно от других цехов предприятия. Однако анализ может показать, что оптимальный размер партии изделий и последовательность нанесения красителей в существенной степени зависят от особенностей функционирования производственного цеха, в котором выпускаются готовые изделия. Таким образом, возникает необходимость принять решение о расширении границ системы путем включения в нее производственного цеха. Разумеется, расширение границ системы повышает размерность и сложность многокомпонентной системы и, следовательно, в значительной мере затрудняет ее анализ. Очевидно, что в инженерной практике следует, насколько это возможно, стремиться к разбиению больших сложных систем на относительно небольшие подсистемы, которые можно изучать по отдельности. Однако при этом необходимо иметь уверенность в том, что такая декомпозиция не приведет к излишнему упрощению реальной ситуации. Характеристический критерий Если подлежащая исследованию система определена и ее границы установлены, то на следующем этапе постановки задачи оптимизации необходимо осуществить выбор критерия, на основе которого можно оценить характеристики системы или ее проекта, с тем чтобы выявить «наилучший» проект или множество «наилучших» условий функционирования системы. В инженерных приложениях обычно выбираются критерии экономического характера. Однако спектр возможных формулировок таких критериев весьма широк; при определении критерия могут использоваться такие экономические характеристики, как валовые капитальные затраты, издержки в единицу времени, чистая прибыль в единицу времени, доходы от инвестиций, отношение затрат к прибыли или собственный капитал на данный момент времени. В других приложениях критерий может основываться на некоторых технологических факторах. Например, это когда требуется минимизировать продолжительность процесса производства изделия, максимизировать темпы производства, минимизировать количество потребляемой энергии, максимизировать величину крутящего момента, максимизировать нагрузку и т. п. Независимо от того, какой критерий выбирается при оптимизации, «наилучшему» варианту всегда соответствует минимальное или максимальное значение характеристического показателя качества функционирования системы. Важно отметить, что независимо от содержания оптимизационных методов только один критерий может использоваться при определении оптимума, так как невозможно получить решение, которое, например, одновременно обеспечивает минимум затрат, максимум надежности и минимум потребляемой энергии. Здесь мы опять сталкиваемся с существенным упрощением реальной ситуации, поскольку в ряде практических случаев было бы весьма желательным найти решение, которое бы являлось «наилучшим» с позиций нескольких различных критериев. Один из путей учета совокупности противоречивых целевых установок состоит в том, что какой-либо из критериев выбирается в качестве первичного, тогда как остальные критерии считаются вторичными. В этом случае первичный критерий используется при оптимизации как характеристическая мера, а вторичные критерии порождают ограничения оптимизационной задачи, которые устанавливают диапазоны изменений соответствующих показателей от минимального до максимального приемлемого значения. В частности, в примере с красильным цехом различными служащими фирмы, которой принадлежит промышленное предприятие, могут быть выбраны следующие критерии. 1.Начальник красильного цеха отдает предпочтение проекту, согласно которому производственный процесс протекает с минимальными изменениями в ассортименте изделий и используемых красок. При этом максимизируется количество изделий, окрашиваемых в единицу времени. 2.Руководитель отдела сбыта заинтересован в реализации проекта, в соответствии с которым объемы складских запасов изделий всех видов и окрасок максимальны. В этом случае минимизируется продолжительность интервала времени между получением заказа от потребителя и его выполнением. 3.Руководитель фирмы отдает предпочтение проекту, в соответствии с которым объемы складских запасов минимальны, с тем чтобы уменьшить капитальные издержки на хранение изделий. Нетрудно видеть, что эти критерии не могут быть реализованы при оптимизации одновременно. Приемлемым компромиссом является выбор в качестве первичного характеристического показателя качества функционирования системы минимума суммарных затрат в единицу времени с последующим учетом необходимых вторичных условий. К их числу можно отнести поддержание объемов складских запасов изделий всех видов в заранее установленных границах, а также ограничение количества изменений в ассортименте изделий и используемых красок в течение недели. Независимые переменные На третьем основном этапе постановки задачи оптимизации осуществляется выбор независимых переменных, которые должны адекватно описывать допустимые проекты или условия функционирования системы. В процессе выбора независимых переменных следует принять во внимание ряд важных обстоятельств Во-первых, необходимо провести различие между переменными, значения которых могут изменяться в достаточно широком диапазоне, и переменными, значения которых фиксированы и определяются внешними факторами. Так, в примере с красильным цехом виды изделий и сорта применяемых красок зафиксированы технологическими спецификациями или заказами потребителей, т. е. относятся к числу параметров системы. С другой стороны, порядок окраски изделий в различные цвета с учетом ограничений, накладываемых на количество видов изделий и объемы складских запасов, представляется независимой переменной, значения которой могут варьироваться при заданной производственной программе. Далее важно провести различие между теми параметрами системы, которые могут предполагаться постоянными, и параметрами, которые подвержены флуктуациям вследствие воздействия внешних или неконтролируемых факторов. В частности, в примере с красильным цехом поломки оборудования и прогулы рабочих могут оказать весьма заметное влияние на процесс производства в цехе. Ясно, что существенные изменения этих важных параметров системы должны быть приняты во внимание при постановке задачи производственного планирования, если требуется, чтобы составленный оптимальный план был реалистичным и выполнимым. Во-вторых, при постановке задачи следует учитывать все основные переменные, которые влияют на функционирование системы или качество проекта. Например, если при проектировании газохранилища рассматривать высоту, диаметр и толщину стенок цилиндрического газгольдера как независимые переменные, но исключить возможность использования компрессора для повышения рабочего давления, то получится проект весьма низкого качества. Для выбранной и фиксированной величины давления, разумеется, можно определить размеры газгольдера, обеспечивающие его наименьшую стоимость. Однако если включить в число независимых переменных давление, при котором хранится газ, и ввести в характеристический критерий стоимость компрессора, то можно получить проект, реализация которого требует меньших полных затрат из-за уменьшения необходимого объема газгольдера. Следовательно, независимые переменные должны выбираться таким образом, чтобы все важнейшие технико-экономические решения нашли отражение в формулировке задачи. Исключение возможных альтернатив в общем случае приводит к получению субоптимальных решений. В третьих, еще одним существенным фактором, влияющим на выбор переменных, является уровень детализации при исследовании системы. Очень важно ввести в рассмотрение все основные независимые переменные, но не менее важно не «перегружать» задачу большим количеством мелких, несущественных деталей. При выборе независимых переменных целесообразно руководствоваться правилом, согласно которому следует рассматривать только те переменные, которые оказывают существенное влияние на характеристический критерий, выбранный для анализа сложной системы. Модель системы После того как характеристический критерий и независимые переменные выбраны, на следующем этапе постановки задачи необходимо построить модель, которая описывает взаимосвязи между переменными задачи и отражает влияние независимых переменных на степень достижения цели, определяемой характеристическим критерием. В принципе оптимизационное исследование можно провести на основе непосредственного экспериментирования с системой. Для этого следует зафиксировать значения независимых внутрисистемных переменных, реализовать процедуру наблюдения за функционированием системы в этих условиях и оценить значение характеристического показателя качества функционирования системы, исходя из зарегистрированных характеристик. Затем с помощью оптимизационных методов можно скорректировать значения независимых переменных и продолжить серию экспериментов. Однако на практике оптимизационные исследования проводятся, как правило, на основе упрощенного математического представления системы, которое носит название модели, которая включает основные уравнения материальных и энергетических балансов, соотношения, связанные с проектными решениями, а также уравнения, описывающие физические процессы, протекающие в системе. Эти уравнения обычно дополняются неравенствами, определяющими область допустимых значений независимых переменных и позволяющими определить требования, накладываемые на верхние или нижние границы изменения характеристик функционирования системы. Из вышеизложенного следует, что задача в виде, пригодном для применения оптимизационных методов, объединяет характеристическую меру, множество независимых переменных и модель, отражающую взаимосвязь переменных. Поскольку требования, предъявляемые к оптимизационным задачам, являются весьма общими и носят абстрактный характер, область приложения методов оптимизации может быть достаточно широкой. Действительно, эти методы находят применение при решении самых различных задач науки и техники, включая задачи оптимального проектирования структурных элементов систем и процессов, планирования стратегий капитальных вложений, компоновки сетей складских помещений, определения оптимальных маршрутов движения грузового транспорта, планирования в здравоохранении, проектирования механических узлов и ряд других задач. Применение методов оптимизации в инженерной практике Теория оптимизации находит эффективное применение во всех направлениях инженерной деятельности, и в первую очередь в следующих четырех ее областях: 1) проектирование систем и их составных частей; 2) планирование и анализ функционирования существующих систем; 3)инженерный анализ и обработка информации; 4)управление динамическими системами. В данном разделе кратко рассматриваются типичные приложения методов оптимизации в каждой из первых трех перечисленных областей. Такая важная область инженерной деятельности, как управление динамическими системами, также допускает применение методов оптимизации, однако анализ соответствующих примеров требует специальной подготовки. Использование методов оптимизации при проектировании Сфера применения оптимизационных методов в инженерном проектировании достаточно широка: от проектирования отдельных структурных элементов технических систем до проектирования узлов оборудования и составления предварительных проектов промышленных предприятий в целом. Для того чтобы использовать методы оптимизации, необходимо разработать «принципиальную схему» функционирования системы или выявить ее структуру; тогда задача оптимизации сводится к выбору таких значений переменных, характеризующих размеры отдельных устройств и режимы их работы, которым соответствует наилучшее значение характеристического показателя качества функционирования системы. Пример 1. Проектирование системы снабжения кислородом Описание задачи. Кислородный конвертер, используемый в производстве стали, представляет собой химический реактор периодического действия, который потребляет чистый кислород. Процесс функционирования конвертера — циклический. Руда и флюс загружаются в реактор, взаимодействуют в течение определенного периода времени, а затем продукты взаимодействия выводятся наружу. Этот циклический процесс связан с периодическими изменениями скорости потребления кислорода. Как показано на рис. 1.2, каждый цикл состоит из временного интервала длины t1 на котором расход кислорода в единицу времени невелик и равен D0 и временного интервала (t2—t1), которому соответствует высокая скорость потребления D1. Используемый в конвертере кислород производится на специальной установке в соответствии с распространенным технологическим способом, который позволяет получать кислород из воздуха путем охлаждения и дистилляции. Кислородные установки отличаются высоким уровнем автоматизации и, как правило, имеют постоянную производительность. Для того чтобы соединить непрерывно действующую кислородную установку с циклически функционирующим конвертером, необходимо разработать проект простой системы управления запасами (рис. 1.3), состоящей из компрессора б резервуара для хранения кислорода. Рис. 1.3. Проект системы снабжения кислородом, пример 1.1. Рассмотрим возможные проекты. В самом простом случае производительность кислородной установки можно выбрать равной D1, наибольшей скорости потребления кислорода. В течение интервала времени, которому соответствует низкий расход кислорода, излишек газа придется выпускать в атмосферу. С другой стороны, можно выбрать кислородную установку с такой производительностью, которая позволила бы в течение одного цикла получать количество кислорода, требуемое для обеспечения нормальной работы конвертера. В интервале времени, когда расход газа невелик, излишек кислорода под давлением накапливался бы в резервуаре для последующего использования в течение интервала времени, которому соответствует высокая скорость потребления. Все промежуточные проекты отличаются от рассмотренных различными сочетаниями запасов и потерь кислорода. Задача заключается в том, чтобы выбрать оптимальный проект. Постановка задачи. Изучаемая система состоит из установки для производства кислорода, компрессора и резервуара для хранения газа. Характеристики кислородного конвертера и цикла потребления кислорода предполагаются заданными, так как определяются внешними по отношению к системе факторами. Характеристический показатель качества проекта естественно выбрать в виде полных затрат в единицу времени, которые включают затраты на производство кислорода (постоянные и переменные), затраты на эксплуатацию компрессора, а также постоянные издержки, связанные с приобретением компрессора и резервуара для хранения кислорода. В примере 1 представлена постановка задачи предварительной: проектирования системы, состоящей из нескольких агрегатов. Следующий пример иллюстрирует процесс проектирования отдельного структурного элемента системы.   зически невозможно сделать сварной шов, ширина которого меньше некоторого порогового значения. 2. Использование методов оптимизации при планировании и анализе функционирования систем Вторая важнейшая область применения оптимизационных методов в инженерной практике связана с совершенствованием существующих систем и разработкой производственных планов для многопродуктовых технико-экономических процессов. Задачи анализа функционирования систем обычно возникают в тех случаях, когда требуется адаптировать существующую производственную систему к новым условиям функционирования, отличным от тех условий, которые были предусмотрены проектом этой системы. Причины, порождающие требования такого рода, как правило, связаны с необходимостью 1)увеличения общего объема выпуска продукции; 2)использования других видов сырья и расширения ассортимента изделий; 3)совершенствования технологических операций, отличающихся низким уровнем проектных решений. В связи с решением указанных задач требуется выбрать новый температурный режим, давление или характеристики потока; установить дополнительное оборудование; разработать новые технологические операции. Методы оптимизации в производственном планировании ориентированы главным образом на составление программ производства нескольких видов продукции на отдельном предприятии, а также на координирование производственных планов предприятий, которые связаны хозяйственными отношениями. Поскольку в таких приложениях предполагается, что основное оборудование установлено и функционирует, предметом исследования являются только функции переменных затрат. Возникающие при этом задачи чаще всего можно сформулировать с помощью линейных и квазилинейных моделей. В качестве иллюстрации этого класса приложений оптимизационных методов рассмотрим задачу планирования производства нефтепродуктов. Пример 3. Планирование производства нефтепродуктов Описание задачи. В процессе переработки сырой нефти производится определенное количество бензиновых полупродуктов, которые затем последовательно смешиваются с целью получения двух видов топлива для двигателей внутреннего сгорания — обычного топлива и топлива высшего качества. Для каждого полупродукта известны значение показателя его эффективности, максимальный выход и фиксированная цена единицы объема полупродукта. Для каждого вида топлива установлены минимальное значение показателя эффективности и продажная цена, а также известны удельные затраты на смешивание топлива. Минимальный уровень производства обоих видов топлива определяется договорными обязательствами. Остальное произведенное топливо и неиспользованные полупродукты могут быть реализованы посредством свободной продажи по известным ценам. Требуется составить оптимальный план производства топлива в течение заданного периода времени. Постановка задачи. На схеме, изображенной на рис. 1.5, показано что исследуемая система включает ряд бензиновых полупродуктов, технологическую операцию смешивания и два вида жидкого моторного топлива. Процессы переработки нефти и производства полупродуктов исключены из рассмотрения наряду с подсистемами управления запасами и распределения сырой нефти, полупродуктов и конечной продукции. Поскольку оборудование, необходимое для выполнения операции смешивания, к началу планового периода установлено и функционирует, следует рассмотреть только стоимостные характеристики производственного процесса. Характеристическим показателем качества функционирования системы в данном случае является чистая прибыль, реализуемая в течение планового периода. Чистая прибыль состоит из дохода от продажи топлива и полупродуктов за вычетом затрат на смешивание и производство полупродуктов. Независимые переменные выражают величины потоков по ориентированным дугам, изображенным на рис. 1.5. Таким образом, с каждым из полупродуктов ассоциированы три переменные. Одна из переменных выражает количество полупродукта, направляемого на производство обычного топлива, вторая — количество полупродукта, направляемого на производство топлива высшего качества, и третья — количество полупродукта, поступающего в свободную продажу. 3. Использование методов оптимизации для анализа и обработки информации Еще одна широкая область применения оптимизационных методов в инженерной практике связана с задачами инженерного анализа, в частности с задачами нелинейного регрессионного анализа. Среди наиболее общих проблем, возникающих в процессе разработки инженерных моделей, можно выделить проблему определения параметров некоторой полуэмпирической модели на основе заданного множества экспериментальных данных. Такого рода задачи обработки информации, или задачи регрессионного анализа, путем несложных преобразований приводятся к виду оптимизационных задач, поскольку выбор значений параметров модели осуществляется в соответствии с критерием качества описания имеющихся данных с помощью этой модели. Предположим, что некоторая переменная у зависит от некоторой независимой переменной х, а связь между ними задается равенством y=f(x, Θ1,Θ2), в котором фигурируют два параметра Θ1 и Θ2. Для того чтобы определить соответствующие значения Θ1 и Θ2, необходимо провести серию экспериментов, в каждом из которых задается значение независимой переменной х и регистрируется значение зависимой переменной у. Результатом серии из N экспериментов является множество пар чисел (yi, xi), i = 1…N. Затем на основе полученной информации делается попытка подобрать значения Θ1 и Θ2 таким образом, чтобы обеспечить хорошую точность описания экспериментальных данных с помощью функции f. Наиболее часто используемая на практике мера качества описания экспериментальных данных определяется так называемым критерием наименьших квадратов, в соответствии с которым требуется минимизировать функцию Разность yi—f(xi ,Θ1,Θ2) между зарегистрированным значением yi и теоретическим значением f(x, Θ1,Θ2) показывает, насколько точно выбранная модель описывает имеющиеся данные, и называется остатком. Сумма квадратов остатков по всем экспериментальным точкам является мерой точности описания данных. Действительно, если значение L(Θ1,Θ2) равно нулю, то сделанный выбор Θ1 и Θ2 обеспечивает точное описание, поскольку экспериментальные данные совпадают с теоретической кривой. Таким образом, задачу описания данных можно рассматривать как задачу оптимизации, в которой требуется найти значения параметров Θ1 и Θ2 минимизирующие функцию L(Θ1,Θ2). Пример 4. Нелинейная регрессия Описание задачи. Известно, что соотношение между давлением, молярным объемом и температурой реальных газов отличается от аналогичного соотношения для идеального газа, которое записывается в виде P*v= R*Т, где Р — давление (атм), v — молярный объем (см3/г*моль); Т — температура (К), R — универсальная газовая постоянная (82,06 атм*см3/г*моль*К). Полуэмпирическое уравнение Редлиха — Куонга ориентировано на то, чтобы скомпенсировать отклонение свойств реального газа от свойств идеального газа, и содержит параметры а и b, значения которых определяются на основе экспериментальных данных. Постановка задачи. Найти значения параметров а и в, минимизирующих сумму квадратов остатков. В данном случае эта функция имеет следующий вид: где Рi— результат измерения давления в эксперименте с номером I, а остальные два слагаемых в скобках представляют соответствующие члены уравнения в условиях эксперимента с номером i и зависят от параметров а и b. Кроме задач регрессионного анализа в инженерной практике возникает множество других задач, которые можно формулировать и решать как задачи оптимизации. Отметим ставший классическим подход к определению равновесного состава химической смеси. Известно, что равновесным состоянием замкнутой системы, начальное состояние которой задано, при фиксированной температуре и фиксированном давлении является такое состояние, при котором свободная энергия Гиббса принимает минимальное значение. Показано, что задача определения равновесного состава смеси может быть сформулирована как задача минимизации нелинейной функции при ограничениях, образованных системой линейных уравнений вместе с условиями неотрицательности переменных. Другая классическая инженерная задача, которую можно сформулировать и решить как задачу оптимизации, связана с определением величин установившихся токов в электрической цепи, составленной из активных сопротивлений. Если известны величины сопротивлений и полный ток в цепи, то значения токов через сопротивления можно определить путем решения задачи минимизации полной потери мощности в цепи с учетом линейных ограничений, которые обеспечивают выполнение закона Кирхгофа для каждого узла цепи. Вопросы. 1.Необходимые применения оптимизационных методов. 2.Какие критерии возможны при решении оптимизационных задачах. 3.Сколько критериев может быть у оптимизационной задачи. 4.Что делают, если критериев оптимизации несколько. 5.Что нужно учитывать при выборе независимых переменных. 6.Где применяются методы оптимизации в инженерной практике.