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

 

 

Министерство образования и  науки Российской Федерации федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования  «Московский государственный  индустриальный университет» (ФГБОУ ВПО «МГИУ»)

Кафедра ИДО №74 "Естественно-научные и инженерно-технические дисциплины"

 

 

Курсовая работа
по специальности «Экономико-математическое моделирование»
на тему «Оптимизация сетевой модели комплекса производственных работ»
Группа		Бк08Б22п
Студент		М. И. Макиева
Руководитель проекта		Р. Б. Новрузов

 

 

ДОПУСКАЕТСЯ К ЗАЩИТЕ
Заведующий кафедрой
Оценка	________________	___________

Москва, 2011

 

 

 

 

 

 

 

Содержание

 

 

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

Введение           6

1. Построение сетевого графика       7
2. Анализ сетевого графика        10
3. Оптимизация сетевого графика       11

Заключение          14

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

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

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

 

С математической точки  зрения сетевой график – это связанный орграф без петель и контуров. Основными понятиями СПУ являются работа и событие.

Наглядно граф можно представить как некоторое множество вершин и множество ребер, соединяющих все или некоторые из этих вершин.

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

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

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

Любой путь от истока к стоку называется полным.

Если дугам графа  сопоставлены какие-то числовых характеристики, то граф называется взвешенным, а числовые характеристики – весами.

Подготовка исходных данных для построения сетевого графика включает:

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

При построении сетевых  графиков необходимо соблюдать определенные правила:

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

График должен быть упорядоченным, т.е. порядковый номер "предка" всегда должен быть меньше порядкового номера "потомка".

Построим заданный сетевой график.

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

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

Перечень  событий после нумерации будет выглядеть следующим образом:

1 – начало работ;

2 – готовность деталей;

3 – готовность документации;

4 – поступление дополнительного оборудования;

5 – готовность блоков;

6 – готовность изделия.

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

Рис. 1. Сетевой график

 

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

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

Таблица 1

Исходные данные 2

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

Определим критический  путь в нашем сетевом графике, представим это в таблице 2:

Таблица 2

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

Полные пути	Продолжительность (сутки)
	Нормальный режим	Ускоренный режим
1-2-3-4-6	32	17
1-2-3-5-6	24	15
1-2-4-6	26	14

 

Как видно из таблицы 2, путь 1-2-3-4-6 является критическим при  нормальном и ускоренном режимах, т.к. его продолжительность максимальна  – 32 и 17 суток соответственно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

Существует два способа оптимизации:

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

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

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

Таблица 3

Первый способ решения  оптимизационной задачи

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

Продолжение табл. 3

1	2	3	4	5	6	7	8
3	20	1-2	(1)      1	20	28	25	20
4	25	3-5	(2)      -	-	-	-	-
5	30	4-6	(6)      2	-	26	23	60
6	35	3-4	(5)      -	-	-	-	-
7	40	5-6	(3)      -	-	-	-	-
			всего				+ 110

 

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

Вывод: Подсчитав суммарные дополнительные затраты на произведенное сокращение продолжительности работ (110 у.е.) и зная первоначальную стоимость (1060 у.е.) всего комплекса работ в рассматриваемом нормальном варианте его выполнения, получим, что при снижении продолжительности выполнения всего комплекса работ с 32 суток до 26 суток оптимальные затраты составят:

1060 + 110 = 1170 (у.е.)

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

Таблица 4

Второй способ решения оптимизационной задачи

№ шага	Суточный прирост затрат	Работа	Количество наращиваемых суток	Продолжительность полного  пути			Общее снижение затрат
				1-2-3-5-6	1-2-3-4-6	1-2-4-6
1	2	3	4	5	6	7	8
0	-	-	-	15	17	14	-
1	40	5-6	(3)      3	18	-	-	- 120
2	35	3-4	(5)      5	-	22	-	- 175

 

Продолжение табл. 4

1	2	3	4	5	6	7	8
3	30	4-6	(6)      4	-	26	18	- 120
4	25	3-5	(2)      2	20	-	-	- 50
5	20	1-2	(1)      -	-	-	-	-
6	15	2-4	(5)      5	-	-	23	- 75
7	10	2-3	(3)      -	-	-	-	-
			всего				- 540

 

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

Вывод: Подсчитав суммарное снижение затрат из-за произведенного увеличения продолжительности работ (540 у.е.) и зная первоначальную стоимость (1710 у.е) всего комплекса работ в рассматриваемом ускоренном варианте его выполнения , получим, что при увеличении продолжительности выполнения всего комплекса работ с 17 до 26 суток оптимальные затраты составят:

1710 – 540 = 1770 (у.е.)

 

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

1. продолжительности соответствующих полных путей после оптимизации совпадают –20, 26, 23;
2. стоимости выполнения всего комплекса работ после оптимизации совпадают – 1170 (у.е.).

 

 

 

Заключение

 

Сетевой график – это  связанный упорядоченный взвешенный орграф без контуров. Основными понятиями  СПУ являются работа и событие.

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

Основными параметрами сетевого графика являются: критический путь, резервы времени событий и работ. Путь 1-2-3-4-6 является критическим при нормальном и ускоренном режимах, т.к. его продолжительность максимальна и составляет 32 и 17 суток соответственно.

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

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

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

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

3. продолжительности соответствующих полных путей после оптимизации совпадают – 20, 26, 23;
4. стоимости выполнения всего комплекса работ после оптимизации совпадают – 1170 (у.е.).

Обязательное условие  оптимизации выполнено.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. - М.: Сов. радио, 1967.

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

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

4. Персональные задания на курсовую работу.

5. Учебно-методическое пособие по выполнению курсовой работы.