6. Транспортная задача

Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||x_i_,_j||_mxn), который минимизирует целевую функцию

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)mn. Матрицы систем уравнений в ограничениях (6.2) и (6.3) имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммировать уравнения (6.2) по m, а с другой — уравнения (6.3) по n, то получим одно и то же значение. Из этого следует, что одно из уравнений в системе (6.2)-(6.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n -1, и ее невырожденный базисный план должен содержать m+n -1 ненулевых компонент.

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта a_i), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (x_i_,_j=0), называют свободными, а ненулевые — занятыми (x_i_,_j>0).

C_1,1	C_1,2	……	C_1,n
X_1,1	X_1,2	……	X_1,n	A₁
C_2,1	C_2,2	……	C_2,n
X_2,1	X_2,2	……	X_2,n	A₂
….	….	….	….	….
C_m,1	C_m,2	……	C_m,n
X_m,1	X_m,2	……	X_m,n	A_m
B₁	B₂	….	B_n

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются а_i⁽^q), а текущих неудовлетворенных потребностей — b_j⁽^q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем а_i⁽⁰⁾= а_i, b_j⁽⁰⁾= b_j. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х_i,_j=min{а_i⁽^q), b_j⁽^q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а_i⁽^q+1)= 0 или b_j⁽^q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b_j⁽^q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (а_i⁽^q)=b_j⁽^q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения c_i_,_j. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

Если сумма единиц товара поставщиков не равна сумме единиц товара потребителей, то задача не сбалансированная (открытая), иначе задача сбалансированная (закрытая).

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

Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план перевозок, составленный, например, методом северо-западного угла). Если данный план не вырожденный, то он содержит m+n-1 ненулевых базисных клеток, и по нему можно так определить потенциалы u_i и v_j, чтобы для каждой базисной клетки (т. е. для той, в которой x_i_,_j > 0) выполнялось условие

Переменные u_i называют потенциалами пунктов производства, a v_j — потенциалами пунктов потребления.

Для этого составьте систему для заполненных(!) клеток плана перевозок: v_j-u_i=c_i_,_j; где c_i_,_j - стоимость перевозки из пункта i в пункт j.

Поскольку система (6.5) содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов можно задать произвольно (например, приравнять v₁ или u₁ к нулю).

После этого остальные неизвестные v_j и u_i - определяются однозначно.

Для того, чтобы допустимый план транспортной задачи x_i_,_j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы u_i, v_j, для которых

Вычислите коэффициенты изменения стоимости (dc_i_,_j) для незаполненных(!) клеток плана: dc_i_,_j = v_j- u_i - c_i_,_j;

Заметьте: если все dc_i_,_j оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительныый элемент dc_i_,_j, то далее ведущей (опорной ) клеткой будет клетка [i,j] (при dc_i_,_j>0).

Для того, чтобы найти новый план перевозок необходимо составить цикл пересчета.

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

Цикл повторяется до тех пор пока все dc_i_,_j не станут отрицательными, т.е. пока не будет получен оптимальный план.