Применение метода рассмотрим на маршруте, включающем пункты a1, b1, b2 и b4

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

Приведенная матрица показана в табл. 10.16, б. Справа и внизу матрицы показаны константы приведения – минимальные элементы, которые вычитались вначале из строк, а затем из столбцов матрицы.

Таблица 10.16

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

Сумма констант, равная 28, является нижней границей протяженности для всех маршрутов, то есть для множества "все решения".

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

Для этого определяются оценки всех элементов приведенной матрицы как сумму наименьших величин протяженности соответствующей строки и столбца. Например, для нулевого элемента a₁b₁ оценка составит 1 + 15. Оценка показывает на потери от невключения данного элемента в маршрут. Проставим ее в правом верхнем углу (табл. 10.17).

Таблица 10.17

Определение оценок для нулевых элементов матрицы

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

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

Нижняя граница второго подмножества равна сумме значений нижней границы разделяемого множества и величины оценки пары a₁b₁, то есть 28 + 16 = 44. Строку a₁ и столбец b₁ исключают из рассмотрения, то сеть удаляют из матрицы. Выбор в дальнейшем пары b₁a₁ привел бы к нарушению условия о заезде в каждый пункт только по одному разу. Поэтому пара b₁a₁ блокируется, проставляя в соответствующую клетку матрицы знак блокировки ( ) вместо прежнего значения.

4. Преобразованная и приведенная матрица приведена в табл. 10.18. В процессе вычисления констант появились константы, равные 9 и 7 соответственно. Следовательно, протяженность подмножества, включающего пару a₁b₁, увеличивается на 16 (28 + 16 = 44).

Таблица 10.18

Матрица с исключенными строкой a₁ и столбцом b₁

Как видно из табл. 10.18 все пары имеют одинаковые оценки, равные 1. Выбираем, например, пару b₁b₄. Протяженность множества, не включающего пару b₁b₄, увеличивается на 1 (44 + 1 = 45). Исключаем соответствующие столбец и строку из дельнейшего рассмотрения. Столбец b₁ из матрицы удален, поэтому знак блокировки не ставиться (табл. 10.19). В процессе вычисления появилась константа 1, поэтому увеличиваем нижнюю границу на 1 (44 + 1 = 45).

Таблица 10.19

Матрица с исключенными строкой b₁ и столбцом b₄

• ⇐ Назад
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 202122
• 23
• 24
• Далее ⇒