Глава I. Нелинейное программирование: экстремумы функций нескольких переменных

Мухаметьянов Ильдар Талгатович

МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

К изучению дисциплин

«МЕТОДЫ ОПТИМИЗАЦИИ»,

«МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ»,

«СИСТЕМНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ»,

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ

ОПТИМИЗАЦИИ СИСТЕМ»

Раздел «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ»

ЛЫСЬВА, 2015

ББК

Мухаметьянов И.Т. Методические материалы к изучению дисциплин «Методы оптимизации», «Методы оптимальных решений», «Системный анализ и управление», «Исследование операций и методы оптимизации систем». Раздел «Нелинейное программирование». ¾ Лысьва: Изд-во Лысьвенского филиала Пермского национального исследовательского политехнического ун-та, 2015. ¾ 162 с.

Рассмотрено на заседании кафедры Естественно научных дисциплин:

протокол №____от____________2015 г.

Данное пособие является пособием по разделу «Нелинейное программирование» для студентов вузов. Читатель найдёт в нём как теоретический материал, так и материал для практических занятий по разделу. Кроме того, в пособии приведены варианты для самостоятельной работы студентов (всего 20 вариантов), а также образцы оформления их решений.

ã Мухаметьянов И.Т., 2015 г.

ã Лысьвенский филиал Пермского национального исследовательского политехнического университета (ЛФ ПНИПУ), 2015 г.

Содержание

Содержание………………………………………………………….………………3

Предисловие…………………………………………………………………………4

Глава I. Нелинейное программирование: экстремумы функций нескольких переменных……………………………………………..………………6

§1. Классические методы оптимизации..……………………………….6

1.1. Безусловный экстремум функции одной переменной (6). 1.2. Условный экстремум функции одной переменной (9). 1.3. Безусловный экстремум функции двух переменных (10). 1.3. Условный экстремум функции двух переменных (16). 1.4. Упражнения (18).

§2. Безусловный экстремум функции нескольких переменных.…….19

2.1. Необходимые и достаточные условия (19).

§3. Условный экстремум функции нескольких переменных.……….29

3.1. Основные определения и факты (29). 3.2. Условный экстремум при ограничениях типа равенств (33). 3.3. Условный экстремум при ограничениях типа неравенств (40). 3.4. Условный экстремум при смешанных ограничениях (55). 3.5. Понятие о методах штрафных функций (60).

Глава II. Численные методы нелинейного программирования…………...69

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

1.1. Постановка проблемы (69). 1.2. Общие принципы (69).

§2. Методы нулевого порядка одномерной минимизации……………71

2.1. Общие положения (71). 2.2. Метод равномерного поиска (73). 2.3. Метод деления интервала пополам (74).

§3. Методы первого и второго порядков……………………………….77

3.1. Метод градиентного спуска с постоянным шагом (77). 3.2. Метод Ньютона (82). 3.3. Упражнения (35)

§4. Элементы численных методов задачи условной минимизации выпуклого программирования…………………………………………85

4.1. Общие замечания к численным методам условной минимизации (85). 4.2. Постановка задачи выпуклого программирования (86). 4.3. Численные методы на основе метода штрафных функций (86). 4.4. Метод проекции градиента. (93)

Приложения…………………….………………………………………………………99

Приложение 1. Варианты индивидуальных заданий.………………………99

Приложение 2. Образец выполнения и индивидуального задания………106

ЛИТЕРАТУРА…………..……………………………………………………….163

Предисловие

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

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

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

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

Вторая часть включает в себя приложения. Приложение 1 содержит варианты для индивидуальных самостоятельных работ. В Приложении 2 мы приводим образцы выполнения индивидуального задания. В этой связи нам пришлось повторять изложение некоторых методов решения задач. Следует обратить внимание на следующую особенность образца выполнения индивидуальной работы: индивидуальная самостоятельная работа выполняется за рамками аудиторных часов, поэтому задания не только содержат задачи, требующие больших вычислений, но и подробных пояснений, с соответствующими ссылками на теоретический материал, выходящий даже за рамки данной темы. Это актуально не только для студентов-заочников, для которых выполнение домашних контрольных является неотъемлемым атрибутом учебного процесса, но и для студентов дневного и вечернего отделений, которых в погоне за результативностью на ЕГЭ в школе научили практически только ставить галочки напротив правдоподобного варианта ответа. Поэтому при выполнении письменных индивидуальных работ студент обязан привести все подробности их выполнения.

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

Нумерация, принятая в каждой части тройная и имеет вид i.j.k, где i ¾ номер параграфа, j ¾ номер пункта в параграфе и k ¾ номер определения, утверждения, примера или упражнения, причем нумерация k ¾ сквозная. Аналогична, за некоторыми исключениями, нумерация формул. Кроме того, иногда текст изложения сопровождается комментариями. Они приведены в угловых скобках более мелким шрифтом.

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

Желаем успехов!

Доцент Мухаметьянов Ильдар Талгатович

Глава I. Нелинейное программирование: экстремумы функций нескольких переменных

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

f(x₁, x₂, …, x_n) ® min (max)

(1)

где f, j_i (i=1, 2, …, m) - некоторые функции из R^п в R. При этом система ограничений может отсутствовать.

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