МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЛАДИВОСТОКСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИКИ И СЕРВИСА
КАФЕДРА МАТЕМАТИКИ И МОДЕЛИРОВАНИЯ
Сетевой анализ и оптимальное планирование
Рабочая программа дисциплины
по направлению подготовки
38.03.01 «Экономика»
Профиль Планирование и прогнозирование в бизнесе
Владивосток 2017
Рабочая программа дисциплины «Сетевой анализ и оптимальное планирование» составлена в соответствии с требованиями ФГОС ВО по направлениям подготовки 38.03.01 «Экономика» профиль Планирование и прогнозирование в бизнесе и Порядком организации и осуществления образовательной деятельности по образовательным программам высшего образования – программам бакалавриата, программам специалитета, программам магистратуры (утв. приказом Минобрнауки России от 01.01.01 г. N 1367)
Составители:
, д-р физ.-мат. наук, профессор кафедры математики и моделирования
, доцент, кафедры математики и моделирования,
, канд. экон. наук, доцент кафедры математики и моделирования.
Утверждена на заседании кафедры математики и моделирования от 01.01.2001г., протокол № 9.
Редакция 2017 г. утверждена на заседании кафедры математики и моделирования от 01.01.2001г., протокол № 8
Заведующий кафедрой (разработчика) _____________________
«____»_______________20__г.
1 Цель и задачи освоения дисциплины (модуля)
Целью изучения дисциплины «Сетевой анализ и оптимальное планирование» является задача не только обучить студентов методам сетевого анализа, но и научить их применять данные методы для решения конкретных производственных задач.
Задача сетевого планирования состоит в том, чтобы графически, наглядно и системно отобразить, и оптимизировать последовательность и взаимозависимость работ, действий или мероприятий, обеспечивающих своевременное и планомерное достижение конечных целей.
2 Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенных с планируемыми результатами освоения образовательной программы
Планируемыми результатами обучения по дисциплине, являются знания, умения, владения и/или опыт деятельности, характеризующие этапы/уровни формирования компетенций и обеспечивающие достижение планируемых результатов освоения образовательной программы в целом. Перечень компетенций, формируемых в результате изучения дисциплины, приведен в таблице 1.
Таблица 1 – Формируемые компетенции
Название ОПОП ВО (сокращенное название) | Компетенции | Название компетенции | Составляющие компетенции | |
38.03.01 «Экономика» | ПК-1 | способностью собрать и проанализировать исходные данные, необходимые для расчета экономических и социально-экономических показателей, характеризующих деятельность хозяйствующих субъектов | Знания: | методов сетевого анализа |
Умения: | применять методы сетевого анализа для решения конкретных производственных задач | |||
Владения: | знаниями, которые в дальнейшем могут быть использованы при составлении плана выполнения работ, определении порядка выполнения работ, определении оптимальных сроков выполнения работ с учетом имеющихся ресурсов; |
3 Место дисциплины (модуля) в структуре основной образовательной программы
Дисциплина «Сетевой анализ и оптимальное планирование» относится к дисциплинам по выбору «Блока 1 Дисциплины (модули)» учебного плана направления «Экономика» профиль Макроэкономическое планирование и прогнозирование, профиль Планирование и прогнозирование.
Данная дисциплина базируется на компетенциях, полученных при изучении дисциплин «Алгебра и геометрия», «Дискретная математика».
4. Объем дисциплины (модуля)
Объем дисциплины (модуля) в зачетных единицах с указанием количества академических часов, выделенных на контактную работу с обучающимися (по видам учебных занятий) и на самостоятельную работу по всем формам обучения, приведен в таблице 2.
Название ОПОП | Форма обучения | Индекс | Семестр курс | Трудоемкость (З. Е.) | Объем контактной работы (час) | СРС | Форма аттестации | |||
Всего | Аудиторная | Внеаудиторная | ||||||||
лек | прак | лаб | ПА | КСР | ||||||
Б-ЭУ | ОФО | Б.1.ДВ. Б.02 | 7 | 3 | 60 | 34 | 17 | 9 | 48 | Экзамен |
Таблица 2 – Общая трудоемкость дисциплины
5 Структура и содержание дисциплины (модуля)
5.1 Структура дисциплины (модуля)
Тематический план, отражающий содержание дисциплины (перечень разделов и тем), структурированное по видам учебных занятий с указанием их объемов в соответствии с учебным планом, приведен в таблице 3.
Таблица 3 – Структура дисциплины
№ | Название темы | Вид занятия | Объем час | Кол-во часов в интерактивной и электронной форме | СРС |
1 | Некоторые сведения о графах и сетевых графиках | Лекция | 2 | 2 | |
Практическое занятие | 2 | ||||
2 | Параметры сети | Лекция | 2 | 2 | |
Практическое занятие | 2 | 2 | |||
3 | Отыскание критического пути | Лекция | 2 | 3 | |
Практическое занятие | - | ||||
4 | Необходимые теоремы о критическом пути | Лекция | 2 | 2 | |
Практическое занятие | |||||
5 | Матричный метод решения задачи | Лекция | 2 | 5 | |
Практическое занятие | 2 | 2 | |||
6 | Пронумерованные и непронумерованные сети | Лекция | 2 | 2 | |
Практическое занятие | - | ||||
7 | Укрупненные сетевые графики | Лекция | 2 | 5 | |
Практическое занятие | 2 | ||||
8 | Циклы | Лекция | 2 | 2 | |
Практическое занятие | - | ||||
9 | Задачи при постоянных интенсивностях | Лекция | 2 | 4 | |
Практическое занятие | 2 | 2 | |||
10 | Уплотнение ресурса | Лекция | 2 | 3 | |
Практическое занятие | 1 | ||||
11 | Задачи при переменных интенсивностях | Лекция | 4 | 5 | |
Практическое занятие | 2 | 2 | |||
12 | Минимальной задержки выполнения проекта | Лекция | 2 | 2 | |
Практическое занятие | - | ||||
13 | Различные постановки задачи оптимального распределения ресурсов при заданном времени | Лекция | 2 | 2 | |
Практическое занятие | - | ||||
14 | Минимизация среднеквадратичного уклонения | Лекция | 3 | 4 | |
Практическое занятие | 2 | 2 | |||
15 | Минимизация максимального потребления ресурса | Лекция | 3 | 5 | |
Практическое занятие | 2 | 2 |
5.2 Содержание дисциплины (модуля)
Темы лекций
Тема 1. «Некоторые сведения о графах и сетевых графиках» (2 час.).
Определения графа, симметрического и антисимметрического графа, выходящих из вершины и входящих в вершину дуг, сети, длины дуги. Сетевой график: определения событий, начала и конца проекта пессимистического, оптимистического и наиболее вероятного времени выполнения работы. Правила составления сетевого графика; понятия фиктивной и простой работы. Нумерация событий; метод вычеркивания дуг. Основной алгоритм задачи нумерации, иллюстрация основного алгоритма на примере.
Тема 2. «Параметры сети» (2 час.)
Критическое время и критический путь: понятия длины работы, длины пути, минимального времени наступления события, критического времени проекта, критического пути. Алгоритм вычисления минимальных времен и критического времени, иллюстрация алгоритма на примере.
Тема 3. «Отыскание критического пути» (2 час.).
Формулировка и доказательство необходимого и достаточного условия того, чтобы данный путь был критическим; описание способа нахождения критического пути, основанного на данном критерии; понятие свободного резерва времени; иллюстрация описанного способа нахождения критического пути на примере. Максимальные времена наступления событий: понятие максимального времени наступления события, формула для нахождения максимального времени наступления события, описание алгоритма для нахождения максимального времени наступления события, иллюстрация алгоритма на примере.
Тема 4. «Необходимые теоремы о критическом пути» (2 час.).
Условия принадлежности событий и работы критическому пути: формулировка и доказательство необходимого и достаточного условия принадлежности события критическому пути; формулировка и доказательство необходимого и достаточного условия принадлежности работы критическому пути; понятия критической и некритической работы. Резервы времени: понятия и смысл полного резерва времени и независимого резерва времени; условия совпадения полного резерва времени со свободным; иллюстрация данных понятий на примере. Подкритические работы, коэффициенты напряженности: понятие подкритической работы; способ отыскания подкритической работы; отыскание среди додкритических путей, проходящих через данную работу, только максимальные по длине; иллюстрация описанных приемов на примере конкретного –сетевого графика; введение нового параметра, характеризующего напряженность выполнения каждой работы, так называемого коэффициента напряженности работы; формула для отыскания коэффициента напряженности работы; нахождение коэффициента напряженности конкретной работы для конкретного сетевого графика.
Тема 5. «Матричный метод решения задачи» (2 час.).
Матричный метод реализации алгоритма вычислений минимального и максимального времени наступления события: описание матричного метода вычисления минимального и максимального времени наступления события; нахождение критического времени выполнения проекта и критического пути матричным методом; применение данного алгоритма к случаю непронумерованной сети, а также к случаю табличного задания условий задачи; иллюстрация работы данного алгоритма на примере пронумерованного сетевого графика.
Тема 6. «Пронумерованные и непронумерованные сети» (2 час.).
Вычисление минимального и максимального времени наступления события на графе в случае небольшого количества событий: вычисление минимального и максимального времени наступления события на графе для пронумерованной сети, а также для непронумерованной с помощью вычисления рангов вершин, метода вычеркивания дуг и применения алгоритма вычисление минимального и максимального времени наступления события на графе для пронумерованной сети; иллюстрация данного алгоритма на примере пронумерованного сетевого графика. Вычисление минимального и максимального времени наступления события по таблице в случае представления проекта списком работ: построение по списку работ расширенной таблицы; алгоритм пошагового заполнения дополнительных столбцов расширенной таблицы; получение ответа на последнем шаге заполнения дополнительных столбцов расширенной таблицы; иллюстрация описанного алгоритма на примере табличного задания комплекса работ.
Тема 7. «Укрупненные сетевые графики» (2 час.).
Понятия подграфика, входа и выхода подграфика, внутренних и внешних вершин подграфика, укрупненного сетевого графика данного сетевого графика по подграфику; пример укрупненного сетевого графика некоторого сетевого графика по некоторому подграфику; утверждение о граничных вершинах, соединенных в подграфике некоторым путем; алгоритм определения новых дуг укрупненного сетевого графика; обоснование данного алгоритма; иллюстрация приведенного алгоритма на конкретном сетевом графике; утверждение о равенстве минимальных и максимальных времен наступления события, принадлежащего одновременно исходному графику и его укрупненному по некоторому подграфику графику.
Тема 8. «Циклы» (2 час.).
Выявление циклов: описание алгоритма, который при наличии циклов в сетевом графике, выявляет все события, входящие в цикл, а при отсутствии их вычисляет для каждого события минимальное время наступления этого события; иллюстрация данного алгоритма на конкретном сетевом графике; применение данного алгоритма к вычислению максимального времени наступления каждого события и критического пути; модификации данного алгоритма.
Тема 9. «Задачи при постоянных интенсивностях» (2 час.).
Задачи, заключающиеся в оптимальном распределении ресурсов по работам, т. е. в таком размещении работ, которое при заданных ограниченных ресурсах обеспечило бы выполнение проекта в минимальное время; понятие объема работ. Алгоритм приближенного решения рассматриваемой задачи для случая, когда работы проекта не допускают перерыва в их выполнении и когда работы допускают перерыв в своем выполнении; применение данного алгоритма к случаю, когда учитываются несколько видов ресурсов. Пример, иллюстрирующий применение алгоритма на примере сетевого графика с заданными интенсивностями выполнения соответствующих работ как для случая, когда работы проекта не допускают перерыва в их выполнении, так и для случая, когда работы допускают перерыв в своем выполнении.
Тема 10. «Уплотнение ресурса» (2 час.).
Алгоритм уплотнения ресурсов для случая, когда работы проекта не допускают перерыва в их выполнении и когда работы допускают перерыв в своем выполнении; иллюстрация данного алгоритма на примере проекта, изображенного на линейной диаграмме с заданными интенсивностями выполнения работ как для случая, когда работы проекта не допускают перерыва в их выполнении, так и для случая, когда работы допускают перерыв в своем выполнении.
Тема 11. «Задачи при переменных интенсивностях» (4 час.).
Решение задачи, если для каждой работы известен ее объем в ресурсо-единицах, кроме того, известно, что интенсивность выполнения этой работы ограничена сверху и задана функция наличия данного ресурса в каждый момент времени; требуется так распределить по работам имеющийся ресурс, чтобы проект был выполнен в минимальное время; понятия фронта работ, максимального фронта работ, резерва времени работы данного фронта в данный момент. Алгоритм решения данной задачи; иллюстрация данного алгоритма, примененного к задаче распределения ресурса на каждой работе, с учетом сетевого графика и ограниченности ее интенсивности, чтобы проект можно было выполнить в минимальное время, для некоторого сетевого графика с известными максимальными интенсивностями выполнения работ, объемами работ и величиной ежедневного наличия ресурса.
Тема 12. «Минимальной задержки выполнения проекта» (2 час.).
Понятия функции поставок, интегральных графиков потребности, ресурсно-допустимого времени окончания проекта; алгоритм отыскания минимального ресурсно-допустимого времени окончания проекта при заданных поставках ресурсов, т. е. отыскания минимальной задержки окончания выполнения проекта по сравнению с критическим временем; иллюстрация применения алгоритма для сетевого графика в предположении, что проект выполняется одним ресурсом, поставки заданы.
Тема 13. «Различные постановки задачи оптимального распределения ресурсов при заданном времени» (2 час.).
Понятия среднего квадратичного уклонения потребляемого в момент t ресурса R(t) от его среднего ежедневного потребления, наибольшее по абсолютной величине уклонения потребляемого в момент t ресурса R(t) от его среднего ежедневного потребления, наибольшее ежедневное потребление; различные определения оптимального плана в соответствии с введенными понятиями и соответствующие различные постановки задачи оптимального распределения ресурсов при заданном времени.
Тема 14. «Минимизация среднеквадратичного уклонения» (3 час.).
Алгоритм решения задачи нахождения оптимального плана, в котором под оптимальным планом понимается план, выполненный за данное время и минимизирующий среднего квадратичного уклонения потребляемого в момент t ресурса R(t) от его среднего ежедневного потребления; иллюстрация работы данного алгоритма при приближенном решении задачи оптимального потребления ресурсов при наличии нескольких их видов для сетевого графика при заданных интенсивностях и продолжительностях работ.
Тема 15. «Минимизация максимального потребления ресурса» (3 час.).
Алгоритм решения задачи нахождения оптимального плана, в котором под оптимальным планом понимается план, выполненный за данное время и минимизирующий максимальное потребление ресурса; применение данного алгоритма для случая наличия нескольких видов ресурсов, а также для случая нескольких проектов; иллюстрация работы данного алгоритма на примере проекта, заданного сетевым графиком с двумя ресурсами.
Перечень тем практических занятий
Тема 1. «Некоторые сведения о графах и сетевых графиках» (2 час.).
Построение сетевых графиков. Нумерация событий; метод вычеркивания дуг. Основной алгоритм задачи нумерации.
Тема 2. «Параметры сети» (2 час., «снежный ком»).
Нахождение критического времени и критического пути сетевого графика. Алгоритм вычисления минимальных времен и критического времени.
Тема 3. «Матричный метод решения задачи» (2 час.).
Матричный метод реализации алгоритма вычислений минимального и максимального времени наступления события: описание матричного метода вычисления минимального и максимального времени наступления события; нахождение критического времени выполнения проекта и критического пути матричным методом.
Тема 4. «Укрупненные сетевые графики» (2 час.).
Укрупненного сетевого графика данного сетевого графика по подграфику.
Тема 5. «Задачи при постоянных интенсивностях» (2 час., метод «мозгового штурма»).
Задачи, заключающиеся в оптимальном распределении ресурсов по работам, т. е. в таком размещении работ, которое при заданных ограниченных ресурсах обеспечило бы выполнение проекта в минимальное время; понятие объема работ. Алгоритм приближенного решения рассматриваемой задачи для случая, когда работы проекта не допускают перерыва в их выполнении и когда работы допускают перерыв в своем выполнении; применение данного алгоритма к случаю, когда учитываются несколько видов ресурсов.
Тема 6. «Уплотнение ресурса» (2 час.).
Алгоритм уплотнения ресурсов для случая, когда работы проекта не допускают перерыва в их выполнении и когда работы допускают перерыв в своем выполнении.
Тема 7. «Задачи при переменных интенсивностях» (2 час., метод «мозгового штурма»). Решение задачи, если для каждой работы известен ее объем в ресурсо-единицах, кроме того, известно, что интенсивность выполнения этой работы ограничена сверху и задана функция наличия данного ресурса в каждый момент времени; требуется так распределить по работам имеющийся ресурс, чтобы проект был выполнен в минимальное время; понятия фронта работ, максимального фронта работ, резерва времени работы данного фронта в данный момент. Алгоритм решения данной задачи.
Тема 8. «Минимизация среднеквадратичного уклонения» (2 час., «снежный ком»). Алгоритм решения задачи нахождения оптимального плана, в котором под оптимальным планом понимается план, выполненный за данное время и минимизирующий среднего квадратичного уклонения потребляемого в момент t ресурса R(t) от его среднего ежедневного потребления.
Тема 9. «Минимизация максимального потребления ресурса» (2 час., метод «мозгового штурма). Алгоритм решения задачи нахождения оптимального плана, в котором под оптимальным планом понимается план, выполненный за данное время и минимизирующий максимальное потребление ресурса; применение данного алгоритма для случая наличия нескольких видов ресурсов, а также для случая нескольких проектов; иллюстрация работы данного алгоритма на примере проекта, заданного сетевым графиком с двумя ресурсами.
5.3 Формы и методы проведения занятий по теме, применяемые образовательные технологии
При проведении практических занятиях применяются следующие интерактивные методы обучения:
- метод «мозгового штурма»: метод представляет собой разновидность групповой дискуссии, которая характеризуется сбором всех вариантов решений, гипотез и предложений, рожденных в процессе осмысления какой-либо проблемы, их последующим анализом с точки зрения перспективы дальнейшего использования или реализации на практике;
-«снежный ком»: цель наработка и согласование мнений всех членов группы. При использовании этой техники в активное обсуждение включаются практически все студенты.
Для студентов в качестве самостоятельной работы предполагается выполнения домашних заданий, изучение дополнительных тем.
5.4 Форма текущего контроля
Для студентов в качестве самостоятельной работы предполагается выполнения индивидуальных домашних заданий и контрольных работ:
Контрольные работы проводятся по темам:
1. Построить сетевой график.
2. Минимальные и максимальные времена, критический путь.
3. Свободный, полный и независимый резервы времени
4. Оптимальное распределение ресурсов при постоянных интенсивностях.
Индивидуальные домашние задания (ИДЗ) выдаются на практических занятиях в начале изучения соответствующих тем.
Темы ИДЗ:
1.Отыскание критического пути, максимальные времена наступления событий, условия принадлежности событий и работы критическому пути, определение резервов времени, подкритических работ, коэффициентов напряженности;
2. Укрупнение сетевого графика по ориентированным графам, выявление циклов.
На усмотрение преподавателя темы аудиторных контрольных работ могут быть заменены темами ИДЗ и наоборот.
6 Методические указания для обучающихся по освоению дисциплины
Для обеспечения систематической и регулярной работы по изучению дисциплины и успешного прохождения текущих и промежуточных контрольных испытаний студенту рекомендуется придерживаться следующего порядка обучения:
- самостоятельно определить объем времени, необходимого для проработки каждой темы;
- регулярно изучать каждую тему дисциплины, используя различные формы индивидуальной работы;
- согласовывать с преподавателем виды работы по изучению дисциплины.
По завершении отдельных тем сдавать выполненные работы (ИДЗ, рефераты) преподавателю.
При выполнении индивидуальных домашних заданий необходимо использовать теоретический материал, делать ссылки на соответствующие теоремы, свойства, формулы и др. Решение ИДЗ выполняется подробно и содержит необходимые пояснительные ссылки.
Самостоятельность в учебной работе способствует развитию заинтересованности студента в изучаемом материале, вырабатывает у него умение и потребность самостоятельно получать знания, что весьма важно для специалиста с высшим образованием.
Целью самостоятельной работы студентов является овладение фундаментальными знаниями, профессиональными умениями и навыками деятельности по профилю, опытом творческой, исследовательской деятельности.
Контроль успеваемости осуществляется в соответствии с рейтинговой системой оценки знаний студентов. Оценка по дисциплине определяется по 100-бальной шкале как сумма баллов, набранных студентом в результате работы в семестре. Распределение баллов доводится до студентов в начале семестра.
Основной формой промежуточного контроля уровня подготовки студентов является экзамен, который может проводиться в виде теста, собеседования или по результатам работы в семестре.
В процессе изучения дисциплины «Сетевой анализ и оптимальное планирование» помимо теоретического материала, предоставленного преподавателем во время лекционных занятий, может возникнуть необходимость в использовании учебной литературы.
Наиболее подробно и просто изучаемые темы изложены в книге и «Математические методы сетевого планирования», а также в учебном пособии , , и «Сетевые графики в планировании».
В качестве учебника для формирования практических навыков решения задач по сетевому анализу и оптимальному планированию наилучшим образом подходит учебное пособие , и «Сетевые методы планирования и управления».
Остальные учебники, указанные в списке рекомендованной литературы, характеризуются либо сложностью изложения, либо подробным освещением некоторых тем.
7 Перечень учебно-методического обеспечения для самостоятельной работы
нет
8 Фонд оценочных средств для проведения промежуточной аттестации
В соответствии с требованиями ФГОС ВО для аттестации обучающихся на соответствие их персональных достижений планируемым результатам обучения по дисциплине созданы фонды оценочных средств (Приложение 1).
9 Перечень основной и дополнительной учебной литературы, необходимой для освоения дисциплины (модуля)
а) основная литература
1. Балдин методы и модели в экономике [Электронный ресурс] : учебник / , , ; под общ. ред. . - М.: ФЛИНТА : НОУ ВПО «МПСИ», 2012. - 328 с. - ISBN 978-5-9765-0313-7 (ФЛИНТА), ISBN 978-5-9770-0647-7 (НОУ ВПО «МПСИ»).
Режим доступа http://biblioclub. ru/index. php? page=book_red&id=103331
2. Невежин операций и принятие решений в экономике: Сборник задач и упр.: учебное пособие для вузов/, , - М.: Форум, НИЦ ИНФРА-М, 2015. - 400 с.: 60x90 1/16. - (ВО)(П) ISBN 978-5-91134-556-3
Режим доступа http:///go. php? id=504735
3. Хуснутдинов -математические методы и модели: Учебное пособие / . - М.: НИЦ ИНФРА-М, 2014. - 224 с.: 60x90 1/16. - (Высшее образование). (переплет) ISBN 978-5-16-005313-4
Режим доступа http:///go. php? id=430259
б) дополнительная литература
1. Бухалков на предприятии: Учебник / . - 4-e изд., испр. и доп. - М.: НИЦ ИНФРА-М, 2015. - 411 с.: 60x90 1/16. - (Высшее образование: Бакалавриат). Режим доступа http:///catalog. php? bookinfo=426964.
2. , Чупрынов математики и ее приложения в экономическом образовании: Учеб. - М.: Дело, 2000.
10 Перечень ресурсов информационно - телекоммуникационной сети «Интернет»
а) автоматизированная система учета библиотечных фондов http://lib. vvsu. ru
б) интернет-ресурсы: www. newbook. ru;
11 Перечень информационных технологий, используемых при осуществлении образовательного процесса по дисциплине (модулю)
а) сайт раздаточных материалов (http://study. vvsu. ru);
б) сервер интерактивного тестирования обучаемых (СИТО) (http://cito. vvsu. ru);
12 Электронная поддержка дисциплины (модуля)
нет
13 Материально-техническое обеспечение дисциплины (модуля)
Для проведения лекционных занятий по данной дисциплине используются аудитории, оснащенные мультимедийным оборудованием.
12 Словарь основных терминов
Сетевой график – наглядное изображение проекта в виде графа, который отображает технологическую связь между работами.
Критическое время – это минимальное время выполнения проекта.
Минимальное время появление события – это наиболее раннее время наступления всех работ, выходящих из данного события.
Максимальное время появление события – это наиболее позднее время окончания всех работ, входящих в данное событие.
Полный резерв времени – это max время, на которое можно растянуть продолжительность выполнения данной работы или же сдвинуть начало работы так, что критическое время не меняется.
