Geum.ru

Самостоятельная работа 2 часа в неделю всего часов

Вид материалаСамостоятельная работа

Содержание


Всего часов
Заведующий кафедрой
Список литературы
Подобный материал:

министерство образования и науки российской федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»


УТВЕРЖДАЮ

проректор по учебной работе

Ю.Н. Волков


«___» _____________ 20___ г.




П Р О Г Р А М М А




курса МЕТОДЫ ЦЕЛОЧИСЛЕННОЙ ОПТИМИЗАЦИИ

по направлению 010900 «Прикладные математика и физика»

по магистерским программам 010990

факультет управления и прикладной математики (ФУПМ)

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

курс V

семестры 9 (осенний)


лекции 34 часа экзамен 9 семестр (осенний)

семинары нет зачёт нет

лабораторные занятия нет


самостоятельная работа 2 часа в неделю

ВСЕГО ЧАСОВ 34




Программу составил: к.ф.-м.н. Поспелов А.И.

Программа обсуждена на заседании кафедры

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

14 марта 2011 года



Заведующий кафедрой

чл.-корр. РАН А.П. Кулешов


Программа обсуждена на заседании методического

совета ФУПМ 20 апреля 2011 года


Председатель методического совета

чл.-корр. РАН Ю.А. Флёров

  1. Постановка задачи целочисленной оптимизации. Примеры целочисленных задач. Особенности задач целочисленной оптимизации. Общие сведения о подходах к решению целочисленных задач.



  1. Приближенный алгоритм. Полиномиальные приближенные схеме. Вполне полиномиальные приближенные схеме. N-приближенные алгоритмы.



  1. Вероятностные алгоритмы. Вероятностное округления, оценка его эффективности.



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



  1. Основы полуопределённого программирования. Применение полуопределённого программирования для решения целочисленных задач (методы Лассерра, Ловаса-Шрийвера, Шерали-Адамса).



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



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



СПИСОК ЛИТЕРАТУРЫ

1. Ковалев М.М. Дискретная оптимизация. Целочисленное программирование. Едиториал УРСС, 2003.

2. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: ФИЗМАТЛИТ, 2007.

3. Junger M., Liebling T.M. et al. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer, 2009. [имеется в библиотечном фонде кафедры]

4. Laurent M., Rendl F. Semidefinite Programming and Integer Programming. CWI / Amsterdam, 2002. [имеется в библиотечном фонде кафедры]

5. Schütze O. Set Oriented Methods for Global Optimization PhD thesis. University of Paderborn, 2004. [имеется в библиотечном фонде кафедры]