А. Н. Туполева утверждаю: Проректор по учебной и методической работе И. К. Насыров 2007 г. Программа дисциплины

Вид материала

Содержание

Подобный материал:

1 2 3 4

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А.Н. ТУПОЛЕВА

УТВЕРЖДАЮ:

Проректор по учебной и методической

работе

_________________ И.К. Насыров

«_____» _______________ 2007 г.

ПРОГРАММА ДИСЦИПЛИНЫ

ЕН.Ф.01.7 "МЕТОДЫ ОПТИМИЗАЦИИ"

Рекомендуется УМЦ КГТУ им. А.Н. Туполева для направлений

(специальностей)

направления: 230100 « Информатика и вычислительная техника »

специальности: 230105 « Программное обеспечение вычислительной техники

и автоматизированных систем »

формы обучения: очная

Цель и задачи дисциплины.

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

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

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

Для изучения дисциплины “Методы оптимизации” необходимо усвоение студентами разделов “Математического анализа”: числовые множества и последовательности, дифференциальное и интегральное исчисление, линейная алгебра.

2. Требования к уровню освоения содержания дисциплины.

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

Знать

- основы современной технологии разработки математической модели поиска оптимальных решений;

-классификацию экстремальных задач и методов их решения;

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

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

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

- типовые задачи оптимизации на графах;

-простейшую задачу вариационного исчисления и метод ее решения.

Уметь

-формулировать основные математические задачи оптимизации, в зависимости от типа критерия качества и наличия ограничений;

-решать классическим методом задачи безусловной минимизации функций одной и нескольких переменных;

-решать симплекс-методом задачу линейного программирования;

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

- решать задачу о максимальном потоке в среде MS Excel 2003.

Иметь опыт

-использования методов оптимизации на ПК в операционной системе Microsoft Windows.

Иметь представление

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

-о современной технологии постановки и практического решения типовых задач оптимизации в среде MS Excel.

3. Объем дисциплины и виды учебной работы

	Всего	Семестр
	Всего	5
Общая трудоемкость дисциплины	140	140
Аудиторные занятия	51	51
Лекции (Л)	34	34
Практические занятия (ПЗ)	0	0
Семинары (С)	0	0
Лабораторные работы (ЛР)	17	17
Самостоятельная работа	89	89
Курсовой проект(работа)	0	0
Расчётно-графические работы	17	17
Реферат	0	0
Другие виды самостоятельной работы	72	72
Вид итогового контроля		Экзамен

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

4.1. Тематический план

№ п/п	Наименование тем
№ п/п	Наименование тем	Л	ЛР
	Введение	2	0
1	Предмет и задачи дисциплины	1	0
2	Математическое моделирование в оптимизации	1	0
	Методы одномерной оптимизации	4	4
3	Математическая модель одномерной оптимизации	1	0
4	Классический метод одномерной оптимизации	1	0
5	Прямые методы одномерного поиска	2	4
	Методы безусловной минимизации функции многих переменных	9	4
6	Математическая модель многомерной оптимизации	2	0
7	Прямые методы безусловной оптимизации	1	8
8	Методы безусловной оптимизации, использующие производные функции	4	4
9	Градиентные методы второго порядка	2	0
	Методы оптимизации при наличии ограничений	13	8
10	Математическая модель конечномерной оптимизации при наличии ограничений	1	0
11	Постановка задачи линейного программирования (ЗЛП)	3	0
12	Графический метод решения ЗЛП	1	0
13	Метод последовательного улучшения плана	4	0
14	Методы последовательной безусловной оптимизации	0	4
15	Метод случайного поиска	0	4
16	Постановка задачи выпуклого программирования (ЗВП)	1	0
17	Метод возможных направлений решения ЗВП	3	6
	Оптимизация на графах	2	0
18	Типовые задачи оптимизации на графах и их решение в среде MS Excel 2003.	2	0
	Оптимизация в функциональных пространствах	4	0
19	Простейшая задача вариационного исчисления	2	0
20	Аналитический метод решения вариационной задачи	2	0

4.2. Содержание тем

Введение

1. Предмет и задачи дисциплины (1/1)

Экстремальные проблемы в технике и экономике, их возникновение и развитие.

Признаки классификации экстремальных задач. Задачи математического

программирования и их классификация.

2. Математическое моделирование в оптимизации (1/1)

. Объект оптимизации. Выбор управляемых переменных и числового критерия оптимизации. Формулировка математической задачи оптимизации. Примеры формализации задач на экстремум. Задачи классического вариационного исчисления и оптимального управления.

Методы одномерной оптимизации

3. Математическая модель одномерной оптимизации (1/2).

Минимум функции одной переменной. Ее точки минимума и точная нижняя грань.

