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

А.И. Данилин

Основы теории оптимизации

(постановки задач)

 

 

Электронное учебное пособие

САМАРА

УДК 51.380.115

ББК 22.18

Д 182

 

 

Данилин А. И., Основы теории оптимизации (постановки задач) [Электронный ресурс]: электрон.учеб. пособие / А. И. Данилин; Минобрнауки России, Самар. гос. аэрокосм. ун-т им. С. П. Королева (нац. исслед. ун-т). - Электрон. текстовые и граф. дан. (1,2 MБайт). - Самара, 2011. - 1 эл. опт. диск (CD-ROM).

 

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

 

Учебное пособие предназначено для студентов факультета инженеров воздушного транспорта, обучающихся по направлению подготовки магистров специальностей 162300.68 "Техническая эксплуатация летательных аппаратов и двигателей" и 162500.68 «Техническая эксплуатация авиационных электросистем и пилотажно-навигационных комплексов», дисциплина «Методы оптимизации», семестр 9.

Разработано на кафедре эксплуатации авиационной техники.

 

 

© Самарский государственный

аэрокосмический университет, 2011

Введение.

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

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

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

 

	Воздействие на вход
Законы природы	Система или изделие
	Выход
Дано	Найти	Название процесса
Система или изделие, воздействие на вход, законы природы	Выход	Анализ (прогнозирование и/или расчёт характеристик, поведения, последствий… во всех сферах деятельности)
Система или изделие, выход, законы природы	Воздействие на вход	Инверсный анализ (медицина, театр, расследование происшествий, планирование деятельности…)
Система или изделие, воздействие на вход, выход	Законы природы	Научные исследования
Воздействие на ход, выход, законы природы	Систему или изделие	Инженерное проектирование

 

Инженерное проектирование является на сегодняшний день интеллектуально самым трудным видом деятельности вне зависимости от объекта проектирования. В названии деятельности термин «инженерный» используется в его изначальном смысле, а именно: ingenium в переводе с латыни означает изобретение; то есть, «инженерный» означает «творческий, с элементами изобретательства», а инженер – это изобретатель. Равно как и термин «проект» происходит от латинского proectus – брошенный вперед; то есть, проект – это нечто такое, чего раньше не существовало.

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

1. Проектирование – это принятие решения в условиях неопределённости с тяжелыми последствиями в случае ошибки;- автор: Азимов.

2. Проектирование – это приведение изделия (системы) в соответствие с обстановкой при максимальном учёте всех требований; - автор: Грегори.

3. Проектирование – это вдохновенный прыжок от фактов настоящего к возможностям будущего; - автор: Пейдж.

4. Проектирование – это использование научных принципов, технической информации и воображения для определения … структуры машины или системы, предназначенной для выполнения заранее заданных функций с наибольшей экономичностью и эффективностью; - автор: Филден.

Эти определения неявно предполагают три вещи.

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

2. Эти функции невозможно удовлетворительно решить с помощью уже существующих технических объектов или систем.

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

На рис. 1 показаны этапы создания новой системы.

 

 

Уяснение цели

Формирование идеи

Инженерный анализ и оптимизация

Конкретизация решения

Строительство, ввод в действие

 

Рис. 1. Этапы создания системы или изделия

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

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

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

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

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

Термин "оптимальный " сильно перегружен смысловым наполнением. В переводе с латинского он означает "наилучший" и корнями уходит к богине Опе - богине плодородия и урожая у древнеиталийского племени сабинов [1]. Впоследствии богиня Опа стала женой бога времени Сатурна и матерью Юпитера. Она изображается держащей в одной руке рог изобилия мифических благ, а в другой весы, символизирующие измерение и принятие решения.

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

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

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

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

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

Название «математическое программирование» предложено Робертом Дорфманом приблизительно в 1950г.; теперь оно объединяет линейное программирование, целочисленное программирование, динамическое программирование, выпуклое программирование, нелинейное программирование и программирование при наличии неопределенности. Причём «программирование» здесь не имеет ничего общего с реальным написанием кода программ, а должно читаться по сути своего содержания как «методы оптимизации».

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

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

При решении любой организационной или технической задачи её сначала необходимо сформулировать, то есть ответить на вопросы: 1) С чем мы имеем дело? Каковы функции системы, каковы её связи с внешним окружением? 2) Чего мы хотим? Что нужно сделать, или как нужно сделать? 3) Каковы наши возможности? Какие у нас есть ресурсы для исполнения наших желаний?

