Оптимизация сетевой модели комплекса производственных работ. 6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовой  проект

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

Задание курсового проекта …………………………………………...................3

Введение ……………………………………………………………….................6

1. Построение сетевого графика ……………………………………..…............ 8

2. Анализ сетевого графика …………………………………………................ 12

3. Оптимизация сетевого графика …………………………………….............. 13

Заключение …………………………………………………………................... 18

Список используемой литературы ……………………………………............. 19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

Области применения СПУ:

1. Комплексные целевые  научно-технические программы, включающие  НИР, ОКР, проектирование, опытное  производство, испытания сложных  систем.

2. Основная деятельность НИИ и КБ, проектных институтов, предприятий опытного, единичного и мелкосерийного производства.

3. Подготовка и освоение  выпуска новых видов продукции.

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

а) Работа — отображается на сетевом графике стрелками;

б) Событие — отражается на сетевом графике кружками.

Под работой понимается:

- действительная  работа - трудовой процесс, требующий затрат времени и ресурсов;

- ожидание - процесс, требующий затрат только времени;

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

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

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

- промежуточное событие – условие, означающее окончание всех работ, предшествующих данному событию и возможность начала выполнения последующих работ комплекса.

• конечное событие – условия, определяющие достижение конечных целей выполнения комплекса работ.

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

Цель  курсового проекта — определить минимальную стоимость комплекса производственных работ при заданной продолжительности его выполнения и других указанных условиях.

 

1. Построение  сетевого графика

 

Сетевой график - это связанный упорядоченный взвешенный орграф без контуров (петель).

Для построения сетевого графика нужно:

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

При построении сетевого графика для СПУ должны учитываться  следующие четыре правила:

• график должен иметь только одно начальное событие (исток) и только одно конечное событие (сток);
• ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы;
• ни одна работа, выходящая из какого-либо события, не может начаться до тех пор, пока не произойдет данное событие;
• график должен быть упорядоченным.

 

 

В построенном сетевом  графике 6 событий-вершин и 7 работ-дуг. Построение сетевого графика производится по первой таблице исходных данных.

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

Начальным событием –  истоком I является «начало работ», а завершающим событием – стоком S – «готовность изделия». Поэтому нумеруем их соответственно числами 1 и 6.

 

 

Из таблицы 1 видно, что  событие 1 (по горизонтали) является началом  одной работы-дуги, завершающиеся в событии (по вертикали). Её обозначим по порядку 2. То же событие по горизонтали обозначаем тем же числом.

Из события 2 (по горизонтали) выходит одна работа-дуга, которая ведёт к соответствующему событию (по вертикали) - 4. Соответствующему событию по горизонтали  присвоим то же число.

Из события 3 (по горизонтали) выходит одна работа-дуга, которая ведёт к соответствующему событию по вертикали 4.

Из события 4  ведут  три работы-дуги, которые ведут к соответствующим событиям по вертикали, которые нумеруем – 3, 5, 6.

        Из события 5 (по горизонтали) выходит одна работа-дуга, которая ведёт к соответствующему событию по вертикали 6.

 

Таблица 3.

 

События                (предки)   События (потомки)	Начало работ (1)	Готовность деталей (3)	Готовность документации (5)	Поступление дополнительного оборудования (2)	Готовность блоков (4)
Готовность деталей (3)				Изготовление деталей (4/3)
Готовность документации (5)				Подготовка документации (5/2)
Поступление дополнительного оборудования (2)	Закупка дополнительного  оборудова ния (10/5)
Готовность блоков (4)		Сборка блоков (6/4)	Составление инструкций (11/6)
Готовность изделия (6)				Установка дополнительного  оборудования (12/6)	Компоновка изделия (9/6)

 

Таким образом, оказались  пронумерованы все события. Используя  эту нумерацию, а также указанные веса дуг, построим график (Рисунок1.).

 

 

 

 

 

Рисунок 1.

 5/2

 10/5 4/3 11/6

  12/6 

 6/4

9/6

 

 

Полученный график оказался неупорядоченным, т.к. предок 5 предшествует потомку 4 (5<4). Поэтому эти числа  необходимо поменять местами, чтобы получить упорядоченный граф – сетевой график.

Тогда получим окончательный  сетевой график.

Рисунок 2.

 

 5/2

 10/5 4/3 11/6

  12/6 

 6/4

9/6

 

 

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

 

 

 

Таблица 4

