Основные свойства ТЗ

Транспортная задача имеет закрытую модель, если суммарный запас равен суммарной потребности, то есть

(5)

иначе будет открытая модель:

(6)

1. ТЗ всегда имеет решение для закрытой модели.

2. Число уравнений задачи (1)-(4) равно (m+n), а число переменных – mn.

3. Коэффициенты при переменных в урвнениях (1) и (2) равны 1.

4. Количество независимых уравнений будет (m+n-1), так как сумма m уравнений (1) всегда равна сумме n уравнений (2) (рассматривается закрытая модель). Значит, базисных переменных будет (m+n-1), а свободных переменных – (m-1)(n-1) (столько нулей, по крайней мере, будет в оптимальном плане).

Методы построения первоначального плана

Решение транспортной задачи проводится в два этапа.

1. На первом этапе находится первоначальный опорный план.

2. На втором этапе на базе опорного плана методом потенциалов определяется оптимальный план.

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

Самыми простыми методами построения первоначального плана ТЗ являются:

Метод северо-западного угла (или диагональный метод).

Метод минимальной стоимости(или минимального элемента, или минимального тарифа).

Метод двойного предпочтения.

Из методов оптимизации первоначального плана самым распространенным является метод потенциалов.