Основные теоремы.

1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл).

2. ДБР x=(x_ij, i=1...,m, j=1...,n) оптимальный тогда и только затем, когда существуют потенциалы u_i, v_j такие, что

v_j – u_i = с_іj, если x_ij - базисная перевозка

v_j – u_i £ с_іj, если x_ij - небазисная перевозка.