Реферат: Даутова Айгуль Зейнуллиновна преп. Оспанова Гульмира Абугалиевна Кафедра Информатика и информационные системы программа дисциплины

Программа дисциплины для студентов





Форма

Ф СО ПГУ 7.18.2/07


Министерство образования и науки Республики Казахстан


Павлодарский государственный университет имени С.Торайгырова

Кафедра информатики и информационных систем


ПРОГРАММА ДИСЦИПЛИНЫ ДЛЯ СТУДЕНТОВ

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

для специальности 050703 «информационные системы»


Павлодар


Лист утверждения к программе дисциплин для студентов





Форма

Ф СО ПГУ 7.18.1/11


УТВЕРЖДАЮ

Декан ФФМиИТ

__________________С.К.Тлеукенов

«__»________________2008 г.


^ Составитель: доцент ПГУ Даутова Айгуль Зейнуллиновна
преп. Оспанова Гульмира Абугалиевна

Кафедра Информатика и информационные системы


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

«методы оптимизации и исследование операций»


для студентов специальности 050703 «информационные системы»


Рекомендована на заседании кафедры от «__»_________________200__г.

Протокол №_____


Заведующий кафедрой_________________________Ж.К.Нурбекова

(подпись)

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

«___»___________200__г. Протокол №______


Председатель УМС_______________________________ А.З.Даутова

(подпись)


^ 1 Данные о преподавателях

Лекции: доц. ПГУ Даутова Айгуль Зейнуллиновна

Практические занятия- преп. Оспанова Гульмира Абугалиевна

Приемные часы: ГУК А1-102, 103 в соответствии с утвержденным графиком консультаций

^ 2 Данные о дисциплине

«методы оптимизации и исследование операций» (3 кредита)

Курс рассчитан на 1 семестр. В 3-м семестре предусмотрено 30-лекционных занятий, 15-практических занятий, 30 часов лабораторных занятий и 22,5 часов - СРСП. Форма контроля –зачет в 4-м семестре.

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

Пререквизиты

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

^ Краткое описание дисциплины

Дисциплина «методы оптимизации и исследование операций» предполагает изучение основной терминологии вычислительной математики; особенностей применения компьютерных технологий, тенденции их развития и совершенствования. Задачами курса является формирования у студентов в систематизированной форме понятия о приближенных (численных) методах решения прикладных задач и подготовить студентов к разработке и применению с помощью ЭВМ вычислительных алгоритмов решения математических задач, возникающих в процессе познания и использования в практической деятельности законов реального мира, посредством математического моделирования.

После изучения дисциплины студент приобретает:

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

навыки работы, необходимые для освоения и применения вычислительной техники в дальнейшей профессиональной деятельности;

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

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

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

иметь представления об основных методах вариационного исчисления.

Литература

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

Численные методы и задачи оптимизации. / под ред. В.Н. Игнатьева, Г.Ш. Фридмана. Томск, изд-во Томского ун-та, 1983.-165 с.

В.М. Монахов и другие. Методы оптимизации. Применение математических методов в экономике. Пособие для учителя. М., Просвещение, 1978.-175 с.

Г. И. Марчук Методы вычислительной математики. М., Наука, 1980.

Г.С. Ганшин Методы оптимизации и решение уравнений. М., Наука, 1987.

В.М. Заварыкин Лабораторный практикум по вычислительной математике. Учебное пособие для физико-математического факультета пед. Институтов. Свердловск, Свердловский гос. Пед. Институт, 1986.-87 с.

Н. Культин Программирование на Object Pascal в Delphi 5. Спб, БХБ, Санкт-Петербург, 1999.

Фаронов В.В. Турбо Паскаль 7.0 Учебный курс.-М., 1998.-433с.

Фаронов В.В. DELPHI 4 . Учебный курс.-М., 1999.-464с.

9. Электронные учебники по языкам программирования.

дополнительная

