Использование метода ветвей и границ

    

 

СОДЕРЖАНИЕ 

 

     ЛАБОРАТОРНАЯ  РАБОТА № 1 
 

     Тема: Применение метода «Ветвей и границ» для решения задачи коммивояжера и задачи установления оптимальной последовательности выполнения работ в производстве, сервисе, длительность которых зависит от очередности их выполнения на рабочем месте (4 часа). 

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

     ИНДИВИДУАЛЬНОЕ  ЗАДАНИЕ № 1 

     Имеется 5 городов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояние между городами заданы матрицей А=[a_ij], i=1,…,5; j=1,…,5 отражены в таблице 1.1.

     Таблица 1

 

     Решение

1. Шаг А1. В исходной матрице А знак × уже проставлен в клетках главной диагонали матрицы с северо-западного угла до юго-восточного.
2. Шаг А2. Приведение матрицы

     Таблица 2

 

     Таблица 3

 
 
 
 
 
 
 
 
     

3. Шаг Б. Вычисление нижней границы

     Таблица 4

 

     Нижняя  граница (оценка) множества Е равно 7.

     (НГЕ= ). 

     

4. Шаг В. Выбор претендующей коммуникации на ветвление

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

     d(1;4)=2+0=2

     d(2;4)=5+0=5

     d(3;2)=4+2=6

     d(4;1)=1+0=1

     d(4;5)=3+0=3

     d(5;3)=1+5=6 

     Максимальное  значение понижения рассматриваемых  элементов соответствует наиболее перспективному претенденту на ветвление. Максимальную оценку имеют две пары претендентов на ветвление, а именно: (3;2) и (5;3). В случае равенства максимальных значений для нескольких претендентов выбор из них перспективной коммуникации на ветвление осуществляется произвольно.

     Выбираем  для ветвления пару (5;3). 

     

5. Шаг Г. Разделение подмножества (ветвление)

     Производим  ветвление:

     Е=Е(i;j)͝ (i;j), где Е(i;j)={5;3}, (i;j)={ }

     Вычислим  оценку подмножества (i;j).

     Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е и понижения для наиболее перспективного претендента на ветвление, вычисленного на шаге В. Нижняя граница множества полных циклов Е была вычислена на шаге Б. Следовательно:

     НГ (5;3)=НГЕ+d(5;3)=7+6=13 
 

     

6. Шаг Д. Переход к матрице  меньшего размера (усечение матрицы)

     На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij)

     В приведенной матрице (см. 1.2. шаг А2) матрице вычеркивается пятая строка и третий столбец. Для вновь полученной матрицы повторяется шаг А, то есть осуществляется выставление запрета во избежание образования неполного цикла в клетке 5,3 и проводится ее приведение.

     Таблица 5