Учебное пособие по решению задач по курсу Экономико-математические методы и модели — Алесинская Т.В
• R ( i ) = T п ( i ) − T р ( i ) – резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом. i Tр(i) R(i) Tп(i) Рис. 8.1. Отображение временных параметров событий на сетевом графике Ранние сроки свершения событий T р ( i ) рассчитываются от исходного (И) к завершающему (З) событию следующим образом: 1) для исходного события И T р ( И ) = 0 ; 2) для всех остальных событий I T р ( i ) = max [T р ( k ) + t ( k ,i ) ], ( k,i ) где максимум берется по всем работам ( k,i ) , входящим в событие i; t ( k,i ) – длительность работы (k,i) (рис. 8.2). k 1 T р (k 1 ) t(k 1 ,i) i Tр(i) . t(k 2 ,i) k 2 T р (k 2 ) Рис. 8.2. Расчет раннего срока T р ( i ) свершения события i
Поздние сроки свершения событий T п ( i ) рассчитываются от завершающего к исходному событию: 1) для завершающего события З T п ( З ) = T р ( З ) ; 2) для всех остальных событий T п (i) = min [T п ( j) − t(i, j)], ( i, j ) где минимум берется по всем работам ( i, j ) , выходящим из события i; t ( k,i ) – длительность работы (k,i) (рис. 8.3).
| j 1 | ||
| t(i, j 1 ) | T п ( j 1 ) | |
| i | . | |
| T п (i) | t(i, j 2 ) | j 2 |
| T п ( j 2 ) |
Рис. 8.3. Расчет позднего срока T п ( i ) свершения события i Временные параметры работ определяются на основе ранних и поздних сроков событий: • T рн ( i, j ) = T р ( i ) – ранний срок начала работы; • T ро ( i, j ) = T р ( i ) + t ( i, j ) – ранний срок окончания работы; • T по ( i, j ) = T п ( j ) – поздний срок окончания работы; • T пн ( i, j ) = T п ( j ) − t ( i, j ) – поздний срок начала работы; • R п ( i, j ) = T п ( j ) − T р ( i ) − t ( i, j ) – полный резерв работы показывает максимальное время, на которое можно увеличить длительность работы ( i, j )
или отсрочить ее начало, чтобы не нарушился срок завершения проекта в целом; • R с ( i, j ) = T р ( j ) − T р ( i ) − t ( i, j ) – свободный резерв работы показывает максимальное время, на которое можно увеличить продолжительность работы ( i, j ) или отсрочить ее начало, не меняя ранних сроков начала последующих работ. Путь – это последовательность работ в сетевом графике (в частном случае это одна работа), в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы. Полный путь – это путь от исходного до завершающего события. Критический путь – максимальный по продолжительности полный путь. Работы, лежащие на критическом пути, называют критическими . Критические работы имеют нулевые свободные и полные резервы. Подкритический путь – полный путь, ближайший по длительности к критическому пути. Для проведения анализа временных параметров сетевой модели используют график привязки , который отображает взаимосвязь выполняемых работ во времени. По вертикальной оси графика привязки откладываются коды работ, по горизонтальной оси – отрезки, соответствующие длительностям работ (раннее начало и раннее окончание работ). График привязки можно построить на основе данных о продолжительности работ. При этом необходимо помнить, что работа ( i, j ) может выполняться только после того как будут выполнены все предшествующие ей работы ( k,i ) . 8.2. Методические рекомендации Задача № 8.01 Компания разрабатывает строительный проект. Исходные данные по основным операциям проекта представлены в табл. 8.1. Постройте сетевую
Решение
Построим сетевую модель и рассчитаем временные параметры событий. При поиске критических путей на сетевом графике будем использовать следующие условия его критичности:
необходимое условие – нулевые резервы событий, лежащих на критическом пути;
достаточное условие – нулевые полные резервы работ, лежащих на критическом пути.
Согласно необходимому условию два полных пути сетевой модели (см. рис.5.7) и могут быть критическими. Проверим достаточное условие критичности для работ (1,2) и (1,3)
Путь , начинающийся с работы (1,3) не является критическим, т.к. как минимум одна из его работ (1,3,) не является критической. Работа (1,3) имеет ненулевой полный резерв, а значит может быть задержана с выполнением, что недопустимо для критических работ.
Таким образом, сетевая модель имеет единственный критический путь длительностью недель. За выполнением работ этого пути необходим особый контроль, т.к. любое увеличение их длительности нарушит срок выполнения проекта в целом.
Рис.5.7. — Сетевой график задачи
Работа D или (2,5) не является критической, ее полный резерв равен 3-м неделям. Это означает, что при задержке работы в пределах 3-х недель срок выполнения проекта не будет нарушен. Поэтому если согласно условию работа D задержится на 4 недели, то весь проект закончится на 1 неделю позже.
Варианты задач для самостоятельного решения
1. Постройте сетевую модель разработки и производства станков, используя упорядочение работ из табл.5.2.
A – cоставление сметы затрат
C – покупка собственного оборудования
D – подготовка конструкторских проектов
E – строительство основного цеха
G – испытание оборудования
H – определение типа модели
I – проектирование внешнего корпуса
J – создание внешнего корпуса
2. Постройте сетевую модель, используя упорядочение работ из табл.5.3.
4. Построение сетевых моделей
№1. Постройте сетевую модель разработки и производства станков, используя упорядочение работ из табл.
A – cоставление сметы затрат
C – покупка собственного оборудования
D – подготовка конструкторских проектов
E – строительство основного цеха
G – испытание оборудования
H – определение типа модели
I – проектирование внешнего корпуса
J – создание внешнего корпуса
№2. Постройте сетевую модель организации выступления хора при свечах, используя данные табл.
A – выбор музыкального произведения
C – размножение нотных партий
E – получение канделябров в прокат
G – установка канделябров со свечами
J – заказ костюмов для хора
L – проверка системы усиления звука
M – настройка системы усиления звука
N – генеральная репетиция хора
№3. Постройте сетевую модель, используя упорядочение работ из табл.
Непосредственно предшествующие работы
№4. Постройте сетевую модель переноса участка воздушной высоковольтной линии, используя упорядочение работ из табл.
A – оценка состава и содержания работ
B – осведомление потребителей электроэнергии о временном отключении системы
C – составление заявки на материалы и оборудование
D – обследование района проведения работ
E – доставка опор и материалов
F – распределение опор по точкам монтажа
H – разметка точек монтажа
K – защита старых проводов
L – протяжка новых проводов
N – выверка провиса новых проводов
P – обесточивание и переключение линий
Q – включение и фазировка новой линии
R – уборка строительного мусора
S – снятие старых проводов
U – доставка неиспользованных материалов на склад
№5. Найдите нарушения правил построения сетевых графиков в сетевой модели на рис.
№6*. Используя данные о непосредственно предшествующих работах, перечислите работы, которые неверно отображены на сетевом графике, устраните найденные ошибки.
Непосредственно предшествующие работы
№ 7. Рассмотрим систему автомобильных дорог в Волоколамском районе Московской области. Поток автомобилей в направлении северо-запад – юго-восток достигает уровня 15000 автомобилей в час в наиболее напряженное время. В соответствии с летней программой текущего ремонта дорог, предусматривающего временное закрытие проселочных дорог и дополнительное ограничение скорости, областная администрация предложила сеть альтернативных путей. Альтернативные пути включают в себя как другие шоссейные дороги, так и городские улицы Волоколамска. Из-за различий в ограничениях на скорость и сложившихся автомобильных потоков мощности дуг сети в значительной степени зависят от того, какие дороги или улицы они отображают. Предлагаемая сеть с мощностями дуг представлена на рисунке:
М ощность потока зависит от направления потока. Например, дорога, отображенная дугой 1-2, имеет мощность 5000 автомобилей в час в направлении от 1 к 2; проектировщики предполагают, что здесь будет введено одностороннее движение, поэтому мощность дуги в направлении от 2 к 1 равна нулю. Поскольку узел 1 является входным и потенциально грозит автомобильными пробками, было бы нежелательно допускать выходной поток в этот узел.
- Найдите путь от въезда в район до выезда, который характеризуется отличными от нуля мощностями на всех его дугах в направлении потока.
- Какой максимальный поток через эту систему (тыс. Автомашин в час) ?
Ответ: Результаты анализа максимального потока показывают, что планируемая сеть дорог не сможет выдержать пиковой нагрузки в 15 тыс. Автомобилей в час. При планировании транспортировки необходимо либо расширить сеть дорог и увеличить действующие мощности потоков на дугах, либо подготовиться к серьезным проблемам, связанных с образованием автомобильных пробок. Если сеть будет расширена или модифицирована, то последующий анализ максимального потока даст возможность определить, в какой степени достигнуто улучшение.
№8. Телефонная компания использует подземную кабельную сеть линий связи для обеспечения высококачественной аудиосвязи между двумя большими городами (узлы 1 и 7 сети). Переговоры осуществляются через серию кабельных линий и соединяющие их узлы сети, как это показано на рисунке. На нем показано также число телефонных переговоров (тыс.), которое допускается одновременно в любой точке времени.
1) Каково максимальное число телефонных переговоров между двумя городами, которое может быть допущено одновременно (тыс. шт.) ?
2 ) Какое число телефонных переговоров должно обеспечиваться кабелем 4-7?
№9. Нефтяная компания «Лукойл» владеет сетью нефтепроводов, через которые нефть перекачивается от месторождений до нефтехранилищ. Часть этой сети представлена на рисунке (пропускная способность нефтепроводов показана в тыс. т/ч).
1 ) Если фирма хочет поставить нефть в хранилище 7 и полностью использовать пропускную способность системы, то, сколько времени займет поставка в седьмое нефтехранилище 10 тыс. т нефти?
2) Если на линии 2-3 случится авария, и она будет закрыта, каким будет максимальный поток для системы (тыс. т/ч)?
№ 10. Химический завод имеет сеть труб, предназначенных для перемещения жидких химических продуктов из одних частей предприятия в другие. Сеть труб и пропускные способности показаны на рисунке.
1) Каков максимальный поток для системы, если компания собирается перегнать из узла 1 в узел 9 столько жидких химикатов, сколько это возможно?
2) Сколько химикатов будет поступать через секцию 3-5?
№ 11. Компания грузовых перевозок осуществляет услуги по перевозке грузов между Воронежем (В) и райцентрами. Если компания получает заказ на обслуживание, она как можно быстрее посылает грузовик в райцентр, из которого поступил заказ. Так как существенны быстрое обслуживание и минимальные транспортные затраты, большое значение приобретает то, что грузовик проследует из Воронежа в соответствующий райцентр по наиболее короткому маршруту. Сеть, представленная ниже, отображает сеть дорог. Расстояния указаны в километрах. Найти кратчайшие маршруты от Воронежа до всех 10 райцентров. Какова длина кратчайшего пути от Воронежа до 10 райцентра.