МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

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

Закреплена за кафедройКафедра вычислительной техники и электроники
Направление подготовки09.03.01. Информатика и вычислительная техника
ПрофильИнформатика и вычислительная техника
Форма обученияОчная
Общая трудоемкость5 ЗЕТ
Учебный план09_03_01_ИиВТ-1-2020
Часов по учебному плану 180
в том числе:
аудиторные занятия 72
самостоятельная работа 81
контроль 27
Виды контроля по семестрам
экзамены: 4

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

Курс (семестр) 2 (4) Итого
Недель 19
Вид занятий УПРПДУПРПД
Лекции 20 20 20 20
Лабораторные 36 36 36 36
Практические 16 16 16 16
Сам. работа 81 81 81 81
Часы на контроль 27 27 27 27
Итого 180 180 180 180

Программу составил(и):
к.ф.-м.н., доцент, Пашнев В.В.

Рецензент(ы):
к.ф.-м.н, доцент, Рудер Д.Д.

Рабочая программа дисциплины
Методы оптимизации

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 09.03.01 Информатика и вычислительная техника (уровень бакалавриата) (приказ Минобрнауки России от 19.09.2017г. №929)

составлена на основании учебного плана:
09.03.01 Информатика и вычислительная техника
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

Рабочая программа одобрена на заседании кафедры
Кафедра вычислительной техники и электроники

Протокол от 26.06.2020 г. № 69/18-19
Срок действия программы: 2020-2021 уч. г.

Заведующий кафедрой
д.т.н., Седалищев Викторт Николаевич, профессор, заведующий кафедрой вычислительной техники и электроники

Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра вычислительной техники и электроники

Протокол от 26.06.2020 г. № 69/18-19
Заведующий кафедрой д.т.н., Седалищев Викторт Николаевич, профессор, заведующий кафедрой вычислительной техники и электроники

1. Цели освоения дисциплины

1.1.Цель преподавания дисциплины состоит в изучении студентами математической базы решения оптимизационных задач, формирования навыков экспериментальных исследований при выборе метода оптимизации.
Задачи изучения дисциплины. В результате изучения дисциплины студенты должны знать основные понятия и постановки задач теории минимизации гладких функций, выпуклого и линейного программирования, переборных задач. Вариационного исчисления, методы решения типовых задач из указанных областей. Уметь решать вручную и с помощью ЭВМ типовые задачи небольшой размерности. Иметь представление о разнообразных постановках оптимизационных задач, а также о стандартных программных средствах решения типовых оптимизационных задач.

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.В.01

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

