Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Пермский национальный исследовательский
политехнический университет»
Лысьвенский филиал
Кафедра Естественнонаучных дисциплин
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ
«Исследование операций и методы оптимизации систем»
основной образовательной программы подготовки бакалавров
по направлению «09.03.01 Информатика и вычислительная техника»
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по организации практических занятий
Лысьва 2016 г.
Разработчик-составитель Мухаметьянов И.Т., к. ф.-м. н, доцент
Методические указания рассмотрены и одобрены на заседании кафедры
__________________________ « ___» __________2016 г, протокол № ____.
Содержание ............................................................................................................................................... 3
1. Общие положения................................................................................................................................ 4
2. Перечень тем практических занятий по дисциплине........................................................................ 6
3. Рекомендации по подготовке и проведению практических занятий.............................................. 7
Практическое занятие 1. Симплекс-метод решения задачи линейного программирования. ....... 7
Практическое занятие 2. Построение двойственной задачи и применение двойственных теорем
............................................................................................................................................................................ 9
Практическое занятие 3. Метод потенциалов решения транспортной задачи............................. 10
Практическое занятие 4. Метод идеальной точки решения многоцелевой задачи линейного
программирования. Сведение многоцелевой задачи линейного программирования к одноцелевой
задаче ............................................................................................................................................................... 12
Практическое занятие 5. Оптимизация потока в сети. Вычисление числовых характеристик
основных видов систем массового обслуживания...................................................................................... 14
Список рекомендуемой литературы................................................................................................. 16
1. Общие положения
Цель дисциплины формирование знаний в области исследования операций и
методов оптимизации систем.
В процессе изучения данной дисциплины студент осваивает следующие компетенции:
Общекультурных:
способность разрабатывать бизнес-планы и технические задания на оснащение
отделов, лабораторий, офисов компьютерным и сетевым оборудованием (ОПК-3);
Профессиональных:
способность обосновывать принимаемые проектные решения, осуществлять
постановку и выполнять эксперименты по проверке их корректности и эффективности
(ПК-3).
Задачи изучения дисциплины:
овладеть знаниями теоретических основ линейного программирования (включая целочисленное программирование, транспортную задачу), векторной оптимизации,
теории матричных игр, систем массового обслуживания;
приобрести практические навыки в решении задач линейного программирования методом искусственного базиса, целочисленного программирования методом Гомори, транспортной задачи методом потенциалов, матричных игр геометрическим методом
и сведением к задаче линейного программирования, в расчѐтах основных характеристик
систем массового обслуживания;
освоить указанные в предыдущем пункте методы.
Место дисциплины в структуре профессиональной подготовки выпускников.
Дисциплина «Исследование операций и методы оптимизации систем» относится к
дисциплинам Вариативной части Блока 1 (Б1). Дисциплины (модули) и является обязательной при освоении ОПОП по направлению подготовки 09.03.01 Информатика и вычислительная техника, профиль Вычислительные машины, комплексы, системы и сети.
Обязательные предшествующие дисциплины «Инженерная графика». Знания,
полученные при изучении дисциплины «Исследование операций и методы оптимизации
систем», необходимы при изучении дисциплин «Операционные системы», «Сети и телекоммуникации», «Теория вероятностей, математическая статистика и случайные процессы», «Управление программными проектами», «Научно-исследовательская работа».
После изучения дисциплины обучающийся должен демонстрировать следующие
результаты:
Знать:
линейное программирование;
5
основы теории матричных игр;
основы векторной оптимизации;
потоки в сетях;
основы теории систем массового обслуживания.
Уметь:
применять методы исследования операций и методов оптимизации систем в
своей профессиональной деятельности;
применять вычислительную технику в реализации методов исследования операций и методов оптимизации систем;
оптимизировать потоки в сетях;
вычислять основные характеристики систем массового обслуживания.
Владеть:
методами линейного программирования (методом искусственного базиса, методами решения задач целочисленного программирования, транспортной задачи);
теоремами двойственности;
методами сведения задач нелинейного программирования к задаче линейного
программирования;
методами сведения многоцелевой задачи линейного программирования к обычной задаче линейного программирования;
методами сведения матричной игры к задаче линейного программирования.
Предметом освоения дисциплины являются следующие объекты:
методология системного анализа;
линейное программирование;
векторная оптимизация;
теория игр;
системы массового обслуживания.
6
2. Перечень тем практических занятий по дисциплине
Т а б л и ц а 2.1 – Темы практических занятий
№ п.п. Номер темы
дисциплины
Наименование темы практического занятия
1 2 3
1 4
Симплекс-метод решения задачи линейного программирования
2 6
Построение двойственной задачи и применение двойственных теорем
3 8 Метод потенциалов решения транспортной задачи
4 10
Метод идеальной точки решения многоцелевой задачи
линейного программирования. Сведение многоцелевой
задачи линейного программирования к одноцелевой задаче
5 15, 17
Оптимизация потока в сети. Вычисление числовых характеристик основных видов систем массового обслуживания
7
3. Рекомендации по подготовке и проведению практических занятий
Практическое занятие 1. Симплекс-метод решения задачи линейного программирования.
1) План практического занятия
1. Повторить теорию по теме.
2. Решить пример под руководством преподавателя.
3. Решить самостоятельно пример.
4. Подвести итоги и дать задание для самостоятельной работы.
2) Вопросы для подготовки
1. Симплекс-метод решения задачи линейного программирования
3) Справочные материалы
[1], Глава I, §1. Задача линейного программирования. Типичные задачи линейного программирования, их математические модели
1.1. Задача линейного программирования.
1.2. Типичные задачи линейного программирования, их математические
модели.
§2. Общая ЗЛП. Канонический вид ЗЛП
2.1. Общая ЗЛП.
2.2. Канонический вид ЗЛП.
§3. Теоретические основы решения ЗЛП. Геометрическая интерпретация ЗЛП.
Идея аналитического решения
3.1. Теоретические основы решения ЗЛП.
3.2. Геометрическая интерпретация ЗЛП.
3.4. Идея аналитического решения ЗЛП.
3.5. Теоретические основы решения ЗЛП (продолжение).
§4. Симплекс-метод решения ЗЛП
4.1. Алгоритм симплекс-метода.
4.2. Симплекс-таблица.
4) Практические задания
1. Разобрать решение Примеров 1, 2 из [1], Глава I, §4.
2. Решить ЗЛП Упражнения 1.3.1а) из [1], Глава I, §4, симплекс-методом под руководством преподавателя.
3. Решить ЗЛП Упражнения 1.3.1е) из [1], Глава I, §4, симплекс-методом самостоятельно.
Д/з: 1. Решить ЗЛП Упражнения 1.3.1ж), з) симплекс-методом.
8
2. Подготовиться к лабораторной работе №2 «Реализация симплекс-метода в
оболочке Excel»: [2], §1.
Вопросы для самоконтроля:
1. Как приводится ЗЛП к каноническому виду?
2. Как строится первоначальный опорный план?
3. Как проверяется опорный план на оптимальность?
4. Как осуществляется переход к новому опорному плану?
5. Сформулировать алгоритм симплекс-метода.
9
Практическое занятие 2. Построение двойственной задачи и применение
двойственных теорем
1) План практического занятия
1. Повторить теорию по теме.
2. Решить пример под руководством преподавателя.
3. Решить самостоятельно пример.
4. Подвести итоги и дать задание для самостоятельной работы.
2) Вопросы для подготовки
1. Задача, приводящая к паре двойственных задач.
2. Пара симметричных двойственных задач.
3. Пара несимметричных двойственных задач.
4. Теоремы двойственности.
3) Справочные материалы
[1], Глава II, §1. Теория двойственности.
1.1. Задача, приводящая к паре двойственных задач.
1.2. Пара симметричных двойственных задач.
1.3. Пара несимметричных двойственных задач.
1.4. Теоремы двойственности.
4) Практические задания
1. Разобрать решение Примеров 1 и 2 из [1], Глава II, §1.
2. К ЗЛП Упражнения 1.3.1а) Главы I ([1]) составить двойственную и найти еѐ
решение по решению исходной под руководством преподавателя.
3. К ЗЛП Упражнения 1.3.1е) Главы I ([1]) составить двойственную и найти еѐ решение по решению исходной самостоятельно.
Д/з: 1. К ЗЛП Упражнения 1.3.1ж), з) Главы I ([1]) составить двойственную и
найти еѐ решение по решению исходной.
2. Решить Задание ЛП-2.2) индивидуальной работы относительно двойственности ([1], Приложение 1).
3. Подготовиться к лабораторной работе №3 «Применение теории двойственности в оболочке Excel. Метод Гомори решения целочисленной задачи линейного программирования»: [2], Глава II, §1, 1.1 1.4, §2, 2.1, 2.2.
Вопросы для самоконтроля:
1. Сформулировать условия двойственности.
2. Сформулировать теоремы двойственности.
10
Практическое занятие 3. Метод потенциалов решения транспортной задачи
1) План практического занятия
1. Повторить теорию по теме.
2. Решить пример под руководством преподавателя.
3. Решить самостоятельно пример.
4. Подвести итоги и дать задание для самостоятельной работы.
2) Вопросы для подготовки
1. Постановка транспортной задачи.
2. Сведение задачи открытого типа к задаче закрытого типа.
3. Построение первоначального опорного плана методами северо-западного угла и
наименьших затрат.
4. Помеченный цикл и сдвиг по нему.
5. Критерий оптимальности опорного плана транспортной задачи.
6. Нахождение потенциалов.
7. Алгоритм метода потенциалов.
3) Справочные материалы
[2], Глава II, §3. Транспортная задача
3.1. Постановка и математическая модель транспортной задачи
3.2. Теоретические основы решения транспортной задачи
3.3. Алгоритм метода потенциалов.
3.4. Сведение задачи открытого типа к задаче закрытого типа.
4) Практические задания
1. Разобрать примеры 1, 2, 5 из §3, и пример из пункта 3.3.5.
2. Решить упражнение 3.5.1.1) под руководством преподавателя.
3. Решить упражнение 3.5.1.2) самостоятельно.
4. Свести задачи упражнения 3.5.3) к задаче закрытого типа.
5. Разобрать примеры 3, 4, 6 9 из §3.
6. Решить упражнение 3.5.2.1) под руководством преподавателя.
7. Решить упражнение 3.5.2.2) самостоятельно.
Д/з: 1. Построить первоначальный опорный план задач упражнения 3.5.3) методами северо-западного угла и наименьших затрат.
2. Решить упражнение 3.5.3).
3. Решить Задание ЛП-6 индивидуальной работы ([2], Приложение 1).
11
4. Подготовиться к лабораторной работе №5 «Решение транспортной задачи
с применением среды Excel» [2], §2, 2.1, 2.2.
Вопросы для самоконтроля:
1. Сформулировать постановку транспортной задачи.
2. Сформулировать математическую модель транспортной задачи.
3. Чем отличается задача открытого типа от задачи закрытого типа?
4. В чѐм заключается метод северо-западного угла построения первоначального
опорного плана?
5. В чѐм заключается метод наименьших затрат построения первоначального опорного плана?
6. Что такое помеченный цикл и сдвиг по циклу?
7. Что такое потенциалы и как они находятся.
8. Сформулировать условие оптимальности транспортной задачи.
9. Сформулировать алгоритм метода потенциалов.
12
Практическое занятие 4. Метод идеальной точки решения многоцелевой
задачи линейного программирования. Сведение
многоцелевой задачи линейного программирования к одноцелевой задаче
1) План практического занятия
1. Повторить теорию по теме.
2. Решить пример под руководством преподавателя.
3. Решить самостоятельно пример.
4. Подвести итоги и дать задание для самостоятельной работы.
2) Вопросы для подготовки
1. Постановка многоцелевой задачи линейного программирования.
2. Метод идеальной точки решения многоцелевой задачи линейного программирования.
3. Метод введения дополнительной переменной решения многоцелевой задачи линейного программирования.
3) Справочные материалы
[2], Приложение 4. §1. Постановка задачи векторной оптимизации и принципиальные подходы к еѐ решению
1.1. Постановка задачи векторной оптимизации
1.2. Принципиальные подходы к решению задачи векторной оптимизации
§2. Многоцелевая задача линейного программирования
2.1. Постановка многоцелевой задачи линейного программирования
2.2. Метод идеальной точки
4) Практические задания
1. Разобрать пример 1 из §2 ([2], Приложение 4).
2. Решить упражнение 1.4а) ([2], Приложение 4) (соответствующим методом) под
руководством преподавателя.
3. Решить упражнение 1.4б) (соответствующим методом) самостоятельно.
Д/з: 1. Решить Задание 1 индивидуальной работы из [2], Приложение 7.
2. Подготовиться к лабораторной работе №7 «Решение многоцелевой задачи
линейного программирования сведением к одноцелевой»: [2], Приложение 4, §2, 2.1.
Вопросы для самоконтроля:
1. Сформулировать постановку многоцелевой задачи линейного программирования.
13
2. Сформулировать математическую модель многоцелевой задачи линейного программирования.
3. В чѐм заключается метод идеальной точки решения многоцелевой задачи линейного программирования?
4. В чѐм заключается метод введения дополнительной переменной решения многоцелевой задачи линейного программирования?
14
Практическое занятие 5. Оптимизация потока в сети. Вычисление числовых характеристик основных видов систем
массового обслуживания
1) План практического занятия
1. Повторить теорию по теме.
2. Решить пример под руководством преподавателя.
3. Решить самостоятельно пример.
4. Подвести итоги и дать задание для самостоятельной работы.
2) Вопросы для подготовки
1. Потоки в сетях и их оптимизация
2. Формулировка задачи и характеристики СМО.
3. Основные виды СМО.
3) Справочные материалы
[2], Приложение 6. Понятие о потоках в сетях и их оптимизации
[2], Приложение 7. §1. Элементы теории случайных процессов
1.1. Понятие Марковского случайного процесса
1.2. Потоки событий
1.3. Уравнения Колмогорова. Предельные вероятности состояние
1.4. Процесс гибели и размножения
§2. Элементы систем массового обслуживания
2.1. Формулировка задачи и характеристики СМО
2.2. СМО с отказами.
2.3. СМО с неограниченным ожиданием
2.4. СМО с ожиданием и с ограниченной длиной очереди
2.5. Примеры: определение эффективности использования трудовых и производственных ресурсов в системах массового обслуживания
4) Практические задания
1. Разобрать пример из [2], Приложение 6.
2. Разобрать примеры 1 3 из §3, [2], Приложение 7.
3. Решить Задания 4 6 индивидуальной работы из [3], Приложение А.
Вопросы для самоконтроля:
1. Что такое поток в сети?
2. Как определяется оптимальный разрез?
3. Сформулировать постановку задачи СМО.
15
4. Перечислить основные характеристики.
5. Перечислить основные виды СМО и их характеристики.
16
Список рекомендуемой литературы
Основная литература
1. Мухаметьянов И.Т. Методические материалы к изучению дисциплин «Методы
оптимизации», «Методы оптимальных решений», «Системный анализ и управление»,
«Исследование операций и методы оптимизации систем». Раздел «Линейное программирование». Лысьва: Изд-во Лысьвенского филиала Пермского национального исследовательского политехнического ун-та, 2015. 154 с.
2. Мухаметьянов И.Т. Учебно-методический комплекс дисциплины «Исследование
операций и методы оптимизации систем». Методические указания по организации, выполнению и контролю самостоятельной работы студентов. Лысьва: Изд-во Лысьвенского филиала Пермского национального исследовательского политехнического ун-та,
2015. ____ с.
Комментариев нет:
Отправить комментарий