Материал: Оптимизация транспортных потоков при перевозке грузов с использованием автомобильного транспорта

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,3=3500, Г2,5=0, Г4,5=4700, Г7,2=3500,

Максимальное значение имеет Г4,5=4700

Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5)

В строке 7 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (7,3) значение бесконечности, чтобы избежать преждевременного замыкания контура.

Текущая Нижняя граница=34600

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,3=3500, Г7,2=3500,

В результате сравнения мы получили 4 одинаковых максимальных Г=3500. Это означает, что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,2=3500

Удалим из матрицы стоимости строку 1 и столбец 2, и присвоим элементу (2,1) значение бесконечности. Внесем в текущий ориентированный граф дугу (1,2)

В строке 2 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (2,1) значение бесконечности, чтобы избежать преждевременного замыкания контура.

Текущая Нижняя граница=34600

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (1, 2), (2, 3), (7, 1)

------------------------------------------------------------------------

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,2. Удалим из матрицы стоимости строку 2 и столбец 7. Внесем в текущий ориентированный граф дугу (7,2)

В строке 2 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (2,3) значение бесконечности, чтобы избежать преждевременного замыкания контура.

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (7, 2), (1, 3), (2, 1)

------------------------------------------------------------------------

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,3. Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (2,3)

В строке 7 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (7,2) значение бесконечности, чтобы избежать преждевременного замыкания контура.

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 3), (1, 2), (7, 1)

------------------------------------------------------------------------

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,1. Удалим из матрицы стоимости строку 1 и столбец 2. Внесем в текущий ориентированный граф дугу (2,1)

В строке 1 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (1,2) значение бесконечности, чтобы избежать преждевременного замыкания контура.

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

НГр=38100

Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 1), (1, 3), (7, 2)

------------------------------------------------------------------------

Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,6. Удалим из матрицы стоимости строку 6 и столбец 7. Внесем в текущий ориентированный граф дугу (7,6)

В строке 6 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (6,7) значение бесконечности, чтобы избежать преждевременного замыкания контура.

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,5=0, Г2,7=2300, Г3,4=1800, Г4,3=1800, Г5,2=700, Г6,5=5000,

Максимальное значение имеет Г6,5=5000

Удалим из матрицы стоимости строку 6 и столбец 5. Внесем в текущий ориентированный граф дугу (6,5)

В строке 5 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (5,7) значение бесконечности, чтобы избежать преждевременного замыкания контура.

Текущая Нижняя граница=32800

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,4=1800, Г4,3=6500, Г5,2=700,

Максимальное значение имеет Г4,3=6500

Удалим из матрицы стоимости строку 4 и столбец 3. Внесем в текущий ориентированный граф дугу (4,3)

В строке 3 и столбце 4 отсутствует элемент равный ∞. Присвоим элементу (3,4) значение бесконечности чтобы избежать преждевременного замыкания контура.