Транспортная задача в матричной постановке и ее свойства

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

(6.1)

на множестве допустимых планов

(6.2)

при соблюдении условия баланса

(6.3)

(6.4)

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (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).

Рис. 6.1

6.2. Построение исходного допустимого плана в транс­портной задаче

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла. Суть метода состоит в последова­тельном распределении всех запасов, имеющихся в первом, вто­ром и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте про­изводства или к попытке полного удовлетворения потребно­стей в очередном пункте потребления. На каждом шаге 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)= а_i^(q) - x_i,j, b_j^(q+1)= b_j^(q) - x_i,j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а_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. В связи с этим на практике для по­лучения исходного плана используется другой способ — ме­тод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наи­меньшими ценами.

Несбалансированная задача

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

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