5.2. Пример

Решим ТЗ с нижеприводимой матрицей стоимостей, где векторы, расположенные слева от матрицы и над ней, дают величины предложения и спроса соответственно источников и стоков. (Векторы весов здесь не нужны.)

Вышеприведенная матрица редуцируется к следующей:

После нескольких применений шагов 2, 3, 6 и 7 с непосредственвенным обнаружением аугментальной цепи матрица С, векторы

пометки будут такими:

Вычисленное равно 1, а новая матрица С такова:

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

На шаге 2 алгоритм заканчивает свою работу, так как все и решение в вышеприведенной матрице показано отмеченными элементами. Для этой ТЗ минимальная стоимость равна