Транспортировка в цепях поставок

 

     Для маршрута № 2 грузоотправителя Б составим матрицу кратчайших расстояний (табл.15):

     Таблица 15

Матрица кратчайших расстояний для маршрута №2

(грузоотправитель  Б)

 

     В каждой строке находим минимальный  элемент hi и выполним приведение матрицы  по строкам, то есть определим значения lij' по формуле

     lij' = lij – hi, i, j = 1, 2, …, n

     где lij' – элемент новой матрицы  приведенной по строкам.

     Полученный  результат представим в таблице 16. 

Таблица 16

     Матрица кратчайших расстояний, приведенная  по строкам

 

     Далее полученную матрицу необходимо привести по столбцам, используя следующую формулу:

     lij'' = lij' – hj, I, j = 1, 2, …, n

     где  lij'' – элемент новой матрицы после следующего приведения исходной матрицы по столбцам, а hj – минимальный элемент в столбце.

     Результаты представлены в таблице 17.

     Таблица 17

     Матрица кратчайших расстояний, приведенная по столбцам

 

      Определим нижнюю границу (минимально возможную  длину маршрута) по формуле:

     

     

= 22 + 5 = 27 

     Для нулевых элементов матрицы, приведенной в табл. 17, определим оценки Q_ij  (табл.18), которые проставим в правом нижнем углу соответствующей ячейки. Так для нулевого элемента, находящегося на пересечении строки B и столбца 2, оценка Q_Б2 = 0 + 2 = 2 (минимальное значение по строке – 0, а по столбцу – 2). 

     Таблица 18

     Расчет  оценок для нулевых элементов

 
 

      В табл. 18 получили две максимальные оценки равные 4. Для дальнейшего решения выберем одну из них. Пусть ветвь маршрута будет 5-6. Таким образом, исключает из дальнейшего рассмотрения строку k = 5 и столбец s = 6. На пересечении строки 5 и столбца 6 ставим знак M, иначе маршрут замкнется, не охватив другие пункты (табл.19). 
 
 

     Таблица 19

     Расчет  оценок для нулевых элементов

 
 

     От  начальной вершины "все решения" проводят ответвление вершин ks и с нижними границами:

     Графическое изображение полученного решения  приведено на рис. 3. 

Таблица 20

Приведение  матрицы усеченной на строку 5 и  столбец 6 

 

      Рис.3. Первое ветвление «дерева решений» для метода «ветвей и границ»

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

Таблица 21

Расчет оценок для усеченной матрицы 

 
 

     Получены  пять максимальных оценок, равные 2. Выбираем строку Б и столбец 2, на их пересечении вместо элемента ставим М, то есть накладывается запрет на его включение в маршрут или блокирование и снова приводим матрицу по строкам и столбцам (табл.21).

Таблица 22

Приведение матрицы усеченной на строку Б и столбец 2

В каждой строке и столбце присутствует 0, поэтому верхняя граница ветки  Б-2 увеличивается. Полученное ветвление отмечаем на дереве решений (Рис.4). 

      Рис.4. Второе ветвление «дерева решений» для метода «ветвей и границ»

Таблица 23

Определение оценок для усеченной матрицы