Индивидуальное задание студента

ЛАБОРАТОРНАЯ РАБОТА № 3

По дисциплине «Имитационное моделирование»

Сетевые модели планирования

Цель занятия:

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

- освоить методы построения сетевого графика;

- освоить методы решения сетевых моделей с помощью

программы MS Excel.

Немного из теории

 

Данная задача является одной из основных при моделировании различных технологических процессов производства и бизнес-процессов в экономике, а также при планировании и управлении проектами выполнения работ самого разного назначения.

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

В тоже время выполнение отдельных операций требует согласования времени начала и окончания отдельных работ, вызванное привлечением денежных средств, ресурсов и исполнителей работ.

В общем случае модель технологических процессов, отражающая последовательность и логическую взаимосвязь выполнения работ, может быть представлена в виде конечного ориентированного графа. При этом отдельные работы интерпретируются в виде дуг графа, а вершины отражают момент начала и окончания соответствующей работы. Временные и количественные оценки проставляются обычно над дугами графа. Событие имеет двойственное значение. Для всех предшествующих работ оно является законченным свершением, а для последующих работ – начальным пунктом их выполнения. Во всяком сетевом графике бывает два особых события, которые не имеют двойственного значения – исходное и завершающее. Исходное событие – это момент начала выполнения комплекса работ. Оно не является результатом предыдущих работ, поэтому в него не входит ни одной стрелки. К особенностям завершающего события относится то, что оно свидетельствует об окончании всех работ и поэтому не имеет ни одной последующей работы. Из этого события не выходит ни одной стрелки.

Основой для построения сетевой модели является полный перечень работ, входящих в данный проект, который готовится специалистами-экспертами данной предметной области. На основе этого перечня формируется упорядоченная таблица работ, в которой все работы логически увязаны на основе технологического процесса данной отрасли.

После упорядочения работ и установления их продолжительности и трудозатрат (стоимости выполнения) определяются временные параметры сетевого графика.

В таблице 1 приведены основные временные параметры сетевых графиков. Важнейшим показателем сетевого графика являются резервы времени. Резервы времени каждого пути показывают, на какую величину может быть увеличена продолжительность данного пути без ущерба для наступления завершающего события. Поскольку каждый некритический путь сетевого графика имеет свой полный резерв времени, то и каждое событие этого пути имеет свой резерв времени.

Таблица 1

Элемент сети	Наименование параметра	Условное обозначение параметра
Событие i	Ранний срок свершения события Поздний срок свершения события Резерв времени события	tp(i) tn(i) R(i)
Работа (i, j)	Продолжительность работы Ранний срок начала работы Ранний срок окончания работы Поздний срок начала работы Поздний срок окончания работы Полный резерв времени работы	t(i,j) tрн(i,j) tpo(i,j) tпн(i,j) tпо(i,j) Rп(i,j)
Путь L	Продолжительность пути Продолжительность критического пути Резерв времени пути	t(L) tkp R(L)

 

Для определения резервов времени по событиям сети рассчитывают наиболее ранние и наиболее поздние сроки свершения событий. Любое событие не может наступить прежде, чем свершатся все предшествующие ему события и не будут выполнены все предшествующие работы. Поэтому ранний (или ожидаемый) срок свершения i-ого события определяется продолжительностью максимального пути, предшествующего этому событию:

, (1)

где – любой путь, предшествующий i-му событию, то есть путь от исходного до i-ого события сети.

Если событие j имеет несколько предшествующих путей, а, следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле

(2)

Задержка свершения события i по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит, и на сроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этого события и продолжительности (длины) максимального из следующих за ним путей не превысит длины критического пути. Поэтому поздний (или предельный) срок свершения i-ого события равен:

(3)

где - любой путь, следующий за i событием, т.е. путь от i-ого до завершающего события сети.

Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле

(4)

Резерв времени R(i) i-ого события определяется как разность между поздним и ранним сроками его свершения:

. (5)

Резерв времени события показывает, на какой допустимый период времени можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения комплекса работ.

Критические события резервов времени не имеют, так как любая задержка в свершении события, лежащего на критическом пути, вызовет такую же задержку в свершении завершающего события. Таким образом, определив ранний срок наступления завершающего события сети, мы тем самым определяем длину критического пути. Отдельная работа может начаться (и окончиться) в ранние, поздние и другие промежуточные сроки. При оптимизации графика, возможно, любое размещение работы в заданном интервале.

Очевидно, что ранний срок t_рн(i,j) начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i, то есть

