Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 752905.01.99
Доступ онлайн
2 000 ₽
В корзину
Изложены основные методы решения задач безусловной оптимизации. Рассмотрены методы одномерной оптимизации: методы прямого поиска и методы с использованием производной, методы многомерной оптимизации: методы нулевого порядка и градиентные методы. Курс лекций основан на материалах, которые читались студентам специальности «Прикладная математика» на протяжении четырех лет в рамках дисциплины «Исследование операций». Предназначен для студентов, обучающихся по специальности «Прикладная математика», и может быть полезен студентам специальности «Стандартизация и сертификация» и магистрам направления «Менеджмент», а также может быть использован студентами др.угих технических специальностей, изучающими прикладные аспекты применения методов оптимизации.
Бунькина, Н. И. Исследование операций : безусловная оптимизация : курс лекций / Н. И. Бунькина. - Москва : Изд. Дом МИСиС, 2009. - 65 с. - ISBN 978-5-87623-260-1. - Текст : электронный. - URL: https://znanium.com/catalog/product/1231388 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

№ 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. Необходимо провести различие между переменными, значения 
которых могут изменяться в широком диапазоне, и переменными, 
значения которых фиксированы и определяются внешними факторами. Например, для сборочного цеха детали, из которых собирается 
изделие, являются фиксированными переменными, а объемы складских запасов деталей для сборки являются независимыми перемен
ными, значения которых могут варьироваться при заданной производственной программе. 
2. Важно провести различие между теми параметрами системы, которые остаются постоянными, и теми, которые подвержены воздействию внешних или случайных факторов. Например, расстояние от склада 
до торгового зала – величина известная и постоянная, в то время как 
спрос на отдельные виды продукции и производительность труда – величины, зависящие от множества факторов, в том числе и плохо формализуемых. Показатели, которые являются постоянными в процессе решения оптимизационной задачи, называются параметрами модели. 
3. Независимые переменные должны выбираться таким образом, 
чтобы все важнейшие технико-экономические показатели нашли отражение в формулировке задачи. Например, если в задаче максимизации выпуска продукции учитывать время работы, парк оборудования, стоимость материалов и комплектующих, производственные 
площади, людские ресурсы, но при этом отбросить такие важные 
внешние факторы, как прогноз спроса и наличие конкурентов, то полученная постановка задачи будет неадекватна реальной ситуации. В 
задачах оптимизации независимые переменные называются искомыми переменными.  
Последний этап заключается в построении модели, которая описывает взаимосвязи между искомыми переменными задачи и отражает влияние независимых переменных на степень достижения цели, 
определяемой целевой функцией. 

Структура оптимизационных задач 

Все задачи оптимизации можно классифицировать как задачи нахождения максимума или минимума вещественной функции f(x), nмерного векторного аргумента x = (x1, x2, ... , xn), компоненты которого могут удовлетворять системе уравнений Нk(х) = 0, набору неравенств Gj(х) ≥ 0, а также могут быть ограничены сверху и снизу, т.е. 

u
l

j
j
j
X
X
X
≥
≥
. В последующем функцию f(x) будем называть целевой 

функцией, уравнения Нk(х) = 0 – ограничениями в виде равенств, а 
неравенства: Gj(х) ≥ 0 – ограничениями в виде неравенств. При этом 
предполагается, что все фигурирующие в задаче функции принимают действительные значения, а число ограничений конечно.  
Задача оптимизации, представленная в следующем виде: 

 
найти (max (min) f(x)) 
(В1) 

при ограничениях 

 

( )
0,
1, 2, ...,
;

( )
0,
1, 2, ...,
;

,
1, 2, ..., ,

k

j

u
l
i
i
i

H
x
k
K

G
x
j
J

X
X
X
i
I

=
=

≥
=

≥
≥
=

 
(В2) 

