Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Методы оптимизации
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к базовой части ОПОП ВО 

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по математическому анализу, линейной алгебре и алгебре логики в объеме, соответствующем программе первого и второго годов обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.
Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):
•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решении задач в области профессиональной деятельности 
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат

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

Знать:
1.	основные понятия, факты и методы дискретной оптимизации (в том числе с позиций теории сложности);
2.	основные понятия, факты и методы линейного программирования (в том числе теорию двойственности и сложность задач);
3.	общую теорию и основные методы безусловной оптимизации (в том числе градиентные методы, методы Ньютона);
4.	общую теорию и основные методы условной оптимизации (в том числе методы штрафов и внутренней точки);
5.	основы теории нелинейного программирования (условия оптимальности);
6.	общие схемы методов комбинаторной оптимизации (динамического программирования, ветвей и границ);
7.	свойства задач целочисленного линейного программирования.

Уметь:  
1.	применять на практике средства теории сложности для классификации задач оптимизации;
2.	применять на практике методы целочисленного, линейного и нелинейного программирования с пониманием их свойств; 
3.	находить приближённые решения задач нелинейной оптимизации функций нескольких переменных;
4.	выписывать двойственные задачи, применять свойство двойственности для анализа и решения оптимизационных моделей;
5.	строить функцию Лагранжа в задачах условной оптимизации, применять необходимые условия оптимальности для анализа оптимизационных моделей;
6.	применять свойство двойственности для анализа и решения линейных задач;
7.	строго обосновывать математические утверждения.

Владеть:
1.	языком теории сложности, теории и методов оптимизации;
2.	навыками определения сложности задач оптимизации;
3.	навыком построения двойственной задачи линейного программирования и функции Лагранжа в условной оптимизации;
4.	навыками использования градиентного метода и метода Ньютона в задачах нелинейной оптимизации.

4. Формат обучения: лекции проводятся с использованием меловой доски, самостоятельное выполнение студентами заданий осуществляется на бумажном носителе.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 48 академических часов, отведенных на контактную работу обучающихся с преподавателем, 60 академических часа на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Введение в теорию сложности: основные определения (индивидуальной и массовой задачи, кодировки, алгоритма решения массовой задачи, его временной сложности, классов P и NP); примеры; понятия: полиномиальной сводимости, классов NPС, со-NP, NP-hard, хорошей характеризации; взаимоотношение классов сложности, критерий NP-полноты, теорема Кука (без доказательства), доказательство NP-полноты БЛН и 3-ВЫП, NP-трудности ЦЛП;  класс РSРАСЕ.	14	6	0	6	6	
2.	Приближенное решение задач комбинаторной оптимизации (псевдополиномиальные алгоритмы, пример для задачи о рюкзаке, сильная NP-полнота, теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения; определение задачи комбинаторной оптимизации и приближенного алгоритма ее решения; утверждение о разнице между приближенным и точным оптимумом в задаче о рюкзаке; понятие ε-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС); связь между существованием ПППС и псевдополиномиальностью; теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания свойств; пример для задачи о коммивояжере). 	8	8	0	8	0	
3.	Текущий контроль успеваемости: контрольная работа № 1 	2	0	0	0	2	
4.	Понятие о сложности задачи линейного программирования (ЛП): формы записи ЛП, принцип граничных решений и геометрическое описание симплекс-метода; алгебраическая и битовая сложность методов ЛП; результаты по сложности задач, близких к ЛП; теорема о границах решений задач ЛП с целыми коэффициентами, теорема о мере несовместности систем линейных неравенств с целыми коэффициентами;  полиномиальный алгоритм округления ε-приближенного решения системы линейных неравенств, метод эллипсоидов  ε-приближенного решения озЛП, оценка сложности метода эллипсоидов, полиномиальность ЛП. 	12	8	0	8	4	
5.	Теория двойственности ЛП (следствия систем ЛН, Афинная лемма Фаркаша (без доказательства), лемма Фаркаша о неразрешимости, теорема двойственности ЛП); применение теории двойственности (смысл двойственных переменных, сведение ЛП к решению однородной системы уравнений с ограничением положительности; идея метода Кармаркара – описание метода и обсуждение его отличий от симплекс-метода).	10	6	0	6	4	
6.	Текущий контроль успеваемости: контрольная работа № 2	2	0	0	0	2	
7.	Основы математического программирования (МП): понятие о МП и классификация задач МП; сложность общей задачи МП, преимущества выпуклости, понятие о градиентных и ньютоновских методах минимизации функций нескольких переменных (определения, идеи, свойства, геометрические аналогии); условная оптимизация, способы освобождения от ограничений (методы штрафов и внутренней точки). 	6	6	0	6	0	
8.	Условная оптимизация: пример для метода Кармаркара,  необходимые условия локального минимума гладких функций при ограничениях неравенствах; понятие о регулярности ограничений-неравенств в задаче МП; метод множителей Лагранжа; теорема Куна-Таккера и ее приложения. 	6	4	0	4	2	
9.	Текущий контроль успеваемости: контрольная работа № 3	2	0	0	0	2	
10.	Способы решения переборных задач: методы глобальной оптимизации (случайный и последовательный перебор, метод ветвей и границ (МВГ) в глобальной оптимизации, описание и стратегии метода), целочисленное ЛП (ЦЛП) –  существенная нелинейность ограничений  целочисленности (неэффективность округления решения ЛП до ближайшего целого, случай унимодулярной матрицы ограничений);  МВГ в ЦЛП, МВГ для булева ЛП (БЛП); оценки сложности МВГ. 	6	6	0	6	2	
11.	Метод динамического программирования (МДП): основы теории,  общая схема метода, МДП) для БЛП+, сравнение МДП и МВГ для БЛП+.	4	4	0	4	0	
Промежуточная аттестация: устный экзамен	36	0			36	
Итого	108	48	0	48	60	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Контрольная работа № 1 (у каждого свой вариант). Примеры вариантов:	
Вариант 1	Вариант 2	
1. К какому классу сложности принадлежит задача проверки делимости на 2019? 	1. К какому классу сложности относится задача, дополнительная к БЛН? 	
Контрольная работа № 2 (у каждого свой вариант). Примеры вариантов:	
Вариант 1	Вариант 2	
Сформулировать теорему двойственности линейного программирования (ЛП). Построить двойственную задачу для задачи ЛП:
                                                            max     (2х + 1)
                                                      -1 < x < 3

