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

Автор работы: Пользователь скрыл имя, 30 Ноября 2011 в 16:27, контрольная работа

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

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

Скачать целиком (71.09 Кб) Сколько стоит заказать работу?
Содержимое работы - 1 файл

контрольная ЭММ.doc

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

     Решение:

      Решим данную задачу методом теории графов, известным как метод "ветвей и  границ". 

      Итак, начнем с приведения матрицы исходных данных. Матрица считается приведенной, если в каждой строке и каждом столбце содержит не менее одного нуля.

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

Получаем

                   
  А   Б   В   Г   Д   Е    
А -   6   2   0   0   7   -4
                1   0      
Б 0   -   5   7   0   0   -4
    0               0   1  
В 2   4   -   2   0   6   -6
                    2      
Г 0   6   3   -   12   1   -4
    1                      
Д 0   2   0   10   -   4   -4
    0       2              
Е 6   0   5   1   6   -   -6
        3                  
  0   0   -1   -1   0     -2 32

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

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

      Для построения следующей приведенной матрицы убираем строку и столбец с максимальной характеристикой нуля, в нашем случае ЕБ. Следовательно, получается новая приведенная матрица вида:

  А   В   Г   Д   Е    
А -   2   0   0   7    
            2   0      
Б 0   5   7   0   -    
    0           0      
В 2   -   2   0   6    
                2      
Г 0   3   -   12   1    
    1                  
Д 0   0   10   -   4    
    0   2              

                              -1

      Делаем  матрицу приведенной, вычитая из каждого элемента последнего столбца единицу: 

  А   В   Г   Д   Е    
А -   2   0   0   6    
            2   0      
Б 0   5   7   0   -    
    0           0      
В 2   -   2   0   5    
                2      
Г 0   3   -   12   -    
    0                  
Д 0   0   10   -   3    
    0   2              

                             

      Исключаем строку-столбец ДВ (max – 2) 

      Для создания следующей приведенной  матрицы (матрица у которой в каждой строке и каждом столбце содержится не менее одного нуля) вычитаем наименьший элемент из необходимой строки и столбца и получаем: 

  А   Г   Д   Е    
А -   0   0   6    
        2   0      
Б 0   7   0   0    
    0       0   0  
В 2   2   -   5    
                   
Г 0   -   12   0    
    0           0  

                             

                 

     Аналогично выполняем действия. Исключаем строку-столбец АГ (max - 2)

Итак, получаем новую матрицу: 

  А   Д   Е    
Б 0   0   -    
    2   12      
В 2   -   5    
               
Г -   12   0    
            17  
 

Исключаем ГЕ (max - 17) 

      И получаем матрицу вида:

  А   Д    
Б -   0    
        0  
В 2   -    
           

      -2 

     Делаем  полученную матрицу приведенной, отнимая  от элементов первого столбца  двойку. 

      Получили  матрицу вида: 

  А   Д    
Б -   0    
           
В 0   -    
           

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