Именно здесь совершается много ошибок. Как точно заметил Джон Дьюи: «Хорошо поставленная задача уже наполовину решена». Задача, сведённая к конкретным вопросам, позволяет выразить получаемое решение через величины, которые можно затем вычислить или измерить. Другими словами, нужно ставить такие вопросы, на которые можно получить количественный ответ. Недостаточно ставить вопросы типа: Будет ли самолёт экономичным? Будет ли конструкция работать? Такие вопросы не являются конкретными. Вместо этого нужно ставить вопросы иного характера. Какова будет стоимость тонно-километра при перевозке 30 пассажиров на дальность 1000 км при рейсовой скорости 450 км/час? Какие напряжения возникнут в элементах конструкции при нагрузке 80 кН и нагреве до 300⁰С? Для подготовки таких вопросов, то есть для определения задачи необходимо чёткое понимание реальной физической ситуации и умение рассуждать. Формулировке задачи обычно мешают избыточные условия, которые делают технические задачи неимоверно сложными. И здесь огромную помощь оказывает определение задачи в терминах математического программирования. Согласно ей, при постановке задачи математического программирования необходимо выполнить следующие работы: 1) выбрать функцию цели; 2) выбрать проектные переменные; 3) записать ограничения.

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

Функция цели.

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

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

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

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

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

3. Руководитель аэропорта отдаст предпочтение проекту, в соответствии с которым объемы складских запасов минимальны, с тем, чтобы уменьшить капитальные издержки на хранение изделий.

Нетрудно видеть, что эти критерии при оптимизации не могут быть реализованы одновременно.

Здесь мы подошли к вопросу: как быть, если к проекту предъявляются минимаксные требования по многим критериям? Подробные и предельно чёткие ответы на этот вопрос можно найти в книге Д.И.Батищева [2], но из всех рекомендаций по построению единственной функции цели отметим два подхода, чтобы проиллюстрировать общее направление мыслей.

1. Метод взвешенных сумм. Функция цели имеет вид: , где - частные критерии качества; λ_k – весовые коэффициенты, показывающие важность отдельного критерия в общей оценке качества проекта.

2. Оценка по потерям. Функция цели имеет вид: . Здесь - минимальное или максимальное значение частного критерия качества.

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

Проектные переменные.

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

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

Например, при модификации самолёта было принято решение изменить аэродинамический профиль крыла. Какой профиль выбрать по критерию максимального аэродинамического качества?

Можно обратиться к доступному сортаменту профилей и выбрать какой-либо профиль из них. А может быть есть другие профили? Конечно, есть и вопрос об оптимальности принятого решения не закрыт.

Попытаемся ввести более универсальные проектные переменные. Для этого выберем в качестве проектных переменных координаты конечного множества точек в какой-либо системе координат ξη и будем считать, что профиль представляет собой замкнутую линию, проведённую через эти точки, см. рис. 2. Нетрудно видеть, что различным определённым значениям этих проектных переменных могут соответствовать любые профили из любых сортаментов и множество новых.

Рис. 2. Задание профиля крыла.

Рис. 3. Двухсвязная область

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

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

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

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

Запись ограничений.

Ограничения бывают двух типов. Во-первых, это ограничения на диапазон изменения самих проектных переменных: a_i ≤ x _i≤ b_i, i=1,2,..n. Такие ограничения называются геометрическими. Например, толщина обшивки может быть ограничена конструктивно: δ_min ≤ δ _i≤ δ_max.

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

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

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

Функциональные и геометрические ограничения могут привести к следующим ситуациям.

1. Допустимая область проектных решений является пустой.

2. Допустимая область проектных решений содержит единственную точку.

3. Допустимая область содержит множество проектных решений.

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

Построение модели.

Модель является непременным атрибутом оптимизации, поскольку она связывает проектные переменные, характеристики проектируемого объекта и сам объект в процессе функционирования.

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

Рис. 4. Построение модели объекта.

К математическим моделям предъявляются следующие требования.

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

2. Точность модели – согласованность расчётных данных с натурным экспериментом.

3. Быстродействие модели – возможность получения расчётных данных за приемлемое, обычно заданное, календарное время.

4. Работоспособность во всём диапазоне изменения проектных переменных.

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

Принятие допущений.

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

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

Серьёзную опасность представляет принятие допущений без должного их понимания. Это недопустимо, поскольку инженер в этом случае не видит границ применимости своей модели. Всегда, начиная и заканчивая анализ, необходимо знать о принятых допущениях, включая скрытые допущения, которые прячутся, как правило, в формулах и методиках, взятых из справочной литературы. Технические справочники набиты формулами и методиками, но они не сообщают, при каких допущениях получены формулы, какие факторы учтены при их выводе, каковы границы их применимости. К примеру, если построить модель расчёта переходных процессов в полупроводниковых системах и забыть, что она верна только при определённых напряжениях и токах, то можно подать на вход такой модели напряжение 30 000 В и она сосчитает все переходные процессы, а также построит их графики. Что же будет в реальности? Легкий дымок и всё…