Шлыков В.И., Сорокина Е.В., Сочнев А.М.

В.И. ШЛЫКОВ

Е.В. СОРОКИНА

А.М. СОЧНЕВ

ДИСКРЕТНАЯ МАТЕМАТИКА

РАСЧЁТ СЕТЕВОГО ГРАФА

Методические рекомендации

для проведения практического занятия на ЭВТ

Новочеркасское высшее военное командное училище связи 2007

УДК 51

ББК 22.1

С 69

Шлыков В.И., Сорокина Е.В., Сочнев А.М.

Дискретная математика. Расчёт сетевого графа: Метод. рекомендации для выполнения практического занятия на ЭВТ / Новочерк. высш. военное командное училище связи. - Новочеркасск, 2007. – __ c.

Методические рекомендации предназначены для курсантов, выполняющих задания по расчёту сетевого графа в дисциплине “Дискретная математика” в третьем семестре обучения. В пособии представлены необходимые данные для подготовки к работе, выполнения заданий и оформления отчета.

ã Новочеркасское высшее

военное командное

училище связи, 2007

ã Шлыков В.И., Сорокина Е.В.,

Сочнев А.М., 2007

ОГЛАВЛЕНИЕ

1.	ОБЩИЕ СВЕДЕНИЯ О РАБОТЕ	.
2.	ПОСТАНОВКА ЗАДАЧИ НА ИССЛЕДОВАНИЯ
3.	ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
3.1.	Построение таблицы исходных данных
3.2.	Построение сетевого графа
	3.2.1. Первый этап построения графа (установление связей в графе)
	3.2.2. Второй этап построения графа – определение ранних сроков начала и окончания работ (прямой проход)
	3.2.3. Третий этап построения графа – определение поздних сроков начала и окончания работ (обратный проход)
3.3.	Построение календарных графиков работ и определение числовых характеристик распределения рабочих сил
	3.3.1. Нахождение требуемого числа рабочих сил для выполнения всего плана
	3.3.2. Нахождение трудозатрат для выполнения всего плана работ
	3.3.3. Нахождение коэффициента трудопотерь при выполнения всего плана работ
3.4.	Построение сравнительных графиков потребностей в рабочей силе
3.5.	Рекомендации по оформлению результатов исследований
4.	ОСОБЕННОСТИ РАСЧЁТОВ НА КОМПЬЮТЕРЕ
5.	ПРИМЕРНЫЙ ОБРАЗЕЦ ТИТУЛЬНОГО ЛИСТА ОТЧЁТА
6.	БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ОБЩИЕ СВЕДЕНИЯ О РАБОТЕ

Практическое занятие на ЭВТ “Расчёт сетевого графа” по дисциплине “Дискретная математика” проводится в течение четырёх часов с использованием компьютеров кафедры.

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

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

ПОСТАНОВКА ЗАДАЧИ НА ИССЛЕДОВАНИЯ

1. По заданному индивидуальному коду построить таблицу исходных данных (выполняется в отчёте в часы самостоятельной работы, на занятии переносится в компьютер).

2. Построить сетевой граф (выполняется в отчёте в часы самостоятельной работы, на занятии переносится в компьютер).

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

4. Построить сравнительные графики потребностей в рабочей силе (в часы самостоятельной работы делается заготовка в отчёте).

5. Результаты исследований с надлежащими пояснениями привести в отчёте, сформулировать выводы. Отчёты сдать на проверку.

Индивидуальный код содержит шесть цифр:

QÎ[0;5]; KÎ[0;5]; MÎ[0;8]; WÎ[1;5]; GÎ[0;9]; NÎ[0;9].

Этот код предназначен для получения исходных данных с помощью таблицы, показанной на рис.1.

Номер работы	Номера предшествующих работ	Продолжи-тельность	Потребное число р/с
	-	-	-		R1
	-	-	-	W×15	R2
	-	-	-		R3
	-			W×10	R4
	-				R5
	Q	W	K	W×5	R6
	-	W			R7
	-	W+2		W×10	R8
	Q+1		M		R9
	Q+2			W×5	R10

Рис. 1

Как следует из таблицы, предполагается составление сетевого плана для 10 работ, номера которых показаны в первом столбце. Эти работы будем обозначать A1¸A10. Продолжительности работ задаются в 5 столбце.

Некоторые из работ могут начаться не раннее, чем закончится выполнение предшествующих работ, номера которых указаны в 2, 3 и 4 столбцах.

Потребное число рабочих сил устанавливается в 6 столбце согласно формуле:

Особенности расчётов проследим с помощью конкретного примера.

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ

Пусть задан код: 231487.

Это означает: Q = 2; K = 3; M = 1; W = 4; G = 8; N = 7.

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

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

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

Моментом начала всего плана работ будем считать ноль.

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

Потребностей в рабочей силе

Графики потребностей в рабочей силе составляются на основе результатов подсчёта числа занятых рабочих сил на интервалах. Эти графики для полученных трёх календарных графиков работ представлены на рис. 7.

