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

Автор работы: Пользователь скрыл имя, 21 Января 2012 в 11:50, контрольная работа

Краткое описание

На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.

Содержимое работы - 1 файл

Контрольная работа.doc

— 466.00 Кб (Скачать файл)
 

    Нижняя  граница подмножества (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

     РЕШЕНИЕ: 

     Для оптимизации, прежде всего, необходимо рассчитать основные параметры сетевого графика: возможные ранние сроки начала (tijPH) и раннего окончания (tijPI), допустимые поздние сроки начала (tijIH) и позднего окончания (tijIo) , частный (÷ij) и полный резерв времени (Rij) для выполнения каждой i,j - работы. Расчет параметров выполнить в таблице.

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

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

Шифр  работ

i-j

Продолжительность работы,

1 2 3 4 5 6 7 8
1-2 2 0 2 6 8 6 0
1-3 5 0 5 0 5 0 0
1-4 6 0 6 8 14 8 0
2-5 4 2 6 8 12 6 6
3-5 7 5 12 5 12 0 0
3-6 3 5 8 13 16 8 0
4-6 2 6 8 14 16 8 0
5-7 6 12 18 12 18 0 0
6-7 2 8 10 16 18 8 8

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

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

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

    tроij = 0 + tij

    Определяем эти параметры для исходных работ 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 + tij Например : tро2-5 = tрн 2-5 + t2-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 - tij Например : tпн5-7 = tпо5-7 -t5-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).

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

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

    Rij = tпнij - tрнij = tпоij - tроij.

    Например : R4-6 = tпо4-6 - tро4-6 = 16 – 8 = 8

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

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

    rij = tрнjk - tроij Например : r2-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 человек. 

Код работ

i-j

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1-2 2 0
8

8

8

8

                               
1-3 5 0
20
20 20 20 20                          
1-4 6 0
11
11
11

8

11

8

11

8

11

8

 
8
 
8
 
8
                 
2-5 4 6  
11 11 11 11        
14
 
14
 
14
           
3-5 7 0        
14 14 14 14 14 14 14            
3-6 3 0        
11

6

11

6

11

6

 
6
       
6
 
6
       
4-6 2 0            
3
3          
3
 
3
       
5-7 6 0                        
18
18 18 18 18 18
6-7 2 8                
15
15      
 
10
 
10
 
10
 
10
Число рабочих до корректировки 39 39 42 42 42 47 28 28 29 29 14 14 18 18 18 18 18 18
Число рабочих после корректировки 28 28 28 28 28 28 28 28 28 28 28 28 27 27 28 28 28 28

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