На научной международной конференции «Профессиональное образование. Современные аспекты международного сотрудничества», состоявшейся в Израиле в мае 2008 года в докладе Вергуна Т.В. «Инновационные средства обучения в системе высшего образования» отмечалось, что «На современном этапе развития общества вполне уверенно можно говорить о формировании единого образовательного и информационного пространства. Однако в последнее время четко обозначается тенденция избытка информации. До последнего времени было принято считать, что студенту необходимо больше знаний, потому что знание это сила, так как позволяет распоряжаться своей жизнью. Но на современном этапе человеческой цивилизации произошло достаточно серьезное изменение: важным является не факт сбора как можно большего количества информации на определенную тему, а актуализируется проблема так называемого информационного отбора».
В Интернете, а также в магазинах с большим количеством печатных изданий, можно найти много информации по определенным вопросам. Преподаватели помогают студентам помочь в огромном количестве информации отобрать ту, которая действительно поможет в конкретных вопросах. Применение компьютерных программ Microsoft PowerPoint, AutoCAD, Microsoft Excel, с помощью которых создаются тексты, рисунки, заполняются таблицы и т.п., позволяет студенту не только качественно изучить и выполнить задания, расчеты, а также сэкономить время на подготовку необходимых материалов.
При изучении дисциплины «Математика» студенты средних профессиональных учреждений должны овладеть математическими знаниями и умениями, необходимыми в повседневной жизни; для изучения смежных естественнонаучных дисциплин, а также дисциплин профессионального цикла, без знания которых невозможна будущая профессиональная деятельность.
При изучении раздела «Основы дискретной математики», конкретно темы «Основные понятия теории графов», студенты должны не только иметь представление об основных понятиях теории графов: знать определение графа, его элементов, операции над ними, а также уметь решать прикладные задачи.
Мы хотим показать как знания, полученные при изучении указанной темы, студенты могут применять в практической деятельности.
Графические представления – удобный способ иллюстрации различных понятий, отображения исследуемого процесса. Распространенным является представление количественных показателей в виде круговых и столбчатых диаграмм (слайд), по наглядным характеристикам которых можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.
Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы. В теории графов используется геометрический подход к изучению объектов, значительно упрощая их анализ. Основное понятие теории – граф – задается множеством вершин (точек) и множеством ребер (дуг), соединяющих некоторые пары вершин. Пример графа – схема метрополитена: множество станций (вершины графа) и соединяющее их линии (ребра графа). (слайд)
Основоположником теории графов является Леонард Эйлер, опубликовавший в 1736 году решение задачи о кенигсбергских мостах. В городе Кёнигсберге было два острова, соединенных семью мостами так, как показано на рисунке 1.(1.12)
Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши (A, B, C, D), который бы начинался бы с любой из них, кончался на ней же и только один раз проходил по каждому мосту.
Эйлер доказал, что задача не имеет решений. Для этого он обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром). Получился граф, представленный на рисунке 2.(1.13)
Утверждение о невозможности нахождения указанного маршрута эквивалентно утверждению о невозможности обойти граф указанным образом. Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий обхода (специального маршрута): граф должен быть связанным, а каждая его вершина должна быть инцидентна четному числу ребер.
Продемонстрируем понятие графа на следующих примерах.
Почтальон обслуживает одну улицу. Чтобы доставить по некоторому адресу корреспонденцию, он должен знать два числа: первое – номер дома, второе – номер квартиры. Например, числа 15 и 140 означают дом 15, квартира 140. Если числа поменять местами, то получится другой адрес: дом 140, квартира 15. Значит, почтальон должен знать не просто два числа, а пару чисел, т.е. два числа, заданные в определенном порядке. Любая пара элементов обозначается с помощью круглых скобок. Так, пара чисел 15 и 140 есть (15; 140), а пара чисел 140 и 15 есть (140; 15). Пары (15; 140) и (140; 15) не равны, так как у них различны первые элементы. (слайд с ковертами и парами)
На рисунке 3 9 показано изображение пары точек (A; B). Стрелка выходит из первого элемента и входит во второй. Таким способом наглядно изображают не только пары элементов, но и истинные высказывания о них. Такого вида рисунки называют графами.
На рисунке 4 10 изображен еще один граф с вершинами A, B, C, D, M и P. Стрелку, соединяющую две различные или совпадающие вершины графа, называют ребром. Этот граф имеет 7 ребер: AP, PC, CA, AC, MA, AA и DD. Ребра вида AA и DD называют петлями. Ребра AP и PC образуют цепь APC, так как первое ребро выходит из точки A и входит в точку P, а второе выходит из точки P и входит в точку C. На графе можно найти и более длинные цепи, например, MACAP, CAAC. Некоторые цепи на графе могут иметь замыкающее ребро. Так цепь APC имеет замыкающее ребро AC. Начало замыкающего ребра совпадает с началом цепи, а конец – с ее концом.
С помощью графов решаются многие задачи, в том числе задачи на вычерчивание фигур «одним росчерком». Пусть, например, требуется начертить конверт (рис.5 11), не отрывая карандаша от бумаги и не проводя по одному отрезку дважды. Чтобы уточнить задание, надо на эту фигуру наложить неориентированный граф (рис.6 12), т.е. выделить точки, которые будут вершинами графа. Решение задачи состоит в выборе направления на ребрах с таким расчетом, чтобы получилась цепь, содержащая все ребра. Можно доказать, что задача разрешима, если на неориентированном графе имеется нуль или две вершины с нечетным числом ребер. В нашем случае таких вершин две. Значит, предложенную задачу можно решить.
На рисунке 7 13 у каждой вершины неориентированного графа указано число ребер, принадлежащих этой вершине. Так как нечетных чисел четыре, то одним росчерком этот граф начертить нельзя.
При изображении графов не все его детали одинаково важны. Несущественными являются геометрические свойства ребра (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости. На рисунке 8 1.15 приведены одинаковые графы.
При изучении указанной темы, ознакомившись по совету преподавателя с книгой норвежского математика Остина Оре «Графы и их применение», нам стало интересно, как может теория графов понадобиться нам в дальнейшей работе.
Оказалось, что теория графов решает большое число разнообразных задач. Это задачи по анализу графов, определению характеристик их строения, подсчет графов или их частей, обладающих определенными свойствами. Графы находят применение при проектировании вычислительных машин, в теории программирования, в изучении химических, физических и технологических процессов, в решении транспортных задач, задач сетевого планирования и управления, в проектировании организационных структур управления и т.д.
Рассмотрим сетевой график, используемый в строительстве, который основан на использовании математической модели – графа.
Говоря более привычным для инженера (но менее точным) языком, граф - это набор кружков (прямоугольников, треугольников и проч.), соединенных направленными или ненаправленными отрезками. В этом случае сами кружки (или другие используемые фигуры) по терминологии теории графов будут называться "вершинами", а соединяющие их ненаправленные отрезки - "ребрами", направленные (стрелки) - "дугами". Если все отрезки являются направленными, граф называется ориентированным, если ненаправленными - неориентированным.
Существует два типа сетевых графиков. Мы в своей работе использовали наиболее распространенный тип сетевого графика работ, который представляет систему кружков и соединяющих их направленных отрезков (стрелок), где стрелки отображают сами работы, а кружки на их концах ("события") - начало или окончание этих работ.
 
Рисунок 9 показывает упрощенно лишь одну из возможных конфигураций сетевого графика, без данных, характеризующих сами планируемые работы. Фактически на сетевом графике приводится множество сведений о производимых работах. Над каждой стрелкой пишется наименование работы, под стрелкой - продолжительность, этой работы (обычно в днях).
В самих кружках (разделенных на секторы) также содержится информация, смысл которой будет пояснен в дальнейшем. Фрагмент возможного сетевого графика с такими данными представлен на рисунке 10.
В графике могут использоваться пунктирные стрелки - это так называемые "зависимости" (фиктивные работы), не требующие ни времени, ни ресурсов.
Они указывают на то, что "событие", на которое направлена пунктирная стрелка, может происходить только после свершения события, из которого исходит эта стрелка.
Нумерация событий производится примерно в той последовательности, в какой они будут происходить. Начальное событие располагается обычно с левой стороны графика, конечное — с правой.
Последовательность стрелок, в которой начало каждой последующей стрелки совпадает с концом предыдущей, называется путем. Путь обозначается в виде последовательности номеров событий.
В сетевом графике между начальным и конечным событиями может быть несколько путей. Путь, имеющий наибольшую продолжительность, называется критическим. Критический путь определяет общую продолжительность работ. Все остальные пути имеют меньшую продолжительность, и поэтому в них выполняемое работы имеют резервы времени.
Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).
Особое значение при составлении сетевого графика имеют два понятия:
· Раннее начало работы - срок, раньше которого нельзя начать данную работу, не нарушив принятой технологической последовательности. Он определяется наиболее долгим путем от исходного события до начала данной работы
· Позднее окончание работы - самый поздний срок окончания работы, при котором не увеличивается общая продолжительность работ. Он определяется самым коротким путем от данного события до завершения всех работ.
При оценке резервов времени удобно использовать еще два вспомогательных понятия:
· Раннее окончание - срок, раньше которого нельзя закончить данную работу. Он равен раннему началу плюс продолжительность данной работы
· Позднее начало - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен позднему окончанию минус продолжительность данной работы.
Если событие является окончанием лишь одной работы (т.е. в него направлена только одна стрелка), то раннее окончание этой работы совпадает с ранним началом последующей.
Общий (полный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не увеличивая общую продолжительность работ. Он определяется разностью между поздним и ранним началом (или поздним и ранним окончанием - что то же самое).
Частный (свободный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не меняя раннего начала последующей. Этот резерв возможен только тогда, когда в событие входят две или более работы (зависимости), т.е. на него направлены две или более стрелки (сплошные или пунктирные). Тогда лишь у одной из этих работ раннее окончание будет совпадать с ранним началом последующей работы, для остальных же это будут разные значения. Эта разница у каждой работы и будет ее частным резервом.
Корректировка сетевых графиков производится как на этапе их составления, так и использования. Она состоит в оптимизации строительных работ по времени и по ресурсам (в частности по движению рабочей силы). Если, например, сетевой график не обеспечивает выполнения работ в необходимые сроки (нормативные или установленные контрактом) производится его корректировка по времени, т.е. сокращается продолжительность критического пути. Обычно это делается
· за счет резервов времени некритических работ и соответствующего перераспределения ресурсов
· за счет привлечения дополнительных ресурсов
· за счет изменения организационно-технологической последовательности и взаимосвязи работ, тогда приходится менять конфигурацию графиков (топологию).
Корректировка по ресурсам производится путем построения линейных календарных графиков по ранним началам, соответствующих тому или иному варианту сетевого графика, и корректировки этого варианта.
Разработка такого графика направлена на отражение технологического процесса, а не на его результат. В сетевой модели показателем является результат работы, а конечной целью – ввод объекта в эксплуатацию.
Разработка сетевого графика используется при организации строительства объекта
Например, прежде чем составить конкретный сетевой график для организации строительства производственного цеха по изготовлению строительной оснастки и инвентаря мощностью 6 тыс. тонн в год необходимо:
1) установить исходные данные, сведения об условиях строительства и определении строительного объема вводимого объекта;
2) сведения о выборе способов производства основных строительно-монтажных работ, машин и механизмов;
3) номенклатура (перечень) работ и подсчет их объемов, расчет требуемых затрат труда и машино-смен. Определение состава, объемов, трудоемкости и машиноемкости работ (для необходимо заполнить таблицы).
Только выполнив указанные расчеты, заполнив таблицы (показ лишь части таблицы), можно построить сетевой график организации строительства (показ сетевого графика).
Подчеркнем еще раз, что заполнение таблиц и построение графика, требует знаний специальных дисциплин (связанных с организацией строительства и управления), математики, ЕНиРов (единых норм и расценок на строительные, монтажные и ремонтно-строительные работы). Умение пользоваться компьютерными программами облегчает работу студентов, а в дальнейшем специалистов.
И только после построения сетевого графика можно переходить к проектированию строительного генерального плана, который мы научимся выполнять на выпускном курсе, а также при продолжении обучения по выбранной специальности в высшем учебном заведении.
Это знать, если зададут вопрос: кроме описанного типа сетевых графиков, в котором вершины графа ("кружки") отображают события, а стрелки - работы, существует другой тип, в котором вершинами являются работы. Различие между этими типами непринципиальное - все основные понятия (раннее начало, позднее окончание, общие и частные резервы, критический путь и т.д.) сохраняются неизменными, отличаются лишь способы их записи.
|