ПК-8: Способен разрабатывать стратегии тестирования и управления тестированием в области ИТ;
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.О разнообразных постоновках задач оптисмизации.
О задачах линейного програмирования и способах их решения.
О экономической интерпретации задач оптимизации.
О методах нелинейной оптимизации.
3.2.Уметь:
3.2.1.Теорию минимизации гладких функций. Постановку задач выпуклого и линейного програмирования. Методы решения типовых задач.
Уметь решать вручную и с помощью ЭВМ типовые задачи.
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.-постоновки задач объемного планирования, задачи о смесях, транспортной задачи и их решения;
- решения задач симплекс-методом;
- применения программных средств для решения типовых оптимизационных задач.

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

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Введение.
1.1. Основные понятия и определения. Задачи принятия решений. Математическое моделирование. Лекции 4 2 Л2.1, Л1.2
Раздел 2. Линейные математические модели.
2.1. Задача объемного планирования. Задача о диете. Транспортная задача. Общий вид математической модели задачи линейного программирования. Приведение задачи линейного программирования от одной эквивалентной формы к другой. Графическое решение задач. Лекции 4 2 Л2.1, Л1.2
2.2. Графическое решение задач. Сам. работа 4 6 Л2.1, Л1.1, Л2.3
2.3. Задача объемного планирования. Задача о диете. Транспортная задача. Сам. работа 4 10 Л2.1, Л1.2
Раздел 3. Математические свойства задачи линейного программирования.
3.1. Свойства области допустимых решений. Базисные и опорные решения. Лекции 4 2 Л2.1, Л1.2
3.2. Свойства области допустимых решений. Базисные и опорные решения. Практические 4 2 Л2.1, Л1.1, Л2.3
3.3. Свойства области допустимых решений. Базисные и опорные решения. Сам. работа 4 8 Л2.1, Л1.2
Раздел 4. Симплекс-метод решения задачи линейного программирования.
4.1. Симплекс-метод. Векторное представление симплексных преобразований. Симплекс-метод в уравнениях. Симплекс-метод в таблицах. Правила построения симплекс-таблиц. Варианты разрешимости задачи линейного программирования. Лекции 4 2 Л2.1, Л1.2
4.2. Симплекс-метод решения задачи линейного программирования.Решение задач. Практические 4 2 Л2.1, Л1.1, Л2.3
4.3. Решение задач Сам. работа 4 14 Л2.1, Л1.1, Л2.3
Раздел 5. Метод искусственного базиса.
5.1. Метод искусственного базиса. Лекции 4 2 Л2.1, Л1.2
5.2. Метод искусственного базиса.Решение задач. Практические 4 2 Л2.1, Л1.1, Л2.3
5.3. Метод искусственного базиса.Решение задач. Сам. работа 4 12 Л2.1, Л1.2
Раздел 6. Теория двойственности в задачах линейного программирования.
6.1. Построение двойственной задачи. Правила построения двойственной задачи. Математические свойства пары взаимно двойственных задач. Вторая теорема двойственности. Анализ чувствительности оптимального решения. Построение областей устойчивости двойственных оценок. Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой. Двойственный симплексный метод. Лекции 4 2 Л2.1, Л1.2
6.2. Двойственные задачи. Решение задач. Практические 4 2 Л2.1, Л1.1, Л2.3
6.3. Двойственные задачи. Решение задач. Сам. работа 4 11 Л2.1, Л1.2
Раздел 7. Послеоптимизационный анализ задачи линейного программирования.
7.1. Постановка задачи. Добавление нового ограничения. Добавление новой переменной. Изменение коэффициентов критерия. Изменение технологических коэффициентов. Лекции 4 2 Л2.1, Л1.2
7.2. Изменение коэффициентов критерия. Изменение технологических коэффициентов. Решение задач. Практические 4 2 Л2.1, Л1.1, Л2.3
7.3. Изменение коэффициентов критерия. Изменение технологических коэффициентов. Решение задач. Сам. работа 4 4 Л2.1, Л1.2
Раздел 8. Методы нелинейной оптимизации. Классическая теория оптимизации.
8.1. Основные понятия. Необходимые условия оптимальности. Достаточные условия оптимальности. Лекции 4 2 Л2.1, Л1.1, Л2.3, Л1.2
8.2. Достаточные условия оптимальности. Практические 4 2 Л2.1, Л1.1, Л2.3
8.3. Достаточные условия оптимальности. Сам. работа 4 2 Л2.1, Л1.2
Раздел 9. Нелинейное программирование.
9.1. Задачи на условный экстремум. Метод множителей Лагранжа. Лекции 4 2 Л2.1, Л1.2
9.2. Задачи на условный экстремум. Практические 4 2 Л2.1, Л1.1, Л2.3
9.3. Задачи на условный экстремум. Сам. работа 4 2 Л2.1, Л1.1, Л2.3
Раздел 10. Задача выпуклого программирования.
10.1. Постановка задачи. Условия Куна-Такера. Геометрический смысл задачи выпуклого программирования. Лекции 4 2 Л2.1, Л1.2
10.2. Решение задач выпуклого программирования. Практические 4 2 Л2.1, Л1.1, Л2.3
10.3. Решение задач выпуклого программирования. Сам. работа 4 4 Л2.1, Л1.1, Л2.3
Раздел 11. Лабораторные работы
11.1. Транспортная задача Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.2. Графический метод решения задач линейного программирования Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.3. Задача коммивояжера Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.4. Теория двойственности Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.5. Задачи выпуклого программирования. Теорема Куна-Такера. Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.6. Задача о рационе Лабораторные 4 6 Л2.1, Л2.2, Л2.3, Л1.2
11.7. Обработка результатов. Подготовка отчетов по лаб-ным работам Сам. работа 4 4 Л2.1, Л1.1, Л2.3, Л1.2
11.8. Изучение надстройки "Поиск решения" в Excel. Решение задач оптимизации в Excel. Сам. работа 4 2 Л1.1, Л2.3
11.9. Matlab. Решение задач оптимизации в пакете Matlab. Сам. работа 4 2 Л1.1, Л2.3
Раздел 12. Аттестация
12.1. Экзамен 4 27 Л2.1, Л2.2, Л1.1, Л2.3, Л1.2

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания
вопросы к экзамену
Линейные математические модели. Задача объемного планирования (задача о выпуске продукции). Задача о диете (задача о составлении смеси). Общий вид математической модели задачи линейного программирования. Различные формы задач линейного программирования. Приведение задачи линейного программирования от одной эквивалентной формы к другой. Графическое решение задач. Свойства градиента функции. Свойства области допустимых решений.
Математические свойства задачи линейного программирования. Свойства области допустимых решений. Базисные и опорные решения.
Симплекс-метод решения задачи линейного программирования. Идея симплекс-метода. Векторное представление симплексных преобразований. Симплекс-метод в уравнениях. Симплекс-метод в таблицах. Правила построения симплекс-таблиц. Этапы симплекс-метода. Варианты разрешимости задачи линейного программирования. Предупреждение зацикливания симплекс-метода.
Метод искусственного базиса. Построение начального опорного плана. Решение задачи линейного программирования методом искусственного базиса.
Теория двойственности в задачах линейного программирования. Построение двойственной задачи. Математическая формулировка двойственной задачи к произвольной задаче линейного программирования. Правила построения двойственной задачи. Математические свойства пары взаимно двойственных задач. Варианты разрешимости задач двойственной пары. Вторая теорема двойственности. Экономическая интерпретация второй теоремы двойственности. Анализ чувствительности оптимального решения к изменению свободных членов ограничений. Экономическая интерпретация третьей теоремы двойственности. Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой. Двойственный симплексный метод.
Послеоптимизационный анализ задач линейного программирования. Добавление нового ограничения. Добавление новой переменной. Изменение коэффициентов критерия. Изменение технологических коэффициентов.
Методы нелинейной оптимизации. Классическая теория оптимизации. Необходимые условия оптимальности. Достаточные условия оптимальности.
Нелинейное программирование. Задачи на условный экстремум. Метод множителей Лагранжа. Задачи выпуклого программирования.
5.2. Темы письменных работ (эссе, рефераты, курсовые работы и др.)
Не требуется
5.3. Фонд оценочных средств
ФОС приведены в Приложении
Приложения

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Акулич И.Л. Математическое программирование в примерах и задачах: Учебные пособия Издательство "Лань", 2011 https://e.lanbook.com/book/2027
Л1.2 Лесин В.В., Лисовец Ю.П. Основы методов оптимизации: Учебные пособия Издательство "Лань", 2016 https://e.lanbook.com/book/86017
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 А.В. Жариков, Л.А. Хворова Методы оптимизации и вариационное исчисление: учеб. пособие Барнаул: Изд-во АлтГУ, 2007
Л2.2 Ю. А. Панченко, В. В. Пашнев Лабораторные работы по курсу "Методы оптимизации" [Электронный ресурс]: учеб. пособие АлтГУ, 2018 http://elibrary.asu.ru/handle/asu/5001
Л2.3 Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и упражнениях: Практикумы, лабораторные работы, сборники задач и упражнений Издательство "Лань", 2012 https://e.lanbook.com/book/3799
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Методы оптимизации https://portal.edu.asu.ru/course/view.php?id=1713
Э2 9. www.biblioclub.ru/ Университетская библиотека ONLINE
Э3 8. elanbook.com/ Издательство "Лань", Электронно-библиотечная система
Э4 7. www.window.edu.ru/ Библиотека учебной и методической литературы
Э5 6. www.intuit.ru/ Образовательный сайт
Э6 5. www.tests.specialist.ru/ Центр компьютерного обучения МГТУ им. Н.Э.Баумана.
Э7 4. www.rsl.ru/ Российская государственная библиотека.
Э8 3. www.nns.ru/ Национальная электронная библиотека.
Э9 2. www.nlr.ru/ Российская национальная библиотека.
Э10 1. www.gpntb.ru/ Государственная публичная научно-техническая библиотека.
6.3. Перечень программного обеспечения
Microsoft Office
Microsoft Windows
Open Office
Условия использования: http://www.openoffice.org/license.html
LibreOffice
Условия использования: https://ru.libreoffice.org/about-us/license/
7-zip
Условия использования: https://www.7-zip.org/license.txt
Mozila FireFox
Условия использования: https://www.mozilla.org/en-US/about/legal/eula/
Chrome
Условия использования: http://www.chromium.org/chromium-os/licenses
Acrobat Reader
Условия использования: http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf
6.4. Перечень информационных справочных систем
1 Федеральная служба государственной статистики РФ [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.gks.ru/.
2 Федеральный портал по научной и инновационной деятельности [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.sci-innov.ru/.
3 Научная и учебно-методическая литература [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.intuit.ru.
4 Научный журнал «Вестник Российской академии естественных наук» [Электрон-ный ресурс]. - Электронные данные. - Режим доступа: http://www.ras.ru/publishing/rasherald/rasherald_archive.aspx.
5 Научный журнал «Интеграл» [Электронный ресурс]. - Электронные данные. – Ре-жим доступа: http://www.portalnano.ru/read/databases/publication/journal_integral.
6 Научный журнал «Инновации» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://ojs.innovjoum.ru/index.php/innov
7 Научный журнал «Информатика и системы управления» [Электронный ресурс]. – Электронные данные. - Режим доступа: http://ics.khstu.ru/
8 Научный журнал «Информационные системы и технологии» [Электронный ре-сурс]. - Электронные данные. - Режим доступа: http://gu-unpk.ru/science/joumal/isit
9 Научный журнал «Информационные технологии» [Электронный ресурс]. - Элек-тронные данные. - Режим доступа: http://novtex.ru/IT/
10 Научный журнал «Нейрокомпьютеры: разработка, применение» [Электронный ре-сурс].-Электронные данные. – Режим доступа: http://www.radiotec.ru/catalog.php?cat=jr7
11 Научный журнал «Программные продукты и системы» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://www.swsys.ru/

Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
203К лаборатория цифровой обработки сигналов - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 12 посадочных мест; рабочее место преподавателя; доска меловая 2 шт.; компьютеры: марка компьютер Парус модель 945 MSI - 12 единиц; коммутатор D-LINK; методические указания по выполнению лабораторной работы по дисциплине "Нейроинформационные технологии": алгоритм обратного рассеяния; обучение без учителя; персептрон; Сети Хопфилда и Хемминга.
001вК склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ

8. Методические указания для обучающихся по освоению дисциплины

не требуется