Решить прямую и двойственную задачи. Найти значения оптимума для прямой и двойственной задач, проверить, что они совпадают.
	Сформулировать теорему двойственности линейного программирования (ЛП). Построить по определению двойственную задачу для задачи ЛП:
                                                            min    (2y1  – 3y2 )
                                                          y1= y2
                                                     y1 > 0, y2  > 0
Выяснить существование решения прямой и двойственной задачи Если существуют, то найти значения оптимума для прямой и 
двойственной задач, проверить, что они совпадают. 	
Контрольная работа № 3 (у каждого свой вариант). Примеры вариантов:	
Вариант 1	Вариант 2	
Выписать 4 итерации метода градиентного спуска с постоянным шагом для задачи поиска минимума функции  f (х1, х2) = 2х12 + 3х22
при начальном приближении (х1, х2) = (-1, 2) и шаге а = 1. Указать условия на шаг для сходимости метода. Решить задачу методом Ньютона (с тем же начальным приближением).	Выписать 4 итерации метода градиентного спуска с постоянным шагом для задачи поиска минимума функции  f (х1, х2) = 2х12 + 4х22
при начальном приближении (х1, х2) = (-3, 2) и шаге а = 1. Указать условия на шаг для сходимости метода. Решить задачу методом Ньютона (с тем же начальным приближением).	

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