t_рн(i,j) = t_р(i). (6)

Тогда ранний срок t_ро(i,j) окончания работы (i,j) определяется по формуле

t_ро(i,j) = t_р(i)+ t(i,j). (7)

Ни одна работа не может окончиться позже допустимого срока своего конечного события j. Поэтому поздний срок t_по(i,j) окончания работы (i,j) определяется соотношением:

t_по(i,j) = t_п(j), (8)

а поздний срок t_пн(i,j) начала этой работы – соотношением

t_пн(i,j) = t_п(j) - t(i,j). (9)

Прежде чем рассматривать резервы времени работ, обратимся к резерву времени пути. Такие резервы имеют все некритические пути. Резерв времени пути определяется как разность между длиной критического и рассматриваемого пути:

R(L) = t_kp - t(L ) (10)

Он показывает, насколько в сумме могут быть увеличены продолжительности всех работ, принадлежащих этому пути. Любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени.

Полный резерв времени R_п(i,j) работы (i,j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв R_п(i,j) определяется по формуле

R_п(i,j) = t_п(j) - t_р(i) - t(i,j) (11)

Полный резерв времени работы равен резерву максимального из путей, проходящего через данную работу. Этим резервом можно располагать при выполнении данной работы, если ее начальное событие свершится в самый ранний срок, и можно допустить свершение ее конечного события в самый поздний срок. Важным свойством полного резерва времени работы является то, что он принадлежит не только этой работе, но и всем полным путям, проходящим через нее.

Работы, лежащие на критическом пути, так же, как и критические события, резервов времени не имеют.

Следует отметить, что кроме полного резерва времени работы, выделяют еще три разновидности резервов. Частный резерв времени первого вида R₁ - часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. R₁ находится по формуле

R(i,j)= R_п(i,j) - R(i) (12)

Частный резерв времени второго вида, или свободный резерв времени R_c работы (i,j) представляет собой часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. R_c находится по формуле

R_с(i,j)= R_п(i,j) - R(j) (13)

Независимый резерв времени R_н работы (i,j) - часть полного резерва, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие начинаются в ранние сроки. R_н находится по формуле

R_н(i,j)= R_п(i,j) - R(i) - R(j) (14)

 

Реализацию алгоритма поиска критического пути и определения числовых характеристик сетевой модели рассмотрим на примере. Пусть дана упорядоченная структурно-временная таблица перечня работ по организации выставки-продажи товаров. Требуется построить сетевой график, определить критический путь, критические работы, резервы времени, провести графический анализ комплекса работ.

Таблица 2 – Упорядоченный перечень работ

Содержание работы	Обозначение	Опорные работы	Коэффициент пересчета	Длительность работы
Заказ на оборудование	а1	-	c1 = 0,1	t1=9
Разработка системы учета спроса	а2	-	c2 = 0,2	t2=11
Отбор товара и выписка счетов	а3	а1	c3 = 0,3	t3=4
Завоз товара	а4	а3	c4 = 0,4	t4=4
Завоз оборудования	а5	а1	c5 = 0,5	t5=6
Установка оборудования	а6	а5	c6 = 0,6	t6=5
Выкладка товара	а7	а4	c7 = 0,7	t7=3
Учет наличия товара	а8	а4	c8 = 0,8	t8=6
Оформление зала и витрин	а9	a6,a7	c9 = 0,9	t9=6
Изучение документов учета	а10	а2, а8	с10 =1,0	t10=5
Репетиция выставки-продажи	а11	а9,а10	c11 = 1,1	t11=3

 

1. Для построения сетевого графика события (состояние системы после выполнения какой-либо работы) обозначаются кружками, а работы-стрелками. Обозначим исходное событие цифрой 1, будем учитывать то, что каждая работа опирается на предыдущую (кроме а₁ и а₂). Строим сетевой график (рис.1).

 

 

Данный сетевой график разбивается на четыре пути, имеющих разную последовательность:

 

1 путь: дн.

2 путь: дн.

3 путь: дн.

4 путь: дн.

 

Путь, обладающий наибольшей продолжительностью (3 путь), называется критическим путем. Работы - называются критическими. Для сетевой модели определяют временные характеристики: раннее начало работы, раннее окончание работы, позднее начало, позднее окончание работы.

Расчет временных характеристик сетевого графика включает два этапа. Первый этап – прямой проход обеспечивает вычисление ранних сроков наступления событий. Вычисления начинают с исходного события и заканчивают завершающим. Используется формула .

 

дн.

д.

д.

д.

д.

д.

д.

д.

 

На втором этапе вычисляют поздние сроки наступления событий. Обратный проход начинают с завершающего события. Используется формула . В нашем примере

д.

д.

д.

д.

д.

д.

д.

д.

 

Работа принадлежит критическому пути, если выполняются три условия:

.

Этим условиям удовлетворяет путь №3, критическими работами будут .

 

 

Решение задачи нахождения критического пути сетевого графика c помощью программы MS Excel. В соответствии с содержательной постановкой задачи нахождения критического пути, каждая дуга представляется отдельной операцией производственного процесса, а значения t представляет время выполнения соответствующей операции.

В предположении, что исходный граф является связным и вершина достижима из , требуется определить ориентированный маршрут максимальной длины из начальной вершины в конечную. Введем в рассмотрение следующие булевы переменные , если дуга входит в критический путь (максимальной длины), и , если дуга не входит в искомый маршрут. В этом случае математическую модель задачи о нахождении критического пути можно представить в следующем виде:

 

x max - целевая функция и ограничения:

 

Первое ограничение задает условие начала пути в начальной вершине , второе ограничение определяет условие завершения пути в вершине . Третье условие определяет условие связности пути, то есть искомый минимальный маршрут должен проходить через промежуточные вершины без разрыва. Последнее ограничение определяет условие принадлежности взятой дуги выбранному пути, то есть x =1, если дуга (x x ) принадлежит искомому пути, и x =0, в противном случае.

Зададим конкретные значения параметров графа, воспользовавшись вше приведенным примером (рис.2.)

 

 

Математическая модель задачи – целевая функция:

 

 

Ограничения задачи:

 

 

Для решения задачи посредством программы MS Excel выполним следующие подготовительные действия:

1. Внесем необходимые надписи в рабочий лист в ячейки A1:F1.

2. В ячейки A2:A12 введем индексы начальных вершин, а в ячейки B2:B12- индексы конечных вершин всех ребер множества ребер графа.

3. В ячейки C2:C12 введем значения коэффициентов целевой функции.

4. В ячейку F2 введем формулу вычисления целевой функции: = СУММПРОИЗВ ().

5. В ячейки введем значение левой части первых сумм ограничений:

- в ячейку Е2: = СУММ(D2:D12);

- в ячейку Е3: = D12;

- в ячейку Е4: =D2- СУММ(D4:D5);

- в ячейку Е5: = D4-D6;

- в ячейку Е6: = D5-D7;

- в ячейку Е7: =D6- СУММ(D8:D9);

- в ячейку Е8: = СУММ (D7;D8)-D10;

- в ячейку Е9: = СУММ(D3;D9) – D11;

- в ячейку Е10: = СУММ(D10:D11) – D12.

Внешний вид рабочего листа – исходные данные приведен на рис.3.

Для решения задачи выполним операции главного меню: «СЕРВИС ® ПОИСК РЕШЕНИЯ». После появления диалогового окна «ПОИСК РЕШЕНИЯ» выполним следующие действия:

	А	В	С	D	E	F
					Ограничения	Целевая функция
					=СУММ	=СУММПРОИЗВ (C2:C12;D2:D12)
					=
					= - СУММ
					=
					=
					= -СУММ
					=СУММ
					=СУММ
					=СУММ

 

Рис.3. Рабочий лист - исходные данные

 

1. В поле с именем «УСТАНОВИТЬ ЦЕЛЕВУЮ ЯЧЕЙКУ» введем абсолютный адрес: $F$2.

2. Для группы «РАВНОЙ»задать вариант поиска - «МАКСИМАЛЬНОМУ ЗНАЧЕНИЮ».

3. В поле «ИЗМЕНЯЯ ЯЧЕЙКИ» ввести абсолютный адрес .

4. Зададим ограничений задачи. Для ввода первого ограничения в исходном окне ПОИСК РЕШЕНИЯ выполним следующие действия:

- нажимаем кнопку с надписью «ДОБАВИТЬ»;

- в появившемся окне «ДОБАВЛЕНИЕ ОГРАНИЧЕНИЙ» ввести абсолютный адрес , который отображается в поле с именем «ССЫЛКА НА ЯЧЕЙКУ»;

- в качестве знака ограничения выбрать «=»;

- в качестве значения правой части ограничения ввести с клавиатуры значение 1;

- поместить курсор на кнопку «ДОБАВИТЬ». На экране вновь появится диалоговое окно «ДОБАВЛЕНИЕ ОГРАНИЧЕНИЙ». Остальные четыре ограничения вводятся аналогично.

5. Введем последнее ограничение на булевы переменные. Для этого выполним следующие действия:

- в исходном окне «ПОИСК РЕШЕНИЯ» нажать кнопку «ДОБАВИТЬ»;

- в появившемся дополнительном окне «ДОБАВЛЕНИЕ ОГРАНИЧЕНИЙ» выберем диапазон ячеек , который отображается в поле с именем «ССЫЛКА НА ЯЧЕЙКУ»;

- в качестве знака ограничения в среднем окне выбираем строку «ДВОИЧ»;

в качестве правой части в поле с именем «ОГРАНИЧЕНИЯ» оставим без изменения вставленное программой значение «ДВОИЧНОЕ»;

- для добавления ограничения нажимаем кнопку «ДОБАВИТЬ».

1. Вводим параметры для решения задачи, для чего в диалоговом окне нажимаем кнопку «ПАРАМЕТРЫ». В появившемся окне параметров «ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ» установим отметки в окнах «ЛИНЕЙНАЯ МОДЕЛЬ» и «НЕОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ». После нажатия кнопки ОК в появившемсяокне «ПОИСК РЕШЕНИЯ» нажимаем кнопку «ВЫПОЛНИТЬ».

После выполнения расчетов программой MS Excel будет получено решение задачи (рис.4):

	А	В	С	D	E	F
				Переменные X:	Ограничения	Значение целевой функции

 

Рис.4. Рабочий лист решения задачи

 

 

Анализ полученного численного решения указывает на то, что в критический путь включены дуги Полная продолжительность критического пути оставляет 31 ед.

 

Индивидуальное задание студента

Администрация города Курска рассматривает возможность реконструкции территории бывшей ВДНХ (ул. Энгельса, 140). После сноса старых павильонов проектом предусматривается строительство современного торгового и развлекательного центра с последующей сдачей площадей в аренду торговым фирмам. Работы, которые необходимо выполнить при реализации проекта, а также взаимосвязь работ и время их выполнения (в неделях) указаны в таблице.

Исходя из намеченных мероприятий (таблица исходных данных), необходимо: - построить сетевой график работ;

- определить числовые характеристики сетевого графика;

- определить критический путь и критические работы;

- провести расчеты с использованием пакета MS Excel;

- данные расчетов оформить в виде отчета в формате А4.

Таблица – Исходные данные

Наименование работы

Обозначение работы ai

Предшеству- ющая работа ai-1

Продол- житель- ность t недель

Вариант задания – предпоследняя цифра зачетной книжки, m

Подготовка проекта торгового центра

a1

-

n

Отчуждение земельного участка

a2

-

Подбор арендаторов

a3

-

n

Подготовка документации

a4

a1

n

Согласование документов

a5

a1

n

Получение разрешения на строительство

a6

a2

n

n

Выбор подрядчика

a7

a3

Снос старых строений

a8

a6

n

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

a9

a6

n

Осуществление строительства

a10

a5

n

n

Заключение контрактов

a11

a4

n

Заказ оборудования

a12

a5

n

Отбор товаров и выписка счетов

a13

a11

Завоз товара и оборудования

a14

a10,a9

n

Установка оборудования

a15

a10,a9

Выкладка товара

a16

a7,a8

Оформление зала и витрин выставки

a17

a7,a8

Изучение документов учета

a18

a12,a13,a14

Репетиция открытия выставки

a19

a15,a16,a18

Презентация выставки

a20

a17,a19

 

Примечание: Параметры исходных данных определяются по номеру зачетной книжки студента (пропуска): n – предпоследняя цифра, n -последняя цифра.

Литература

1. Лугинин О.Е. Экономико-математические методы и модели: теория и практика с решением задач: учебн. пособие/ О.Е.Лугинин, В.Н.Фомишина. – Ростов на Дону: Феникс, 2009. – 440 с.

2. Экономико-математические методы и прикладные модели: Учебн. Пособие для вузов / В.В.Федосеев, А.Н.Гармаш и др.; Под ред.В.В.Федосеева. – М.:ЮНИТИ, 2005 – 304 с.

3. Экономико-математические методы и модели: Учебн. Пособие/ кол. авторов под ред. С.И.Макарова. – М.: КНОРУС, 2009. – 240 с.

4. Экономико-математические методы и модели.Задачник: учебно-практическое пособие/ кол. авторов под ред. С.И.Макарова. – М.: КНОРУС, 2009. – 208 с.

 

 

Поделиться:

Воспользуйтесь поиском по сайту: