Решение сетевой задачи строительства дороги

Муниципальное общеобразовательное учреждение «Гимназия №20»

Городская научно – практическая конференция « Шаг в будущее»

Секция «МАТЕМАТИКА»

Решение сетевой задачи строительства дороги

по ул. Пушкина

                                                                              Выполнил: ученик 9 и/м класса

                                                                                                  Константинов Алексей,

                                                                              Руководитель: учитель математики

                                                                                                        Сорочкина О.А.

2010 год

Введение

        В настоящее время к значительному кругу практических задач широко применяют понятие «сеть», «сетевая модель», «сетевые методы», « сетевой анализ».

        Обратимся к словарю и попробуем разобраться в терминологии:

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

          2) что – либо, напоминающее своим внешним видом множество скрещенных, переплетенных линий, нитей, волокон.

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

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

Метод – ( от греческого methodos – способ) – прием, способ познания или образ действия.

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

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

        Примеров сетевых моделей в повседневной жизни можно привести достаточное количество. Это:

– карты дорог города, области или страны;

– аналогичные карты электрических сетей;

– сети водоснабжения поселка или города;

– канализационные системы;

– оросительные сети;

– газопроводные сети;

– телефонные сети;

– сети авиалиний;

– градусные сети;

– агентурные сети.

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

        В последнее время интерес к сетям неимоверно вырос. Это связано как с увеличением объемов реальных сетей и поэтому невозможностью их решения другими способами, кроме как с использованием сетевых методов, так и с более глубоким изучением внутренних свойств сетей и открытием на этой почве новых сетевых методов, которые могут быть применены к более широкому кругу практических задач. Данная работа посвящена решению сетевой задачи, связанной со строительством дороги по ул. Пушкина. Такой выбор сделан потому, что если я сам буду строителем дорог или архитектором и тому подобное, надеюсь, в дальнейшем эта работа мне поможет.

Цель работы: составление диаграммы работ или сетевого проекта при строительстве дороги по ул. Пушкина.

Для достижения обозначенной цели я поставил перед собой следующие задачи: 

1. Познакомиться с различными видами сетей и их структурой.
2. Рассмотреть методы решения сетевых задач
3. Применить полученные знания к сетевому проекту на строительство дороги.
4. Оформить результаты работы в виде проекта.

Объект моего исследования: сетевые задачи.

Предмет: сетевое проектирование.

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

4

1. Теоретическая часть.

                                                 1.1. Сети.

        Сети могут быть ненаправленными, направленными и смешенными. Кроме того они могут быть полными, неполными, двудольными и представлять собой сеть – дерево.

        Что бы понять терминологию, принятую в теории сетей, обратимся в качестве примера к транспортным сетям.

1) Ненаправленная сеть.

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

– для вершин V  = {1,2,3…, 24}

– для ребер     Е  = {(1,2), (1,3),…, (23,24}

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

2) Сеть – дерево.

Карта дорог, на которой показаны наилучшие маршруты « в город» и « из города», представляет собой сеть – дерево. Рис.2 – пример такой карты маршрутов « в » и « из » города 1 для сети дорог с рис.1. Данная сеть носит такое название потому, что обладает основным свойством дерева: любая новая ветка не соединяется с другой веткой. Чтобы определить структуру дерева, вводится понятие пути от начальной вершины к конечной  как последовательность  различных вершин и соединяющих их ребер. На рис.1 последовательности

                                                  9,   (9,10),  10,(10,12)  12(12,18) и

                                                  9,   (9,1),    1(1,13),   13(13,18)

являются двумя путями от вершины 9 до вершины 18.

Циклом называют путь, в котором начальная и конечная вершины совпадают. На рис. 1 последовательность

                                                  2, (2,3),  3, (3,4),  4, (4,5),  5, (5,2), 2

является циклом. На рис.2 циклов нет. Если каждая вершина сети связана с каждой другой вершиной, то такая сеть называется связной. Поэтому сеть – дерево можно определить как связную сеть без циклов.

3) Полная сеть.

В качестве полной сети может быть представлена транспортная сеть, на которой показаны транспортные потоки между пятью соседними городами (рис.3). Числа, которыми обозначены ребра сети, представляют транспортные потоки, например, среднее число рейсов в будний день. Так, полное движение между городами 1 и 3 в обоих направлениях составляет 5000 рейсов в день. То что в данной сети потоки движения изображены прямыми, не имеет географического значения: они не являются маршрутами движения. На рис.1 и 2 изображены неполные сети.

5

4) Направленные и смешанные сети.

Рассмотрим карту дорог центрального района большого города ( рис.4), который испытывает транспортные проблемы. Инженеры по движению транспорта пытаются облегчить их, вводя улицы с односторонним движением. Эти улицы на карте показаны направленными ребрами. Алгебраически направленное ребро представляют упорядоченной парой вершиной так, что (1,2) – это не то же самое, что (2,1). Для автомобилиста есть разница между движением  в правильном и неправильном направлениях по улицам с односторонним движением.

        Сеть, имеющая только ненаправленные ребра (рис.1 и 2) называется ненаправленной. Сеть, где все ребра направленные, – направленной (рис.5) и сеть, где и те и другие ребра, – смешанной (рис.4).

5) Двудольная сеть.

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

1.2 Сетевые методы.

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

6

                                                   2. Практическая часть

                2.1 Составление сетевой задачи

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

        Хотя наша дорога небольшая, на разные виды работ можно привлекать разное количество работников транспорта, но такое, чтобы они не мешали друг другу. Это условие поможет нам более произвольно оценить продолжительность каждого вида работ. Обозначим каждый вид работ буквой алфавита, а продолжительность выразим в днях. Занесем это в таблицу:

Составим последовательность операций:

В и Г  должно следовать за  А и Б

Д,Е  должно следовать за  В и Г

Ж,З,И  должно следовать за  Д,Е

2.2 Вычерчивание диаграммы работ

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

7

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

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

        Согласно диаграммы на полное завершение строительства дороги понадобится ? рабочих дней. Начало строительства соответствует вершине 1, а конец – вершине 9.

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

Для нашего случая длительность рёбер (5,6) и (7,9) больше, чем (1,2) потому что работа по прокладыванию электрических сетей может быть растянута или отложена на несколько (не более 4) дней.

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

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

8

Заключение

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

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

9

Литература

Кн. “Новые области применения математике” 1981г.

10