Алгоритм решения транспортной задачи методом потенциалов

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

Для описания алгоритма используем формульно-словесный способ. Рассмотрим пример транспортной задачи (табл. 3.2).

Таблица 3.2 - Исходная транспортная матрица

В табл. 3.2 по строкам матрицы представлены пункты (станции) отправления от А₁ до А₄ и объемы погрузки в тоннах – 100, 150, 90, 30 т, а по столбцам – пункты (станции) назначения от В₁ до В₅ и объемы выгрузки – 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (a_i = b_j = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А₁ и станцией выгрузки В₁, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом – 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, – оптимальным планом перевозок.

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

Операция 1. Построение опорного плана.

Опорным, называется любой допустимый, как правило, не оптимальный план, который является исходным для последующего решения. Для построения опорного плана существует ряд методов. Самый простой из них – метод северо-западного угла (табл. 3.3).

Таблица 3.3 - Метод северо-западного угла

Берем «северо-западную» клетку матрицы – это клетка А₁В₁ и записываем в нее максимально возможную поставку – 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А₁ не исчерпаны, следуем по первой строке вправо и записываем в клетку А₁В₂ корреспонденцию равную максимально возможной величине – 60 т. Таким образом получается, что ресурсы станции А₁ полностью использованы, однако спрос станции выгрузки В₂ не удовлетворен. Тогда от клетки А₁В₂ опускаемся вниз до клетки А₂В₂ и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 3.3) составит:

F_{сев-зап.} = 40 ∙ 10 + 60 ∙ 9 + 20 ∙ 7 + 110 ∙ 13 + 20 ∙ 6 + 30 ∙ 7 + 60 ∙ 1 + + 30 ∙ 2 = 2960 ткм [см. формулу (3.4)].

После расстановки корреспонденции матрица проверяется на вырождение, т. е. должно выполняться условие

, (3.5)

где m – количество строк, n – количество столбцов, N_баз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 8 = 4 + 5 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

Метод северо-западного угла имеет существенный недостаток. При его использовании не учитываются значения показателей критерия оптимальности в клетках матрицы. Поэтому поставки могут попасть в «дорогие» клетки с заведомо высокой ценой или большим расстоянием. Опорный план, полученный с использованием данного метода, как правило, далек от оптимального, что обусловливает большой объем последующих расчетов для доведения его до оптимального. Описанный метод обычно не применяется.

Наиболее предпочтительным при ручном решении транспортных задач считается метод минимальной стоимости или, как его еще называют, метод наименьшего элемента в матрице. Суть его в следующем. В транспортной матрице выбирается клетка с минимальной стоимостью (расстоянием). В нашем случае это клетка А₃В₅. В нее записывается максимально возможная поставка – это 90 т (табл. 3.4).

Таблица 3.4 - Метод наименьшего элемента в матрице

Далее отыскиваются клетка, имеющая следующее по величине расстояние. В нашей матрице это две клетки с расстоянием 2 км в пятом столбце. Однако в эти клетки поставки корреспонденцию грузов ставить нельзя, поскольку спрос станции В₅ полностью удовлетворен со станции А₃. Поэтому столбец 5 из дальнейшего построения плана исключаем. Следующие по величине показателя критерия оптимальности клетки с расстоянием 4 км это клетки А₂В₁ и А₄В₂. Выбираем одну из них, например, А₂В₁ и записываем в нее поставку 40 т. Далее идет клетка А₄В₂ – поставка 30 т, потом А₁В₄ – 50 т, А₂В₂ – 50 т. Все оставшиеся ресурсы по станциям погрузки распределяем между клетками третьего столбца в клетки А₁В₃ и А₂В₃. После составления опорного плана во избежание ошибок целесообразно проверить балансы погрузки, выгрузки и суммы корреспонденций по строкам и по столбцам матрицы. Функционал F плана, составленного методом наименьшей стоимости, равен 2150 ткм. Таким образом, построенный план значительно лучше плана, построенного методом северо-западного угла. Однако число базисных клеток в плане – 7. Это не соответствует условию (3.5), т. е. меньше требуемого на единицу. Такой план математики назвали вырожденным (случай вырождения). Случай вырождения «лечат» путем введения в матрицу недостающего количества базисных клеток с нулевыми поставками. Нулевую поставку необходимо вводить в матрицу рядом с базисной клеткой, которая обусловила «пропажу» базисной клетки.

Для того чтобы понять, почему «пропадают» поставки, обратимся к методу северо-западного угла. Из табл. 3.3 следует, что как только была заполнена «северо-западная» клетка, рядом с ней сразу появляется соседняя базисная клетка, потом еще одна и т.д. Цепочка базисных клеток без разрыва следует до «юго-восточного угла» матрицы. Однако если бы в этой цепочке появилась клетка, связывающая поставщика и потребителя с равными объемами погрузки и выгрузки, и в нее была бы записана такая же поставка, то это привело бы к пропаже базисной клетки. Описанная ситуация имела место в табл. 3.4, когда в клетку А₃В₅ была введена корреспонденция объемом 90 т, равная объемам погрузки и выгрузки по соответствующим станциям. Поэтому необходимо ввести в план дополнительную базисную клетку с нулевой поставкой. Эта клетка должна стоять рядом с клеткой А₃В₅. Из трех соседних клеток следует выбрать клетку с минимальным расстоянием, например, А₂В₅. Записываем в нее корреспонденцию, равную «0» (табл. 3.5).

Таблица 3.5 - Добавление нулевой поставки

Таким образом, причиной вырождения плана транспортной задачи является наличие поставщиков и потребителей с равными объемами погрузки и выгрузки или равными объемами сумм погрузки и выгрузки по нескольким станциям в разнообразных комбинациях. Такие случаи необходимо уметь находить для того, чтобы правильно определять места для нулевых поставок. В процессе решения задачи возможны случаи, когда число базисных клеток превышает величину «n + m – 1». Это означает появление ошибки вследствие того, что при построении опорного плана в какую-то клетку была введена не максимально возможная поставка.

Операция 2. Проверка плана на оптимальность.