ТРАНСПОРТНАЯ ЗАДАЧА

Особенности экономико-математической модели транспортной задачи:

• система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

• коэффициенты при переменных системы ограничений равны единице или нулю;

• каждая переменная входит в систему ограничений два раза.

Для математической формулировки транспортной задачи в общей постановке обозначим через c_ij коэффициенты затрат, через м_i - мощности поставщиков, через n_j - мощности потребителей, где m - число поставщиков, n - число потребителей. Тогда система ограничений примет вид:

(16)

(17)

Система (16) включает в себя уравнение баланса по строкам, а система (17) - по столбцам таблицы поставок. Линейная функция в данном случае

. (18)

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (16), (17) найти такое решение , при котором значение линейной функции (18) минимально.

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

Транспортная задача, приведенная в примере (см. ниже), обладает важной особенностью: суммарная мощность поставщиков равна суммарной мощности потребителей, т.е.

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

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

Число r основных переменных транспортной задачи равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).