Унимодальные функции и их свойства. Гладкие и выпуклые функции, их свойства.

4. Классический метод одномерной оптимизации (1/2)

Необходимые и достаточные условия экстремума функции одной переменной. Алгоритмы реализации классического метода. Примеры.

5. Прямые методы одномерного поиска (7/1)

Приближённые методы решения задачи одномерной оптимизации.

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

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

6. Математическая модель многомерной оптимизации (2/2 )

Постановка задачи безусловной минимизации функций многих переменных. Минимум функции многих переменных. Дифференцируемые функции многих переменных. Необходимые и достаточные условия экстремума дифференцируемой функции. Алгоритм классического метода. Примеры.

7. Прямые методы безусловной оптимизации (1/2)

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

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

8. Методы безусловной оптимизации, использующие производные (4/2)

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

9. Градиентные методы второго порядка (2/2)

Понятие дважды дифференцируемой функции многих переменных. Квадратичная аппроксимация. Матрица Гессе. Метод Ньютона. Обобщенный метод Ньютона. Примеры.

Методы оптимизации при наличии ограничений

10. Математическая модель конечномерной оптимизации при наличии

ограничений (1/2)

Общая постановка и классификация задач математического программирования. Задача на условный экстремум. Функция Лагранжа. Правило множителей Лагранжа. Примеры.

11. Постановка задачи линейного программирования ( 3/1)

Общая постановка ЗЛП. Каноническая форма ЗЛП. Приведение общей ЗЛП к канонической форме. Множество планов ЗЛП и его свойства. Угловые точки. Опорные планы вырожденные и невырожденные. Свойства решений ЗЛП.

12. Графический метод решения ЗЛП (1/2)

Графическая интерпретация ЗЛП. Гиперплоскость линейной формы. Опорная гиперплоскость множества планов ЗЛП. Алгоритм графического метода решения ЗЛП. Примеры.

13. Метод последовательного улучшения плана (4/2)

Основная идея метода последовательного улучшения планов. Переход от одного опорного плана к другому. Признак оптимальности опорного плана. Рекуррентные соотношения для параметров соседних опорных планов. Первый алгоритм симплекс-метода. Способы построения начального опорного плана.

14. Методы последовательной безусловной оптимизации (4/1)

Метод штрафных функций. Последовательность штрафных функций. Метод барьерных функций. Последовательность барьерных функций. Комбинированный

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

15. Метод случайного поиска (4/1)

Случаи предпочтительного выбора метода случайного поиска (МСП). Правило построения минимизирующей последовательности в МСП. Особенности алгоритмической реализации МСП. Понятие неудачного шага в МСП. Критерий

прекращения поиска. Алгоритмы МСП с обучением и без обучения. Поиск с возвратом при неудачном шаге.Алгоритм наилучшей пробы. Алгоритм статистического градиента.

16. Постановка задачи выпуклого программирования (1/2)

Выпуклые множества и их свойства. Выпуклые функции и их экстремальные свойства. Постановка ЗВП. Выпуклость допустимой области ЗВП.

17. Метод возможных направлений решения ЗВП (3/2)

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

Оптимизация на графах

18. Типовые задачи оптимизации на графах и их решение в среде MS Excel 2003(2/2)

Типовые задачи оптимизации на графах. Задача о максимальном потоке. Общая математическая постановка задач оптимизации на графах. Математическая модель задачи

о максимальном потоке. Компонент офисного пакета MS System Office – MS Excel.

Решение задачи о максимальном потоке в среде – MS Excel 2003.

Оптимизация в функциональных пространствах

18. Простейшая задача вариационного исчисления (2/2)

Основные понятия вариационного исчисления. Минимум функционала на заданном классе функций. Вариации функции и ее производных. Кривые сравнения нулевого и первого порядка близости. Лемма Лагранжа. Простейшая вариационная задача с фиксированными границами.

19. Аналитический метод решения вариационной задачи (2/2)

Построение функций сравнения в задаче с фиксированными границами. Вывод необходимого условия экстремума функционала на классе гладких функций. Уравнение Эйлера. Примеры.

4.3. Лабораторный практикум

№ п/п	Номер темы	Объём в часах		Наименование лабораторных работ
№ п/п	Номер темы	Очное	Заочное	Наименование лабораторных работ
1	5	5		Методы одномерного поиска
2	8	4	2	Градиентные методы
3	14	4	2	Методы последовательной безусловной оптимизации
4	15	4		Метод случайного поиска

Blog

А. Н. Туполева утверждаю: Проректор по учебной и методической работе И. К. Насыров 2007 г. Программа дисциплины

Содержание

ПРОГРАММА ДИСЦИПЛИНЫ

ЕН.Ф.01.7 "МЕТОДЫ ОПТИМИЗАЦИИ"