Работы	Нормальный вариант		Ускоренный вариант		Прирост затрат на одни сутки  ускорения
	Время (сутки)	Затраты (у.е.)	Время (сутки)	Затраты (у.е.)
2-3	4	100	3	120	20
1-2	10	150	5	225	15
3-5	6	50	4	100	25
2-4	5	70	2	100	10
2-6	12	250	6	430	30
4-5	11	260	6	435	35
5-6	9	180	6	300	40
	Всего	1060	Всего	1710

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Анализ сетевого  графика

 

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

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

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

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

Таблица 5.

Полные пути	Продолжительность (сутки)
	Нормальный режим	Ускоренный режим
1-2-6	22	11
1 -2-4-5-6	35	19
1-2-3-5-6	29	18

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

3. Оптимизация сетевого  графика

 

С каждой работой, имеющей  определенный неизменный объем, связаны  затраты на ее выполнение. Затраты  на выполнение работы с неизменным  объемом возрастают с уменьшением  ее продолжительности и снижаются  при увеличении ее продолжительности.

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

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

Оптимизация сетевого графика может осуществляться по следующим двум критериям:

- минимизация времени  выполнения комплекса работ при  заданных затратах на это выполнение;

- минимизация затрат  на выполнение комплекса работ  при заданном времени этого  выполнения.

Таким образом, нельзя добиться выполнения комплекса работ одновременно в минимальные сроки и с наименьшими затратами.

 

Оптимизируем по критерию минимизации затрат сетевой график при заданной продолжительности выполнения всего комплекса работ – 26 дней.

Представим алгоритм решения поставленной оптимизационной задачи первым способом (нормальный вариант выполнения комплекса работ) в таблице:

 

 

 

 

 

 

Таблица 6

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток	Продолжительность полного пути			Общий прирост затрат
				1-2-6	1 -2-4-5-6	1-2-3-5-6
0	-	-	-	22	35	29
1	10	2-4	(3)  3	-	32	-	30
2	15	1-2	(5)  5	17	27	24	75
3	20	2-3	(1)  0	-	-	-	-
4	25	3-5	(2)  2	-	-	-	-
5	30	2-6	(6)  0	-	-	-	-
6	35	4-5	(5)  1	-	26	-	35
7	40	5-6	(3)  0	-	-	-	-
Всего							140

 

На первом шаге рассматриваем  работу 2-4, которая входит во второй путь. Сокращение ее продолжительности производится по максимуму на 3 суток. Получим: 35-3=32. Указанное сокращение продолжительности этой работы приведет к дополнительным затратам, величина которых будет равна 10 х 3 = 30 (у.е.). Эта величина учитывается в таблице в общем приросте затрат.

На втором шаге рассматриваем работу 1-2, которая входит в первый, второй и третий полные пути. Сократим её на максимально возможную величину (на 5). Получим: 22 – 5 = 17; 32 – 5 = 27 и 29 – 5 = 24. Указанное сокращение продолжительности этой работы приведет к дополнительным затратам, величина которых будет равна 15 х 5 = 75 (у.е.). Эта величина учитывается в таблице в общем приросте затрат.

Работа 2-3, 3-5 входящие в третий полный путь, не требуют сокращения, так как они меньше заданной.

Работа 2-6, входящую в первый полный путь, также не требует сокращения, так как она меньше заданной.

       На  шестом шаге рассмотрим работу 4-5, входящую во второй полный  путь. Сократим её на минимальное  число суток (1). Получим: 27-1=26. Дополнительные  затраты будут равны: 35 х 1=(35 у.е.).

Работа 5-6, входящая во второй и третий полные пути, не требует сокращения, так как она меньше заданной.

Суммарные дополнительные затраты на произведенное сокращение продолжительности работ равно:  30+75+35 = 140 (у.е.).

 

Анализ  полученных результатов на оптимальность.

 

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

 Теперь подсчитав  суммарные дополнительные затраты на произведенное сокращение продолжительностей работ (140 у.е.) и зная первоначальную стоимость (1060 у.е.) всего комплекса работ в рассматриваемом нормальном варианте его выполнения, получим, что при снижении продолжительности выполнения всего комплекса работ с 35 суток (критический путь) до 26 суток оптимальные затраты составят  1060 + 140 = 1200 (у.е.).

 

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

Таблица 7.

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток	Продолжительность полного пути			Общее снижение затрат
				1-2-6	1-2-4-5-6	1-2-3-5-6
