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

 

 

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

Кафедра ИДО №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