Исследование операций : безусловная оптимизация

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

№ 1378 

Кафедра инженерной кибернетики 

Н.И. Бунькина 
 
 

Исследование операций 

Безусловная оптимизация 

Курс лекций 

Рекомендовано редакционно-издательским 
советом университета 

Москва     Издательский Дом МИСиС     2009 

УДК 519.8 
 
Б91 

Р е ц е н з е н т  
д-р техн. наук, проф. Н.Н. Зиятдинов (КГТУ) 

Бунькина Н.И. 
Б91  
Исследование операций: Безусловная оптимизация: Курс 
лекций. – М.: Изд. Дом МИСиС, 2009. – 65 с. 
ISBN 978-5-87623-260-1 

Изложены основные методы решения задач безусловной оптимизации. 
Рассмотрены методы одномерной оптимизации: методы прямого поиска и 
методы с использованием производной; методы многомерной оптимизации: 
методы нулевого порядка и градиентные методы. Курс лекций основан на 
материалах, которые читались студентам специальности «Прикладная математика» на протяжении четырех лет в рамках дисциплины «Исследование 
операций». 
Предназначен для студентов, обучающихся по специальности «Прикладная математика», и может быть полезен студентам специальности «Стандартизация и сертификация» и магистрам направления «Менеджмент», а также 
может быть использован студентами других технических специальностей, 
изучающими прикладные аспекты применения методов оптимизации. 
 

УДК 519.8 

ISBN 978-5-87623-260-1 
© Национальный исследовательский 
технологический университет 
«МИСиС», 2009 

ОГЛАВЛЕНИЕ 

Введение....................................................................................................4 
Предмет и задачи курса «Исследование операций»..........................4 
Необходимые условия для применения оптимизационных 
методов ..................................................................................................5 
Структура оптимизационных задач....................................................8 
Контрольные вопросы........................................................................11 
1. Методы безусловной оптимизации функции одной переменной 
(одномерная оптимизация) ....................................................................13 
1.1. Методы прямого поиска (нулевого порядка)............................13 
1.2. Методы с использованием производных ..................................23 
Контрольные вопросы........................................................................33 
2. Методы безусловной оптимизации функции нескольких 
переменных (многомерная оптимизация) ............................................34 
2.1. Математическая модель..............................................................34 
2.2. Методы прямого поиска (нулевого порядка)............................37 
2.3. Градиентные методы...................................................................45 
Контрольные вопросы........................................................................62 
Библиографический список...................................................................64 
 

ВВЕДЕНИЕ 

Предмет и задачи курса 
«Исследование операций» 

Изучив данный раздел, вы узнаете, что представляет собой курс 
«Исследование операций», почему важной его частью является курс 
«Методы оптимизации», какие вопросы рассматриваются в данном 
курсе и почему его изучение важно для аналитической и практической деятельности инженера-математика. В этой книге рассмотрены 
методы безусловной оптимизации. 
Рассмотрев приведенные в данном разделе теоретические выкладки, вы познакомитесь с основными терминами и понятиями, необходимыми для понимания данного курса, условиями, при которых 
формируются модели задач оптимизации, а также со структурой оптимизационных задач. 
Теория оптимизации представляет собой совокупность фундаментальных математических исследований, ориентированных на нахождение и идентификацию наилучших решений из множества альтернатив и позволяющих избежать полного перебора и оценивания возможных вариантов. 
Математические методы оптимизации находят практическое применение в самых разных областях человеческой деятельности, прежде всего в экономике и промышленности. В процессе деятельности 
любого объекта всегда возникает потребность найти те условия, при 
которых объект будет функционировать наилучшим образом, позволяя добиться максимальных результатов, определяющих эффективность его деятельности. Под объектом здесь может пониматься предприятие, производящее продукцию, или торговый центр; финансовое 
инвестиционное учреждение или строительная организация.  
В методах оптимизации используются теория матриц, элементы 
линейной алгебры и дифференциального исчисления, положения математического анализа. Для того чтобы решать задачи оптимизации, 
были разработаны специальные пакеты. Прежде всего – это Mathlab 
и Мathcad, а также пакеты «Линейное программирование» и «Математическое программирование». Встроенный в Microsoft Office Excel 
7.0 также позволяет находить решение некоторых задач оптимизации 
небольшой размерности. 

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

Необходимые условия для применения 
оптимизационных методов 

