Тема 5. Транспортная задача

1. Постановка транспортной задачи.

2. Общий подход к решению транспортной задачи.

Краткое содержание темы

Среди задач линейного программирования выделяется класс задач, условия постановки которых в определенной степени позволяют упростить процедуру их решения и определить специфические алгоритмы нахождения этих решений. Этот класс задач получил название "Транспортные задачи".

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A₁, A₂,..., A_m, производящих один и тот же продукт в количествах соответственно a₁, a₂,..., a_m.

Пусть, далее, имеется n потребителей (складов) B₁, B₂,..., B_n с потребностями (вместимостями) соответственно b₁, b₂,..., b_n.

Пусть весь произведенный продукт может быть размещен на складах B₁, B₂,..., B_n при полном их заполнении.

Пусть, наконец, перевозка единицы продукции из пункта A_i в пункт B_j оценивается величиной c_ij (c_ij - заданы).

Необходимо определить наилучший план перевозок по стоимости, т.е. такой план, который давал бы минимальную стоимость перевозок всей произведенной продукции на склады.

Строим математическую модель. Пусть x_ij - количество продукта, перевозимого из пункта A_i в пункт B_j. Из постановки задачи очевидно, что каждый склад вмещает:

.

А так как производится столько продукции, сколько ее потребляется (складируется), то:

(продукт с предприятия вывозится полностью).

Далее, очевидным является то, что количество перевозимой с предприятия на склад продукции не может быть отрицательным, т.е.  (i = 1, 2, ..., m; j = 1, 2, ..., n).

Так как необходимо определить наилучший план перевозок по стоимости, то строим целевую функцию суммарных затрат на перевозки. Она должна быть минимизирована. Такая целевая функция имеет вид:

.

Таким образом, имеем следующую математическую постановку задачи. Найти такие x_ij, которые доставляют минимум линейной форме L, т.е.  и удовлетворяют условиям:

     (1)

     (2)

                                            (3)

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

Рассмотрим теперь подходы к решению транспортной задачи в общем виде, т.е. задачи размерности m x n.

Введем следующие понятия:

· прямоугольная цепь;

· независимые расположения;

· подходящие решения.

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

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

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

Подходящие решения - это последовательность допустимых решений, удовлетворяющих условиям:

· матрица перевозок каждого решения содержит ровно (m+n-1) ненулевых клеток;

· клетки матрицы перевозок независимо расположены.

Можно указать способ нахождения последовательности подходящих решений, для которых транспортные издержки будут постоянно уменьшаться до тех пор, пока не будет достигнуто оптимальное решение с минимальными затратами.

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