Вопросы к экзамену.
1.	Определения: индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
2.	Формула градиентного метода в задаче безусловной минимизации.
3.	Задачи распознавания свойств. Классы Р и NР.
4.	Формула метода Ньютона в задаче безусловной минимизации.
5.	Теорема об экспоненциальной временной оценке для задач из класса NР.
6.	Идея метода штрафов.
7.	Определение полиномиальной сводимости. Класс NРС.
8.	Теорема Кука /без док-ва/.
9.	Геометрическое описание симплекс-метода.
10.	Критерий NР-полноты. Док-во NР-полноты задачи ЦЛH.
11.	Методы глобальной минимизации.
12.	Док-во NР-полноты задачи 3-выполнимость. NР-трудные задачи.
13.	Формула градиентного метода в задаче безусловной минимизации.
14.	Класс со-NР. Пример задачи, допускающей хорошую характеризацию.
15.	Доказательство утверждения о взаимоотношении классов NРС и со-NР.
16.	Формула метода Ньютона в задаче безусловной минимизации.
17.	Взаимоотношение классов Р, NР и NРС, NР и со-NР. Класс РSРАСЕ.
18.	Полиномиальный алгоритм округления ε1-приближенного решения системы линейных неравенств.
19.	Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке.
20.	Идея метода эллипсоидов.
21.	Сильная NР-полнота. Теорема о связи сильной NР-полноты задачи с существованием псевдополиномиального алгоритма ее решения.
22.	Идея метода штрафов.
23.	Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке.
24.	Идея метода Ньютона.
25.	Определение е-приближенного алгоритма и полностью полиномиальной приближенной схемы /ПППС/. Связь между существованием ПППС и псевдополиномиальностью. 
26.	Теорема оптимальности для разложимых функций.
27.	Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NР-полным задачам распознавания.
28.	Геометрическая идея симплекс-метода.
29.	Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.
30.	Идея метода ветвей и границ. Пример для задачи БЛП.
31.	Теорема о границах решений задач ЛП с целыми коэффициентами.
32.	Метод ветвей и границ для ЦЛП. Различные стратегии метода.
33.	Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами.
34.	Метод ветвей и границ для глобальной минимизации липшицевых функций.
35.	Следствия систем линейных неравенств. Афинная лемма Фаркаша /без док-ва/.
36.	Понятие о временной сложности алгоритмов.
37.	Лемма Фаркаша о неразрешимости.
38.	Понятие о недетерминированно полиномиальных задачах.
39.	Теорема двойственности ЛП.
40.	Метод динамического программирования для БЛП с неотрицательными коэффициентами.
41.	Сведение озЛП к однородной системе уравнений с ограничением x>0.
42.	Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи.
43.	Классификация задач математического программирования. Преимущества выпуклого случая.   
44.	Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций.
45.	Идея метода Кармаркара.
46.	Понятие о регулярности ограничений-неравенств в задаче математического программирования.
47.	Описание метода эллипсоидов.
48.	Теорема о целочисленности решения задачи ЛП с целыми коэффициентами для вполне унимодулярных матриц ограничений.
49.	Оценка сложности метода эллипсоидов ε2-приближенного решения озЛП.

Типовые задачи для экзамена.
1.	Показать, что двойственная задача к двойственной задаче ЛП совпадает с прямой задачей ЛП /для озЛП/.
2.	Расшифровать формулировку теоремы Куна-Таккера для случая ocновной задачи ЛП (озЛП).
3.	Представить каноническую задачу ЛП в форме основной задачи ЛП.
4.	Дать алгоритм распознавания простоты числа, оценить сложность алгоритма.
5.	Доказать, что задача распознавания простоты числа принадлежит классу со-NР.
6.	Оценить по порядку длину входа задачи коммивояжера.
7.	Оценить по порядку битовую длину входа задачи ЛП.
8.	Построить двойственную задачу к указанной.
9.	Привести пример задачи, имеющей указанный класс сложности.
10.	Выписать первые 5 итераций градиентного метода решения указанной задачи с предложенным шагом и начальным приближением, объяснить полученные свойства метода.
11.	Решить методом Ньютона задачу минимизации.
12.	Выписать алгоритм метода штрафов для конкретной задачи, придумать штрафную функцию для предложенной задачи.
Экзаменационный билет состоит из двух вопросов и задачи, например

1. Теорема о границах решений задач ЛП с целыми коэффициентами.
2. Метод ветвей и границ для ЦЛП. Различные стратегии метода.
3. Доказать, что задача распознавания простоты числа принадлежит классу со-NР.

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен
	Отсутствие знаний, грубые ошибки принципиального характера	Фрагментарные знания при отсутствии грубых ошибок принципиального характера и при общем понимании	Общие, но не структурированные знания, недостаточное понимание	Сформированные систематические знания и понимание	
