9286

УДК 004.9

Прокопенко Н.Ю. / Методы оптимизации [Электронный ресурс]: учеб.-метод. пос. / Н.Ю. Прокопенко; Нижегор. гос. архитектур. - строит. ун-т – Н. Новгород: ННГАСУ, 2016. – 132 с.– 1 электрон. опт. диск (CD-RW).

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

Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Методы оптимизации» по направлению подготовки 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике.

Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике, утверждённым решением учёного совета ННГАСУ от 02.09.2016 г. (протокол № 1).

© Н.Ю. Прокопенко, 2016 © ННГАСУ, 2016

2

Оглавление

1.Общие положения……………………………………………………………….......4

1.1Цели изучения дисциплины и результаты обучения……………………….....4

1.2Содержание дисциплины………………………………………………….…....4

1.3Порядок освоения материала……………………………………………….…..5

2.Методические указания по подготовке к лекциям………………………….….....6

2.1Общие рекомендации по работе на лекциях…………………………….…….6

2.2Общие рекомендации при работе с конспектом лекций……………….….....6

2.3Краткое содержание лекций………………………………………………..…..7

2.3.1. Раздел 1. Оптимизационные задачи нелинейного программирования.

Их классификация.……………………………………………………………...….7

2.3.2.Раздел 2. Безусловная нелинейная оптимизация функций одной переменной. Классификация методов……………………………………….…...20

2.3.3.Раздел 3. Безусловная оптимизация функции многих переменных.……40

2.3.4.Раздел 4. Условная оптимизация функции многих переменных. ………70

2.4Контрольные вопросы………………………………………………………...84

3.Методические указания по подготовке к практическим занятиям……….…....87

3.1Общие рекомендации по подготовке к практическим занятиям…………..87

3.2Примеры задач для практических занятий…………………………....….…87

4.Методические указания по организации самостоятельной работы…….….....109

4.1Общие рекомендации для самостоятельной работы………………….…...109

4.2Темы для самостоятельного изучения……………………………………...109

4.3.Учебно-методическое обеспечение самостоятельной работы…………...113

4.4 Задания для самостоятельной работы……………………………………...114

3

1. Общие положения

1.1 Цели изучения дисциплины и результаты обучения

Основными целями освоения учебной дисциплины «Методы оптимизации» являются: изучение математических методов и базовых алгоритмов оптимизации,

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

В процессе освоения дисциплины студент должен Знать:

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

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

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

Уметь:

оптимизировать одномерную и многомерную целевую функции;

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

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

Владеть:

навыками оптимизации одномерной и многомерной целевой функции с помощью программных средств;

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

1.2 Содержание дисциплины

Материал дисциплины сгруппирован по следующим разделам:

1. Оптимизационные задачи нелинейного программирования. Их классификация.

Основные понятия. Классификация и примеры оптимизационных нелинейных

4

задач в науке, производстве и экономике. Сравнение моделей линейного и

нелинейного программирования.

2.Безусловная нелинейная оптимизация функций одной переменной.

Классификация методов.

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

3. Безусловная оптимизация функции многих переменных.

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

метод наискорейшего спуска, метод сопряженных градиентов, метод Ньютона.

4. Условная оптимизация функции многих переменных.

Методы условной оптимизации функции многих переменных в задачах с ограничениями-равенствами и с ограничениями-неравенствами. Графический анализ задач нелинейного программирования. Метод множителей Лагранжа.

Экономическая интерпретация множителей Лагранжа и нормировочных градиентов.

Метод штрафных функций.

1.3 Порядок освоения материала

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

следующей таблице: Таблица 1

Порядок освоения дисциплины

5

2. Методические указания по подготовке к лекциям

2.1 Общие рекомендации по работе на лекциях

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

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

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

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

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

2.2Общие рекомендации при работе с конспектом лекций

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

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

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

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

6

вопросов без обсуждения означает в большинстве случаев неусвоенность материала

дисциплины.

2.3 Краткое содержание лекций.

2.3.1. Раздел 1. Оптимизационные задачи нелинейного программирования.

Их классификация.

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

логических режимов, элементов конструкций, структуры технологических цепочек,

условий экономической деятельности, повышение доходности и т. д.), оптимальное управление построением нематематических моделей объектов управления (миними-

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

пасами, трудовыми ресурсами, транспортными потоками и т. д.).

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

где f (x) – целевая функция;

X – допустимое множество

x X – допустимая точка задачи.

В основном мы будем иметь дело с конечномерными задачами оптимизации, то есть с задачами, в которых допустимое множество X лежит в евклидовом пространстве R n ( x R n ).

Точка x* X , являющаяся решением задачи, может быть точкой глобального или локального минимума.

Определение. Точка x* X называется

7

2) точкой локального минимума функции f (x) на множестве Х или локальным

няется как строгое при x x , то x* – точка строгого минимума (строгое решение) в

глобальном или локальном смысле.

Ясно, что глобальное решение является и локальным; обратное неверно.

f (x) на множестве Х. В этом случае arg min f (x) – это просто произвольная точка

из множества Arg min f (x).

x X

По аналогии с Ошибка! Источник ссылки не найден. записывают задачу максимизации функции f (x) на множестве Х, в виде f (x) max , x X

(3).

Заменяя в данных выше определениях слово «минимум» на «максимум» и за-

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

полученные для задачи минимизации, на задачи максимизации, и наоборот.

Пример. Рассмотрим график некоторой функции Y=F(X) (рис. 1). Тогда имеем:

Х1 – точка локального максимума;

Х2 – точка локального минимума;

Х3 – точка глобального максимума;

Х4 – точка глобального минимума.

Рис. 1.

Замечание.

1) Всякая точка глобального минимума является и точкой локального миниму-

ма этой функции. Обратное, вообще говоря, неверно.

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

3)Если функция обладает свойством унимодальности, то локальный минимум автоматически является глобальным минимумом.

9

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

При изучении задач оптимизации в первую очередь возникает вопрос о суще-

ствовании решения. Ответ на этот вопрос дает теорема Вейерштрасса.

Теорема Вейерштрасса.

Пусть Х – замкнутое ограниченное множество в R n , f (x) – непрерывная функция на множестве Х. Тогда точка глобального минимума функции f (x) на Х существует (глобальное решение задачи существует).

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

Классификацию задач оптимизации можно проводить по нескольким призна-

кам в зависимости от вида функции f (x) и множества Х:

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

стями; статические, динамические (например, задачи управления);

2)безусловной и условной оптимизации;

3)с непрерывными и дискретными переменными (частично - целочисленные,

целочисленные, с булевыми переменными);

4)однокритериальные и многокритериальные;

5)линейные и нелинейные;

6)одномерные и многомерные, причем многомерные задачи могут быть малой и большой размерности;

7)с выпуклыми и невыпуклыми целевыми функциями;

8)одноэкстремальные и многоэкстремальные.

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

дачи. Все возможные методы решения задач нелинейного программирования можно

10