Корн Т., Корн К. Справочник по математике для научных работников и инженеров определения, теоремы, формулы. Издание четвертое.

Реньи А. Трилогия о математике. М., 1980. - 374 с.

Яглом А. М., Яглом И. М. Вероятность и информация. - М.:Наука, 1973. - 511с.



Тематический план дисциплины






Форма

Ф СО ПГУ 7.18.2/07




^ ТЕМАТИЧЕСКИЙ ПЛАН ДИСЦИПЛИНЫ

№

р/с

Наименование тем

часы

лекции

прак

лаб

СРО

1

2

3

4

5

6



Введение.

2












Элементы выпуклого анализа.

2

1

2






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

2

1

2






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

2

1

2






Вариационное исчисление.

2

1

2






Оптимальное управление и принцип максимума.

2

1

2

4



Оптимальное управление. Динамическое программирование.

2

1

2

4

8

Предмет, история и перспектива развития предмета “Исследования операций”.

2

1

2




9

Основные понятия предмета “ исследования операции” и системного анализа. Методологические основы теории принятия решений.

2

1

2




10

Линейные модели ИСО. Задачи линейного программирования. Двойственные задачи линейного программирования.

2

1

2

4

11

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

2

1

3

4

12

Сетевое планирование. Постановка задачи сетевого планирования.

2

1

2

4

13

Теория расписаний. Постановка задачи составления расписаний.

2

1

3

2,5

14

Вероятностные модели.

2

1

2




15

Имитационное моделирование. Системный анализ.

2

2

2




Всего:

30

15

30

22,5



^ СОДЕРЖАНИЕ ЛЕКЦИОННЫХ ЗАНЯТИЙ

Тема 1 Введение. Предмет, история становления и перспективы развития методов оптимизации.

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

Компактные множества. Полунепрерывность снизу. Теоремы о достижении нижней грани функции на заданном множестве.

^ Тема 2 Элементы выпуклого анализа.

Выпуклые множества. Аффинная оболочка. Внутренние, граничные, относительно внутренние точки. Выпуклая комбинация точек. Необходимые и достаточные условия выпуклости множеств. Выпуклая оболочка. Теоремы о свойствах выпуклой оболочки.

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

Отделимость выпуклых множеств. Отделимость множества и точки. Отделимость выпуклых множеств, не имеющих общих точек. Сильная отделимость выпуклых множеств. Теорема о пустоте пересечения выпуклых множеств. Теорема Дубовицкого- Милютина.

Функция Лагранжа. Седловая точка. Основная лемма о седловой точке. Основная теорема о глобальном минимуме.

Теорема Куна - Таккера. Условия Слейтера. Теорема существования седловой точки функции Лагранжа. Лемма Фаркаша. Различные формы условий оптимального выпуклой функции на выпуклом множестве. Элементы теории двойственности в линейном программировании.

^ Тема 3 Линейное программирование.

Основная, общая и каноническая задачи линейного программирования. Двойственные задачи. Задача линейного программирования в канонической форме. Задачи линейного программирования, их различные формы и метод сведения к задаче с ограничениями в форме равенства. Симплекс – метод и его модификации. Лемма о крайней точке. Лемма о свойстве векторов условий. Лемма о крайней точке в невырожденной задаче. Лемма о выпуклой комбинаций крайних точек. Лемма о глобальном минимуме. Критерий оптимальности. Выбор направления. Построение симплекс- таблицы. Построение начальной крайней точки. Специальные задачи линейного программирования.

^ Тема 4 Нелинейное программирование.

Постановка задачи. Необходимые условия оптимальности. Построение конусов. Конус направления убывания. Конус внутренних направлений. Конус касательных направлений. Доказательства теоремы об оптимальности.

^ Тема 5 Нелинейное программирование.

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

Теория двойственности. Основная задача. Связь между решениями основной и двойственной задачи.

^ Тема 6 Вариационное исчисление.

