Общие сведения

Классическая формулировка транспортной задачи линейного программирования выглядит так:

· имеется m пунктов отправления А₁, А₂, …, А_m, в которых есть запасы однородного товара в количествах соответственно а₁, а₂, …, а_m единиц;

· имеется также n пунктов назначения В₁, В₂, …, В_n, желающих получить соответственно b₁, b₂, …, b_n единиц товара;

· предполагается, что сумма всех заявок потребителей равна сумме всех запасов у поставщиков:

= ;

· задана матрица стоимостей перевозок единицы товара от каждого отправителя до каждого получателя.

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

Если x_ij – количества груза, отправляемого i-м отправителем j-му получателю (их значения называют перевозками), то эти неотрицательные переменные должны удовлетворять следующим условиям:

- каждый отправитель отправит получателям весь свой запас, то есть

=a₁; =a₂; …, =a_m;

- каждый получатель получит в сумме то, что заявил:

=b₁; =b₂; …. =b_n;

- суммарная стоимость перевозок должна быть минимальной:

=min.

Это типичная задача линейного программирования с ограничениями типа равенств и ее можно решить симплекс-методом, но ряд ее особенностей позволяют упростить решение. Во-первых, все коэффициенты при х в уравнениях равны 1; во-вторых, не все m+n уравнений являются независимыми из-за равенства запасов и заявок, а только m+n–1. Поэтому можно разрешить эти уравнения относительно m+n–1 базисных переменных, выразив их через остальные свободные. Количество свободных переменных равно:

k=mn–(m+n–1)=(m–1)(n–1).

Любую совокупность (x_ij) называют планом перевозок; план считается допустимым, если он удовлетворяет условиям баланса между запасами и заявками – все заявки удовлетворены, а все запасы исчерпаны. План может считаться опорным, если в нем отличны от нуля не более
m+n–1 базисных перевозок x_ij, а остальные равны нулю. План является оптимальным, если он приводит к наименьшей среди всех допустимых планов суммарной стоимости перевозок.

Методы решения транспортной задачи не требуют манипуляций с симплекс-таблицей – решение получают с помощью простых операций с так называемой транспортной таблицей. Номера строк этой таблицы – это номера отправителей, номера столбцов – номера получателей, всего m строк и n столбцов, в ячейках таблицы записываются соответствующие перевозки. В каждом опорном плане, включая оптимальный, не более m+n–1 ненулевых базисных перевозок, остальные свободные равны нулю. Решение ТЗ сводится к следующему: найти значения положительных перевозок, суммы которых в каждой строке равны запасу соответствующего отправителя, а суммы по столбцам равны заявкам соответствующих получателей. Общая стоимость перевозок – минимальна.

Формирование опорного плана

Решение транспортной задачи в отличие от общей задачи линейного программирования всегда существует. Среди допустимых планов всегда есть оптимальный в силу заведомой неотрицательности стоимости перевозок в минимизируемой линейной форме. Для построения опорного плана существует много разработанных методов, из них простейшим является так называемый «метод северо-западного угла».

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

Циклические переносы перевозок для улучшения плана

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

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

Ценой цикла называют изменение стоимости перевозок при перемещении по циклу единицы груза – она равна сумме стоимостей перевозок по клеткам цикла, причем стоимость перевозки берется со знаком «+» для клеток с увеличивающейся перевозкой и со знаком «–» для клеток с уменьшающейся перевозкой. Очевидно, что план будет улучшаться только при перемещении перевозок по циклам с отрицательной ценой. Перевозки не могут быть отрицательными, поэтому со знаком минус могут выступать только базисные клетки с ненулевыми положительными перевозками – брать будем только там, где есть что взять. Если циклов с отрицательной ценой в таблице больше нет, значит улучшить план больше нельзя и он является оптимальным.

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

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