называется задачей оптимизации с ограничениями, или задачей условной оптимизации. 
Задачи, поиск оптимума в которых осуществляется без условий, 
описываемых ограничениями (В.2), называются задачами безусловной оптимизации. Если х представляет собой одномерный вектор, то 
такие задачи называются задачами одномерной оптимизации или задачами оптимизации функции одной переменной, и составляют простейший, но важный подкласс оптимизационных задач. Если х представляет собой многомерный вектор, то такие задачи называются 
задачами многомерной оптимизации или задачами оптимизации 
функции нескольких переменных. 
Задачи оптимизации можно классифицировать в соответствии с 
видом функций f(x), Нk(х), Gj(х) и размерностью вектора х. Задачи 
условной оптимизации, в которых функции Нk(х), Gj(х) являются линейными, носят название задач с линейными ограничениями. В таких 
задачах целевая функция может быть линейной или нелинейной. Задачи, которые содержат только линейные функции, называются задачами линейного программирования. Если на искомую переменную 
накладывается условие целочисленности, то такие задачи называются задачами целочисленной, или дискретной, оптимизации. 
Задачи с нелинейной целевой функцией и линейными ограничениями называются задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно 
классифицировать на основе структурных особенностей целевой 
функции. Если целевая функция квадратичная, то мы имеем дело с 
задачей квадратичного программирования. Если же целевая функция 
представляет собой отношение линейных функций, соответствующая 
задача носит название задачи дробно-линейного программирования. 
Особое место среди задач нелинейного программирования занимают 
задачи выпуклого программирования, в которых целевая функция 
является выпуклой. Для данного класса задач есть множество хорошо разработанных методов решения, основанных на существовании 
единственного оптимума целевой функции.  

Для задач нелинейного программирования, в которых функции 
f(x), Нk(х) и Gj(х) являются нелинейными, подбор численного метода 
решения существенно затруднен. В таких случаях необходимо разрабатывать специальные алгоритмы, учитывающие особенности функций, участвующих в постановке задачи, или пытаться свести исходную задачу к задаче математического программирования, для которой существуют численные методы решения с хорошей сходимостью, в ущерб, возможно, точности решения. 
Каждый из перечисленных классов задач характеризуется собственным подходом к решению оптимизационных задач, и для них разработаны соответствующие методы решения.  
Условно методы решения задач оптимизации разделяют на два 
класса: 
• методы прямого поиска; 
• градиентные методы. 
К первому классу относятся методы, в которых алгоритм поиска и 
оценка его результата построены на вычислении значения исследуемой функции на каждой итерации, и такие методы еще называются 
методами нулевого порядка. Если же процедура поиска основана на 
свойствах градиента функции, то такие методы называются градиентными методами (методами с использованием производной в случае одномерной оптимизации). Они, в свою очередь, подразделяются 
на методы первого и второго порядка в зависимости от того, используется ли только градиент (производная) функции или необходимо 
значение производной второго порядка исследуемой функции. 
Большинство из существующих алгоритмов оптимизации являются 
приближенными, т.е. не гарантирующими точного решения. В связи с 
этим возникает вопрос: по какому критерию следует оценивать полученное на каждой итерации решение с целью окончания поиска? Существует несколько критериев окончания поиска, которые могут применяться как по отдельности, так и в сочетании друг с другом: 
1) по разности значений целевой функции на двух последних итерациях: 

 
(
)
1
(
)
(
)
;
k
k
f x
f x
+
−
≤ ε  

2) по разности значений двух точек, найденных на последних шагах: 

 
(
1)
( )
;
k
k
x
x
+
−
≤ ε  

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

 
( )
(
)
;
k
f x
∇
≤ ε  

4) по числу итераций: 

 
n ≤ ε, где n – число итераций. 

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

Контрольные вопросы 

1. Что такое оптимизационная задача? 
2. Как установить границы рассматриваемого с целью оптимизации объекта? 
3. Что такое система ограничений задачи?  
4. Что такое искомая переменная?  
5. Как называется критерий эффективности в оптимизационных 
задачах? 
6. Что собой представляют параметры математической модели?  
7. Задача. Химическому предприятию в целях развития необходимо провести трубопровод с наименьшими затратами. Известно, 
что затраты состоят из стоимости труб, монтажа труб и стоимости и 
установки насосного оборудования. Все перечисленные затраты зависят от диаметра трубы. Диаметр может принимать значения в известном диапазоне. Идентифицируйте для данной задачи следующие 
понятия: 

Доступ онлайн
2 000 ₽
В корзину