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

Форма Ф СО ПГУ 7.18.2/07

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

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

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

ДЛЯ СТУДЕНТОВ

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

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

Павлодар

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

Форма Ф СО ПГУ 7.18.1/11

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

«__»________________2008 г.

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

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

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

Протокол №_____

(подпись)

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

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

(подпись)

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

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

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

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

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

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

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

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

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

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

• формирование у студентов базовые понятия о численном решении задачи;

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

1. 
   Численные методы и задачи оптимизации. / под ред. В.Н. Игнатьева, Г.Ш. Фридмана. Томск, изд-во Томского ун-та, 1983.-165 с.
   
2. 
   В.М. Монахов и другие. Методы оптимизации. Применение математических методов в экономике. Пособие для учителя. М., Просвещение, 1978.-175 с.
   
3. 
   Г. И. Марчук Методы вычислительной математики. М., Наука, 1980.
   
4. 
   Г.С. Ганшин Методы оптимизации и решение уравнений. М., Наука, 1987.
   
5. 
   В.М. Заварыкин Лабораторный практикум по вычислительной математике. Учебное пособие для физико-математического факультета пед. Институтов. Свердловск, Свердловский гос. Пед. Институт, 1986.-87 с.
   
6. 
   Н. Культин Программирование на Object Pascal в Delphi 5. Спб, БХБ, Санкт-Петербург, 1999.
   
7. 
   Фаронов В.В. Турбо Паскаль 7.0 Учебный курс.-М., 1998.-433с.
   
8. 
   Фаронов В.В. DELPHI 4 . Учебный курс.-М., 1999.-464с.
   

1. 
   Корн Т., Корн К. Справочник по математике для научных работников и инженеров определения, теоремы, формулы. Издание четвертое.
   
2. 
   Реньи А. Трилогия о математике. М., 1980. - 374 с.
   
3. 
   Яглом А. М., Яглом И. М. Вероятность и информация. - М.:Наука, 1973. - 511с.
   

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

Форма Ф СО ПГУ 7.18.2/07

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 
  проработать каждую лекцию; изучить дополнительный материал по пройденным темам (УО1, УО2, УО3, УО4, УО5);
  
• 
  изучить материал, необходимый для выполнения практических работ;
  
• 
  написать программы для численного решения задач и сдать их;
  
• 
  выполнить домашние задания в виде решения задач и ответов на контрольные вопросы (ДЗ1, ДЗ2);
  
• 
  подготовиться к контрольным мероприятиям (К1, К2), рубежным контролям, к экзамену.
  

1. 
   Текущий контроль 0,6
   
2. 
   Экзамен 0,4
   

Календарный график контрольных мероприятий

текущей успеваемости, заочное

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