Методы решения транспортной задачи

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

Одним из наиболее распространенных методов решения транспортной задачи является метод потенциалов. Отличительной чертой данного метода является его простой и ясный экономический смысл. Потенциалами называется система чисел, приписанных соответственно каждой строке i и каждому столбцу j. Экономическая интерпретация потенциалов следующая: потенциал U_i, который устанавливается для каждой строки, можно принять условно за цену продукта в пункте его производства. Потенциал V_j, который устанавливается для каждого столбца, можно принять условно за цену продукта в пункте потребления.

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

V_j = U_i + C_ij; (2.4)

U_i = V_j - C_ij . (2.5)

Приведенные выше формулы представляют собой правила расчета потенциалов.

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

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

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

Шаг1. Построение первоначального плана

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

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

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

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

Описанные действия повторяются до тех пор, пока все предложение поставщиков не будет распределено, а потребности потребителей удовлетворены.

Результаты построения первоначального плана методом северо-западного угла представлены в табл. 2.2.

Таблица 2.2