0	-	-	-	11	19	18
1	40	5-6	(3)  3	-	22	21	-120
2	35	4-5	(5)  4	-	26	-	- 140
3	30	2-6	(6)  6	17	-	-	-180
4	25	3-5	(2)  2	-	-	23	- 50
5	20	2-3	(1)  1	-	-	24	-20
6	15	1-2	(5)  0	-	-	-	-
7	10	2-4	(3)  0	-	-	-	-
Всего							- 510

 

На первом шаге продолжительность  работы 5-6 , входящей во второй и третий пути, может быть увеличена на 3 суток: 19 + 3 = 22 дня и 18+3=21 день. Тогда затраты на эту работу снизятся на 40 х 3 = 120, т. е. - 120 (у. е.).

Рассматривая работу 4-5 на 2 шаге, входящей во второй путь, можно сделать вывод, что ее продолжительность можно увеличить на 4 суток. При этом продолжительность второго пути станет: 22 + 4 = 26. Затраты на работу снизятся 35 х 4 = 140 (у.е.), т. е. – (140 у.е.).

На 3 шаге работу 2-6, входящую  в первый путь увеличиваем на максимальное число суток  (6). Получим: 11 + 6 = 17. Затраты на работу снизятся 30 х 6 = 180 (у.е.), т. е. - 180 (у.е.).

Работа 3-5 на четвёртом  шаге входит в третий путь. Её можно  увеличить на максимально возможную величину суток (2). Получим: 21+2=23. Снижение затрат составит 25 х 2 = 50 (у.е.), т.е. -50 (у.е.).

Работа на пятом шаге 2-3 входит в третий путь. Её можно увеличить на одни сутки. Получим: 23 + 1 = 24. Снижение затрат составит 20 х 1 = 20.

Шестой и седьмой шаги не используем, поскольку работа 1-2 входит в первый, второй и третий пути, а 2-4 входит во второй  путь и это приведет к недопустимому увеличению всего комплекса работ.

Подсчитав суммарное  снижение затрат из-за произведенного увеличения продолжительностей работ (- 120 – 140 – 180 – 50 – 20 = - 510 у.е.) и зная первоначальную стоимость (1710 у.е.) всего комплекса работ в рассматриваемом ускоренном варианте его выполнения, получим, что при увеличении продолжительности выполнения всего комплекса работ с 19 суток (критический путь) до 26 суток оптимальные затраты составят 1710 – 510 = 1200 у.е..

 

Итоговые результаты, полученные обоими способами оптимизации, совпадают:

1. Продолжительность  соответствующих полных путей  после оптимизации совпадают – 17, 26, 24.

2. Стоимость выполнения  всего комплекса работ после оптимизации совпадают 1200.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

На основании исходных данных (перечня событий и работ) был построен сетевой график комплекса  работ. График является связанным (не имеет обособленных вершин), упорядоченным (номер предка меньше номера потомка), взвешенным (работы-дуги имеют продолжительность), без контуров и петель. Указано ожидаемое время выполнения работ.  По этим данным определена продолжительность всех полных путей и найден критический путь. Критическим оказался второй путь — максимальный по продолжительности — 35 суток при нормальном режиме работы и 19 суток при ускоренном режиме работы.

Целью оптимизации сетевой  модели комплекса производственных работ является определение минимальной стоимости комплекса производственных работ при заданной продолжительности его выполнения. Оптимизация проводилась двумя способами:

1. уменьшении продолжительности выполнения работ, начиная с тех, которые дают наименьший прирост затрат;

   2. увеличении продолжительности выполнения работ, начиная с тех, которые дают наибольший прирост затрат.

В первом случае произошло  сокращение количества суток на выполнение комплекса работ до заданного — 26 суток, но при этом увеличилась стоимость выполнения работ.

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

Итоговые результаты, полученные обоими способами оптимизации, совпадают:

1. Продолжительность  соответствующих полных путей после оптимизации совпадают – 17, 26, 24.

2. Стоимость выполнения  всего комплекса работ после оптимизации совпадают 1200.

Список используемой литературы

 

1. Казаков О.Л., Миненко  С.Н., Смирнов Г.Б. Экономико-математическое  моделирование: учебно-методическое  пособие. – М.: МГИУ, 2006 г. – 136 с.

2. Миненко С.Н., Казаков  О.Л., Подзорова В.Н. Экономико-математическое  моделирование производственных  систем: Учебно-методическое пособие.  – М.: ГИНФО, 2002 г. – 128 с