Лекции по "Методам оптимизации"

Конспект лекций по методам оптимизации.

Виктор Павлович Пирог

Оформление в электронном виде:

Алексеева Елена

Содержание:

1. Тема 1. Введение        2

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

∙ Задачи оптимизации        2

1.2. Выпуклые множества        3

1.3. Выпуклые функции        7

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

∙ Постановка задачи        11

∙ Классы оптимизационных задач        12

2. Тема 2. Линейное программирование. Введение        16

2.1. Постановка общей задачи линейного программирования        16

2.2. Геометрическая интерпретация задач линейного программирования        17

2.3. Свойства решений задачи линейного программирования        18

2.4. Двойственные задачи линейного программирования        21

3. Тема 3. Методы решения общей задачи ЛП        25

3.1. Идея метода последовательного улучшения плана, признак оптимальности        25

3.2. Алгебраическое обоснование метода последовательного улучшения плана        

(По выданному В.П. конспекту на 34-х страницах для самостоятельного изучения – АЕ)

Учебно-методическое обеспечение дисциплины

Основная литература

1. Мустафин Н.Г., Пирог В.П., Родионов В.Д. Задачник по курсу "Методы оптимизации": Учеб. пособие.-Л.: РИО ЛЭТИ, 1978.519\М-91
2. Мустафин Н.Г., Пирог В.П., Родионов В.Д. Задачник по курсу "Исследование операций": Учеб. пособие.-Л.: РИО ЛЭТИ, 1979. 519\М-91
3. Волков Н.В., Мустафин Н.Г., Пирог В.П. Методы и алгоритмы решения линейных оптимизационных задач: Учеб. пособие.-Л.: РИО ЛЭТИ, 1983. 518.6\В-67
4. Методы и алгоритмы решения нелинейных оптимизационных задач : Учеб.пособие/ Н.Г.Мустафин, В.П.Пирог,Л.И.Яшин. ЛЭТИ им.В.И.Ульянова(Ленина). -Л.: ЛЭТИ, 1990. В-18\М-91
5. Решение линейных оптимизационных задач средствами ППП микроЛП: учеб.пособие / Н.Е.Матевицкая,Н.Г.Мустафин, В.ПЛирог, А.И.Яшин; СПбГЭТУ (ЛЭТИ). - СПб. : Изд-воСПбГЭТУ "ЛЭТИ", 1998 В-18\Р-46
6. Решение линейных оптимизационных задач средствами ППП QSВ+ : Метод, указ./ Сост.: Н.Е.Матевицкая, Н.Г.Мустафин, В.П.Пирог; СПбГЭТУ "ЛЭТИ". -СПб.: Изд-во СПбГЭТУ "ЛЭТИ", 2000. 32с В-18\Р34

Дополнительная литература

1. Аттетков А.В., Галкин СВ., Зарубин В.С. Методы оптимизации: Учеб. для вузов.-М.: Изд-во МГТУ им Н.Э. Баумана, 2001. (Сер. Математика в техническом университете; Вып. XIV). В-18\А-92

(18.09.2011). Отредактировано - 06.09.2014 и 09.02.2015.

(--2--)

Тема 1. Введение

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

Задачи оптимизации

1. Нахождение экстремумов функций [pic 1]

1. Нахождение локального экстремума

1. Поиск безусловного экстремума

1. Методы одномерного поиска

• Без использования производных
• С использованием производных

1. Методы многомерного поиска

• Без использования производных
• С использованием производных
• Методы сопряженных направлений

1. Методы случайного поиска

1. Поиск условного экстремума

1. Методы математического программирования

• Методы линейного программирования
• Методы нелинейного программирования

• Методы дробно-линейного программирования
• Методы сепарабельного программирования
• Методы штрафных и барьерных функций
• Методы возможных направлений и градиентные методы

• Методы целочисленного программирования
• Методы стохастического программирования

1. Вариационное исчисление и принцип максимума
2. Динамическое программирование
3. Методы случайного поиска

1. Поиск экстемумов функций, вычисляемых со случайной ошибкой

1. Метод стохастической аппроксимации
2. Метод планирования экспериментов

1. Нахождение глобального экстремума

• Вариационное исчисление
• Принцип максимума
• Динамическое программирование
• Человеко-машинные методы

1. Нахождение экстремумов функционалов [pic 2]

• Вариационное исчисление
• Принцип максимума
• Динамическое программирование
• Человеко-машинные методы

(--3--)

Выпуклые множества

Рассмотрим набор из произвольных векторов из Еn: [pic 3] и составим линейную комбинацию векторов с весами μi, i=1,2,…,r:

[pic 4]        (1)

При этом, если [pic 5] и [pic 6], i=1,2,…,r, то выражение (1) называется выпуклой линейной комбинацией.

В свою очередь, множество [pic 7] (содержащееся) называется выпуклым, если вместе с любыми своими двум точками [pic 8] оно содержит и любую выпуклую линейную комбинацию вида: