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

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

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

Итоговое распределение поставок по методу «северо-западного» угла

Потребители Поставщики	В1 = 150		В2 = 230		В3 = 160		В4 = 60
А1= 170	150	3	20	5		6		2
А2= 250		6	210	4	40	7		5
А3= 180		5		4	120	6	60	5

Метод «наименьшей стоимости» можно применять по строкам или столбцам. В первую очередь следует рассмотреть строки (столбцы) с максимальными объемами производства (потребления). В нашем примере (табл.2.2) такой является строка 2 с объемом производства 250 единиц. В этой строке наименьшая стоимость перевозки находится на пересечении со столбцом 2 и равна 4 единицам. Мы имеем здесь возможность полностью удовлетворить потребность второго потребителя в 230 единиц, после чего у второго поставщика останется 20 единиц ресурсов.

Следующей по объему ресурсов является строка 3, где наименьшая стоимость перевозки также находится во втором столбце. Однако в связи с тем, что потребность второго потребителя уже удовлетворена, переходим к столбцам 1 и 4, где после второго столбца наименьшая стоимость перевозки (пять единиц). Теперь полностью удовлетворяем потребность первого потребителя - 150 единиц ресурсов (выбирая из двоих того, у которого потребность больше), и у третьего поставщика остается 30 единиц ресурсов.

В последнюю очередь просматриваем строку 1. Здесь наименьшая стоимость перевозки у четвертого потребителя (2 единицы), которому отдаем всю его потребность - 60 единиц. В результате у первого поставщика остается еще 110 единиц ресурсов.

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

Cоставленный первоначальный план прикрепления потребителей к поставщикам изображен в табл. 2.3.

Таблица 2.3

Итоговое распределение поставок по методу наименьшей стоимости

Потребители поставщики	В1 = 150		В2 = 230		В3 = 160		В4 = 60
А1= 170		3		5	110	6	60	2
А2= 250		6	230	4	20	7		5
А3= 180	150	5		4	30	6		5

Первоначальный план содержит шесть перевозок» что удовлетворяет условию n + m -1 (6 = 3 + 4 - 1).

Ш а г 2. Построение системы потенциалов

Начнем с того, что строке 1 присваиваем потенциал 0, т. е. принимаем условную цену продукта в первом пункте производства равной нулю. От первого поставщика в соответствии с пер­воначальным планом продукт направляют третьему и четвертому потребителям. Следовательно, в соответствии с формулой (2.3) V₃ = 0 + 6 = 6, а V₄= 0 + 2 = 2, т.е. условная цена продукта в третьем пункте потребления равна 6 единицам, а в четвертом пункте потребления - 2 единицам. Зная условную цену продукта в третьем пункте потребления, находим условную цену по формуле (2.4) во втором и третьем пунктах производства, а именно:

U₂ = 6 – 7 = -1, U₃ = 6 – 6 = 0.

Аналогично, зная условную цену продукта в первом и втором пунктах производства, находим по формуле (2.3) условную цену продукта в первом и втором пунктах потребления, а именно:

V₁ = 0 + 5 = 5, V₂ = -1 + 4 = 3.

Вычисленные нами потенциалы строк

U₁ = 0, U₂ = - 1, U₃ = 0

и потенциалы столбцов

V₁ = 5, V₂ = 3, V₃ = 6, V₄ = 2

помещаем в дополнительных столбце и строке табл. 2.4.

Таблица 2.4