Процес знаходження оптимального маршруту, в задачі комівояжера, методом редукції рядків і колонок розкладається на (n-2) етапа. У межах кожного етапу алгоритм розрахунків однаковий.
Для наглядності, розглянемо конкретний випадок задачі комівояжера, а саме, комівояжер повинен обїхати 5 міст, побувавши в кожному по одному разу і повернутися у початкове. При цьому витрати повинні бути мінімальними.
Тарифи на переміщення між містами знаходяться в наступній таблиці:
Перш ніж приступити до першого етапу, знайдемо можливу верхню межу функції мети. Для цього, вибираємо довільний маршрут , для якого обчислюємо значення функції
. Значення функції мети
повинно бути меншим за
.
Етап 1. Виконуємо редукцію рядків, тобто в кожному рядку знаходимо мінімальний елемент і віднімаємо його від елементів даного рядка. В результаті отримуємо наступну таблицю:
де стовбець містить значення мінімальних елементів кожного рядка.
Далі, виконуємо редукцію колонок – в кожній колонці знаходимо мінімальний елемент і віднімаємо йлго від елементів даної колонки (рядок містить мінімальні елементи кожної колонки).
Після цього, обчислюємо найнижчу можливу межу функції мети.
Тобто, функція мети повинна знаходитьсь в межах
.
Далі провіряємо, чи у кожному рядку і колонці міститься по одному нульовому елементі. Якщо дана умова виконується, то розв’язок припиняється і нульові комірки позначають оптимальний шлях комівояжера з оптимальною функцією мети . Якщо ж дана умова не виконується, то розв’язок продовжується, і переходимо до визначення одного з кроків оптимального шляху комівояжера. Для цього визначаємо величини
та
, які називають штрафами рядків і колонок і заносимо їх у відповідну колонку і рядок таблиці.
Штрафом i-го рядка називається найменше значення даного рядка після першого нуля. Якщо i-й рядок містить дві чи більше нульові комірки, то .
Штрафом j-ї колонки називається найменше значення даної колонки після першого нуля. Якщо j-та колонка містить дві чи більше нульові комірки, то .
Для кожної нульової комірки визначаємо вторинні штрафи за наступною формулою: . Після чого заносимо їх в наступну таблицю:
Далі, знаходимо максимальне значення серед знайдених вторинних штрафів. В нашому випадку найбільшим є . Тобто, в шлях комівояжера потрібно внести комірку (5,3). В результаті, отримуємо нову таблицю, в якій викреслюємо з розгляду п’ятий рядок і третю колонку.
Виходячи з того, що у будь-якому рядку і у будь-якій колонці таблиці комівояжера повинна існувати одна заборонена комірка. В нашому випадку, такої комірки немає у рядку i=3 та колонці j=5. Тому забороняємо дану комірку. В результаті отримуємо нову таблицю, яку використовуємо для розрахунків на другому етапі.
Етап 2. Анілогічно першому етапу виконуємо редукцію рядків і колонок. Отримуємо:
Якщо б дані і
відрізнялися від нуля, то ми повинні були б визначити нову функцію:
і врахувати, що шукане значення функції мети повинно хнаходитись в межах . Виходячи з того, що в нашому випадку всі
і
рівні нулю, ми даний крок пропускаємо.
Знаходимо штрафи рядків і колонок.
Для кожної нульової комірки визначаємо вторинні штрафи.
Серед знайдених значень вторинних штрафів знаходимо максимальне. Це означає, що комівояжер повинен використати на своєму шляху відвідати місто (1,2). В результаті, для третього етапу отримуємо нову таблицю, в якій відсутні рядок i=1 та колонку j=2, та комірка (2, 1) являється забороненою.
Етап 3. Виконуємо редукцію рядків і колонок, а також знаходимо штрафи рядків і колонок.
Для кожної нульової комірки визначаємо вторинні штрафи.
Серед знайдених значень вторинних штрафів знаходимо максимальне і заносимо до оптимального шляху комівояжера місто (3,4). В результаті ми отримали ма таблицю, яка містить два рядки і дві колонкт. На цьому алгоритм припиняється, бо дана таблиця вказує завершальний шлях комівояжера (2,5) і (4,1).
Таким чином, ми отримали маршрут:
з витратами . При цьому виконується умова
.