Для того, чтобы использовать математические результаты и численные методы теории оптимизации для решения конкретных экономических и инженерных задач, необходимо: 
• определить систему, в которой нужно найти наилучший вариант; 
• установить границы рассматриваемой системы; 
• определить количественный критерий, на основе которого можно произвести анализ вариантов с целью выявления «наилучшего»; 
• осуществить выбор внутрисистемных переменных, которые 
используются для определения характеристик и идентификации вариантов; 
• построить модель, отражающую взаимосвязи между переменными. 
Эта последовательность действий составляет процесс постановки 
математической модели задачи оптимизации. Прежде чем приступить к оптимизационному исследованию, необходимо четко понять, 
какой именно объект нуждается в поиске оптимального решения. 
Если речь идет об экономическом состоянии предприятия, то в качестве определяющей системы будет выступать такое производство, 
при котором достигаются наилучшие экономические результаты. Если речь идет о прокладке новой дороги между населенными пунктами, то определяющим будет выбор такой траектории, которая позволит соединить эти населенные пункты с наименьшими затратами.  

Также важно определить границы изучаемой системы. В данном 
контексте система представляет собой некоторую изолированную 
часть реального мира. При проведении анализа предполагается, что 
взаимосвязи между системой и внешней средой зафиксированы на 
некотором выбранном уровне представления. Совокупность условий, 
при которых осуществляется поиск оптимума целевой функции, выраженных в виде аналитических зависимостей, называется системой 
ограничений оптимизационной задачи. 
Предположим, что торговому предприятию необходимо определить оптимальную партию закупаемого товара. На первом этапе для 
решения этой задачи достаточно знать объем складского помещения 
и скорость реализации товара, т.е. ограничиться системой склад – 
торговля. Однако в реальности необходимо учитывать стоимость и 
ритмичность доставки товара, а также прогноз маркетинговых изменений на потребительском рынке, т.е. расширить границы системы, 
введя в нее новые зависимости. Разумеется, расширение границ повышает размерность и сложность системы, что, в свою очередь, затрудняет ее анализ.  
Стремление учесть все факторы часто приводит к тому, что найти 
оптимальное решение оказывается невозможным. Компромисс между упрощением реальной ситуации, когда границы системы оказываются слишком жесткими, и построением громоздкой многокомпонентной системы, учитывающей максимальное число факторов, и 
является искусством построения математической модели. Значительную помощь здесь оказывает декомпозиция – процесс разбиения 
большой сложной системы на небольшие подсистемы, которые можно изучать по отдельности. 
На следующем этапе постановки задачи оптимизации необходимо 
осуществить выбор критерия, на основе которого можно оценить характеристики системы, чтобы выявить «наилучшие» условия функционирования системы. Обычно выбираются критерии экономического характера такие, как валовые капитальные затраты, издержки в 
единицу времени, чистая прибыль, доходы от инвестиций, себестоимость выпускаемой продукции. В других приложениях критерий 
может основываться на некоторых технологических факторах: минимизации продолжительности процесса производства, минимизации потребляемой энергии, максимизации качества выпускаемой 
продукции. 
Независимо от того, какой критерий выбран, «наилучшему» варианту всегда соответствует минимальное или максимальное значение 

показателя качества функционирования объекта. В задачах оптимизации критерий эффективности называется целевой функцией. 
Необходимо отметить, что оценить эффективность системы не 
всегда удается, определяя только один критерий оптимизации. Задачи, в которых необходимо учитывать несколько критериев, называются многокритериальными, или многоцелевыми, или векторными 
задачами оптимизации и относятся к теории многокритериальной 
(многоцелевой, векторной) оптимизации. В реальной ситуации принятие решения всегда сопровождается поиском компромисса в совокупности противоречивых целевых установок. Одним из способов 
учета этих целей является то, что какой-либо из критериев используется при оптимизации как целевая функция, а вторичные критерии 
порождают ограничения оптимизационной задачи. 
Рассмотрим пример. Пусть производственное предприятие выпускает несколько видов промышленных товаров. С точки зрения 
руководителя отдела сбыта, наилучшим функционированием предприятия будет такое, которое обеспечит прогноз потребительского 
рынка в текущем периоде. Управляющий цехом будет считать оптимальным такое производство, которое обеспечит отсутствие очередей у уникальных станков и недогрузку оборудования, что уже входит в противоречие с первым критерием. Руководитель предприятия 
наилучшим результатом будет считать снижение себестоимости продукции, что также может не совпадать с предыдущими критериями. 
Приемлемым компромиссом является выбор в качестве критерия минимизации показателя суммарных затрат в единицу времени с последующим учетом остальных требований в виде ограничений задачи. В 
данном курсе мы не будем рассматривать многокритериальные задачи и ограничимся всегда только одним критерием.  
На следующем этапе постановки задачи осуществляется выбор 
независимых переменных, которые должны адекватно описывать 
условия функционирования системы. В процессе выбора независимых переменных следует принять во внимание ряд важных обстоятельств. 
1. Необходимо провести различие между переменными, значения 
которых могут изменяться в широком диапазоне, и переменными, 
значения которых фиксированы и определяются внешними факторами. Например, для сборочного цеха детали, из которых собирается 
изделие, являются фиксированными переменными, а объемы складских запасов деталей для сборки являются независимыми перемен