Свойства транспортной задачи

1.ТЗ имеет оптимальное решение тогда и только тогда, когда

(20)

2. Если план X* является оптимальным, то ему соответствует система из m+n чисел u₁,…,u_m и v₁,…,v_n (называемых потенциалами), удовлетворяющих условию:

ui+vj=cij для всех xij>0, (21)

ui+vj≤cij для всех xij*=0, (22)

3. Если все числа a1,...,am и b1,...,bm - целые и выполнено условие (20), то элементы оптимального плана являются целыми числами.

4. Ранг системы векторов условий ТЗ (т.е. число линейно независимых столбцов матрицы ограничений) равен m+n-1. План перевозок X, содержащий ровно m+n-1 ненулевых перевозок, называется опорным планом (ОП) и играет роль д.б.р. в задаче ЛП. План, содержащий меньше чем m+n-1 ненулевых элементов называется вырожденным.

В зависимости от содержательной трактовки чисел с_ij транспортная задача может быть поставлена на минимизацию суммарного расстояния или времени Пробега транспорта или на минимизацию расхода горючего, более общей является открытая модель ТЗ (когда не требуется выполнения равенства (20)) и сетевая постановка ТЗ (когда один и тот же пункт выступает в роди производителя и потребителя),. Открытые ТЗ решаются путем сведения к замкнутой ТЗ (вводятся фиктивные потребители или производители), а для решения сетевых ТЗ существуют специальные методы (например, метод динамического программирования).