Экономико-математические методы и модели в отрасли связи

 

    Нижняя  граница подмножества (5,2) равна:

    H(5,2) = 36 + 0 = 36  <  45

    Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут.

    В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,1).

    В результате по дереву ветвлений гамильтонов  цикл образуют ребра:

    (3,4), (4,6), (6,1), (1,5), (5,2), (2,3),

    Длина маршрута равна F(Mk) = 36

    Литература:

1. Барсук В.А., Губин Н.М., Батый А.Р. Экономико-математические методы в планировании и управлении в отрасли связи.-М.: Радио и связь, 1984. Глава 11, § 11.3, стр. 213.
2. Губин Н.М., Добронравов А.С., Дорохов Б.С. Экономико-математические методы в планировании и управлении в отрасли связи. -М.: Радио и связь, 1993.

     ЗАДАЧА 4. 

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

     В распоряжении организации, выполняющей  этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.

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

     

     Рисунок 1

     РЕШЕНИЕ: 

     Для оптимизации, прежде всего, необходимо рассчитать основные параметры сетевого графика: возможные ранние сроки начала (t_ij^PH) и раннего окончания (t_ij^PI), допустимые поздние сроки начала (t_ij^IH) и позднего окончания (t_ij^Io) , частный (÷ij) и полный резерв времени (R_ij) для выполнения каждой i,j - работы. Расчет параметров выполнить в таблице.

    Перед началом расчета на основании  сетевого графика (рис.1) заполняются колонки 1 и 2 таблицы.

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

Таблица 12- График выполнения работ.

    Для каждой работы в сетевом графике  ранние сроки начала и окончания  определяются переходом от более ранних событий к более поздним. Расчет ранних сроков начала и окончания работ (колонки 3 и 4) ведется от исходного события к завершающему (сверху вниз).

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

    t^ро_ij = 0 + t_ij

    Определяем эти параметры для исходных работ 1-2, 1-3 и 1-4, раннее начало которых равно нулю, а ранее окончание соответственно:

    t^ро_1-2 = 0+2=2

    t^ро_1-3 = 0+5=5

    t^ро_1-4 = 0+6=6

    Затем последовательно определяем ранние параметры для всех других работ. Раннее окончание работ равно раннему ее началу плюс продолжительность самой работы.

    t^ро_ij = t^рн_ij + t_ij Например : t^ро_2-5 = t^рн _2-5 + t_2-5 = 2+4 = 6

    Если  данной работе предшествует только одна работа, то раннее начало данной работы равно раннему окончанию предшествующей работы.

    t^рн_ij = t^ро_hi Например : t^рн_3-6 = t^ро_1-3 = 5

    Если  данной работе предшествуют несколько  работ, то ее раннее начало равно максимальному значению из всех ранних окончаний предшествующих работ t^рн_ij = max { t^ро_hi }.

    Например: t^рн _5-7 = max{t^ро_2-5, t^ро_3-5 }= max{6, 12} = 12

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

    Продолжительность критического пути: t_кр = t^ро_5-7 = 18 дней.

    Затем последовательно определяем поздние параметры всех остальных работ (колонки 5 и 6). Поздние сроки начала и окончания работ определяем от завершающего события к исходному, то есть снизу вверх.

    Позднее начало работы определяется как разность ее позднего окончания и продолжительности самой работы.

    t^пн_ij = t^по_ij - t_ij Например : t^пн_5-7 = t^по_5-7 -t_5-7 = 18-6=12

    Если  у данной работы последующих работ одна, ее позднее окончание равно позднему началу последующей работы

    t^по_ij = t^пн_jk. Например : t^по_4-6 = t^пн _6-7 =16

    Если  за данной работой следует не одна, а несколько работ, то ее позднее  окончание будет равно минимальному значению из всех поздних начал последующих работ.

    t^по_ij = min{t^пн_jk}

    Например, t^по_1-3 = min{t^пн_3-5, t^пн_3-6} = min{5,13}= 5

    После расчета ранних и поздних временных  параметров работ определяем полный и частный резервы времени (колонки 7 и 8).

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

    Полный  резерв равен разности позднего и раннего начала или позднего и раннего окончания всех работы.

    R_ij = t^пн_ij - t^рн_ij = t^по_ij - t^ро_ij.

    Например : R_4-6 = t^по_4-6 - t^ро_4-6 = 16 – 8 = 8

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

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

    r_ij = t^рн_jk - t^ро_ij Например : r_2-5 = t^рн_5-7 - t^ро_2-5 = 12 - 6= 6.

    Затем находим работы, образующие критический путь, у них резервы времени равны нулю. В нашем примере это работы 1-3, 3-5 и 5-7.

    Известно, что в распоряжении организации  имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой. Учитывая это ограничение, определить сроки выполнения работ. На основании данных о продолжительностях работ, возможных сроков их раннего начала и окончания строим линейный календарный план выполнения работ по ранним началам некритических работ (таблица 13) указав, сколько исполнителей ежедневно занято на выполнении каждой конкретной работы. Суммируя количество рабочих на каждый день по всем работам и построив по этим данным график движения рабочих, видно, что в какие-то дни суммарное число работников оказалось больше заданного ограничения. Следовательно, сетевой график с точки зрения использования рабочих составлен неудовлетворительно и должен быть скорректирован с учетом имеющихся ограничений по количеству рабочих. Корректировка возможна за счет использования имеющихся у работ резервов времени - частного и полного. Продолжительность работ увеличиваем в пределах имеющихся резервов с одновременным уменьшением ежедневной потребности в исполнителях.

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

    Работу 1-2 продолжительностью два дня оставляем без изменения.

    Работу  1-3 (критическую) оставляем без изменения, так как резерв времени у этой работы равен нулю.

    Начало  работы 1-4 сдвигаем на два дня, при  этом сокращая количество рабочих с 11 до 8 и увеличивая продолжительность  работы с 6 до 7 дней. 

    Работу 2-5, имеющую трудоемкость 11 человеко-дня и запас времени 6 дней можно передвинуть на 7 дней вправо и сократить ее выполнение до трех дней, при этом количество рабочих увеличится с 11 до 14.

    Работа  3-5 является критической и поэтому остается без изменения.

    Работа 3-6 имеет продолжительность 3 дня. Растягиваем эту работу до 6 дней, уменьшая при этом количество рабочих с 11 до 6, но при этом делаем перерыв между четвертым и пятым днем продолжительностью 3 дня.

    Начало  работы 4-6 передвигаем на 6 дней, не изменяя  сроки и количество рабочих, два дня и 3 человека соответственно.

    Работа  5-7 – критическая, поэтому остается без изменения.

    Работа 6-7 следует за работами 3-6 и 4-6, поэтому  ее начало сдвигается на 6 дней, при  этом увеличиваем ее продолжительность  до 4 дней, а количество рабочих сокращаем до 10 человек.

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

    После корректировки сетевого графика  видно, что каждый день на всех работах  будет занято 28 человек, в 13 и 14 день возможно сократить количество рабочих до 27 человек.