Свойства ТЗО и основные теоремы.

1. Ранг сложенной из векторов A_ij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, что допустимое базисное решение задачи (если он существует) имеет не более m+n–1 перевозок x_ij, которые удовлетворяют условие 0<x_ij<r_ij.

2. Решение ТЗО является базисным, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл).

3. ДБР 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 = 0, небазисная перевозка

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