Рис. 7

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

3.5. Рекомендации по оформлению результатов исследований

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

Численные результаты расчётов требуется записать в конце отчёта (перед выводами и подписью). Эти результаты необходимо ввести в проверочную Excel – таблицу.

Для рассмотренного примера численные ответы выглядят следующим образом.

1. Требуемое число р/с 1-го календарного графика MaxРС_1 = 25.

2. Коэффициент трудопотерь 1-го календарного графика КТП_1 » 0,741.

3. Требуемое число р/с 2-го календарного графика MaxРС_2 = 27.

4. Коэффициент трудопотерь 2-го календарного графика КТП_2 » 0,880.

5. Требуемое число р/с 3-го календарного графика MaxРС_3 = 25.

6. Коэффициент трудопотерь 3-го календарного графика КТП_3 » 0,741.

ПРИМЕРНЫЙ ОБРАЗЕЦ ТИТУЛЬНОГО ЛИСТА ОТЧЁТА

КОМАНДНОЕ УЧИЛИЩЕ СВЯЗИ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М; Новосибирск: НГТУ, 2003. – 280 с.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. Пособие. – М.: ФИЗМАТЛИТ, 2004. – 416 с.

3. Плотников А.Д. Дискретная математика: Учебное пособие. – М.: Новое знание, 2005. – 288 с.

4. Спирина М.С. Дискретная математика: Учебник. – М.: "Академия", 2004. – 368 с.

___________________

Учебное издание

Виктор Иванович Шлыков

Елена Владимировна Сорокина

Александр Михайлович Сочнев

ДИСКРЕТНАЯ МАТЕМАТИКА

РАСЧЁТ СЕТЕВОГО ГРАФА

Методические рекомендации

для проведения практического занятия на ЭВТ

Издается в авторской редакции

Редакционно-издательский план 2007 г.

Подписано в печать _._.2007 г. Формат ___.

Бумага офсетная. Печать офсетная.

Печ. л. ____. Уч.-изд. л. _____.

Тираж ___ экз. Заказ №______ .

Типография НВВКУС

346418, г. Новочеркасск, ул. Атаманская, 36

В.И. ШЛЫКОВ

Е.В. СОРОКИНА

А.М. СОЧНЕВ

ДИСКРЕТНАЯ МАТЕМАТИКА

РАСЧЁТ СЕТЕВОГО ГРАФА

Методические рекомендации

для проведения практического занятия на ЭВТ

Новочеркасское высшее военное командное училище связи 2007

УДК 51

ББК 22.1

С 69

Шлыков В.И., Сорокина Е.В., Сочнев А.М.

Дискретная математика. Расчёт сетевого графа: Метод. рекомендации для выполнения практического занятия на ЭВТ / Новочерк. высш. военное командное училище связи. - Новочеркасск, 2007. – __ c.

Методические рекомендации предназначены для курсантов, выполняющих задания по расчёту сетевого графа в дисциплине “Дискретная математика” в третьем семестре обучения. В пособии представлены необходимые данные для подготовки к работе, выполнения заданий и оформления отчета.

ã Новочеркасское высшее

военное командное

училище связи, 2007

ã Шлыков В.И., Сорокина Е.В.,

Сочнев А.М., 2007

ОГЛАВЛЕНИЕ

1.	ОБЩИЕ СВЕДЕНИЯ О РАБОТЕ	.
2.	ПОСТАНОВКА ЗАДАЧИ НА ИССЛЕДОВАНИЯ
3.	ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
3.1.	Построение таблицы исходных данных
3.2.	Построение сетевого графа
	3.2.1. Первый этап построения графа (установление связей в графе)
	3.2.2. Второй этап построения графа – определение ранних сроков начала и окончания работ (прямой проход)
	3.2.3. Третий этап построения графа – определение поздних сроков начала и окончания работ (обратный проход)
3.3.	Построение календарных графиков работ и определение числовых характеристик распределения рабочих сил
	3.3.1. Нахождение требуемого числа рабочих сил для выполнения всего плана
	3.3.2. Нахождение трудозатрат для выполнения всего плана работ
	3.3.3. Нахождение коэффициента трудопотерь при выполнения всего плана работ
3.4.	Построение сравнительных графиков потребностей в рабочей силе
3.5.	Рекомендации по оформлению результатов исследований
4.	ОСОБЕННОСТИ РАСЧЁТОВ НА КОМПЬЮТЕРЕ
5.	ПРИМЕРНЫЙ ОБРАЗЕЦ ТИТУЛЬНОГО ЛИСТА ОТЧЁТА
6.	БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ОБЩИЕ СВЕДЕНИЯ О РАБОТЕ

Практическое занятие на ЭВТ “Расчёт сетевого графа” по дисциплине “Дискретная математика” проводится в течение четырёх часов с использованием компьютеров кафедры.

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

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