Умения
Контрольные работы, выполнение самостоятельных домашних заданий 	Отсутствие умений	В целом успешное, но не систематическое умение по основным темам курса	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен,
контрольные работы 	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основные понятия, факты и методы дискретной оптимизации (в том числе с позиций теории сложности);
2.	основные понятия, факты и методы линейного программирования (в том числе теорию двойственности);
3.	общую теорию и основные методы безусловной оптимизации (в том числе градиентные методы, методы Ньютона);
4.	общую теорию и основные методы условной оптимизации (в том числе методы штрафов и внутренней точки);
5.	основы теории нелинейного программирования (условия оптимальности);
6.	общие схемы методов комбинаторной оптимизации (динамического программирования, ветвей и границ);
7.	свойства задач целочисленного линейного программирования.
Уметь:
1.	применять на практике средства теории сложности для классификации задач оптимизации;
2.	применять на практике методы целочисленного, линейного и нелинейного программирования с пониманием их свойств; 
3.	находить приближённые решения задач нелинейной оптимизации функций нескольких переменных.
Владеть: 
1.	языком теории сложности, теории и методов оптимизации;
2.	навыком построения двойственной задачи линейного программирования и функции Лагранжа в условной оптимизации;
3.	навыками использования градиентного метода и метода Ньютона в задачах нелинейной оптимизации.	

ОПК-1.Б	
Знать:
1.	основные понятия, факты и методы дискретной оптимизации (в том числе с позиций теории сложности);
2.	основные понятия, факты и методы линейного программирования (в том числе теорию двойственности и сложность задач);
3.	общую теорию и основные методы безусловной оптимизации (в том числе градиентные методы, методы Ньютона);
4.	общую теорию и основные методы условной оптимизации (в том числе методы штрафов и внутренней точки);
5.	основы теории нелинейного программирования (условия оптимальности);
6.	общие схемы методов комбинаторной оптимизации (динамического программирования, ветвей и границ);
7.	свойства задач целочисленного линейного программирования.
Уметь:  
1.	выписывать двойственные задачи, применять свойство двойственности для анализа и решения оптимизационных моделей;
2.	строить функцию Лагранжа в задачах условной оптимизации, применять необходимые условия оптимальности для анализа оптимизационных моделей;
3.	применять свойство двойственности для анализа и решения линейных задач;
4.	строго обосновывать математические утверждения.
Владеть: 
1.	языком теории сложности, теории и методов оптимизации;
2.	навыками определения сложности задач оптимизации;
3.	навыком построения двойственной задачи линейного программирования и функции Лагранжа в условной оптимизации;
4.	навыками использования градиентного метода и метода Ньютона в задачах нелинейной оптимизации;

ОПК-2.Б	
Владеть:  
1.	языком теории сложности, теории и методов оптимизации;
2.	навыками определения сложности задач оптимизации;
3.	навыком построения двойственной задачи линейного программирования и функции Лагранжа в условной оптимизации;
4.	навыками использования градиентного метода и метода Ньютона в задачах нелинейной оптимизации. 	

ПК-2.Б	

8. Ресурсное обеспечение:

Основная литература:
1. Новикова Н.М. Дискретные и непрерывные задачи оптимизации (основные сведения по теории и методам решения). Изд-во ВЦ РАН,  Москва, 1996 г.
Лекции можно взять по адресу: http://www.ccas.ru/depart/malashen/53kmsu.htm
2. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. 2-е изд. М.: Физматлит, 2005.

Дополнительная литература:
1.	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
2.	Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.
3.	Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987, N 10.
4.	Мину М. Математическое программирование. М.: Наука, 1990.
5.	Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988 (или последующие издания).
6.	Карманов В.Г. Математическое программирование. М.: Физматлит, 2000.
7.	Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1989 или М.:УРСС, 2013.

Материально-техническое обеспечение:  аудитория с партами и меловой доской.

9. Язык преподавания - русский.

10. Преподаватели:  профессор факультета ВМК МГУ Н.М. Новикова

11. Автор программы:  профессор факультета ВМК МГУ Н.М. Новикова.