Задача о брахистохроне. Простейшая задача. Сильный локальный минимум. Слабый локальный минимум. Необходимые условия слабого локального минимума. Лемма Лагранжа. Уравнение Эйлера. Лемма Дю Буа-Реймонда. Задача Больца. Необходимые условия Вейерштрассе. Условия Лагранжа. Условия Якоби. Условия Вейерштрассе-Эрдмана.

Функционалы, зависящие от n неизвестных функции. Функционалы, зависящие от производных высших порядков. Изопериметрическая задача. Задача Лагранжа.

^ Тема 7 Оптимальное управление и принцип максимума.

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

^ Тема 8 Оптимальное управление. Динамическое программирование.

Принцип оптимальности, уравнение Р. Беллмана. Линейная истема с квадратичным функционалом. Достаточные условия оптимальности В.Ф. Кротова. Основные леммы и теорема В.Ф. Кротова.

^ Тема 9 Предмет, история и перспектива развития предмета “исследования операций”.

Тема 10 Основные понятия предмета “ исследования операции” и системного анализа. Методологические основы теории принятия решений.

^ Тема 11 Линейные модели ИСО.

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

Тема 12 Экстремальные задачи на графах.

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

^ Тема 13 Сетевое планирование.

Постановка задачи сетевого планирования.

Тема 14 Вероятностные модели.

Тема 15 Имитационное моделирование. Системный анализ.

^ СОДЕРЖАНИЕ ПРАКТИЧЕСКИХ ЗАНЯТИЙ


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

^ П1 Элементы выпуклого анализа.

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

^ П2 Нелинейное программирование.

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

^ П3 Линейное программирование.

Постановка задачи. Теория двойственности. Элементы линейного программирования. Стандартная задача ЛП. Симплекс – метод. Транспортная задача.

^ П 4 Вариационное исчисление.

П 5 Оптимальное управление и принцип максимума.

П 6 Предмет, история и перспектива развития предмета “исследования операций”.

П 7 Методологические основы теории принятия решений.

^ П 8 Линейные модели ИСО.

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

П 9 Экстремальные задачи на графах. Основные понятия и определения из теории графов. Задача о кратчайшем пути.

^ П 10 Задача о максимальном потоке.

П 11 Сетевое планирование.

Постановка задачи сетевого планирования.

П 12 Теория расписаний.

Постановка задачи составления расписаний.

П 13 Вероятностные модели.

П 14- П 15 Имитационное моделирование. Системный анализ.

4.4 Содержание СРО

4.4.1 Перечень видов самостоятельной работы студента с преподавателем

СРСП 1- Элементы выпуклого анализа.

Тема: Выпуклое программирование. Выпуклые множества. Выпуклые функции. Проекция точки на множество.

^ СРСП 2- Элементы выпуклого анализа.

Тема: Отделимость выпуклых множеств. Лемма Фаркаша. Различные формы условий оптимального выпуклой функции на выпуклом множестве.

^ СРСП 3- Элементы выпуклого анализа.

Тема: Теорема Куна - Таккера. Элементы теории двойственности в линейном программировании.

^ СРСП 4- Численные методы математического программирования.

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

^ СРСП 5- Численные методы математического программирования.

Тема: Симплекс – метод и его модификации.

СРСП 6- Численные методы математического программирования.

Тема: Специальные задачи линейного программирования.

^ СРСП 7- Нелинейное программирование.

Тема: Нелинейная задача выпуклого программирования.

СРСП 8- Нелинейное программирование.

Тема: Методы минимизации функции одной переменной.


^ СРСП 9- Нелинейное программирование.

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

СРСП 10- Нелинейное программирование.

Тема: Градиентные методы минимизации функции при наличии ограничений. Методы, основанные на сведении задач условной минимизации к решению задач безусловной минимизации.

^ СРСП 11- Нелинейное программирование.

Тема: Регуляризация некорректных экстремальных задач. Основы многоэкстремальной минимизации, глобальный экстремум.

^ СРСП 12- Нелинейное программирование.

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

^ СРСП 13 - Оптимальное управление и вариационное исчисление.

Тема: Задача оптимального управления. Принцип максимума Понтрягина.

СРСП 14-Оптимальное управление и вариационное исчисление.

Тема: Оптимальное управление линейными системами. Необходимые и достаточные условия оптимальности.

^ СРСП 15-Оптимальное управление и вариационное исчисление.

Тема: Проблема синтеза.

СРСП 16-Задача вариационного исчисления.

Тема: Уравнения Эйлера.

СРСП 17-18-Задача вариационного исчисления.

Тема: Связь между принципом максимума и классическим вариационным исчислением.

^ 4.4.2 Перечень видов самостоятельной работы студента

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

проработать каждую лекцию; изучить дополнительный материал по пройденным темам (УО1, УО2, УО3, УО4, УО5);

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

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

выполнить домашние задания в виде решения задач и ответов на контрольные вопросы (ДЗ1, ДЗ2);

подготовиться к контрольным мероприятиям (К1, К2), рубежным контролям, к экзамену.

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

Распределение весовых долей по видам контроля

Текущий контроль 0,6

Экзамен 0,4

^ Распределение баллов текущей успеваемости по видам контроля

Формы контроля


Баллы


3 семестр

Р1

(7 недель)

Р2

(8 недель)

^ Текущий контроль:

80


80


Посещение, своевременное выполнение и защита практических работ

28

35

Посещение лекционных занятий и качественное ведение конспектов лекций

18

18

Своевременное выполнение и защита заданий на СРС

34

27

^ Рубежный контроль:

20

20

Всего:


100

100
^ Календарный график контрольных мероприятий текущей успеваемости
3 семестр


1 рейтинг

Итого

баллов

Недели

1

2

3

4

5


6


7

8

9

Р1

Максимальный балл,

в том числе по видам

контроля:

2

14

2

19

2

23

2

14

2

20

100

Посещение

занятий, подготовка к занятиям и работа в группе

Лекции

2

2

2

2

2

2

2

2

2




18

практ




1




1




1




1







4

Выполнение и защита

практических работ




Л1

6




Л2

6




Л3

6




Л4

6







24

Выполнение и защита

СРС




УО1

5




К1

10




ДЗ1

14




УО2

5







34

Рубежный контроль




























РК1

20

20




2 рейтинг

Итого

баллов

Недели

10

11

12

13

14

15

16

17

18

Р2

Максимальный балл,

в том числе по видам

контроля:

9

5

9

2

19

12

9

6

9

20

100

Посещение

занятий, подготовка к занятиям и работа в группе

Лекции

2

2

2

2

2

2

2

2

2




18

практ

1




1




1




1




1




5

Выполнение и защита

практических работ

Л5

6




Л6

6




Л7

6




Л8

6




Л9

6




30

Выполнение и защита

СРС




УО3

3








К2

10

ДЗ2

10




УО4

4








27

Рубежный контроль




























РК2

20

20



Виды контроля: РК - рубежный контроль, Л - лабораторные работы, РКР - разделы курсовой работы, К- контрольные работы, ДЗ - домашние задания, УО – устный опрос


^ 6 Политика курса

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

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

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

Несвоевременное выполнение СРС (кроме подготовки к занятиям) приводит к снижению балла:

на 1/3 при опоздании на неделю;

в 2 раза при опоздании более чем на неделю.

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

В случае опоздания студент не допускается к занятию и не имеет возможности отработать пропущенное занятие.

За любые нарушения этики поведения на занятиях устанавливаются штрафные санкции — вычитается 5 баллов за одно занятие!

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

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

В семестре предусмотрены два рубежных контроля в форме тестирования. Тестирование будет проводиться по материалу соответствующего блока.

Семестровый рейтинг рассчитывается по формуле:

,

где Р1 – рейтинг 1

Р2 – рейтинг2

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

,

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